프로세스 동기화(Process Synchronization)

6. 프로세스 동기화(Process Synchronization)

▶ 협력 프로세스(cooperating processes)

- 논리 주소 공간(코드와 데이터)을 공유하거나: ‘스레드’(4.5절 참조)에 의해 수행가능

- 파일에 의해 데이터를 공유함

→ 공유 데이터에 대한 동시 접근은 데이터의 불일치를 유발할 수 있음

6.1 배경(Background)

▶ 유한 버퍼 문제의 공유기억장치 해결책

1) 두 개의 포인터 in과 out을 사용하는 원형 배열(circular array)로 구현하는 방법: 4.4절 참조

→ 단점: 동시에 채워질 수 있는 버퍼의 개수가 최대 n-1개임

2) 변수 counter를 추가하는 방법: p.170의 알고리즘

- 초기화: counter = 0

- 저장소에 버퍼를 추가할 때마다, counter를 1씩 증가

- 저장소에서 버퍼를 빼낼 때마다, counter를 1씩 감소

▶ 생산자와 소비자 루틴이 개별적으로는 정확할지라도, 동시에 실행시키면 잘못 동작할 수 있음

- 기계어 수준 코드

① register1 := counter;

(생산자) counter := counter + 1; → ② register1 := register1 + 1;

③ counter = register1;

① register2 := counter;

(소비자) counter := counter - 1; → ② register2 := register2 - 1;

③ counter = register2;

  이때, register1과 register2가 동일한 레지스터이더라도 이 레지스터의 내용은 인터럽트 핸들러에 의하여 메모리에 보관되었다가 다시 적재됨(2.1절 참조)

- 동시 수행시의 예: counter = 5인 경우

T0: (P)  register1 := counter;

T1: (P)  register1 := register1 +1;

T2: (C)  register2 := counter;

T3: (C)  register2 := register2 -1;

T4: (P)  counter := register1;

T5: (C)  counter := register2;

이때, count는 5가 아닌 4가 나옴, 또한 T4와 T5의 순서가 바뀌면 6이 나옴

(이유) 두 프로세스가 변수 counter를 동시에 조작하기 때문

  →  ‘경합 조건(race condition)’이라 함

(해결) 변수 counter를 어떤 시간에 한 프로세스만 유일하게 조작할 수 있게 해야 함

  → 프로세스의 ‘동기화(synchronization)’ 필요

6.2 임계 구역 문제(The Critical-Section Problem) 

▶ n개의 유기적인 프로세스 으로 구성된 시스템: 

→ 각 프로세스는 ‘임계 구역(critical section)’이라는 코드 세그먼트를 가짐

- 예로써, 공통의 변수를 읽거나, 테이블을 갱신하거나, 파일에 기록하는 등의 일을 수행

- 프로세스에 의한 임계구역의 수행은 상호 배타적임: 각 프로세스는 임계구역에 들어갈 수 있는지를 미리 확인해야 하며, 다른 프로세스가 임계구역에서 수행중인 때에는 기다려야 함

▶ 프로세스의 구조: [그림 6.1] 전형적인 프로세스 Pi의 일반적인 구조

repeat

entry section

   critical section

exit section 

   remainder section;

until false;

1) 진입 구역(entry section): 임계 구역에 진입하기 위해 허가권을 요청하는 코드

2) 임계 구역(critical section)

3) 출구 구역(exit section)

4) 잔류 구역(remainder section)

▶ 임계 구역 문제의 해결을 위한 세 가지 요구 조건

① 상호 배제(mutual exclusion): 한 프로세스가 임계구역을 수행 중일 때 다른 프로세스는 임계 구역 수행 불가

② 진행(progress): 임계 구역에서 수행중인 프로세스가 없는 경우에는, 잔류 구역을 처리하고 있지 않으면서 임계구역에 들어가고자 하는 프로세스들 중에서 선택

→ 즉, 한 프로세스가 임계 구역을 끝내고 잔류 구역을 진행중일 때, 다른 프로세스가 임계구역에 들어갈 수 있음

③ 한계 대기(bounded waiting): 한 프로세스의 임계 구역 요청 후 수락까지의 기간에 임계 구역을 수행하는 다른 프로세스의 수에 제한을 둠 

→ 무한정 기다림 방지

6.2.1 두 프로세스를 위한 해결법(Two-Process Solutions)

▶ 한번에 단지 2개의 프로세스(P0, P1)만이 가능한 경우로 제한: Pi, Pj, j=1-i, i=0 or 1

begin

  common variable declarations

  parbegin

 P0;

 P1;

  parend;

end

6.2.1.1 알고리즘(Algorithm) 1

▶ 공통 변수 turn 공유: 임계 구역에 들어갈 수 있는 프로세스를 나타냄

- var turn: 0..1; → 0 or 1로 초기화

- turn = i: Pi가 임계 구역에서 실행할 수 있음을 의미

▶ 프로세스 Pi의 구조: [그림 6.2] 알고리즘 1에서 프로세스 Pi의 구조

repeat

  

while turn ≠ i do no-op;

critical section

  

turn := j;

remainder section

until false;

