동시성 제어

1. lock 기반 규약

고립성을 보장하기 위한 한 가지 방법은 데이터 항목들이 상호 배타적으로 액세스되도록 하는 것이다. 즉, 한 트랜잭션이 하나의 데이터 항목을 액세스했을 때는 다른 트랜잭션이 동일한 데이터 항목에 대해 갱신 작업을 할 수 없도록 하는 것이다. 이 기법을 구현하기 위해 가장 일반적으로 사용되는 방법은 데이터 항목에 lock을 가지고 있는 트랜잭션만이 그 데이터 항목에 액세스할 수 있도록 하는 것이다.

1) lock

데이터 항목에 여러 가지 모드로 lock을 걸 수 있다. 이번 절에서는 두 가지 모드에 대해 살펴본다.

1. 공유(shared) lock 모드 : 트랜잭션 $T_{i}$가 데이터 항목 Q에 공유 모드의 lock(S로 표기)을 가지고 있다면 $T_{i}$는 Q를 읽을 수는 있지만 Q를 갱신할 수는 없다.
2. 독점적(exclusive) lock 모드 : 트랜잭션 $T_{i}$가 데이터 항목 Q에 대해 독점적 모드의 lock(X로 표기)을 가지고 있다면 $T_{i}$는 Q를 읽을 수도 있고 갱신할 수도 있다.

모든 트랜잭션은 데이터 항목 Q에 어떤 연산을 수행할지에 따라 적절한 모드의 lock을 동시성 제어 관리 모듈에게 요청(request)해야 한다. 이 요청에 따라 동시성 제어 관리 모듈이 해당 트랜잭션에게 요청한 lock을 허용(grant)해주었을 때 트랜잭션은 자신의 연산을 계속 진행할 수 있다. 이러한 두 개의 lock 모드는 다수의 트랜잭션들이 데이터 아이템을 읽게 하면서도 한 번에 하나의 트랜잭션에만 쓰기 접근을 제한하도록 해준다.

공유 모드의 lock은 공유 모드의 lock과는 호환성을 가지지만 독점적 모드의 lock과는 호환성을 가지지 않는다. 여기서 호환(compatible)된다는 것은 어떤 트랜잭션 $T_{i}$가 모드 B의 lock을 가지고 있는 상태에서 $T_{j}$가 모드 A lock을 얻을 수 있는 경우를 말한다. 어느 때라도 특정 항목에 서로 다른 트랜잭션들에 의해 여러 개의 공유 모드 lock이 존재할 수 있기 때문에 독점적 모드의 lock을 걸기 위해서는 현재 걸려있는 공유 모드의 lock들이 모두 해제될 때까지 기다리고 있어야 한다.

데이터 항목에 액세스 하기 위해 트랜잭션 $T_{i}$는 반드시 먼저 그 항목에 lock을 걸어야 한다. 만약 이미 다른 트랜잭션에 의해 그 항목에 호환되지 않는 모드의 lock이 걸려있다면 그 모든 비호환적인 lock이 해제될 때까지 동시성 제어 관리 모듈은 $T_{i}$의 lock 요청을 허용하지 않게 된다. 그러므로 $T_{i}$는 이 모든 lock이 해제될 때까지 대기상태로 존재한다.

트랜잭션이 데이터 항목을 마지막으로 액세스한 다음 바로 그 항목에 걸린 lock을 해제하는 것이 바람직하지 못한 경우도 있는데, 직렬성이 보장되지 않을 수도 있기 때문이다. 다음의 예를 보자.

A와 B를 트랜잭션 $T_{1}$과 $T_{2}$에 의해 액세스되는 두 계좌라고 하고 트랜잭션 $T_{1}$이 계좌 B에서 $50를 계좌 A로 이체하려고 한다. 트랜잭션 $T_{2}$는 계좌 A와 B의 합한 잔고, 즉 A+B를 보여준다.

계좌 A와 B에 각각 $100와 $200의 잔고가 있다고 하자. 만일 이 트랜잭션들이 순차적으로 수행된다면 $T_{2}$는 $300이라는 값을 보여줄 것이다. 그러나 만약 이들 트랜잭션들이 아래 그림 18.4에 나와있는 스케줄대로 동시에 실행될 경우, 트랜잭션 $T_{2}$는 잘못된 값인 $250를 보여줄 것이다. 이러한 오류가 발생하는 이유는 트랜잭션 $T_{1}$이 너무 일찍 lock 해제를 하는 바람에 트랜잭션 $T_{2}$가 비일관성 상태의 데이터를 액세스했기 때문이다.

교착상태

