제6장 프로세스 동기화(Process Synchronization) 운영체제 6장 제6장 프로세스 동기화(Process Synchronization) 프로세스 협조 file 공유 logical address space 공유(thread) -> data (inconsistency) 자료 불일치 발생 가능 -> 프로세스 협조와 동기화 필요 6.1 배경(Background) 공유 메모리를 이용한 생산자-소비자 문제 해결법 version 2 : counter=0 이용 buffer n개 사용 생산자 repeat ... produce an item in 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; consume the item in nextc until false;

6.1 배경(Background) [cont.] 운영체제 6장 6.1 배경(Background) [cont.] 경합 상태(race condition) : 두 개의 프로세스가 경쟁적으로 한 변수를 조작 (예) 공유 변수 counter의 변경 명령이 동시에 수행될 경우 불일치 발생 생산자의 counter := counter + 1; register1 := counter; register1 := register1 + 1; counter := register1; 소비자의 counter := counter - 1; register2 := counter; register2 := register2 -1; counter := register2; 병행 실행(concurrent execution) T0: 생산자 register1 := counter {register1 = 5} T1: 생산자 register1 : = register1 + 1 {register1 = 6} T2: 소비자 register2 := counter {register2 = 5} T3: 소비자 register2 := register2 - 1 {register2 = 4} T4: 생산자 counter := register1 {counter = 6} T5: 소비자 counter := register2 {counter = 4} 한 process만 접근하게 해야 함

6.2 임계 구역(The Critical-Section Problem)문제 운영체제 6장 6.2 임계 구역(The Critical-Section Problem)문제 임계구역 프로세스가 공유자료를 변경하는 코드영역 상호 배타적(mutually exclusive)이어야 함 프로세스 구조 진입 구역(entry section) : 진입허가 요청(한 프로세스만 실행) 출구 구역(exit section) 잔류 구역(remainer section) 임계구역 해결을 위한 3 요구 조건(requirements) R1. 상호 배제(mutual exclusion): 한 프로세스만 임계 구역 진입 R2. 진행(progress): 자연스럽게 막힘이 없이 진행, 임계구역에 진입할 프로세스 선택이 영원히 지연되지 않음 R3. 한계 대기(bounded waiting): 한 프로세스가 임계구역 진입 요청 후 기다리는데 한계가 있음 (no starvation) 기본 기계 명령어들(load, store, test)들은 원자적으로 실행됨(executed atomically)을 가정

6.2 임계 구역(The Critical-Section Problem)문제 [cont.] 운영체제 6장 6.2 임계 구역(The Critical-Section Problem)문제 [cont.] ① 2개 프로세스를 위한 해결법(Two-Process Solutions) Algorithm 1 : turn 이용 var turn : 0..1 초기값 0 while turn != i do no-op; 임계구역 turn :=j; 잔류구역 until false; R1(상호 배제) 만족 R2(진행) 불만 turn = 0 이고 P1은 진입 준비상태, P0가 잔류영역에 ->영원히 P1 진입 불가 R3(한계 대기) 불만

6.2 임계 영역(The Critical-Section Problem)문제 [cont.] 운영체제 6장 6.2 임계 영역(The Critical-Section Problem)문제 [cont.] Algorithm 2 : 진입준비 flag 이용 (P0 sets flag[0] = ture, P1 sets flag[1] = ture) 자료구조 var flag:array[0..1] of boolean; (초기값 false) repeat flag[i] := true; while flag[j] do no-op; 임계구역 flag[i] := false; 잔류구역 until false; R1(상호 배제) 만족 R2(진행) 불만: flag[0] = true set 직후 flag[1] = true -> looping forever (flag[0] = true set 후 timer interrupt 가능한 환경 또는 병행실행 환경에서) 그래서 순서 바꾸면 -> 상호 배제 불만, 둘 다 CS 진입 R3(한계 대기) 불만: looping forever이므로