▶ 문제점: 상호배제는 보장하나 진행 조건을 충족시킬 수 없음

ex) P0 다음에 P1이 잔류 구역에 들어가서 P1이 먼저 끝나면, turn=0이고 P0는 잔류 구역 수행중인 상태가 되기 때문에 P1이 임계 구역에 못 들어감

→ 원인: turn으로는 프로세스가 임계 구역에 있는지 잔류 구역에 있는지 구분이 안되기 때문

6.2.1.2 알고리즘(Algorithm) 2

▶ 변수 turn → 배열 flag: 각 프로세스가 임계 구역에 있는지 잔류 구역에 있는지를 보다 자세히 나타내기 위함 

var flag: array [0..1] of boolean; 

  - false로 초기화됨

  - flag[i] = true: Pi가 임계 구역에 진입할 준비가 되어있음을 의미함

▶ 프로세스 Pi의 구조: [그림 6.3] 알고리즘 2에서 프로세스 Pi의 구조

repeat

  

flag[i] := true;

while flag[j] do no-op;

critical section 

  

flag[i] := false;

remainder section

until false;

▶ 문제점: 여전히 진행 조건을 만족 못함

ex) 프로세스 P0와 P1가 동시에 임계구역에 들어가려는 경우 → 두 프로세스 모두 무한 대기 수행

  T0: P0가 flag[0] = true 설정

  T1: P1가 flag[1] = true 설정

6.2.1.3 알고리즘(Algorithm) 3

▶ “알고리즘1 + 알고리즘2”: 즉, 변수 turn과 배열 flag를 모두 사용

var flag: array [0..1] of boolean;

    turn: 0..1;

  - 초기값: flag[0] = flag[1] = false, turn = 0 or 1

▶ 프로세스 Pi의 구조: [그림 6.4] 알고리즘 3에서 프로세스 Pi의 구조

repeat

  

flag[i] := true;

turn := j; ← 상대방 우선

while (flag[j] and turn=j) do no-op;

critical section 

  

flag[i] := false;

remainder section

until false;

▶ 증명

① 상호 배제: P0와 P1이 동시에 임계 구역을 요청하는 경우, flag[0] = flag[1] = true이고 turn = 0 or 1 중 유일한 값이므로, 임계구역에 들어갈 수 있는 것은 반드시 하나임

② 진행: Pi가 요청했을 때 이미 Pj가 임계 구역을 수행중이면, flag[j] = true이고 turn = j 이므로 Pi는 기다리다가, Pj가 임계 구역을 벗어나는 순간 flag[j] = false가 되어 Pi가 임계 구역에 진입하게 됨

③ 한계 대기: Pi는 Pj가 기껏해야 한번 임계 구역에 들어간 후에는, Pj가 잔류 구역을 수행중이라도 임계 구역에 들어갈 수 있음

6.2.2 복수 프로세스를 위한 해결법(Multiple-Process Solutions)

▶ 제과점 알고리즘(bakery algorithm):

- 가게에 들어서자마자 고객은 번호표를 받음(이때, 동일한 번호가 존재할 수 있다고 가정)

- 번호표가 낮은 프로세스가 우선하되,

- 동일한 번호표의 Pi와 Pj는 i<j(i, j는 고유)인 경우, Pi가 먼저 서비스를 받음

▶ 공동 변수 선언

var choosing: array [0..n-1] of boolean; ← (초기화) false

    number: array [0..n-1] of integer; ← (초기화) 0

▶ 표기법 정의

- (number, id): 

- 

▶ 프로세스 Pi의 구조: [그림 6.4] 제과점 알고리즘에서 프로세스 Pi의 구조

repeat

  

                       (다른 프로세스에서도 이 문장을 동시에 수행할 수 있으므로

 choosing[i] := true;     동일한 number를 갖는 서로 다른 프로세스가 존재 가능)

 number[i] := max(number[0], number[1], ..., number[n-1]) + 1; ↙

 choosing[i] := false;

 for j := 0 to n-1

     do begin

            while choosing[j] do no-op; ← (다른 프로세스의 number 선택을 기다림)

            while number[j]≠0 and (number[j], j) < (number[i], i) do no-op; ↖

end;                       (number가 더 작은 프로세스가 존재하면 기다림)

critical section 

    

number[i] := 0;

 ← (number가 0이면 제과점에 들어가지 않은 상태임)

remainder section

until false;

▶ 증명

① 상호 배제: number가 0이 아니면서 보다 작은 프로세스가 존재하면 기다림

② 진행: 임계구역을 벗어나자마자 number가 0이 되어 다른 프로세스의 진행을 방해하지 않음

③ 한계 대기: 먼저 임계 구역에 도착하면 보다 작은 number를 갖게 되어 먼저 수행되므로   (first-come, first-served), 기껏해야 1 cycle만 대기함

6.3 동기화 하드웨어(Synchronization Hardware)

▶ 하드웨어 명령어의 중요한 특징: 인터럽트 되지 않고 하나의 단위로 처리됨 원자적(atomical) 실행

  → 임계 구역 문제를 보다 쉽고 효율적으로 해결할 수 있음

▶ Test-and-Set 명령어의 정의: [그림 6.6] Test-and-Set 명령어의 정의

