B演習(言語処理系演習)第一回

B演習(言語処理系演習)第9回
12/12
メモリ管理・ごみ集め
田浦
我々の処理系はmalloc/newを使って
いる
字句解析器
 構文解析結果(構文木)
 関数を呼び出すたびに作られる「環境」
 式を評価した結果

• 例: 2.3 + 3.4, [ 1, 2, 3 ], { a : b }, …
復習: C/C++言語で代表的な3種類の
メモリ割り当て方法

局所変数・配列  関数呼び出し終了と共に使えな
おそらく間違い
くなる
• int* f() { int a[1000]; …; return a; }
• double* g() { double f; …; return &f; }


大域変数・配列  プログラム実行中常に使える．し
かし，実行中に「追加割り当て」できない
ヒープ : OSから実行時に取得．代表API : malloc
(C), new (C++), …
• 注 : 中でmallocを呼ぶ関数(e.g., strdup)もある
基本フォーム
関数呼び出し後も使いたいメモリ局所変数・
配列の領域は使うな
 何バイト確保すべきか，同時にいくつ確保す
べきかわからない大域変数・配列の領域は
使うな
 そのような時はmalloc/newを使う
 しかしmalloc/newされた領域をいつfree/delete
すべきかはプログラマの責任…

割り当てたメモリは「いらなくなったら」
解放しなくてはならない
いつ「いらなくなる」のか
 あまり気にする必要ないもの

• 字句解析器
• 構文解析結果(構文木)

大いに問題となるもの
• 「環境」
• 式を評価した結果
実験: mallocしっぱなしだと何が起こる
か
GC (Garbage Collection)
あるメモリ領域が「いらなくなった」かどうか，
自動的に見つけていらなければ解放(再利
用)する仕組み
 Java, Python, Perl, VBA, … (最近の)言語に
は必ずといっていいほど備わっている
 C/C++にはそれがないのだが…

天の助け GC ライブラリ
http://www.hpl.hp.com/personal/Hans_Boehm/
gc/
 C/C++プログラムのmallocをGC_MALLOCに
置き換え, freeを除去するだけで再コンパイル
&リンクをするだけで，自動的にいらないメモ
リを解放してくれるライブラリ
 演習HP「各種情報」参照

GCの原理
GC以前のメモリ管理の基本原理
メモリ管理モジュールが「現在使われている/
いない領域」を把握するデータ構造を構築
 割り当て(e.g., malloc(100))

• 使われていない領域から，要求サイズを満たす
領域を探索

解放(e.g., free(p))
• 解放された領域を「使われていない領域」として
記録(以降のmallocで利用)
メモリ管理データ構造の例
空き領域リスト(フリーリスト)
 使用中アドレス サイズの表
free
(例: ハッシュ表)

空き領域
使用中領域
例(続)



空き領域リストのデータ表現
typedef struct free_region * free_region_t;
typedef struct free_region{
free_region_t next;
int sz;
} free_region;
malloc(sz) {
空き領域リストをたどって要求szを満たす
regionを検索;
}
GCなしのメモリ管理の危険


メモリ管理ライブラリは盲目的にユーザプログラム
(malloc/freeの呼び出し)を信ずる
早すぎるfree
• freeしてはいけないものをfree
• 本来別のアドレスに割り当てられるべき複数の領域が同
じアドレスに割り当てられる意図しないデータの破壊

メモリリーク
• freeすべきものをfreeしない
• 本来他の目的に使われるべきアドレスが再利用されない
意図しない使用メモリ領域の増大
自動メモリ管理(ごみ集め; Garbage
Collection)
「もう使われない領域」を自動的に発見して解
放
 プログラムの安全性は格段に向上する
 GC用語

• (プログラム実行中のある時点で) 「生きている領
域」 = その時点以降使われる(アクセスされる)領
域
• 反対語: 「死んでいる領域」
もう使われない領域をどう発見するの
か?


(実現不可能な)理想的メモリ管理  プログラムを
実行し続けた際に，今後使われる領域とそうでない
領域を各時点で100%正しく判定する(一種の未来予
知? アルゴリズム自動理解?)
main()
この地点以降使われるメモリ領域は
{
a[0], a[1], a[4], a[9], a[16], …
…;
for (i = 0; i < n; i++) {
p = a[i * i];
… *p …
}
}
実際のGCが行っている「近似」

