Think Stitch
PRINCIPIA  最近の更新


継続渡しスタイル CPS による CSP カーネル

ちょっとはずかしい言葉遊びのようなタイトルになっちゃいました。 またまた体調を崩して熱を出してしまったので、休息がてら文章書きに逃げてきました。

SyncStitch は並行プロセスの理論 CSP に基づいて、並行システムのモデル化と検査を行うツールです。 モデルは状態遷移図、またはプロセス式で書きます。 状態遷移図は内部でプロセス式に変換していますので、プロセスのプリミティブな表現はプロセス式です。 SyncStitch のプロセス式は CSP と Scheme を合わせて作られています。 理論としての CSP では、プロセスを表すのに数学の記号を使いますけど、SyncStitch ではこれを S 式で表して、Scheme と融合しています。

実は SyncStitch 自身、このモデルを記述するのに使うプロセス式で記述されています。 それを動かすために、CSP の部分を Scheme に変換するコンパイラと、オペレーティングシステムのようなカーネルを持っています。 このカーネルも Scheme で書かれています。 これを CSP カーネルと呼んでいます。 今日はこの CSP カーネルの話をしたいと思います。 もし興味がありましたら、おつきあいください。

継続でプロセスを表す

前回、継続と継続渡し(Continuation-Passing Style, CPS)の話をしました。 継続というのは計算がある程度進んだ時点から見て、残っている続きの計算を表すものだという説明をしました。 継続を関数として表し、利用する CPS についてもご紹介しました。

ちょっといい方を変えると、継続というのは計算の途中の状態を保存しているものだと考えることができます (中間結果のことはちょっと置かせてください)。 すると、継続を複数持っていれば、複数の計算の途中過程を持っていることになります。 これらを少しずつ動かせば、計算を並行に実行しているように見えます。 つまり継続でプロセスを表すことができるわけです。

一般にオペレーティングシステム(以下、OS と書きます)の中では、プロセスを PCB (Process Control Block) というもので管理しています。 あくまでも概要的な話ですが、PCB は、プロセスが所有するメモリ空間(スタック領域を含む)以外の計算の途中状態、例えば各レジスタの値であるとか、所有するリソースの情報であるとか、を内包していたり、関連として持っていたりします。 PCB とメモリ空間を合わせたものは、そのプロセスの計算の途中の状態を表していて、そこから計算を再開することができます。 この意味で、OS が管理・保持するプロセスの情報は、継続にそっくりです。

CPS によるシステムコール

OS の場合は割り込みその他のハードウェア的な支援を借りて、プロセスが特に意識しなくても並行実行を可能にしています。 しかし継続を使ってプロセスを表すには、プロセス側の協力が必要です。 (プリエンプションのない OS に似ています。) 例えば、あるシステムコールを呼び出す場合、単なる関数として呼び出して結果が返ってくるのを待つのではなく、システムコールの処理が終わった後で実行する継続を渡します。つまり継続渡し、CPS です。

(system-call arg1 arg2 ... argN k)

例えば、あくまでも仮の例ですが、ファイルをオープンするシステムコール sys-open があるとすると、つぎのような感じになります。

(sys-open filename mode
  (lambda (fd)
    (if (= fd -1)
        ...)))

システムコール sys-open からのリターンは期待していなくて、末尾再帰の最適化によって継続へ制御を渡していくわけです。 このようにすると、カーネル側は渡された継続を保存したり、待たせたりすることができます。 継続は PCB の一部であるレジスタの値(特にプログラムカウンタ)のようなものです。

このように継続を使ってカーネルを作る方法はよく知られていて、検索すると解説や実装を見つけることができます。

プロセスの生成 csp-par

では具体的に CSP カーネルのシステムコールをご紹介します。 まずはプロセスを生成するシステムコール csp-par です。

(csp-par syncobj-list thunk-list)

ここで syncobj-list は生成するプロセスが同期するイベントとチャネルのリスト、thunk-list は引数を持たない関数のリストです。 thunk-list の各要素が、プロセスの初期状態を表す継続です。 このシステムコールはプロセス式の演算子 par に対応します。

(par syncobj-list process ...)

CSP カーネルは生成したプロセスを PCB の木として組み立てて管理します。 この木はプロセスの親子関係を表す木です。 PCB の一部をお見せすると、次のようになっています。

(define-record-type csp-process
  state
  parent
  children
  continuation
  ...)

state はプロセスの状態です。running, ready, wait-for-children, wait-for-sync, omega などがあります。 parent と children が親子関係を作るためのフィールドです。 csp-par が呼び出されると、thunk-list の分だけプロセスを作り、呼び出したプロセスの PCB children フィールドに登録します。 呼び出しプロセスは待ち状態 wait-for-children になります。 作成されたプロセスはすべて ready 状態となり、実行待ち行列に入ります。

