CPUスケジューリング

(1)

１０－１２並行プロセス

(2)

順序グラフ



今まで，

 プログラムの逐次的実行



これから，

 プログラム内の並行実行



上記の文を平行に実行したい！



①と②は，並列に実行できる．



③は，①の後



④は，③の後

2 ① a:=x+y; ② b:=z+1; ③ c:=a-b; ④ w:=c+1;

(3)

順序グラフの定義

3

S1

S2

S3

S7

S4

S5

S6

図９．１順序グラフ

S1

S2

S3

図９．２循環のある順序グラフ 循環のあるグラフは考えない．

(4)

並行に実行できるための条件



記号の定義

R(Si)：文Siで読み出される変数の集合

W(Si)：文Siで書きこまれる変数の集合



例



R(③)＝｛a,b｝，W(③)＝｛ｃ｝



２つの連続する文S1,S2が並行実行可能であるための必

要十分条件

以下の３つが成立すること（Bernsteinの条件（1966））

1)R（S1）∩W(S2)＝｛｝

2)W（S1） ∩ R(S2)＝｛｝

3)W（S1） ∩ W(S2)＝｛｝

4 ① a:=x+y; ② b:=z+1; ③ c:=a-b; ④ w:=c+1;

(5)

仕様



プログラミング言語で用いる並列命令

１）ForkとJoin構造体

２）parbeginとparendの構造体

(6)

ForkとJoin構造体（１／３）



Conway(1963), Dennis and Van Horn(1966)が提案

6

S1

Fork

S2

S3

join

S1

S2

図９．３ fork構造体のための順序グラフ図９．４ join構造体のための順序グラフ

(7)

ForkとJoin構造体（２／３）

7

Fork

S2

S3

join

count:=2;

fork L1;

・

S3;

go to L2;

L1: S2;

L2: join count;

Join命令；

Count:= count -1;

If count != 0;

then quit;

(8)

ForkとJoin構造体（３／３）

ー図９．１のプログラムー

8

S1

S2

S3

S7

S4

S5

S6

S1;

Count:=3;

Fork L1;

S2;

S4;

Fork L2;

S5;

Go to L3

L2: S6;

Go to L3;

L1: S3;

L3: join count;

S7;

(9)

並行文：parbeginとparendの構造体（１／２）



より高級な構造体



Dijkstra(1965)により提案



形式

Parbegin S1; S2; ・・・, Sn parend;

9

S0

S2

Sn-1

Sn+1

S1

Sn

図９．５並行文のための順序グラフ

(10)

並行文：parbeginとparendの構造体（２／２）

10 ① a:=x+y; ② b:=z+1; ③ c:=a-b; ④ w:=c+1;

parbegn

a:= x+y;

b:= z+1;

parend

c:= a-b;

w:= c+1;

S1;

parbegin

S3;

begin

S2;

S4;

parbegin

S5;

S6;

parend;

end

parend

S7;

S1

S2

S3

S7

S4

S5

S6

(11)

比較（fork/joinとparbegin/parend）（１／２）



任意の順序グラフを表現でき

るか？



（例）図９．６を例にとると，

 並行文（parbegin/parend）

では表現できない．

 Fork/joinでは，表現できる．



使いやすさ

 Fork/join <

parbegin/parend

 任意の順序グラフを表現で

きる必要があるか？

 多くの問題にできようでき

るだけで十分では？

11

S1

S2

S3

S7

S4

S5

S6

図９．６対応する並行文のない順序グラフ

S1;

count1:= 2;

fork L1;

S2;

S4;

count 2:=2;

fork L2;

S5;

go to L3;

L1: S3;

L2: join count1;

S6;

L3: join count2;

S7;

(12)

比較（fork/joinとparbegin/parend）（２／２）



Parbegin/parend構造

は，fork/joinで記述で

きる．

count:=n;

fork L2;

fork L3;

・

fork Ln;

S1;

go to Lj;

L2: S2;

go to Lj;

L3: S3;

go to Lj;

・

Ln: Sn;

