실습 문제 2
같은 방향의 충돌만 쌓이면 선행 그래프는 순환하지 않습니다

이 스케줄은 A와 B 모두에서 같은 결론을 만듭니다. 각 항목에서 생기는 간선 방향만 모으면 왜 T1 → T2로 직렬화되는지 바로 확인할 수 있습니다.

공통 스케줄을 항목별 증거로 나누기

충돌 직렬 가능성은 충돌 개수보다, 각 항목이 어떤 방향의 간선을 만드는지로 판단합니다.

스케줄 S
R1(A) W1(A) R2(A) W2(A) · R1(B) W1(B) R2(B) W2(B)
항목
충돌 관찰
생기는 간선
A
W1(A) < R2(A), W2(A)

T1이 먼저 쓴 뒤 T2가 읽고 쓰므로, A에서는 역방향 충돌이 생기지 않습니다.

T1 → T2
B
W1(B) < R2(B), W2(B)

B도 같은 순서라서 새 간선이 추가돼도 방향은 그대로 유지됩니다.

T1 → T2

선행 그래프에서 읽는 최종 판정

두 데이터 항목이 같은 방향의 간선을 만들면, 그래프는 한쪽으로만 흐릅니다.

T1
모든 충돌
T2
1

A, B 모두 T1 → T2만 추가하므로 그래프에 방향 불일치가 없습니다.

2

T2 → T1이 없어서 시작점으로 되돌아오는 사이클을 만들 수 없습니다.

3

따라서 이 스케줄은 T1 다음 T2의 직렬 실행과 동등합니다.

핵심 판단 기준

충돌이 여러 번 있어도, 간선 방향이 하나로만 모이면 선행 그래프에는 사이클이 생기지 않습니다.