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

GC編集する

最終更新： author_nari author_nari 2010年03月14日(日) 20:47:11履歴


このWikiが目指す所

　ずばり
　「日本語によるGCアルゴリズムの詳細解説」
　です。
　
　このWikiには最新の技法から古い技法まで，自分のまとめたものをちまちま書いていくつもりです。
　編集は自由ですので，よかったら何か書いてもらえるとありがたいです．

　id:authorNariが管理人です．
　何か有りましたら，authorNari at gmail.com の方へどうぞ．

GCとは？

　どこからも参照されなくなった(つまり不要)メモリ領域を自動で掃除してくれる便利なやつ。
　本当はmalloc/freeと手動でメモリ管理しなければならない所（C言語など）を
　あるタイミング(使う側には指定できない事が多い)でいらない領域をfreeしてくれる。
　本Wikiは概要についてはあんまり説明しないのでガベージコレクション(wikipedia)を参照
　
　GCは二つの略語をさします。
  • (garbage collection) ガベージコレクション -- プログラム上で不要となったメモリを回収する動作。
  • (garbage collector) ガベージコレクタ -- 上記を実現するメカニズム。

　本Wikiでは、統括して「GC」と呼ぶ事にします。

GCを学ぶ前に知っておく事

専門用語を知らないと中々辛いので、まとめています。
用語集

実行時メモリ構造



これからの物事を理解するために、プログラムが動いている時のメモリ領域の構造を図 に示す。
大まかには、Java, ML, C 言語も含めほとんどの言語は似たような構造になる。
ヒープ内の小さい四角はオブジェクトを表す。
また、あるオブジェクトA の中に含まれるポインタが、別のオブジェクトB を指していることがある。
(record の中にrecord がある場合や、オブジェクトのフィールドに別のオブジェクトを含む場合など)
図中では参照関係を、A からB への矢印で表す。
  • スタックには、局所変数や関数呼び出しの履歴などが格納される。(話をごく簡単にすると) 関数呼び出しが起こると伸びて、return が起こると縮む。
  • 大域変数を格納する領域が用意される。定数が格納される領域も独立に用意される場合が多い。
  • レジスタは、関数の引数、計算の途中結果など様々な値をとる。オブジェクトを指すポインタの可能性もある。
  • ヒープは自由な順番でメモリ領域を確保/解放できる領域である。
　オブジェクト作成(C ではmalloc)を行なうと、ヒープの中に必要な大きさの領域が確保される。
  • 図には示していないが、プログラムのコード領域もどこかにある。

基本アルゴリズム編

世の中にあるGCアルゴリズムはこの3パターンに最終的に集約される．
基本中の基本のアルゴリズムである．

Reference Counter

参照カウント(GC)

Mark&Sweep

印づけ、掃除

Copying

生きてるものだけ違う入れ物にいれて，死んでるものは入れ物毎捨てる

応用アルゴリズム編

ここでは基本アルゴリズムを応用し、欠点を解決したアルゴリズムの紹介をする。

IncrementalGC

ちょっとづつGC

世代別GC

若いやつらを優先するGC

スナップショット型GC

開始時の写真を元にゴミ掃除

LazySweep

遅延Sweep

TwoFinger

空いてる所につっこむ

Lisp2

先頭にずらす

Partial Mark and Sweep -Cycle Collection-

部分的なMarkandSweep

Mostly Parallel GC

極力ParallelなGCを行う

train gc

Old世代を車両に分割してインクリメンタルにGC

MostlyCopyingGC(Bartlett 1989)

あいまいなポインタを考慮し，極力CopyingをするGC

TreadmillGC(Barker 1992)

Copyingに似たnon-movingなインクリメンタルGC

補足

conservativeGC(保守的GC)とexactGC(絶対的GC)

大抵のGCでは最初にルートの走査を行う。
具体的には参照先のアドレス(ポインタ)がヒープ領域内にあるかどうか？という
チェックをルートすべてに行うのだが、
この際に、もし、ヒープ領域内を指す数値が見つかった場合、
それがプログラム中に使用された数値(intなど)なのか、オブジェクトへの参照(ポインタ)なのか
判断する事ができない。
この問題にどう対処するかによって、conservativeGCとexactGCの2種類にGCは分けられる。
conservativeGC(保守的GC)
conservativeGCはこの場合、オブジェクトへの参照では無く、只の数値だったとしても
そのオブジェクトの解放は行わない。
つまり、数値であった場合にポインタの値を変更(CopyGCなど)した時はプログラムとして致命的である為、
何も触らない方向に倒すという事だ。
まさに保守的なGCだ。

利点
  • 無駄な細工をせずに済むので処理が軽い
  • 実装が楽

欠点
  • 回収されないゴミが残る可能性がある
  • CopyingGCなどオブジェクトを移動する事ができない。
　→解決方法1：オブジェクトとポインタの間に一枚ハンドルを噛まして抽象化する。
　　　　　　　　実際にハンドルの数値だけが変わり元のポインタに影響はない。
　　　　　　　　(間接参照になる為、通常の処理が遅くなる欠点)

詳細な解説
exactGC(絶対的GC)
conservativeGCではなんでもオブジェクトとみなして、ゴミが残る可能性があったが
exactGCではポインタと数値をはっきり区別し、ゴミを残さず回収する事をポリシーとする。
ポインタと数値を区別する具体的な方法は、
  • 整数値の範囲を1 bit減らして、その1bitをタグビットとして利用する。
  • stack map方式
がある。

ほとんどの処理系は，処理系自身がルートを提供する事であいまいなポインタがなくなりexactGCとなる．
この場合，GCにより協力的な処理系と言える．

利点
  • ゴミを全て回収するのでメモリ効率がいい
  • オブジェクトの移動が楽にできる。(コンパクション)

