List
1. 락 기반 규약
1.1. 동시성 제어
•
트랜잭션 직렬화와 회복화는 데이터의 일관성에 영향을 미치는 여부를 판별하고, 일관성이 유지되는 성태로 복원시키기 위해 정의한 개념
•
동시성 제어
◦
트랜잭션 간 연산 순서 제어
◦
무결성 유지
◦
동시 실행 트랜잭션 수 증가
•
동시성 제어 규약
◦
락 기반 규약
◦
타임스탬프 기반 규약
◦
검증 기반 유약
1.2. 락 기반 규약
•
직렬 가능성 보장을 위해 락을 사용
•
락 획득 → 연산 → 반납
•
락 종류
◦
Shared lock
▪
공유 락을 획득하면 다른 트랜잭션이 읽을 수는 있지만 쓸 수 없음
◦
Exclusive lock
▪
쓰기 트랜잭션 수행시 사용. 다른 트랜잭션이 읽고 쓰는 것 모두 불가
1.3. 락 양립성
•
락을 획득해야만 연산 진행 가능
•
락 양립성 함수
•
락 반납시 UN() 명령 사용
1.4. 동시 실행 스케쥴
•
락 반납을 일찍한 트랜잭션
◦
T10이 락을 일찍 반납하여 비일관적인 상태에서 데이터 접근이 가능해져 T11이 정확하지 않은 결과 값을 출력
◦
Dirty Read
•
락 반납 지연 트랜잭션
•
락 반납 지연의 문제
◦
교착상태(Deadlock) 발생
◦
락이 해제되어 획득할때까지 대기해야 함
1.5. 2단계 락킹 규약 (2PL)
•
락을 요청/반납하는 두단계로 구성
◦
확장 단계 - 락을 얻을 수 있으나 반납할 수없음
◦
축소 단계 - 락을 반납할 수 있으나 새로운 락을 얻을 수 는 없는 단계
•
직렬성을 보장하나 교착상태 예방 불가
2. 타임스탬프 순서 규약
2.1. 개념
•
각 트랜잭션 실행 순서 판단을 위해 타임스탬프 (TS)를 부여
•
데이터 항목에 대한 타임스탬프 할당
◦
W-TS(Q)
▪
Write(Q)를 성공적으로 실행한 트랜잭션 중 가장 큰 타임스탬프
◦
R-TS(Q)
▪
Read(Q)를 성공적으로 실행한 트랜잭션 중 가장 큰 타임스탬프
•
타임스태프 할당 방법
◦
시스템 클럭 값
◦
논리적 계수기
2.2. Ti가 Read(Q)를 수행할 때
•
TS(Ti) < W-TS(Q) 이면 Read 연산이 거부되고 Ti는 롤백
•
TS(Ti) ≥ W-TS(Q) 이면 Read 연산이 수행되고 R-TS(Q)는 기존 R-TS(Q)와 TS(Ti) 중 최대값으로 설정
2.3. Ti가 Write(Q)를 수행할 때
•
TS(Ti) < R-TS(Q) 또는 TS(Ti) < W-TS(Q)이면 Write 연산은 거부되고 Ti는 롤백
•
그렇지 않으면 Write 연산을 수행하고 W-TS(Q)는 TS(Ti)로 설정
2.4. 타임스탬프 기반 규약의 적용
•
TS(T14) < TS(T15)
2.5. 토마스 기록 규칙
•
TS(Ti) < R-TS(Q) 이면 Write 연산이 거부되고 Ti는 롤백
•
TS(Ti) < W-TS(Q)이면 Write 연산은 거부된다
•
그렇지 않으면 Write 연산을 수행하고 W-TS(Q)는 TS(Ti)로 설정
3. 교착 상태
•
트랜잭션이 특정 레코드 획득을 위해 다른 트랜잭션을 기다리는 상태
3.2. 교착상태 처리 방법
•
교착상태 발생이 비교적 높은 시스템의 경우
◦
교착상태 방지 규약 사용
▪
모든 데이터 항목에 대해 락을 설정하는 기법
•
어떤 데이터에 락을 걸어야할지 예측 어려움
•
데이터 항목에 대한 자원 이용률이 낮음
▪
타임스탬프를 이용한 선저유 기법
•
교착상태 발생이 비교적 높지 않은 시스템의 경우
◦
교착상태 탐지 및 회복 기법 사용
▪
대기 그래프
▪
희생자 선정
3.3. 교착상태 방지
•
타임스탬프 이용
◦
Ti가 락을 소유한 데이터 항목을 Ti가 요청하는 상황
▪
wait-die 기법 (비선점유 기반)
•
T1 < T2일때 T1은 기다림
•
T1 < T2일때 T2는 롤백
▪
wound-wait 기법 (선점유 기반)
•
T1 < T2일때 T2는 기다림
◦
T1이 획득한 락이 해제될때까지 기다림
•
T1 < T2일때 T2은 롤백하고 락을 이양
◦
T1이 먼저 시작된 트랜잭션이므로 먼저 시작된 트랜잭션에게 락을 이양
3.4. 교착상태 탐지와 회복
◦
프로세스
▪
트랜잭션이 할당된 데이터 항목과 현재 요청되고 있는 데이터 항목에 대한 정보 유지
▪
교착상태 발생 여부 판별을 위해 시스템 상태 검사 알고리즘 주기적으로 실행
▪
교착상태 검출되면 시스템은 교착상태로부터 회복 절차 수행
◦
탐지
▪
대기 그래프 (wait-for graph)를 이용하여 확인 가능
▪
정점 V는 시스템 내 트랜잭션으로 구성
▪
간선 E는 트랜잭션의 순서쌍 (Ti, Tj)로 이루어짐
•
Ti가 요청한 데이터 락을 Tj가 소유하고 있음
•
Ti는 Tj가 락을 반납하기를 대기하는 상태
▪
대기 그래프에 사이클이 있다면 교착상태 발생
▪
예시
•
교착상태 X
•
교착상태 O
◦
회복
▪
희생자 선정: 롤백 비용이 가장 적은 트랜잭션을 선택
•
연산을 수행한 시간과 남은 작업을 마치기 위한 시간
•
사용한 데이터와 트랜잭션 실행에 필요한 추가적인 데이터
•
롤백에 포함되는 트랜잭션 개수
▪
희생자 롤백: 어느시점까지 롤백할건지 결정
•
전체 롤백 VS 교착상태 해결 지점
•
모든 트랜잭션 상태에 대한 정보를 부가적으로 유지
▪
무한정 기다림 해결
•
같은 트랜잭션이 항상 희생자로 선정되지 않도록 희생자 선정 시 롤백 횟수 고려