6.2 임계 구역(The Critical-Section Problem)문제 [cont.] 운영체제 6장 6.2 임계 구역(The Critical-Section Problem)문제 [cont.] Algorithm 3 : 진입준비 flag + turn Algorithm 1 + Algorithm 2 자료구조 var flag : array[0..1] of boolean; turn : 0..1 초기값 : flag[0] = flag[1] = false; flag[i] = true 후 turn = j repeat flag[i] := true; turn := j; while(flag[j] and turn = j) do no-op; 임계구역 flag[i] := false; 잔류구역 until false; R1(상호배제) 만족: Pi는 turn=i 이거나 turn=j이어도 flag[j] = false 일 때 진입(flag[0]=flag[1]=true이어도 turn은 0 또는 1) R2(진행) 만족: flag[j] = false 이면 Pi 진입 OK, flag[j] = true 일 때 turn = i 또는 j, 이 때turn=i 이면 Pi 진행, turn=j 이면 Pj 진행 후 flag[j] = false -> Pi 진입, 즉시 flag[I]=true로 재설정 되더라도 turn=j되므로 Pi는 Pj 1회 실행 후 진입 가능 R3(한계대기) 만족: Pi는 Pj 많아야 한번 진입 후 진입 진행됨(R2에서 처럼)

6.2 임계 구역(The Critical-Section Problem)문제 [cont.] 운영체제 6장 6.2 임계 구역(The Critical-Section Problem)문제 [cont.] ② 복수 프로세스를 위한 해결법(Multiple-Process Solutions) Bakery algorithm : 분산 시스템을 위한 알고리즘 : Dijkatra 번호 대기 -> 가장 낮은 번호가 다음 차례, tie이면 낮은 이름이 다음 차례 자료구조 var choosing : array[0..n-1] of boolean; number : array[0..n-1] of integer; (a,b) < (c,d) if a<c or if a=c and b<d max(a0, ... An-1) is a number, k, such that K>=Ai for i=0,...,n-1 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; 0이면 while number[j] /= 0 <- 번호들 없음, 임계영역 진입 많음 and (number[j], j) <number[i], i) do no-op; end 임계영역 number[i] := 0; 잔류영역 until false; R1 만족 : number[i] /= 0, (number[i], i)<(number[k], k)인 동안 기다리다 Pi 끝나면 진입 R2 만족 : FCFS 번호 순서대로 R3 만족 : FCFS 번호 순서대로

6.3 동기화 하드웨어(Synchronization Hardware) 운영체제 6장 6.3 동기화 하드웨어(Synchronization Hardware) CS 문제 -> CS동안 interrupt금지(no preemption) uniprocessor : interrupt disable로 해결 multiprocessor : interrupt로는 불가능 : message passing overhead hardware 명령(원자적으로 실행됨)으로 해결 Test-and-Set 0->1, 1->1 Swap AT&T3B20 Read-and-Clean 0->0, 1->0 한 처리기만 원래 값 읽고 나머지는 O을 읽음 ① Function Test-and-Set (var target: boolean): boolean; ...원자적으로 실행 begin Test-and-Set := target; target := true; end; 원자적으로 실행(executed atomically) 중간에 인터럽트가 되지 않는 하나의 단위로 수행됨 하나의 기억장치 사이클 내에서 수행됨 상호배제 구현 : lock 초기값 false repeat while Test-and-Set(lock) do no-op; 임계구역 lock := false; 잔류구역 until false;

6.3 동기화 하드웨어(Synchronization Hardware) [cont.] 운영체제 6장 6.3 동기화 하드웨어(Synchronization Hardware) [cont.] ② procedure Swap(var a,b: boolean); <- 원자적으로 실행 var temp: boolean; begin temp := a; a := b; b := temp; end; 상호배제 구현 : lock초기값 false repeat key := true; <- 처음에 열쇠 가지고 swap(lock, key); <- 열쇠로 잠그고 until key = false; <- 키가 필요 없을 때 까지 임계 영역 lock := false; <- 열어 놓고 나감 잔류 영역 until false; ①② 모두 R3 한계 대기 불만

