제 6 장 프로세스 동기화 (Process Synchronization) 6.1 배경 경합 상태(race condition) : 두 프로세스 모두 공동 변수를 조작 repeat ... nextp에서 한 항목 생산 while counter = n do no-op; buffer[in]:=nextp; in:=in+1 mod n; counter := counter + 1; until false; 생산자 repeat ... while counter = 0 do no-op; nextc:=buffer[out]; out:=out+1 mod n; counter := counter - 1; nextc에서 한 항목 소비 until false; 소비자 공동 변수 조작

register1 := counter register1 := register1 + 1 counter := register1 T0: producer execute register1 := counter {register1 = 5} T1: producer execute register1 := register1 + 1 {register1 = 6} T2: consumer execute register2 := counter {register2 = 5} T3: consumer execute register2 := register2 - 1 {register2 = 4} T4: producer execute counter := register1 {counter = 6} T5: consumer execute counter := register2 {counter = 4}

6.2 임계 구역(Critical Section) 문제 임계 구역: 공동 변수 변경 등을 수행하는 구역 임계 구역의 실행은 시간적으로 상호 배타적이어야… 진입 구역(entry section) : 임계 구역 바로 앞, 허가권 요청 출구 구역(exit section) : 임계 구역 바로 뒤 잔류 구역(remainder section) : 나머지 코드 임계 구역 문제 해결을 위한 3가지 요건 상호 배제(mutual exclusion) : 오직 한 프로세스만 실행 진행(progress) : 임계 구역에 프로세스가 없고, 잔류 구역이 아닌 곳에서 진입을 원하는 프로세스가 있으면 무한히 연기할 수 없다 한계 대기 : 진입 요청 후 진입 허용 사이에 다른 프로세스가 진입하는 횟수에는 한계가 있어야 한다

6.2.1 2개 프로세스를 위한 해결법 repeat while turn  i do no-op; 임계 구역 turn := j; 잔류 구역 until false; [그림 6.1] 알고리즘 1- Pi의 구조 처음에 turn이 1이고 P1이 진입하려 하지 않으면 P0는 “진행” 못함 repeat flag[i] := true; while flag[j] do no-op; 임계 구역 flag[i] := false; 잔류 구역 until false; [그림 6.1] 알고리즘 2- Pi의 구조 여기서 interrupt되면 둘 다 “진행” 못할 수 있음

while (flag[j] and turn=j) do no-op; 임계 구역 flag[i] := false; 잔류 구역 앞의 둘을 결합 3 조건 모두 만족 repeat flag[i] := true; turn := j; while (flag[j] and turn=j) do no-op; 임계 구역 flag[i] := false; 잔류 구역 until false; [그림 6.1] 알고리즘 3- Pi의 구조

6.3 복수 프로세스를 위한 해결법 repeat choosing[i] := true; number의 초기값은 모두 0 repeat choosing[i] := true; 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; while number[j]  0 and (number[j], j) < (number[i], i) do no-op; end; 임계 구역 number[i] := 0; 잔류 구역 until false; [그림 6.5] 제과점 알고리즘에서 프로세스 Pi의 구조 나중에 실행하는 프로세스가 큰 수를 할당 받음 number가 같으면, 프로세스 번호까지 비교

6.3 동기화 하드웨어 원자적으로 실행되는 하드웨어 명령어: test-and-set, swap function Test-and-Set (var target: boolean): boolean; begin Test-and-Set := target; target := true; end; [그림 6.6] Test-and-Set을 이용한 한계 대기 상호 배제 중간에 interrupt되지 않음 Repeat while Test-and-Set( lock ) do no-op; 임계 구역 lock := false; 잔류 구역 until false; [그림 6.7] Test-and-Set으로 상호 배제 구현 아직 한계 대기 조건 은 만족 안됨 but 6.2, 6.3 보다 낫고 간단! 처음엔 false

Procedure Swap (var a, b: boolean); var temp: boolean; begin temp := a; a := b; b := temp; end; [그림 6.8] swap 명령어의 정의 앞의 Test-and-Set과 완전히 동일한 효과 repeat key := true; Swap(lock, key); until key = false; 임계 구역 lock := false; 잔류 구역 until false; [그림 6.9] Swap 명령어에 의한 상호 배제의 구현 처음엔 false

while waiting[i] and key do key := Test-and-Set(lock); waiting[i]와 lock은 처음에 모두 false repeat waiting[i] := true; key := true; while waiting[i] and key do key := Test-and-Set(lock); waiting[i] := false; 임계 구역 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; 잔류 구역 until false; [그림 6.10] Test-and-Set을 이용한 한계 대기 상호 배제 한계 대기를 위한 조치 다른 프로세스가 요청 후 기다리고 있는지 차례로 검사 요청 후 기다리고 있는 프로세스가 하나도 없으면... 만약 있다면, lock을 풀지 않은 채로 대기 중인 프로세스를 임계 구역으로 진입시킴

