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

マーク・アンド・スイープ（mark-and-sweep）は、ガベージコレクタの動作方法の一つ。

方法

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

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

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

特徴

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

反面、ガベージコレクタ自体は、参照カウント方式より処理時間がかかるため、参照カウントによるごみ集めと併用されることがある。いくつかのシステムでは、参照カウントによるごみ集めを常に行い、マークアンドスイープは、次のような適当なタイミングを見計らって時々行う。

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

保守的なガベージコレクタ

C言語やC++言語など、ガベージコレクタを仕様に含んでいないプログラミング言語でマーク・アンド・スイープを実行するには、マシンスタックやマシンレジスタ内にも参照がないかを確認する必要がある。しかし、通常マシンスタックやマシンレジスタの値が参照アドレスを表しているのか、ただの数値を表しているのかを区別することは出来ない。そこで、マシンスタックやレジスタ中の値は全て参照アドレス値であると解釈して、該当アドレスのオブジェクト回収を保留する。このような実装を保守的なガベージコレクタと呼ぶ。処理手順は以下のようになる。

1. まず、使用中であることが確実である参照を調べる。具体的には、スタック領域や定数領域にあるポインタ変数などである。見つかった参照から到達可能なオブジェクトに印をつける。
2. そして、このオブジェクトからの参照を順々にたどっていき、使用中のメモリやオブジェクトの一覧を作る。
3. この時、スタック上やオブジェクト内にある参照でないデータも、参照をあらわすデータと見なして処理を進める。使用中のメモリを誤って解放してしまうことの方が、解放しないことよりも圧倒的に問題なので、使用中かどうか疑わしいメモリは解放しないのが安全である。それゆえ、保守的と呼ばれる。
4. そうして、使用中でないことが確実なメモリの一覧を作り、それを解放する。

Boost C++ Library の shared_ptr など 参照カウント法のメモリ管理とは異なり、保守的なガベージコレクタでは、特定のライブラリやネイティブスレッドとの同時使用によりトラブルが起こることがあるので、注意が必要である。

実装例

• Boehm-Demers-Weiser conservative garbage collector - 1980年代から使われている、C/C++用の最も有名な保守的なガベージコレクタ。