23_원자적 트랜잭션 (Atomic Transaction) – 직렬화, 락킹 프로토콜, 타임스탬프 프로토콜

23_원자적 트랜잭션 (Atomic Transaction)

• 직렬가능성(Serializability), 락킹 프로토콜(Locking Protocol), 타임스탬프 기반 프로토콜(Timestamp Base Protocol)

 

 

직렬 가능성이란 임계구역 내에서 다수의 트랜잭션들이 동시 활성화 될 경우 각 트랜잭션들은 원자적이기 때문에 여러 트랜잭션들을 병렬로 수행시키면 그 결과는 이 모든 트랜잭션들을 어떤 임의의 순서에 따라 하나씩 차례로 순차적으로 실행되는 것을 말한다.

 

직렬 가능성으로 트랜잭션이 병렬로 수행되면 원자성이 보장되기는 하지만 비효율이 발생 하므로 몇 가지 동시성 제어 알고리즘(concurrency-control algorithm)이 직렬성을 유지하면서 트랜잭션 수행을 중첩 시킬 수 있다.

 

[직렬 가능성(Serializability)]

각 트랜잭션들이 원자적으로 수행되는 스케줄을 직렬 스케줄(Serialzability)이라 부른다. 직렬 스케줄은 여러 트랜잭션들의 명령어들의 순서로 구성되고 특정 트랜잭션에 속한 명령어들은 연속된 집합 형태로 나타난다.

T0	T1
Read(A)
Write(A)
Read(B)
Write(B)
	Read(A)
	Write(A)
	Read(B)
	Write(B)

 

N 개의 트랜잭션이 있다면 N! 개의 유효한(valid) 직렬 스케줄이 존재 한다. 각 트랜잭션들을 임의의 순서로 원자적으로 수행시키는 것과 동등하기 때문에 각 직렬 스케줄은 올바르다(correct)라 한다.

 

두 개의 트랜잭션이 중첩되게 실행시키면 그 결과는 더 이상 직렬 스케줄이 아니다. 비직렬 스케줄이 반드시 잘못된(incorrect) 스케줄은 아니다. 이 때는 충돌 연산(conflicting operation)을 정의해야 한다.

 

충돌 연산의 예를 들어 두 개의 트랜잭션T1, T2에 속한 연산 O1, O2 를 실행하는 스케줄 S가 있을 때 O1과 O2가 다른 트랜잭션에 속해 있으면서 O1과 O2가 서로 충돌하지 않는다면 우리는 O1과 O2의 순서를 바꾸어(swap) 새로운 스케줄 S'를 만들 수 있다. 이 때 S와 S'은 동등하다고 기대 할 수 있다. 왜냐하면 두 스케줄에서 O1과 O2를 제외한 나머지 연산들은 다 동일하며 O1과 O2도 비록 그 순서는 바뀌었지만 아무런 영향을 미치지 않기 때문이다.

정리하면 다음과 같은 표로 나타낼 수 있다.

T0	T1
Read(A)
Write(A)
	Read(A)
	Write(A)
Read(B)
Write(B)
	Read(B)
	Write(B)

 

스케줄 S에 있는 비충돌 연산들을 스왑 시켜줌으로써 직렬 스케줄로 변환시켜 줄 수 있다면 [S가 충돌 직렬가능(conflict serialzable)하다] 라고 표현 한다.

 

 

[락킹 프로토콜(Locking Protocol)]

직렬 가능성을 보장하는 한 가지 방법은 각 자료 항목마다 락을 두고 각 트랜잭션이 일정한 락킹 프로토콜에 맞추어 락을 획득하고 반납하도록 규정하는 것이다.

• 공유(Shared) : 트랜잭션 T1이 자료 항목 Q에 대한 공유 모드(shared mode) 락(S)을 가지고 있으며 T1은 Q를 읽을 수 있지만 Q에 쓸 수는 없다.
• 독점(Exclusive) : 트랜잭션 T1가 자료 항목 Q에 대한 독점 모드(exclusive mode) 락(X)을 가지고 있으며 T1는 Q에 읽기와 쓰기를 모두 할 수 있다.

 

트랜잭션은 이전에 락을 걸었던 자료 항목에 대해서는 락을 해제할 수 있다. 그렇지만 그 자료 항목을 접근하는 기간 동안에는 계속 락을 유지하여야 한다.

자료 항목에 대한 마지막 접근이 끝난 직후 바로 락을 해제하는 것은 직렬 가능성이 보장되지 않을 수 있기 때문에 바람직 하지 않을 수 있다.

 

두 단계 락킹 프로토콜(tow phase locking protocol)은 직렬 가능성을 보장해 주는 프로토콜의 하나이다. 이 프로토콜은 락과 언락을 두 단계로 수행 할 것을 요구 한다.

• 확장 단계(Growing phase) : 트랜잭션은 락을 새로 얻을 수 있지만 얻었던 락을 반납해서는 안된다.
• 수축 된다(shrinking phase) : 트랜잭션은 얻었던 락을 반납할 수는 있지만 새로운 락을 얻어서는 안된다.

 

트랜잭션은 최초에는 확장 단계에서 시작하며 필요한 만큼 락을 확보 한다. 그러나 트랜잭션이 일단 한 개의 락을 해제하기 시작하면 수축 단계로 들어가며 기 이후부터는 새로운 락을 획득 해서는 안된다.

 

두 단계 락킹 프로토콜은 충돌 직렬가능성을 보장한다. 그러나 교착 상태 문제가 발생 할 수 있다.

 

[타임 스탬프 기반 프로토콜(timestamp based protocol)]

트랜잭션 충돌을 위해 직렬 가능한 순서를 정하는데 가장 많이 사용하는 방법이 타임 스탬프 순서 기법이다. 시스템의 각 트랜잭션마다 고유한 고정 타임스탬프를 부여한다.

타임 스탬프가 직렬 가능성을 보장하기 때문에 TS1 < TS2 라면 시스템은 T1을 처리한 후 T2를 처리하여 직렬 스케줄과 동등하도록 보장한다.

 

• 시스템 클록(system clock)방법은 이 트랜잭션이 시스템에 도착할 당시 클록의 값이 된다. 이 방법은 별도의 시스템에서 수행되거나 두 처리가 클록을 공유하지 않는 환경에서는 사용할 수 없다.
• 논리적 카운터(logincal counter)방법은 트랜잭션이 시스템에 도착할 당시 논리적 카운터의 값이 된다. 카운터는 새 타임스탬프가 부여된 후에 증가 된다.

 

타임스탬프 프로토콜은 트랜잭션들이 서로 기다리는 일이 없기 때문에 교착 상태를 유발하지는 않는다.