Download presentation
Presentation is loading. Please wait.
1
コンパイラ 2012年11月15日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp)
2
コンパイラと実行環境の連携２ メモリに関係するバグを未然に防ぎたい 使用されていないメモリの自動回収・再利用 今回の内容
ごみ集め(Garbage Collection) メモリの断片が、使用中かどうかを判定 今回の内容 GCのアルゴリズム トレース式 印掃式GC 複写式GC 参照カウント式
3
トレース式GCの考え方 「参照する」「参照される」という関係を有向グラフ化する GCのアルゴリズム
Javaでは、基本型は値型なのでここでは無関係。 Javaでは、オブジェクト変数は「参照する」関係の出発点 木ではないが出発点なので、図では「ルート」としている 「参照される」対象はインスタンス インスタンスにもオブジェクト変数を定義できるので、グラフになる GCのアルゴリズム 印掃式 すべてのルートからグラフをたどり、インスタンスに印をつける 最後まで印のつかなかったインスタンスを回収・再利用する 複写式 ヒープを２つにわけ、一方の領域がいっぱいになるまで割り付ける 空きがなくなったとき、他方の領域へルートからたどりつつコピーする
4
印掃式GC (138ページ a) 順に割り付けて使用中
レジスタ群 レジスタ R1 レジスタ R32 … 実行時スタック 空き領域 スタックフ レーム C レーム B レーム A SP→ 大域変数群 大域変数 a 大域変数 b ルート データ構造Ａ データ構造Ｂ データ構造Ｃ データ構造Ｄ データ構造Ｅ ヒープ領域 印掃式GC (138ページ a) 順に割り付けて使用中
5
印掃式GC (138ページ b) GCが作業中 レジスタ群 レジスタ R1 レジスタ R32 … 実行時スタック 空き領域 スタックフ
レーム A SP→ 大域変数群 大域変数 a 大域変数 b ルート 印 データ構造Ａ 印 データ構造Ｂ 印 データ構造Ｃ 印 データ構造Ｄ データ構造Ｅ ごみ、空き領域に還元する ヒープ領域 印掃式GC (138ページ b) GCが作業中
6
複写式GC (140ページ a) 順に割り付け中 レジスタ群 レジスタ R1 レジスタ R32 … 実行時スタック 空き領域 スタックフ
レーム B レーム A SP→ 大域変数群 大域変数 a 大域変数 b ルート to 領域 from 領域 データ構造Ａ データ構造Ｂ データ構造Ｃ データ構造Ｄ データ構造Ｅ ヒープ領域 複写式GC (140ページ a) 順に割り付け中
7
複写式GC (140ページ b) 空きがなくなりGC起動
レジスタ群 レジスタ R1 レジスタ R32 … 実行時スタック 空き領域 スタックフ レーム C レーム B レーム A SP→ 大域変数群 大域変数 a 大域変数 b ルート from 領域 to 領域 済 データ構造Ａ データ構造A 済 データ構造Ｂ データ構造B 済 データ構造Ｃ データ構造C すべてごみ！ 済 データ構造Ｄ データ構造D データ構造Ｅ ヒープ領域 複写式GC (140ページ b) 空きがなくなりGC起動
8
複写式GCにおけるデータ構造の移動 複写の際にインスタンスが移動する ルートからたどっている最中に参照を更新する
参照は、Javaではオブジェクト変数、Cではポインタ 参照への参照（ポインタへのポインタ）を引数に関数を呼ぶ。 void updateReference(reference *field){ /* fieldはポインタへのポインタ */ reference ref = *field; if(ref != null){ if(!alreadyMoved(ref)){ reference new_address = copyToToArea(ref); *field = new_address; markAsMoved(ref, new_address); } else { *field = getForwardPointer(ref);
9
参照カウント式GC データ構造の中にカウンタを設けておく カウンタの値が０になれば空き領域に加え再利用する 欠点もある
参照されると+１、参照されなくなったら-１する そのインスタンスを参照しているオブジェクト変数の数になる オブジェクト変数への代入時に処理 カウンタの値が０になれば空き領域に加え再利用する 欠点もある カウンタを操作するオーバーヘッドが大きい 「参照する」「参照される」関係グラフにサイクルがあるとき、 そのサイクル全体がルートから到達不可能でも使用中と 誤認識される メモリリークという致命的欠陥
10
参照カウント式GC (141ページ) レジスタ群 レジスタ R1 レジスタ R32 … 実行時スタック 空き領域 スタックフ レーム C
レーム B レーム A SP→ 大域変数群 大域変数 a 大域変数 b ルート ２ データ構造Ａ １ データ構造Ｂ ２ データ構造Ｃ １ データ構造Ｄ １ データ構造Ｅ ヒープ領域 参照カウント式GC (141ページ)
11
GCとコンパイラの連携 そもそもポインタが何時何処に存在するのか？ ポインタとそれ以外の区別方法
代入以外にも、ポインタからの参照がなくなるときがある 自動変数として消滅するとき インスタンスが消滅するとき ポインタとそれ以外の区別方法 参照の在処をコンパイラが提供する データ構造中の参照 実行時スタックおよびレジスタ
12
データ構造中の参照の在処 クラスを表すデータ構造 … フィールド数 フィールド情報 クラス名 Data ３ クラスDataのインスタンス
class Data { int field1; Data field2; Data field3; クラスを表すデータ構造 … フィールド数 フィールド情報 クラス名 Data ３ クラスDataのインスタンス ヘッダ field1 クラス field2 field3 フィールドに関する情報 field1 field2 field3 フィールド名 オフセット 型 ２ ３ ４ Data int
13
データ構造の走査 void scanDataStructure(reference ref){
class *k = reference->ヘッダ.クラス; int number_of_fields = k->フィールド数; FieldInfo *fields = k->フィールド情報; for(int i = 0; i < number_of_fields; i++){ FieldInfo *field = &fields[i]; if(is_reference(field->型)){ updateReference(&(ref[field->オフセット])); }
14
実行時スタックおよびレジスタ中の参照 名前 型 格納先 オフセット あるいは レジスタ名 戻り番地 変数数 変数情報 ２ ３ ４ 21 12
23 22 27 24 34 33 ee ExecEnv* レジスタ R3 o void スタックフレーム -20
15
実行時スタックおよびレジスタの走査 void scanStackFrames(){
StackFrame *frame = lastFrame(); while(frame > stack_bottom){ PCInfo *info = InfoForPC*frame->return_address); int number_of_variables = info->変数数; VariableInfo *variables = info->変数情報; frame = frame->previous_frame; for(int i = 0; i < number_of_variables; i++){ VariableInfo *variable = &variables[i]; if(is_reference(variable->型)){ if(is_register(variable->格納先)){ updateReference(&frame[variable->オフセット]); } else { updateReference(addressFor(frame, variable->レジスタ名));
16
Q末試験 日時 ２０１２年１１月２２日２時限目 場所 A１０６（いつもの講義室）
日時 ２０１２年１１月２２日２時限目 場所 A１０６（いつもの講義室） 時間 10時40分から12時10分までの１時間30分 開始後30分過ぎたら退室可 開始後30分までは入室可（遅刻限度） 持ち込んでいいもの 紙の資料、紙の書籍 （紙媒体であればいい）
Similar presentations