function Test-and-Set(var target: boolean): boolean;

   begin

       Test-and-Set := target;

       target := true;

   end;

▶ Test-and-Set에 의한 상호 배제 구현: [그림 6.7] Test-and-Set에 의한 상호 배제 구현

(공통 변수의 초기화) lock = false;

repeat

   

while Test-and-Set(lock) do no-op;

critical section

   

lock := false;

remainder section

until false;

▶ Swap 명령어의 정의: [그림 6.8] Swap 명령어의 정의

procedure Swap (var a,b: boolean);

  var temp: boolean;

  begin

     temp := a;

     a := b;

     b := temp;

  end;

▶ Swap에 의한 상호 배제 구현: [그림 6.9] Swap에 의한 상호 배제 구현

(공통 변수의 초기화) lock = false;

repeat

   

key := true;

repeat

    swap(lock, key);

until key = false;

critical section

   

lock := false;

remainder section

until false;

→ (문제점) 앞의 두 알고리즘은 제한된 대기를 만족하지 못하고 무한정 기다릴 수 있음

▶ Test-and-Set 명령을 사용한 임계 구역 문제의 요구 조건을 모두 만족하는 알고리즘

(공통 변수의 선언 및 초기화)

var waiting: array[0..n-1] of boolean; ← 프로세스의 상태: (초기값) false

   lock: boolean; ← 임계 구역의 상태: (초기값) false

var j: 0..n-1;

  key: boolean;

repeat

   

waiting[i] := true;

key := true;                           (lock이 false일 때까지 기다림)

while waiting[i] and key do key := Test-and-Set(lock); ↙

waiting[i] := false;

critical section

   

j := i+1 mod n;

while (j≠i) and (not waiting[j]) do j := j+1 mod n;

if j=i then lock := false;

      else waiting[j] := false;

remainder section

until false;

(증명)

① 상호 배제: 임계 구역에 들어가려면 waiting[i] = false이거나 key = false라야 한다. 

- 어떤 프로세스가 임계 구역을 떠날 때 임계 구역을 기다리는 다른 프로세스가 존재하지 않으면, lock = false가 되고 그 후 최초로 Test-and-Set을 호출한 프로세스만 key = false가 됨

- 어떤 프로세스가 임계 구역을 떠날 때 임계 구역을 기다리는 다른 프로세스들이 존재하면, 그 중 하나의 프로세스만이 waiting[i] = false가 됨

② 진행: 출구 구역에서 대기하고 있는 프로세스들 중에서 waiting[j] := false가 되는 Pj가 임계 구역에 들어감

③ 제한된 대기: 출구 구역에서 순환 순서로 대기 중인 프로세스를 검사하므로, 기껏해야 n-1번째로 들어감

→ (문제점) 위와 같은 복잡한 연산의 하드웨어 구현은 일반적으로 지원되지 않음

6.4 세마포(Semaphore): “동기화 도구”

▶ 세마포 S: 두 표준 원자 연산 wait(또는 P)와 signal(또는 V)에 의해서만 접근되는 정수 변수

- P(proberen): “검사하다”의 네덜란드어

- V(verhogen): “증가하다”의 네덜란드어

 wait(S): while S≤0 do no-op;

         S := S-1;

 signal(S): S := S+1;

→ wait, signal 연산 내에서 세마포의 수정은 원자적으로 수행되어야 하는데, 특히 wait(S)의 경우, S의 테스트(S≤0)와 S의 수정(S:=S-1)이 인터럽트에 걸리지 않고 수행되어야 함

6.4.1 사용법(Usage)

▶ n개 프로세스의 임계 구역 문제를 취급하는데 사용

→ 세마포 mutex 공유(초기값=1)

repeat

  

wait(mutex);

     critical section

  

signal(mutex);

     remainder section

until false;

[그림 6.11] 세마포에 의한 상호배제의 구현

▶ 동기화 문제를 해결하는데 사용

(예) 두 프로세스에서 P1이 문장 S1을 수행한 후, P2가 문장 S2를 수행해야 하는 경우

→ 세마포 synch 공유(초기값=0)

P1: S1;

  signal(synch); ← ⌌synch := synch + 1⌏

P2: wait(synch); ← ⌌while synch≤0 do no-op; synch := synch - 1;⌏

  S2;

6.4.2 구현(Implementation)

▶ 문제점: “바쁜 대기(busy-waiting)" - 지금까지의 모든 알고리즘에 해당

  즉, 어떤 프로세스가 임계 구역 내에 있는 동안, 그 임계 구역에 들어가려는 다른 프로세스들은 진입코드(entry code)에서 계속 수행함 → CPU 시간 낭비: “spinlock”이라고 함

▶ 해결책:

- 바쁜 대기 대신에 wait 연산내에 있는 block 연산에 의해 프로세스 자신을 봉쇄(block)시킴

→ block 연산은 프로세스를 세마포와 관련된 대기 큐에 넣고, 프로세스의 상태를 대기 상태(waiting state)로 전환함

- 세마포 S에 대해 대기하면서 봉쇄된 프로세스는 다른 프로세스의 signal 연산내의 wakeup 연산에 의해 재시작됨