Lj; join count;

(13)

プロセスの概念



プロセスとは？

（厳密な概念はない！定義は困難．）

１）実行しているプログラム

２）疑似プロセッサ

プログラムを実行するための器

OSが管理するための単位

プロセスのことをタスクとも言う．

13 図９．６対応する並行文のない順序グラフ

(14)

プロセスの状態



実行中(running)

命令をプロセッサで実行している状態



実行待ち（ready）

プロセッサの割り当てを待っている状態



待機中（封鎖，blocked, suspended）

ある事象が起こるのを待っている状態

入出力の完了，．．．



デッドロック（deadlocked）

14 図９．７プロセス状態推移図（準備中_）

(15)

プロセスの階層構成



プロセスグラフ

プロセスの依存関係を表すグラフ

15

(16)

危険区域（クリティカルセクション，critical section）

問題



危険区域（クリティカルセクション，critical section）

際どい区域（際どい領域）とも言う．



例として，生産者／消費者問題(Producer/consumer

problem)を考える．

16

(17)

生産者／消費者問題(Producer/consumer problem)（１／３）



生産者：消費者によって消費されるものを生産する．



消費者：生産者がつくったものを消費する．

（例）



実社会：どら息子，．．．



計算機の世界

プリンタ，コンパイラ，アセンブラ，デバイスドライ

バ，．．

17

(18)

生産者／消費者問題(Producer/consumer problem)（２／３）



注意すべきこと：

生産者：まだ消費していないところに，上書きして

はいけない．

消費者：生産されていないところから読んではい

けない．



格納する場所が必要

バッファ



バッファの大きさ

無限長：制約なしバッファ(unbounded-buffer)

有限長：制約バッファ(bounded-buffer)

18

(19)

生産者／消費者問題：制約バッファでの実現（３／３）

 使用する変数  n：バッファの大きさ  in: 次の空きバッファを指すポインタ（生産者はinで指されたバッファに格納する）  Out: 詰まっている最初のバッファを指すポインタ（消費者はoutで指されたバッファから取り出す）  注意事項  バッファが一杯，空をどうやって判断するか？  in==outのとき，バッファは空

 (in+1 mod n) == out のとき，バッファは一杯

19

out

in

(20)

処理概要

20 parbegin producer: begin repeat ・・・項目を生産してnextpに入れる・・・

while in+1 mod n = out do skip; /*バッファが一杯か？*/ buffer[in] := nextp ; in := in + 1 mod n ; /*ポインタを＋１*/ until false end; consumer: begin repeat

while in = out do skip; /*バッファが空か?*/ nextc := buffer[out] ;

out := out + 1 mod n ; /*ポインタを＋１*/ ・・・ nextcの項目を消費する・・・ until false ; end ; ・生産者：バッファが一杯でなければ，バッファに格納．ポインタinを＋１・消費者：バッファが空でなければ，バッファから取り出す．ポインタoutを＋１ 同時に一杯にできるバッファ数最大：バッファ容量(n) －１

(21)

修正アルゴリズム

 バッファ容量数(n)だけ使えるようにしたい．  方針  一杯であるバッファ数を記憶しておく． counter ：一杯であるバッファ数 counter == 0; バッファが空 counter == n（バッファ数）; バッファが満杯処理概要  生産者  バッファが満杯かどうかチェック  満杯でなければ，  バッファに格納  ポインタinを＋１  消費者  バッファが空かどうかチェック  空でなければ，  バッファから取り出す  ポインタoutを＋１ 21

(22)

修正した処理(プログラム)の概要

22 生産者 repeat ・・・項目を生産してnextpに入れる・・・

while counter = n do skip; /*バッファが一杯か？*/ buffer[in] := nextp ; in := in + 1 mod n ; /*ポインタを＋１*/ counter := counter + 1 ; until false 消費者 repeat

while counter = 0 do skip; /*バッファが空か?*/ nextc := buffer[out] ;

out := out + 1 mod n ; /*ポインタを＋１*/ counter := counter - 1 ; ・・・ nextcの項目を消費する・・・ until false ;

