잠금(Lock)

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)