9.Garbage Collection for C 早稲田大学理工学部情報学科上田研究室 山根信之 自動メモリ管理 • 宣言型、文字列処理言語の早期から関連 付けられてきた • オブジェクト指向型言語でも多くは自動メモ リ管理を提供している CでのGC • プログラマがGCを使う時だけ使うようにし たい • 効率的な自動管理システムがあってもあ まり使われないし、メモリ操作に費やす時 間は小さい • GCが利益を得るまでは、コンパイラやラン タイムシステムから独立して動作できなけ ればならない GCの持たない情報 • どこでrootが見つかるのか • スタックフレームレイアウトやレジスタの協定 • どのwordがポインタで、どれがそうでないの か 9.1 曖昧なroot集めの分類法(1) • Garbage collectorはコンパイラの密接な知 識や協調でオブジェクトのレイアウトを明 確に決定する • 保守的collectorはコンパイラからヒープを 受け取らない。どのwordも潜在的なポイン タの可能性があるのでポインタかどうか調 べる 9.1 曖昧なroot集めの分類法(2) • この２つの中間に、部分的に正確だったり 曖昧だったりするcollectorがある • これはコンパイラの助けを全く受けないの で、スタックレイアウトやレジスタに関する 知識を持たない。プログラマ自身がデータ 配置を決める Conservative collector • ごみの量を保守的に見積もる • 使われない参照もいくらか余分に保持する • コンパイラの助けのない、非強調的な環境 の中で動くcollectorのことを表すことにする • この章ではBoehm,Demers,Weiserの開発し たcollectorとBartlettが開発したcollectorを 見ていく Boehm-Demers-Weiser collector • mark and deferred sweepに基づいた non-moving collector • CやC++と共に使うのに適している • 現在はincrementalやgenerationalもサポー トしている • 幅広いOSで実行 Bartlett’s collector • The Mostly Copying Garbage collector • CやC++と共に使うこともできる • いくつかの他のcollectorの基本 9.2 保守的GC • 明確なメモリ管理に比べてわずかなペナ ルティを普段から課す • collectorはmark-and-sweepに基づく • bitmapや異なるサイズのオブジェクトを隔 離したフリーリストを使う • マーカーは回収スタックを使い、オーバー フローしそうならより大きいスタックを用意 Allocation • Collectorはtwo-level allocatorを使う →Section4.5 • ヒープは4kbyteのブロックからなる • ブロックはmalloc等のOSのスタンダードア ロケータで取得 • ブロックはsingle sizeのオブジェクトを含む • 隣の空のブロックと結合もできる Allocation • ブロックの半分よりも大きいオブジェクトは 自分の一塊のブロックにallocateされる • 十分なサイズのフリーな塊が利用できなけ ればGCに頼るかヒープを拡張する • アロケータはfirst-fit戦略を使う Allocation • 小さいオブジェクトは、free-listの最初のメ ンバをそのオブジェクトサイズ分だけどけ てallocateする • free listが空になれば、sweep phaseで回収 して満たそうとする • 回収も成功しなければ、lower-levelの allocatorから新たなブロックを得てヒープを 拡張 Root and pointer finding • 保守的collectorは、遭遇した全てのwordを (特にわかっていない限り)潜在的ポインタ として扱わなければならない • 正確に安価にこれを決定できるとよい • 非常に保守的なcollectorは大量のごみを 保持してしまう Objectをマークするためのテスト • 潜在的ポインタpはヒープを参照している か？ • このオブジェクトを含んでいそうなヒープブ ロックは配置されたか？ • ブロックの初めから疑わしいオブジェクトの オフセットは、オブジェクトサイズのブロック 倍か？ Interior pointer • 小さいオブジェクトは内部ポインタの最初 のsignificant bitを覆うことでブロックヘッダ のアドレスを得る • 大きいオブジェクトはその開始点を見つけ るかポインタが無効になるまでブロックに スキップしてbottom_indexを調べる。 保守的GCの問題点 • データをヒープポインタとして誤認識するリ スクを持つか、一部のごみを不要に保持 する • collectorが内部ポインタを有効とみなすよ うにすると、ポインタでないwordがポインタ として認識されることが増える Misidentification • ポインタに間違えられたwordは大体整数 • 小さい整数は多くのシステム上では有効な ヒープアドレスではない • 非初期化データもポインタに間違えられや すい • atomic objectは定義上他のヒープのオブ ジェクトへの参照を持てない Misidentification • 大きなprocedure frameを奨励するアーキテ クチャで、フレームの大きな部分が正しく初 期化されていないと間違った参照を生成す る • black listingはヒープにあるメモリの一部を 解放して利用できなくする Efficiency • 設計はallocationとフラグメンテーションへ の耐久度の間で妥協が必要 • 古いオブジェクトを解放するのはコストが かかるので単純にmallocやfreeの実行命 令数を数えるのは効率的でない Incremental/generational GC • Boehm-Demers-Weiser collectorもこの方法 をサポートしている 9.3 Mostly Copying collection • 保守的なCopying collectorである。 • スタックやレジスタやstatic areaから参照さ れているかもしれないオブジェクトはcopyさ れない。 • そのためallocationが速く、ヒープオブジェ クトにあるポインタを発見するのが単純 で、GCが正確。 Heap layout • Fromspace,Tospaceではなく、spaceIDのつ いたブロックから成る。 • ブロック内のオブジェクトをコピーする方法 には次の二つがある。 – Tospaceとなっているブロックへコピーする – そのブロックをTospaceにセットする • spaceIDがcurrent_spaceと同じブロックは Fromspaceである。 Allocation • ブロックに十分な空きがあればそこへ配置。 • ブロックに十分な空きがなければ、フリーブ ロックを探す。フリーブロックはIDが current_spaceでもnext_spaceでもない。 • 大きなオブジェクトは複数のブロックにまた がる。 Garbage Collection(1) • まずrootからscanしていき、辿ったブロック のIDをnext_spaceの値に変更し、そのブ ロックをTospace scan-listに加える。 • 次にTospace scan-listにあるブロックの中を 調べ、到達可能なオブジェクトは新たなメ モリ空間(Tospace)へとコピーされる。 Garbage Collection(2) • ヒープを探索する方法は２つある。 – 同じIDのブロックに入っているオブジェクトの 型を同じにする • これはオブジェクトがコンパクトになるが、allocation が複雑になる – オブジェクトごとにオブジェクト型を示すヘッダ をつける Generational GC(1) • Bartlettのcollectorでも世代GCができる。 • メモリの50%が使われるとminor collection が起きる。 • 世代は２世代で、新しい世代はIDが偶数 番号、古い世代はIDが奇数番号とする。 • ルートセットから直接参照されるオブジェク トのあるブロックはID書き換えでTospaceに なり、それ以外のブロックのオブジェクトは 普通にコピーされる。 Generational GC(2) • Minor collectionを繰り返すと古い世代が 大半を占めるようになる。これが85%を超 えるとmajor collection(mark and compact) が起きる。 • この完了後にヒープが75%以上埋まってい れば、megabyte incrementをする。 • 最初のフェイズでブロックの1/3以下しか使 われていないブロックをscavengeして空に し、次のフェイズでポインタを修正する。 Ambiguous data structures • Unionでintとポインタを宣言すると、intなの かポインタなのかを判断できない。 • Bartlettはこれを後で回収できるようにする ためにcontinuationsを使う計画を設計し た。 • この方法だと、２倍高価になる。 The efficiency of Mostly Copying • CopyingはspaceIDやオブジェクトの型情 報、promotion bit、ブロックへのリンクなど の空間的オーバーヘッドがある。 • Generationalはremembered setの維持コス トがかかるが、GCに使う時間が減少する。
© Copyright 2024 ExpyDoc
