Parallel Schemeに向けたテストその4

Scheme Inside Ypsilon

いろいろと考えてイプシロンではVMの並列化を:

  1. 各スレッドは独立したヒープを持つ。これはスレッド終了時に自動的に回収される。
  2. 各スレッドは独立してコンカレントGCを行う。
  3. 各スレッドは親子関係を持つ。
  4. 子は親のヒープを読むことができるが書くことはできない。
  5. 親は子のヒープを読むことも書くこともできない。
  6. 各スレッドはデタッチされた状態で生成される。
  7. 各スレッドは親の環境をRead Onlyで継承する。
  8. 各スレッドは例外ハンドラを除く動的環境をCopy on Writeで継承する。
  9. 例外ハンドラは各スレッドで独立したものを使用する。
  10. Linux, FreeBSD, MacOSX, Win32に対応。

といった仕様で実装してみました。難しかったのは親も子もすべてのスレッドを独立して動かし続けるという点でしょうか。これはどういうことかというと・・・
例えば以下のようなプログラムがあったとします。

(define task
  (lambda (x)
    (define foo (lambda (y) (list x y)))
    (spawn
     (lambda ()
       (let loop ()
         (display (foo 1))
         (loop))))
    (set! foo (lambda (y) (- x y)))))

単純に親子を独立に動作させた場合に発生するシナリオは、

  1. spawnされた子のスレッドがapplyするためにfooの値を取り出してVMレジスタにしまう。レジスタの値は(lambda (y) (list x y))のアドレスになる。
  2. 子と並列実行している親がfooの値を(lambda (y) (- x y))にset!する
  3. 親のGCが起動
  4. かつてfooに入っていた(lambda (y) (list x y))は親にしてみればゴミなので回収する。
  5. 子はレジスタの値を見てapplyを試みる。レジスタの値はさっきまで(lambda (y) (list x y))の存在したアドレス。
  6. しかしその実態はGCされていてもうない。
  7. SEGV

これを防止するには、親がGCを行う時にすべての子を止め、その上で子から親へのすべての参照を確認してゴミかどうか判断するのが簡単な方法です。上の例では子のVMレジスタに(lambda (y) (list x y))のアドレスが入っているので、これを回収しないことにするわけです。

しかしイプシロンではどのスレッドも止めたくありません・・・
で、難しいことになったわけです :(