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

Presentation on theme: "Chapter 6. 프로세스 동기화(Process Synchronization)"— Presentation transcript:

1 Chapter 6. 프로세스 동기화(Process Synchronization)
Questions of the day 두 개 프로세스를 위한 임계구역(critical section) 문제를 소프트웨어로 최초로 푼 사람은 누구인지? Dekker의 알고리즘이 임계구역 문제의 세 가지 요건을 모두 충족시키는지? 바쁜 대기(busy-waiting)의 의미는? 운영체제 안에서 이 방식과 다르게 기다리는 방식은? 바쁜 대기를 전혀 사용하지 않을 수 있는지? Peterson’s Solution에서 바쁜 대기가 사용되었는지요? 스핀락(spinlock)이 다중 처리기에서는 종종 사용되는데 비해 왜 단일 처리기 시스템에서는 소용이 없는지? 교재 p241 그림 6.19 식사하는 철학자 문제에 대한 모니터 해결안을 사용하면 굶는 철학자가 생길지? Dijkstra는 어떻게 식사하는 철학자 문제를 해결하였는지? 운영체제

2 프로세스 동기화(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; }; 운영체제

3 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; } 운영체제

4 배경(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 := register {register2 = 4} T4: 생산자 count := register {counter = 6} T5: 소비자 count := register {counter = 4} 한 process만 접근하게 해야 함 운영체제

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

6 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”); MutualExclusion.criticalSection(); 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; 운영체제

7 MutualExclusion Abstract Class
public abstract class MutualExclusion { public static void criticalSection() { // simulate the critical section try { Thread.sleep( (int) (Math.random() * 3000) ); } catch (InterruptedException e) { } 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; 운영체제

8 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(); } 운영체제

9 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; 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; turn = 0, t = 0 turn = 0, t = 1 운영체제

10 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]; 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]; flag[0] = true, flag[1] = ? flag[1] = true, flag[1] = ? 운영체제

11 Algorithm 3 (Peterson’s Solution)
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]; 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]; 운영체제

12 Peterson’s Solution 2개 프로세스 해법 LOAD 와 STORE 명령은 원자적(atomic)
즉, 수행 도중 절대 인터럽트 되지 않음 2개 프로세스가 아래 2개 변수 공유: int turn; Boolean flag[2] 변수 turn 은 어느 임계 구역 진입 순번 표시 The flag 배열은 임계 구역 진입 준비됨 표시 flag[i] = true 는 process Pi 가 준비되었음!

13 2개 프로세스를 위한 소프트웨어 해법: Two-Tasks Solutions
Algorithm 1 : turn 이용 R1(상호 배제) 만족 R2(진행) 불만 turn = 1 이고 P0은 진입 준비상태이고 P1이 잔류영역에 → 영원히 P0 진입 불가 R3(한계 대기) 불만 Algorithm 2 : 진입준비 flag 이용 (P0 sets flag[0] = true, P1 sets flag[1] = true) 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에서 처럼) 운영체제

14 Algorithm for Process Pi
/* Peterson’s in C program */ while (true) { flag[i] = TRUE; turn = j; while ( flag[j] && turn == j ) ; CRITICAL SECTION flag[i] = FALSE; REMAINDER SECTION } /* Peterson’s in JAVA program */ 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];