プロセスの終了 csp-skip

プロセスを終了するためのシステムコールは csp-skip です。 終了ですから継続も受け取りません。

すべての子プロセスが終了すると、待ち状態 wait-for-children だった親プロセスも終了して、兄弟姉妹の終了待ち状態 omega になります。 このとき子供の PCB は削除されて、プロセス木は畳まれます。

同期システムコール csp-alt

プロセス間で相互作用を行うためには、同期システムコールは csp-alt を使います。 csp-alt のフォーマットは次のとおりです。

(csp-alt sync-form-list)

ここで sync-form-list というのは同期フォームと呼ぶもののリストです。 同期フォームというのはイベント同期や送受信を指定するもので、次の3つの種類があります。

(event . continuation)
(channel args . continuation)
(channel guard . continuation)

1番目はイベント同期、2番目はチャネル送信、3番目はチャネル受信です。 それぞれに継続を指定します。

プロセスがシステムコール csp-alt を呼び出すと、カーネルは指定されたイベントやチャネルを調べます。

もし同期するものがあれば、対応する継続を呼び出します。このときチャネル受信だけ特別で、継続に受信した値が渡されます。 同期した相手のプロセスは待ち状態 wait-for-sync から実行可能状態 ready に移されます。

もし同期するものがない場合は、プロセスを待ち状態 wait-for-sync にします。 そして実行可能待ち行列から別のプロセスを選んで実行します。 このときもし待ち行列が空だったら・・・デッドロックということです!

CSP から Scheme への変換

以上、ごらんのとおり、CSP カーネルのシステムコールは単純で、そのまま CSP に対応します。 したがってプロセス式を Scheme に変換するのは難しくありません。

先ほどはコンパイラといいましたけれども、実際にはこの変換はマクロとして実装されています。 いわゆる埋め込み言語です。 このおかげで、一般的な Scheme の対話的環境の中でどの層も対話的に開発することができます。

補足

関数オブジェクトはクロージャとも呼ばれるとおり、変数束縛を内包することができるので、計算の途中結果もいっしょに表すことができます。チャネル受信のところでは、カーネルが仲介した受信値を引数で渡すようになっています。

Scheme の call/cc を使えば、CPS ではない形でカーネルを作ることもできます。 しかし call/cc は CPS に比べるとコストが高いので、実用にはちょっとキビシイです。

継続にはもう少し軽量のフォーマリズムもあるそうです。 ちょうど先日くらいに、その軽量の継続のしくみを使って並行プロセスを作った方の話を見かけました。

csp-alt の中で、チャネル受信の同期を求めるところは面白いのですけど、ちょっと複雑なのでやめておきます。

あと他には逐次実行のしくみや改名のしくみなどがあります。 実行系ですから隠蔽はありません。 (追記:嘘書きました。隠蔽あり〼)

CSP ではイベントやチャネルはすべてグローバルです。 しかし実行系では局所的なイベントやチャネルを動的に作ることも簡単にできます。 ただそうすると、表面上、理論との対応をつけられなくなるので、実装していません。 理論的な裏打ちもできるのかもしれませんが・・・そのうち挑戦してみたいと思います。

2013/09/18

追記

これを CSP カーネルと呼んだのは、CSP で提唱されている同期型の相互作用のためのシステムコールを用意したカーネルという意味です。CSP で記述したプロセスを、簡単な変換で効率よく動かせるようにすることが目的です。 既存の OS に同期型のシステムコールを追加すれば、より面白いと思います。例えば μITRON は近いものを持っています。

ちょっと話が飛びますが、プログラミング言語だと ADA がランデブを持っていると聞いたことがあります。 Occam と Transputer であればいちばん幸せなんですが。

スケジューリングに関する部分が2カ所あります。 1つは実行可能プロセスの待ち行列からどれをどのように選ぶかという点。 もう1つは、csp-alt で、同期するイベントやチャネル、あるいは引数について複数の可能性があった場合に、どれを選ぶかという点です。 システムコールのモデルを作ったときには、プロセスを返す順序はあまり問題になりませんでした(問題になるようなモデルを作りませんでした)が、時分割による並行システムでは、この順序に依存するプロセスを作ることができてしまうので問題になることがあります(実はウィンドウシステムの中にあって、ちょっと困っています)。 基本的には、もっとも非決定的な仕様を満たしていれば問題になりません。カーネルがどのようなスケジューリング戦略をとっても対応できるはずだからです。 逆に、ふつうのリアルタイムオペレーティングシステムのように、優先順位をつけて積極的に利用することもできますが、そうすると理論の方を拡張しなければ検査できなくなります。

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