4

ストップ アンド コピー ガベージ コレクターをペアとして実装する場合、2 つのメモリ バンク (古いものと空きの新しいもの) が必要です。1 つのメモリ バンクは、the-cars と the-cdrs で構成されます。基本的に、新しいアドレスを作成するとき、それは the-cars と the-cdrs へのポインターです。

新しいメモリを割り当てるときに十分なスペースがないことがわかった場合、GC を開始します。これが行うことは次のとおりです。

  • メモリーバンクを切り替える
  • 移動: 古いバンクから car と cdr を読み取り、新しいバンクにコピーして、後で使用するために古いバンクに新しいバンクへのポインタを置きます。
  • scan: メモリをループして、古いものから新しいものへすべてをコピーします。

問題は、なぜ最初にスキャンしてから移動する必要があるのか​​ということです。両方を一緒にできないのはなぜですか？

4

1 に答える 1

5

独自のコレクター (マークとスイープ、停止とコピー、世代別) を実装する、本当に素晴らしいガベージ コレクションの割り当てを行っているようです。

質問に対する一般的な回答: 通常、2 パス アルゴリズムは、スペースと時間を交換することにより、1 パス アルゴリズムよりも少ないメモリを使用します。

より具体的な答え: ストップ アンド コピー コレクターでは、(1) 最初にライブ データを新しいセミスペースにコピーし、(2) ライブ データの内部参照を調整して要素を参照するという 2 つのパスでそれを行います。新しい半空間、古いメモリを新しいメモリにマッピングします。

マッピングを行うために必要な情報は、魔法のように利用できるわけではないことを認識する必要があります。移動したメモリをリダイレクトする方法を追跡するには、メモリが必要です。そして覚えておいてください: コレクター自体はプログラムであり、限定された少量のメモリを使用する必要があります! たとえば、簿記を行うためにコレクターにハッシュ テーブルを保持することは禁止されています。規則に従っていないからです。したがって、追跡する必要があることの 1 つは、コレクターが限られた量のメモリでプレイしていることを確認することです。ストップ アンド コピー コレクターが古いセミスペースを再利用し、そこにリダイレクト レコードを書き込む理由はこれで説明できます。

この制約を念頭に置いて、ライブ セットをどのようにトラバースするかに注意する必要があることを理解することが重要です。どのアプローチを選択するかは、非常に微妙で驚くべき方法で追加のメモリを必要とする場合と必要としない場合があります。特に、一般的な場合の再帰は無料ではありません! 技術的には、最初のパスでは、コピーのターゲットとしてだけでなく、ライブ データをウォークスルーする再帰プロセスを実装するために使用するコントロールスタックのファンキーな表現として、新しい半空間を使用する必要があります。

具体的には、ライブ セットをコピーするために次のようなワンパス アプローチを行う場合:

;; copy-live-set: number -> void
;; copies the live set starting from memory-location.

Pseudocode:

to copy-live-set starting at memory-location:

  copy the block at memory-location over to the new semispace, and

  record a redirection record in the old semispace

  for each internal-reference in the block:

      recursively call copy-live-set at the internal-reference if
      it hasn't been copied already

      remap the internal-reference to that new memory location

すると、メモリがめちゃくちゃになっていることに驚くかもしれません。ここでの再帰は反復的ではないため、上記はコレクターがランタイム環境に対して行っている約束を破ります! コントロール スタック スペースを消費します。ライブ セットのトラバーサル中は、歩いている構造物の深さに比例してコントロール スタック スペースが消費されます。おっと。

ライブ セットをウォークスルーする別の方法を試してみると、限定された小さなコントロール スタックの使用を保証しながら、ライブ セット全体をトラバースする良い方法があることが最終的にわかるはずです。ヒント: グラフ トラバーサル アルゴリズムを単純な while ループとして記述し、コンテナーを使い果たすまで次にアクセスするものを保持する明示的なコンテナーを使用する方法を検討してください。正しく目を細めると、新しい半空間の中間値がそのコンテナーのように見えます。

一定の制御スタック スペースでライブ セットをトラバースする方法を発見すると、完全なコピー アンド リライト内部参照を実行するためにこれら 2 つのパスが必要になることがわかります。これらの詳細を気にするのは厄介ですが、ガベージ コレクターが実際にどのように機能するかを確認することは重要です。実際のコレクターは、コレクション中に制限されたメモリを確実に使用するために、スタックの使用を制御するために、このようなことを行う必要があります。

要約: 2 パス アルゴリズムは、ある程度の時間を犠牲にしてメモリを使用するのに役立つソリューションです。しかし、パフォーマンスに関してはあまりお金を払っていません。ライブ セットを 2 回通過しますが、プロセスはライブ セットのサイズに比例します。

歴史: Cheney's Algorithmを参照し、影響力のある論文の強調のタイトルに注意してください: " A Nonrecursive List Compacting Algorithm ". この 1 つの強調表示された単語「非再帰」が、2 パス アプローチの動機の鍵です。これは、制御スタックの消費を回避しようとしています。Cheney の論文は、Fenichel と Yochelson による論文「A LISP Garbage-Collector for Virtual-Memory Computer Systems」を拡張したものであり、そこで著者は基本的に再帰的でスタックを使用するアプローチを最初に提案しました。状況を改善するために、Fenichel と Yochelson は、非再帰的 (しかし複雑な!) Schorr-Waite DFS アルゴリズムを使用することを提案しました。トラバーサルを行います。Cheney のアプローチは、トラバーサルがより単純であるため、改善されています。

于 2013-05-20T22:32:25.050 に答える