Lock-based Protocols

Lock-based Protocols

lock 이란 data item 에 동시 접근하는 것을 통제하기 위한 메커니즘이다.

data item 은 두 가지 모드로 lock 될 수 있다.

- exclusive (X) mode : 읽기/쓰기 모두 가능한 lock
- shared (S) mode : 읽기만 가능한 lock

모두 S-lock인 경우에만 서로 다른 트랜잭션이 동시에 락을 얻을 수 있다.

 

트랜잭션은 요청이 승인된 후에만 실행될 수 있다.

즉, 트랜잭션이 어떤 item 에 대해 요청한 lock 이, 이미 그 아이템에 다른 트랜잭션에 의해 걸려있는 lock 과 compatible 하다면 승인될 것이다.

• 얼마든지 많은 트랜잭션은 item 에 대해 shared lock을 hold할 수 있다.
• 다만, 어떤 트랜잭션이 item 에 대해 exclusive lock (X) 을 갖고 있다면 그 어떤 트랜잭션도 그 item 에 대해 어떤 lock 도 가질 수 없을 것이다.

-> 만약 서로 incompatible 한 락을 요청하여 lock 요청이 승인되지 않는 경우라면, 그 item 에 대해 먼저 lock 소유한 트랜잭션이 해당 lock 을 release 할때까지 대기해야 한다. 그러면 lock 을 얻을 수 있다.

위와 같은 순서로 연산이 실행된다고 하자. 이러한 방식은 serializability 를 보장하지 않는다.

read(A), read(B), display(A+B) 연산 사이에 A, B 가 업데이트될 경우 read(A), read(B), display(A+B) 의 값도 바뀔 것이기 때문이다.

 

Two-phase Locking Protocol 

- Phase1 : growing phase

Lock을 수행할 수는 있지만 풀 수는 없다.

- Phase2 : shrinking phase

Lock을 수행할 수는 없지만 풀 수는 있다. 

- Lock points

트랜잭션 내에서 가장 마지막에 lock을 획득한 순간

 

-> 이러한 프로토콜은 serializability 를 보장한다. 트랜잭션은 lock point 의 순서에 따라 serialized 되기 때문이다.

 

Cascadinig rollback 이 일어날 수 있다.

- 이를 방지하기 위해선, strict two-phase locking 이라 불리는 변형된 프로토콜을 사용해야 한다.
이 프로토콜은 트랜잭션이 commit/abort 를 할 때까지 exclusive lock (X-lock) 을 풀지않고 갖고 있어야 한다.

- Rigorous two-phase locking 프로토콜은 X-lock 뿐만 아니라 S-lock 도 commit/abort 를 할 때까지 풀지않고 갖고 있어야 한다. 이 프로토콜이 주로 사용됨

Two-phase locking 은 deadlock 이 발생할 수 있다. 

 

Lock Conversions

- Phase1

S/X lock 을 얻을 수 있다.

S-lock 을 X-lock 으로 업그레이드 가능하다. 

- Phase2

S/X lock 을 release 할 수 있다.

X-lock 을 S-lock 으로 다운그레이드 가능하다. 

 

Two-phase Locking Protocol 이 conflict serializability 를 보장하는 이유

2PL 이 conflict serializability 를 보장하지 않는다고 가정해보자.

2PL을 만족하는 non-serializable 한 schedule T0, T1, ... , Tn 이 존재한다고 하자.

non-serializable schedule 은  precedence graph에서 사이클이 존재할 것이다.

그 사이클을 T0-> T1 -> … -> Tn -> T0 이라고 하자.

그리고 Ti의 lock을 마지막으로 얻은 시점인 lock point 를 ai 라고 하자.

그렇다면 모든 트랜잭션 Ti -> Tj 에 대해서 ai < aj 가 성립하며,  (lock 을 풀어야지만 다음 트랜잭션을 수행할 수 있으므로 ai 는 항상 aj 보다 앞선다. )

사이클 T0 -> T1 -> … -> Tn -> T0 는 a0 < a1 < … < an < a0 을 만족해야한다.