(23)

前記のプログラムは正しく動作するか？

 生産者と消費者で共有している（共有変数）counterがくせもの！  _{Counter操作の実現コード} （例）  counter := counter +1 ; ①register1 := counter ; ②register1 := register1 + 1 ; ③counter := register1 ;  _{counter := counter -1 ;} ④register2 := counter ; ⑤register2 := register2 - 1 ; ⑥counter := register2 ; 23 正しく動作しない系列の系・いま，counter = 0とする．左記の２つの文がまじりあって実行されると，（_{論理的には，＋－１で，counter = 0のはず}_）１）生産者が①を実行(r1 =0, c=0) ２）生産者が②を実行(r1 = 1, c=0) ここで，何らかの理由で生産者の実行が中断し，消費者に実行が移る．（理由の例：ラウンドスケジューリングでタイムスライスを使い切って，たまたま消費者プログラムが実行対象に選択された）３）消費者が④を実行(r2=0, c=0) ４）消費者が⑤を実行(r2 = -1, c=0) ５）消費者が⑥を実行(r2= -1, c= -1) （この後，何らかの理由で，生産者に実行が移った）６）生産者が③を実行(r1=1, c=1) 上記の実行結果： counter = 1 → 論理的に正しくない．

(24)

クリティカルセクション問題の定義



クリティカルセクションとは（critical section，危険領域，

際どい領域）とは？

まじあって実行されてはいけない区域，領域，操作の

こと．

操作が不可分に実行されなくてはいけない．

複数のプログラムが共有オブジェクトへの読書きを行

うと，必ず生じる．



有限バッファの例

Counterへの操作(+1, -1)

24 プログラム１プログラムｎ共有オブジェクト読書き・・・読書き

(25)

クリティカルセクション問題の例



リストの管理（ダブルポインタ）

(26)

クリティカルセクション問題を解決する解に要請する

（満たすべき）条件

今から，考える解は，次の３つの条件を満たす必要あり．

１）相互排除(Mutual exclusion)

 クリティカルセクションに同時に入れるプロセスは高々１つ

２）前進(Progress)

 クリティカルセクション内にプロセスがない場合，入口で待って

いるプロセスの内，尐なくとも１つは有限時間でクリティカルセ

クションに入れる．（必ずどれかは入れる．）

３）有限待機(Bounded waiting)

 クリティカルセクションへ入ろうとして待たされる時間は，有限

時間でなければならない．（待っているプロセスからみれば，有

限時間待てば，必ずクリティカルセクションに入れる．永久に待

たされることはない．）

26

(27)

仮定と解について



仮定

 プロセスの実行速度は任意（でも，!= 0）

 機械命令は不可分に実行される．

 Load, store, test, ….

クリティカルセクションを実現する解



歴史をみる．



ソフトウェアによる解

 基本的な機械命令を用いる（特殊な機械命令はない）．

１）プロセス数が２つの場合（最も単純な場合）

２）プロセス数が一般（ｎ）の場合



ハードウェアによる解

 特殊な機械命令を用いた解

27

(28)

ソフトウェアによる解

ープロセス数が２の場合ー



プロセス

プロセス０： P0

プロセス１： P1



変数（整数）

i = 0, 1

j = 1 – i

i = 0, j = 1

I = 1, j = 0

28

(29)

ソフトウェアによる解

ープロセス数が２の場合ーアルゴリズム１



考え方：

 クリティカルセクションに入れるプロセスを指定する共有変数を設ける．

29 Repeat

while turn≠i do skip ;

危険区域（クリティカルセクション） turn = j ; 残り区域 until false; 考察 相互排除の要請は満足 前進，有限待機の要請は満足していない． プロセスは交互にしかクリティカルセクションに入れない．

(30)

アルゴリズム１

30 自分の番か？ＣＳ実行お前の番だ！ No Yes

PO

自分の番か？ＣＳ実行お前の番だ！ No Yes

P1

変数 Read Write Read Write ＣＳ：クリティカルセクション

