DBMSのデッドロック

デッドロックは、2つ以上のプロセスが、他のプロセスによって保持されている実行を完了するために何らかのリソースを必要とする場合に発生します。

上の図では、プロセス1にはリソース1があり、リソース2が必要です。同様にプロセス2にはリソース2があり、リソース1が必要です。これらの各プロセスは、完了するために他のリソースを必要としますが、どちらもリソースを放棄する意思はありません。したがって、プロセス1とプロセス2はデッドロック状態にあります。

コフマンの状態

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

相互排除

一度に1つのプロセスでのみ保持できるリソースが必要です。次の図では、リソースR1のインスタンスが1つあり、プロセスP1によってのみ保持されています。

しばらくお待ちください

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

プリエンプションなし

リソースを強制的にプロセスからプリエンプションすることはできません。プロセスは、リソースを自発的に解放することしかできません。次の図では、プロセスP1はリソースR3をプロセスP2からプリエンプトできません。実行が完了した後、P2が自発的に放棄した場合にのみリリースされます。

循環待機

プロセスは、最後のプロセスが最初のプロセスによって保持されているリソースを待機するまで、3番目のプロセスによって保持されているリソースを待機している2番目のプロセスによって保持されているリソースを待機しています。これにより、円形のチェーンが形成されます。次に例を示します。プロセスP1にはリソースR1が割り当てられており、リソースR2を要求しています。同様に、プロセスP2にはリソースR2が割り当てられ、リソースR1を要求しています。これにより、循環待機ループが形成されます。

プロセスは、最後のプロセスが最初のプロセスによって保持されているリソースを待機するまで、3番目のプロセスによって保持されているリソースを待機している2番目のプロセスによって保持されているリソースを待機しています。これにより、円形のチェーンが形成されます。次に例を示します。プロセスP1にはリソースR1が割り当てられており、リソースR2を要求しています。同様に、プロセスP2にはリソースR2が割り当てられ、リソースR1を要求しています。これにより、循環待機ループが形成されます。

デッドロックの検出

リソーススケジューラは、さまざまなプロセスに割り当てられているすべてのリソースを追跡するため、デッドロックを検出できます。デッドロックが検出された後、次の方法を使用して解決できます。

• デッドロックに関係するすべてのプロセスが終了します。プロセスによって行われたすべての進行状況が破壊されるため、これは適切なアプローチではありません。
• リソースは、デッドロックが解決されるまで、一部のプロセスからプリエンプションされ、他のプロセスに渡される可能性があります。

デッドロック防止

デッドロックが発生する前に、デッドロックを防止することが不可欠です。そのため、システムは実行前に各トランザクションを厳密にチェックして、デッドロックが発生しないことを確認します。トランザクションがデッドロックにつながる可能性がある場合でも、実行は許可されません。

デッドロックが発生しないようにするためにタイムスタンプを使用するデッドロック防止スキームがいくつかあります。これらは-

• 待機-ダイスキーム

  待機-ダイスキームでは、トランザクションT1がトランザクションT2によって保持されているリソースを要求すると、次の2つの可能性のいずれかが発生する可能性があります。

  • TS（T1）

  • TS（T1）> TS（T2）-T1がT2よりも若い場合、つまりT1がT2の後にシステムに入った場合、T1は強制終了されます。後で同じタイムスタンプで再起動されます。

• 傷-待機スキーム

  創傷待機スキームでは、トランザクションT1がトランザクションT2によって保持されているリソースを要求すると、次の2つの可能性のいずれかが発生する可能性があります。

  • TS（T1）

  • TS（T1）> TS（T2）-T1がT2よりも若い場合、つまりT1がT2の後にシステムに入ってきた場合、T2が実行を完了したときに解放されるリソースを待つことができます。

デッドロックの回避

デッドロックが発生した後に対策を講じるよりも、デッドロックを回避する方が適切です。待機グラフは、デッドロックを回避するために使用できます。ただし、これは大規模なデータベースでは非常に複雑になる可能性があるため、小規模なデータベースでのみ役立ちます。

グラフを待つ

待機グラフは、リソースとトランザクションの関係を示しています。トランザクションがリソースを要求する場合、またはトランザクションがすでにリソースを保持している場合は、待機グラフのエッジとして表示されます。グラフの待機にサイクルが含まれている場合は、システムにデッドロックが発生している可能性があります。そうでない場合は、そうではありません。

デッドロックを無視する-ダチョウアルゴリズム

ダチョウアルゴリズムは、デッドロックが単に無視され、デッドロックが発生しないと想定されることを意味します。これが行われるのは、一部のシステムでは、デッドロックが非常にまれにしか発生しないため、デッドロックを単に無視するよりも処理コストがはるかに高いためです。したがって、デッドロックが発生することはなく、万が一発生した場合はシステムが再起動されると単純に想定されています。