日本語の資料がすくないGCアルゴリズムについて詳細に解説します

Mark&Sweep

和訳:印づけ、掃除

アルゴリズム

ルート(用語集)を全走査し、参照されているオブジェクトを見つけ出す。
見つけたオブジェクトに対して1bitマークをし、続けてオブジェクト内で参照しているオブジェクト(枝のオブジェクト)
に対して、印をつけていく。
ルートの走査が終わると、印があるもの(図:緑)とないもの(図:水色)に別れ、
印がないものはゴミ(参照なし)と判断され解放される。

この印付けをMark、ゴミの解放をSweepという。
保守的GCによく使われる。

オブジェクトの格納領域(ヒープ領域)を作成する際に、新規にallocateする処理の為に、
フリーリストで利用可能な領域を繋ぐ(空のオブジェクトを繋ぐと考えるといいかも)
そして、ユーザーがオブジェクトを作成する際にフリーリストから一つオブジェクトを貸し出す。
Sweepフェイズではヒープ領域を全走査し、Markされていないものを解放後、フリーリストにつなぎ直す。

利点

  1. GCの実装以外の場所ではGCのことを(あまり)考えなくていい
  2. サイクルも解放できる(サイクルについてはリファレンスカウントの項を参照)

欠点

  1. スイープのため最低一度はオブジェクトを全部なめる必要がある
  2. GCの負荷が一点に集中する(停止時間が長い)

実コードを見たい場合

 ・Ruby処理系
  →読みやすいのでおすすめ
 ・BoehmGC

コメントをかく


ユーザーIDでかく場合はこちら

画像に記載されている文字を下のフォームに入力してください。

「http://」を含む投稿は禁止されています。

利用規約をご確認のうえご記入下さい

×

この広告は60日間更新がないwikiに表示されております。

Wiki内検索

Wiki内検索

フリーエリア

編集にはIDが必要です