동시성 제어

개념

1. 트랜잭션 직렬화와 회복하는 스케줄이 데터 일관성에 영향을 미치는 여부를 판별하고 일관성이 유지되는 상태로 복원시키기 위해 정의한 개념

2. 일관성 훼손을 발생시키는 트랜잭션에 대해 동시성 제어를 통해 일관성 유지에 개입

• 트랜잭션 간 연산의 순서를 제어
• 어떠한 데이터 읽기, 갱신 연산에도 무결성을 유지
• 동시에 실행되는 트랜잭션 수를 증가

3. 동시셍 제어 구약

• 락 기반 규약
• 타임스탬프 기반 규약
• 검증 기반 규약

---

락 기반 규약

1. 직렬 가능성을 보장하기 위해 락(잠금)을 사용하여 데이터 항목에 연산 적용 전 트랜잭션이 락(잠금)을 사용하여 데이터 항목에 연산 적용 전 트랜잭션이 락을 획득하고 연산 후 반납하도록 하는 규약
2. 락의 종류

• 공유 락(shared lock: S): 트랜잭션 T가 LS(Q) 명령으로 데이터 항목 Q에 공유 락을 획득하면 T는 Q를 읽을 수는 있지만 쓸 수는 없는 락
• 배타 락(exclusive lock: X): 트랜잭션 T가 LX(Q) 명령으로 데이터 항목 Q에 대한 배타 락을 획득하면, T가 Q를 읽고 쓸 수 있는 락

---

락 양립성

1. 트랜잭션은 연산하고자 하는 데이터에 대한 락을 획득해야만 연산 진행 가능
2. 락 양립성 함수

-	공유 락(S)	배타 락(X)
공유 락(S)	가능	불가능
배타 락(X)	불가능	가능

• 공유 락: 다른 공유 락과 양립 가능
• 배타 락: 다른 락과 양립 불가능
• 배타 락 요청은 공유 락 반납 시까지 대기
• 락의 반납은 UN() 명령 사용

---

동시실행 스케줄

---

락 반납이 지연된 스케줄

-> 일관성 유지 가능

---

락 반납 지연의 문제

---

2단계 락킹 규약(2PL)

---

타임스탬프 기반 규약

---

Tᵢ가 Read(Q)를 수행할 때

1. TS(Tᵢ) < W-TS(Q)이면 Read 연산이 거부되고 Tᵢ는 롤백
2. TS(Tᵢ) >= W-TS(Q)이면 Read 연산이 수행되고 R-TS(Q)는 기존 R-TS(Q)와 TS(Tᵢ)중 최대값으로 설정

---

Tᵢ가 Write(Q)를 수행할 때

1. TS(Tᵢ) < R-TS(Q) 또는 TS(Tᵢ) < W-TS(Q)이면 Write 연산이 거부되고 Tᵢ는 롤백
2. 그렇지 않으면 Write 연산을 수행하고 W-TS(Q)는 TS(Tᵢ)로 설정

---

타임스탬프 기반 규약의 적용

-> 문제없음

---

토마스 기록 규칙

1. TS(Tᵢ) < R-TS(Q)인 경우 Write 연산 거부 && Tᵢ는 롤백
2. TS(Tᵢ) < W-TS(Q)인 경우 Write 연산 거부
3. 아닌 경우 Write 연산 수행 && W-TS(Q)는 TS(Tᵢ)로 설정

---

교착상태

---

처리방법

1. 교착상태 발생이 비교적 높은 시스템의 경우

• 교상태 방지 규약 사용
• 모든 데이터 항목에 대해 락을 설정하는 기법
  - 단점1) : 트랜잭션이 시작되기 전에 어떤 데이터에 락을 걸어야 하는지 미리 알기가 어려움
  - 단점2): 락이 걸린 상태에서 많은 데이터들이 오랫동안 사용되지 않아 데이터 항목에 대한 이용률이 매우 낮아짐
• 타임스탬프를 이용한 선점유 기법

2. 교착상태 발생이 비교적 높지 않은 시스템의 경우

• 교착상태 탐지와 회복 기법 사용
  - 대기 그래프
  - 희생자 선정

---

교착상태 방지

---

교착상태 탐지와 회복

1. 교착상태 발생이 비교적 높지 않은 시스템의 경우 주기적으로 교착상태를 탐지하고 발생 시 회복절차를 수행
2. 탐지 및 회복 절차

• 트랜잭션이 할당된 데이터 항목과 현재 요청되고 있는 데이터 항목에 대한 정보를 유지
• 교착상태가 발생여부를 판별하기 위해 시스템의 상태를 검사하는 알고리즘을 주기적으로 수행
• 교착상태가 검출되면 시스템은 교착상태로부터 회복을 위한 절차를 수행

---

교착상태 탐지

1. 대기 그래프 (wait-for graph)를 이용하여 확인 가능

• 정점 V는 시스템 내의 트랜잭션으로 구성되며
• 간선 E는 트랜잭션의 순서쌍 (Tᵢ, T𝘫)으로 이루어짐
  - Tᵢ가 요청한 데이터의 락을 T𝘫가 소유하고 있으며,
  - Tᵢ는 T𝘫가 락을 반납하는 것을 대기하는 상태

2. 대기 그래프에 사이클이 있다면 교착 상태가 발생

---

교착상태 회복

1. 희생자 선정: 롤백 비용이 가장 적은 트랜잭션을 선택

• 연산을 수행한 시간과 남은 작업을 마치기 위한 시간
• 사용한 데이터와 트랜잭션 실행에 필요한 추가적인 데이터
• 롤백에 포함되는 트랜잭션의 개수

2. 희생자 롤백: 어느 시점까지 롤백할 것인지 결정

• 전체 롤백 vs 교착상태를 해결하는 지점
• 모든 트랜잭션의 상태에 대한 정보를 부가적으로 유지

3. 무한정 기다림 해결

• 같은 트랜잭션이 항상 희생자로 선정되지 않도록 희생자 선정시 롤백 횟수를 고려