6.3 동기화 하드웨어(Synchronization Hardware) [cont.] 운영체제 6장 6.3 동기화 하드웨어(Synchronization Hardware) [cont.] ③ Test-and-Set를 이용한 한계대기(bounded waiting) 상호 배제 구현 Swap을 이용한 한계대기 상호배제 연구할 것 var waiting : array[0...n-1] of boolean lock : boolean (lock = false) Var j : 0... N-1; key : boolean; 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.4 세마포어(Semaphores) Dijkstra 1965 세마포어 S 이용(Usage) 운영체제 6장 6.4 세마포어(Semaphores) Dijkstra 1965 세마포어 S 원자적 연산 wait(P:proberen, wait)와 signal(V:verhogen, increment)로 접근되는 정수 변수 wait(S) : while S <= 0 do no-op; 원자적으로 실행(without interruption) S := S-1; signal(S) : S := S+1; 이용(Usage) i) n개 프로세스의 임계 구역 문제(=상호배제 문제)에 이용 n개 프로세스가 세마포어 mutex(mutual exclusion)을 공유 mutex 초기값 1 repeat wait(mutex); 임계구역 signal(mutex); 잔류구역 until false; ii) 동기화 문제에 이용(P1과 P2가 세마포어 synch를 공유, synch 초기값 0) 프로세스 P1: S1; Signal(synch); -> synch = 1; 프로세스 P2: wait(synch); while synch <=0 do no-op; S2; synch = synch-1;

6.4 세마포어(Semaphores) [cont.] 운영체제 6장 6.4 세마포어(Semaphores) [cont.] 효율적 구현(Implementation) 지금까지의 상호배제 해법들 : busy waiting(do no-op;)해야 함(단일 프로세서로 다중 프로그래밍할 때 문제 일으킴) 다른 말로 -> spinlock : 문맥 교환 없이 Lock상태에서 기다림 busy waiting 없는 세마포어 Wait으로 busy waiting하는 대신 자신을 중지 시키고(block itself) 하여 CPU는 다른 일을 하게 함 Wakeup으로 재시작 시킴 Type semaphore = record value : integer; L: list of process; end; var S : semaphore; S.value = 1; 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 P from S.L; wakeup(P)l

6.4 세마포어(Semaphores) [cont.] 운영체제 6장 6.4 세마포어(Semaphores) [cont.] 원래 semaphore : never negative |S.value| : 세마포어 S에서 대기하고 있는 프로세스 개수 S.L : PCB들의 FIFO 큐 등 스케줄링 알고리즘에 따른 대기 큐 원자적 실행(executed atomically) 1. uniprocessor : 실행 수준 높여 interrupt방지 2. mutiprocessor : 임계영역 문제 해결 방법들(Ex) turn+flag algo, bakery algo) busy waiting 없는 세마포어: Critical Section이긴 응용에서 busy waiting해결하는 방법임 교착상태(Deadlock)와 기아상태(Starvation) deadlock(두개 이상의 프로세스가 현재 대기중인 프로세스에 의해서만 일어날 수 있는 event를 무한히 기다림) (예) P0 <- deadlocked -> P1 (초기값 S=1, Q=1) wait(S); wait(Q); wait(Q); wait(S); .... .... signal(S); signal(Q); signal(Q); signal(S); 기아상태(starvation) 또는 무한 정지(indefinite blocking) 세마포어 안에서(S.L) 무한히 기다림 (예) 세마포어의 대기 리스트를 LIFO 순으로 처리하면 -> Starvation

6.4 세마포어(Semaphores) [cont.] 운영체제 6장 6.4 세마포어(Semaphores) [cont.] 이진 세마포어(Binary Semaphores) counting semaphore : integer value binary semaphore : 0,1 S : counting semaphore var S1 : binary-semaphore; S2 : binary-semaphore; C : integer; 초기값 S1 = S3 = 1, S2 = 0, C = counting semaphore 초기값 ㆍwait(C) 연산 ㆍsignal(C) 연산 wait(S1); wait(S1); C:=C-1; C:=C+1; if C<0 if C<=0 then signal(S2); then begin else signal(S1); signal(S1); wait(S2); end;

