久野です。

kono@ie.u-ryukyu.ac.jpさん:
> あるいは、
>     incremental GC の時間を制約できる
> ってことなのかな。

  そうですそうです。

> できると思うけど、あまり簡単ではないでしょうね。(問題とその解
> 決法が2,3いきなり頭の中で点滅した...) 振舞的には lazy
> reference count っぽいのか。

  lazyにするとそのlazyにしたものを何とかするときが問題ね。

  3色塗りって知ってますか。メモリセルを

  白→調べてない
  灰→生きている。そのセル中の参照はまだチェックしてない。
  黒→生きている。そのセル中の参照もチェック完了。

の3種類に分類する。GCフェーズの最初は全部白からはじめる。まずルー
トからたどれるものを灰色にする。次に灰色のセルを1つ取り、そこか
ら直接たどれるセルを調べ、それが白なら灰色にする。済んだら最初の
セルは黒にする。これを繰り返して灰色がなくなったら白がゴミ確定。
これだとどこで止めても問題ないでしょ? alloc()があるごとに一定数
ずつ灰色セルを処理する、という形でGCすれば上限が保証できる。

  ただし、GC中にポインタの変更がある場合の処理も必要(ライトバリ
ア)。これは、セルAにセルBへのポインタをセットしようとしたとき、
次の処理を行えばよい。

  A  B
  白 白  なにもしない
  白 灰  なにもしない
  白 黒  なにもしない
  灰 白  なにもしない
  灰 灰  なにもしない
  灰 黒  なにもしない
  黒 白  Bを灰に
  黒 灰  なにもしない
  黒 黒  なにもしない

これも上限保証できますよね。

           おおまかには以上です。いかがっすか?              久野