병행제어

○ 병행제어(Concurrent Control)

   - 병행제어 실패시에는 갱신분실(Lost Update), 모순성(Inconsistency), 회복불능/연쇄복귀(Cascade Rollback)가 발생함.

Binary Lock	Shared Lock, Exclusive Lock	Optimistic Concurrnecy Control  확인기법(Validation Schema)
° Lock이 걸린 상태와 해제된 상태의 두 가지 값을 가짐	° Data에 접근전에 Locking 연산 수행 ° 다른 Transaction은 대기	° 트랜잭션이 수행되는 동안 어떠한 검사도 하지 않음 ° 트랜잭션의 수행 마지막에 갱신 사항들이 직렬가능성을 위반하는지 검증
° Lock과 Unlock는 나누어질 수 없는 단위로 구현되어야 함	° 공용 Lock   - Data 읽기 가능, 기록 불가   - 다른 Transaction이 공용 Lock 가능 ° 전용 Lock   - Data 읽기, 쓰기 가능   - 다른 Transaction이 어떤 Lock도 불가 ° 직렬가능성 보장 안됨 ° DeadLock 발생 가능	° 3단계 - 읽기단계(Read Phase) - 검증단계(Validation Phase) - 쓰기단계(Write Phase) ° 직렬성이 보장되면 실제 DB에 반영 ° 연쇄복귀 없고 회복 가능함 ° 트랜잭션들 사이에 거의 방해가 일어나지 않는 상황에 적합

2 Phase Locking	TimeStamping
° 모든 Transaction의 Lock과 Unlock 연산을 2단계로 구분	° 시스템에서 생성하는 고유번호인 Timestamp를 Transaction에 부여하여 동시성 제어의 기준으로 사용
° 1단계(확장단계)   - Transaction은 Lock만 수행 가능   - Unlock은 수행할 수 없는 단계 ° 2단계(축소단계)   - Transaction은 Unlock만 수행 가능   - Lock은 수행할 수 없는 단계 ° 직렬가능성을 보장하는 Protocol Conservative 2PL ° read set, write set을 미리 선언 ° transaction 실행 전에 모든 항목에 Lock 연산 ° DeadLock free protocol Strict 2PL ° 모든 write lock을 트랜잭션 종료시까지 유지 ° 연쇄복귀를 피할 수 있으나 Deadlock위험 Rigorous 2PL ° 모든 lock를 트랜잭션 종료시까지 유지 ° 모든 트랜잭션을 완료하는 순서로 직렬화 가능	° 시스템 시계, 논리적 계수기 사용 ° 순서규약 - Ti가 read(x) 수행시,   ① TS(Ti) ≥ write-TS(x)이면 실행   ② 아니면 read(x)를 거부하고는 복귀됨 - Ti가 write(x) 수행시,   ① TS(Ti) ≥ read-TS(x)이고 TS(Ti) ≥ write-TS(x)이면 실행   ② TS(Ti) < read-TS(x)이면 거부하고 복귀됨   ③ TS(Ti) < write-TS(x)이면 거부하고 복귀됨 ° Tomas 기록규칙 - Ti가 write(x) 수행시,   ① TS(Ti) ≥ read-TS(x)이고 TS(Ti) ≥ write-TS(x)이면 실행   ② TS(Ti) < read-TS(x)이면 거부하고 복귀됨 ③ TS(Ti) < write-TS(x)이면 Ti를 단순무시 ° 직렬성을 보장함 ° 교착상태(Deadlock)를 방지함 ° 연쇄복귀를 초래 및 순환적 재시작(Starvation 문제) ※ 연쇄복귀 : 어떤 트랜잭션이 복귀됨에 따라 그 트랜잭션이 변경한 데이터 항목값을 읽은 다른 트랜잭션이 연쇄적으로 복귀되는 현상

다중버전 타임스탬프	다중버전 2PL
° 데이터 아이템 x에 대해 여러 버전<X1, X2, ..., Xn>을 유지	° 각 항목 X에 대해 두개의 버전을 유지 ° 하나의 버전은 항상 완료된 트랜잭션이 쓰기를 수행한 것 ° 두 번째 버전은 트랜잭션이 항목 X에 대해 write-lock를 획득할 때 생성됨
° 각 버전 Xk의 값과 write-TS(Xk), read-TS(Xk) timestamp 저장 ° 규약 - Ti가 read(x) 수행시,   ① Xk값을 반환 TS(Ti) > read-TS(Xk)이면 read-TS(Xk) 갱신 - Ti가 write(x) 수행시,   ① TS(Ti) ≥ read-TS(Xk)이면 새버전의 Xm+1을 생성하고 read-TS(Xm+1) = write-TS(Xm+1) = TS(Ti)로 설정 ° 연쇄복귀 가능성 ° read연산 결코 실패하지 않음 ° read시마다 read-TS갱신을 위해 두 번의 디스크 접근이 필요	° read-lock, write-lock, certify-lock, unlock로 구성 ° 트랜잭션 T가 완료시에 write-lock를 보유하고 있는 모든 항목에 대해 certify-lock를 획득해야하며 certify-lock은 첫 번째 버전을 읽고 있는 다른 트랜잭션의 모든 lock가 해제될 때 까지 T의 완료가 지연됨 ° 연쇄복귀가 없고 회복가능함

다단계 로킹(Multigranularity)	※ Phantom Conflict ※ 트랜잭션 복귀비용 고려요소 ① 복귀에 포함되는 트랜잭션의 개수 ② 트랜잭션이 사용한 데이터 항목의 개수 ③ 트랜잭션을 마칠 때까지 필요한 데이터 항목의 개수 ④ 트랜잭션이 수행한 시간과 수행해야할 시간 정의 ° 실제 DB에 저장된 튜플이 아니라 장래에 DB에 삽입되어질 튜플에 대해 T1,T2가 충돌하는 것 해결책 ° Lock단위를 크게 함(릴레이션 단위) ° 인덱스 locking 기법 - 인덱스가 있다는 것을 이용하여 Phantom Conflict를 인덱스 버킷에 대한 충돌로서 해결하는 방법
° 몇 개의 데이터 아이템을 그룹지어 이것을 하나의 단위로 묶어 하나의 단위로 취급하는 계층트리를 만들어, 불필요한 lock/unlock연산을 줄여 효율을 높이는 방법
° 다단계 lock를 지원하기 위해 데이터 레코드들을 여러 유형의 논리적 크기로 정의하며 개별적으로 lock가능함 ° 의도락(Intention Lock) - 특정 노드에 의도락을 걸면 자손노드 중에 명시적 lock이 걸려있음을 나타냄 - 원하는 목표 노드에 명시적 lock을 걸기 위해서는 해당 노드의 모든 선조들에게 의도락을 건다 - 종류 : IX, IS, SIX