DBMS-デッドロック

マルチプロセスシステムでは、デッドロックは共有リソース環境で発生する望ましくない状況であり、プロセスは別のプロセスによって保持されているリソースを無期限に待機します。

たとえば、一連のトランザクション\ {T〜[.small]＃0＃〜、T〜[.small]＃1＃〜、T〜[.small]＃2＃〜、…、T〜[ .small]＃n＃〜}。 T〜[.small]＃0＃〜は、タスクを完了するためにリソースXを必要とします。リソースXはT〜[.small]＃1＃〜によって保持され、T〜[.small]＃1＃〜はT〜[.small]＃2＃〜によって保持されるリソースYを待機しています。 T〜[.small]＃2＃〜はT〜[.small]＃0＃〜が保持するリソースZを待機しています。したがって、すべてのプロセスは互いにリソースを解放するのを待ちます。この状況では、どのプロセスもタスクを完了できません。この状況は、デッドロックとして知られています。

デッドロックはシステムにとって健全ではありません。システムがデッドロックでスタックしている場合、デッドロックに関係するトランザクションはロールバックされるか再起動されます。

デッドロック防止

システムのデッドロック状態を防ぐために、DBMSはトランザクションが実行されようとしているすべての操作を積極的に検査します。 DBMSは操作を検査し、デッドロック状態が発生する可能性があるかどうかを分析します。デッドロック状態が発生する可能性があることが判明した場合、そのトランザクションの実行は許可されません。

デッドロック状況を事前に決定するために、トランザクションのタイムスタンプ順序付けメカニズムを使用するデッドロック防止スキームがあります。

ウェイトダイスキーム

このスキームでは、トランザクションが別のトランザクションによって競合するロックで既に保持されているリソース（データ項目）のロックを要求する場合、2つの可能性のいずれかが発生する可能性があります-

TS（T〜[.small]＃i＃〜）<TS（T〜[.small]＃j＃〜）-つまり、競合するロックを要求しているT〜[.small]＃i＃〜が古い場合T〜[.small]＃j＃〜-その後、T〜[.small]＃i＃〜は、データ項目が利用可能になるまで待機できます。
TS（T〜[.small]＃i＃〜）> TS（t〜[.small]＃j＃〜）-T〜[.small]＃i＃〜がT〜[.small]＃よりも若い場合j＃〜-その後T〜[.small]＃i＃〜が死にます。 T〜[.small]＃i＃〜は、ランダムな遅延で同じタイムスタンプで後で再起動されます。

このスキームにより、古いトランザクションは待機できますが、若いトランザクションは強制終了されます。

創傷待機スキーム

このスキームでは、トランザクションがリソース（データ項目）のロックを要求した場合、すでに別のトランザクションによって競合するロックが保持されているため、2つの可能性のいずれかが発生する可能性があります-

TS（T〜[.small]＃i＃〜）<TS（T〜[.small]＃j＃〜）の場合、T〜[.small]＃i＃〜はT〜[.small]＃j＃〜を強制的にロールバックされる-それはT〜[.small]＃i＃〜傷T〜[.small]＃j＃〜です。 T〜[.small]＃j＃〜は、ランダムな遅延で同じタイムスタンプで後で再起動されます。
TS（T〜[.small]＃i＃〜）> TS（T〜[.small]＃j＃〜）の場合、T〜[.small]＃i＃〜はリソースが利用可能になるまで待たされます。

このスキームでは、若いトランザクションが待機できます。しかし、古いトランザクションが新しいアイテムに保持されているアイテムを要求すると、古いトランザクションは新しいアイテムを強制的にアイテムを中止してリリースします。

どちらの場合も、後の段階でシステムに入るトランザクションは中止されます。

デッドロック回避

トランザクションの中止は、常に実際的なアプローチとは限りません。代わりに、デッドロック回避メカニズムを使用して、デッドロック状況を事前に検出できます。「グラフの待機」などのメソッドは使用可能ですが、トランザクションが軽量でリソースのインスタンスが少ないシステムにのみ適しています。かさばるシステムでは、デッドロック防止技術がうまく機能する場合があります。

グラフを待つ

これは、デッドロック状態が発生する可能性があるかどうかを追跡するために利用できる簡単な方法です。システムに入る各トランザクションに対して、ノードが作成されます。トランザクションT〜[.small]＃i＃〜が、他のトランザクションT〜[.small]＃j＃〜によって保持されているXなどのアイテムのロックを要求すると、T〜[から有向エッジが作成されます.small]＃i＃〜からT〜[.small]＃j＃〜へ。 T〜[.small]＃j＃〜がアイテムXを解放すると、それらの間のエッジはドロップされ、T〜[.small]＃i＃〜はデータアイテムをロックします。

システムは、他のユーザーが保持している一部のデータ項目を待機しているすべてのトランザクションについて、この待機グラフを維持します。システムは、グラフにサイクルがあるかどうかをチェックし続けます。

Wait-for Graph

ここでは、次の2つのアプローチのいずれかを使用できます-

まず、別のトランザクションによってすでにロックされているアイテムのリクエストを許可しないでください。これは常に実行可能であるとは限らず、トランザクションがデータ項目を無期限に待機し、それを取得できない飢starを引き起こす可能性があります。
2番目のオプションは、トランザクションの1つをロールバックすることです。古いトランザクションよりも重要な場合があるため、若いトランザクションをロールバックすることは必ずしも実行可能ではありません。相対アルゴリズムの助けを借りて、トランザクションが選択され、中止されます。このトランザクションは victim と呼ばれ、プロセスは victim selection と呼ばれます。

Dbms-deadlock

目次