セグメントの管理
ヒープ管理の根本となる部分は"セグメント"とよぶ。C言語なりなんなりで言うところのmallocとfreeを実装する仕事になる。
管理対象は16kbしか無いので、とりあえず線形リスト、first-fitで実装することにする。
- セグメントヘッダのチェイン
セグメントとして確保された領域の先頭にはセグメントヘッダと呼ぶ情報を置く。セグメントヘッダは
+------------------+ -2|NEXT SEGMENT HDR|F|-----+<- first-segment-header +------------------+ | -1| REVERSE PTR | | +------------------+ | +0| Data | | +------------------+ | +1| : | | : : : : : : : : : +------------------+ | | SEGMENT HEADER |<----+ +------------------+ | : : : : : : : : : +------------------+ | | ZERO |<----+ ; ここがヒープ空間の末尾となる +------------------+
のような構造を持ち、最初のヘッダはグローバル変数first-segment-headerで指され、最後のセグメントヘッダはゼロを指している。最後のヘッダの指すゼロは単に無駄なワードとなるが、番人(sentinel)として機能する。
セグメントヘッダは、フリーで無い限り何らかのVector headから指されていることになる。
セグメントヘッダのリンク構造は必ずアドレス順になっている必要がある。これは、セグメントのサイズを導出するためにnext headerのアドレスを用いている事に依る。
- 確保/解放
確保は、セグメントヘッダを辿っていき、(1)確保されておらず、(2)十分なサイズがあるセグメントを分割して利用する。ただし、サイズの余裕がある程度(今回は16wordsとした)よりも小さい場合はセグメントを分割しない。
条件に適合するセグメントのうちどれを使うかも問題になる。もっとも良く適合するセグメントを使う(best-fit)や最初の見つかったセグメントを使う(first-fit)といった戦略がある。今回はfirst-fitを用いる。
解放は、単にセグメントのFフラグを1にすることで行う。
空いているセグメント同士を融合する処理はGCの折に行うことにする。
cellの確保とGC
cellは、予め未使用のcellをある程度プールしておいて利用する。もし、このプールが枯渇したら、新たにセグメントとVector head(cell)を割り当て、プールに追加する。(当然、"次のセグメントを指すためのvector-headになるcellとそのvector-headを指すpairになるcell"は予め確保しておく必要がある)
プールはlistであり、グローバル変数free-listから参照される。(null? free-list)ならばプールが枯渇したということになるし、不要なcellは、(set-cdr! unused-cell free-list)、(set! free-list unused-cell)の形でfree-listに繋げられる。このとき、cellのtypeは強制的にpairとする。
Vector headを独立させるか否か
地味にデザインチョイスになっているのはVector headを(1)cellにするか、(2)単に(cellと識別可能な)セグメントヘッダとするか。
今回、Vector headをcellにしているのは、メモリ領域の移動を意図しているため。もっとも、設計さえ適切に行えばどちらかに切り替えるのは容易と言える。
今回の選択(1)の悪いところは、セグメント中のデータを参照するにあたって一旦メモリアクセスが増えること。しかし、この悪いポイントは、そのままセグメントが移動可能になるというメリットも生んでいる。
両方を搭載して、移動可能なデータに限りこの選択を行うという方針も考えられる。cellのtypeにはまだ余裕があるので選択の価値があるかも知れない。
