分野：テクノロジ系
中分類：データベース
小分類：トランザクション処理

デッドロックとは、共有資源を使用する2つ以上のトランザクションが、互いに相手トランザクションが必要とする資源を排他的に使用していて、互いのトランザクションが相手が使用している資源の解放を待っている状態です。デッドロックが発生するとトランザクションは永遠に待ち状態になってしまうため、処理の続行ができなくなってしまいます。この問題では、2つのトランザクションのロック要求を追跡することでデッドロックが発生するか否かを判断しますが、その前提として共有ロック・専有ロック及び2相ロッキングプロトコルについて確認しておきましょう。

共有ロック

データを読込むときに使うロックで、この状態の場合は他のトランザクションによる更新処理ができなくなる(読込みは可能)。

専有ロック

データを更新するときに使うロックで、この状態の場合は他のトランザクションによる読込みや更新ができなくなる。

上記の性質から、ある資源に共有または専有ロックが掛けられているときの新たなロックの可否は次の表のようになります。つまり、資源にかけられているロックが"共有"である場合にのみ、別のトランザクションが新たに"共有ロック"をかけることが可能です。

そして、2相ロッキングプロトコルは、トランザクション処理で読書きが必要になったデータにその都度ロックをかけていき、全てのロックを獲得した後にだけロックの解除を行うルールを課すロック方式です。つまり、ロックの解除が行われるのはトランザクションの終了時になります。各処理が終わる度に当該ロックを解除するわけではないので注意しましょう。

これを踏まえて、トランザクションA(以下、T_A)とトランザクションB(以下、T_B)の処理を選択肢ごとに見ていきます。

• 1. T_Aが W を共有ロックする。
  2. T_Bが W を共有ロックする。
  3. T_Aが X を専有ロックする。
  4. T_Bが Y を専有ロックする。
  5. T_Aが Y の専有ロックを要求するが、T_Bが専有ロック中なので待ち状態となる。
  6. T_Bが X の専有ロックを要求するが、T_Aが専有ロック中なので待ち状態となる。
  7. T_Aが Y の解放を、T_Bが X の解放を互いに待っているのでデッドロックとなる。
  
• 1. T_Aが W を共有ロックする。
  2. T_Bが W を共有ロックする。
  3. T_Aが X を専有ロックする。
  4. T_Bが Y を専有ロックする。
  5. T_Aが Y の専有ロックを要求するが、T_Bが専有ロック中なので待ち状態となる。
  6. T_Bが Z を専有ロックする。
  7. T_Bが X の専有ロックを要求するが、T_Aが専有ロック中なので待ち状態となる。
  8. T_Aが Y の解放を、T_Bが X の解放を互いに待っているのでデッドロックとなる。
  
• 1. T_Aが W を共有ロックする。
  2. T_Bが X を専有ロックする。
  3. T_Aが X の専有ロックを要求するが、T_Bが専有ロック中なので待ち状態となる。
  4. T_Bが W を共有ロックする。
  5. T_Bが Y を専有ロックする。
  6. T_Bが Z を専有ロックする。
  7. T_Bの終了によりロックが解除される。
  8. T_Aが X を専有ロックする。
  9. T_Aが Y を専有ロックする。
  10. T_Aが Z を専有ロックする。
  11. T_Aの終了によりロックが解除される。
  
  この順序だとデッドロックが発生しません。一般的に双方のトランザクションで資源の専有順序が同じ場合にはデッドロックが発生しないことが知られています。本問でも、T_A・「ウ」ともに X→Y→Z の順になっています。
• 1. T_Aが W を共有ロックする。
  2. T_Bが Y を専有ロックする。
  3. T_Aが X を専有ロックする。
  4. T_Bが Z を専有ロックする。
  5. T_Aが Y の専有ロックを要求するが、T_Bが専有ロック中なので待ち状態となる。
  6. T_Bが X の専有ロックを要求するが、T_Aが専有ロック中なので待ち状態となる。
  7. T_Aが Y の解放を、T_Bが X の解放を互いに待っているのでデッドロックとなる。