6.5 동기화의 고전적인 문제들(Classical Problems of Synchronization) 운영체제 6장 6.5 동기화의 고전적인 문제들(Classical Problems of Synchronization) concurrency-control problem에 포함됨 : semaphore이용함 유한버퍼 생산자-소비자 문제(The Bounded-Buffer Problem) 생산자 repeat ... produce an item in nextp wait(empty); wait(mutex); nextp를 buffer에 추가 signal(mutex); signal(full); until false; 소비자 wait(full); 0 이면 기다림 n-1 buffer로부터 한 항목을 삭제하여 nextc 에 넣음 Signal(mutex); Signal(empty); Consume the item in nextc Until false;

6.5 동기화의 고전적인 문제들(Classical Problems of Synchronization) [cont.] 운영체제 6장 6.5 동기화의 고전적인 문제들(Classical Problems of Synchronization) [cont.] 판독자와 기록자 문제(The Readers and Writers Problem) readers : 읽기만 writer : 읽고 쓰기(update) -> 공유 데이터에 단독 접근해야 (exclusive access) 유형 1 : writer가 대기 중이더라도 writer가 실제로 공유자료를 접근하지 않는 한 reader는 기다리지 않음 -> Writers may starve. Reading중이면 다른 reader도 수행가능 Writer는 reader가 없을 때 공유자료 접근 유형 2 : writer가 대기중이면 reader는 기다림 -> Readers may starve. -> 다른 기아상태 없는 해법들 있음 (유형 1 예) var mutex, wrt : semaphore; (mutex = wrt = 1) readcounter: integer; 세마포어 mutex = 1 : 공유변수(readcount)에의 상호배제 wrt = 1 : writer 상호배제 여러 writer X readcounter = 0; reader processes 갯수 writer: wait(wrt); ... Writing is performed signal(wrt);

6.5 동기화의 고전적인 문제들(Classical Problems of Synchronization) [cont.] 운영체제 6장 6.5 동기화의 고전적인 문제들(Classical Problems of Synchronization) [cont.] reader : wait(mutex); readcount := readcount + 1; if readcount = 1 then wait(wrt); signal(mutec); 읽기 수행 readcount := readcount -1; if readcount = 0 then signal(wrt); signal(mutex); 임계구역에 1 writer 있을 때, 1 reader 는 wrt에서 대기, n-1 readers는 mutex에서 대기 writer가 signal(wrt)후 scheduler가 waiting reader나 waitung writer중 하나 실행시킴 마지막 reader가 signal(wrt)후 waiting writer실행 세마포어 wrt : writer, 첫번 reader, 마지막 reader가 사용 mutex : 다른 reader들이 사용 유형 2 -> 각자

6.5 동기화의 고전적인 문제들(Classical Problems of Synchronization) [cont.] 운영체제 6장 6.5 동기화의 고전적인 문제들(Classical Problems of Synchronization) [cont.] 식사하는 철학자 문제(The Dining-Philosophers Problem) : Dijkstra 차원(chostick)을 프로세스(philosophers)들에게 deadlock이나 starvation 없이 할당하는 문제 식사하는 철학자 Version 1 var chopstick : array[0...4] of semaphore; chopstick[i] 초기값 =1 repeat wait (chopstick[i]); wait (chopstick[i+1 mod 5]); 식사 signal(chopstick[i]); signal(chopstick[i+1 mod 5]); 생각 Until false; 문제점 1: 만일 이웃하는 철학자가 동시에 식사할 수 있게 하면 deadlock 가능 교착상태 없는 식사하는 철학자 문제 해법들 해법 ① : 4명 까지만 동시에 식탁에 앉게 함 해법 ② : 양쪽 chopstick이 사용가능 할 때만 chopstick 잡게 함 해법 ③ : Asymmetric solution : 홀수번째 철학자들은 왼쪽 chopstick 먼저 잡게 하고, 짝수번째 철학자들은 오른쪽 chopstick 먼저 잡게 함 문제점 2 : starvation : 어떤 경우라도 한 철학자가 굶는 일 없게 해야 함->각자