現在局所・大域変数に入っているアドレス(が
指すメモリ領域)は「生きている」
• 注: アドレスが指す「メモリ領域」  そのアドレスを
含む，一回のメモリ割り当てで割り当てられた領
域

ある「使われる」メモリ領域中に入っているア
ドレス(が指すメモリ領域)は「生きている」
• 配列の要素，構造体のフィールドなど

「今後使われる」  「生きている」
同じことの書き換え
LIVE : (ある注目している時点で)「生きてい
る」アドレスの集合
 ある局所・大域変数の値 = a  a  LIVE
 “a  LIVE” かつ “pが，aが指すメモリ領域内
に格納されている”  p  LIVE
a

p
要するに局所・大域変数から「到達可
能」なものが「生きている」
局所変数
大域変数
GCの基本原理

割り当て (e.g., malloc(sz);)
• 空き領域からszバイト分の連続した空き領域(a)を発見
• [a, a + sz) を使用中と記録 (a をキーとして探索するとszが
分かるよう，何らかのデータ構造に記録しておく)

このとき，空き領域が足りなくなったら(基準は様々)，
• 1. 生きている領域をすべて見つける(マーク)
• 2. 残りの領域を解放(スイープ)
マーク

生きているものすべてに「印」をつける
• 印の場所: オブジェクトの先頭に専用の領域を
作っておく，ハッシュ表などを作る，などがある

要するにグラフのdepth-first searchの要領 (必
ずしもdepth-firstである必要もない)
擬似コード:
• void GC() {
mark_stack = mk_empty_mark_stack();
initialize all memory blocks as `not marked’;
for each word p in global variable { mark(p); }
for each word p in local variable { mark(p); }
while (! empty(mark_stack)) {
p = pop (mark_stack);
for each word q in the memory block pointed to by p {
mark(q);
}
}
for all memory block p not marked { free(p); }
}
void mark(p) {
if (! marked(p)) {
record p as `marked’;
push(p, mark_stack);
}}
「mini-Pythonに自力GCを実装」の
チャレンジャーへ

最低限必要なこと
• アドレスa  aが割り当て中領域であるかどうか
が判定できる．そうならばそのサイズ
• 割り当てた領域のアドレスをすべて列挙できる
• 全局所変数中のポインタの列挙
• 全大域変数中のポインタの列挙
• あるアドレスaで指されている領域中のポインタの
列挙
チャレンジャー用tips

要領1: 空き領域管理は，それ自身重労働．こ
れをmallocにまかせると楽かもしれない
• my_GC_malloc(sz) {
a = malloc(sz);
aからszバイト割り当て中と記録;
return a;
application
}
my_GC_malloc
my_GC_malloc
malloc
malloc/free
free
チャレンジャー用tips
要領2 : 主たる手間は「割り当て中領域」を記
録するデータ構造
 おそらくハッシュ表を作るのが良いだろう

• キー : アドレス
• 値 : 割り当てサイズ + 「印」

注: ポインタとしてありえない値(最下位2bitが
0でない)はハッシュ表を引くまでもない
全局所変数の列挙
局所変数はスタックに格納されている．ごく一
部はレジスタ
 スタック: main関数における局所変数のアドレ
スとGCが起動されたときの局所変数のアドレ
スに挟まれた領域
 レジスタ上の値については，挑戦したい人は
質問してください(try “man setjmp”)

main
interpreter
eval_...
GC()
(ほぼすべての)局所変数
大域変数の列挙


インタプリタ実装時に，大域変数を使わない(大域変
数にポインタを置かない)のが一番簡単
使う場合は，
• 「大域変数のアドレスをGCに登録するAPI」を用意すると
良いかもしれない
• int * global_var;
GC_register_root(&global_var, sizeof(int));

奥の手については，チャレンジする人は質問してく
ださい
GCはいつ起動すべきか

×mallocが成功する限り起動しない
• メモリ使用量が多くなりすぎる
自らある制限(使用中メモリサイズ <= A)を課
す
 Aをいくらにするか?

• GC終了後に「生きている量」を測り，その最大値
×定数(2～3)とするのが基本

Download Report