→ 프로세스를 준비 큐로 이동시킴으로써, 프로세스의 상태가 대기 상태에서 준비 상태(ready state)로 변경됨

▶ 세마포의 정의

type semaphore = record

     value: integer;

     L: list of process; ← 대기 리스트

 end;

▶ 세마포 연산의 정의

wait(S): S.value := S.value - 1;

if S.value < 0

   then begin 

    add this process to S.L;

    block; ← 호출한 프로세스 자신 P를 봉쇄함: OS 제공 연산

end;

signal(S): S.value := S.value + 1;

 if S.value ≤ 0

     then begin 

      remove a process P from S.L;

      wakeup(P); ← 봉쇄된 프로세스 P를 재개함: OS 제공 연산

  end;

▶ 세마포의 특성

- 세마포의 값은 음수가 될 수 있으며, 음수값은 그 세마포에 대해 기다리는 프로세스의 수를 의미

→ 대기 프로세스 중에서 하나를 선택하는 방법은 FIFO, LIFO, 우선순위 등 임의의 방법 가능

- 세마포는 원자적으로 수행되어야 함

1) 단일 프로세서인 경우: wait와 signal의 조작 시 인터럽트를 금지시키면 됨

2) 다중 프로세서인 경우: 인터럽트 금지로 해결 불가

  → 하드웨어에 의해 특별한 명령이 지원되든지, 복잡한 소프트웨어로 해결되어야 함

6.4.3 교착 상태(Deadlocks)와 기아(Starvation)

▶ 교착 상태(deadlock): 어떤 세마포에 연관된 대기 큐에서 대기중인 프로세스 집합에서 모든 프로세스들이 다른 프로세스가 야기하는 사건을 기다리는 상태 → 7장 참조

  ex) p.186의 예

▶ 무한 블록킹(infinite blocking)/기아(starvation): 프로세스들이 세마포에서 무한히 기다리는 것

6.4.4 이진 세마포(Binary Semaphores)

▶ 이진 세마포(binary semaphore) ↔ 계수 세마포(counting semaphore)

- 계수 세마포: 앞에 정의한 바와 같이, 정수값의 범위에 제한이 없는 세마포

- 이진 세마포: 정수값이 0 또는 1인 세마포 → 하드웨어로 구현

▶ 이진 세마포에 의한 계수 세마포 S의 구현: p.187의 내용

- 자료구조

var S1: binary-semaphore; ← 원자연산 위함(초기값: 1)

   S2: binary-semaphore; ← 상호배제 위함(초기값: 0)

   C: integer; ← 계수 세마포 S의 값(초기값: S의 초기값 - ex) 1, 0, or N)

- 계수 세마포 S의 wait 연산

wait(S1);

C := C - 1;

if C < 0

   then begin

    signal(S1);

    wait(S2);

end

signal(S1);

- 계수 세마포 S의 signal 연산

wait(S1);

C := C + 1;

if C ≤ 0

   then signal(S2);

   else signal(S1);

6.5 동기화의 고전적인 문제들(Classical Problems of Synchronization)

▶ “병행제어 문제의 예” → 동기화 기법 검사에 사용

6.5.1 한계 버퍼 문제(The Bounded-Buffer Problem)

▶ 푸울: n개의 버퍼로 구성

▶ 세마포

  1) mutex: 버퍼 푸울 접근의 상호배제 제공(초기값 = 1)

  2) empty: 빈 버퍼의 수(초기값 = n)

  3) full: 찬 버퍼의 수(초기값 = 0)

▶ 알고리즘

  1) 생산자 프로세스: [그림 6.12] 생산자 프로세스의 구조

  2) 소비자 프로세스: [그림 6.13] 소비자 프로세스의 구조

6.5.2 판독 기록 문제(The Readers and Writers Problem)

▶ 자료 객체(data object; 파일, 레코드 등)가 여러 병행 프로세스간에 공유될 때, 기록기(writer)가 공유 객체에 대해 배타적 접근하도록 해야 함

1) 판독 기록 문제1: 기록기가 대기중일지라도, 새로운 판독기는 기다릴 필요 없음

  → 기록기의 기아 상태 가능

2) 판독 기록 문제2 : 기록기가 대기중이면, 새로운 판독기는 기다려야 함

  → 판독기의 기아 상태 가능

▶ 판독 기록 문제1

1) 자료구조

var mutex, wrt: semaphore; (초기값=1)

 readcount: integer; (초기값=0)

- mutex: readcount가 갱신될 때 상호 배제를 보장하기 위함

- wrt: 기록기와 판독기들의 상호 배제 위함

- readcount: 현재 객체를 읽고 있는 프로세스의 수

2) 기록기 프로세스의 일반적인 구조: [그림 6.14] writer 프로세스의 구조

3) 판독기 프로세스의 일반적인 구조: [그림 6.15] reader 프로세스의 구조

6.5.3 식사하는 철학자 문제(Dining Philosophers Problem)

▶ 5명의 철학자와 원형 테이블: [그림 6.16] 철학자들의 만찬 상황

- 철학자: 생각 모드, 식사 모드

- 젓가락: 5개(5쌍 아님)