(31)

ソフトウェアによる解

ープロセス数が２の場合ーアルゴリズム２（１／３）



考え方：

 クリティカルセクションに入っているかどうかを識別する．

 識別する変数: flag[i] 論理変数

 Flag[i] = true（クリティカルセクションに入っている）  Flag[i] = false（〃に入っていない） 31 Repeat

while flag[j] do skip ; flag[i] := true ;

危険区域（クリティカルセクション） flag[i]:= false ;

残り区域 until false;

(32)

アルゴリズム２（２／３）

32 相手が入っているか？ＣＳ実行 Yes No

プロセス PO

出たぞ！自分が入っているぞ！ＣＳ：クリティカルセクション相手が入っているか？ＣＳ実行 Yes No

プロセス P1

出たぞ！自分が入っているぞ！

(33)

ソフトウェアによる解

ープロセス数が２の場合ーアルゴリズム３（１／３）



アルゴリズム２がうまくいかなかった理由：

自分がクリティカルセクションに入ったことを告げる

前に，誰かクリティカルセクションに入っているかどう

かを判断している．

誰か入っていないか？

while flag[j] do skip ;

クリティカルセクションに自分が入ったことを告げる．

flag[i] := true ;

(34)

ソフトウェアによる解

ープロセス数が２の場合ーアルゴリズム３（２／３）



改良点：

クリティカルセクションに入りたいことをつげる．

↓

誰か入りたがっていないか？

34 Repeat flag[i] := true ;

while flag[j] do skip ;

危険区域（クリティカルセクション） flag[i]:= false ;

残り区域 until false;

(35)

アルゴリズム３（３／３）

ＣＳ実行相手が入りたがっているか？ Yes No

プロセス PO

出たぞ！入りたいよう！ＣＳ：クリティカルセクションＣＳ実行相手が入りたがっているか？ Yes No

プロセス P1

出たぞ！入りたいよう！

(36)

アルゴリズム３はクリティカルセクション問題を

正しく解決するか？

１）相互排除の要請は満たされているか？

ＯＫ

２）前進の要請は満たされているか？

満たされていない．

どの待ちプロセスも入れないことが起こり得る．

例：

36

(37)

Repeat

flag[i] := true ; turn := j ;

while( flag[j] and turn = j ) do skip ; 危険区域（クリティカルセクション） fkag[i]:= false ; 残り区域 until false;

ソフトウェアによる解

ープロセス数が２の場合ーアルゴリズム４（１／３）



正しいアルゴリズム

Perterson[1981]による

37

(38)

アルゴリズム４（２／３）

ＣＳ実行相手が入りたがっているか？ Yes No

プロセス PO

出たぞ！入りたいよう！自分が先に手を付けたか？（相手の手が上にあるか？）カルタに手を付ける Yes No パスＢ パスＡ ＣＳ実行相手が入りたがっているか？ Yes No

プロセス P1

出たぞ！入りたいよう！自分が先に手を付けたか？（相手の手が上にあるか？）カルタに手を付ける Yes No パスＢ パスＡ カルタＣＳ：クリティカルセクション

(39)

アルゴリズム４が３つの要請を満たしていることの証明概要



アルゴリズム４

Simplified Dekker’s Algorithm(Pertersonが提案)とも言

う．

Dekker：最初に提案した学者

Dekkerが提案したアルゴリズムは複雑だったので，

Pertersonが簡単にしたアルゴリズムが，このアルゴリズム４



３つの要請

１）相互排除

２）前進

３）有限待機

39

(40)

アルゴリズム４が「相互排除」の要請を満たしていることの証明概要（１／

６）



相互排除

 クリティカルセクション（ＣＳ）に同時に入れるプロセスは高々１つ．

証明のやり方



背理法を用いる．

 ２つのプロセスがＣＳに入れるとする．

↓

 矛盾を導く．だから，２つのプロセスがＣＳには入れない．

↓

だから，同時にＣＳに入っているプロセスは高々１つ．



プロセスＰ０のＣＳへの入り方

