Aritalab:Lecture/Database/Transaction - Revision history

Adm: /* 整列化可能≠デッドロック回避 */

2011-10-03T02:43:38Z

‎整列化可能≠デッドロック回避

Adm: /* 整列化可能≠デッドロック回避 */

2011-10-03T02:42:59Z

‎整列化可能≠デッドロック回避

Adm: /* 整列化可能≠デッドロック回避 */

2011-10-03T02:39:09Z

‎整列化可能≠デッドロック回避

Adm: /* 整列化可能≠デッドロック回避 */

2011-10-03T02:36:34Z

‎整列化可能≠デッドロック回避

Adm: /* 整列化可能性 */

2011-10-03T02:24:42Z

‎整列化可能性

Adm: /* 整列化可能性判定グラフ */

2011-10-03T01:58:38Z

‎整列化可能性判定グラフ

Adm: /* 整列化可能≠デッドロック回避 */

2011-09-28T08:57:26Z

‎整列化可能≠デッドロック回避

Adm: /* ２相ロック */

2011-09-28T08:55:37Z

‎２相ロック

Adm: /* ２相ロック */

2011-09-28T08:55:02Z

‎２相ロック

Adm: /* Conservative 2PL */

2011-09-28T08:46:54Z

‎Conservative 2PL

@@ Line 258: / Line 258: @@
 |}
 スケジュール S' について整列化可能性判定グラフを作ると
-T1 &rarr; T3 <br/>
+T1 &rarr; T3 となります。つまりT3より先にT1が実行されなくてはなりません。
 となります。つまりT3より先にT1が実行されなくてはなりません。
 よってデッドロックの場合T1ではなくT2を中断すべきですが、実際においてどちらが中断されるかはシステムによって異なります。
 ;参考、注釈
 <references/>

@@ Line 223: / Line 223: @@
 ===整列化可能≠デッドロック回避===