그림 18.7에서 트랜잭션 $T_{3}$과 $T_{4}$의 부분적인 스케줄을 살펴보자. $T_{3}$이 B에 대해 독점적 모드의 lock을 가지고 있으므로 $T_{4}$가 이 B에 공유모드의 lock을 요청해도 $T_{3}$이 B에 대한 lock을 해제할 때까지 기다리고 있어야 한다. 마찬가지로 $T_{4}$가 이미 A에 대한 공유 모드의 lock을 가지고 있기 때문에 $T_{3}$이 A에 독점적 모드의 lock을 요청해도 $T_{4}$가 A에 대한 lock을 해제할 때까지는 계속 기다리고 있어야 한다. 결국 이 두 트랜잭션은 더 이상 정상적인 수행을 하지 못하고 계속해서 자신들이 요청한 lock이 얻어질 때까지 기다리게 된다. 이러한 상태를 교착(deadlock) 상태라고 부른다. 교착 상태가 발생하면 반드시 시스템은 두 트랜잭션 중 하나를 취소해야 한다. 일단 트랜잭션이 취소되면 그 트랜잭션이 가지고 있던 모든 lock이 해제되기 때문에 다른 트랜잭션이 lock이 해제된 데이터 항목에 대해 lock을 얻을 수 있고 결국 다음 연산 실행을 계속할 수 있게 된다.

locking protocol

시스템 내의 각 트랜잭션은 locking protocol이라고 불리는 일련의 규칙을 따를 필요가 있다. 이 locking protocol은 트랜잭션이 데이터 항목에 언제 lock을 걸고 해제할 수 있는지를 알려준다. 그리고 locking protocol은 트랜잭션들의 실행 스케줄 수를 제한한다. 여기서는 충돌 직렬성을 갖는 스케줄만을 허용하는 몇 가지 locking protocol들을 다룰 것이다.

{$T_{0}$, $T_{1}$,...,$T_{n}$}을 스케줄 S에 포함된 일련의 트랜잭션들이라고 하자. 트랜잭션 $T_{i}$이 데이터 항목 Q에 모드 A의 lock을 가지고 다시 트랜잭션 $T_{j}$가 데이터 항목 Q에 모드 B의 lock을 가지면서 comp(A, B)=false인 데이터 항목 Q가 있을 경우, 스케줄 S에서 $T_{i}$가 $T_{j}$를 앞선다고 하고 $T_{i} \rightarrow T_{j}$로 표기한다. $T_{i} \rightarrow T_{j}$의 경우 $T_{i}$가 $T_{j}$를 앞선다는 것은 동등한 연산 순서를 가지는 모든 스케줄에서 $T_{i}$가 반드시 $T_{j}$보다 먼저 있어야 한다는 것이다.

만일 스케줄 S가 locking protocol의 규칙을 따르는 일련의 트랜잭션들의 스케줄이라면 주어진 locking protocol 하에서 S는 정당하다(legal)고 말할 수 있다. 그리고 모든 정당한 스케줄들이 충돌 직렬성을 가진다면, locking protocol이 충돌 직렬성을 보장한다(ensure)고 말할 수 있다.

2) lock의 허용

트랜잭션 $T_{2}$가 하나의 데이터 항목에 공유 모드의 lock을 가지고 있고 또 다른 트랜잭션 $T_{1}$이 그 데이터 항목에 대해 독점적 모드의 lock을 요청했다고 하자. $T_{1}$은 $T_{2}$가 공유 모드 lock을 해제할 때까지 기다려야 한다. 이때 트랜잭션 $T_{3}$가 같은 데이터 항목에 대해 공유 모드의 lock을 요청할 수 있다. $T_{3}$가 요청한 lock 모드는 $T_{2}$가 가지는 lock 모드와 호환성이 있기 때문에 $T_{3}$도 같은 데이터 항목에 대해 공유 모드의 lock을 허용 받게 된다. 이런 식으로 계속 공유 모드의 lock을 허용하다보면 $T_{1}$은 독점적 모드의 lock을 허용 받기가 어려워진다. 그러므로 $T_{1}$은 더이상 진행하지 못하고 결국에는 기아(starvation) 상태에 빠지게 된다.

그러나 다음과 같은 방법으로 lock을 허용하면 트랜잭션의 기아를 회피할 수 있다. 트랜잭션 $T_{i}$가 특정 모드 M으로 데이터 항목 Q에 lock을 요청할 경우 동시성 제어 관리 모듈은 다음 두 가지 경우에 한해 lock을 허용해준다.

1. M과 충동되는 lock 모드로 Q에 lock을 걸고 있는 다른 트랜잭션들이 없다.
2. $T_{1}$보다 먼저 Q에 lock을 요청해서 기다리고 있는 트랜잭션이 없다.

이렇게 하면 현재의 lock 요청이 나중에 들어올 lock 요청에 의해 블록되는 경우는 발생하지 않는다.