15 Peterson’s .vs. Dekker’s
do { flag[i] = TRUE; while (flag[j]) { if (turn == j) { flag[i] = FALSE; while (turn == j) ; // do nothing flag[i] = TRUE; } // critical section turn = j; } while (TRUE); while (true) { flag[i] = TRUE; turn = j; while ( flag[j] && turn == j ) ; // CRITICAL SECTION flag[i] = FALSE; // REMAINDER SECTION }

16 동기화 하드웨어(Synchronization Hardware)
락(lock)을 사용한 임계 구역 해법 do { acquire lock critical section release lock remainder section } while (TRUE); 프로세스는 임계 구역에 진입하기 전 반드시 락을 획득

17 동기화 하드웨어(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을 읽음 현대 컴퓨터는 특수 원자적 하드웨어(atomic hardware) 명령 제공 원자적으로 실행(executed atomically): 중간에 인터럽트 되지 않는(non-interruptible) 하나의 단위로 수행됨 하나의 기억장치 사이클 내에서 수행됨 운영체제

18 동기화 하드웨어(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(); Lab 6: Worker class 응용하여 두 개 스레드 동작으로 수정하기 운영체제

19 동기화 하드웨어(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  Lab 4: Worker class 응용하여 5개 스레드 동작으로 수정하기 운영체제

20 동기화 하드웨어(Synchronization Hardware)
/* Version 1 */ public class HardwareData { public HardwareData(boolean v) { data = v; } public boolean get() { return data; public void set(boolean v) { private boolean data; /* Version 2 */ public class HardwareData { public HardwareData(boolean v) { data = v; } public synchronized boolean get() { return data; public synchronized void set(boolean v) { private volatile boolean data; 운영체제

21 동기화 하드웨어(Synchronization Hardware)
/* Version 1 */ class HardwareSolution { public static boolean testAndSet(HardwareData target) { HardwareData temp = new HardwareData(target.get()); target.set(true); return temp.get(); } public static void swap(HardwareData a, HardwareData b) { HardwareData temp = new HardwareData(a.get()); a.set(b.get()); b.set(temp.get()); return b.get(); /* Version 2 */ class HardwareSolution { public synchronized static boolean testAndSet(HardwareData target) { HardwareData temp = new HardwareData(target.get()); target.set(true); return temp.get(); } public synchronized static boolean swap(HardwareData a, HardwareData b) { HardwareData temp = new HardwareData(a.get()); a.set(b.get()); b.set(temp.get()); return b.get(); 운영체제

22 Worker class 응용하여 두 개 스레드 동작으로 수정하기
/* testAndSet */ public class Worker extends Thread { public Worker(String n, HardwareData l) { name = n; lock = l; } public void run() { // The following is used to test the testAndSet instruction while (true) { while (HardwareSolution.testAndSet(lock)) Thread.yield(); // do nothing System.out.println(name + " In Critical Section"); try { Thread.sleep( (int) (Math.random() * 3000) ); catch (InterruptedException e) { } lock.set(false); System.out.println(name + " Out of Critical Section"); private String name; private volatile HardwareData lock; /* swap */ public class Worker extends Thread { public Worker(String n, HardwareData l) { name = n; lock= l; } public void run() { while (true) { HardwareData key = new HardwareData(true); key.set(true); while (HardwareSolution.swap(lock, key)) Thread.yield(); // do nothing // do { // HardwareSolution.swap(lock, key); // } while (key.get() == true); System.out.println(name + " In Critical Section"); try { Thread.sleep( (int) (Math.random() * 3000) ); catch (InterruptedException e) { } lock.set(false); System.out.println(name + " Out of Critical Section"); private String name; private volatile HardwareData lock; volatile: It specifies that the field is used by synchronized threads and that the compiler should not attempt to perform optimization with it. For example, it should read the variable’s value from the memory every time and not attempt to save a copy of it on the stack. 운영체제

23 Worker class 응용하여 두 개 스레드 동작으로 수정하기
public class Driver { public static void main(String args[]) { HardwareData lock = new HardwareData(false); Worker first = new Worker("Runner 0", lock); Worker second = new Worker("Runner 1", lock); first.start(); second.start(); } 운영체제

24 세마포어(Semaphores) Edsger Wybe 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); 운영체제

25 세마포어(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; 운영체제

26 세마포어(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; 운영체제

27 세마포어(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(); 운영체제

28 세마포어(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해결하는 방법임 운영체제

29 세마포어(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); 운영체제

30 세마포어(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); 운영체제

31 Linux에서 Wait Queue와 Semaphore
P(S) (= down(sem))에서 process status를 TASK_UNINTERRUPTIBLE로 uninterruptible하게 만들고 대기큐에 들어가고 CPU 스케줄러 호출하여 제어를 넘김 V(S) (=up(sem))에서 TASK_RUNNING으로 재활성화됨 (Linux Kernel Internals, 2nd Ed., p34~36 참조) struct wait_queue() { int task_struct *task; struct wait_queue *next; }; struct semaphore() { int count; struct wait_queue *wait; void add_wait_queue(struct wait_queue ** queue, struct wait_queue *entry); void remove_wait_queue(struct wait_queue ** queue, struct wait_queue *entry); 운영체제

32 Linux에서 Wait Queue와 Semaphore
P(S) 연산 void down(structure semaphore *sem) { while(sem->count <= 0) sleep_on(&sem->wait); sem->count--; } V(S) 연산 void up(structure semaphore *sem) sem->count++; wake_up(&sem->wait); void sleep_on(struct wait_queue **queue) { struct wait_queue entry = {current, NULL}; current->state=TASK_UNINTERRUPTIBLE; add_wait_queue(queue, &entry); schedule(); remove_wait_queue(queue, &entry); } void wake_up(struct wait_queue **queue) struct wait_queue *p = *queue; do p->task->state = TASK_RUNNING; p = p->next; } while(p != *queue); 운영체제

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

34 프로세스 협조(Cooperating Processes)
유한 버퍼 생산자-소비자 문제(bounded-buffer producer-consumer problem)  쓰레드(LWP)로 하면 효과적 Version 1: 공유 메모리를 이용한 해결책 (3.4.1절) Version 2: 메시지 전달을 이용한 해결책 (3.4.2절) Version 3: 세마포어를 이용한 해결책 (6.6.1절) Version 4: 세마포어와 스레드를 이용한 해결책 (6장 프로젝트 p266) Version 5: Java synchronization을 이용한 해결책 운영체제

35 유한버퍼 생산자-소비자 문제(The Bounded-Buffer Problem)
N buffers, each can hold one item Semaphore mutex initialized to the value 1 Semaphore full initialized to the value 0 Semaphore empty initialized to the value N The structure of the producer process do { // produce an item in nextp wait (empty); wait (mutex); // add the item to the buffer signal (mutex); signal (full); } while (TRUE); The structure of the consumer process do { wait (full); wait (mutex); // remove an item from buffer to nextc signal (mutex); signal (empty); // consume the item in nextc } while (TRUE);

36 판독자와 기록자 문제(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 → 다른 기아상태 없는 해법들 있음 운영체제

37 판독자와 기록자 문제(The Readers and Writers Problem)
Semaphore mutex initialized to 1 Semaphore wrt initialized to 1 Integer readcount initialized to 0 The structure of a reader process do { wait (mutex) ; readcount ++ ; if (readcount == 1) wait (wrt) ; signal (mutex) // reading is performed readcount - - ; if (readcount == 0) signal (wrt) ; signal (mutex) ; } while (TRUE); The structure of a writer process do { wait (wrt) ; // writing is performed signal (wrt) ; } while (TRUE); Q: 유형 1 인가? 유형 2 인가?

38 동기화의 고전적인 문제들(Classical Problems of Synchronization)
식사하는 철학자 문제(The Dining Philosophers Problem) Shared data Semaphore chopStick[] = new Semaphore[5]; 피터고라스 데카르트 플라톤 볼테르? 소크라테스 운영체제

39 식사하는 철학자 문제(The Dining Philosophers Problem)
Philosopher i: while (true) { // get left chopstick chopStick[i].P(); // get right chopstick chopStick[(i + 1) % 5].P(); // eat for a while //return left chopstick chopStick[i].V(); // return right chopstick chopStick[(i + 1) % 5].V(); // think for awhile } Semaphore chopStick[] = new Semaphore[5]; The structure of Philosopher i: do { wait ( chopstick[i] ); wait ( chopStick[ (i + 1) % 5] ); // eat signal ( chopstick[i] ); signal ( chopstick[ (i + 1) % 5] ); // think } while (TRUE); Semaphore chopstick [5] initialized to 1 운영체제

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

41 모니터(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) 프로그래머가 동기화 프로그래밍 하다 실수하는 대신 컴파일러가 정확한 프로그램 지원 운영체제

42 모니터(Monitors) monitor monitor-name { // shared variable declarations
procedure P1 (…) { …. } … procedure Pn (…) {……} Initialization code ( ….) { … } } 모니터 : 한 순간에 한 프로세스만이 모니터 안에서 활성화 되게 만들어진 고급언어 구조체 모니터를 powerful 하게 보완 → 모니터 + condition(프로그래머 재량) 한 procedure가 중간에 block되었다가 조건이 만족되면 다시 진행 P가 x.signal한 후의 처리(Q는 x.wait) (추천). Signal-and-Wait(Hoare와 Brinch-Hansen): P는 Q가 모니터를 떠나기를 기다리거나 다른 조건을 기다림 Signal-and-Continue: Q는 P가 모니터를 떠나기를 기다리거나 다른 조건을 기다림 (1+2) : Concurrent Pascal : P는 signal후 즉시 monitor를 떠나고 Q가 재시작 : 한 프로시주어 안에서 한 signal만 가능(signal이 모니터 프로시주어의 맨 마지막 줄에만 올 수 있게 하면 구현 간단) 운영체제

43 Monitor 구조 운영체제

44 조건 변수를 갖는 Monitor 운영체제

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

46 모니터(Monitors) x.wait x-count := x-count +1;
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 운영체제

47 모니터(Monitors) 식사하는 철학자 Version 2 : 교착상태 없는 식사하는 철학자들의 문제 해법 ②
이웃하는 철학자는 동시에 식사할 수 없게 하는 방법(과연 굶는 일이 있을까요? → Q: 있다|없다?) 철학자 작업 -> chopstick분배 dp.pick up(i) ...eat... dp.put down(i) 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 */ } public entry pickUp(int i) { state[i] = HUNGRY; test(i); if (state[i] != EATING) self[i].wait; } public entry putDown(int i) { state[i] = THINKING; // test left and right neighbors test((i + 4) % 5); test((i + 1) % 5); private test(int i) { if ( (state[(i + 4) % 5] != EATING) && (state[i] == HUNGRY) && (state[(i + 1) % 5] != EATING) ) { state[i] = EATING; self[i].signal; 운영체제

48 모니터를 이용한 식사하는 철학자 해법 monitor DP {
enum { THINKING; HUNGRY, EATING) state [5] ; condition self [5]; void pickup (int i) { state[i] = HUNGRY; test(i); if (state[i] != EATING) self [i].wait; } void putdown (int i) { state[i] = THINKING; // test left and right neighbors test((i + 4) % 5); test((i + 1) % 5); void test (int i) { if ( (state[(i + 4) % 5] != EATING) && (state[i] == HUNGRY) && (state[(i + 1) % 5] != EATING) ) { state[i] = EATING ; self[i].signal () ; } initialization_code() { for (int i = 0; i < 5; i++) state[i] = THINKING;

49 하나의 자원을 할당해 주는 모니터 monitor ResourceAllocator { boolean busy;
condition x; void acquire(int time) { if (busy) x.wait(time); busy = TRUE; } void release() { busy = FALSE; x.signal(); initialization code() { time: 자원을 사용할 최대 시간 모니터는 이중 가장 적은 시간을 희망한 프로세스에게 자원을 할당

50 Java Synchronization Thread safe: 여러 thread에 의해 동시에 접근되어도 데이터의 일관성(data consistency)을 보장할 수 있을 때 Synchronized Statement 모든 객체에는 하나의 락(lock)이 결합(associate)되어 있음 동기화 메소드(synchronized method)를 호출하려면 lock의 소유가 필요함 OS는 호출하는 스레드가 lock을 소유하고 있지 않으면(다른 스레드가 lock을 이미 소유한 경우임), 호출하는 스레드는 객체의 lock을 대기하는 wait set에 위치시킴 동기화 메소드(synchronized method)를 빠져 나갈 때 lock을 방출함 The wait() Method 스레드가 wait()를 호출하면: 스레드가 객체의 락을 방출 스레드 상태를 blocked로 설정 스레드는 wait set에 위치 Notify Method 스레드가 notify()를 호출하면: wait set로부터 임의의 스레드 T 를 선택 T를 entry set에 위치 T를 Runnable로 설정 T 는 다시 객체의 락을 얻기 위해 경쟁 운영체제

51 Multiple Notifications
notify() 는 wait set로부터 임의의 스레드를 선택 원하는 스레드를 선택할 수 없음 Java에서는 선택될 스레드를 명시할 수 없음 notifyAll()은 wait set로부터 모든 스레드를 제거하여 entry set에 위치시킴 이 들 중에서 다음에 진행될 스레드가 결정됨 notifyAll()은 wait set에 다수의 스레드가 있을 때 가장 잘 동작하는 신중한(conservative) 방법임 운영체제

52 Java Synchronization Entry Set 운영체제

53 Java Synchronization Entry and Waits Set 운영체제

54 Java Synchronization <synchronized 와 yield() 이용한 Bounded Buffer> : 코딩할 것 deadlock 가능 (어떻게? 왜?) Synchronized enter() Method public synchronized void enter(Object item) { while (count == BUFFER_SIZE) Thread.yield(); ++count; buffer[in] = item; in = (in + 1) % BUFFER_SIZE; } Synchronized remove() Method public synchronized Object remove() { Object item; while (count == 0) Thread.yield(); --count; item = buffer[out]; out = (out + 1) % BUFFER_SIZE; return item; } 운영체제

55 DoWork() public class DoWork {
// pnum is the number of the thread that wishes to do some work public synchronized void DoWork(int pnum) { while (turn != pnum) { try { wait(); } catch (InterruptedException e) {} // do some work for awhile System.out.println("Worker " + pnum + " will do some work"); Thread.sleep( (int) (Math.random() * 3000) ); catch (InterruptedException e) { } // ok, we're finished. Now indicate to the next waiting // thread that it is their turn to do some work. System.out.println("Worker " + pnum + " is done working"); if (turn < 5) ++turn; else turn = 1; // change this to notifyAll() to see it run correctly! notify(); private int turn = 1; 운영체제

56 DoWork() public class Worker extends Thread public class TestIt { {
public Worker(DoWork p, String n, int i) { pile = p; name = n; num = i; } public void run() { while (true) { Runner.slacking(); pile.DoWork(num); private DoWork pile; private String name; private int num; public class Runner public static void slacking() { try { Thread.sleep( (int) (Math.random() * 3000) ); catch (InterruptedException e) { } public class TestIt { public static void main(String args[]) { DoWork pile = new DoWork(); Worker[] bees = new Worker[5]; for (int i = 1; i <= 5; i++) bees[i-1] = new Worker(pile, “Worker” + (new Integer(i)).toString(), i); bees[i-1].start(); } 운영체제

57 Solaris에서의 동기화(Synchronization in Solaris)
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 가능하므로) Turnstile : 객체의 락 때문에 봉쇄된 스레드들을 수용하는 큐, 각 스레드별로 하나씩 존재, 우선순위 역전(priority inversion) 방지 위해 우선순위상속 프로토콜(priority inheritance protocol) 사용 커널의 락킹 메커니즘은 사용자 수준 스레드도 그대로 사용 가능, 단 커널 락킹만 커널 우선순위 상속함 (kernel priority inheritance) 운영체제

58 Windows XP의 동기화 (Synchronization in Windows XP)
다중 처리기 다중 쓰레드 커널 단일 처리기 시스템에서 커널이 전역 자원(global resources) 접근할 때에는 다른 인터럽트 핸들러가 실행되지 않도록 잠시 인터럽트를 중지 시키는 인터럽트 마스크(interrupt mask)를 사용하여 전역 자원 접근 보호 다중 처리기 시스템에서는 짧은 코드에 대해서 스핀락(spinlocks) 사용하여 전역 변수 보호 뮤텍스(mutexes) 또는 세마포어(semaphores) 처럼 동작하는 디스패처 (dispatcher) 객체제공 Nonsignaled: lock을 획득한 상태 Signaled: lock을 방출한 상태 디스패처 객체는 조건 변수(condition variable)와 유사한 사건(events) 객체 제공 운영체제

59 Linux의 동기화 (Synchronization in Linux)
kernel Version 2.6, 이전에는 짧은 임계 구역(critical section) 수행 도중 인터럽트(선점) 불가능(disables interrupts) Version 2.6 이후에는 우선순위에 따라 완전 선점 가능(fully preemptive) Linux 는 락킹(locking)을 위해 세마포(semaphore)와 스핀락(spinlock) 제공 semaphores: 긴 임계 구역에 사용 spinlocks: 짧은 임계 구역에 사용, SMP 기본 락킹 기법 단일 처리기: 커널 모드 태스크가 락을 소유하고 있으면 커널은 선점 불가능 preempt_disable(), preempt_enable() 시스템 호출 사용 다중 처리기: spinlock 획득, spinlock 방출 reader-writer locks Semaphore mutex initialized to 1 Semaphore wrt initialized to 1 Integer readcount initialized to 0 운영체제

60 Pthread의 동기화 (Synchronization in Pthread)
Pthreads API는 OS 독립적(OS-independent) POSIX 동기화 도구 mutex locks(초기값=1) condition variables(초기값=0) read-write locks POSIX SEM(Non-portable extensions) 제공 도구 semaphores spinlocks 운영체제

61 원자적 트랜잭션 (Atomic Transaction)
시스템 모델(System Model) 로그 기반 복구(Log-based Recovery): 한 순간에 한 트랜잭션 활성화 검사점(Checkpoints) 동시 수행 원자적 트랜잭션(Concurrent Atomic Transactions): 다수 트랜잭션이 동시에 활성화 트랜잭션의 원자성 = 자료의 일관성 유지를 위해 추구하는 데이터베이스 기법 운영체제

62 시스템 모델(System Model) 컴퓨터 시스템 안에서 어떤 고장이 발생하더라도 트랜잭션(Transaction)의 원자성(atomicity)은 반드시 보장되어야 함 하나의 논리적인 단위로 발생하거나 전혀 발생하지 않도록 해야 함 데이터베이스 시스템의 필드와 관련됨 Transaction – 하나의 논리적인 기능을 수행하는 명령(또는 연산)의 집합 비휘발성 저장장치인 디스크 내 파일 형태의 자료 항목 갱신 Transaction은 일련의 read 와 write 연산의 연속 commit (transaction successful) 또는 abort (transaction failed) 연산으로 끝남 abort transaction은 만일 변경이 수행되었다면 반드시 rolled back 되어야 함

63 저장장치 형태(Types of Storage Media)
휘발성 저장장치(volatile storage) – 시스템이 고장나면 정보는 사라짐 Example: main memory, cache 비휘발성 저장장치(nonvolatile storage) – 시스템이 고장나도 정보는 항상 보존됨 Example: disk and tape 안전 저장장치(stable storage) – 정보는 결코 손실되지 않음 고장에 영향을 받지 않는 독립적인 비휘발성 장치(RAID, redundant array of independent disk)에 중복 기록 목표는 시스템 고장이 났을 때 자료 손실의 가능성이 있는 비휘발성 저장장치에서 transaction atomicity 를 보장하는 것

64 로그 기반 복구(Log-based Recovery)
한 순간에 하나의 트랜잭션만 수행되는 환경에서 로그에 기반하여 트랜잭션에 의한 모든 변경을 안전 저장장치(stable storage)에 기록 가장 많이 사용되는 방법은 write-ahead logging 안전 저장장치에 기록되는 각 로그 레코드는 하나의 트랜잭션의 쓰기 연산을 설명 Transaction name Data item name Old value New value 트랜잭션 시작 전 <Ti starts> 로그에 기록 트랜잭션이 완료(commit)되면 <Ti commits> 로그에 기록

65 로그 기반 복구(Log-based Recovery)
로그를 사용하면 휘발성 저장장치(volatile memory)의 오류를 관리할 수 있음 Undo(Ti): 트랜잭션 Ti 이전의 값으로 복구restores value of all data updated by Ti Redo(Ti): 트랜잭션 Ti 의 새로운 값으로 변경 undo(Ti) 와 redo(Ti) 는 반드시 멱등(idempotent; 여러 번 수행해도 한 번 수행한 것과 동일)해야 함 시스템이 고장나면, 로그를 보면서 갱신된 모든 자료를 복구 로그에 <Ti starts> 레코드 있고 <Ti commits> 레코드가 없으면 → undo(Ti) 로그에 <Ti starts> 레코드와 <Ti commits> 레코드가 있으면 → redo(Ti)

66 검사점(Checkpoints) 로그 기반 복구는 로그 전체를 조사해야 하므로 시간 소모가 많음
휘발성 저장장치에 있던 현재까지의 모든 로그 레코드를 안전 저장장치에 출력 휘발성 저장장치에서 현재까지 갱신된 모든 자료를 안전 저장장치에 출력 <checkpoint>라는 로그 레코드를 안전 저장장치에 출력 가장 최근의 검사점 이전에 수행이 시작(starts)된 가장 최근의 트랜잭션 Ti 와 검사점 이후에 시행된 모든 트랜잭션 Tj 들만 복구하면 됨 <Tk commits>가 최근의 검사점 이후의 로그에 기록되어 있으면 redo(Tk) <Tk commits>가 최근의 검사점 이후의 로그에 기록되어 있지 않으면 undo(Tk)

67 동시 수행 원자적 트랜잭션(Concurrent Atomic Transactions)
한 순간에 다수의 트랜잭션이 동시에 활성화 되는 환경에서 병렬로 수행되었더라도 순차적으로 실행시킨 것과 같아야 함: 직렬가능성 (serializability) 모든 트랜잭션을 임계 구역(critical section) 안에서 수행시키면 됨 세마포어 mutex(초기값 1) 사용, wait(mutex)과 signal(mutex)으로 구현 가능 → 그러나 병렬수행을 원천적으로 제한하여 비 효율적 동시성 제어 알고리즘(Concurrency-control algorithms) 들이 직렬가능성(serializability) 보장해 줄 수 있음 스왑에 의한 직렬가능성(serializability) 락킹 프로토콜(Locking Protocol) 타임 스탬프 기반 프로토콜(Timestamp-based Protocols)

68 직렬가능성(Serializability)
2개 트랜잭션 T0 와 T1 T0, T1 순서로 원자적(atomically) 수행 가정 수행 순서를 스케줄(schedule)이라 함 원자적으로 수행된 스케줄 순서(atomically executed transaction order) 를 직렬 스케줄(serial schedule) 이라 함: 원자적 수행이므로 올바른(correct) 스케줄 N 개 트랜잭션에 대해, N! 개의 유효한 직렬 스케줄(valid serial schedules) 가능 비직렬 스케줄(Nonserial Schedule) 비직렬 스케줄(Nonserial schedule)은 수행 중첩을 허용 → 비직렬 스케줄(nonserial schedule)이 반드시 잘못된(incorrect) 스케줄은 아님 스케줄 S의 연산 Oi, Oj 를 연속 수행할 때, 동일한 자료 항목에 접근하며 적어도 하나가 쓰기 연산일 때 연산 Oi, Oj 는 충돌(Conflict) 한다고 말함 만일 연속된 Oi, Oj 이 서로 다른 트랜잭션에 속해 있고 충돌하지 않는다면 스케줄 S의 연산의 순서를 스왑(swap)한 스케줄 S’의 Oj, Oi 는 동등(equivalent)함 만일 스케줄 S의 비충돌(nonconflicting) 연산들을 스왑하여 직렬 스케줄 S’로 변환시킬 수 있다면 → S’ 는 충돌 직렬가능(conflict serializable)함

69 (Concurrent Serializable Schedule)
Schedule 1: T0 then T1 T0 read(B)와 T1 read(A) 스왑 T0 write(B)와 T1 write(A) 스왑 T0 write(B)와 T1 read(A) 스왑? 직렬 스케줄 (Serial Schedule) 동시수행 직렬가능 스케줄 (Concurrent Serializable Schedule)

70 락킹 프로토콜(Locking Protocol)
각 자료 항목마다 락(lock)을 결합(associate)하여 직렬가능성(serializability)을 보장 by associating lock with each data item 락킹 프로토콜 공유(Shared) – Ti has shared-mode lock (S) on item Q, Ti can read Q but not write Q 독점(Exclusive) – Ti has exclusive-mode lock (X) on Q, Ti can read and write Q 항목 Q 에 대한 모든 트랜잭션은 적절한 모드의 락을 요청함 만일 락이 이미 사용 중이면 새로운 요청은 락이 사용가능할 때까지 기다림(readers-writers algorithm과 유사) 두 단계 락킹 프로토콜(Two-phase Locking Protocol) 마지막 접근이 끝나자마자 바로 락을 해제하면 직렬가능성이 보장되지 않을 수 있기 때문에 충돌 직렬가능성(conflict serializability) 보장해 주는 프로토콜 필요 각 트랜잭션은 lock과 unlock 요청을 아래 두 단계로 수행 확장단계(Growing) – obtaining locks(락의 확득만 가능, 반납 불가능) 수축단계(Shrinking) – releasing locks(락의 반납만 가능, 획득 불가능) 교착상태(deadlock) 발생 가능

71 타임스탬프 기반 프로토콜(Timestamp-based Protocols)
미리 트랜잭션들의 순서를 결정 – timestamp-ordering 트랜잭션 Ti 시작 직전 시스템이 Ti 에 타임스탬프 TS(Ti) 부여 TS(Ti) < TS(Tj) 만일 Ti 가 Tj 이전에 부여되었으면 TS 는 매 트랜잭션 마다 시스템 클록(system clock )으로부터 생성하거나 논리 계수기(logical counter)를 증가시켜 생성 타임스탬프로 직렬화 순서 결정 만일 TS(Ti) < TS(Tj)이면, 시스템은 트랜잭션 Ti 처리 후 트랜잭션 Tj 처리하는 직렬 스케줄(serial schedule)과 동등(equivalent)한 스케줄 생성을 보장해 주어야 함 자료 항목 Q 마다 2개 타임스탬프 부여 W-timestamp(Q) – 성공적으로 끝낸 write(Q)의 타임스탬프 중 가장 큰 값 R-timestamp(Q) – 성공적으로 끝낸 read(Q) 중 가장 큰 값 (매 read(Q) 또는 write(Q) 가 수행될 때마다 갱신됨)

72 타임스탬프 순서 프로토콜(Timestamp-ordering Protocol)
타임스탬프 순서 프로토콜(Timestamp-ordering protocol)은 모든 충돌하는 read와 write 연산들이 타임스탬프 순서대로 수행됨을 보장함 트랜잭션 Ti 가 read(Q)를 수행했을 때: 만일 TS(Ti) < W-timestamp(Q)이면, Ti 이미 겹쳐써(overwritten) 사라진 Q의 값을 읽으려고 하므로 read 연산은 거부되고, Ti는 롤백(rolled back)됨 만일 If TS(Ti) ≥ W-timestamp(Q)이면, read 는 수행되고, R-timestamp(Q)는 R-timestamp(Q)와 TS(Ti)중 큰 값으로 설정됨(max(R-timestamp(Q), TS(Ti))) 트랜잭션 Ti 가 write(Q)를 수행했을 때: 만일 TS(Ti) < R-timestamp(Q)이면, Ti에 의해 생성된 Q 값은 이미 과거에 필요했었고 Ti 는 이 값이 다시 생성되지 않음을 가정하므로 Write 연산은 거부되고, Ti는 롤백(rolled back)됨 만일 TS(Ti) < W-tiimestamp(Q)이면, Ti 는 이미 소용없게된 값을 Q 에 쓰려는 것이므로 기타의 경우에는, write 연산을 수행함 롤백된 트랜잭션 Ti 에는 새 타임스탬프가 부여되고 처음부터 다시 시작됨 타임스탬프 순서 프로토콜은 충돌 직렬가능성(conflict serializability)을 보장함 교착상태(deadlock) 없음

73 타임스탬프 프로토콜에 의해 가능한 스케줄