이때 a0 < a0 은 모순이므로, 따라서 사이클이 존재하지 않는다는 것이 증명되었다. 

즉, 2PL 은 non-serializable schedule 을 생성할 수 없다.

 

Automatic Acquisition of Locks

트랜잭션은 명시적인 locking call 을 할 필요가 없다. -> read/write 명령 전에 자동으로 lock 이 실행된다.

어떤 트랜잭션이 D 를 read 하고자 하면 다음과 같이 처리된다.

어떤 트랜잭션이 D 를 write 하고자 하면 다음과 같이 처리된다.

 

Implementation of Locking

Lock-Manager 라는 독립된 프로세스를 통해 구현하며, 트랜잭션은 lock manager에게 lock / unlock 요청을 보낸다.

트랜잭션이 lock을 요청하고 lock manager 에게 응답이 올 때까지 기다린다.

- lock manager 은 lock 을 승인하는 메세지를 보내거나, deadlock 이 발생했을 때는 roll back 을 해라고 메세지를 보낸다.
- lock manager 은 승인된 lock 과 보류중인 요청을 저장하는 lock table 이라는 data structure 을 가지고 있다.
- lock table 은 보통 hash table 로 구현이 된다. 

 

Lock Table

 

 

만약 T23 트랜잭션이 abort 된다면, 트랜잭션이 가지고 있거나 기다리고 있는 모든 lock 을 해제시켜주어야한다.

이를 위해서 각 트랜잭션이 가지고 있는 lock 을 linked-list 로 구현한다.

 

Deadlock

T3 은 Lock-X(A) 를 얻기 위해 T4 가 Lock-S(A) 를 release 하기를 대기하고 있고,

T4 는 Lock-S(B) 를 얻기 위해 T3 이 Lock-X(B) 를 release 하기를 대기하고 있다.

이처럼 T3 과 T4 모두 더 이상 실행하지 못하는 상황을 deadlock 이라고 한다.

 

Starvation

특정 트랜잭션이 이 반복적으로 roll back 되거나 lock 을 아예 얻지 못하는 현상이다.

-> 우리는 데드락 현상은 피할 수 없지만 기아현상은 피할 수 있다.

 

Graph-based Protocol

two-phase locking 의 대안으로 나온 프로토콜이다.

D = {d1, d2, …, dn} 이라는  모든 data item 의 집합에 대해 순서 -> 가 존재한다.

- di -> dj 라면, 어떤 트랜잭션이라도 dj 에 접근하기 전에 di 에 먼저 접근해야 한다.
- 이러한 집합 D 는 directed acyclic graph 이며 이를 데이터베이스 그래프라고 부른다.

-> tree 기반의 프로토콜에 주로 사용됨

 

Tree-based Protocol

오직 X-lock 만 허용되며, Ti 가 데이터 Q에 대해서 lock을 걸려면 반드시 Ti가 Q의 부모에 대한 락을 갖고 있어야한다.

언제든지 lock을 얻고, 풀 수 있다.

어떤 데이터 item 이 Ti 에 의해 한 번 lock 이 걸렸거나 풀렸다면, Ti 에 의해 다시 lock 이 걸릴 수는 없다.

 

ex)

-> T1 에서 unlock(B) , unlock(D) 다음에 unlock(C) 를 하지 못하는 이유는, 그 다음에 lock-X(E) 를 얻기 위함 때문이다.

 

Graph-Based Protocol

장점

Tree protocol 은 conflict serializability 를 보장하며 deadlock 에 걸릴 일이 없다.

-> 반드시 부모의 lock이 있어야하고, tree는 cycle 이 존재하지 않는 단방향이기 때문이다.

 

단점

recoverability와 cascade rollback 을 보장하지 않는다. 

굳이 접근하지 않아도 되는 데이터(Parent) 에 대해 락을 얻어야하므로 locking overhead 가 크고, waiting time 이 증가하고 concurrency 가 감소한다.

 

2PL에서 불가능한 스케줄이 트리 기반에서 가능하며, 이 역도 가능하다.