6.6 임계 영역(Critical Regions) 운영체제 6장 6.6 임계 영역(Critical Regions) Semaphore 이용에서의 timing errors (producer-consumers count 에서도) 실행 순서가 틀릴 경우 세마포어를 잘못 사용하는 경우 (1) signal(mutex); 임계구역 wait(mutex); 상호배제 위반(violates mutual execulusion) (2) wait(mutex); 교착상태(deadlock) (3) wait(mutex) 또는 signal(mutex)을 빼먹으면 상호배제 위반 또는 교착상태 고급 언어 동기화 구조체로 해결 ① 임계영역(조건 임계구역) : region 문 ② 모니터(monitor) -> 6.7절 프로그래머가 동기화 프로그래밍 하다 실수하는 대신 컴파일러가 정확한 프로그램 지원 var V shared T; region V when B do S; S가 수행중인 동안에는 다른 프로세스는 공유변수 V에 접근할 수 없음 B가 true이면 임계구역 S수행 B가 false이면 waiting

6.6 임계 영역(Critical Regions) [cont.] 운영체제 6장 6.6 임계 영역(Critical Regions) [cont.] 병행 수행 region V when true do S1; region V when true do S2; (S1; -> S2; 또는 S2; -> S1;) 임계 영역을 이용한 유한 버퍼 생산자-소비자 문제 version 4 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;

6.6 임계 구역(Critical Regions) [cont.] 운영체제 6장 6.6 임계 구역(Critical Regions) [cont.] region x when B do S; 의 구현 : 두 개의 대기 큐 이용 -> 하나이면 ? 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; else if second-count > 0 then si gnal(second-delay);

운영체제 6장 6.7 모니터(Monitors) type monitor-name = monitor 공유 variable declarations procedure entry P1(...); begin ... end; procedure entry P2(...); ... procedure entry Pn(...); begin initialization code end 모니터 : 한 순간에 한 프로세스만이 모니터 안에서 활성화 되게 만들어진 고급언어 구조체 : p197 그림 6.19 모니터를 powerful 하게 보완 -> 모니터 + condition(프로그래머 재량) 한 procedure가 중간에 block되었다가 조건이 만족되면 다시 진행 P가 x.signal한 후의 처리(Q는 x.wait) 1. P는 Q가 모니터를 떠나기를 기다리거나 다른 조건을 기다림 2. Q는 P가 모니터를 떠나기를 기다리거나 다른 조건을 기다림 1+2 : Concurrent Pascal : P는 signal후 즉시 monitor를 떠나고 Q가 재시작 : 한 프로시주어 안에서 한 signal만 가능

운영체제 6장 6.7 모니터(Monitors) [cont.] 식사하는 철학자 Version 2 : 교착상태 없는 식사하는 철학자들의 문제 해법 ② 이웃하는 철학자는 동시에 식사할 수 없게 하는 방법(굶는 일은 있음 : 해결 연구!) 철학자 작업 : dp.pick up(i)...eat...dp.put down(i) -> chopstick분배 type dining-philosophes = monitor var state : array[0..4] of (thinking, hungry, eating); var self : array[0..4] of condition; procedure entry pickup (i: 0..4); begin state[i] := hungry; test(i); if state[i] /= eating then self[i].wait; end; procedure entry putdown (i:0..4); state[i] := thinking; test (i+4 mod 5); test (i+1 mod 5); procedure test (k: 0..4); if state[k+4 mod 5] /= eating and state[k] = hungry and state[k+1 mod 5] /= eating then begin state[k] := eating; self[k].signal; for i := 0 to 4 do state[i] := thinking; end.

