排他制御：Petersonのアルゴリズムを分かりやすく

情報工学科のプログラミングの講義で、排他制御についての話題があり、その中で登場したPetersonのアルゴリズムが難解で腑に落ちなかったので、勉強のためにいろいろ考えてみました。
この記事は、分かりやすい喩えで解説する試みです。

　排他制御のクリティカルセクションを交差点に喩え
一方のみが通行許可される「看板」と、１組の「信号機」を組み合わせて制御している。
これらは片方のみだと破綻してしまうが、２つだと上手くいくように組み合わさっている。

　片方のみだとどのような問題があるのか、確かめてみよう。

看板を使った排他制御

　「看板」は表示されている方の道路のみが通行でき、その道路からきた車がクリティカルセクションを去ったらもう一方の道路を表示する。
ただし、これだと連続して同じ道路に車が来た場合、もう一方の道路に車が来るまで２台目の車は延々と待つはめになる。

図を入れたい：上手くいく例と、上手くいかない例

つまり、２つのスレッドに絶え間なく処理のリクエストが届くような場合は処理がうまくいくが、片方のスレッドに処理リクエスト数が偏っている場合は多い方の待ち時間が長くなるか、最悪破綻する。

信号機を使った排他制御

一方で、「信号機」の処理は

1. 自分の道路に車が来たら、もう一方の道路の信号を赤にする。
2. 自分の信号が青になるまで待つ。
3. 交差点を通過する。
4. もう一方の道路の信号を青に戻す。

となっている。

これにより、通行不可となる時間が少なくなり、看板方式のようにもう一方の道路の通行状況に依存しなくなるが、これも問題がある。

両方の道路に同時に車が到着するとデッドロックが発生する。
同時に車が到着した場合、CPUが実行するのは以下の流れとなる：

命令1. (道路A) 信号機Bを赤にする
命令2. (道路B) 信号機Aを赤にする
命令3. (道路A) 信号機Aが青になるまで待つ
命令4. (道路B) 信号機Bが青になるまで待つ

道路A, Bともに相手側が自分の信号を青にしてくれるのを待ち続けてしまうので、これも破綻する。

組み合わせると・・・

　そこで、この看板と信号機を両方使うことでこの問題が解消される。
信号機方式で起きている問題は、上記の命令3と命令4のような事態において、優先権が決まっていないことだと言える。
その優先権を「看板」で与えるのがPeterson方式である。

車が同時到着するというケースが起きたとき、看板によって誰が優先して通行可能かを示すようにしているのである。
単にAを優先するとしてもよいが、公平性をもたせるために交互に優先権が渡るようにしている。