정답
스케줄 (가)의 직렬화 그래프에는 \(T_1 \rightarrow T_2\), \(T_2 \rightarrow T_3\), \(T_1 \rightarrow T_3\), \(T_3 \rightarrow T_1\)의 간선이 존재하여 사이클 \(T_1 \rightarrow T_3 \rightarrow T_1\)이 생기므로, 스케줄 (가)는 충돌 직렬가능 스케줄이 아니다. ㉠ lock(X), ㉡ lock(Y), ㉢ unlock(X), ㉣ unlock(Y)
출제 의도
트랜잭션 스케줄에서 충돌 연산들을 이용해 직렬화 그래프를 작성하고, 그래프의 사이클 존재 여부로 충돌 직렬가능성을 판정하는 능력을 평가한다. 또한 기본 2단계 잠금(2PL) 프로토콜의 조건을 만족하도록 트랜잭션에 lock/unlock 연산을 적절히 삽입할 수 있는지를 묻는 문제이다.
풀이 과정
먼저 스케줄 (가)의 연산들을 시간 순서대로 적으면 다음과 같다.
\(T_1:\) read(X), write(X), read(Y), write(Y) \(T_2:\) read(X), write(X), read(Z), write(Z) \(T_3:\) read(Y), write(Y), read(Z), write(Z)
동일 데이터 항목에 대한 두 트랜잭션의 read/write, write/read, write/write 순서는 충돌이므로, 조건 (다)에 따라 직렬화 그래프의 간선을 만든다.
X에 대해 – \(T_1\)의 write(X) → \(T_2\)의 read(X) – \(T_1\)의 write(X) → \(T_2\)의 write(X) 따라서 \(T_1 \rightarrow T_2\) 간선이 생긴다.
Y에 대해 – \(T_1\)의 read(Y) → \(T_3\)의 write(Y) ⇒ \(T_1 \rightarrow T_3\) – \(T_3\)의 read(Y) → \(T_1\)의 write(Y) ⇒ \(T_3 \rightarrow T_1\) – \(T_1\)의 write(Y) → \(T_3\)의 write(Y) ⇒ \(T_1 \rightarrow T_3\) (이미 존재)
Z에 대해 – \(T_2\)의 read(Z) → \(T_3\)의 write(Z) – \(T_2\)의 write(Z) → \(T_3\)의 read(Z), write(Z) 따라서 \(T_2 \rightarrow T_3\) 간선이 생긴다.
정리하면 직렬화 그래프의 간선은
$$ T_1 \rightarrow T_2,\quad T_2 \rightarrow T_3,\quad T_1 \rightarrow T_3,\quad T_3 \rightarrow T_1 $$
이고, 특히 \(T_1 \rightarrow T_3 \rightarrow T_1\)의 사이클이 존재한다. 직렬화 그래프에 사이클이 있으면 해당 스케줄은 어떤 직렬 스케줄과도 충돌 동치가 될 수 없으므로, 스케줄 (가)는 충돌 직렬가능 스케줄이 아니다.
다음으로 기본 2PL 프로토콜을 적용하여 트랜잭션 \(T_1\)에 lock/unlock 연산을 추가한 것이 (나)이다. 기본 2PL의 조건은
– 모든 lock 연산은 최초의 unlock 연산보다 앞서 수행되어야 한다. – unlock 연산이 수행된 뒤에는 새로운 lock 연산을 할 수 없다.
T1은 데이터 X와 Y를 차례로 읽고 쓴다. 따라서
1. X를 사용하기 전에 X에 대한 독점락을 획득해야 하므로, read(X) 전에 lock(X)을 둔다. → ㉠ = lock(X) 2. Y를 사용하기 전에 Y에 대한 독점락을 획득해야 하므로, write(X) 이후, read(Y) 이전에 lock(Y)를 둔다. → ㉡ = lock(Y)
이 시점까지는 unlock 연산이 없으므로, 모든 lock이 unlock보다 앞에 있어 2PL의 증가 단계에 해당한다.
이후에는 더 이상 새로운 lock이 필요 없으므로, 감소 단계에서 락을 해제한다.
3. 이미 Y에 대한 lock까지 획득한 뒤이므로, X에 대한 lock은 read/write(X)가 끝난 시점에서 해제할 수 있다. 따라서 read(Y) 앞에 unlock(X)를 둔다. → ㉢ = unlock(X) 4. 마지막으로 Y에 대한 연산인 write(Y)가 끝난 뒤, Y에 대한 lock을 해제한다. → ㉣ = unlock(Y)
결국 (나)의 T1 스케줄은 다음과 같이 된다.
lock(X); read(X); write(X); lock(Y); unlock(X); read(Y); write(Y); unlock(Y)
모든 lock 연산이 최초의 unlock 연산(unlock(X))보다 먼저 수행되고, unlock 이후에는 새로운 lock을 획득하지 않으므로, T1은 기본 2PL 프로토콜을 만족하며 이로 인해 충돌 직렬가능 스케줄이 되도록 조정된다.
<풀이가 부정확할 수 있으니 반드시 교차검증 확인 바랍니다.>