프로세스 동기화(Process Synchronization) 프로세스 협조 file 공유 logical address space 공유(thread) -> data (inconsistency) 자료 불일치 발생 가능 -> 프로세스 협조와 동기화 필요 배경(Background) ~ 공유 메모리를 이용한 생산자-소비자 문제 해결법 : 동기화에 count 이용 생산자 public class BoundedBuffer { public void enter(Object item) { // producer calls this method } 소비자 public Object remove() { // consumer calls this method } // potential race condition on count private volatile int count; }; 2000 운영체제

enter() Method & remove() Method // producer calls this method public void enter(Object item) { while (count == BUFFER_SIZE) ; // do nothing // add an item to the buffer ++count; buffer[in] = item; in = (in + 1) % BUFFER_SIZE; } // consumer calls this method public Object remove() { Object item; while (count == 0) ; // do nothing // remove an item from the buffer --count; item = buffer[out]; out = (out + 1) % BUFFER_SIZE; return item; } 2000 운영체제

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

임계 구역(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)을 가정 2000 운영체제

2개 프로세스를 위한 해결법(Two-Tasks Solutions) ~ Algorithm 1 : turn 이용 R1(상호 배제) 만족 R2(진행) 불만 turn = 0 이고 P1은 진입 준비상태이고 P0가 잔류영역에 -> 영원히 P1 진입 불가 R3(한계 대기) 불만 Algorithm 2 : 진입준비 flag 이용 (P0 sets flag[0] = ture, P1 sets flag[1] = ture) R2(진행) 불만: flag[0] = true set 직후 flag[1] = true -> looping forever (flag[0] = true set 후 timer interrupt 가능한 환경 또는 병행실행 환경에서) 그래서 순서 바꾸면 -> 상호 배제 불만, 둘 다 CS 진입 R3(한계 대기) 불만: looping forever이므로 Algorithm 3 : 진입준비 flag + turn (Algorithm 1 + Algorithm 2) 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에서 처럼) 2000 운영체제

Worker Thread public class Worker extends Thread { public Worker(String n, int i, MutualExclusion s) { name = n; id = i; shared = s; } public void run() { while (true) { shared.enteringCriticalSection(id); // in critical section code System.Out.println(“Worker “ + name + “ in critical section”); shared.leavingCriticalSection(id); // out of critical section code System.Out.println(“Worker “ + name + “ out of critical section”); private String name; private int id; private MutualExclusion shared; 2000 운영체제

MutualExclusion Abstract Class public abstract class MutualExclusion { public static void criticalSection() { // simulate the critical section } public static void nonCriticalSection() { // simulate the non-critical section public abstract void enteringCriticalSection(int t); public abstract void leavingCriticalSection(int t); public static final int TURN_0 = 0; public static final int TURN_1 = 1; 2000 운영체제

Testing Each Algorithm public class TestAlgorithm { public static void main(String args[]) { MutualExclusion alg = new Algorithm_1(); Worker first = new Worker("Runner 0", 0, alg); Worker second = new Worker("Runner 1", 1, alg); first.start(); second.start(); } 2000 운영체제

Algorithm 1 public class Algorithm_1 extends MutualExclusion { public Algorithm_1() { turn = TURN_0; } public void enteringCriticalSection(int t) { while (turn != t) Thread.yield(); public void leavingCriticalSection(int t) { turn = 1 - t; private volatile int turn; 2000 운영체제

Algorithm 2 public class Algorithm_2 extends MutualExclusion { public Algorithm_2() { flag[0] = false; flag[1] = false; } public void enteringCriticalSection(int t) { int other; other = 1 - t; flag[t] = true; while (flag[other] == true) Thread.yield(); public void leavingCriticalSection(int t) { flag[t] = false; private volatile boolean[] flag = new boolean[2]; 2000 운영체제

Algorithm 3 public class Algorithm_3 extends MutualExclusion { public Algorithm_3() { flag[0] = false; flag[1] = false; turn = TURN_0; } public void enteringCriticalSection(int t) { int other = 1 - t; flag[t] = true; turn = other; while (flag[other] == true) && (turn == other)) Thread.yield(); public void leavingCriticalSection(int t) { flag[t] = false; private volatile int turn; private volatile boolean[] flag = new boolean[2]; 2000 운영체제

동기화 하드웨어(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을 읽음 원자적으로 실행(executed atomically) 중간에 인터럽트가 되지 않는 하나의 단위로 수행됨 하나의 기억장치 사이클 내에서 수행됨 Data structure for hardware solutions public { public HardwareData(boolean v) { data = v; } public boolean get() { return data; public void set(boolean v) { private boolean data; 2000 운영체제

동기화 하드웨어(Synchronization Hardware) ~ Test-and-Set instruction in Java Public class HardwareSolution { public static boolean testAndSet(HardwareData target) { // 원자적 수행 HardwareData temp = new HardwareData(target.get()); target.set(true); return temp.get(); } Thread using Test-and-Set lock HardwareData lock = new HardwareData(false); // lock 공유 while (true) { while (HardwareSolution.testAndSet(lock)) // 원자적 실행 Thread.yield(); criticalSection(); lock.set(false); nonCriticalSection(); 2000 운영체제

동기화 하드웨어(Synchronization Hardware) ~ Swap instruction public static void swap(HardwareData a, HardwareData b) { // 원자적 수행 HardwareData temp = new HardwareData(a.get()); a.set(b.get()); b.set(temp.get()); } Thread using swap HardwareData lock = new HardwareData(false); HardwareData key = new HardwareData(true); while (true) { key.set(true); do { HardwareSolution.swap(lock, key); // 원자적 실행 } while (key.get() == true); // now in critical section code lock.set(false); // out of critical section 2000 운영체제

세마포어(Semaphores) ~ Dijkstra 1965 세마포어 S 원자적 연산 wait(P:proberen, wait)와 signal(V:verhogen, increment)로 접근되는 정수 변수 P(S) { while S≤0 ; //no-op S--; } V(S) { S++; 이용(Usage) counting semaphore의 값은 무제한(unrestricted domain) binary semaphore의 값은 0 또는 1 counting semaphore S는 binary semaphore로 구현 가능 (초기값은 1, S가 0이 되면 모든 자원 이용 중이므로 S가 0이상이 될 때까지 대기) Semaphore S; P(S); criticalSection(); V(S); 2000 운영체제

세마포어(Semaphores) ~ public class Worker extends Thread { public Worker(Semaphore s, String n) { name = n; sem = s; } public void run() { while (true) { sem.P(); System.out.println(name + “ is in critical section.”); Runner.criticalSection(); sem.V(); System.out.println(name + “ is out of critical section.”); Runner.nonCriticalSection(); private Semaphore sem; private String name; 2000 운영체제

세마포어(Semaphores) ~ public final class Semaphore { public Semaphore() { value = 0; } public Semaphore(int v) { value = v; public synchronized void P() { // 원자적 실행 while (value <= 0) { try { wait(); catch (InterruptedException e) { } value --; public synchronized void V() { // 원자적 실행 ++value; notify(); private int value; 2000 운영체제

세마포어(Semaphores) ~ public class Runner { public static void criticalSection() { try { Thread.sleep( (int) (Math.random() * 3000) ); } catch (InterruptedException e) { } public static void nonCriticalSection() { public class FirstSemaphore public static void main(String args[]) { Semaphore sem = new Semaphore(1); Worker[] bees = new Worker[5]; for (int i = 0; i < 5; i++) bees[i] = new Worker(sem, “Worker ” + (new Integer(i)).toString()); for(int i = 0; i < 5; i++) bees[i].start(); 2000 운영체제

세마포어(Semaphores) ~ 효율적 구현(Implementation) 지금까지의 상호배제 해법들 : busy waiting(do no-op;)해야 함(단일 프로세서로 다중 프로그래밍할 때 문제 일으킴) 다른 말로 -> spinlock : 문맥 교환 없이 Lock상태에서 기다림 busy waiting 없는 세마포어 Wait으로 busy waiting하는 대신 자신을 중지 시키고(block itself) CPU는 다른 일을 하게 함 Wakeup으로 재시작 시킴 세마포어 S integer : 절대값은 세마포어 S에서 대기하고 있는 프로세스 개수 list : PCB들의 FIFO 큐 등 스케줄링 알고리즘에 따른 대기 큐 원자적 실행(executed atomically) 1. uniprocessor : 실행 수준 높여 interrupt방지 2. mutiprocessor : 임계영역 문제 해결 방법들(Ex) turn+flag algo, bakery algo) busy waiting 없는 세마포어: Critical Section이긴 응용에서 busy waiting해결하는 방법임 Linux의 세마포어 원자적 연산 구현: P(S)에서 process status를 TASK_UNINTERRUPTIBLE로 uninterruptible하게 만들고 CPU 스케줄링 호출하여 실행, V(S)에서 TASK_RUNNING으로 interruptible하게 복귀(Linux Kernel Internals, 2nd Ed., p34~36 참조) 2000 운영체제

세마포어(Semaphores) ~ P(S) { value--; if(value<0) { add this process to list block; } V(S) { value++; if(value≤0) { remove a process P from list wakeup(P); } 2000 운영체제

세마포어(Semaphores) 교착상태(Deadlock)와 기아상태(Starvation) deadlock(두개 이상의 프로세스가 현재 대기중인 프로세스에 의해서만 일어날 수 있는 event를 무한히 기다림) (예) P0 ← deadlocked P(S); P(Q); .... V(S); V(Q); 기아상태(starvation) 또는 무한 정지(indefinite blocking) 세마포어 안에서 무한히 기다림 (예) 세마포어의 대기 리스트를 LIFO 순으로 처리하면 -> Starvation → P1 (초기값 S=1, Q=1) P(Q); P(S); …. V(Q); V(S); 2000 운영체제

동기화의 고전적인 문제들(Classical Problems of Synchronization) semaphore를 이용한 동시성 제어(concurrency-control) 문제 유한 버퍼 생산자-소비자 문제(Bounded-Buffer Problem) 판독자와 기록자 문제(Readers and Writers Problem) 식사하는 철학자 문제(Dining-Philosophers Problem) 2000 운영체제

유한버퍼 생산자-소비자 문제(The Bounded-Buffer Problem) BoundedBuffer class public class BoundedBuffer { public BoundedBuffer() { // buffer is initially empty count = 0; in = 0; out = 0; buffer = new Object[BUFFER_SIZE]; mutex = new Semaphore(1); empty = new Semaphore(BUFFER_SIZE); full = new Semaphore(0); } public void enter() { /* see next slides */ } public Object remove() { /* see next slides */ } private static final int BUFFER_SIZE = 2; private Semaphore mutex; private Semaphore empty; private Semaphore full; private int in, out; private Object[] buffer; 2000 운영체제

유한버퍼 생산자-소비자 문제(The Bounded-Buffer Problem) The enter() method public void enter(Object item) { empty.P(); mutex.P(); // add an item to the buffer ++count; buffer[in] = item; in = (in + 1) % BUFFER_SIZE; if (count == BUFFER_SIZE) System.out.println(“Producer Entered “ + item + “Buffer FULL”); else System.out.println(“Producer Entered “ + item + “Buffer Size =“ + count); mutex.V(); full.V(); } 2000 운영체제

유한버퍼 생산자-소비자 문제(The Bounded-Buffer Problem) The remove() method public Object remove() { full.P(); mutex.P(); // remove an item from the buffer Object item = buffer[out]; out = (out + 1) % BUFFER_SIZE; mutex.V(); empty.V(); return item; } 2000 운영체제

유한버퍼 생산자-소비자 문제(The Bounded-Buffer Problem) 생산자 Thread import java.util.*; public class Producer extends Thread { public Producer(boundedBuffer b) { buffer = b; } public void run() { Date message; while(true) { BoundedBuffer.napping(); // produce an item & enter it into the buffer message = new Date(); System.out.println(“Producer produced “ + message); private BoundedBuffer buffer; 2000 운영체제

유한버퍼 생산자-소비자 문제(The Bounded-Buffer Problem) 소비자 Thread import java.util.*; public class Consumer extends Thread { public Consumer(boundedBuffer b) { buffer = b; } public void run() { Date message; while (true) { BoundedBuffer.napping(); // consume an item from the buffer System.out.println(“Consumer wants to consume”); message = (Date)buffer.remove(); private BoundedBuffer buffer; 2000 운영체제

유한버퍼 생산자-소비자 문제(The Bounded-Buffer Problem) BoundedBufferServer public class BoundedBufferServer { public static void main(String args[]) { BoundedBuffer server = new BoundedBuffer(); // now create the producer and consumer threads Producer producerThread = new Producer(server); Consumer consumerThread = new Consumer(server); producerThread.start(); consumerThread.start(); } 2000 운영체제

판독자와 기록자 문제(The Readers and Writers Problem) writer : 읽고 쓰기(update) -> 공유 데이터에 단독 접근해야 (exclusive access) 유형 1 : writer가 대기 중이더라도 writer가 실제로 공유자료를 접근하지 않는 한 reader는 기다리지 않음 -> Writers may starve. Reading중이면 다른 reader도 수행가능 Writer는 reader가 없을 때 공유자료 접근 유형 2 : writer가 대기중이면 reader는 기다림 -> Readers may starve. -> 다른 기아상태 없는 해법들 있음 2000 운영체제

동기화의 고전적인 문제들(Classical Problems of Synchronization) ~ Reader public class Reader extends Thread { public Reader(Database db) { server = db; } public void run() { int c; while (true) { c = server.startRead(); // now reading the database c = server.endRead(); private Database server; 2000 운영체제

동기화의 고전적인 문제들(Classical Problems of Synchronization) ~ Writer public class Writer extends Thread { public Writer(Database db) { server = db; } public void run() { while (true) { server.startWrite(); // now writing the database server.endWrite(); private Database server; 2000 운영체제

동기화의 고전적인 문제들(Classical Problems of Synchronization) ~ The database for the readers-writers problems public class Database { public Database() { readerCount = 0; mutex = new Semaphore(1); db = new Semaphore(1); } public int startRead() { /* see next slides */ } public int endRead() { /* see next slides */ } public void startWrite() { /* see next slides */ } public void endWrite() { /* see next slides */ } private int readerCount; // number of active readers Semaphore mutex; // controls access to readerCount Semaphore db; // controls access to the database 2000 운영체제

동기화의 고전적인 문제들(Classical Problems of Synchronization) ~ Methods called by readers public int startRead() { mutex.P(); ++readerCount; // if Iam the first reader tell all others // that the database is being read if (readerCount == 1) db.P(); mutex.V(); return readerCount; } public int endRead() { mutex.P(); --readerCount; // if I am the last reader tell all others // that the database is no longer being read if (readerCount == 0) db.V(); mutex.V(); return readerCount; } 2000 운영체제

동기화의 고전적인 문제들(Classical Problems of Synchronization) ~ Methods called by writers public void startWrite() { db.P(); } public void endWrite() { db.V(); 2000 운영체제

동기화의 고전적인 문제들(Classical Problems of Synchronization) ~ 식사하는 철학자 문제(The Dining Philosophers Problem) Shared data Semaphore chopStick[] = new Semaphore[5]; 2000 운영체제

식사하는 철학자 문제(The Dining Philosophers Problem) ~ Philosopher i: while (true) { // get left chopstick chopStick[i].P(); // get right chopstick chopStick[(i + 1) % 5].P(); // eat for awhile //return left chopstick chopStick[i].V(); // return right chopstick chopStick[(i + 1) % 5].V(); // think for awhile } 2000 운영체제

식사하는 철학자 문제(The Dining Philosophers Problem) 식사하는 철학자 문제(The Dining-Philosophers Problem) : Dijkstra 차원(chostick)을 프로세스(philosophers)들에게 deadlock이나 starvation 없이 할당하는 문제 문제점 1: 만일 이웃하는 철학자가 동시에 식사할 수 있게 하면 deadlock 가능 교착상태 없는 식사하는 철학자 문제 해법들 해법 ① : 4명 까지만 동시에 식탁에 앉게 함 해법 ② : 양쪽 chopstick이 사용가능 할 때만 chopstick 잡게 함 해법 ③ : Asymmetric solution : 홀수번째 철학자들은 왼쪽 chopstick 먼저 잡게 하고, 짝수번째 철학자들은 오른쪽 chopstick 먼저 잡게 함 문제점 2 : starvation : 어떤 경우라도 한 철학자가 굶는 일 없게 해야 함->각자 2000 운영체제

Monitors ~ Semaphore 이용에서의 timing errors (producer-consumers count 에서도) 실행 순서가 틀릴 경우 세마포어를 잘못 사용하는 경우 (1) signal(mutex); 임계구역 wait(mutex); 상호배제 위반(violates mutual execulusion) (2) wait(mutex); 교착상태(deadlock) (3) wait(mutex) 또는 signal(mutex)을 빼먹으면 상호배제 위반 또는 교착상태 고급 언어 동기화 구조체로 해결 모니터(monitor) 프로그래머가 동기화 프로그래밍 하다 실수하는 대신 컴파일러가 정확한 프로그램 지원 2000 운영체제

모니터(Monitors) ~ monitor monitor-name { // variable declarations public entry p1(…) { … } public entry p2(…) { 모니터 : 한 순간에 한 프로세스만이 모니터 안에서 활성화 되게 만들어진 고급언어 구조체 : p202 그림 7.26 모니터를 powerful 하게 보완 -> 모니터 + condition(프로그래머 재량) 한 procedure가 중간에 block되었다가 조건이 만족되면 다시 진행 P가 x.signal한 후의 처리(Q는 x.wait) 1. Signal-and-Wait: P는 Q가 모니터를 떠나기를 기다리거나 다른 조건을 기다림 2. Signal-and-Continue: Q는 P가 모니터를 떠나기를 기다리거나 다른 조건을 기다림 1+2 : Concurrent Pascal : P는 signal후 즉시 monitor를 떠나고 Q가 재시작 : 한 프로시주어 안에서 한 signal만 가능 2000 운영체제

Monitor with condition variables 2000 운영체제

모니터(Monitors) ~ 식사하는 철학자 Version 2 : 교착상태 없는 식사하는 철학자들의 문제 해법 ② 이웃하는 철학자는 동시에 식사할 수 없게 하는 방법(굶는 일은 있음 : 해결 연구!) 철학자 작업 : dp.pick up(i)...eat...dp.put down(i) -> chopstick분배 monitor diningPhilosophers { int[] state = new int[5]; static final int THINKING = 0; static final int HUNGRY = 1; static final int EATING = 2; condition[] self = new condition[5]; public diningPhilosophers { for (int i = 0; i < 5; i++) state[i] = THINKING; } public entry pickUp(int i) { /* see next slides */ } public entry putDown(int i) { /* see next slides */ } private test(int i) {/* see next slides */ } 2000 운영체제

모니터(Monitors) ~ public entry pickUp(int i) { private test(int i) { state[i] = HUNGRY; test(i); if (state[i] != EATING) self[i].wait; } private test(int i) { if ( (state[(i + 4) % 5] != EATING) && (state[i] == HUNGRY) && (state[(i + 1) % 5] != EATING) ) { state[i] = EATING; self[i].signal; } public entry putDown(int i) { state[i] = THINKING; // test left and right neighbors test((i + 4) % 5); test((i + 1) % 5); } 2000 운영체제