6.7 모니터(Monitors) [cont.] 세마포어를 이용한 모니터의 구현 운영체제 6장 6.7 모니터(Monitors) [cont.] 세마포어를 이용한 모니터의 구현 signaling process 들이 대기하는 큐 next 필요 세마포어 mutex = 1, next = 0, next_count = 0 var mutex, next : semaphore; var next_count : integer; wait(mutex) ... 프로시주어 F의 몸체; If next-count > 0 [x.signal하고 대기중인 프로세스가 있음] then signal(next) else signal(mutex); signaling process는 재시작된 프로세스가 모니터 떠나거나 다른 wait를 할 때까지 기다림.

6.7 모니터(Monitors) [cont.] Condition variable의 구현 : 조건 x에 대한 세마포어 운영체제 6장 6.7 모니터(Monitors) [cont.] Condition variable의 구현 : 조건 x에 대한 세마포어 var x-sem; semaphore x-count: integer; x-sem = 0, x-count = 0 [조건 x 를 기다리는 프로세스 개수] x.wait x-count := x-count +1; if next-count >0 then signal(next) [나는 기다리고 signaling process 중 기다리라는 것 있으면 진행] else signal(mutex); [나는 기다리고 다른 process 진행] wait(x-sem); [x.wait 큐로] x-count := x-count-1; x.signal if x-count > 0 [x.wait 하고 있는 프로세스 있음, x-count = 0 이면 x.wait process 없음] then begin next-count := next-count + 1; signal(x-sem); [x.wait 하고 있는 프로세스 풀어 줌] wait(next); [signaling process 들이 대기하는 next wait queue 로 들어 감] next-count := next-count - 1; end

6.7 모니터(Monitors) [cont.] monitor를 이용한 스케줄링 운영체제 6장 6.7 모니터(Monitors) [cont.] monitor를 이용한 스케줄링 한 자원을 여러 경쟁하는 프로세스들 중 하나에 할당 우선순위 값이 가장 작은 작업(예 : 이용시간이 가장 작은 작업) x.wait(c) c 는 우선순위 번호 (priority scheduling) 대기 큐에 들어가면서 우선 순위 번호와 프로세스 이름을 같이 기록함 x.signal 가장 작은 우선 순위번호를 가진(가장 높은 우선순위의) 프로세스를 재시작 시킴 프로세스 작업 자원 요청 : R.acquire(t); [t : 자원 최대 사용 시간] ... 자원 접근 자원 해제 : R.release; 모니터는 프로시주어들의 올바른 접근 순서 보장 못함 프로세스가 접근 허가를 미리 받지 않고 자원에 접근할 수도 있다. 프로세스가 자원 접근을 허용 받은 다음 절대 자원을 해제하지 않을 수도 있다. 프로세스가 결코 요청되지 않을 자원을 해제할 수도 있다. 프로세스가 같은 자원을 두 번 요청할 수도 있다. 모니터 프로시주어를 잘 못 사용하는 timing error 발생 가능 고급 프로그래머 정의 연산들을 정확히 사용해야 함(컴파일러가 해결하지 못함)

6.7 모니터(Monitors) [cont.] Monitor의 단점 : 모니터 프로시주어의 올바른 접근 순서를 보장 못함 운영체제 6장 6.7 모니터(Monitors) [cont.] type resource-allocation = monitor var busy:boolean; x:condition; procedure entry acquire (time:integer); begin if busy then x.wait(time); busy := true; end; procedure entry release; busy := false; x.signal; end Monitor의 단점 : 모니터 프로시주어의 올바른 접근 순서를 보장 못함 (예) release...acquire, acquire...acquire, acquire나 release 빠트림(wait & signal처럼) 올바른 접근 순서 보장 위해 ① 모든 user program이 모니터 call을 올바르게 하는지 검사해야 ② 모든 프로세스가 상호배제 protocol(규약)을 잘 지키는지 검사해야 : 작고 정적인 시스템에서만 가능, 대형 시스템이나 동적인 시스템에 부적합 ->19장 생산자-소비자 모니터와 연습문제 6.12 꼭 해보세요!