- 좌・우 젓가락을 한번에 하나씩 모두 들어야 식사 가능

→ (해결책) 각 젓가락을 세마포로 표시

▶ 공유 자료 구조 및 기본 연산

  var chopstick: array[0..4] of semaphore; (초기값=1)

- 젓가락 들기: wait(chopstick[i])

- 젓가락 놓기: signal(chopstick[i])

▶ 철학자 i의 구조: [그림 6.17] 철학자 i의 구조

▶ 문제점: 두 이웃이 동시에 식사할 수 없음에도 불구하고 “교착 상태” 발생 가능함

→ 즉, 모든 철학자가 동시에 식사를 시작하는 경우

    - 각 철학자가 동시에 왼쪽 chopstick을 들면, chopstick의 각 요소는 ‘0’이 됨

    - 우측 chopstick을 들기 위해 모두 기다리게 됨

▶ 해결책

  ① 동시에 4명의 철학자만이 동시에 테이블에 앉도록(젓가락을 들도록) 함

  ② 철학자는 그의 양쪽 젓가락 모두가 사용가능할 때만 들도록 함(도로 내려놓음)

  ③ 비대칭 해결법: 홀수 철학자는 왼쪽 젓가락부터 들고, 짝수 철학자는 오른쪽 젓가락부터 들게 함

  * 교착 상태의 해결 후 기아 상태(starvation)의 가능성도 제거해야 함

  → 6.7절에서 교착상태 없는 알고리즘 소개

6.6 임계 영역(Critical Region): “동기화 구조체”

▶ 세마포(semaphore): 임계 구역 문제의 해결이나 임의의 동기화 기법에 사용 가능

  ex) ‘mutex’ 세마포 변수를 공유 (초기치 = 1)

    - 임계 구역에 들어가기 전: wait(mutex) 수행

    - 임계 구역에서 나온 직후: signal(mutex) 수행

▶ 문제점: 순수 프로그램 오류, 비협조적인 프로그래머에 의해 발생

1) 세마포 mutex에 대한 연산을 바꾸어 적용한 경우 → 상호 배제 위배

signal(mutex);

  …

 critical section;

  …

wait(mutex);

2) signal(mutex)를 wait(mutex)로 바꾼 경우 → 교착 상태 발생

wait(mutex);

  …

 critical section;

  …

wait(mutex);

3) wait(mutex)나 signal(mutex) 또는 둘 다 생략한 경우 → 상호 배제 위배 or 교착 상태 발생

→ 시간 종속 오류의 예: 단점 극복을 위한 새로운 언어 구조 등장

▶ 임계 영역(critical region)/조건 임계 영역(conditional critical region)

1) 공유 변수 선언

var v: shared T; … 형태 T인 공유변수 v 선언

2) 구문

region v when B do S; 

  - 변수 v는 S내에서만 접근 가능

      즉, 문장 S가 수행되는 동안 다른 프로세스는 변수 v에 접근할 수 없음

  - B = true: S 수행

B = false: B가 true가 되고 v에 대한 상호배제가 해제될 때까지 기다림

  - P1: region v do S1;      “S1 다음에 S2” or “S2 다음에 S1”의 순차실행과 동일

    P2: region v do S2;       (즉, 동시에 S1과 S2가 수행되지 않음)

▶ (예) 한계 버퍼 문제: p.194-195

1) 공유 변수 선언

var buffer: shared record

     pool: array [0..n-1] of item;

     count, in, out: integer;

  end;

2) 생산자 프로세스

region buffer when count < n

  do begin

 pool[in] := nextp;

 in := in + 1 mod n;

 count := count + 1;

      end;

3) 소비자 프로세스

region buffer when count > 0

  do begin

 nextc := pool[out];

 out := out + 1 mod n;

 count := count - 1;

     end;

▶ 세마포에 의한 조건 임계 영역의 구현: p.195-196 참조

- 공유 변수

var mutex, first-delay, second-delay: semaphore; (초기값: 1, 0, 0)

   first-count, second-count: integer; (초기값: 0, 0)

- 구조체

  [그림 6.18] 조건 영역 구조체의 구현

6.7 모니터(Monitor): “고급 동기화 구조체”

▶ 모니터의 개념: “임계 영역 + 클래스”

→ 프로그래머 정의 연산들의 집합으로 특징지어지는 고급 동기화 구조체

▶ 모니터의 문법: p.196-197의 형식

1) 공유 자료를 위한 변수 선언

2) 변수에 대한 연산을 위한 프로시저나 함수 정의

3) 변수의 초기화 코드

▶ 모니터의 구조: [그림 6.19] 모니터의 구조

→ 모니터 구조체는 한 순간에 하나의 프로세스만 모니터 안에서 활동하도록 보장함: ‘상호배제’

▶ 조건 구조체(condition construct): 부수적인 동기화 메커니즘

- 조건(condition) 타입의 변수 선언: 

var x, y: condition;

- 조건 변수의 유일한 두 연산:

x.wait;  x.signal;

[그림 6.20] 조건 변수를 가진 모니터