더욱 다양한 동기화 문제(“순서” 제어 등)의 해결이 목표 6.4 세마포 (Semaphore)  더욱 다양한 동기화 문제(“순서” 제어 등)의 해결이 목표 세마포 S(정수)를 wait연산과 signal 연산(혹은 P, V)으로 조절 wait와 signal은 모두 원자적 연산 mutex는 처음에 1 고전적 정의 repeat wait(mutex); 임계 구역 signal(mutex); 잔류 구역 until false; [그림 .11] 세마포에 의한 상호 배제의 구현 wait(S): while S  0 do no-op; S := S - 1; signal(S): S:= S + 1; 프로세스 1 프로세스 2 S1; wait(synch) signal(synch) S2; 명시적 순서 지정(synch는 처음에 0)

구현 방법 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; signal(S): S.value := S.value + 1; if S.value  0 remove a process from S.L; wakeup(P); S가 음수면, |S| = 대기 프로세스 수 FIFO라면, 한계 대기 보장 가능 OS에 시스템 호출 바쁜 대기(busy waiting) 제거

var S1: binary-semaphore; S2: binary-semaphore; C: integer; wait 연산: wait(S1); C := C - 1; if C < 0 then begin signal(S1); wait(S2); end signal 연산: wait(S1); C := C + 1; if C  0 then signal(S2); else signal(S1); 6.4.3 교착상태와 기아 P0 P1 wait(S); wait(Q); wait(Q); wait(S); . . signal(S); signal(Q); signal(Q); signal(S); 인터럽트 금지나 임계 구역을 사용 하지 않고 구현 6.4.4 이진 세마포

6.5 동기화의 고전적인 문제들 6.5.1 한계 버퍼 문제 repeat … nextp에서 한 항목을 생산 초기값: mutex=1, empty=n, full=0 repeat … nextp에서 한 항목을 생산 wait(empty); wait(mutex); nextp를 buffer에 추가 signal(mutex); signal(full); until false; [그림 6.12] 생산자 프로세스의 구조 repeat wait(full); wait(mutex); … buffer로부터 삭제하여 nextc로 signal(mutex); signal(empty); nextp에서 한 항목을 생산 until false; [그림 6.13] 소비자 프로세스의 구조

readcount := readcount + 1; if readcount = 1 then wait(wrt); … 쓰기를 수행 signal(wrt); [그림 6.14] writer 프로세스의 구조 6.5.2 판독 기록 문제 wrt는 writer와 첫 reader가 공유 mutex는 reader들끼리 공유 wait(mutex); readcount := readcount + 1; if readcount = 1 then wait(wrt); signal(mutex); … 읽기를 수행 readcount := readcount - 1; if readcount = 0 then signal(wrt); [그림 6.15] reader 프로세스의 구조 초기값: mutex=0, wrt=0 첫번째 reader만 writer 때문에 기다리고, 이후의 reader들은 다른 reader 때문에 기다림 일단 read가 시작되면 reader들은 병행 read 가능 마지막 reader가 writer를 깨움

6.5.3 철학자들의 만찬(Dining Philosophers) 문제 각 젓가락 -> 세마포 repeat  wait(chopstick[i]); wait(chopstick[i+1 mod 5]); … 식사한다 signal(chopstick[i]); signal(chopstick[i+1 mod 5]); 생각한다 until false; [그림 6.17] 철학자 i의 구조 인접한 둘이 동시에 먹는 일은 방지, 그러나 교착 상태나 굶어 죽는 일 발생 가능 교착상태까지 막으려면… 1. 철학자를 4명만 앉게 2. 2개 모두 잡을 수 있을 때만 잡게 (임계구역에서 wait) 3. 홀짝제

6.6 임계 영역 (Critical Region)  오류 혹은 악의에 의해 wait, signal을 잘못 표현 임계 구역 동시 수행 혹은 교착 상태 유발 가능 임계 영역: 고수준 언어 구조체(construct) (동기화 구조) var v: shared T; region v when B do S (공유 변수 선언) (region 문) S 실행 동안 다른 프로세스가 v를 접근 못함

Encapusulation(캡슐화): var buffer: shared record pool: array [0..n-1] of item; count, in, out: integer; end; 생산자 프로세스: region buffer when count < n do begin pool[in] := nextp; in := in + 1 mod n; count := count + 1; 소비자 프로세스: region buffer when count > 0 nextc := pool[out]; out := out + 1 mod n; count := count - 1; pool, count, in 등을 프로세스에서 함부로 접근 못함 (반드시 region문을 통해서만 가능)

first-count := first-count + 1; if second-count > 0 wait(mutex); while not B do begin first-count := first-count + 1; if second-count > 0 then signal(second-delay) else signal(mutex); wait(first-delay); first-count := first-count - 1; second-count := second-count + 1; if first-count > 0 then signal(first-delay) else signal(second-delay); wait(second-delay); second-count := second-count - 1; end; S; then signal(first-delay); else if second-count > 0 then signal(second-delay); [그림 6.18] 조건부 구역 구조체의 구현 Mutex=1, 나머지는 모두 0으로 초기화