DBMS-デッドロック
マルチプロセスシステムでは、デッドロックは共有リソース環境で発生する望ましくない状況であり、プロセスは別のプロセスによって保持されているリソースを無期限に待機します。
たとえば、トランザクションのセット{T 0、T 1、T 2、...、Tn }を想定します。T 0は、そのタスクを完了するためにリソースXを必要とします。リソースXはTに保持されている1、及びT 1がTに保持されているリソースY、待っている2。T 2は、T0によって保持されているリソースZを待機しています。したがって、すべてのプロセスは互いにリソースを解放するのを待ちます。この状況では、どのプロセスもタスクを完了できません。この状況はデッドロックとして知られています。
デッドロックはシステムにとって健全ではありません。システムがデッドロックに陥った場合、デッドロックに関係するトランザクションはロールバックされるか、再起動されます。
デッドロック防止
システムでのデッドロック状態を防ぐために、DBMSは、トランザクションが実行されようとしているすべての操作を積極的に検査します。DBMSは操作を検査し、デッドロック状態を引き起こす可能性があるかどうかを分析します。デッドロック状態が発生する可能性があることが判明した場合、そのトランザクションの実行は許可されません。
デッドロック状況を事前に決定するために、トランザクションのタイムスタンプ順序付けメカニズムを使用するデッドロック防止スキームがあります。
ウェイトダイスキーム
このスキームでは、トランザクションが、別のトランザクションによって競合するロックですでに保持されているリソース（データ項目）のロックを要求した場合、2つの可能性のいずれかが発生する可能性があります。
もしTS（T I）<TS（T J） - Tである私の競合ロック、Tのより古い要求している、Jその後、Tは-私は、データ項目が使用可能になるまで待つように許可されています。
TS（T場合は、私が）> TS（トンのJ Tである- ）私はTよりも年下であるJ -そしてTは私が死にます。T iは後でランダムな遅延で再起動されますが、タイムスタンプは同じです。
このスキームでは、古いトランザクションは待機できますが、若いトランザクションは強制終了されます。
創傷待機スキーム
このスキームでは、トランザクションが、別のトランザクションによって競合するロックですでに保持されているリソース（データ項目）のロックを要求した場合、2つの可能性のいずれかが発生する可能性があります。
もしTS（T I）<TS（T J）、その後、T iがTの強制jのロールバックする- Tのある私の傷のT jは。T jは後でランダムな遅延で再起動されますが、タイムスタンプは同じです。
TS（T i）> TS（T j）の場合、Tiはリソースが使用可能になるまで待機するように強制されます。
このスキームにより、若いトランザクションを待機できます。ただし、古いトランザクションが若いトランザクションによって保持されているアイテムを要求すると、古いトランザクションは若いトランザクションにアイテムを中止して解放するように強制します。
どちらの場合も、後の段階でシステムに入るトランザクションは中止されます。
デッドロックの回避
トランザクションを中止することは、必ずしも実際的なアプローチではありません。代わりに、デッドロック回避メカニズムを使用して、デッドロック状況を事前に検出できます。「待機グラフ」のような方法が利用可能ですが、それらは、リソースのインスタンスが少なく、トランザクションが軽量であるシステムにのみ適しています。かさばるシステムでは、デッドロック防止技術がうまく機能する場合があります。
待ち行列グラフ
これは、デッドロック状態が発生する可能性があるかどうかを追跡するために使用できる簡単な方法です。システムに入るトランザクションごとに、ノードが作成されます。トランザクションTは場合iは、アイテムのロックを要求する、いくつかの他のトランザクションのTに保持されているX、言うjは、有向エッジがTから作成されたI TのにJ。T jがアイテムXを解放すると、それらの間のエッジがドロップされ、Tiがデータアイテムをロックします。
システムは、他のデータ項目が保持している一部のデータ項目を待機しているすべてのトランザクションについて、この待機グラフを維持します。システムは、グラフにサイクルがあるかどうかをチェックし続けます。
ここでは、次の2つのアプローチのいずれかを使用できます-
まず、別のトランザクションによってすでにロックされているアイテムのリクエストを許可しないでください。これは常に実行可能であるとは限らず、トランザクションがデータ項目を無期限に待機し、それを取得できないという飢餓を引き起こす可能性があります。
2番目のオプションは、トランザクションの1つをロールバックすることです。古いトランザクションよりも重要な場合があるため、若いトランザクションをロールバックすることが常に実行可能であるとは限りません。いくつかの相対的なアルゴリズムの助けを借りて、トランザクションが選択され、それは中止されます。このトランザクションは、victim プロセスはとして知られています victim selection。