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)방법은 트랜잭션이 시스템에 도착할 당시 논리적 카운터의 값이 된다. 카운터는 새 타임스탬프가 부여된 후에 증가 된다.
타임스탬프 프로토콜은 트랜잭션들이 서로 기다리는 일이 없기 때문에 교착 상태를 유발하지는 않는다.
'SW Engineering > OS Concept' 카테고리의 다른 글
25_메인 메모리(Main Memory) (1) | 2015.07.16 |
---|---|
24_교착 상태(Deadlock) (0) | 2015.07.16 |
22_원자적 트랜잭션 (Atomic Transaction) – 시스템 모델, 로그 기반 복구, 검사점 (2) | 2015.07.16 |
21_프로세스 모니터링 (0) | 2015.07.16 |
20_프로세스 임계 구역 (0) | 2015.07.16 |