16

痛々しいほど単純なものが欠けているように感じますが、Andrew Appel の『Modern Compiler Implementation in ML』ブックに従ってマーク アンド スイープ ガベージ コレクションを理解しようとしています。Mark and Sweep セクション内に Pointer Reversal (270) というタイトルの小さな段落があります。

この時点で、私はそれがどのように機能するかを理解していると思います。簡単に言えば、グラフをトラバースすると、すべてのポインターが反転し、前のポインターが一連のフィールド内に表示されます。次に、特定の要素を使い終わったら、ポインターを元に戻して、再び正しい場所を指すようにします。

それが正しければ、それはあなたに何をもたらしますか? Appel はこれを説明しようとしていますが、私は彼の言い回しを完全には理解していません。

4

1 に答える 1

16

マーキング中、オブジェクトは次の 3 つのカテゴリに分類されます。

  1. マークされていないオブジェクト
  2. マークされているが、マークされていないオブジェクトを指すことができるオブジェクト
  3. マークされ、マークされたオブジェクトのみを指すオブジェクト

マーキングが進むにつれて、オブジェクトの状態がカテゴリ 1 からカテゴリ 2 に、カテゴリ 2 からカテゴリ 3 に変化します。ガベージ コレクタは、カテゴリ 2 のすべてのオブジェクトを追跡して、マークされていないオブジェクトをすべて見つけられるようにする必要があります。しかし、その情報はどこに保存されるのでしょうか? メモリが完全にいっぱいのときにガベージ コレクションが実行されている可能性があるため、データ構造を動的に割り当てることができません。すでに割り当てられているメモリを使用して、カテゴリ 2 のオブジェクトを保持するデータ構造を構築する必要があります。ポインタ反転は、メモリを割り当てずにこれらのオブジェクトのリンク リストを作成するためのアルゴリズムです。

于 2012-04-23T16:38:01.967 に答える