개념
-
트랜잭션 직렬화와 회복하는 스케줄이 데터 일관성에 영향을 미치는 여부를 판별하고 일관성이 유지되는 상태로 복원시키기 위해 정의한 개념
-
일관성 훼손을 발생시키는 트랜잭션에 대해 동시성 제어를 통해 일관성 유지에 개입
- 트랜잭션 간 연산의 순서를 제어
- 어떠한 데이터 읽기, 갱신 연산에도 무결성을 유지
- 동시에 실행되는 트랜잭션 수를 증가
- 동시셍 제어 구약
- 락 기반 규약
- 타임스탬프 기반 규약
- 검증 기반 규약
락 기반 규약
- 직렬 가능성을 보장하기 위해 락(잠금)을 사용하여 데이터 항목에 연산 적용 전 트랜잭션이 락(잠금)을 사용하여 데이터 항목에 연산 적용 전 트랜잭션이 락을 획득하고 연산 후 반납하도록 하는 규약
- 락의 종류
- 공유 락(shared lock: S): 트랜잭션 T가 LS(Q) 명령으로 데이터 항목 Q에 공유 락을 획득하면 T는 Q를 읽을 수는 있지만 쓸 수는 없는 락
- 배타 락(exclusive lock: X): 트랜잭션 T가 LX(Q) 명령으로 데이터 항목 Q에 대한 배타 락을 획득하면, T가 Q를 읽고 쓸 수 있는 락
락 양립성
- 트랜잭션은 연산하고자 하는 데이터에 대한 락을 획득해야만 연산 진행 가능
- 락 양립성 함수
| - | 공유 락(S) | 배타 락(X) |
|---|---|---|
| 공유 락(S) | 가능 | 불가능 |
| 배타 락(X) | 불가능 | 가능 |
- 공유 락: 다른 공유 락과 양립 가능
- 배타 락: 다른 락과 양립 불가능
- 배타 락 요청은 공유 락 반납 시까지 대기
- 락의 반납은 UN() 명령 사용
동시실행 스케줄
락 반납이 지연된 스케줄
-> 일관성 유지 가능
락 반납 지연의 문제
2단계 락킹 규약(2PL)
타임스탬프 기반 규약
Tᵢ가 Read(Q)를 수행할 때
- TS(Tᵢ) < W-TS(Q)이면 Read 연산이 거부되고 Tᵢ는 롤백
- TS(Tᵢ) >= W-TS(Q)이면 Read 연산이 수행되고 R-TS(Q)는 기존 R-TS(Q)와 TS(Tᵢ)중 최대값으로 설정
Tᵢ가 Write(Q)를 수행할 때
- TS(Tᵢ) < R-TS(Q) 또는 TS(Tᵢ) < W-TS(Q)이면 Write 연산이 거부되고 Tᵢ는 롤백
- 그렇지 않으면 Write 연산을 수행하고 W-TS(Q)는 TS(Tᵢ)로 설정
타임스탬프 기반 규약의 적용
-> 문제없음
토마스 기록 규칙
- TS(Tᵢ) < R-TS(Q)인 경우 Write 연산 거부 && Tᵢ는 롤백
- TS(Tᵢ) < W-TS(Q)인 경우 Write 연산 거부
- 아닌 경우 Write 연산 수행 && W-TS(Q)는 TS(Tᵢ)로 설정
교착상태
처리방법
1. 교착상태 발생이 비교적 높은 시스템의 경우
- 교상태 방지 규약 사용
- 모든 데이터 항목에 대해 락을 설정하는 기법
- 단점1) : 트랜잭션이 시작되기 전에 어떤 데이터에 락을 걸어야 하는지 미리 알기가 어려움
- 단점2): 락이 걸린 상태에서 많은 데이터들이 오랫동안 사용되지 않아 데이터 항목에 대한 이용률이 매우 낮아짐 - 타임스탬프를 이용한 선점유 기법
2. 교착상태 발생이 비교적 높지 않은 시스템의 경우
- 교착상태 탐지와 회복 기법 사용
- 대기 그래프
- 희생자 선정
교착상태 방지
교착상태 탐지와 회복
- 교착상태 발생이 비교적 높지 않은 시스템의 경우 주기적으로 교착상태를 탐지하고 발생 시 회복절차를 수행
- 탐지 및 회복 절차
- 트랜잭션이 할당된 데이터 항목과 현재 요청되고 있는 데이터 항목에 대한 정보를 유지
- 교착상태가 발생여부를 판별하기 위해 시스템의 상태를 검사하는 알고리즘을 주기적으로 수행
- 교착상태가 검출되면 시스템은 교착상태로부터 회복을 위한 절차를 수행
교착상태 탐지
- 대기 그래프 (wait-for graph)를 이용하여 확인 가능
- 정점 V는 시스템 내의 트랜잭션으로 구성되며
- 간선 E는 트랜잭션의 순서쌍 (Tᵢ, T𝘫)으로 이루어짐
- Tᵢ가 요청한 데이터의 락을 T𝘫가 소유하고 있으며,
- Tᵢ는 T𝘫가 락을 반납하는 것을 대기하는 상태
- 대기 그래프에 사이클이 있다면 교착 상태가 발생
교착상태 회복
- 희생자 선정: 롤백 비용이 가장 적은 트랜잭션을 선택
- 연산을 수행한 시간과 남은 작업을 마치기 위한 시간
- 사용한 데이터와 트랜잭션 실행에 필요한 추가적인 데이터
- 롤백에 포함되는 트랜잭션의 개수
- 희생자 롤백: 어느 시점까지 롤백할 것인지 결정
- 전체 롤백 vs 교착상태를 해결하는 지점
- 모든 트랜잭션의 상태에 대한 정보를 부가적으로 유지
- 무한정 기다림 해결
- 같은 트랜잭션이 항상 희생자로 선정되지 않도록 희생자 선정시 롤백 횟수를 고려
우리스러움