6.8 Solaris 2에서의 동기화(Synchronization in Solaris 2) 운영체제 6장 6.8 Solaris 2에서의 동기화(Synchronization in Solaris 2) 1. 적응성(adaptive) mutexes : 짧은 임계구역에 i) multiprocessor system에서 처음에는 표준 세마포어처럼 동작(spinlock)하다 사용하려는 데이터가 lock 되었을 때 ① lock한 프로세스가 running thread이면 그대로 spinlock 하다가 진행 ② lock한 프로세스가 running thread 아니면(spinlock시간이 길어질 경우) sleeping thread로 처리 : block되어 sleep했다가 wakeup됨(바쁜 대기 없는 세마포어 처럼) ii) uniprocessor system에서 항상 sleeping thread로 처리 다른 thread가 lock test하는 순간 이미 CPU는 다른 thread 처리 중이므로 2. 조건 변수(Condition variable) : 긴 임계구역에 lock 되었으면 thread는 wait and sleeps lock을 푸는 스레드가 signal 3. 판독자-기록자 잠금(readers-writers locks) : 긴 임계구역에 대부분의 경우 read-only인 data 보호 semaphore보다 유리 (multiple reads 가능하므로)

6.9 원자적 트랜잭션(Atomic Transactions) 운영체제 6장 6.9 원자적 트랜잭션(Atomic Transactions) DBMS 기술을 OS에 응용 시스템 모델(System Model) 트랜잭션(transaction) : 하나의 논리적인 기능을 수행하는 명령어들의 집합 원자적 처리가 보장되어야 함 commit 또는 abort로 끝나는 일련의 read와 write 연산 commit : 트랜잭션 성공 abort : 트랜잭션 실패 -> 원자성 보장위해 복귀(roll back)되어야 함 기억장치의 형태 휘발성(volatile) 기억장치 : 주기억, 캐시 비휘발성(nonvolatile) 기억장치 : 디스크, 자기 테이프 안정(stable) 기억장치 : 여러 비휘발성 캐시에 중복 저장 로그 기반 회복(Log-Based Recovery) 기록-전-로깅(write-ahead logging) : 안전 기억장치에 로그 유지 Log record 1. 트랜잭션 이름(transaction name) 2. 자료 항목 이름(data item name) 3. 이전 값(old value) 4. 새로운 값(new value)

6.9 원자적 트랜잭션(Atomic Transactions) [cont.] 운영체제 6장 6.9 원자적 트랜잭션(Atomic Transactions) [cont.] 사건 기록 : <Ti starts> log record <Ti commits> log record(x) 안정 기억장치에 기록한 후 write(x) -> 더 많은 기억장소 필요 회복(recovery) Undo(Ti): <Ti starts> only : Ti로 변경된 모든 데이터를 이전 값으로 회복 Redo(Ti): <Ti starts> and <Ti commits> : Ti로 변경된 모든 값들을 새 값으로 설정 검사점(Checkpoints) 시스템 오류 시 undo 또는 redo할 트랜잭션 결정위한 로그 탐색 필요 탐색 시간 오버헤드 대다수 redo Checkpoints 주기억에 있는 모든 로그 레코드들을 안정 기억으로 출력 주기억에 있는 모든 변경된 데이터들을 안정기억으로 출력 <Checkpoint> 로그 레코드를 안정기억으로 출력 시스템 오류 시 역으로 첫번째 checkpoint 전에 있는 첫번 <Ti start>와 그 이후의 모든 Tj들이 undo 또는 redo 대상 : Tk라 할 때 <Tk commits>가 로그 안에 나타나면 redo(Tk) <Tk commits>가 로그 안에 없으면 undo(Tk)

