class: title, smokescreen, shelf, no-footer # 競合状態と排他制御 <div class=footnote> <small> </small> </div> --- class: title, smokescreen, shelf, no-footer # 競合状態 <div class=footnote> <small> </small> </div> --- class: img-right,compact # 競合状態とは? <div class=footnote> <small> (脚注1) N+1番目に入れる客は?->並んだ順とは限りません(順を保証するにはコードが複雑化) <br> (脚注2) セマフォの詳細は省略;基本情報より難しい試験には出ます e.g. P操作,V操作 </small> </div>   - 複数のプロセスがリソース(資源)を取り合っている状態のこと - 右図は「スーパーの入場人数制限」で、これが競合状態の好例 - **最大N人**しか入れないように、**N個のカゴ**が入り口にあり、 カゴがないなら入ってはいけません - N+1人め以降の客は入り口で待ちます - 客が一人でれば一人はいれるようになるので、 待っている客に「入れるようになった」と知らせます - これをモデル化したものが**セマフォ(semaphore)**(ダイクストラ,1965) --- class: compact # 一つのリソースを排他制御したい(例: 在庫処理) <div class=footnote> <small> </small> </div> - 実際にプログラムを書こうとすると 「一つのリソースを取り合う」状態つまり**ロック(lock)**が必要な場面に出会います (**排他制御**と呼ばれます) - ショッピングサイトの在庫管理が良い例です。 たくさんのユーザが同時にカートを操作し、注文を同時に出すことも多々あるでしょう。 カートにいれた注文の「確定」とは、 以下の擬似コード(関数「確定」)のように、 在庫(変数)の値を減らす処理です。 簡単にみえますが、 この関数の呼び出しが**同時に複数おこわれた**時も正しく動くか? ``` 関数 確定 (商品) { 商品の在庫を -1 する // 在庫 -1 に成功できれば、このお客さんの商品を確保できている // このお客さんの購入品としてデータベースをアップデートなりする... } ``` --- class: compact # 間違ったコード: 在庫を -1 するとは？ <div class=footnote> <small> (脚注) 「操作してますフラグ」はユーザにまたがるグローバル変数のイメージで読んでください </small> </div> <small> - 素直に考えると次のような擬似コードを書きそうですが、これは間違いです ``` if (操作してますフラグ == 0) { // 誰も操作してないなら 操作してますフラグ = 1 // 自分が操作します！ 商品の在庫数を取得 商品の在庫を -1 する 操作してますフラグ = 0 // 操作終わりました！ } ``` - なぜならプロセスの回に説明したようにプログラムの途中で中断/再開しうるから  </small> --- class: compact # 間違ったコード: こう動く可能性があります - プロセスAとBが同時に注文しているとすると、 以下のように、 最終的に在庫数が-2(して在庫数98)にならないといけないのに-1(在庫数99)にしかならないことがありえます (フラグのチェックと更新タイミングが絶妙に入り乱れた結果->まちがい) ``` A if (操作してますフラグ == 0) { // プロセスAは操作してOKと思っている B if (操作してますフラグ == 0) { // プロセスBも操作してOKと思っている B 操作してますフラグ = 1 // 自分Bが操作します！ B Bが在庫数を取得 // たとえば在庫数 = 100 A 操作してますフラグ = 1 // 自分Aが操作します！ A Aが在庫数を取得 // Aにも在庫数 = 100 と見えてしまう A 商品の在庫を -1 する // Aが在庫数を 99 に設定 B 商品の在庫を -1 する // Bも在庫数を 99 に設定 A 操作してますフラグ = 0 // 操作終わりました！ B 操作してますフラグ = 0 // 操作終わりました！ ``` --- class: compact # 正しい動作: これを防ぐには? - (a)「条件:だれも操作してない?」の確認と (b)「自分が操作します(フラグを1に設定)」 (擬似コードで * がついている2行)を中断されることなく実行できる保証があればOK - CPUは「同時に二つの動作(条件文と何らかの値の操作)をする」機械語を提供します。 これを使った**排他制御**の機能をカーネルが提供するので、これを利用 ``` A* if (操作してますフラグ == 0) { // プロセスAは操作してOKと思っている A* 操作してますフラグ = 1 // 自分Aが操作します！ B if (操作してますフラグ == 0) { // Aが操作中Bは操作できない、のちほど再挑戦 A Aが在庫数を取得 // 在庫数 = 100 を取得 A 商品の在庫を -1 する // 在庫数を 99 に設定 A 操作してますフラグ = 0 // Aは操作終わりました！ B* if (操作してますフラグ == 0) { // プロセスBが再挑戦、操作できるようになった B* 操作してますフラグ = 1 // 自分Bが操作します！ B Bが在庫数を取得 // 在庫数 = 99 B 商品の在庫を -1 する // 在庫数を 98 に設定 B 操作してますフラグ = 0 // Bは操作終わりました！ ``` --- class: title, smokescreen, shelf, no-footer # ロック <div class=footnote> <small> (脚注) おおざっぱに言えば、取り合う資源N=1のときがロックに相当します </small> </div> --- class: compact # ロック - 大昔はgiant lock (ジャイアントロック)、現代ではmutex(ミューテックス)を使います - ジャイアントロックの典型は「割り込みを禁止」する実装(誰からも中断されない) - 前回、多重割り込み(割り込み優先度)の解説をしました。これの応用です。 割り込み優先度を変更し、どんな割りこみもできないようにするのがgiant lockの原理です - **シンプルな実装で分かりやすいことはメリット**ですが、 各種**割り込みができない=待ち時間などを有効に使えない**ため、OS全体の性能に影響をおよぼします。 とくにハードウエアの性能があがるとCPUが遊んでいる時間が増えてしまいます - mutexを使えば粒度をあげられます - ロックしたい対象ごとのロック変数に対して操作します -> 粒度があがります - できるだけ細かい処理単位で書くことが大事で、 「ある処理を使うフラグをoff/onする」だけのコードを書くことが原則です (くわしくは後述の条件変数のところで) --- class: compact # ロックの擬似コード(例:HDDへの読み書きを占有) <div class=footnote> <small> (脚注) 非効率? = HDDの読み書きは待ち時間も長いので、その間は他の仕事もできるのに... </small> </div> - ジャイアントロックでは**割り込まれない**のでHDDの読み書きだけを実行(非効率) - mutexの場合、HDDを「使ってます」変数以外はロックしません。割り込みも可。 HDDの読み書きと(擬似)並行で他のデバイスのロックも可能だし他のプロセスも実行可 ``` 関数 HDDへの読み書き (HDD) { // もっとも大味なジャイアントロック版のイメージ すべての割り込みをうけつけない HDDを読み書き // 中断されずHDDの読み書きが終わるまで実行し続ける 割り込みの受け付けを再開 } 関数 HDDへの読み書き (HDD) { // mutex(を使うけれど単純化された大味)版のイメージ mutexの処理(「HDDを使ってます変数」だけをロック,他の仕事も平行処理が可能) HDDを読み書き mutexのロックを開放 } ``` --- class: compact # もう少しモダンな書き方 - OS全体の利用効率を上げるには、 前頁のように「他の処理をうけつけない」部分を減らさないとイケません。 そうしないと、 中断(プリエンプション)してコンテキスト切り替えしても意味が無い (たとえば、切り替えてもデバイスの処理が終わるまで待つ=休眠するしかない)ことになります - そのため競合状態をさばく粒度を上げる必要があります - いろいろ細かいことを考えていけば、どんどん粒度があがりますが、 どんどん緻密なコードの書き方が要求されるようになり、 ミスをさそいがちです - 解決策にはコンパイラがサポートする案もあるのですが、一般にはOSの提供する機能を使います。 この機能は、細かい手順のいくつかをまとめて書きやすくしたもので、 開発者がミスをしないようにしてくれます - 次頁は代表例の**条件変数(condition variable)**を使う例です。 必ずmutexと条件変数をコンビで使います --- class: compact # もう少しモダンな条件変数を使った書き方 <div class=footnote> <small> (脚注1) 詳細は分からなくてもOK (脚注2) cv_wait()はmutexのロックをはずしてから休眠し、復帰する際にmutexを再度ロックします。 休眠中おなじmutexを使う他の処理は実行可 </small> </div> - 実際のデバイスドライバ(後述)では次のようなコードを書いて競合状態を避けています - リソースはHDDやキーボードなど、条件変数cvは待ち合わせるチャンネル ``` 1 mutexでロックをかける 2 while (リソースを使っていますフラグ == 1) { // (mutexロック下で)使用中か?を確認 3 cv_wait(条件変数cv, mutex変数) // 条件変数cvで待つ(待つ間は休眠) 4 } // 注: whileを抜ける時はリソースが使えるようになった時, そしてmutexを再ロック済 5 リソースを使っていますフラグ = 1 // (mutexロック下で)フラグ=1 6 mutexのロックを外す 7 リソースを使う // デバイスドライバの処理本体を書くところ 8 mutexでロックをかける 9 リソースを使っていますフラグ = 0 // (mutexロック下で)フラグ=0 10 条件変数cvで待っているプロセスを起こす // 次に処理できるプロセスはスケジューラしだい 11 mutexのロックを外す ```