- 複数のプロセスが、お互いのリソース開放を永久に待ち続ける状態が発生しない
- 広義のデッドロック(Livelock)も禁止
ネタ
- Any deadlock-free mutex algorithm requires allocating and then reading or writing at least n distinct locations in the worst case.
定理
Deadlock-freedom特性を持つMutexアルゴリズムは、同時スレッドの最大数をnとしたときに、少なくともn個のメモリ領域を読み書きする必要がある
証明
- 3スレッドあるとして、2つのメモリ領域のみを使用するDeadlock freeなLockアルゴリズムがあると仮定して、矛盾を示す (背理法)
- Covering Stateの概念を導入
- 各メモリ位置に対して、少なくとも1つのスレッドがその位置に書き込もうとしている状態
- Lockオブジェクトの状態は、クリティカルセクションにいるスレッドが0に見える
- Covering stateからはじまる実行を考える
- まずスレッドCを実行させる。Cはクリティカルセクションに入る。
- スレッドA,Bを実行させる。Covering stateを更新させる。
- AもBも、Cがクリティカルセクションにいるかどうか判断できない (何の印もないので)
- で、AがCSに突入して、AとCが同時にCSにいることになってオシマイ
(TAoMPより)