1) THE LOCATION OF "BEIS AVTINAS"
OPINIONS: The Mishnah states that Kohanim stand guard in three places in the Beis ha'Mikdash: in Beis Avtinas, Beis ha'Nitzotz, and Beis ha'Moked. Beis Avtinas was so called because the Avtinas family made the Ketores there (see Yoma 38a). It was there that the Kohen Gadol was taught how to perform the Chafinah of the Ketores on Erev Yom Kippur and was required to take an oath that he would perform all of the Avodos in accordance with the Halachah (Yoma 18b). The Gemara in Yoma (19a) explains that the Kohen Gadol had a personal chamber in Beis Avtinas.
The Gemara there in Yoma explains that the Kohen Gadol's chamber of Beis Avtinas was located in either one of two places. It was either in the northern part of the Azarah, near the Lishkas ha'Gazis, or it was in the southern part of the Azarah next to the Mikvah, which was located above the Sha'ar ha'Mayim.
The Rishonim offer more exact descriptions as to the location of the Kohen Gadol's chamber.
(a) The RAMBAM (Perush ha'Mishnayos, Midos 5:1) explains that the chamber was next to the private Mikvah of the Kohen Gadol, which was above the Sha'ar ha'Mayim, one of the southern gates of the Azarah (see diagram of the TIFERES YISRAEL #34, or diagram of the Vilna Shas #64), as the Gemara says in its second suggestion.
In the Rambam's diagram of the Azarah, Beis Avtinas is slightly to the east of the Sha'ar ha'Mayim (since Leviyim, and not Kohanim, would stand guard at the gate itself; see Insights to Tamid 27a). (There appears to be a printer's error in the diagram of the Tiferes Yisrael, as #33 and #34 seem to be switched. The number 33, which appears slightly to the east of the gate, is lost likely where Beis Avtinas is, as the Rambam draws it, while number 34 is obviously the gate itself).
(b) The ROSH (27a, DH Al) writes that the Lishkas Beis Avtinas was not located on one of the gates of the Azarah. Rather, it was in one of the corners of the Azarah. The RA'AVAD (27a) adds (based on the Gemara in Yoma) that it was located near -- but not actually in -- either the southeastern or the northeastern corner of the Azarah.
2) THE LOCATION OF THE "BEIS HA'MOKED"
OPINIONS: The Mishnah states that Kohanim stand guard in three places in the Beis ha'Mikdash: in Beis Avtinas, Beis ha'Nitzotz, and Beis ha'Moked. The Mishnah says that Beis ha'Moked was built like a dome. It was a large structure with stone "Rovdim" (ledges) protruding all around. The elders of the Beis Av would sleep there, with the keys to the Azarah in their hands, while the Pirchei Kohanim (young Kohanim) would sleep on the floor.
Where exactly is the Beis ha'Moked?
(a) The Mishnah in Midos (1:5) states that Sha'ar Beis ha'Moked was the northeastern gate of the Azarah (see diagram of the TIFERES YISRAEL #43, or diagram of the Vilna Shas #51).
The RAMBAM (Hilchos Beis ha'Bechirah 5:9) explains that the Beis ha'Moked itself was located to the north of the Azarah. It was built entirely on the outside of the Azarah, between the Azarah and the Cheil. It was part-Kodesh and part-Chol, since it had two entrances, one leading into the Azarah and one leading outwards. This is also the opinion of the RASH in Midos (1:5).
(b) RASHI in Yoma (15b, DH Shtayim) writes that the Beis ha'Moked was built partially in the Azarah and partially out of the Azarah. This is the Girsa of many Rishonim in the Tosefta in Ma'aser Sheni (ch. 5) as well. According to Rashi, it was part-Kodesh since it was built partially in the Azarah.