日々の破片

_ 並行プログラミングの原理から実践まで

アスキーの鈴木さんからもらって読み始めたが、いきなり1章の練習問題でつまづく。教科書（序文によれば大学の最終年度の教科書兼実務者の参考文献を想定している）っぽく、ぶっきらぼうに問題が出ていて解答はない。

おれの本来の読者（実務者）としての正しい読み方は1章をすっとばして（アムダールの法則は別らしい）、いきなり実践編の並行スタックだとか並行キューとか、プライオリティキューとかを読めば良いのだろうが、せっかくだからまじめに（CSコースの読み方）読んでみようかなぁと。

（もっとも2章の相互排他、3章の並行オブジェクトは基本的に読むべきとされている。3章ではJavaメモリモデルとしてダブルチェックロッキングがなぜ無効なのかについての解説があったりするが、わかりやすい。ただ、volatileフィールドを揮発性フィールド、シリアライザブルを線形化可能と日本語にしているので（教科書としては正しいのかも知れない）ちょっととまどった。特に線形化のほう。このあたりは実務的には理解しているはずなので流し読みでも良いかなぁとか思った。が、練習問題のレベルは別）

プログラミング言語としてはJavaを利用して、扱う範囲としては原理編の最後の章（第6章で、ここまでが全体の1/3）が「コンセンサスの普遍性」として「ロックフリー普遍構造」「無待機の普遍構造」となっている。ここでの普遍性とは、オブジェクトの数が十分であるとすれば、任意の並行オブジェクトの線形化可能な無待機実装を構築可能なことを意味している。

The Art of Multiprocessor Programming 並行プログラミングの原理から実践まで(Maurice Herlihy)

価格の高さは刷り数の少なさを意味するから、2年後くらいには入手困難となりそうな書籍なので、ちょっとでも必要性を感じたら購入しておくべきと思う。

で、つまづいている問題は以下のようなやつ。

P人の囚人の1人と仮定する。

看守が次のように言う。

・今日は戦略を巡らし意見交換可能である。明日からは独房に入り連絡は取れない。

・オンとオフのスイッチを持つ部屋がある。スイッチはどこにも接続されていない。

・ときどき1人の囚人を無作為に選んで、スイッチ部屋へ入れる。囚人はオンとオフの間で切り替えることも、そのままにすることもできる。

・囚人を部屋に入れる頻度は任意である。Nが任意の正数であれば、最終的に各囚人は最低でもN回スイッチ部屋に収容される。

・どの囚人も常に「全員が少なくとも1回はスイッチ部屋に収容された」と主張できる。正しければ、その囚人を釈放する。正しくなければ、全員をワニの餌にする。

問1）初期状態がオフの場合の必勝法を考えよ

問2）初期状態が不明な場合の必勝法を考えよ

ヒント）すべての囚人が同じことをする必要はない

今写して気づいたが、「その囚人を」であって、全員ではないのか。