Zenn
Open1

Deadlock, Livelock and Starvation (デッドロック、ライブロックと飢餓）

Linux
lock
mutex
zulinx86zulinx86

Deadlock, Livelock and Starvation

  • 並行処理では、リソースが利用可能になるのを待つことに起因するスタック状態が、大きく３種類存在する。

Deadlock (デッドロック)

  • 2 つ以上のプロセスが互いにリソースの解放を待機して、スタックする状況のこと。
  • 例
    • プロセス 1 がリソース A を先にロックしている他方で、プロセス 2 がリソース B をロックしている状態を想定する。
    • この状態で、プロセス 1 がリソース B のロックも取得しようとすると、すでにプロセス 2 がロックを取得しているため、リソース B が利用可能になるのを待つ。
    • 他方で、プロセス 2 がリソース A のロックを取得しようとすると、すでに待ち状態にプロセス 1 がロックを取得しており、こちらもリソース A が利用可能になるまで待つ必要が出てくる。
    • 結果として、お互いがお互いを永遠と待ってしまう状況に陥る。
  • 発生条件
    • Unshareable (共有不可能): 少なくとも１つのリソースが、特定のプロセスによって、共有不可能なモードでロックされている。他のプロセスは、そのリソースにアクセスするために待たなければ行けない。
    • Hold and Wait (一方をロックした上で、他方のロックを待つ): １つのリソースをロックしているプロセスが、他のプロセスによってロックされている別のリソースにアクセスしようとしている。
    • No Preemption (プリエンプションされない): リソースのロックが確保され続けていて、プロセスから強制的に解放する手段がない。そのプロセス本人が対象リソースを解放する必要がある。
    • Circular Wait (循環した待ち): プロセス 1 がプロセス 2 がロックしているリソースを待ち、プロセス 2 がプロセス 3 がロックしているリソースを待ち、、、、プロセス N がプロセス 1 がロックしているリソースを待っている。
  • 回避方法
    • Shareable (共有可能にする): Read-only (読み込みのみ) にして、複数のプロセスで共有できるようにする。
    • Release Locks (ロックの解放): ロックしたいリソースが利用可能でない場合に、現在ロックしている全てのリソースを解放する or させることができる。
    • Order Locks (ロックの順序付け): リソースをアクセスする際の順序を制御する。N 個のリソースがある場合、必ずリソース 1、リソース 2、、、リソース N の順番でロックをする。

Livelock (ライブロック)

  • ２つ以上のプロセスが、他のプロセスの状態の変化に応じて、状態を継続的に変更しているが、進歩が見られない状況のこと。
  • よくあるアナロジー
    • 狭い道で、お互いがどちらか一方に寄ってすれ違おうとしているのに、お互いが同じ方向に寄ってしまって、いつまでもすれ違うことができない状況。
    • リモート会議で、同時に複数の人が話し出そうとして、お互いに譲り合い、再び両者が同時に話し出そうとしてしまう状況。
  • Deadlock との違い
    • Livelock では、どちらもブロックされて待機状態にあるわけではなく、進展はないにも関わらず、実行され続けてビジーな状態にある点である。
    • 特に何かを実行しようとして、失敗したら (場合によっては、一定間隔空けて) リトライし続けるというビジーウェイト / スピンロックを行い続ける場合に発生する。
  • 例
    • プロセス数の上限が 20 個のシステムにおいて、2 つのプロセスがそれぞれ新しく 15 個のプロセスを作ろうとしていた場合
      • プロセス数の合計が 20 個になるまでは、お互いがプロセスを作り続けるが、20 個の上限に達した場合に (例えばプロセス A 側が合計 12 プロセスになり、プロセス B が合計 8 プロセスになった場合に)、お互い作った全てのプロセスを削除し、相手に処理を譲ったとする。
      • 両者が同じ時間だけ待ったあとに、同じ処理を実行しようとすると、再びプロセス数の上限に達し、お互いがプロセスを削除するという無限ループに陥ってしまう。
      • もし仮に、片方が処理を続け、もう一方だけが処理を中断して明け渡すことができれば、プロセス数の上限 20 個には達さずに、お互いが処理を完了できる。
    • 2 つのプロセスが、異なる順番でリソースをロックしようとして、ロックに失敗した場合にリトライし続ける場合
      • プロセス 1 が「リソース A => リソース B」の順番でロックしようとし、プロセス 2 が「リソース B => リソース A」の順番でロックしようとしている。
      • ロックに失敗したら、一旦リソースを解放して、すぐにリトライしようとし続ける (ビジーウェイト / スピンロック) 。
      • 状況としては Deadlock にかなり似ているが、ロックを確保したまま、利用したいリソースが利用可能になるまでブロックされ続けるわけではなく、お互いがロックを確保しようとし続ける点が異なる。
  • 回避方法
    • Break Symmetry (対称性を壊す): 両者が異なる時間間隔でリトライしたり、異なるタイムアウトの長さを利用することで、解消できる場合がある。対称性を崩すためにランダム性 (乱数) を利用したりする。
    • Mutual Exclusion (排他制御): お互いがほぼ同時に排他的でアトミックでない処理することで発生する事象なので、排他的でアトミックなロック機構を使うことで、ロックを獲得したプロセスが先に処理を進めることができるようになる。
    • Deadlock と同じ回避方法たち
      • Shareable (共有可能にする): そもそも共有できれば何かを待ったりロックしたりする必要がない。
      • Order Locks (ロックの順序付け): 2 つ目の例でロックが順序付けされていて、ロックが排他的かつアトミックな操作であれば問題ない。

Starvation (飢餓)

  • 他のプロセスが、特定のリソースを独占し続けているため、いつまで経っても共有リソースにアクセスできるようにならない状況のこと。
  • 例
    • プリエンプションがない OS (OS がプロセスを強制的に一時中断して、他のプロセスに実行を切り替える機能がなく、プロセスが自身でリソースを解放して他のプロセスに実行を譲るタイプの OS) において、特定のプロセスがずっと CPU リソースを使い続けて、永遠と他のプロセスに処理を明け渡さない。
    • プリエンプションが存在するがプロセスの優先度が設定できる OS において、プリエンプションが発生するが、スケジューリングの結果、結局同じ優先度の高いプロセスが選ばれ続けてしまう。
  • 回避方法
    • Preemption (プリエンプション): 特定のプロセスがリソースを独占できないように、中断する仕組みを持つ。
    • Fair Scheduling / Round Robin (公平なスケジューリング / ラウンドロビン): 優先度が定義できたとしても、他のプロセスが全く実行されないといった極端に偏ったリソースの割り当てを行わない。

参考リンク