DBMSのデッドロックとは？発生条件と対策手法をわかりやすく解説

デッドロックとは

デッドロックとは、2つ以上のプロセスが、それぞれ実行の完了に必要なリソースを相手側が保持しており、互いに待ち続けてしまう状態を指します。

上記の図では、プロセス1がリソース1を保持しており、リソース2を必要としています。同様に、プロセス2はリソース2を保持し、リソース1を必要としています。どちらのプロセスも相手の持つリソースがなければ処理を完了できないにもかかわらず、自分のリソースを手放そうとしないため、プロセス1とプロセス2はデッドロック状態に陥ります。

コフマン条件（Coffman Conditions）

デッドロックが発生するのは、次の4つのコフマン条件がすべて成立している場合のみです。これらの条件は必ずしも相互排他的ではありません。

1. 相互排除（Mutual Exclusion）

あるリソースが、一度に1つのプロセスによってしか保持できないこと。下図では、リソースR1のインスタンスは1つだけであり、プロセスP1だけがそれを保持しています。

2. 保持と待機（Hold and Wait）

プロセスが複数のリソースを保持したまま、他のプロセスが保持しているリソースをさらに要求できること。下図では、プロセスP1はリソースR1とR2を保持したまま、プロセスP2が保持するリソースR3を要求しています。

3. 強制奪取不可（No Preemption）

リソースをプロセスから強制的に取り上げることができないこと。リソースを解放できるのは、そのプロセス自身が自発的に解放する場合のみです。下図では、プロセスP1はプロセスP2からリソースR3を強制的に奪うことはできません。R3はP2の実行完了後に自発的に解放されるだけです。

4. 循環待機（Circular Wait）

あるプロセスが別のプロセスの保持するリソースを待ち、そのプロセスがさらに次のプロセスの保持するリソースを待ち…という具合に、最後のプロセスが最初のプロセスの保持するリソースを待つことで、循環的な連鎖が形成されること。例えば、プロセスP1にはリソースR1が割り当てられており、リソースR2を要求しています。同様に、プロセスP2にはリソースR2が割り当てられ、リソースR1を要求しています。これにより循環待機ループが形成されます。

デッドロック検出

リソーススケジューラは、各プロセスに割り当てられたすべてのリソースを常時追跡しているため、デッドロックを検出することができます。デッドロックが検出された後は、以下のいずれかの方法で解消できます。

• デッドロックに関与しているすべてのプロセスを終了させる。ただし、この方法では各プロセスがそこまでに達成した進捗がすべて失われてしまうため、あまり良いアプローチとは言えません。
• 一部のプロセスからリソースを強制的に奪い取り、他のプロセスへ割り当てることを、デッドロックが解消されるまで繰り返す。

デッドロック予防

デッドロックは、発生してから対処するよりも、事前に防ぐことが極めて重要です。そのため、システムはトランザクションを実行する前に厳密なチェックを行い、デッドロックにつながらないことを確認します。トランザクションがデッドロックを引き起こす可能性が少しでもある場合、その実行は一切許可されません。

タイムスタンプを利用してデッドロックの発生を防ぐ代表的なスキームとして、以下の2つが挙げられます。

Wait-Die方式（待機・死滅方式）

トランザクションT1が、トランザクションT2が保持しているリソースを要求した場合、次の2つのケースのいずれかが起こります。

• TS(T1) < TS(T2)：T1がT2より古い（システムに先に入った）場合、T1は待機することが許されます。リソースはT2の実行完了後に解放されます。
• TS(T1) > TS(T2)：T1がT2より若い（システムに後から入った）場合、T1は強制終了されます。その後、同じタイムスタンプで再実行されます。

Wound-Wait方式（傷つけ・待機方式）

トランザクションT1が、トランザクションT2が保持しているリソースを要求した場合、次の2つのケースのいずれかが起こります。

• TS(T1) < TS(T2)：T1がT2より古い場合、T1はT2をロールバック（傷つける）ことが許されます。その後、T1がリソースを取得して実行を完了させます。T2は後で同じタイムスタンプで再開されます。
• TS(T1) > TS(T2)：T1がT2より若い場合、T1は待機することが許されます。リソースはT2の実行完了後に解放されます。

デッドロック回避

デッドロックは、発生後に措置を講じるよりも、あらかじめ回避する方が望ましいと言えます。デッドロックの回避には「待機グラフ」を利用できます。ただし、大規模なデータベースではこの手法が非常に複雑になるため、有効なのは比較的小規模なデータベースにとどまります。

待機グラフ（Wait-for Graph）

待機グラフは、リソースとトランザクションの関係を表現します。トランザクションがリソースを要求している場合、または既に保持している場合は、待機グラフ上にエッジ（辺）として表示されます。待機グラフ内にサイクル（閉路）が存在すれば、システムにデッドロックが発生している可能性があります。逆にサイクルが存在しなければ、デッドロックは発生していません。

デッドロックを無視する ― ダチョウアルゴリズム（Ostrich Algorithm）

ダチョウアルゴリズムとは、デッドロックを単純に無視し、「そもそも発生しない」と想定するアプローチです。一部のシステムでは、デッドロックの発生頻度が非常に低く、対応にかかるコストの方がはるかに高くつくため、この方法が採用されます。つまり、デッドロックは発生しないものとみなし、万が一発生した場合にはシステムを再起動して対応します。