１）パスＡ

２）パスＢ

40

(41)

１）パスＡ経由でＣＳに入った場合  Ｐ０がパスＡ経由で入った時，Ｐ１は， _{「入りたいよう！」} 以前を実行していた．  この後，Ｐ１は， _{「入りたいよう！」，「カルタに手付」} を実行  従って，Ｐ１は，パスＢ経由でしか入れない．（理由：Ｐ０がすでにＣＳに入っているので）  Ｐ１がパスＢ経由で入ったならば，Ｐ０の手が上になければならない．  これはありえない．（理由：Ｐ０が先に入ったのだから，当然，Ｐ１の手はＰ０の手の下にあるはず．）矛盾  従って，ＣＳにいるＰ０は，ＣＳにはパスＡ経由で入っていない． 41 ＣＳ実行相手が入りたがっているか？ Yes No 出たぞ！入りたいよう！自分が先に手を付けたか？（相手の手が上にあるか？）カルタに手を付ける Yes No パスＢ パスＡ

アルゴリズム４が「相互排除」の要請を満たしていることの証明概要（２／

６）

(42)

２）パスＢ経由でＣＳに入った場合



Ｐ１のＣＳへの入り方：

２－１）パスＡ

２－２）パスＢ

の2種類

上記，各々の場合を考える．

42 ＣＳ実行相手が入りたがっているか？ Yes No 出たぞ！入りたいよう！自分が先に手を付けたか？（相手の手が上にあるか？）カルタに手を付ける Yes No パスＢ パスＡ

アルゴリズム４が「相互排除」の要請を満たしていることの証明概要（３／

６）

(43)

２－１）パスＡ経由の場合  状況を整理すると，Ｐ０：パスＢ，Ｐ１：パスＡＰ０：Ｐ１が入りたがっているので，パスＢ経由で入った．Ｐ１：Ｐ０が入りたがっていないので，パスＡ経由で入った．  Ｐ１が入った時は，Ｐ０は，「入りたいよう！」以前を実行（Ｐ１は，「カルタの手付」を終了している）  Ｐ０は，パスＢ経由で入れない．（理由：Ｐ１の手がＰ０の上にあることはない．というのは，Ｐ１の方が早く「カルタの手付」を実行しているから）矛盾  従って，ＣＳにいるＰ０が，パスＢ経由で入った場合，Ｐ１はパスＡ経由では入っていない． 43 ＣＳ実行相手が入りたがっているか？ Yes No 出たぞ！入りたいよう！自分が先に手を付けたか？（相手の手が上にあるか？）カルタに手を付ける Yes No パスＢ パスＡ

アルゴリズム４が「相互排除」の要請を満たしていることの証明概要（４／

６）

(44)

２－２）パスＢ経由の場合  状況を整理すると，Ｐ０：パスＢ，Ｐ１：パスＢＰ０：Ｐ１が入りたがっているので，パスＢ経由で入った．Ｐ１：Ｐ０が〃  同時にパスＢ経由で入ったことはあり得ない！（理由：Ｐ０，Ｐ１もパスＢ経由で入ったということは，相手の手が上にあるのを確認してから入ったことになる）  これは，あり得ない．  というのは，「カルタの手付き」は１回だけなので，必ずどちらかの手が上になるので．矛盾  従って，ＣＳにいるＰ０が，パスＢ経由で入った場合，Ｐ１はパスＢ経由では入っていない． 44 ＣＳ実行相手が入りたがっているか？ Yes No 出たぞ！入りたいよう！自分が先に手を付けたか？（相手の手が上にあるか？）カルタに手を付ける Yes No パスＢ パスＡ

アルゴリズム４が「相互排除」の要請を満たしていることの証明概要（５／

６）

(45)

まとめ



Ｐ０，Ｐ１が同時にＣＳに入って

いるとすると，矛盾が生じる．



だから，Ｐ０，Ｐ１が同時に入っ

ていることは，あり得ない．



従って，同時にＣＳに入ってい

るプロセスの数は，

高々１つ

