Think Stitch
PRINCIPIA  最近の更新


ローカル手続き呼び出し(Local Procedure Call, LPC)

Microsoft Windows (16bit および 95 系列を除く)はマイクロカーネル方式で作られていて、API(システムコール)呼び出しもプロセス間通信として実現されているのだそうです(本の受け売りなので棒読み)。 表面的には関数呼び出しのように見えるけど、実はそれは単なるライブラリの関数で、その関数の中でカーネルプロセスや他のサービスプロセスと通信をしているのだそうです(棒はつづく)。

もう古い話なのでどこで読んだのかは忘れてしまいましたが、このクライアントプロセスとサービスプロセス(カーネルを含めてそう呼ぶことにします)の間の通信では、イベントペアと呼ばれる2つのイベントオブジェクトを使って、リモート手続き呼び出しのようなことをしているのだそうです。 実際はリモートではなくローカルでの話なので、ローカル手続き呼び出し(Local Procedure Call)、略して LPC というのだそうです。

詳細は知りませんので、想像(捏造)で補って、この LPC を作ってみることにします。

LPC 設計概要

2つのプロセス P と Q が通信をするとします。 P が呼び出しを行う側、Q が処理をして結果を返す側です。 引数と結果の受け渡しは共有メモリ上のバッファを使います。

LPC の概要は次のとおりです。

  1. まずプロセス P がバッファに引数を書き込み、メッセージ通知用のイベントオブジェクトを使って要求を通知します。そして応答用のイベントオブジェクトを待ちます。
  2. プロセス Q はこれを受けてバッファから引数を引き取り、結果を求めてバッファに書き込みます。そして応答用のイベントオブジェクトを使って通知します。

LPC 設計

プロセスを以下の図のように構成します。

呼び出し元プロセス(Caller) P

呼び出し側プロセス P を下図のように定義します。

呼び出しの順序が正しいことを確認するために、渡す引数を 0, 1, 2, ..., M-1 の順に循環させることにします。 次に渡す引数の値を覚えておくために、状態変数 k を用意します。 状態変数 k は抽象状態 PA で定義して、各状態で継承します。

プロセス P は引数をバッファに書き込んだあと、msg.signal によって要求を通知します。 そして結果を待つために ack.wait を待ちます。 ack.wait から返ってきたら結果を引き取ります。

呼び出し先プロセス(Callee) Q

LPC の手続き側、すなわち呼び出される側のプロセス Q を下図のように定義します。

プロセス Q は起動してすぐに要求 msg.wait の待ち状態に入ります。 要求を受け取ったら、つまり msg.wait から返ってきたら、引数を読み込み、計算を行い、結果を共有メモリ上のバッファに書き込みます。 ここでは簡単に、受け取った引数の値に定数 M を加えた値を返すことにします。 結果を書き込んだら ack.signal で結果が用意できたことを通知します。 そして初期状態に戻り、次の要求を待ちます。

今回は検査を簡単にするために、メモリの読み書きチャネルをプロセス P と Q で分けることにします。

共有メモリ上のバッファ MEM

共有メモリ上のバッファは単なる1変数です。 プロセス P 用のチャネル rd, wr とプロセス Q 用のチャネル q.rd, q.wr を用意します。

(define-process (MEM m)
  (alt
    (! rd (m) (MEM m))
    (! q.rd (m) (MEM m))
    (? wr (x) (MEM x))
    (? q.wr (x) (MEM x))
    (! terminate SKIP)))

自動リセットイベントオブジェクト EVENTOBJ

自動リセットイベントオブジェクトのプロセス EVENTOBJ を再掲しておきます。

