- 共有メモリ上のコミュニケーションを通じた、
- 複数プロセッサのプログラミング
非同期処理の難しい所
- 何の前触れも無く中断されたり遅くなったりして予測できない
- 本書では原則と実践の両面から解説をする
- 計算可能性についての議論が中心
- 何をするべきでないかが分かる
プログラムの正当性(correctness)が重要
- 安全性 … 悪いことが起こらない事
- liveness(生きている事?) … 正しい事が起こる事
- 逐次プログラミングでは比較的考慮しなくてよい
- パフォーマンスの話題が中心
- 並列プログラミングでは内部の動作の考慮が必要
- キャッシュ階層(CPUキャッシュ、メモリ、ディスク)など
- 逐次プログラミングをする際にはうまく抽象化されている
- 並列処理に役立つツールとその問題点について解説
- java がメイン、他の言語での対応はおまけに記載
- 各章にリファレンスを記載
並列処理で起きる問題や対策の一例をエピソードで紹介
- i*(10^9)で分けて、10個のプロセッサで分散処理する
- 各スレッドの計算時間に偏りがあってうまくいかない
- 共有されたカウンターを使って計算するとうまくいく
- 単純な実装(図1.3)。うまくいかない
- 一時的にデータをスレッド毎の領域にコピーして計算しているから
- 対策1: read-modify-write命令(5章)
- 読み込み→変更→書き込みの流れをアトミックに行う
- 大抵の今時のハードウェアには用意されている
- 対策2: 相互排他
- 特定のコードを1スレッドだけが実行できるようにする
- 相互排他(Mutual Exclusion, Mutex)問題の紹介
- 二つの基本的な戦略(割り込みとロック)の紹介
- 並列の問題に関わる性質の紹介
- アリスが猫、ボブが犬を飼っている
- 犬と猫を両方庭に放してはいけない
- 庭は広いので庭の様子をちゃんと見ることはできない
- お互いの家の窓に紐で繋げた缶をいくつか置く(図1.4)
- ペットを外に出す時に、紐を引く
- 缶が倒れているのを気づいたら、全て戻す
- 問題: 缶を戻す前に全部落ちる事がある
- お互いの家に旗を用意
- アリスが猫を放すとき
- 旗を上げる
- ボブの旗が下りた時に、猫を放す
- 猫が帰ってきた時、旗を下ろす
- ボブが犬を放すとき
- 旗を上げる
- アリスの旗が上がっている時
- 旗を下ろす
- アリスの旗が下りるまで待つ
- 旗を上げる
- アリスの旗が下りていれば、犬を放す
- 犬が帰ってきた時に、旗を下ろす
- 旗を上げた後に
- 相手の旗を見る
- (ペットを放す前に相手の旗が下りているのを見た瞬間がある)
(読んで、わかりましたか?)
- 仮に、両方のペットが庭に出たとする
- アリスはボブの旗が下りているのを見たはず (a2)
- ボブが旗が上げきる前に旗を見た (a2 → b1)
- ボブがアリスの旗を見たのはアリスが旗を上げた後 (a2 → b1 →b2)
- 旗が上がっているのでボブは犬を開放しない
- 矛盾
- 背理法での証明はこれからも出てくる
- フラグをあげるような処理は一瞬であると仮定してはいけない
- 解決策1は、どのタイミングで紐を引っ張るのだろう??
- 解決策2は、なんでボブはこんなに複雑? → 二人が同時に旗をあげてしまった場合の対策
- 解決策2は、なんでボブが一度旗をあげてから確認している? → 旗の操作と相手の旗の確認は同時にはできないから
- 相互排他 … 複数が同時に実行されない(庭にペットがいない)事
- (性質としての相互排他と問題としての相互排他は別のもの??)
- デッドロックフリー … 複数が実行しようとしている時に少なくともどれか一つが実行できる事
- スタベーションフリー … 一部の特定の処理が長期間実行できなくなる事態にならない事
- 待ち
- 耐障害性の一例とも言える。待ちがあると処理に問題が起きた時に影響が伝搬してしまう。
- 相互相互排他は満たす
- デッドロックも起こらない
- スタベーションは起こる
- アリスの猫が遊び続けているとボブの犬は遊べない
- 待ちも発生する
- アリスがフラグをあげた直後に急病で入院してしまったら…
- 一時的(transient)なコミュニケーション … 同時に双方がいないと成り立たない
- 永続的なコミュニケーション … 送信と受信が異なる時間でも構わない
- transient なコミュニケーションは相互排他には利用できない
- 相手が返事が出来るかどうかが分からないため
- 割り込み
- スレッドAがフラグを立てる
- スレッドBは定期的にフラグを見る
- Bはフラグをリセットする
- 相互排他問題の解決にはならない
- Java の wait()/notifyAll() の基礎
- 二つのスレッドの相互排他は1ビットである程度解決できる事がわかる
- アリスがペットを複数飼っている
- ボブはアリスのペットに餌を提供する
- 餌は庭に置く
- ボブとペットは同時に庭にいてはいけない
- 不必要に庭に出ない
- 餌が無い時にアリスはペットを放さない
- 餌があるうちはボブは餌を置かない
アリスのところに缶を置く
- アリス
- 缶が倒れるまで待つ
- ペットを放す
- ペットが戻り、餌が空になったら缶を戻す
- ボブ
- 缶が戻るまで待つ
- 庭に餌を置く
- 缶を倒す
- 相互排他 … ボブとペットは庭にいない
- スタベーションフリー
- ボブは常に餌を提供したい、ペットは常に餌を食べたい、という状況の場合
- ペットは常に餌を食べられる
- 生産者-消費者 … 餌がないならペットは庭に入らない、餌があるならボブは庭に入らない
缶と紐のプロトコルを相互排他(前回の庭の遊びの問題解決)にはできない
- デッドロックが起こるから
- 相互排他 … 保証される
- 初期状態 … 缶が倒れていれば、ペットだけが庭に入れるから相互排他は保たれる
- アリスが缶を戻す時 … ペットが戻っているはずなので、相互排他は保たれる
- ボブが缶を倒す時 … ボブが庭から戻っているはずなので、相互はいたは保たれる
- スタベーションフリー …
- ペットが空腹だとすると、餌が無い、ボブが餌を提供するのに失敗している
- 缶が落ちているはず。
- 餌がなく、缶が落ちていれば、アリスは缶をあげるはず
- 正常系に戻る
- 生産者-消費者
- 缶を戻っていなければボブは庭に入らない。缶が戻っているなら、餌は無い
- 缶が落ちていなければペットは庭に入らない。缶が落ちているなら、餌がある
- 待ちが生じる
- 掲示板によるコミュニケーション
- ボブが掲示板にメッセージを書く
- アリスが読む
- 読み込み途中で掲示板の内容が変わった場合、正しくメッセージが受け取られない
- 相互排他プロトコル、缶と紐のプロトコル
- 待ちが生じる
- 待ちを必要としない解法がある