第一種實(shí)用和完善的垃圾收集算法是 J. McCarthy 等人在 1960 年提出并成功地應(yīng)用于 Lisp 語言的標(biāo)記－清除算法。仍以餐巾紙為例，標(biāo)記－清除算法的執(zhí)行過程是這樣的：
午餐過程中，餐廳里的所有人都根據(jù)自己的需要取用餐巾紙。當(dāng)垃圾收集機(jī)器人想收集廢舊餐巾紙的時(shí)候，它會(huì)讓所有用餐的人先停下來，然后，依次詢問餐廳里的每一個(gè)人：“你正在用餐巾紙嗎？你用的是哪一張餐巾紙？”機(jī)器人根據(jù)每個(gè)人的回答將人們正在使用的餐巾紙畫上記號(hào)。詢問過程結(jié)束后，機(jī)器人在餐廳里尋找所有散落在餐桌上且沒有記號(hào)的餐巾紙（這些顯然都是用過的廢舊餐巾紙），把它們統(tǒng)統(tǒng)扔到垃圾箱里。
正如其名稱所暗示的那樣，標(biāo)記－清除算法的執(zhí)行過程分為“標(biāo)記”和“清除”兩大階段。這種分步執(zhí)行的思路奠定了現(xiàn)代垃圾收集算法的思想基礎(chǔ)。與引用計(jì)數(shù)算法不同的是，標(biāo)記－清除算法不需要運(yùn)行環(huán)境監(jiān)測(cè)每一次內(nèi)存分配和指針操作，而只要在“標(biāo)記”階段中跟蹤每一個(gè)指針變量的指向——用類似思路實(shí)現(xiàn)的垃圾收集器也常被后人統(tǒng)稱為跟蹤收集器（ Tracing Collector ）
伴隨著 Lisp 語言的成功，標(biāo)記－清除算法也在大多數(shù)早期的 Lisp 運(yùn)行環(huán)境中大放異彩。盡管最初版本的標(biāo)記－清除算法在今天看來還存在效率不高（標(biāo)記和清除是兩個(gè)相當(dāng)耗時(shí)的過程）等諸多缺陷，但在后面的討論中，我們可以看到，幾乎所有現(xiàn)代垃圾收集算法都是標(biāo)記－清除思想的延續(xù)，僅此一點(diǎn)， J. McCarthy 等人在垃圾收集技術(shù)方面的貢獻(xiàn)就絲毫不亞于他們?cè)?nbsp;Lisp 語言上的成就了。