コンピューターサイエンス：アルゴリズム / OS / ネットワーク / DB
デッドロック
口座ごとに鍵を分けたら、送金が止まった
鍵を口座ごとに持たせて、別々の口座なら並行に動けるようになりました。ところが送金は 2 つの口座を触ります。減らす側と増やす側の両方に鍵をかけないと、片方だけ減った途中の状態を他人に見せてしまうからです。
A から B へ送る処理は、A の鍵を取り、B の鍵を取り、それから残高を動かします。ちょうど同じ瞬間に、別のスレッドが B から A へ送っていたとします。
プレーンテキスト
スレッド 1 スレッド 2
A の鍵を取った B の鍵を取った
B の鍵が空くのを待つ ←──────── B の鍵は 2 が持ったまま
A の鍵は 1 が持ったまま ────────→ A の鍵が空くのを待つ1 は B が空くまで動きません。2 は A が空くまで動きません。そして、どちらも待っている間は自分の鍵を手放しません。この 2 つは永久に再開しません。デッドロック です。
CPU 使用率は 0% のまま、例外もタイムアウトも出ず、ただリクエストが返らなくなります。しばらくすると、同じ口座に来た他のリクエストも同じ鍵の前に積み上がり、スレッドプールが枯れてサーバー全体が応答を止めます。
待ちの輪ができている
矢印にすると、待ちが輪になっています。
デッドロックの正体はこの輪です。裏を返せば、輪ができないようにさえすれば起きません。
取る順番を、全員でそろえる
輪ができたのは、1 が A から B の順で取り、2 が B から A の順で取ったからです。全員が同じ順序で取ると決めておけば、この形は作れなくなります。
Python
def transfer(src, dst, amount):
first, second = sorted([src, dst], key=lambda a: a.id)
with first.lock:
with second.lock:
...口座 ID の小さいほうから取る、と決めました。B から A への送金でも、内部では A の鍵から取りにいきます。先に A を取れた側が必ず B も取れるので、2 つが向かい合うことがありません。
順序を決めきれない場面では、待ちに上限を設けます。lock.acquire(timeout=2) で取れなければ、持っている鍵をいったん全部返し、少し待ってやり直す。RDB がデッドロックを検出して片方のトランザクションをロールバックし、アプリに再試行させるのも同じ考え方です。
条件は 4 つあるが、潰すのは 1 つでよい
教科書では、相互排除・持ったまま待つ・横取りできない・待ちが循環する、の 4 つがすべて揃ったときにデッドロックが成立すると説明されます。順序の固定は 4 つ目を、タイムアウトは 3 つ目を潰しています。どれか 1 つ崩せば足ります。
