コンパイラ 2012年11月15日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2012/index.html

コンパイラと実行環境の連携２ メモリに関係するバグを未然に防ぎたい 使用されていないメモリの自動回収・再利用 今回の内容 ごみ集め(Garbage Collection) メモリの断片が、使用中かどうかを判定 今回の内容 GCのアルゴリズム トレース式 印掃式GC 複写式GC 参照カウント式

トレース式GCの考え方 「参照する」「参照される」という関係を有向グラフ化する GCのアルゴリズム Javaでは、基本型は値型なのでここでは無関係。 Javaでは、オブジェクト変数は「参照する」関係の出発点 木ではないが出発点なので、図では「ルート」としている 「参照される」対象はインスタンス インスタンスにもオブジェクト変数を定義できるので、グラフになる GCのアルゴリズム 印掃式 すべてのルートからグラフをたどり、インスタンスに印をつける 最後まで印のつかなかったインスタンスを回収・再利用する 複写式 ヒープを２つにわけ、一方の領域がいっぱいになるまで割り付ける 空きがなくなったとき、他方の領域へルートからたどりつつコピーする

印掃式GC (138ページ a) 順に割り付けて使用中 レジスタ群 レジスタ R1 レジスタ R32 … 実行時スタック 空き領域 スタックフ レーム C レーム B レーム A SP→ 大域変数群 大域変数 a 大域変数 b ルート データ構造Ａ データ構造Ｂ データ構造Ｃ データ構造Ｄ データ構造Ｅ ヒープ領域 印掃式GC (138ページ a)　順に割り付けて使用中

印掃式GC (138ページ b) GCが作業中 レジスタ群 レジスタ R1 レジスタ R32 … 実行時スタック 空き領域 スタックフ レーム A SP→ 大域変数群 大域変数 a 大域変数 b ルート 印 データ構造Ａ 印 データ構造Ｂ 印 データ構造Ｃ 印 データ構造Ｄ データ構造Ｅ ごみ、空き領域に還元する ヒープ領域 印掃式GC (138ページ b)　GCが作業中

複写式GC (140ページ a) 順に割り付け中 レジスタ群 レジスタ R1 レジスタ R32 … 実行時スタック 空き領域 スタックフ レーム B レーム A SP→ 大域変数群 大域変数 a 大域変数 b ルート to 領域 from 領域 データ構造Ａ データ構造Ｂ データ構造Ｃ データ構造Ｄ データ構造Ｅ ヒープ領域 複写式GC (140ページ a)　順に割り付け中

複写式GC (140ページ b) 空きがなくなりGC起動 レジスタ群 レジスタ R1 レジスタ R32 … 実行時スタック 空き領域 スタックフ レーム C レーム B レーム A SP→ 大域変数群 大域変数 a 大域変数 b ルート from 領域 to 領域 済 データ構造Ａ データ構造A 済 データ構造Ｂ データ構造B 済 データ構造Ｃ データ構造C すべてごみ！ 済 データ構造Ｄ データ構造D データ構造Ｅ ヒープ領域 複写式GC (140ページ b)　空きがなくなりGC起動

複写式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);

参照カウント式GC データ構造の中にカウンタを設けておく カウンタの値が０になれば空き領域に加え再利用する 欠点もある 参照されると+１、参照されなくなったら-１する そのインスタンスを参照しているオブジェクト変数の数になる オブジェクト変数への代入時に処理 カウンタの値が０になれば空き領域に加え再利用する 欠点もある カウンタを操作するオーバーヘッドが大きい 「参照する」「参照される」関係グラフにサイクルがあるとき、 そのサイクル全体がルートから到達不可能でも使用中と 誤認識される メモリリークという致命的欠陥

参照カウント式GC (141ページ) レジスタ群 レジスタ R1 レジスタ R32 … 実行時スタック 空き領域 スタックフ レーム C レーム B レーム A SP→ 大域変数群 大域変数 a 大域変数 b ルート ２ データ構造Ａ １ データ構造Ｂ ２ データ構造Ｃ １ データ構造Ｄ １ データ構造Ｅ ヒープ領域 参照カウント式GC (141ページ)

GCとコンパイラの連携 そもそもポインタが何時何処に存在するのか？ ポインタとそれ以外の区別方法 代入以外にも、ポインタからの参照がなくなるときがある 自動変数として消滅するとき インスタンスが消滅するとき ポインタとそれ以外の区別方法 参照の在処をコンパイラが提供する データ構造中の参照 実行時スタックおよびレジスタ

データ構造中の参照の在処 クラスを表すデータ構造 … フィールド数 フィールド情報 クラス名 Data ３ クラスDataのインスタンス class Data { int field1; Data field2; Data field3; クラスを表すデータ構造 … フィールド数 フィールド情報 クラス名 Data ３ クラスDataのインスタンス ヘッダ field1 クラス field2 field3 フィールドに関する情報 field1 field2 field3 フィールド名 オフセット 型 ２ ３ ４ Data int

データ構造の走査 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->オフセット])); }

実行時スタックおよびレジスタ中の参照 名前 型 格納先 オフセット あるいは レジスタ名 戻り番地 変数数 変数情報 ２ ３ ４ 21 12 23 22 27 24 34 33 ee ExecEnv* レジスタ R3 o void スタックフレーム -20

実行時スタックおよびレジスタの走査 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->レジスタ名));

Q末試験 日時 ２０１２年１１月２２日２時限目 場所 A１０６（いつもの講義室） 日時 ２０１２年１１月２２日２時限目 場所 A１０６（いつもの講義室） 時間 10時40分から12時10分までの１時間30分 開始後30分過ぎたら退室可 開始後30分までは入室可（遅刻限度） 持ち込んでいいもの 紙の資料、紙の書籍　（紙媒体であればいい）