→ x.wait를 호출한 프로세스는 임의의 다른 프로세스가 x.signal을 호출할 때까지 기다린다. 이때, 재개되는 프로세스는 x.signal 신호당 하나씩이며, 기다리는 프로세스가 없는 경우에는 x.signal 신호가 아무런 영향을 끼치지 않는다.

▶ 변수 x에 연관해서 중단된 Q가 있을 때, P의 x.signal 호출이 발생하는 상황: 

Q: x.wait → P: x.signal

→ 개념적으로는 P와 Q가 계속해서 수행되지만, 상호배제를 위해서는 하나씩 수행해야 함

① Q가 모니터를 떠나거나 다른 조건을 대기할 때까지, P가 대기

  → Hoare 소개: 보다 간단하고 세련된 증명으로 구현 가능

② P가 모니터를 떠나거나 다른 조건을 대기할 때까지, Q가 대기

  → 수행중이던 P가 계속 수행하는 것은 바람직하지만 비논리적임

③ ①과 ②의 절충안: Concurrent Pascal에서 채택

  → 프로세스 P가 signal 연산을 수행한 직후 모니터를 떠나고, Q가 즉시 재개됨

▶ (예) 교착 상태가 없는 철학자 만찬 문제(단, 기아 상태는 발생 가능)

- 가정: 양쪽 젓가락을 모두 사용할 수 있을 경우에만 철학자가 젓가락을 집을 수 있음

- 모니터 타입 선언: [그림 6.21] 식사하는 철학자 문제에 대한 모니터 해결

- 모니터 선언 및 각 철학자 프로세스 i의 모듈

  (공동 변수) var dp: dining-philosopher;

  (철학자 i) dp.pickup(i);

  …

dp.putdown(i);

▶ 세마포에 의한 모니터 메커니즘의 구현

- 세마포 mutex(초기값=1): 각 모니터마다 존재하여 모니터 진입의 상호배제를 위해 사용

- 세마포 next(초기값=0): signal을 보내는 프로세스 자신을 재개된 프로세스가 떠나거나 대기할 때까지 기다리게 하기 위해 사용

- 정수 변수 next-count(초기값=0): next에서 중단된 프로세스의 수를 세기 위해 제공

→ 외부 프로시저 F의 구현: p.201의 코드

▶ 조건 변수 x의 구현

- 세마포 x-sem(초기값=0)

- 정수 변수 x-count(초기값=0)

→ x.wait의 구현: p.201의 코드

   x.signal의 구현: p.202의 코드

▶ 프로세스의 재개 순서 결정 방법

→ “여러 프로세스가 조건 x상에서 대기하고 있고, x.signal이 수행되면 어떤 프로세스가 재개될까?”

① FCFS 기법: 가장 오래 기다린 프로세스가 제일 먼저 재개

② 조건부 대기 구조체(conditional wait construct): Hoare 도입

  x.wait(c)

       ↳우선 순위 번호: c값이 가장 작은 프로세스가 먼저 재개됨

▶ (예) 단일 자원 할당

- 가정: 자원 할당을 요구하는 프로세스는 자원을 사용하는데 예상되는 최대 시간을 규정함

       모니터는 가장 짧은 시간을 요청하는 프로세스에게 자원을 할당함

- 모니터: [그림 6.22] 단일 자원을 할당하는 모니터

- 프로세스: p.203의 코드

▶ 시간 종속 오류의 예

- 프로세스가 자원에 대한 접근 허가를 얻지 않고 그 자원을 연산하는 경우

- 프로세스가 자원 접근을 허용받고 나서 그 자원을 결코 해제하지 않는 경우

- 프로세스가 요청하지 않은 자원을 해제하는 경우

- 프로세스가 동일한 자원을 반복해서 요청하는 경우

→ 정확성을 위해,

1) 사용자 프로세스는 항상 정확한 순서로 모니터에 대한 호출을 수행해야 함

2) 협조 관계에 있지 않은 프로세스가 접근 프로토콜을 이용하지 않고 공유 자원을 직접 접근하게 해서는 안됨

6.8 솔라리스 2에서의 동기화(Synchronization in Solaris 2) → 생략

6.9 원자성 트랜잭션(Atomic Transactions)

▶ 원자성 트랜잭션의 구현 방법

- 임계 구역 방법: 각 트랜잭션의 원자성은 보장하나, 병행성은 보장하지 않음

- 병행 원자 트랜잭션 방법: 각 트랜잭션의 원자성과 병행성을 모두 보장함

6.9.1 시스템 모델(System Model)

▶ 트랜잭션(transaction): 하나의 논리적인 기능을 수행하는 명령들(동작들)의 집합

→ 원자성 보장 기법 필요

ex) 디스크상의 파일에 저장되어 있는 다양한 자료 항목들을 접근하고 경우에 따라서는 갱신하는 프로그램 단위: 즉, 일련의 read 연산과 write 연산들

▶ 트랜잭션의 종료

① commit 연산: 성공 종료

② abort 연산: 오류 발생 종료 

→ 트랜잭션의 복귀(roll back): 취소된 트랜잭션이 다루었던 자료들은 해당 트랜잭션이 수행되기 전 상태로 복귀되어야 함

