9

私はストップ・ザ・ワールド、インクリメンタル、パラレル、コンカレント、(ソフト/ハード) リアルタイム ガベージ コレクタの概念を知っています。しかし、私は主に並行GCを理解できません。同時GCとの違いは？違いは何ですか？なぜほとんどと呼ばれるのですか？

4

2 に答える 2

7

私はストップ・ザ・ワールド、インクリメンタル、パラレル、コンカレント、(ソフト/ハード) リアルタイム ガベージ コレクタの概念を知っています。しかし、私は主に並行GCを理解できません。同時GCとの違いは？違いは何ですか？なぜそれがほとんどと呼ばれるのですか？

他の多くの主題と同様に、ガベージ コレクションは用語のあいまいさの霧に包まれています。ベームは、従来の用語を型にはまらない方法で使用することで特に悪名高いですが、彼は従来の意味がまだ骨化されていない時代にこの分野の先駆者だったので、彼を許すべきです! :-)

私が理解しているように、stop-the-world GC は、ヒープ全体をマークする場合など、GC サイクルの全期間にわたってすべてのミューテーター スレッドを一時停止するアルゴリズムを指します。たとえば、.NET サーバー GC はこれを行い、結果として 300 ミリ秒という膨大な一時停止時間が発生します。インクリメンタル GC は、OCaml の GC の「主要なスライス」など、各マイナー GC サイクルで主要な GC 作業を少し実行します。並列とは、GC が複数のスレッドを使用してガベージ コレクションのプロセスを高速化することを意味します。同時 GC とは、GC が .NET ワークステーション GC などのミューテーターと同時に実行されることを意味します。リアルタイムを定義するのは難しく、本来は制限付きの最大一時停止時間を意味していましたが、現在では最小ミューテーター使用率 (MMU) も意味し、ミューテーターの実行を決して許可しないことでミューテーターを長時間一時停止しないという GC の病理学的問題を回避します! リチャード・ジョーンズの新しい本によると、オンザフライ GC は、一度に複数のミューテーターを一時停止することはありません (つまり、stop-the-world フェーズはありません)。彼は、ミューテーターが互いに独立して一時停止されることを意味していたのではないかと思います。最後に、ほぼ同時の GC は、すべてのミューテーター スレッドを同時に一時停止するものですが、短時間だけであり、任意に長い GC サイクルではありません。したがって、ミューテーターは、GC の実行中にほとんどの時間自由に実行できます。このため、これは「ほとんど同時」の GC と呼ばれます。ほとんど同時の GC は、すべてのミューテーター スレッドを同時に一時停止するものですが、短時間だけであり、任意に長い GC サイクルではありません。したがって、ミューテーターは、GC の実行中にほとんどの時間自由に実行できます。このため、これは「ほとんど同時」の GC と呼ばれます。ほとんど同時の GC は、すべてのミューテーター スレッドを同時に一時停止するものですが、短時間だけであり、任意に長い GC サイクルではありません。したがって、ミューテーターは、GC の実行中にほとんどの時間自由に実行できます。このため、これは「ほとんど同時」の GC と呼ばれます。

ほとんどの (すべて?) 主要な GC がこのカテゴリに分類されるため、「ほぼ同時に」という分類は重要です。これは、一時停止時間とスループットの間の適切なトレードオフを提供するためです。たとえば、.NET ワークステーション GC は、グローバル ルートのスナップショットを取得するときにすべてのミューテーター スレッドを一時停止しますが、マークとスイープの間はそれらを再開します。

于 2011-11-01T16:47:02.690 に答える
2

Bohem、Demers、および Shenker による論文「Mostly Parallel Garbage Collection」 (Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation、SIGPLAN Notices 26、6 (1991 年 6 月)、pp. 157-164)。

あの人たちは書く：

仮想メモリの対応するページが書き込まれるたびに自動的に設定される一連の仮想ダーティ ビットを維持できると仮定します。(この機能の受け入れ可能な実装は、ページを書き込み保護し、結果として生じる書き込み障害をキャッチすることによって取得できます。基盤となる OS カーネルを変更する必要はありません。もちろん、OS カーネルでの実装はより効率的です。) stop-the-world 操作については、次の収集アルゴリズムを検討してください。コレクションの開始時に、すべての仮想ダーティ ビットをクリアします。従来のトレース操作をミューテーターと並行して実行します。仮想ダーティ ビットは、ミューテータの書き込みを反映するように更新されます。トレースが完了したら、ワールドを停止し、ダーティ ページにあるすべてのマークされたオブジェクトからトレースします。

...

このアルゴリズムでは、並列トレース フェーズが真の到達可能セットの近似値を提供します。この並列トレース プロセスによってマークされていない、実際に到達可能な唯一のオブジェクトは、トレース後に書き込まれたマークされたオブジェクトから到達可能でなければなりません。stop-the-world トレース フェーズは、そのようなすべてのオブジェクトからトレースするため、最終的に本当に到達可能なオブジェクトがマークされていないままになることはありません。

ガベージ コレクターのトレースについて言及する場合、指定された「ルート ノード」(通常はプログラムのレジスタ) から開始し、到達可能なすべてのオブジェクトへのポインターをたどるコレクターについて言及しています。到達できないものはすべてゴミです。

つまり、ほぼ並列のコレクターは、作業の大部分を並行して実行し、プログラムの実行を停止して、コレクターの実行中にプログラムが行った変更を修正します。したがって、「ほぼ平行」です。

于 2011-10-13T05:01:46.167 に答える