例：
S: セマフォ（あるいは，セマフォ変数）と呼ぶ
P(S), V(S) ともに不可分に実行されなければならない．
P(S), V(S) ： 「クリティカルセクション」として実行されることが重要．
大きなクリティカルセクション ↓ （還元）
小さなクリティカルセクション
59
セマフォ（ Semaphore ）の使用方法
ークリティカルセクション問題の解決方法としてー
60
repeat
P(mutex) ;
危険区域（クリティカルセクション）
V(mutex)
残り区域 until false;
初期値 mutex := 1
セマフォ（ Semaphore ）の使用方法 ー順序グラフの実行ー
61 61
S1
S2 S3
S7 S4
S5 S6
図９．６ 対応する並行文のない 順序グラフ
var a, b, c, d, e, f, g : semaphores ;
（* すべてのセマフォの初期値は0である．*） begin
parbegin
begin S1; V(a); V(b); end ;
begin P(a); S2; S4; V(c); V(d); end ; begin P(b); S3; V(e); end ;
begin P(c); S5; V(f); end ;
begin P(d); P(e); S6; V(g); end ; begin P(f); V(g); S7; end ;
parend ; until false;
セマフォの新しい定義
古典的定義の問題点
繁忙待機（busy-waiting）が生じる．
プロセッサを浪費
待つ場合は，プロセッサを解放する（プロセスをサスペンドさせる）した方がよ い．．
セマフォの新しい定義
プロセスが待たなければならない場合は，（古典的定義のように繁忙待機で 待つのではなく）そのプロセスをサスペンドさせて，プロセッサを解放させる
（他プロセスに明け渡す）
P, Vの新しい定義
P(S):
S := S – 1;
if S < 0
then begin
そのプロセスをサスペンドして，（Sに対応した）キューにつなぐ．
end ;
V(S):
S := S + 1;
if S ≤ 0
then begin
キューの先頭にあるプロセスを起こす．
end ;
S ≤ 0のとき，|S|が待ちプロセス数を表す． 62
セマフォの実現
P(S), V(S) が不可分に実行されなければならない．
本来のクリティカルセクション → 小さなクリティカルセクションに 還元（ P(S), V(S) 操作）
P(S), V(S) のクリティカルセクション問題
（新しい定義の）実現
P(S), V(S) は通常システムコールとして提供
システムモードで実行
１）シングルプロセッサの場合
割込み禁止にして実行，またはハードウェア提供の不可分命 令（例：テストアンドセット命令など）
2 ）マルチプロセッサの場合
割込み禁止にしてもだめ．
ソフトウェアによる実現，またはハードが提供する不可分命令
（例：テストアンドセット命令など）を用いて実現
63
古典的プロセス協調問題
代表的なプロセス協調問題
有限バッファ問題（ bounded buffer problem ）（制 約バッファ問題）（生産者／消費者問題）
読書き問題（ Reader/Writer problem ）
食事をする哲学者問題，哲学者の食事問題
（ Dining philosophers problem ）
64
有限バッファ問題（ Bounded buffer problem ）
同期命令： セマフォ
セマフォ（変数）
full: 一杯のバッファ数
empty ： 空のバッファ数
mutex: バッファへのアクセスを相互排除するため
に使用
65
有 限 バ ッ フ ァ 問 題
66 begin
full := 0 ; empty := n ; mutex := 1 ; parbegin
producer : repeat ・・・
nextpへ１つの項目を生産して入れる．
・・・
P(empty) ; P(mutex) ; ・・・
nextpをbufferに追加する．
・・・
V(mutex) ; V(full) ; until false ; consumer : repeat P(full) ; P(mutex) ; ・・・
bufferから１つの項目を取出してnextcへ置く．
・・・
V(mutex) ; V(empty) ; ・・・
nextcの中の項目を消費する．
・・・
until false ; parend ;
end
読書き問題（ Readers/Writers problem ）
データファイルへのアクセス
データを読み出すだけのプロセス（リーダ，Reader）
データを読書きするプロセス（ライタ，Writer）
注意点
リーダとライタが同時に１つのデータファイルにアクセスすると，データの一貫性が 保てなくなる可能性あり．
ライタは相互排除でデータにアクセスする必要あり．
ファイルアクセスの優先度
待ちプロセスの中に，リーダとライタが混在していたら，どちらのプロセスを優先し て中に入れるか？
第一読書き問題（第一種の読書き問題）
リーダが優先される．
第二読書き問題（第二種の読書き問題）
ライタが優先される．
飢餓状態（starvation，スタベーション）
飢餓状態になる可能性のあるのは，どのプロセスか？
第一読書き問題（第一種の読書き問題）
ライタ
第二読書き問題（第二種の読書き問題）
リーダ 67
読書き問題（ Readers/Writers problem ）
ライタ リーダ
データファイル
ライタ リーダ
待ちプロセス
69
初期値 セマフォ mutex=1, wrt =1, integer readcount = 0
第一種の読書き問題（リーダ優先）
P(mutex) ;
readcount := readcount + 1 ; if readcount >= 1 then p(wrt ) ; V(mutex) ;
・・・
読取りが実行される．
・・・
P(mutex) ;
readcount := readcount – 1 ; if readcount = 0 then V(wrt ) ; V(mutex) ;
読取り系プロセス（リーダ）の一般的な構造
P(wrt) ; ・・・
書込みが実行される．
・・・
V(wrt) ;
書込み系プロセス（ライタ）の一般的な構造
ライタを待たせる
待ちライタを起動
食事をする哲学者問題，哲学者の食事問題（１／４）
(Dining Philosophers problem)
問題の説明
５人の哲学者がテーブルに座っている．
哲学者と哲学者の間に，１本（一対ではない）の箸がおいてある．
哲学者の動作： 下記の食事と思索の２つの動作を繰り返す．
食事：左右の２本の箸をとりあげて食事する．
思索にふける：食事の後，持っていた箸をおいて，思索にふける．
70
哲学者
箸（１本，一対ではない）
食事をする哲学者問題，哲学者の食事問題（２／４）
(Dining Philosophers problem)
やりたいこと：哲学者の動作を記述したい．
哲学者の動作
両方の箸を取り上げて，食事をする．
食事がすんだら，持っている箸を元の場所において，思索にふける．
上記の動作を繰り返す．
要請
デッドロックになってはいけない．
食事をしたい哲学者が餓死してはいけない．（飢餓状態が発生してはいけない）
箸の取り上げは，排他制御で行わなくてはならない．
71
哲学者
箸（１本，一対ではない）
食事をする哲学者問題，哲学者の食事問題（３／４）
(Dining Philosophers problem)
72
初期値 セマフォ chopstick[i] = 1 repeat
P(chopstick[i]) ;
P(chopstick[I + 1 mod 5]) ; ・・・
食べる（食事）
・・・
V(chopstick[i]) ;
V(chopstick[I + 1 mod 5]) ; ・・・
考える（思索にふける）
・・・
until false
１つの例：
どの哲学者も食事をするときは，同じ動作をする（対称動作）
まず，左の箸をとって，次に右の箸をとる．
箸１本の取り上げは，排他制御で行う
排他制御：セマフォを用いる．．
デッドロックが生じる可能性あり！
みんなが同時に，左の箸を取り上げた場合
食事をする哲学者問題，哲学者の食事問題（４／４）
(Dining Philosophers problem)
73
デッドロックを生じさせない方法
１）４人しかテーブルにつけないようにする．
２）左右の箸を同時に取り上げる．
この動作をクリティカルセクションにする．
３）非対称な解を用いる．
偶数番目：右の箸から．
奇数番目：左の箸から
飢餓状態の回避はどうするか？