ランポートのパン屋

そんな面白そうな単語を職場で聞いたものだから調べて覚えるしかないなと。

http://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%9D%E3%83%BC%E3%83%88%E3%81%AE%E3%83%91%E3%83%B3%E5%B1%8B%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

ああ、要するに二重の待ち状態を持つ訳ですね。コードの意味を整理番号とスレッド番号として見た時の解釈。

1. 何らかの形でスレッド番号の配布を受ける。(重複可)
2. 整理番号発行待ちフラグを立てる。
3. 既存の整理番号のMAX+1を整理番号として受け取る。
4. 整理番号発行待ちフラグを除去する。
5. 他のスレッドの整理番号を1個づつ順次確認する。
   1. 整理番号発行待ちなら、整理番号発行を待つ。
   2. 整理番号が0ではなく、自分の持ってる整理番号(及びスレッド番号が低い)場合、整理番号が 0 (整理番号の破棄)を待つ。
6. 何らかの排他処理を行う。
7. 整理番号を破棄(0代入)する。

このコードだけそのまま見れば、N は最大待ちスレッド数より大きくなければならないのかな。
後は整理番号を適当なタイミングでリセット、、、はされるのか。
N が大きくなった時のオーバーヘッドが怖いかなといったところ。

後は、スレッド間でこれをやるうちはいいけど、Nが大きくなるにつれて、マルチプロセス間でのオーバーヘッドは相当なものになりそうな気がしないではない。

次にデッカーのアルゴリズム。

http://ja.wikipedia.org/wiki/%E3%83%87%E3%83%83%E3%82%AB%E3%83%BC%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

なんのこっちゃないシンプルな二重フラグ制御。
最適化が入ると最悪動かなくなるアルゴリズムではある。

ピーターソンのアルゴリズム。

http://ja.wikipedia.org/wiki/%E3%83%94%E3%83%BC%E3%82%BF%E3%83%BC%E3%82%BD%E3%83%B3%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

原則的には、デッカーのものと然程変わらない。
作りがシンプルでわかりやすい。とはいえ、メモリバリア等のプロセッサによるメモリアクセス最適化で無効化される恐れがある。