▶ 저장 매체의 형태: 상대 속도나 고장에 대한 회복에 따라,

① 휘발성 저장장치(volatile storage)

  - 시스템 손상의 경우, 정보 손실 발생

  - 주기억장치, 캐시 기억장치

  - 접근 속도 신속

② 비휘발성 저장장치(nonvolatile storage)

  - 시스템 손상의 경우에도 정보 보전됨

  - 디스크, 자기 테이프

  - 접근 속도 느림

③ 안정 저장장치(stable storage)

  - 저장된 정보를 결코 잃지 않음: 여러 비휘발성 저장장치에 정보를 중복 저장

* 여기서는 휘발성 저장장치에서의 트랜잭션 원자성 기법 고려!

6.9.2 로그 기반 회복(Log-Based Recovery)

▶ 기록 우선 로깅(write-ahead logging): 트랜잭션에 의해 접근된 자료들의 모든 수정 정보를 안정 기억장치에 기록하는 것

▶ 자료구조: “로그” - 로그 레코드의 집합

1) 트랜잭션 write 연산의 기록

- 트랜잭션 이름: write 연산을 하는 트랜잭션의 유일한 이름

- 자료 항목 이름: 기록된 자료 항목의 유일한 이름

- 이전 값: 기록이 이루어지기 전의 자료 항목 값

- 새로운 값: 기록이 이루어진 이후의 자료 항목 값

2) 트랜잭션 처리 중에 일어나는 중요한 사건의 기록

→ 트랜잭션의 시작(start), 완성(commit), 취소(abort)

ex) 트랜잭션  수행 과정

① 시작하기 직전에 레코드 를 로그에 기록

② 모든 write 연산마다 해당 로그에 새 레코드 기록

③ 완성될 때 를 로그에 기록

→ 이때, 새로운 write(X) 연산 수행 전에 반드시 X에 해당하는 로그 레코드가 안정 기억장치에 기록되어야 함

▶ 회복 알고리즘(recovery algorithm)

- 회복에 사용되는 두 프로시저

① : 트랜잭션 에 의해 갱신된 전체 자료의 값을 이전의 값으로 회복

② : 트랜잭션 에 의해 갱신된 전체 자료의 값을 새로운 값으로 설정

- 회복을 위한 트랜잭션의 분류 방법

① 레코드  포함, 레코드 가 미 포함: 트랜잭션 는 undo됨

② 레코드 와 가 모두 포함: 트랜잭션 는 redo됨

6.9.3 검사점(Checkpoint)

▶ 로그 기반 기법의 단점

- 로그 전체에 대해 redo와 undo를 결정하기 위해 탐색 시간이 소요됨

- 이미 redo된 로그의 경우에도 재 설정을 수행하므로 회복 시간이 지연됨

▶ 검사점 개념의 도입

- 수행 중 기록 우선 로그를 유지

- 주기적으로 다음과 같이 검사점을 수행

① 휘발성 저장장치에 있는 모든 로그들을 안정 저장장치로 출력

② 휘발성 저장장치에 있는 모든 변경된 자료를 안정 저장장치로 출력

③ 로그 레코드 를 안정 저장장치 상으로 출력

→ 검사점 이전에 수행이 완성된 트랜잭션은 회복 시에 redo를 할 필요 없음

   즉,  이전에 가 나오는 트랜잭션 는 redo를 하지 않음

6.9.4 병행 원자 트랜잭션(Concurrent Atomic Transactions)

▶ 순차성(serializability): 각 트랜잭션은 원자적이므로, 이들의 병행처리 결과는 임의 순서로 순차적으로 처리되는 결과와 동일해야 함

→ 병행 수행되는 각 트랜잭션이 임계구역에서 수행되게 하면 됨: 그러나 매우 제한적임

→ 순차성을 유지하면서 트랜잭션의 수행을 중첩시킬 수 있는 병행 제어 알고리즘 필요

6.9.4.1 직렬성(Serializability)

▶ 직렬 스케줄(serial schedule): 각 트랜잭션이 원자적으로 수행되는 스케줄

ex) [그림 6.23] 스케줄 1:  다음에 이 따라오는 순차적 스케줄

▶ 비직렬 스케줄(nonserial schedule): 트랜잭션들의 수행에서 중첩을 허용하는 스케줄

→ 충돌 연산이 존재할 수도 그렇지 않을 수도 있음

▶ 충돌 연산(conflicting operation): 연속된 연산 와 가 각각 트랜잭션 와 에 속하는 스케줄 를 고려할 때, 두 연산이 동일한 자료에 접근하고 적어도 하나가  연산이면 두 연산은 충돌한다고 함

ex) [그림 6.24] 스케줄 2: 병행 직렬가능 스케줄

▶ 동등(equivalent) 스케줄: 스케줄 에 있는 연속된 연산 와 가 충돌을 일으키지 않으면 두 연산 와 의 순서만을 바꾼 스케줄 은 와 동등함

ex) 스케줄 2 → 스케줄 1: 동등

① 의  연산과 의  연산이 충돌하지 않으므로 교체

② 의  연산과 의  연산이 충돌하지 않으므로 교체

③ 의  연산과 의  연산이 충돌하지 않으므로 교체

