マーク・アンド・スイープ
出典: フリー百科事典『ウィキペディア（Wikipedia）』
マーク・アンド・スイープ(Mark and Sweep)は、ガベージコレクタの動作方法の一つ。
目次 |
[編集] 方法
基本的な方針は、あるオブジェクト(ここでは、ルートオブジェクトと呼ぶ)からのトラバース(オブジェクトから別のオブジェクトへの参照を辿ること)によって到達可能なオブジェクトに印（マーク）をつけ、印のつかなかったオブジェクトを破棄（スイープ）する、というものである。
具体的な手順の一例は次のようになる：
- ルートオブジェクトに印をつける
- 直前に印をつけたオブジェクトから、1回のトラバースで到達可能なすべてのオブジェクトに印をつける（すでに印がついているものについては何もしない）
- 2の操作を、印がつかなくなるまで行う
- 印がついてないオブジェクトを破棄する
[編集] 特徴
この方式は、参照カウントにおける問題を回避し、不要なオブジェクトを確実に破棄できる。また、参照カウントを使わない分、ガベージコレクタが動作していない間の処理は高速である。
反面、ガベージコレクタ自体は、参照カウント方式より処理時間がかかるため、参照カウントによるごみ集めと併用されることがある。いくつかのシステムでは、参照カウントによるごみ集めを常に行い、マークアンドスイープは、次のような適当なタイミングを見計らって時々行う。
- メモリが不足してきたとき
- システムが何もしていないとき
- プログラムから明示的な指令があったとき(Javaの
System.gcメソッドなど）
[編集] 保守的なガベージコレクタ
C++など、ガベージコレクタを内蔵していないプログラミング言語で、マーク・アンド・スイープを実行するには、保守的なガベージコレクタを使うのが、一般的である。保守的ＧＣでは、以下のようにメモリが使用中か判定する。
- まず、使用中であることが確実であるポインタを調べる。具体的には、スタック領域や定数領域にあるポインタなどである。
- そして、使用中であることが確実なポインタが参照しているポインタを順々にたどっていき、使用中のメモリやオブジェクトの一覧を作る。
- しかし、CやC++では、int型の変数にポインタを入れることもあるので、ポインタかデータかわからないものは、ポインタと見なす。仮想メモリを含めた、全メモリの全ての領域を１つのプロセスで使うということは、現実的にはほぼ無く、しかも、ポインタとして有効なのは、確保したメモリ領域の先頭だけである。なので、統計的には、データをポインタと誤認識してしまう確率は低い。しかし、使用中のメモリを誤って解放してしまうことの方が、解放しないことよりも、圧倒的に問題なので、使用中かどうか疑わしいメモリは解放しない。それゆえ、保守的と呼ばれる。
- そうして、使用中でないことが確実なメモリの一覧を作り、それを解放する。
Boost C++ Library の smart_ptr など、参照カウント法のガベージコレクタで、問題が起こることは少ないが、保守的なガベージコレクタでは、特定のライブラリやネイティブスレッドとの同時使用によってはトラブルが起こることがあるので、注意が必要である。
[編集] 実装例
- Boehm-Demers-Weiser conservative garbage collector - 1980年代から使われている、C/C++用の最も有名な保守的なガベージコレクタ。
