並列セマンティクス

 

ABCL/f は次の二つの方法で伝統的な排他制御モデルを洗練している.

• メソッドを二つのタイプに分類する. 一つはボディの中に become を持つメソッドである. それらは書き込みメソッド と呼ばれる. それらは実行時に実際に更新をするかもしれないし, しないかもしれない(条件分岐の結果に依存する). またもう一つは become を持たないものである. それらは 読みだし専用メソッド と呼ばれる. 読みだし専用メソッドは どんな種類の書き込み操作も行なわないということを意味しない. 読みだし専用メソッドは他のオブジェクトの書き込みメソッドを呼ぶかも しれないし, 自分の書き込みメソッドさえ呼ぶかもしれない. ABCL/f のセマンティクスは読みだし専用メソッドが常に進行することを 保証し, 他のどんなメソッドともオーバーラップする可能性がある.
• 我々は書き込みメソッドの実行を二つの段階, 前段階と 後段階に分割する. 後段階は become の結果の式を 評価し, 前段階は後段階の前の全ての行動を含む. 例えば move! メソッド

  (defmethod point move! (dx dy)
    (become (redraw! self) :x (+ x dx) :y (+ y dy)))
  

  では, 前処理は (+ x dx) と (+ y dy) を 評価することと, インスタンス変数の更新からなる. 後段階は自分に対して redraw! メソッドを起動する. 我々の緩められた排他制御規則は, 起動の前段階は他の起動の 前段階とオーバーラップできない, しかし後段階は他の前段階および 後段階とオーバーラップできるというものである. ゆえに, この例は, 自分への呼び出しをしているにもかかわらずデッドロックしない.

最初の規則は, デッドロックに関する限り, プログラマが 書き込みメソッドのことだけを考えればよいことを意味する. 2.2.3 (1)節に示した緩和の例は, 一つのオブジェクトについて 一つのメソッドのみが起動されるので, 決してデッドロックを起こさない. それはABCL/f では次のように書かれる.

(defmethod cell current-value ()
  value)

(defmethod cell step! ()
  (let ((lv (current-value left)) (rv (current-value right)))
    (become #t :new-value (/ (- (+ lv rv) (* 2 value)) 2))))

current-value はボディ中で become を使用しないので, 読みだし専用メソッドである. それゆえに, 各セル オブジェクトに step! メソッドを並列に起動することは 決してデッドロックをひき起こさない.

     1  (defmethod! bintree-node insert! (k val)
     2    (cond ((< k key)
     3           (if left
     4               (become (insert! left k val))
     5               (become #t :left (make-leaf-bintree-node k val)))
     6          ((= k key)
     7           (format #t "Warning conflicting key (‾s ‾s)‾¥%" key value)
     8           (become #f))
     9          (else
    10           (if right
    11               (become (insert! right k val))
    12               (become #t :right (make-leaf-bintree-node k val)))))))

        図2.2: Insert Method in ABCL/f

二番目の規則は書き込みメソッドは自分の終了よりも早く オブジェクトにつけられた mutex を解放することができる ことを言っている. 2.2.3 (2)節の二分木の例は, ノードオブジェクトは 子オブジェクトを呼び出すことを決めるとすぐにひき続く メソッドを受け入れることができるので, 複数の insert! が一つの木に並列に動作することを許している. これは ABCL/f では図2.2のように記述される.

ABCL/f と, assignment によって変数を変更するより伝統的な文法 との文法的な差異は, ABCL/f では, 更新は become コンストラクトに よって行なわれ, 再帰呼び出しはその become の結果式として書かれる ということである. 再帰呼び出しを結果式の中に入れることによって( 5 行目, 12 行目), そのプロセスが再帰呼び出しをする直前にそのノードは アンロックされる.