🎸 ライブロック 🎸について
この記事は rogy Advent Calendar 2018 - Adventar の 9日目の記事です。
みなさんはデッドロックについてはご存知かと思われます。
// thread A void doA() { lock1.lock(); // (A1) lock2.lock(); // (A2) // クリティカルセクション lock2.unlock(); lock1.unlock(); } // thread B void doB() { lock2.lock(); // (B1) lock1.lock(); // (B2) // クリティカルセクション lock1.unlock(); lock2.unlock(); }
2つのスレッドの処理が A1 → B1 のように進んだ場合、ロック解放待ちのブロックが発生し処理が停止してしまうという現象です。
ところで、デッドロックの親戚の概念としてライブロック(livelock)というものがあります。
A thread often acts in response to the action of another thread. If the other thread's action is also a response to the action of another thread, then livelock may result. As with deadlock, livelocked threads are unable to make further progress. However, the threads are not blocked — they are simply too busy responding to each other to resume work. Starvation and Livelock (The Java™ Tutorials > Essential Classes > Concurrency)
(訳) スレッドは時に別のスレッドの挙動に反応することがあります。一方で、そのスレッドがまた元のスレッドに影響を及ぼしあうとき、ライブロックが起こるかもしれません。デッドロックと同様に、ライブロックしたスレッドは処理を進めることができません。しかし、スレッドは実際にはブロックされていません ――― お互いの処理を再開するために永遠に反応しあうビジー状態に陥っています。
これを説明する比喩として面白い例がよく参照されます。
あなたが狭い道を歩いてるとき、向こうから人がやってきました。あなたはその人を見て右によけようとしますが、相手も同じ側によけられました。今度は左側によけようとしますが、あいてもまた左側によけようとします。結果としてお互いがまるで反復横跳びをしあうように運動し続け、前に進むことはありません。
こういった行動は日常生活でよくあると思いますので、その際はライブロックのことを思い出してください。*1
ライブロックするコードの例についてみてみましょう。
// thread A void doA() { lock1.lock(); // (A1) while (lock2.locked()) // (A2) { lock1.unlock(); // (A3) sleep(); // (A4) lock1.lock(); // (A5) } lock2.lock(); // (A6) // クリティカルセクション lock2.unlock(); lock1.unlock(); } // thread B void doB() { lock2.lock(); // (B1) while (lock1.locked()) // (B2) { lock2.unlock(); // (B3) sleep(); // (B4) lock2.lock(); // (B5) } lock1.lock(); // (B6) // クリティカルセクション lock1.unlock(); lock2.unlock(); }
スレッドAで、A2 ~ A5 でlock2がロックされている場合、lock1 のロックを解除して「もう一方のスレッドに譲る（一旦ロックを解除し(A3)、少し待ってから(A4) 再ロックを行う (A5) ）」行為を行っています。しかしながらスレッドBも同じことをしているため、最悪の場合お互い譲り合いをしあう状態が続き、whileループを抜け出せなくなってしまいます。
では、実際にこのようなバグが発生するのでしょうか？オープンソースの並行バグを調べた研究によると、ライブロックの割合は少ないものの Hadoop といった有名なフレームワークにも存在したようです。*2
ライブロックを起こさない解決方法として以下のものがあげられます。
- 譲るときの待ち時間をランダムにする
- ロックの順番を適切に行う
- デッドロックの解決策としても挙げられるやつです。lock1 の後に lock2 をする、というルールを定めればそのようなバグが起きることはありません。ルールに完璧に従ってプログラムを書ければ、ですが。
- ロックを使わない。
他にも、ライブロック検出のためのアルゴリズムや手法がいくつかの論文で提唱されています。
*1:これを表現するスラングとしてSchlumperdinkというものがあるらしいです https://www.urbandictionary.com/define.php?term=schlumperdink
*2:Concurrency bugs in open source software: a case study https://jisajournal.springeropen.com/articles/10.1186/s13174-017-0055-2
