計算機プログラミング輪講 I&II ’97:
Dough Lee: Concurrent Programming in Java ＃ 1

Tutorial: 並行制御と並行プログラミング
久野靖∗

1997.9.1

はじめに1• 以下の puzzle の前提: メモリの読み、書きは atomic• 基本的なアイデア: メモリに「旗」を立て、旗が立っていれば他人は入らないようにする。

今回は表記の本の輪講に決まったわけですが、本日はキックオフということで、並行プログラミングのチュートリアルを簡• naive な解だとぼろぼろ → じゃあどうする?

単にやります。

Process A:

2

並行プロセスと競合

while(flag != 0) ;flag = 1;

2.1

裸の計算機では…

/* some task */flag = 0;

Q 複数の実行主体 (プロセス、スレッド) が並行して実行 →• Dekker の解

そもそも、なんでそんなことが起こり得るの?

Q 並行プロセスは、なぜ制御しなければならないの?

Process A:flag_a = 1;

Q 並行プロセスを制御する方法?

while(flag_b == 1) {while(turn != ’a’) flag_a = 0;

Q たとえば、次の並行プロセスの競合を解消するには?
Process A:
load r1,countadd

flag_a = 1;

Process B:
load r1,count

r1,$1

store r1,countadd}/* some task */turn = ’b’; flag_a = 0;

r1,$1

store r1,count• Peterson の解

並行プロセスを制御する基本は排他制御 (コードのある部分 —排他領域、critical region — は一時には 1 つのプロセスしか入

Process A:
flag_a = 1; turn = ’a’;

れなくする。

• 排他制御を実装する方法? → 旧来の Unix では…

while(turn = ’a’ && flag_b == 1) ;/* some task */∗ 筑波大学大学院経営システム科学専攻

flag_a = 0;1

2.2

現実の計算機では…

3.2

イベントカウンタ

いちいち前節のようなアルゴリズムでは大変

イベントカウンタ—番号札のようなもの• 順番にスケジュールとは限らない• Read(E) — E の値を返す• busy wait loop は無駄• Advance(E) — E の値を 1 ふやす• Await(E, v) — E の値が v になるまで待つ→ ではどうする?

• 例題: 生産者/消費者 (排他が不要)• より高機能な命令: Test And Set、Swap などの命令

eventcounter in, out;

• 短い排他制御の上に長い排他制御を組み立てる

Producer:3

様々なプリミティブ/言語機構

3.1

セマフォ

/* produce */seq = seq + 1;

seq = seq + 1;
await(in, seq);

await(out, seq-N); /* get item *//* put item */advance(out);

セマフォとは、特別な機能を持ったカウンタのようなもの。

advance(in);• P 操作: カウンタを減らす。0 のときは呼んだプロセスは寝る

3.3• V 操作: カウンタを増やす。0 だったときは増やす変わりに一人起こす

Consumer:/* consume */モニタ

セマフォは構造化されてない…簡単にデッドロックさせてしまう。→より構造化/高レベルの言語機構→モニタ (Hore 1974,• 実際には P とか V とか言うより wait, signal という名前

Brinc Hansen 1975)。

• 単純な排他制御はバイナリセマフォ(初期値が 1) で• モニタは言語構造→コンパイラがサポート

Process A:
wait(mutex);• モニタは排他領域→一時には 1 つのプロセスだけが実行• モジュールの形→付属する手続き=モニタ手続き (入口で排他制御)/* some task */signal(mutex);• 条件を伴う待ち合わせ→条件変数• 例題: 生産者/消費者

monitor ProducerConsumer
semaphore empty = 0, full = N;

condition full, empty;
integer count;

Producer:procedure put;
begin

Consumer:/* produce */wait(full);wait(empty);
wait(mutex);wait(mutex);/* get item *//* put item */signal(mutex);

signal(mutex);
signal(empty);

signal(full);/* consume */if count = N then wait(full);/* put item */count = count + 1;
if count = 1 then signal(empty);end;2表 1: モニタの分類
実行中優先特性

実行中非優先Signal and Urgent Wait

Signal and Wait

Ep < Sp < Wp
Priority Blocking

Ep = Sp < Wp
No Priority Blocking

Signal and Continue

Wait and Notify

Non-Blocking

Ep < Wp < Sp
Priority Non-Blocking

Ep = Wp < Sp
No Priority Non-Blocking

Quasi-Blocking

Ep < Wp = Sp
Priority Quasi-Blocking

Ep = Wp = Sp
No Priority Quasi-Blocking

ExtendedSignal and Return

Immediate Return

Ep < Wp
Priority Immediate ReturnBlocking

Ep = Wp
No Priority Immadiate ReturnAutomatic Signal
Automatic SIgnal

Ep < Wp
Priority AUtomatic Signal

Ep = Wp
No Priority Automatic Signal的に起きる。つまり signal が不要。その代わり実装が大procedure get;
begin

変。条件式がモニタ変数のみしか参照できないという制約を設けるとやや実装が楽。

if count = 0 then wait(empty);/* remove item */Buhr, Frotier, Coffin のサーベイではモニタを分類するのに、count = count - 1;
if count = N - 1 then signal(full);• Ep — 呼ぼうとしている人の優先順位

end;
count = 0; /* initialization */• Sp — signal した人の優先順位• Wp — wait している人の優先順位

end monitor;の大小関係に基づいて整理している。

モニタ機構にはいくつものバリエーションがある。

なお、モニタの中で別のモニタを呼ぶ (nested monitor calls)• Hoare のモニタ: signal したとき、対応する wait プロセス のはデッドロックの可能性があり危うい。
があれば、まずそれが動く (signal した人は寝る)。終った
ら signal した人が続いて動作。間に他のプロセスは介在

3.4

しない。

メッセージパッシング• Brinch Hansen のモニタ: signal はモニタ手続きの最後のメッセージパッシングは立派な並行制御機構。一番簡単なも文でなければいけない。signal した人は直ちにモニタから のとして次のものを考える出さされる。次は wait していた人が実行。
• send(相手, message)• 自動シグナルモニタ: wait が「wait 条件式」という形を• receive(相手, message)している。条件が定期的に調べられ、成立していると自動3

Producrer:/* produce */Consumer:
receive(producer, mes);receive(consumer, mes); send(producer, mes);send(consumer, mes);/* consume */メッセージにもいろいろな分類がある。

• 同期的/非同期的• バッファされるか• 順序の保存• 返事の有無• future
たとえば ABCL/1 ではメッセージとして now、past、future の3 種類が使用できる。

4

オブジェクト指向並行プログラミング
ここまでやってる時間があるのかどうか?

• Actor モデル• ABCL/1• 条件同期の表現方法• ガード• 明示的受信• 受理集合• 継承異常• ...

参考文献[1] Tanenbaum, Modern Operating Systems, Prentice-Hall,
1992.
[2] 前川守, オペレーティングシステム, 岩波, 1988.

[3] Peter A. Buhr, Michel Fortier, Michael H. Coffin, Monitor Classification, ACM Computing Surveys, vol. 27,
no. 1, pp. 63-106, 1995.

4