デッドロック
Lock-freeとWait-freeアルゴリズムでもデッドロックを回避できる。
以上のようなデッドロックを回避するには以下のような方法がある。
CSAとCSBに入る順番を2つの処理で同じにする
“変数Aと変数Bにアクセスする”というミューテックスを用いる
クリティカルセクションに入れない場合は、既に入っているクリティカルセクションから出て処理を終了するようにする
他にも様々な回避方法が存在する。
優先度上限プロトコル機能が拡張されたミューテックスを利用することでも、デッドロックを回避することが可能である。優先度上限プロトコルは組み込みシステムで主に使われ、使うことで効果があるプログラムも限定的であり、汎用的に使える方法ではない。
クリティカルセクションで排他制御を用いた場合の例をあげる。 変数Aと変数Bの2つのデータと、BにAの値を加算し、Aを0にする処理AとAにBの値を加算し、Bを0にする処理Bの2つの処理があったとする。マルチスレッドで処理をするため変数Aと変数BにアクセスするためのクリティカルセクションA(以下CSA)とクリティカルセクションB(以下CSB)の2つのクリティカルセクションを用意する。
処理Aは以下の手順であるとする。
CSAに入る
CSBに入る
BにAの値を加算
Aに0を代入
CSBから出る
CSAから出る
また同様に処理Bは以下の手順であるとする。
CSBに入る
CSAに入る
AにBの値を加算
Bに0を代入
CSAから出る
CSBから出る
この場合は以下のようにプログラムが動作するとデッドロックが発生する。 処理Aを実行するスレッドAが生成され、処理が開始する。処理Aの1でCSAに入った直後にコンテキストスイッチが発生し、処理Bを実行するスレッドBが生成され、処理Bの1でCSBに入る。そして再びコンテキストスイッチが発生しスレッドAがアクティブになり、2でCSBに入ろうと試みる。しかし、スレッドBが既にCSBに入っているためスレッドAは待機状態に入り、スレッドBがアクティブになる。スレッドBは同じく2でCSAに入ろうと試みるがスレッドAが既にCSAに入っているためスレッドBは待機状態に入ってしまう。
こうして両方のスレッドが待機状態になり、プログラムが停止してしまう。この状態がデッドロックである。
以上の処理を時間に沿ってまとめたものが以下の表である。