잠금(Lock)
태그 :
- 개념
- - 트랜잭션이 사용하는 자원 (데이터 항목)에 대하여 상호 배제 (Mutual Exclusive) 기능을 제공하는 기법 - 상호 배제는 특정 트랜잭션이 데이터 항목에 대하여 잠금 (Lock) 을 설정하면, 잠금을 설정한 트랜잭션이 해제 (Unlock) 할 때까지 데이터를 독점적으로 사용할 수 있는 것
1. 동시성제어를 위한 Locking 기법의 개요
가. Locking 기법의 정의
-트랜잭션이 사용하는 자원 (데이터 항목)에 대하여 상호 배제 (Mutual Exclusive) 기능을 제공하는 기법
-상호 배제는 특정 트랜잭션이 데이터 항목에 대하여 잠금 (Lock) 을 설정하면, 잠금을 설정한 트랜잭션이 해제 (Unlock) 할 때까지 데이터를 독점적으로 사용할 수 있는 것
나. Locking 연산의 종류(일반적인 DBMS 모두 지원)
종류 |
주요 개념 |
공유 Lock (Shared Lock) |
- 공유 잠금한 트랜잭션은 데이터 항목에 대해 읽기(read)만 가능 - 다른 트랜잭션도 읽기(read) 만을 실행할 수 있는 형태 |
전용 Lock (Exclusive Lock)
|
- 전용 잠금한 트랜잭션은 데이터 항목에 대해서 읽기(read)와 기록(write)가 모두 가능 - 다른 트랜잭션은 읽기(read)와 기록(Write) 모두 할 수 없는 형태 |
- S-lock간에는 동시 잠금이 허용, 나머지 경우에는 동시 잠금이 허용되지 않음
다. Locking 기법 실행
1) 트랜잭션 T가 read(x)나 write(x) 연산을 하려면 반드시 먼저 lock(x) 연산을 실행해야 함
2) 트랜잭션 T가 실행한 lock(x)에 대해서는 T가 실행을 종료하기 전에 반드시 unlock(x) 연산을 실행해야 함
3) 트랜잭션 T는 다른 트랜잭션에 의해 이미 lock이 걸려 있는 x에 대해 다시 lock(x)를 실행시키지 못 함
4) 트랜잭션 T는 x에 lock을 자기가 걸어 놓지 않았다면 unlock(x)를 실행시키지 못 함
2. Locking 기법의 규칙
가. 잠금(Locking) 규칙
- 트랜잭션 데이터 항목 x에 대해서는 다음 규칙을 준수해야 함.
- 잠금 설정만으로는 직렬 가능한 스케줄이 보장되지 않음, 추가적 제약 필요
조건 |
예시 |
- read(x) 연산을 실행하기 전에 S-lock(x)나 X-lock(x)를 실행 |
S-lock(A) Read(A) Unlock(A) x-lock(A) read(B) B=B+A Write(B) Unlock(B) |
- write(x) 연산을 실행하기 전에 X-lock(x)를 실행해야 함 |
|
- read(x)나 write(x) 연산을 실행이 끝나면 unlock(x) 실행 |
|
- S-lock(x)나 X-lock(x)를 실행한 경우만 unlock(x) 실행가능 |
나. Locking 단위
- Locking 단위가 클수록 병행성 수준 떨어지고, 병행제어기법 간단해짐
- Locking 단위가 작을수록 병행성 수준 높아지고, 관리 복잡해짐
다. 트랜잭션이 어느 한 데이터 아이템의 마지막 접근이 끝나자마자 unlock을 실행하는 것은 바람직하지 않음
3. 동시성 제어를 위한 타임스탬프 순서 기법의 개요
가. 타임스탬프 순서 기법(Timestamp ordering method)의 정의
- 트랜잭션을 식별하기 위해 DBMS가 부여하는 유일한 식별자인 타임 스탬프를 지정하여 트랜잭션간의 순서를 미리 선택
- 데이터베이스 시스템에 들어오는 트랜잭션 순서대로 타임 스탬프를 지정하여 동시성 제어의 기준으로 사용
나. 타임스탬프 순서 기법의 장단점
구분 |
내용 |
|
장점 |
직렬 가능 (Serializable) |
상충되는 연산들이 타임 스탬프 순서로 처리됨으로 직렬성(Serializability) 보장 ※직렬가능(Serializable) : N개의 트랜잭션에 대한 비직렬 스케줄이 직렬 스케줄과 동일한 결과 |
교착상태 (Deadlock)방지 |
트랜잭션이 결코 기다리는 경우가 없으므로 교착상태 (Deadlock) 를 방지할 수 있음 |
|
단점 |
연쇄복귀 (Cascading Rollback) 발생 |
하나의 트랜잭션 복귀(Rollback) 시 이후에 시작된 다른 트랜잭션의 복귀를 유발하여 연쇄복귀를 초래할 수 있음 |
기아(Starvation) 발생 |
동일한 트랜잭션이 여러 번 철회 될 수 있음 |
※ 기아(Starvation) 발생해결(Aging 기법 사용)
트랜잭션이 복귀(Rollback) 될 때 이전과 동일한 타임스탬프를 사용하여
트랜잭션의 우선순위를 높여줌으로 기아 발생 방지 가능
4. 타임스탬프기법의 순서 알고리즘 및 유형
가. 타임스탬프 순서 알고리즘
직렬성을 유지하기 위해 다음과 같은 두 개의 Timestamp 유지.
1) read_TS(X):
- 항목 X의 읽기 타임스탬프(read timestamp)로서 항목 X를 성공적으로 읽은 트랜잭션들의 타임스탬프 중 가장 큰 값.
2) write_TS(X)
- 항목 X의 쓰기 타임스탬프(write timestamp)로서 항목 X를 성공적으로 기록한 트랜잭션들의 타임스탬프 중 가장 큰 값
나. 기본적 타임스탬프 순서(Basic Timestamp Ordering)
1) Ti가 read(x)를 수행 시 - TS(Ti) < write-TS(x)이면 read(x)를 취소하고 Ti는 복귀(Rollback) - TS(Ti) ≥ write-TS(x)이면 read(x)를 수행한 후, read_TS(x)가 TS(Ti) 보 다 작으면 갱신 2) Ti가 write(x)를 수행하려 할 때 - TS(Ti) < read-TS(x) 이거나 TS(Ti) < write-TS(x) 이면 write(x)를 취소하고 Ti는 복귀(Rollback) -이외의 경우는 write(x)를 수행한 후, write_TS(x)를 갱신 |
참고> Thomas 쓰기 규칙에서는 불필요한 write 연산을 무시하여,
TS(Ti) < write-TS(x)인 경우 write연산을 수행하지 않고 Ti 계속 수행 가능
다. 타임스탬프기법의 유형
구분 |
내용 |
시스템 시계 (System Clock)사용 |
- 시스템 시계 값을 타임스탬프 값으로 부여 - 트랜잭션이 시스템에 진입할 때의 시계 값과 동일 |
논리적 계수기 (Logical counter) 사용 |
- 트랜잭션이 발생할 때마다 카운터를 하나씩 증가시켜 타임스탬프 값으로 부여 |
5. Timestamp 기법과 Locking(2PL), Validation 기법의 비교
구분 |
Locking(2PL) |
Validation |
Timestamp |
직렬성 (Serializability) |
O (Lock point 순서) |
O (Validation순서) |
O (타임스탬프순서) |
교착상태 (Deadlock) 방지 |
X |
O (기다리지 않고 Rollback) |
O (기다리지 않고 Rollback) |
기아(Starvation) 방지 |
O |
X |
X |
회복/비연쇄 복귀가능 |
X |
O (트랜잭션 완료 후 DB에 반영) |
X |
<참고>
※ Timestamp 기법을 이용한 Deadlock 방지 방법
가. Wait-die Algorithm
나중에 시작된 프로세스가 먼저 시작된 프로세스가 점유한 자원 요청 시
복귀(rollback)되거나 종료(die)
1) 상황 1 - 고참 프로세스(Older Process)가 신참 프로세스(Younger
Process)가 점유한 자원을 요청 시, 고참 프로세스가
기다림(wait)
2) 상황 2 - 신참 프로세스가 고참 프로세스가 점유한 자원을 요청 시,
신참 프로세스는 die)
나. Wound-Wait Algorithm
먼저 시작된 프로세스가 나중에 시작된 프로세스의 자원을 선점(preempt) 가능 (나중에 시작된 프로세스를 killing 또는 wounding)
상황 1 - 고참 프로세스(Older Process)가 신참 프로세스(Younger Process)가 점유한 자원을 요청 시, 신참 프로세스를 wound(or killed) 하여 자원 선점(preempted)
상황 2 - 신참 프로세스(Younger Process)가 고참 프로세스(Older Process)가 점유한 자원을 요청 시, 신참 프로세스는 기다림(Wait)