の

み．

アルゴリズム４が「相互排除」の要請を満たしていることの証明概要（６／

６）

(46)

アルゴリズム４が「前進」の要請を満たしていることの証明概要

（１／４）

前進



ＣＳに入っていない時，待ちプ

ロセスのどれか（この場合は，

もう１つのプロセス）が必ずＣＳ

には入れるか？



場合分け：

１）Ｐ０のみがＣＳに入ることを要

求，Ｐ１は要求しない

２）Ｐ０，Ｐ１の両方が要求

上記の各々の場合を考える．

(47)

アルゴリズム４が「前進」の要請を満たしていることの証明概要

（２／４）

１）Ｐ０のみがＣＳに入ることを要

求，Ｐ１は要求しない

の場合



Ｐ０はＣＳに入れる（自明）

(48)

アルゴリズム４が「前進」の要請を満たしていることの証明概要

（３／４）

２）Ｐ０，Ｐ１の両方が要求

の場合



両方ともＣＳに入れない状態

 ループで回っている状態

 相手が入りたがっている，かつ，

相手の手が下にある．



上記の状態はあり得ない．というの

は，カルタの手付は１回のみなので．



矛盾

 従って，Ｐ０，Ｐ１がＣＳに入ること

を要求した時，どちらかがＣＳに

入れる．

(49)

まとめ



ＣＳに誰も入っていない時，ＣＳ

に入りたいと要求したプロセス

は，ＣＳに入ることができる．

アルゴリズム４が「前進」の要請を満たしていることの証明概要

（４／４）

(50)

アルゴリズム４が「有限待機」の要請を満たしていることの証明概要

（１／２）

有限待機



ＣＳに入りたがった後，有限時

間でＣＳに入れるか？（永久に

待たされることはない．飢餓状

態（starvation）は生じない）

(51)

アルゴリズム４が「有限待機」の要請を満たしていることの証明概要

（２／２）



Ｐ０が有限時間で入れないとす

る．



これは，Ｐ１が何回も入る状態



Ｐ１が入れるということは，Ｐ１

の手の上に，Ｐ０の手がある，

ということ．



これはあり得ない．（Ｐ０の「カ

ルタの手付」は１回のみなの

で）



矛盾

 従って，ＣＳに誰も入っていない

時，ＣＳに入りたいプロセスは有

限時間で入れる．

(52)

アルゴリズム４が３つの要請を満たしていることの証明概要

まとめ

アルゴリズム４は，以下の３つの要請を満足すること

が証明？できた．



３つの要請

１）相互排除

２）前進

３）有限待機

52

(53)

プロセス数が一般，ｎ，の場合

53

Repeat

choosing[i] := true ;

number[i] := max ( number[0], number[1], ・・・, numbr[n-1] + 1 ); choosing [i] := false ;

for j := 0 to n-1 do begin

while choosing[j] do skip ;

while (number[j] ≠ 0 and (number[j], j ) < ( number[i] , i ) ) do skip ; end ; 危険区域（クリティカルセクション） number[i]:= 0 ; 残り区域 until false; アルゴリズム６ Lamport[1974]による パン屋アルゴリズム(bakery algorithm)

(54)

ハードウェアによる解



ハードウェアが提供する不可分（atomic）命令

（１）テスト・アンド・セット（Test-and-Set）命令

54

function Test-and-Set ( var target: boolean ) : boolean ; begin Test-and-Set := target ; target := true ; end ;

target

変数

②write

①read

true

(55)

ハードウェアによる解



テスト・アンド・セット（Test-and-Set）命令を用いたクリ

ティカルセクション問題を解決する方法

55

repeat

while Test-and-Set(lock) do skip ; 危険区域（クリティカルセクション） lock := false ; 残り区域 until false; 初期値 lock := false 但し，上記のアルゴリズムは，有限待機の要請を満足していない．

(56)

ハードウェアによる解



テスト・アンド・セット（Test-and-Set）命令を用いたクリティカルセクション問

題を解決する方法

 有限待機の要請も満足させるアルゴリズム