欠点
  • 色々と制限がつく
  • 実装が面倒

ちなみに「絶対的GC」という訳はオリジナル。べたに訳すと「確実なGC」になる。
またexactと同じ意味でprecise（プリサイス）と呼ぶ事もある．
（英語ではこっちの方が多いかも）

writebarrier

Mark&Sweepアルゴリズムでは「Root から到達可能かどうか」をチェックするためにオブジェクトにマークを行っていたが、
これとは別に「書き換えられたオブジェクト」をチェックするために別種類の印をつける。
例えば、以下のような Java プログラムを実行しているスレッドが、 object1 のフィールドになんらかのオブジェクトの参照を書き込む場合、
object1 に「書き込まれた」という印を付けるのである。
この処理を ライトバリア (write barrier) と呼ぶ。
object2 が null でない場合は、どんなオブジェクトでもチェックを行う。
void method( Class1 object, Class2 object2 ){ object1.field = object2; }
ライトバリアされた後の、メモリ中のイメージとしては下の図のようになる。



finalize


用語集

個人的にわからなかった単語たち

tenured

和訳：保有権のある、終身在職権のある、身分保障のある
世代別GCの古い世代を置く領域の事

ミュテータ

オブジェクトの状態を書き換える者、すなわちユーザープログラムのこと

scavenge

和訳：清掃をする

sweep

和訳：ゴミを掃き出す

root

和訳：根、根源
GCにおいて、「確実に必要なオブジェクト」。
スタック領域、レジスタ、グローバル変数、定数などから参照されているヒープ領域を指す。
このオブジェクトを起点に必要なオブジェクトが探索され、探索されなかったオブジェクトがGCの対象になる。

chunk

和訳：大きな塊
GCの対象になる塊、場合によってはオブジェクトだったりデータだったり

compaction

Mark&Sweepを何度も繰り返すとメモリの断片化が起こるが、
その状態を整頓するする事を指す。
Windowsで言う所のデフラグの様なもの。

allocate

和訳：割り当てる
メモリ割り当てる行為。GC関連の資料では管理対象のオブジェクトを作成する事を指すことが多い。

promote

和訳：昇進させる、昇格させる
新世代から旧世代に移動させること、殿堂入りとも言う。

starvation

和訳：飢餓状態
要求に応じられるだけのフリーなデータがなくなった状態

ルート挿入

ルート集合から直接さされているセル(データ)に一括して印をつけ、GC用スタックに挿入すること

セル

GCではよくLispなどの処理系で説明が行われる。オブジェクトと同義だと思ってよい。

参考文献

  • ガベージコレクションのアルゴリズムと実装（拙著です）

Wiki作者

id:authorNari
このエントリーをTumblrにポストClip to Evernoteこのエントリーをはてなブックマークに追加
GC - GCアルゴリズム詳細解説 先頭へ

このページへのコメント

管理人様 、はじめまして。鈴木幸子と申します。
恐れながら貴サイトseesaawiki.jp/w/author_nari/ にバナーやtextlinkや記事掲載をお願いしたく ご連絡をさせていただきました。
もし興味がございましたらお返事頂ければと思います。
ご返信をいただければ、どちらのサイト(URL)の管理人様を教えていただきます。
よろしくお願いいたします。

0
Posted by 鈴木幸子 2018年06月24日(日) 15:28:24
http://worldcup2018-japan.com/ 返信

GC鐃緒申鐃暑ゴ鐃所ズ鐃緒申楮找鐃緒申鐃� - Seesaa Wiki鐃淑ワ申鐃緒申鐃緒申鐃緒申 for 鐃緒申鐃殉￥申鐃夙フワ申鐃緒申 ��≪�潟�������若����遺����������� http://www.pslcbi.com/moncler2014.html

0
Posted by ��≪�潟�������若����遺����������� 2013年12月10日(火) 04:54:02 返信

GC鐃緒申鐃暑ゴ鐃所ズ鐃緒申楮找鐃緒申鐃� - Seesaa Wiki鐃淑ワ申鐃緒申鐃緒申鐃緒申 for 鐃緒申鐃殉￥申鐃夙フワ申鐃緒申 ��≪�潟�������若�� 2014 http://www.pslcbi.com/moncler2014.html

0
Posted by ��≪�潟�������若�� 2014 2013年12月08日(日) 03:42:37 返信

アイフォン4s ケース
アイフォンケース http://www.cnbwe.com/

0
Posted by アイフォンケース 2013年11月09日(土) 13:26:27 返信

メンズ ダッフルコート
バーバリーチェック http://www.bet365kaihu.org/カジュアルシャツ-mxz5zj-4.html

0
Posted by バーバリーチェック 2013年10月31日(木) 12:39:55 返信

コメントをかく


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

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

Wiki内検索

メニュー

最近更新したページ

最新コメント

  • 2018-06-24

  • GC by 鈴木幸子

  • 2014-12-16

  • GC/standard by モンクレールウンアウトレット

  • 2014-01-19

  • GC/extend by ケイトスペード アウトレット
  • GC/extend/TwoFinger by シーバイクロエ 財布 新作 2013

  • 2013-12-26

  • GC/extend/TwoFinger by アグ ブーツ 正規品
  • GC/extend by UGG ブーツ メンズ

  • 2013-12-10

  • GC by ��≪�潟�������若����遺�����������

  • 2013-12-09

  • GC/standard/Copying by ��≪�潟�������若�� ���������

  • 2013-12-08

  • GC/standard/Copying by �����若����� ��≪�潟�������若��
  • GC by ��≪�潟�������若�� 2014

タグ

このウィキの読者になる

更新情報がメールで届きます。

読者数：3名

このウィキの読者になる

Wiki内検索

フリーエリア

編集にはIDが必要です