④ 의  연산과 의  연산이 충돌하지 않으므로 교체

▶ 충돌 직렬화 가능(conflict serializable) 스케줄: 충돌 연산이 있는 스케줄 가 연속된 비충돌 연산들의 교체 작업으로 직렬 스케줄 으로 변형되면,  스케줄 는 충돌 직렬화 가능하다고 함

6.9.4.2 로킹 프로토콜(Locking Protocol)

▶ 직렬성(serializability) 보장을 위한 한 방법: 각 자료 항목마다 잠금(lock)을 연관시키고 이 잠금을 획득하고 해제하는 것을 제어하는 로킹 프로토콜(locking protocol)을 각 트랜잭션이 지키도록 하는 방법

▶ 잠금(lock)의 모드 종류

- 공유(shared): 트랜잭션 가 자료 항목 에 대해 공유 모드 잠금(shared-mode lock: 표기 )을 획득한 경우, 는 이 자료를 판독할 수 있지만 기록할 수는 없음

- 배타(exclusive): 트랜잭션 가 자료 항목 에 대해 배타 모드 잠금(exclusive-mode lock: 표기 X)을 획득한 경우, 는 이 자료를 판독할 수도 기록할 수도 없음

▶ 각 트랜잭션은 연산의 종류에 따라 자료 항목 에 대해 적당한 모드의 잠금을 요구할 수 있음

- 가 잠긴 상태가 아니라면, 의 잠금 요청은 받아들여지고, 는 를 접근할 수 있음

- 가 잠긴 상태라면, 는 기다림:

1) 가 의 배타 모드 잠금을 요구한 경우: 에 대한 잠금이 풀릴 때까지 기다림

2) 가 의 공유 모드 잠금을 요구한 경우: 가 배타 모드 잠금이면 잠금이 풀릴 때까지 기다리고, 그렇지 않으면 의 잠금 모드를 획득하고 접근할 수 있음

▶ 트랜잭션은 이전에 잠근 자료 항목을 해제할 수 있음

- 그러나 적어도 접근하는 동안에는 잠금을 유지해야 하고,

- 더욱이 직렬성이 보장되지 않을 수 있으므로, 마지막 접근 직후 해제하는 것은 바람직하지 않을 수 있음

▶ 2 단계 로킹 프로토콜(two-phase locking protocol): 직렬성 보장을 위해 트랜잭션이 다음의 두 단계를 순차적으로 수행하게 하는 방법

① 성장 단계(growing phase): 트랜잭션이 잠금을 얻기만 하고 해제하지 않는 단계

② 위축 단계(shrinking phase): 트랜잭션이 잠금을 해제하기만 하고 새로 얻지 않는 단계

→ 직렬성은 보장하나, 미교착 상태를 보장하지 못함

6.9.4.3 타임스탬프 기반 프로토콜(Timestamp-Based Protocol)

▶ 타임스탬프 순서화 방식(timestamp-ordering scheme): 트랜잭션의 순서를 미리 결정하는 방법

- 각 트랜잭션 에 대해 고정된 타임스탬프 를 유일하게 할당

-  이후에 가 시스템에 들어오면 

(구현)

1) 시스템 클록을 타임스탬프로 사용

2) 논리적 카운터를 타임스탬프로 사용

→ 트랜잭션의 타임스탬프는 직렬화 순서를 결정함: 만일 이면, 시스템은 생성된 스케줄이  다음에 가 뒤따르는 직렬 스케줄과 동등함을 보장해야 함

▶ 자료 항목에 대한 타임스탬프

- W-타임스탬프(): 를 성공적으로 수행한 임의의 트랜잭션의 최대 타임스탬프 값

- R-타임스탬프(): 를 성공적으로 수행한 임의의 트랜잭션의 최대 타임스탬프 값

→ 이 타임스탬프들은 나 를 수행할 때마다 갱신됨

▶ 타임스탬프 순서화 프로토콜(timestamp-ordering protocol): 충돌을 일으키는 모든 와  연산이 타임스탬프 순서로 수행하는 것을 보장하는 방법

1) 트랜잭션 가 를 수행하는 경우

-  < W-타임스탬프(): 는 기록되기 전의 자료 를 판독해야 함을 의미하므로,  연산은 거절되고 는 복귀함

-  ≥ W-타임스탬프():  연산은 수행되고 R-타임스탬프() 값은 기존 R-타임스탬프()과  중에서 최대 값을 취함

2) 트랜잭션 가 를 수행하는 경우

-  < R-타임스탬프(): 가 기록하는 자료 가 이전의 판독에 필요했음을 의미하므로,  연산은 거절되고 는 복귀함

-  < W-타임스탬프(): 는 자료 의 과거 값을 생성하고 있음을 의미하므로,  연산은 거절되고 는 복귀함

- 그렇지 않으면:  연산을 수행함

→ 복귀한 트랜잭션 에게는 새로운 타임스탬프 값이 할당되어 재시작됨

→ 충돌 직렬성을 보장하고, 교착상태를 일으키지 않음

▶ (예) [그림 6.25] 스케줄 3: 타임스탬프 프로토콜 하에서 가능한 스케줄