Think Stitch
PRINCIPIA  最近の更新


並行プログラミング言語 6:隠蔽 2

隠蔽の実装を少し効率化します。

過去の記事は以下のとおりです。

内部イベントにプロセスを関連づける

前回の最後で書いたように,隠蔽によって作られた内部イベントは,隠蔽したプロセスの子プロセス間でしか同期することはないので,同期判定のために毎回プロセス木の根から調べるのは無駄になります。そこで内部イベントを作成する際に,作成者であるプロセス,つまりその時点でのカレントプロセスを関連づけておくことにします。こうしておけば同期判定の際にそこから探索を開始することができます。

内部イベントにプロセスを関連づけるために,イベントをレコードで表すことにします。内部イベントだけでなく,グローバルなふつうのイベントも統一してしまうことにします。グローバルなイベントにはプロセス木の根に対応するプロセス,つまり root-process が関連づいていると考えればよいわけです。プロセスを覚えておくフィールドを creator としました。

(define-record-type event #t #t name creator)

define-event で定義するグローバルなイベントの場合は creator に root-process を入れたいところですが,残念ながら define-event を評価する時点では root-process はまだ決まっていないので,代わりに #f を入れておくことにします。したがって creator が #f ならばグローバルなイベント,プロセスが入っていれば内部イベントということになります。以上より define-event は次のようになります。

(define-macro (define-event e)
  `(define ,e (make-event ',e #f)))

チャネルイベントについても同様の修正をほどこすことはできますが,チャネルイベントを隠蔽する場合は上で定義したレコードによる内部イベントになり,チャネルイベントそのものが内部イベントになるわけではないので,いままでどおりとしておきます。

次に内部イベントを作るところ,つまり隠蔽のシステムコールを修正します。make-event を使って内部イベントを作る際に,creator としてカレントプロセス current-process を指定します。

(define (csp-hide event-list thunk)
  (csp-rename
    (map (lambda (e)
           (cons e (make-event (event-name-symbol e)
                               current-process)))
         event-list)
    thunk))

同期判定部分の修正

最後に,同期判定を行う関数 find-signaling-processes を修正します。 いままでは無条件に root-process から探索を開始していました。 もし同期判定を行うイベントが内部イベントであった場合は,そのイベントが関連づけられている creator プロセスから探索を開始するようにします。creator = #f の場合,つまりグローバルなイベントの場合は root-process から探索します。 (プロセス木を渡り歩く関数 traverse は省略してあります。)

(define (find-signaling-processes event)
  (define (traverse p) ...)
  (traverse
    (if (and (event? event)
             (event-creator event))
        (event-creator event)
        root-process)))

評価

以下のようなプロセスを定義して,traverse が呼び出される回数を数えてみました。

(define-process P
  (par '()
    (par '()
      (par '()
        (par '() SKIP SKIP)
        (par '() SKIP SKIP))
      (par '()
        (par '() SKIP SKIP)
        (par '() SKIP SKIP)))
    (hide (list c)
      (par (list c)
        (! c SKIP)
        (! c SKIP)))))

スケジューラには乱数による非決定性が入っているので,実行のたびごとに回数は変化します。そこでワーストケースを調べました。修正を行う前は38回,修正後は6回となり,だいぶ改善されました。

コメント

内部イベントに限らず一般にあるイベントを選んだとき,プロセス木の中でそのイベントを発生させる可能性があるものは一部だけになります。したがって決してそのイベントを発生させることのないプロセスを探索するのは無駄になります。

そこでここでの修正の考え方を発展させて,過去にイベント同期に関与したことのあるプロセスだけからなる部分木をキャッシュして持つという方法を思いつきます。プロセス木はイベントの同期判定においては AND-OR 木になります。この木を動的に構成してキャッシュします。同期判定のときにカレントプロセスがキャッシュされた木の中に含まれていない場合は,木をカレントプロセスを含む形で再構成します。こうすれば大きなプロセス木の中の,遠く離れた2つのプロセスだけが同期する場合でも効率よく判定を行うことができるでしょう。

今回チャネルイベントにはグローバル/内部の区別を取り入れませんでしたが,チャネルイベントではなくチャネルに区別をつけるというアイデアがあります。チャネル通信を隠蔽すると内部チャネルによる通信になると考えます。こうするとチャネルの隠蔽をイベントに分解することなく行うことができるでしょう。

2014/04/19
© 2013,2014,2015 PRINCIPIA Limited