少しずつ難しい話も増えてきたかな? 第３章です。
「第３章 正当性の検証と性能測定」
◯第３章で学ぶ内容
- 誤りの無い並行アルゴリズムをきちんと設計できたかをどう確認するか
- 並行ソースコードが”十分に”並列動作しているかをどう確認するか
◯Ben-Ariの4つの並行実行一般化
- プログラムとは連続したアトミックな実行文である。
- 並行プログラムは複数のスレッド内のアトミックな実行文のインタリーブである。
- アトミックな実行文の全ての組み合わせは、検証する並行アルゴリズムの全ての性質を満たさなければならない。
- どのインタリーブでもスレッドの実行文が不公平に除外されることはない。
どんなプログラムも最小の実行単位に分けられる。並行処理は”最小の実行単位”が様々な組み合わせで実行される。実装されるアルゴリズム/プログラムはいかなる組み合わせでも正しく実行されなければならない。正しく実行するとは特定の処理が意味もなく除外されないことも含む…ということだと理解しました。
◯クリティカルセクション問題を例にBen-Ariの性質を学ぶ
共有変数を参照/更新するソースコード部分”クリティカルセクション”の実現の方法を通して、Ben-Ariの性質を学ぶ。本では5つの段階を追って解説していますが、ここでは割愛。問題にしたポイントは以下のとおりです。
- 第１段階：１スレッドがクリティカルリージョンを実行していなくても、もう一方のスレッドがクリティカルリージョンに入ることを禁止されていまう
- 第２段階：排他制御が保証されないインタリーブの組み合わせがある。
- 第３段階：デッドロックが発生してしまう
- 第４段階：一方のスレッドがクリティカルリージョンから除外されてしまう(スターベーション)
ということで、スレッドプログラミングでよく陥りそうな問題が満載です。最終的に第５段階として紹介されているのがデッカーのアルゴリズム – Wikipediaです。でもこのアルゴリズムだと2つのスレッドしか排他制御出来ないので、ランポートのパン屋のアルゴリズム – Wikipediaやピーターソンのアルゴリズム – Wikipediaが実用にはいいそうです。でもこの節で学ぶべきは使うアルゴリズムの選択じゃなくて、どういう所に着目して問題を見つけるのかというやり方なので、きちんと学んだことがなければ本を当たった方がいいと思います。
◯デッドロックを発生させる4つの条件
4つの条件はANDで発生する。どれか1つでも成立しなければデッドロックには成り得ない。
- 相互排除条件：リソースを特定のスレッドがロックしようとするからデッドロックが発生する
- 獲得後のウェイト：複数のリソースをロックしようとするとデッドロックが起きやすくなる。
- プリエンプト無し：スレッドが自発的にロックを開放する仕組みが無いからデッドロックが起きると復帰出来ない。
- 循環待ち：ロックの取得関係が循環になってしまう。
デッドロックを避けるにはどれか1つでも起きないようにすればいいらしいけど、複数リソースのロックとか危ういものは出来るだけ避けた方がいいと思う。
◯並行化によってどれぐらい性能が上がったか?
高速化率はどう伝えるべきか? 筆者いわく倍数がいいとのこと。 105%の高速化率と言っても元より5%速くなっただけかもしれないし、205%の高速かもしれない。2倍といったら受けてが迷うこと無いよね とのこと。確かにその通りかも。
逐次処理を並行処理に置き換えた際にどれぐらい高速化出来るかの見積はアムダールの法則 – Wikipediaやグスタフソンの法則 – Wikipediaで出来る。グラフを書いてみると一目瞭然だけど、並行化出来ない処理がたとえ25％でも含まれていると、どんなにコア数を増やしても3倍までしか速くならない。
オライリージャパン
売り上げランキング: 3109
Trackbacks /
Pingbacks