Loading AI tools
ウィキペディアから
マーク・アンド・スイープ(mark-and-sweep)は、ガベージコレクションの実装方法およびガベージコレクタの動作方法の一つ。
基本的な方針は、あるオブジェクト(ここでは、ルートオブジェクトと呼ぶ)からのトラバース(オブジェクトから別のオブジェクトへの参照を辿ること)によって到達可能なオブジェクトに印(マーク)をつけ、印のつかなかったオブジェクトを破棄(スイープ)する、というものである。
具体的な手順の一例は次のようになる:
マーク&スイープ方式は、参照カウントにおける循環参照問題を回避し、不要なオブジェクトを確実に破棄できる。また、参照カウントを使わない分、ガベージコレクタが動作していない間の処理は高速である。
反面、ガベージコレクション自体は、参照カウント方式より処理時間がかかるため、通例次のような適当なタイミングを見計らって時々行う。
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]。
C言語やC++など、ガベージコレクタを仕様に含んでいないプログラミング言語でマーク・アンド・スイープを実行するには、マシンスタックやマシンレジスタ内にも参照がないかを確認する必要がある。しかし、通常マシンスタックやマシンレジスタの値が参照アドレスを表しているのか、ただの数値を表しているのかを区別することはできない。そこで、マシンスタックやレジスタ中の値は全て参照アドレス値であると解釈して、該当アドレスのオブジェクト回収を保留する。このような実装を保守的なガベージコレクタと呼ぶ。処理手順は以下のようになる。
C++11やBoost C++ライブラリのshared_ptr
など参照カウント方式のメモリ管理とは異なり、保守的なガベージコレクタでは、特定のライブラリやネイティブスレッドとの同時使用によりトラブルが起こることがあるので、注意が必要である。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.