▣ 타임스탬프 순서 기법
타임스탬프(TS)란 시스템이 트랜잭션을 유일하게 식별하기 위해 부여한 식별자임
통상적으로 타임스탬프는 트랜잭션이 시스템에 들어오는 순서대로 부여되기 때문에 트랜잭션의 실행 시작 시간으로 생각함
1. 타임스탬프 순서 규약
1) 트랜잭션 Ti가 read(x)를 수행하려 할 때 :
- TS(Ti) ≥ write_TS(x)이면,
read(x)를 허용하고, read_TS(x) ← max{ read_TS(x), TS(Ti) }
- 아니면, read(x)를 거부하고, Ti를 취소시켜 복귀시킴
2) 트랜잭션 Ti가 write(x)를 수행하려 할 때 :
- TS(Ti) ≥ read_TS(x)이고, TS(Ti) ≥ write_TS(x)이면,
write(x)를 허용하고 write_TS(x) ← TS(Ti)
- 아니면, write(x)를 거부하고, Ti를 취소시켜 복귀시킴
* 타임스탬프 순서 규약에서 write 연산의 거부로 인하여 트랜잭션의 취소가 자주 발생
-> 토마스(Thomas)의 기록 규칙으로 감소
2. 토마스의 기록 규칙
트랜잭션 Ti가 write(x)를 수행하려 할 때 :
- TS(Ti) < read_TS(x)이면, write(x)를 거부하고 Ti를 취소시켜 복귀시킴
- TS(Ti) < write_TS(x)이면, Ti의 write(x)를 실행한 것으로 간주하고 무시함
- 그 이외의 경우는 write(x)를 허용하고, write_TS(x) ← TS(Ti)
타임스탬프 초기값
TS(T1) = 2 (2시 시작), TS(T2) = 3 (3시 시작)
read_TS(x) = 1, write_TS(x) = 1
1) T1은 read(x)를 실행하고 read_TS(x)를 그대로 둔다. (틀림)
-> TS(T1) <= write_TS(x) 이므로 읽기허용, read_TS(x) <- max(2,1)
∴ read_TS(x) = 2
2) T2의 write(x)는 TS(T2) >= write_TS(x)이므로 거부된다. (틀림)
-> TS(T2) >= read_TS(x)이고, TS(T2) >= write_TS(x) 이므로 쓰기허용
∴ write_TS(x) = 3
3) 타임스탬프 순서 기법을 적용하면 위와 같이 T1이 취소 복귀되어 직렬 가능한 스케줄이 아님
4) 토마스 기록 규칙을 적용하면 T1의 write(x)는 TS(T1) < write_TS(x) (2 < 3)이므로 실행한 것
으로 간주하고 무시함