56 var j : 0…n-1 ; key : boolean ; repeat waiting[i] := true ; key := true ;

while waiting[i] and key do key := Test-and-Set(lock) ; waiting[i] := false ;

危険区域（クリティカルセクション） j := j + 1 mod n ;

while ( j ≠ i ) and ( not waiting[j] ) do j := j + 1 mod n ; if j = i then lock := false

else waiting[j] := false ; 残り区域

(57)

ハードウェアによる解

（２）スワップ（Swapp）命令

57

Procedure Swap ( var a, b: boolean ) ; var temp : boolean ;

begin temp := a ; a := b ; b := temp ; end ;

変数b

変数a

交換

(58)

ハードウェアによる解



スワップ命令を用いたクリティカルセクション問題を

解決する方法

58 repeat key := true ; repeat

Swapp ( lock, key) ; until key = false ;

危険区域（クリティカルセクション） lock := false ; 残り区域 until false; 初期値 lock := false 但し，上記のアルゴリズムは，有限待機の要請を満足していない．

変数lock

変数key

①true

②交換

(59)

セマフォ（Semaphore）



プロセス間同期のための構造体

 Dijkstra[1965]により提案



命令の種類：次の２つ．

 P命令

 V命令



_{P, V命令の定義（古典的定義）}



_P(S):

while S ≤0 do skip ;

S := S – 1 ;



_V(S):

S := S + 1 ;



_{S: セマフォ（あるいは，セマフォ変数）と呼ぶ}



_{P(S), V(S)ともに不可分に実行されなければならない．}



_{P(S), V(S)：}

「クリティカルセクション」として実行されることが重要．

 大きなクリティカルセクション

↓（還元）

 小さなクリティカルセクション

59

(60)

セマフォ（Semaphore）の使用方法

ークリティカルセクション問題の解決方法としてー

60 repeat P(mutex) ; 危険区域（クリティカルセクション） V(mutex) 残り区域 until false; 初期値 mutex := 1

(61)

セマフォ（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;

(62)

セマフォの新しい定義

 古典的定義の問題点  繁忙待機（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

(63)

セマフォの実現



_{P(S), V(S)が不可分に実行されなければならない．}



本来のクリティカルセクション → 小さなクリティカルセクションに

還元（P(S), V(S)操作）



P(S), V(S)のクリティカルセクション問題

（新しい定義の）実現



P(S), V(S)は通常システムコールとして提供



システムモードで実行

１）シングルプロセッサの場合

 割込み禁止にして実行，またはハードウェア提供の不可分命

令（例：テストアンドセット命令など）

2）マルチプロセッサの場合

 割込み禁止にしてもだめ．

 ソフトウェアによる実現，またはハードが提供する不可分命令

（例：テストアンドセット命令など）を用いて実現

63

(64)

古典的プロセス協調問題



代表的なプロセス協調問題

有限バッファ問題（bounded buffer problem）（制

約バッファ問題）（生産者／消費者問題）

読書き問題（Reader/Writer problem）

食事をする哲学者問題，哲学者の食事問題

（Dining philosophers problem）

(65)

有限バッファ問題（Bounded buffer problem）



同期命令：セマフォ



セマフォ（変数）

full: 一杯のバッファ数

empty：空のバッファ数

mutex: バッファへのアクセスを相互排除するため

に使用

65

(66)

有

限

バ

ッ

フ

ァ

問

題

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

(67)

読書き問題（Readers/Writers problem）

 データファイルへのアクセス  データを読み出すだけのプロセス（リーダ，Reader）  データを読書きするプロセス（ライタ，Writer）  注意点  リーダとライタが同時に１つのデータファイルにアクセスすると，データの一貫性が保てなくなる可能性あり．  ライタは相互排除でデータにアクセスする必要あり．  ファイルアクセスの優先度  待ちプロセスの中に，リーダとライタが混在していたら，どちらのプロセスを優先して中に入れるか？  第一読書き問題（第一種の読書き問題）  リーダが優先される．  第二読書き問題（第二種の読書き問題）  ライタが優先される．  飢餓状態（starvation，スタベーション）  飢餓状態になる可能性のあるのは，どのプロセスか？  第一読書き問題（第一種の読書き問題）  ライタ  第二読書き問題（第二種の読書き問題）  リーダ 67

