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