-整列化可能性とデッドロックとは別の概念です。例えば整列化可能なトランザクションからなる以下のスケジュール S' はデッドロックになっています。T2 と T1 が互いにリソース A, B を要求しつづける点に注意しましょう。この場合、T2 を中断して後回しにします。T2 を後回しにしても、整列化可能性から実行結果の同一性が保証されます。しかし T1 を後回しにすると、T3 の実行結果が初めのスケジュールと異なる可能性が生じます。また、ロック要求を一括しておこなう厳しい２相ロック (conservative 2PL) を実施する場合、デッドロックを回避できます。
+整列化可能性とデッドロックとは別の概念です。例えば整列化可能なトランザクションからなる以下のスケジュール S' はデッドロックになっています。T2 と T1 が互いにリソース A, B を要求しつづける点に注意しましょう。この場合、T2 かT1のどちらかを中断して後回しにします。T2 を後回しにしても、整列化可能性から実行結果の同一性が保証されます。しかし T1 を後回しにすると、T3 の実行結果が初めのスケジュールと異なる可能性が生じます。また、ロック要求を一括しておこなう厳しい２相ロック (conservative 2PL) を実施する場合、デッドロックを回避できます。
 {|
+|
-{| class="wikitable" style="float:right"
+{| class="wikitable"
 ! デッドロックを起こす<br/>スケジュール S'
 |-
@@ Line 243: / Line 243: @@
 |}
+|
-左のスケジュールについて整列化可能性判定グラフを作ると<br/>
+{| class="wikitable"
-T1 &rarr; T3 <br/>
-となります。つまりT3より先にT1が実行されなくてはなりません。
-よってデッドロックの場合、T1ではなくT2を中断すべきです。
-実際のデッドロックにおいてどちらが中断されるかはシステムによって異なります。
-−
-{| class="wikitable" style="float:right"
 ! 厳しい2PLに基づく<br/>スケジュール
 |-
@@ Line 263: / Line 257: @@
 |}
 |}
+スケジュール S' について整列化可能性判定グラフを作ると
+T1 &rarr; T3 <br/>
+となります。つまりT3より先にT1が実行されなくてはなりません。
+よってデッドロックの場合T1ではなくT2を中断すべきですが、実際においてどちらが中断されるかはシステムによって異なります。
 ;参考、注釈
 <references/>

@@ Line 245: / Line 245: @@
 左のスケジュールについて整列化可能性判定グラフを作ると<br/>
 T1 &rarr; T3 <br/>
-となる。
+となります。つまりT3より先にT1が実行されなくてはなりません。
+|
 {| class="wikitable" style="float:right"

@@ Line 223: / Line 223: @@
 ===整列化可能≠デッドロック回避===
-整列化可能性とデッドロックとは別の概念です。例えば整列化可能なトランザクションからなる以下のスケジュールはデッドロックになっています。T2 と T1 が互いにリソース A, B を要求しつづける点に注意しましょう。この場合、T2 を中断して後回しにします。T2 を後回しにしても、整列化可能性から実行結果の同一性が保証されます。しかし T1 を後回しにすると、T3 の実行結果が初めのスケジュールと異なる可能性が生じます。
+整列化可能性とデッドロックとは別の概念です。例えば整列化可能なトランザクションからなる以下のスケジュール S' はデッドロックになっています。T2 と T1 が互いにリソース A, B を要求しつづける点に注意しましょう。この場合、T2 を中断して後回しにします。T2 を後回しにしても、整列化可能性から実行結果の同一性が保証されます。しかし T1 を後回しにすると、T3 の実行結果が初めのスケジュールと異なる可能性が生じます。また、ロック要求を一括しておこなう厳しい２相ロック (conservative 2PL) を実施する場合、デッドロックを回避できます。
-−
-ロック要求を一括しておこなう厳しい２相ロックを実施する場合、デッドロックを回避できます。
 {| class="wikitable" style="float:right"
-! スケジュール S'
+! デッドロックを起こす<br/>スケジュール S'
 |-
+|
@@ Line 242: / Line 242: @@
 T2: UNLOCK A
 |}
 ;参考、注釈
 <references/>

@@ Line 125: / Line 125: @@
 |-
+|
-T2: LOCK B<br/>
+<span style="color:red">T2: LOCK B</span><br/>
 T1: LOCK A<br/>
-T2: UNLOCK B<br/>
+<span style="color:red">T2: UNLOCK B</span><br/>
 T1: LOCK B<br/>
 T1: UNLOCK A<br/>
-T3: LOCK A<br/>
+<span style="color:blue">T3: LOCK A</span><br/>
-T3: UNLOCK A<br/>
+<span style="color:blue">T3: UNLOCK A</span><br/>
 T1: UNLOCK B<br/>
-T2: LOCK A<br/>
+<span style="color:red">T2: LOCK A</span><br/>
-T2: UNLOCK A
+<span style="color:red">T2: UNLOCK A</span>
 |}
 |valign="top"|

@@ Line 160: / Line 160: @@
 T2: UNLOCK A
 |}
-;定理 判定グラフに閉路があれば整列化は不可能、なければ可能
+;定理：判定グラフに閉路があれば整列化は不可能、なければ可能
 : もし閉路がない場合、グラフの出力辺しか持たないトランザクション i が必ず存在します。そのトランザクションを実行列に加え、グラフから頂点 i およびそこから出る辺を消去します。この操作を繰り返せば、整列化が終了します。

@@ Line 63: / Line 63: @@
 ====２相ロック====
-（２相ロックの意味は以下で解説します。）各トランザクションは必要とするリソースすべてのロック要求を出し、ロックマネージャーは全要求を一度に許可するか、全要求を不許可にする方法です。ロック要求をトランザクションの途中ですることが無いためデッドロックが起きえません。一般に２相ロックという場合、「全要求を一度に許可」するプロトコルではなく、全てのロック要求を、ロック解除より前におこなうプロトコルを指します。この場合、２相ロックでデッドロックを回避できません。
+（２相ロックは以下で更に解説します。）各トランザクションは必要とするリソースすべてのロック要求を出し、ロックマネージャーは全要求を一度に許可するか、全要求を不許可にする方法です。ロック要求をトランザクションの途中ですることが無いためデッドロックが起きえません。一般に２相ロックという場合、「全要求を一度に許可」するプロトコルではなく、全てのロック要求を、ロック解除より前におこなうプロトコルを指します。この場合、２相ロックでデッドロックを回避できません。
 トランザクションが用いる全リソースをすべて事前に把握するのは難しい作業です。そのため、必要以上にリソースをロックすることになります。また一つでもリソースが確保できなければ、そのトランザクションは実行を遅らせなくてはなりません。デッドロックを回避するためにロック要求を一括しておこなう制約は、実際には用いられません。

@@ Line 62: / Line 62: @@
 T1 がウェイトして T2 がいつか中断されるのを待つ方針を wait-die 戦略、優先度の高い T1 が決して待たない方針を wound-wait 戦略といいます。いずれにしても、トランザクションが最初に開始された時間（タイムスタンプ）を記録して、中断されたトランザクションが後で必ず実行される保証が必要です。
-====Conservative 2PL====
+====２相ロック====
-（2PLの言葉の意味は以下で解説します。）各トランザクションは必要とするリソースすべてのロック要求を出し、ロックマネージャーは全要求を許可するか、全要求を不許可にする方法です。ロック要求をトランザクションの途中ですることが無いためデッドロックが起きえません。
+（２相ロックの意味は以下で解説します。）各トランザクションは必要とするリソースすべてのロック要求を出し、ロックマネージャーは全要求を許可するか、全要求を不許可にする方法です。ロック要求をトランザクションの途中ですることが無いためデッドロックが起きえません。
 しかしトランザクションが用いる全リソースをすべて事前に把握するのは難しく、必要以上にリソースをロックすることになります。また一つでもリソースが確保できなければ、そのトランザクションは実行を遅らせなくてはなりません。そのため、実際には利用されません。