ホーム > データベーススペシャリスト試験 > 2013年

データベーススペシャリスト試験 2013年午前2 問10

t₁~~t₁₀の時刻でスケジュールされたトランザクションT₁~~T₄がある。時刻t₁₀でT₁がcommitを発行する直前の、トランザクションの待ちグラフを作成した。aに当てはまるトランザクションはどれか。ここで、select（X）は共有ロックを掛けて資源Xを参照することを表し、update（X）は専有ロックを掛けて資源✕を更新することを表す。これらのロックは、commitされた時にアンロックされるものとする。また，トランザクションの待ちグラフの矢印は、Tᵢ→Tⱼとしたとき、Tⱼがロックしている資源のアンロックを、Tᵢが待つことを表す。

ア：

T₁

イ：

T₂

（正解）

ウ：

T₃

エ：

T₄

解説

問題の整理

記号	意味
select(X)	資源 X に共有ロック (S-lock) を取得して読み取り
update(X)	資源 X に排他ロック (X-lock) を取得して更新
ロックのルール	解除 (UNLOCK) は commit まで行われない

待ちグラフ で
Tᵢ → Tⱼ は Tᵢ が必要なロックを、すでに Tⱼ が保持しているため待たされている ことを示す。

待ちグラフの形（問題文より）

   a → b
   ↑   ↓
   d ← c

タイムラインからロック保持状況を追う

1. ロック取得状況

時刻	T₁	T₂	T₃	T₄
t₁	S(A)
t₂		S(B)
t₃			S(A) ← A は T₁ が S ロック中
t₆	S(C)
t₇		S(C) ← C は T₁ が S ロック中
t₈		X(C) 要求 (待機)
t₉			X(A) 要求 (待機)	S(B) ← B は T₂ が S ロック中
t₁₀	commit

T₁：S(A), S(C) を保持したまま t₁₀ まで進行

T₂：S(B) を保持。t₈ で X(C) を取得しようとして T₁ の S(C) に阻まれ待ち

T₃：S(A) を取得。t₉ で X(A) を取得しようとして T₁ の S(A) に阻まれ待ち

T₄：t₄ で S(B) を取得。t₅ で X(B) を取得しようとして T₂ の S(B) に阻まれ待ち

2. エッジを作る

待たされている Tx	欲しいロック	ブロックしている Tx	グラフの矢印
T₂	X(C)	T₁ (S(C))	T₂ → T₁
T₃	X(A)	T₁ (S(A))	T₃ → T₁
T₄	X(B)	T₂ (S(B))	T₄ → T₂

逆方向に T₁ → T₂ や T₁ → T₃ のエッジはない
（T₁ はすでにロック済みで待っていない）。

待ちグラフをマッピング

T₃ → T₁
T₂ → T₁
T₄ → T₂

描き替えると

   T₁
  ↑  ↑
 T₂  T₃
  ↑
 T₄

これは問題文の図

   a
  ↑  ↑
  b  c
  ↑
  d

と 同じ構造。
したがって

ノード	トランザクション
a	T₁
b	T₂
c	T₃
d	T₄

正解選択肢

ノード a に当てはまるトランザクションは T₁…ではなく？
待ちグラフ図では 矢印の向きが逆（a が待ち側）になっている点に注意。
図では a から b に矢印＝ a が b を待つ。
先ほどの解析では T₁ は誰も待たない。
よって a = T₃、b=T₁、c=T₂、d=T₄ と読み替える。

整理すると

ノード	説明	実行中トランザクション
a	他 2 件に矢印を出している待ち元	T₃
b	a をブロックし，d を待たせている	T₁
c	a をブロックしているもう 1 件	T₂
d	b を待つ	T₄

結論

ノード a が表すトランザクションは T₃
選択肢ではウが該当する。

← 前の問題へ次の問題へ →

データベーススペシャリスト試験 2013年 午前2 問10

解説