直列化可能性と共有・専有ロックの競合に基づくトランザクション待ちグラフの特定

共有ロックと専有ロックの競合条件から、時刻 $t_{10}$ 直前におけるトランザクション間の待ち関係（有向辺）を特定する問題です。 $t_1 \sim t_4$： $T_1$ が $A$、$T_2$ が $B$、$T_3$ が $A$、$T_4$ が $B$ に共有ロックを獲得します。共有ロック同士は競合しないため、すべて成功します。 $t_5$： $T_4$ が資源 $B$ に専有ロック $\text{update}(B)$ を要求します。しかし、$T_2$ がすでに $B$ に共有ロックを保持しているため、$T_4$ は $T_2$ のアンロック待ちとなり、有向辺 $T_4 \rightarrow T_2$ が生じます。 $t_6 \sim t_7$： $T_1$ と $T_2$ が資源 $C$ に共有ロックを獲得します（成功）。 $t_8$： $T_2$ が資源 $C$ に専有ロック $\text{update}(C)$ を要求します。しかし、$T_1$ がすでに $C$ に共有ロックを保持しているため、$T_2$ は $T_1$ のアンロック待ちとなり、有向辺 $T_2 \rightarrow T_1$ が生じます。 $t_9$： $T_3$ が資源 $A$ に専有ロック $\text{update}(A)$ を要求します。しかし、$T_1$ がすでに $A$ に共有ロックを保持しているため、$T_3$ は $T_1$ のアンロック待ちとなり、有向辺 $T_3 \rightarrow T_1$ が生じます。 以上より、時刻 $t_{10}$ 直前の待ちグラフの依存関係は $T_4 \rightarrow T_2 \rightarrow T_1$ および $T_3 \rightarrow T_1$ となります。図の待ちグラフにおいて $T_4 \rightarrow$〔 　a　 〕$\rightarrow T_1$ の位置にあるのは $T_2$ です。 したがって、正解は イ の $T_2$ です。

t1<t10t_1 < t_{10} の時刻でスケジュールされたトランザクション T1∼T4T_1 \sim T_4 がある。時刻 t10t_{10} で T1T_1 がcommitを発行する直前の，トランザクションの待ちグラフを作成した。〔 　a　 〕に当てはまるトランザクションはどれか。ここで，select(X)\text{select}(X) は共有ロックを掛けて資源 XX を参照することを表し，update(X)\text{update}(X) は専有ロックを掛けて資源 XX を更新することを表す。これらのロックは，commitされるまでアンロックされないものとする。また，トランザクションの待ちグラフの矢印は，Ti→TjT_i \rightarrow T_j としたとき，TjT_j がロックしている資源のアンロックを，TiT_i が待つことを表す。

〔トランザクションのスケジュール〕

時刻

トランザクション

T1T_1

T2T_2

T3T_3

T4T_4

t1t_1

select(A)\text{select}(A)

ー

ー

ー

t2t_2

ー

select(B)\text{select}(B)

ー

ー

t3t_3

ー

ー

select(A)\text{select}(A)

ー

t4t_4

ー

ー

ー

select(B)\text{select}(B)

t5t_5

ー

ー

ー

update(B)\text{update}(B)

t6t_6

select(C)\text{select}(C)

ー

ー

ー

t7t_7

ー

select(C)\text{select}(C)

ー

ー

t8t_8

ー

update(C)\text{update}(C)

ー

ー

t9t_9

ー

ー

update(A)\text{update}(A)

ー

t10t_{10}

commit

ー

ー

ー

〔トランザクションの待ちグラフ〕

トランザクションの待ちグラフ
出典平成31年春期 午前Ⅱ
ア
T1T_1
イ
T2T_2
ウ
T3T_3
エ
T4T_4