3章 並行プロセスとプログラミング
Chapter3 Concurrent
Process and Programming
3.5 同期のための言語機構
3.5 Language Mechanisms
for Synchronization
発表者：神戸隆行（kando9@is.titech.ac.jp 東京工業大学 情報理工学研究科 計算数理科学専攻）
2000/09/25(月)久野ゼミ(http://www.is.titech.ac.jp/~kando9/kuno_zemi/index.html)
基本的なプロセスの概念を背景に､ここではプロセスの相互作用のための言語の構文について考える。
既存の逐次型言語に付加的な言語機能を追加して並行プログラミングを支援するのは自然なやり方。（人々が新たに学ぶことがより少なくて済む）
逐次型の言語を並行言語へと拡張するには､以下の機能を提供するような構文を追加：
l 並行動作の記述
l プロセスの同期
l プロセス間通信
l プロセス実行の非決定性
これまでの研究：
l プロセスの同期は集中型OSのために広く研究されてきた。
l メッセージ・パッシングによるプロセス間通信は、分散システムを考えようとする場合の新たな話題。
この節の内容：
l プロセス間同期の標準的な解法
l それらと分散システムの関係
l 分散システムにおけるプロセス間通信の進化
l 異なるプログラミング言語間での同期に対する様々な対応
l 言語構造の簡単な説明とそれらがどのようにしてプロセス間同期のために拡張されたか
普通の手続き志向言語では一般に、全ての文法構造と主だった構成要素の意味論が定義されている。
構成要素の典型的な分類：
l
プログラム構造：
プログラムやその部分要素（例：手続き､ブロック､文､式､項、変数、定数､他）がどのように構成されるかを指定。制御文で明示しない限り逐次的に実行されると想定される。
l
データ構造：
プログラム中の対象の表現を指定。データ抽象とその効率的な実装が主要な目的。
l
制御構造：
プログラム実行の流れを調整。殆どの言語はif-then-else、while-do、repeat-until、他のようなone-in-one-outな制御構造を強調。この他に暗黙の制御構造としてサブルーチン呼び出し､復帰（return）、終了（exit）がある。
l
手続きとシステム・コール：
特別なルーチンやシステム・サービスの利用を指定する。実行の流れの変化やパラメータ渡しを含む。
l
入出力：
入力データを読むことや､プログラムの実行結果の出力を指定する。全てのプログラムは少なくとも出力は行う。メッセージの送受信とも解釈できる。
l
代入：
データ・オブジェクトに対する副作用を引き起こす。プログラムの実効に影響を及ぼすための基本的な演算。
表3.1： 同期機構と言語の機能(概要)
|
同期手法 Synchronization Methods |
言語機能 Language Facilities |
|
共有変数に基づく同期 Shared-Variable Synchronization |
|
|
セマフォ semaphore |
共有変数とシステム・コール |
|
モニタ monitor |
データ抽象 |
|
条件付クリティカル・リージョン conditional critical region |
制御構造 |
|
serializer |
データ抽象と制御構造 |
|
パス式 path expression |
データ抽象とプログラム構造 |
|
メッセージ・パッシング同期 Message-Passing Synchronization |
|
|
communicating sequential process |
入出力 |
|
遠隔手続き呼び出し remote procedure call |
手続き呼び出し |
|
ランデブー rendezvous |
プロセス呼び出しと通信 |
以下、で取り上げる例題について：
l
（多くのアプリケーションにおける並行性と同期について十分普遍的なモデルである）リーダー/ライター問題（reader/writer problem | concurrent readers/exclusive writer probrem）を例にとって考える。
読み手は複数に並行アクセス可、書き手は排他的にアクセスするという、データ・オブジェクトでよく見られる状況。
l 正確には強リーダー優先（an arriving writer waits until there are no running readers、ただしリーダーとライターがライターの終了を待っていた場合に次にはリーダーを実行）と弱リーダー優先（基本的には強リーダー優先と同じだが、リーダーとライターがライターの終了を待っていた場合に次にはライターを実行）､ライター優先（an arriving readers waits until there are no running and waiting writers）の3通りがある。
l ここでは弱リーダー優先の事例で比較。
l 概念とアルゴリズムの解説を優先し､構文は非形式的
l 集中型OS上で並行プロセスを同期するために開発されてきた。
l その名の通り、共有変数を通じてプロセス間の協調を実現し、メッセージ・パッシングもクライアント・サーバ通信も利用しない。
l 集中的なアプローチだが、いまだに分散システム内でも有用（分散共有メモリとか）。
l 以下の要約を通じて､構造的に同期サーバ（あるいはリソース・サーバ（3.6節））を必要とすることが結論付けられる。
仕組み（ここでは2値セマフォを扱っている）：
l システムに組み込みのデータ・タイプ及びシステム・コールとして実現（操作の不可分性を維持と、プロセスのブロック／再開については、責任を持ってシステムが行う）
l 内部的にはプロセスをブロックするためのキューとロックからなる。
l 操作はプロセスを同期させるための2つ：
Ø
P：ロックの要求
ロックが既に他のプロセスによって獲得されているのでなければ、ロックしてそのプロセスを続行。
ロックが既に獲得されていればキューに記録して要求してきたプロセスをブロック。
Ø
V：ロックの解除
ロックを解放。もしキューに記録されているプロセスがあればその記録を取り出して該当プロセスを再開。
特徴：
l
プロセス同士を協調させて正しい同期が行われるようにする責任は利用者に任される。
→ 同期に関する透明性は全くない。
l システムが組み込みで特別に提供するセマフォは、より一般的なデータ型をユーザーが定義できるようにする。
図3.12は例題の解：
l ここでは2値セマフォを利用している。
l rcはリーダーの数を管理。
l mutexはrcが排他的にアクセスされるようにするためのセマフォ。
l dbはリーダー達とライターが排他的にデータベースにアクセスするためのセマフォ。
変数定義
var
mutex, db: semaphore;
rc: integer;
読み手プロセス
P(mutex);
rc := rc + 1;
if rc = 1 then P(db);
V(mutex);
データベースを読む
P(mutex);
rc := rc - 1;
if rc = 0 then V(db);
V(mutex);
書き手プロセス
P(db)
データベースに書く
V(db)
仕組み:
l 文法的にはユーザー定義データ型に類似。
l モニタ定義はローカル変数と操作（モニタ手続き monitor procedure）、初期化手続きよりなる。
l ユーザー定義型とは異なりインスタンスは1つだけしか存在しないという前提が維持される。→ 2値セマフォのP操作とV操作の対と同じ排他制御機構として機能する（クリティカル・セクションは固定でモニタ手続きとして表現）。
l 標準的には、モニタ手続き内では2つの操作wait（モニタに入った手続きを停止させる）とsignal（モニタ内で停止された手続きを再開させる）を備える条件変数(conditonal variable)が利用できる。
l モニタ手続きの実行が混ざらないよう、モニタの実装は2つ以上のプロセスが同時にモニタに入れないようにしなければならない。
特徴:
l オブジェクト・モデルの概念に基づきセマフォより構造的な手法。
l
モニタ手続きはパラメータを受け取れる。
→ 同期だけでなく通信にも利用できる。
l 同期の詳細だけは隠蔽できるので、透明性への大きな一歩に。
図3.13は例題の解：
l rcは読み手プロセスの数を記録。
l busyは書き手プロセスが活動中であることを記録。
l to_readとto_writeはそれぞれ読み手プロセスと書き手プロセスの待ち状況を管理。
l モニタが読み手と書き手の関係を制御する制御器として働く。
l 読み手と書き手に直接の相互作用はなく、モニタは読み手と書き手をクライアントとするサーバのように機能する。
l
モニタ手続きは複数起動できないのでリーダを複数並行には動かせない。
→ モニタがシステムによって実装され、readとwriteの制御に責任の負うてさえ、モニタは一人前のリソース・サーバではない。readやwriteの前後に利用する側のプロセスがモニタの手続きを呼ばねばならない。
→ 単なるread/writeほど透明ではない。
（モニタ手続きをスレッドにすれば動きそうに思えるが、モニタとしての前提が失われて同期を明示しなければならなくなる。）
モニタ定義
rw: monitor
var
rc: integer;
busy boolean;
to_read, to_write: condition;
procedure start_read
begin
if busy then to_read.wait;
rc := rc + 1;
to_read.signal;
end
procedure end_read
begin
rc := rc - 1;
if rc = 0 then to_write.signal;
end
procedure start_write
begin
if busy or rc ≠ 0 then to_write.wait;
busy := true;
end
procedure end_write
begin
busy := false;
to_read.signal or to_write.signal;
end
begin
rc := 0;
busy := false;
end
読み手プロセス
rw.start_read;
データベースを読む
rw.end_read;
書き手プロセス
rw.start_write;
データベースに書く
rw.end_write;
仕組み：
l region-begin-end構造によってクリティカル・セクションを明示する。
l クリティカル・セクションにwhen節を追加できて、そこへ入る前に満たすべき条件をテストできる。
l 条件を満たせばクリティカル・セクション本体を実行。
l 条件を満たしていない場合はプロセスはブロックされ、既に停止されている他のプロセスがあれば再開され、条件が調べられる。
特徴：
l セマフォの手法を構造化したもの。
l
共有変数（共有メモリ）と、コンパイル時にOSのプリミティブが利用できること（分割コンパイルに向かない）が前提。
→ 分散化拡張の候補にはなれない。
図3.14は例題の解：
l dbは読み手と書き手の相互排他制御のためのクリティカル・セクション。
l 読み手は複数入れるのでクリティカル・セクションではrcを調整するだけ。
l 書き手はwhen節で読み手が0かどうかテストされる。
変数定義
var
db: shared;
rc: integer;
読み手プロセス
region db begin rc := rc + 1; end;
データベースを読む
region db begin rc := rc - 1; end;
書き手プロセス
region db when rc = 0 begin
データベースに書く
end;
仕組み：
l 構造はモニタと同様。
l
・・・ただし、serializer手続き（モニタ手続きに代わるもの）は、相互排他的なものと並行実行可能なもの（hollow （空ろな）region）という2種類のリージョンを持つ。
→
joincrowd-then-begin構造
hollow部に差し掛かるとプロセスはcrowdという指定された区間（begin-end）を並行実行するプロセスの集まりに追加される。
l
条件変数に代わって、enqueue-until構造を導入
enqueでブロックされ、untilの条件が満たされると再開。（signalを明示する必要がなく、システムが暗黙のうちに行う。）
特徴：
l モニタ手続きを並行に実行できるように、並行実行してもモニタ手続きがアトミックであるようにモニタを拡張したもの。
l
serializerでは内に隠蔽できるものが増えて、オブジェクトモデルにもっとも良く沿っており、リソース・サーバになり得ている。
→ 透明性が向上し、プログラムの明快性が増す。
図3.15は例題の解：
l モニタの場合と基本的に同じだが、部分的に並行実行が可能なため「モニタ手続き」内で読み書き本体も記述できるようになっている。
serializer定義
rw serializer
var
read_q, write_q: queue;
r_crowed, w_crowed: crowed;
procedure read
begin
enqueue(read_q)
until empty(w_crowed);
join_crowed(r_crowed) then begin
データベースを読む
end;
end
procedure write
begin
enqueue(write_q)
until (empty(r_crowed) and empty(r_crowed));
join_crowed(w_crowed) then begin
データベースに書く
end;
end
読み手プロセス
read
書き手プロセス
write
仕組み：
l ここまでに述べたものとは全く異なる形式で、共有オブジェクトに備えられた操作の実行に課せられる制約を直接に記述する高レベル言語。
l コンパイラは並行制御のための実装可能なプリミティブに翻訳せねばならない。
特徴：
l プログラムの形式的記述に類似し、極めてエレガント。
l 簡潔だが並行と同期を指定する十分な表現能力を備える。
l 条件付の協調のための述語を含むのが最も注目すべき例。
例題の解：
l 定数1とそれに続く( )は、括弧内で同時に1つの操作が可能であることを示し、読み手と書き手の相互排他を表現。
l [ ]は読み手が並行実行可能なことを表現。
パス式
path 1:([read], write) end
l 共有メモリのない分散システム内では唯一の通信手段
l 発信→受信という関係があるため暗黙の同期が行われる。殆どのアプリケーションで：
Ø 受信はブロック
Ø 送信はブロックすること（同期メッセージ・パッシング synchronus message passing）もしないこと（非同期メッセージ・パッシング asynchronus message passing）もある。
この節の内容：
l 非同期メッセージ・パッシング
l 同期メッセージ・パッシング
l CSP(Communication Sequencial Processes)とメッセージ・パッシングの関係
l 遠隔手続き呼び出し
l ランデヴー
特徴：
l メッセージ・チャンネルでバッファリングが必要
l
変数の共有はないが、メッセージ・チャンネルは共有されていると考えられる。
→ セマフォを分散システムに拡張したものと考えられる。（ただし、バッファの容量に制限がない場合。完全な実現はムリ。）：
Ø 受信操作でのブロックはセマフォのP操作と等価
Ø ブロックしない送信操作はセマフォのV操作と等価
l メッセージ・チャンネルが言語で指定できてOSがサポートするならば、セマフォと同じくらい有用
l 例） UNIXのパイプやソケット（4章で詳説）
図3.16は相互排他の例：
l チャンネル・サーバはOSが同期のための論理的なメッセージ・チャンネル機構の一部として提供
l メッセージ・チャンネルはメッセージを１つ送ってある状態に初期化
l この相互排他の例ではメッセージの内容は不問
プロセスPi
begin
receive(channnel)
クリティカル・セクション
send(channnel)
end
チャンネル・サーバ
begin
channnel作成
send (channnel)
channel管理
（キューの管理とプロセスのブロック操作）
end
プロセスPj
begin
receive(channnel)
クリティカル・セクション
send(channnel)
end
特徴：
l メッセージ・チャンネルでバッファリングが不要
l
送信は受信の完了を待ち、受信は送信を待つ
→ 互いに待ちあう（対称性）
→ 同期する際には受信と送信の対で協調してデータを交換し、その後は別々の実行を継続（ランデヴー Rendezvous）
l
ランデヴーが有用な実生活での例：
フットボールの観戦の際に競技場の前で待ち合わせてのチケットの相互売買（売り手：
チケットを持って挙手、買い手： チケットの必要枚数を指で表示）。チケットの売買は非同期で対称的。
図3.17は相互排他の例：
l プロセスでの送信がP操作
l プロセスでの受信がV操作
l セマフォサーバーがプロセスへの送信完了を待っている間、受信操作は行われないので、他のプロセスでの送信操作もブロックされる。
l この相互排他の例ではメッセージの内容は不問
プロセスPi
begin
send(sem,msg)
クリティカル・セクション
recieve(sem,msg)
end
セマフォ・サーバsem
loop
receive(pid, msg)
send (pid, msg)
end
プロセスPj
begin
send(sem,msg)
クリティカル・セクション
recieve(sem,msg)
end
一般化：
send-recieveの対に限らず、手続きの名前を利用した一般のランデヴー呼び出しが考えられる。
CSPの特徴：
l 分散システムにおける同期の問題を記述する言語
l 入出力ランデヴーを利用
l
プロセスPが式exｐの内容をプロセスQに送信：
Q!exp
l
プロセスQが変数varへプロセスPから受信：
P?var
l 入力と出力はプロセス名で結合
l var := expという遠隔代入（remote assignment）と見なせる。
l 入力プロセスと出力プロセス間の同期的メッセージ交換によって暗黙のうちの同期を達成
プロセス名の直接利用の問題（例： リーダ／ライタ問題）：
1.
リーダとライタは別々に作成され、互いの存在を知らない
→ リーダがライタを指定してメッセージを送ったりするのは合理的でない。
2.
リーダとライタの並行アクセスを規制するサーバがあればいい（例： S!request requestメッセージには送信者名（RやW）を含めればサーバが返信すべき先も分かる。）
→ リーダとライタが直接通信する必要はない。
alternativeコマンドと条件付コマンド（Guraded Command）：
l 条件付コマンドでは実行文に条件節が付随する
l あるコマンドの全ての条件節が評価されてからalternativeコマンドに制御が移る
l alternativeコマンドでは条件に合致する条件付コマンド群の中からただ１つのコマンドが実行される（非決定的）
l 分散システムでのプログラミングにおいて非決定性は望ましい。
l 入力文は対応する出力文の完了を条件とする条件付コマンドとみなせる
リーダ／ライタ問題：
リーダやライタとのランデヴーが可能な別種のコマンドが必要
l
問題１
サーバーの作成時にリーダとライタの名前がわからなければならない。（非現実的）
l
問題2
プロセス名を利用するのでサーバにエントリを1つしか用意できない。（実際の読み書きを行うのはサーバーなのでそこへ詳細を隠蔽したい（リソース・サーバ、透明性））
l
問題3
読み出しの並行は並行スレッド・プロセスを作成するCSPの並行文で実現できるが・・・
→ サーバ内のスレッド間の同期へ責任を移しただけ
→ スレッド間の同期に関する同期プリミティブが追加されない限りエレガントな解は存在しない。
入出力手続きを改良すればCSPにおける問題は緩和できる。
→ 遠隔手続き呼び出しやAdaのランデブーの開発へ・・・
特徴：
l
手続き呼び出しは呼ばれた手続きが完了するまでは呼び出し元がブロックされる
→ CSPの入出力に類似
→ 通信に利用できる（実装はメッセージ・パッシング）。
l プロセス名でなく手続き名によるならば、プロセスにエントリが複数作れる
l 通信の詳細が隠蔽される(透明性)
l 遠隔手続きの組を備えるプロセスとしてリソース・サーバが実現できる（クライアント／サーバ通信、モニタに類似）
l
サーバは受動的
→ クライアントとサーバ間は非対称（ランデヴーの対称性と対比）：
Ø RPCは通信用
Ø ランデヴーは同期用
RPCの実装と利用例は4章で詳説
Adaのランデヴー（Rendezvous）は分散環境での遠隔ランデヴーのために設計されたものではないが、
l ランデヴーにおける手続き呼び出し概念の利用
l 言語に非決定的な並行プロセスの機能を追加
を示すよい例。
特徴：
l 受動的なRPCの手続き呼び出しとは異なり、ランデヴーの手続き呼び出しは受付準備の完了を示す。（Adaではaccept文： キーワードacceptの後に手続き定義部が続く）
l 実行はaccept文で指定された手続き名を、呼び出し側が指定して行われる。
l あるエントリが実行中は呼び出し側とその他の呼び出しはブロックされる。
l accept文はパラメタの交換ができ動作はatomic
l 排他が必要でない部分はaccept文の外に置かれて並行に実行される。
l クライアント／サーバーではaccept文はサーバー側にのみ現れる。クライアント側は呼び出すだけ。
l CSPのalternativeの代わりにselect文がある。when節で条件指定。
l
図3.18は例題の解：
l rwタスクはサーバ
l 読み手や書き手のクライアントはaccept文で指定されている手続きを呼び出す。
l この例では実現されていないが実際の読み書き動作もサーバーに埋め込める（startread内でプロセスを作成すればよい）。
l 各エントリはentry文で公開（export）され、遠隔手続きとして呼び出せる。