6.9 원자적 트랜잭션(Atomic Transactions) [cont.] 운영체제 6장 6.9 원자적 트랜잭션(Atomic Transactions) [cont.] 병행 원자적 트랜잭션(Concurrent Atomic Transactions) 직렬성(Serializablility) 직렬 스케줄(serial schedule) 세마포어 mutex=1, wait(mutex), signal(mutex 비직렬 스케줄(nonserial schedule) 충돌 연산(conflicting operations) : 같은 데이터 접근, 최소 하나가 write 비충돌 연산(nonconflicting operations) : 순서를 바꿈 : 충돌 직렬화 가능(conflict serializable) p211 그림 6.24, 6.23 잠금 프로토콜(Locking Protocol) 공유 모드 잠금(shared mode lock) : read-only 배타 모드 잠금(exclusive mode) lock : read-write 한 트랜잭션에서 잠그기도하고 잠금을 풀기도하면 직렬성 보장 못할 수도 있음 2단계 잠금 프로토콜(two-phase locking protocol) : 직렬성 보장 성장 단계(growing phase) : 한 트랜잭션은 잠그기만 위축 단계(shrinking phase) : 한 트랙잭션은 해제만 충돌 직렬성(conflict serializability) 보장 교착상태 가능

6.9 원자적 트랜잭션(Atomic Transactions) [cont.] 운영체제 6장 6.9 원자적 트랜잭션(Atomic Transactions) [cont.] 타임스템프 기반 프로토콜(Timestamp-Based Protocols) 시스템이 Ti에 고정 유일한 타임스템프 배당, 새로운 트랜잭션 Tj, TS(Ti) < TS(Tj) 구현 시스템 클록(system clock) : 클록 공유해야 논리적 카운터(logical clock) : 새 트랜잭션 들어올 때 마다 counter 증가 W-timestamp(Q) : write(Q) 성공한 트랜잭션들 중 최대 타임스탬프 값 R-timestamp(Q) : read(Q) 성공한 트랜잭션들 중 최대 타임스탬프 값 타임스템프 순서화 프로토콜 Ti가 read(Q) TS(Ti) < W-timestamp(Q) : read 거절(reject), Ti는 복귀(rollback) TS(Ti) >= W-timestamp(Q) : read 수행, R-timestamp(Q) 갱신(R-timestamp와 TS(Ti) 중 최대 값으로) Ti가 write(Q) TS(Ti) < R-timestamp(Q) : write 거절, Ti 복귀 TS(Ti) < W-timestamp(Q) : write 거절, Ti 복귀 나머지 경우 : write 수행 충돌 직렬성 보장 : 충돌하는 연산들은 타임스템프 순서에 따라 처리 교착상태 없음

류시화 엮은 잠언시집 : 지금 알고 있는 걸 그때도 알았더라면 중에서 수업 운영체제 6장 류시화 엮은 잠언시집 : 지금 알고 있는 걸 그때도 알았더라면 중에서 수업 그때 예수께서 제자들을 산으로 데리고 올라가 곁에 둘러앉히시고 이렇게 가르치셨다. 마음이 가난한 사람은 행복하다. 하늘나라가 그들의 것이다. 온유한 사람은 행복하다. 슬퍼하는 사람은 행복하다. 자비를 베푸는 사람은 행복하다. 박해받는 사람은 행복하다. 고통받는 사람은 행복하다. 하늘나라에서의 보상이 크니 기뻐하고 즐거워하라. 그러자 시몬 베드로가 말했다. “그 말씀을 글로 적어 놓으리까?” 그리고 안드레아가 말했다. “그 말씀을 잘 새겨 둬야 할까요?” 그러자 야고보가 말했다. “그걸 갖고 우리끼리 시험을 쳐볼까요? 그러자 빌립보가 말했다. “우리가 그 뜻을 잘 모를 경우에는 어떻게 할까요?” 그리고 바돌로메가 말했다. “우리가 이 말씀을 다른 사람들에게 전해 줘야 할까요?” 그러자 요한이 말했다. “다른 제자들한테는 이런 걸 알려줄 필요가 있을까요?” 그러자 마태오가 말했다. “우리는 여기서 언제 떠날 건가요?” 그리고 유다가 말했다. “그 말씀이 실생활과는 어떤 관계가 있는 걸까요?” 그리고 그 자리에 참석했던 바리새인 하나는 예수에게 수업 계획서를 보여 줄 것을 요청하면서 그 가르침의 최종적인 목표가 무엇이냐고 물었다. 그러자 예수께서는 우셨다. 작자 미상 M. 스콧 펙 제공