| Timestamp Ordering | 타임스탬프(Timestamp) Ordering(순서) 기법 TS라고 함, 토마스(Thomas)쓰기규칙에서는 불필요한 write연산 무시하여 TS(Ti) < write-TS(x)인 경우 write연산을 수행하지 않고 Ti 수행가능, 장점 : 직렬가능, 교착상태방지, 단점 : 연쇄복귀, 기아문제 |
토마스 쓰기 규칙 |
| 토픽 이름 (상) | Timestamp Ordering |
| 분류 | DB > 동시성제어(병행 제어) > Timestamp Ordering |
| 키워드(암기) | 타임스탬프 지정, 생성방법(논리적계수, 시스템시계), 종류(read_TS, write_TS) |
| 암기법(해당경우) |
기출문제
| 번호 | 문제 | 회차 |
| 1 | 13. 타임스탬프 순서(Timestamp Ordering) 기법에 대하여 설명하시오. | 모의_2017.01 |
| 2 | 8. 동시성 제어 기법에 대하여 다음을 설명하시오. 가. 타임스탬프 순서(Timestamp Ordering) 기법에 대하여 설명하시오. 나. Wait-Die, Wound-Wait 알고리즘에 대하여 설명하시오.. |
합숙_2016.07 |
| 3 | 데이터베이스 동시성 제어기법인 2PL(2 Phase Locking), Timestamp Ordering, 낙관적 검증기법을 비교 설명하시오. | 합숙_2014.01 |
I. 시스템 시계와 논리적 계수기를 이용한 순서지정 방식, Timestamp Ordering의 개요
가. Timestamp Ordering의 정의
- 트랜잭션을 식별하기 위해 DBMS가 부여하는 유일한 식별자인 타임 스탬프를 지정하여 트랜잭션 간의 순서를 미리선택하는 순서대로 직렬화하여 실행한 결과가 같음을 보장하는 동시성 제어 기법
- DBMS 가 부여하는 트랜젝션의 식별자인 타임스탬프를 이용하여 트랜젝션 실행의 순서를 미리 결정
나. Timestamp Ordering 특징
| 구분 | 설명 |
| 직렬성 보장 | - 상충되는 연산들이 타임 스탬프 순서로 처리됨으로 직렬성 (Serializability)이 보장 |
| 교착상태 방지 | - 트랜잭션이 결코 기다리는 경우가 없으므로 교착상태 (Deadlock) 를 방지 |
| 연쇄복귀 초래 | - 문제점은 연쇄복귀 (Cascading Rollback) 를 초래 |
II. Timestamp Ordering 개념도 및 생성 메커니즘
가. Timestamp Ordering 개념도
- DBMS 가 부여하는 트랜젝션의 식별자인 타임스탬프를 이용하여 트랜젝션 실행의 순서를 미리 결정
나. Timestamp Ordering 생성 메커니증
| 분류 | 구분 | 설명 |
| 생성방법 | 논리적 계수 (Logical Counter) |
트랜잭션이 시스템에 들어올 때마다 계수를 하나씩 증가시켜 트랜잭션의 타임스탬프 값으로 부여 |
| 시스템 시계 (System Clock) |
트랜잭션이 시스템에 들어오면 시스템 시계의 값을 그 트랜잭션의 타임스탬프 값으로 부여 | |
| 타임스탬프 종류 | read_TS(x) | 데이터 아이템 x 의 판독 타임스탬프로서 read(x)를 성공적으로 수행한 트랜잭션의 타임스탬프 중에서 제일 큰 타임스탬프 |
| write_TS(x) | 데이터 아이템 x 의 기록 타임스탬프로서 write(x)를 성공적으로 수행한 트랜잭션의 타임스탬프 중에서 제일 큰 타임스탬프 |
- 타임스탬프를 동시성 제어의 기준으로 사용하여 상충되는 연산들을 타임스탬프 순서대로 처리함으로써 직렬성 보장
다. Timestamp Ordering의 순서 규약
| 구분 | 규약 | 설명 |
| 트랜젝션 Ti가 읽기 시도 시 - read(x) 수행 |
TS(Ti) < write_TS(x) | - read(x)를 거부하고 Ti를 취소시켜 복귀시킴 - TS(Ti)보다 타임스탬프가 큰 어떤 트랜젝션이 Ti가 접근하기 전에 이미 x의 값을 먼저 생성 |
| TS(Ti) >= write_TS(x) | - read(x)를 허용하고 read_TS(x)는 TS(Ti)와 현재의 read_TS(x) 중에서 큰 것으로 설정 | |
| 트랜젝션 Ti가 쓰기 시도 시 - write(x) 수행 |
TS(Ti) < read_TS(x) | - write(x)를 거부하고 Ti를 취소시켜 복귀시킴 - TS(Ti)보다 타임스탬프가 큰 트랜젝션이 x의 값을 먼저 판독 |
| TS(Ti) < write_TS(x) | - write(x)를 거부하고 Ti를 취소시켜 복귀시킴 - TS(Ti)보다 타임스탬프가 큰 트랜젝션이 x의 값을 이미 기록 |
|
| TS(Ti) >= read_TS(Ti) 또는 TS(Ti) >= write_TS(Ti) |
- write(x)를 허용하고 write_TS(x)의 값은 TS(Ti)로 고정 |
- 타임스탬프를 이용하여 Dead Lock 을 방지하기 위해 Wait-Die/Wound-Wait 알고리즘이 사용됨
III. 타임스탬프 이용한 Dead Lock 방지 알고리즘
| Wait-Die | Wound-Wait |
 |
 |
- 두 기법 모두 불필요한 복귀가 자주 발생한다는 문제점이 있으며, 토마스의 기록 규칙을 통해 개선 가능
반응형
'정보관리기술사 > DB_데이터분석' 카테고리의 다른 글
| 낙관적 검증(Validation) 기법 (0) | 2023.08.08 |
|---|---|
| 다중 버전 동시성 제어(MVCC) (0) | 2023.08.06 |
| 2PL or 2PLP(2 Phase Locking) (0) | 2023.08.04 |
| 동시성 제어 (0) | 2023.08.03 |
| ARIES (Algorithms for Recovery and Isolation Exploiting Semantics) (0) | 2023.08.02 |