排他制御の仕組1 まず共有変数への排他制御を考えてみる

(1)

排他制御の仕組1

まず

共有変数への排他制御を考えてみる

共有変数に

「読んで書く」更新をするとどうなるか

(2)

共有変数の更新

︓

X を読出す X+a を計算し

X へ書戻す

︓

X を読出す X+b を計算し

X へ書戻す

︓

X=X+a X=X+b

プロセスＡプロセスＢ

初期値０

共有データ

Ｘ

︓

X を読出す X+a を計算し

X へ書戻す

︓

X を読出す X+b を計算し

X へ書戻す

︓

X=X+a X=X+b

初期値０

共有データ

Ｘ

同時に⾛ると、どうなるか︖

(3)

タイミング例１タイミング例２

↓ ↓

Ａが読出す(0) Ａが読出す(0) Ａが書戻す(a) Ｂが読出す(0) Ｂが読出す(a) Ａが書戻す(a) Ｂが書戻す(a+b) Ｂが書戻す(b)

↓ ↓

X=a+b X=b

︓

X を読出す X+a を計算

X へ書戻す

︓

X を読出す X+b を計算

X へ書戻す

︓

X=X+a X=X+b

初期値０

共有データ

Ｘ

結果が違う

↓ ↓

X=a+b X=b

︓

X へ書戻す

︓

X へ書戻す

︓

X=X+a X=X+b

初期値０

共有データ

Ｘ

本来なら０に a を足して b を足すので X は a+b になる

このタイミングだと X は b になる

結果が違う

(4)

↓ ↓

X=a+b X=b

︓

X へ書戻す

︓

X へ書戻す

︓

X=X+a X=X+b

初期値０

共有データ

Ｘ

本来なら０に a を足して b を足すので X は a+b になる

このタイミングだと X は b になる

結果が違う

なぜか

順序がおかしい

↓ ↓

X=a+b X=b

(5)

↓ ↓

X=a+b X=b

Ａが書き戻していないので、

まだ 0 なのにＢが読出した

↓ ↓

X=a+b X=b

どうすればよいのか︖

Ａが書き戻していないので、

まだ 0 なのにＢが読出した

(6)

•

Ａが先に読む+書くしてから、Ｂが読む+書くか、

•

Ｂが先に読む+書くしてから、Ａが読む+書くか、

どちらかに制限する

•

どちらかに制限する（左の２つならＯＫ）

↓ ↓ ↓

Ａが読出す(0) Ｂが読出す(0) Ａが読出す(0) Ａが書戻す(a) Ｂが書戻す(b) Ｂが読出す(0) Ｂが読出す(a) Ａが読出す(b) Ａが書戻す(a) Ｂが書戻す(a+b) Ａが書戻す(b+a) Ｂが書戻す(b)

↓ ↓ ↓

X=a+b X=a+b X=b

ＯＫＮＧ

(7)

•

↓

•

Ａの(読む+書く)の間は、Ｂはアクセスさせない

•

Ｂの(読む+書く)の間は、Ａはアクセスさせない

•

↓

•

Ａの(読む+書く)の間は、Ｂはアクセスさせない

•

Ｂの(読む+書く)の間は、Ａはアクセスさせない

| |

「相互排他」

(8)

排他の仕組＝ロック

•

共有データＸを一方のプロセスがロックすると、

解除するまで、

他のプロセスはアクセス（読書き）できない

(9)

•

︓

X へ書戻す

︓

X へ書戻す

︓

X=X+a X=X+b

初期値０

共有データ

Ｘ

ロック

解除

ロック

解除

この間は他のプロセスが共有データＸを読書きできない

•

︓

X へ書戻す

︓

X へ書戻す

︓

X=X+a X=X+b

初期値０

共有データ

Ｘ

この間は他のプロセスが共有データＸを読書きできない

ロック

解除

ロック

解除

資源確保

資源の解放資源を占有

(10)

• プロセス（orスレッド）

が排他的な資源を使いたくなる

• 空いていれば占有

（ロック）できる

相互排他と占有

プロセスＡ

（スレッドＡ）

実行

相互排他が必要な資源

Ａが占有

Ａが資源を使いたいロックする

• 使い終わったら解放

プロセスＡ

（スレッドＡ）

実行

Ａが占有

Ａが資源を使いたい

