並列読み出しと書き込み

データをコピーする際に通常処理ノードが同じデータをアクセスしているかもしれ ないということに配慮しなければならない。幅優先のコピーの場合には、旧面にある 構造体データを新面にコピーする時旧面データに前方参照ポインターを書き込む。 前方参照ポインターは通常ポインタと見分けがつかないので通常処理ノードにとっ ては異常データを参照してしまうことになる。

この問題を解決する方式はいくつか考えられるが、KLICでは以下に述べる ボトムアップコピー方式と暗黙前方参照方式を実装した。 (それらは条件コンパイルにより切り替えるようにしている)

旧面読み込み専用

GCノードは旧面を読み込み専用とする。通常処理ノードは悪影響を及ぼさない。 このことは、GCノードは前方参照ポインタを一切作らないことを意味する。

しかしこの方式で共有メモリ変数は例外にしなければならない。GCノードは、旧 面の変数を新面にコピーすることで１つの変数を２つの変数に分割できない。一 つの変数を２つの変数に分割することは論理変数の意味を壊してしまう。

そこで、共有メモリ領域の新しい変数を生成し、それと旧面の変数を単一化を許し、 旧面の変数の値は新しい変数へのポインターにしてしまう(このポインターは実質 的に前方参照ポインタとなる)。

前方参照ポインタが使用できないために、GCノードは古い面のコピーデータが新しい 面のどこにあるのかがわからない。(古い面のデータが新しい面にコピーされた かどうかさえわからない）ゆえに、旧面データ生きているパスの数だけのコピー が行われる。その数は非常に大きな数になる恐れがある。 別の前方参照テーブルを設ける方法も考えられるが、余分な空間を必要とすこ とや実行時のオーバヘッドを考えると非現実的である。

ボトムアップコピー方式

旧面のデータ構造を新面へボトムアップにコピーする。旧面を指して いる構造体への旧面にあるポインタは新面にコピーした構造体へのポイ ンタに置き換えられる。リスト[a,b](図  11.3)のコピーは、 図  11.4(a)から図  11.4(b)へと進む。 新面にコピーされた構造体は旧面にあるものと論理的に等価である。このよう な置き換えはいつでも可能である(ポインタの書込みが不可分な処理である とすれば、通常の計算機はこのことを保証している)。たとえば、この場合 通常処理ノードからみて常に[a,b]と見える。

  

Figure 11.3: 元の状態 (コピー前)

  

Figure 11.4: ボトムアップ コピー

file=shm-bottomup-copy1.eps,scale=0.7
(a)

file=shm-bottomup-copy2.eps,scale=0.7
(b)

この方式でも、重複コピーの問題をはらんでいる。特にループしているデータに 出合うと無限ループに陥る。しかし、重複コピーする度合はそれ程多くない。 旧面読み出し専用の場合と違って、参照中のポインタの数だけの重複コピーしか起 こり得ない。(生きているパスの数と比べれば、はるかに小さい数である。)

幸い多くのKL1 プログラムはループ構造を作っていない。また複数のポインタ から参照されるデータ構造の割合も大きくない。

暗黙前方参照方式

暗黙前方参照ポインタは前方参照情報を間接ポインタの出現で代替させる。デー タ中の１語、言うならば先頭に暗黙の前方参照ポインタを配置する。このポインタ は新面のコピーしたレコードを指す。たとえば、リスト[a,b]をコピーする場合、 最初の CONS レコード(C1)を新面にコピーする。局所メモリから指されるポインタ は直ちに新面にコピーされた CONS レコード(C1')を指す。そして、C1 レコードの 最初のフィールド(CAR 部)をC1'へのポインタに書き換える。 (図 11.5(a))この参照ポインタ は前方参照ポインタとして扱う。そして同じようにCONS の２番目のフィールド(C2)を コピーし、前方参照ポインタを設定する。(図 11.5 (b)) 参照点ｋから参照されているデータ 構造は旧面から新面への参照に変る。これらのポインタの付け直しの前後および 途中でも論理的にリスト[a,b]と一定している。

  

Figure 11.5: トップダウン コピー

この方式の問題は、(前方参照タグ方式と比較して)間接ポインタと前方参照ポイン タ見分けが付かないことである。これら２者を識別しなければならない。我々の実装 では共有ヒープ上にポインタを作る場合は以下のような場合に限られている。

1.

構造体要素から共有変数を指すポインタ

2.

共有変数同士の単一化でできるポインタ

(2)ではGCノードによって作られたもの(共有変数を旧面から新面にコピーした時の ポインタ)か通常処理ノードによって作られたものかは識別できない。しかしこれら は区別する必要がない。

(1)の場合、旧面から新面の共有変数へのポインタなら前方 参照ポインタと区別ができなくなる。そのようなポインタは通常処理ノードが局所メ モリ上のネストした構造体をコピーするときに生まれる。ゆえに実行時のコピールー チンでそのようなポインタができないように間接ポインタを差し入れるように修正し た(この措置により通常処理に若干のオーバヘッドが加わっている)。

この方式で更なる問題がもう一つある。新面のレコードから旧面を指すポインタの 存在である。新面に移った通常処理ノードは、直接GC中のそのようなポインタ を参照してしまうことはないのだが、旧面を参照中の別の通常処理ノードからその ようなポインタを受け取ってしまうことがある。ゆえに、この方 式では面を再利用する時、再利用する面を参照しているポインタを新面へのポインタ にするための局所GCが必要である。