(define-process (EVENTOBJ s ps)
  (alt
    (? wait (r) (not (memq r ps))
       (if s
           (! r (EVENTOBJ #f '()))
           (EVENTOBJ #f (cons r ps))))
    (? signal (r) (not (memq r ps))
       (! r
          (if (null? ps)
              (EVENTOBJ #t '())
              (! (car ps)
                 (EVENTOBJ #f (cdr ps))))))
    (! terminate SKIP)))

システムプロセス SYS

プロセス接続図のとおりにプロセスを並行合成します。

2つのイベントオブジェクトを改名によって作ります。

(define-process SYS
  (par (list msg.wait msg.signal
             ack.wait ack.signal
             rd wr q.rd q.wr
             p q
             terminate)
    (par '() (Pw 0) Qw)
    (par '()
      (MEM 0)
      (rename `((,wait . ,msg.wait)
                (,signal . ,msg.signal))
        (EVENTOBJ #f '()))
      (rename `((,wait . ,ack.wait)
                (,signal . ,ack.signal))
        (EVENTOBJ #f '())))))

シミュレーション

典型的なシステムプロセスの実行パスを示します。

  1. まずプロセス Q が要求待ちに入ります。
  2. プロセス P は引数0を書き込み、要求 msg.signal を発行したあと、結果通知 ack.wait の待ち状態に入ります。
  3. プロセス Q は通知を受けて起き上がり、引数 0 を読み込んで結果 3 を書き込みます。そして通知 ack.signal を発行します。
  4. プロセス P は通知を受けて結果を引き取ります。

このように交互にパタパタと動くことがわかります。 一部 P と Q が並行して動作できるところがありますが、どの場合もイベントオブジェクトの待ちで同期するので順序がおかしくなることはなさそうです。

検査

デッドロック検査

デッドロック検査を行うと、デッドロックはないことがわかります。

引数と結果のシーケンスを検査する

より詳細に、引数と結果の読み書きを確認してみます。

仕様

引数の値 k は 0〜M-1 の間で循環します。 各値について

  1. wr.k
  2. q.rd.k
  3. q.wr.(k+M)
  4. rd.(k+M)

というシーケンスが発生するはずです。 そこで次のように仕様を定義します。

(define-process SPEC
  (SPEC-LOOP 0))

(define-process (SPEC-LOOP k)
  (! wr (k)
     (! q.rd (k)
        (! q.wr ((+ k M))
           (! rd ((+ k M))
              (SPEC-LOOP (mod (+ k 1) M)))))))

仕様のパスは一本道で、次のようになります。(SPEC3 の 3 は気にしないでください。)

イベントの隠蔽

上記の仕様と比較を行うために、読み書き以外のイベントを隠蔽したプロセス HSYS を用意します。

(define-process HSYS
  (hide (list msg.wait msg.signal
              ack.wait ack.signal
              p q
              terminate)
    SYS))

正当性検査

正当性検査を行うと、確かに上記仕様を満たしていることが確認できました。

イベントオブジェクトであることの必然性

条件変数のところで、ミューテックスを分離した不完全な条件変数を作りました。 それと自動リセットイベントオブジェクトの違いは、待っているプロセスが存在しないときの signal でシグナル状態を保持するかどうかです。 この違いが LPC では必要なのかどうか調べてみます。

孤独な条件変数 CV

ミューテックスを分離した条件変数 CV を再掲しておきます。

(define-process (CV cs)
  (alt
    (? wait (r) (not (memq r cs))
       (CV (append cs (list r))))
    (? signal (r) (not (memq r cs))
       (! r
          (if (null? cs)
              (CV '())
              (! (car cs) (CV (cdr cs))))))
    (! terminate SKIP)))

システムプロセス SYS2

イベントオブジェクト EVENTOBJ を条件変数 CV に置き換えたシステムプロセス SYS2 を定義します。

(define-process SYS2
  (par (list msg.wait msg.signal
             ack.wait ack.signal
             rd wr q.rd q.wr
             p q
             terminate)
    (par '() (Pw 0) Qw)
    (par '()
      (MEM 0)
      (rename `((,wait . ,msg.wait)
                (,signal . ,msg.signal))
        (CV '()))
      (rename `((,wait . ,ack.wait)
                (,signal . ,ack.signal))
        (CV '())))))

デッドロック検査

デッドロック検査を行うと、デッドロックが発見されます。

デッドロックに至るパスは次のとおりです。

プロセス Q が待ち状態に入る前にプロセス P が signal を実行しているので、空振りしています。 これは初期状態だけの問題ではありません。 例えば、プロセス P が要求を発行して、待ち状態に入る前にプロセス Q がすばやく処理を行って、結果通知の ack.signal を発行してしまうかもしれません。 このように、シグナル状態の保持は必然的だということがわかりました。

補足

このモデルは生産者・消費者問題と同じです。 同じといってもバッファは1個だけ、生産者も消費者も1つだけですから、名前で呼ぶのは大げさですけど。 でも、セマフォじゃなくて、イベントオブジェクト2つでもできるのですね。 しかもミューテックスが必要ないという点がポイントかなと思いました。

2013/09/08
© 2013,2014,2015 PRINCIPIA Limited