実行

Ａが資源を解放する

ロックする

(11)

• 他のプロセスは資源が空くまで待たされる

（ブロックされる）

プロセスＡ

（スレッドＡ）プロセスＢ

（スレッドＢ）

実行

Ａが占有実行

Ｂも資源を使いたいＡが資源を

使いたいロックする

既にＡが使用中

プロセスＡ

実行

Ａが占有実行

使いたい

Ｂは待たされる

ブロックされているロックする

既にＡが使用中

(12)

プロセスＡ

実行

Ａが占有実行

使いたい

Ｂは待たされる

実行

プロセスＡ

実行

Ａが占有実行

使いたい

Ｂは待たされるＢが占有

実行

空いたのでロックできる

(13)

プロセスＡ

実行

Ａが占有実行

使いたい

Ｂは待たされるＢが占有

実行実行

Ｂが資源を解放する

空いたのでロックできる

ことば︓ クリティカルセクション

• 相互排他

＝ mutual exclusion 短縮してmutexと呼ぶ

• ロック = かぎ（錠）〜を掛けて他が入れない、占有

(14)

ことば︓ クリティカルセクション

• 相互排他

＝ mutual exclusion 短縮してmutexと呼ぶ

• ロック = かぎ（錠）〜を掛けて他が入れない、占有

• クリティカルセクション

（クリティカルリージョン）

||

プログラム中で、資源に排他的にアクセスする部分のこと

プロセス（or スレッド）

資源に関わらないコード部分

資源をロック資源にアクセス

（１回とは限らない）

（ロックしたまま何度もアクセスすることも多い）

資源を解放

資源に関わらないコード部分

資源使用中

この部分のコードをクリティカルセクションと呼ぶ

（脱線）ロックの実現

(15)

（脱線）ロックの実現

•

共有変数「ロック中」（使用中）を用意し、

（脱線）ロックの実現

•

もし「１」なら使用中なので待つ

(16)

（脱線）ロックの実現

•

もし「０」なら空いているので

「１」にして、使い始める使い終わったら「０」に戻す

（脱線）ロックの実現

•

もし「０」なら空いているので

「１」にして、使い始める使い終わったら「０」に戻す

•

問題点︓

「ロック中」変数を共有メモリ上に取って

上の仕組を作ると ⇒ うまくいかない

(17)

（脱線）ロックの実現

•

共有変数「ロック中」

がうまくいかない

プロセスＡ ^共有変数_ロックＬ

ロックの操作

ロックしたいＬを読んで０ならＯＫ

Ｌに１を書込む

プロセスＢ

初期値０

値１

ロックの操作

ロックできたと思い込むロックできたと思い込む

（脱線）ロックの実現

•

Ａが変数Lに 1 を書き込まないうちに、

Ｂが L を読出して

まだ空いていると思う

ロックの操作

プロセスＢ

初期値０

値１

ロックの操作

(18)

（脱線）ロックの実現

•

ＡもＢもロックできたと思い込む

ロックの操作

プロセスＢ

初期値０

値１

ロックの操作

（脱線）ロックの実現

•

ＡもＢもロックできたと思い込む

ロックの操作

プロセスＢ

初期値０

値１

ロックの操作

なぜ︖ ⇒ Ａが「読んで書く」間に(書く前に)Ｂが読出すから

(19)

（脱線）ロックの実現〜解決策

1. ハードウェアに工夫して

「読む⇒書く」の動作を不可分（その間他の操作をできない）にする

例︓Test & Set 命令など 2. １CPU上での多プロセス

の場合に限って有効だが、

プロセス切替（割込み）を起こさせない（禁止）ようにする

例︓割込み禁⽌による

ロックの操作

プロセスＢ

初期値０

値１

ロックの操作

排他制御の仕組のまとめ

•

共有データ（共有ファイルも）を

「読んで書く」などしたいとき、

(20)

•

その間で他プロセスがアクセスすると動作の不統一が起こる

•

それを防ぐには

(21)

•

他プロセスが間に入って困る不可分の動作中は

•

他プロセスが間に入って困る不可分の動作中はロックによって排他すればよい

(22)

42

排他制御の必要性と

ロックによる排他制御の方法が理解できましたか︖

排他制御の仕組1 まず 共有変数への排他制御を 考えてみる