マーク・アンド・スイープ

基本的な方針は、あるオブジェクト（ここでは、ルートオブジェクトと呼ぶ）からのトラバース（オブジェクトから別のオブジェクトへの参照を辿ること）によって到達可能なオブジェクトに印（マーク）をつけ、印のつかなかったオブジェクトを破棄（スイープ）する、というものである。

具体的な手順の一例は次のようになる：

1. ルートオブジェクトに印をつける
2. 直前に印をつけたオブジェクトから、1回のトラバースで到達可能なすべてのオブジェクトに印をつける（すでに印がついているものについては何もしない）
3. 2の操作を、印がつかなくなるまで行う
4. 印がついてないオブジェクトを破棄する

マーク＆スイープ方式は、参照カウントにおける循環参照問題を回避し、不要なオブジェクトを確実に破棄できる。また、参照カウントを使わない分、ガベージコレクタが動作していない間の処理は高速である。

反面、ガベージコレクション自体は、参照カウント方式より処理時間がかかるため、通例次のような適当なタイミングを見計らって時々行う。

• メモリが不足してきたとき
• システムが何もしていないとき
• プログラムから明示的な指令があったとき（JavaのSystem.gc()メソッドや.NET FrameworkのSystem.GC.Collect()メソッドなど）

参照カウントによる寿命管理をメインに、マーク＆スイープなどを補助的に併用するシステムや、世代別ガベージコレクションのようにコピーGCとマーク＆スイープを組み合わせる方式もある。Pythonは参照カウントをメインにして、伝統的なマーク＆スイープとは逆順の探索アルゴリズムによる世代別GCも補助的に併用している^[1]。

マーク＆スイープは、GCルートからの参照の到達可能性を追跡するため、オブジェクトの数が増えるほどGCの処理時間が増加していく。また、GC実行中はアプリケーション全体の動作（GC以外のすべてのスレッド）をいったん停止する必要がある（ストップ・ザ・ワールド）。この停止時間の問題を改善するため、世代別GCと組み合わせたうえで、アプリケーションの停止時間を最小化して並行動作するコンカレント・マーク・スイープ (Concurrent Mark Sweep, CMS) と呼ばれる方式も考案されている^[2]。ただしCMSにも問題点はあり、JavaではCMSの代わりにガベージファースト (G1) と呼ばれる発展方式が推奨されている^[3]。