(68)

読書き問題（Readers/Writers problem）

ライタリーダデータファイルライタリーダ待ちプロセス

(69)

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) ; 書込み系プロセス（ライタ）の一般的な構造ライタを待たせる待ちライタを起動

(70)

食事をする哲学者問題，哲学者の食事問題（１／４）

(Dining Philosophers problem)



問題の説明

 ５人の哲学者がテーブルに座っている．

 哲学者と哲学者の間に，１本（一対ではない）の箸がおいてある．

 哲学者の動作：下記の食事と思索の２つの動作を繰り返す．

 食事：左右の２本の箸をとりあげて食事する．  思索にふける：食事の後，持っていた箸をおいて，思索にふける． 70 哲学者箸（１本，一対ではない）

(71)

食事をする哲学者問題，哲学者の食事問題（２／４）

(Dining Philosophers problem)

 やりたいこと：哲学者の動作を記述したい．  哲学者の動作  両方の箸を取り上げて，食事をする．  食事がすんだら，持っている箸を元の場所において，思索にふける．  上記の動作を繰り返す．  要請  デッドロックになってはいけない．  食事をしたい哲学者が餓死してはいけない．（飢餓状態が発生してはいけない）  箸の取り上げは，排他制御で行わなくてはならない． 71 哲学者箸（１本，一対ではない）

(72)

食事をする哲学者問題，哲学者の食事問題（３／４）

(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 １つの例： どの哲学者も食事をするときは，同じ動作をする（対称動作） まず，左の箸をとって，次に右の箸をとる． 箸１本の取り上げは，排他制御で行う 排他制御：セマフォを用いる．．デッドロック_{が生じる可能性あり！} みんなが同時に，左の箸を取り上げた場合

(73)

食事をする哲学者問題，哲学者の食事問題（４／４）

(Dining Philosophers problem)

73 デッドロックを生じさせない方法１）４人しかテーブルにつけないようにする．２）左右の箸を同時に取り上げる． この動作をクリティカルセクションにする．３）非対称な解を用いる． 偶数番目：右の箸から． 奇数番目：左の箸から 飢餓状態の回避はどうするか？

(74)

CPUスケジューリング

１０－１２ 並行プロセス

順序グラフ

今まで，

 プログラムの逐次的実行

これから，

 プログラム内の並行実行

上記の文を平行に実行したい！

①と②は，並列に実行できる．

③は，①の後

④は，③の後

順序グラフの定義

S1

S2

S3

S7

S4

S5

S6

S1

S2

S3

並行に実行できるための条件



記号の定義

R(Si)：文Siで読み出される変数の集合

W(Si)：文Siで書きこまれる変数の集合



例



R(③)＝｛a,b｝，W(③)＝｛ｃ｝



２つの連続する文S1,S2が並行実行可能であるための必

要十分条件

以下の３つが成立すること（Bernsteinの条件（1966））

1)R（S1）∩W(S2)＝｛｝

2)W（S1） ∩ R(S2)＝｛｝

3)W（S1） ∩ W(S2)＝｛｝

仕様



プログラミング言語で用いる並列命令

１）ForkとJoin構造体

２）parbeginとparendの構造体

ForkとJoin構造体（１／３）



Conway(1963), Dennis and Van Horn(1966)が提案

S1

Fork

S2

S3

S3

join

S1

S2

ForkとJoin構造体（２／３）

Fork

S2

S3

join

count:=2;

fork L1;

・

・

・

S3;

go to L2;

L1: S2;

L2: join count;

Join命令；

Count:= count -1;

If count != 0;

then quit;

ForkとJoin構造体（３／３）

ー図９．１のプログラムー

S1

S2

S3

S7

S4

S5

１０－１２並行プロセス