Module 7: Process Synchronization

Chapter 6: Process Synchronization ( 프로세스동기화 ), Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Module 6: Synchronization( 동기화 ) Background( 배경 ) The Critical-Section Problem( 임계구역문제 ) Peterson s Solution( 피터슨솔루션 ) Synchronization Hardware( 동기화하드웨어 ) Semaphores( 세마포 ) Classic Problems of Synchronization( 고전적동기화문제들 ) Monitors( 모니터 ) Synchronization Examples ( 동기화사례 ) Atomic Transactions( 원자적트랜잭션 ) 6.2 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Objectives To introduce the critical-section problem, whose solutions can be used to ensure the consistency of shared data( 공유데이터의일관성을보장하기위한임계구역문제소개 ) To present both software and hardware solutions of the critical-section problem( 임계구역문제의소프트웨어및하드웨어솔루션 ) To introduce the concept of an atomic transaction and describe mechanisms to ensure atomicity( 원자적트랜잭션의개념을소개하고원자성을보장하기위한매카니즘을기술한다.) 6.3 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Background Concurrent access to shared data may result in data inconsistency ( 공유데이터의동시접근은데이터의불일치를초래할수있다.) Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes ( 데이터의일관성을유지하기위해서는프로세스들의실행순서를보증하는메커니즘이요구된다.) Suppose that we wanted to provide a solution to the consumerproducer problem that fills all the buffers. We can do so by having an integer count that keeps track of the number of full buffers. Initially, count is set to 0. It is incremented by the producer after it produces a new buffer and is decremented by the consumer after it consumes a buffer. ( 모든버퍼를사용하는소비자 - 생산자문제에서 count 변수를이용하여소비실행순서를보증하였다.) 6.4 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Previous Producer-Consumer (3.4.1) Bounded Shared Buffer Producer process item nextproduced; while (true) { /* Produce an item in nextproduced */ while ((((in + 1) % BUFFER_SIZE) == out) ; /* do nothing -- no free buffers */ buffer[in] = nextproduced; in = (in + 1) % BUFFER SIZE; Shared Data Consumer process item nextconsumed; while (true) { while (in == out) ; // do nothing -- nothing to consume nextconsumed = buffer[out]; // remove an item from the buffer out = (out + 1) % BUFFER SIZE; /* consume the item in nextconsume */ At most BUFFER_SIZE-1 items in the buffer of BUFFER_SIZE #define BUFFER_SIZE 10 typedef struct {... item; item buffer[buffer_size]; int in = 0; //used by producer int out = 0; //used by consumer 6.5 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Previous Producer-Consumer (3.4.1) New Shared Buffer with counter Producer process while (true) { /* produce an item and put in nextproduced */ while (count == BUFFER_SIZE) ; // do nothing buffer [in] = nextproduced; in = (in + 1) % BUFFER_SIZE; count++; Consumer process while (true) { while (count == 0) ; // do nothing nextconsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; count--; /* consume the item in nextconsumed Allow full buffer, BUFFER_SIZE items in the buffer of BUFFER_SIZE Modified Producer Consumer define BUFFER_SIZE 10 typedef struct {... item; item buffer[buffer_size]; int in = 0; int out = 0; int counter = 0; 6.6 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Bounded Buffer The statements counter++; counter--; must be performed atomically ( 원자적으로연산되어야한다.) Atomic operation means an operation that completes in its entirety without interruption ( 원자연산은외부의인터럽트없이완전히실행되는연산이다.) 6.7 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Race Condition( 경합상태 ) 경합상태 (race condition) : 두개의프로세스가경쟁적으로한변수를조작 ( 예 ) 공유변수 count 의변경명령이동시에수행될경우불일치발생 생산자의 count ++ register1 = count; register1 = register1 + 1; count = register1; 소비자의 counter -- 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 만접근하게해야함 6.8 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

An Example Withdraw money from a bank account( 은행계좌인출문제 ) Suppose you and your girl(boy) friend share a bank account with a balance of 1,000,000won What happens if both go to separate ATM machines, and simultaneously withdraw 100,000won from the account? ( 은행의 100 만원을두사람이다른 ATM 에서인출을동시에시도한다 ) int withdraw (account, amount) { balance = get_balance (account); balance = balance - amount; put_balance (account, balance); return balance; 6.9 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

An Example (Cont d) Interleaved schedules Represent the situation by creating a separate thread for each person to do the withdrawals The execution of the two threads can be interleaved, assuming preemptive scheduling: 6.10 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Solution to 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.11 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Solution to Critical-Section Problem General structure for a typical process Pi do { entry section exit section critical section remainder section while (TRUE); 6.12 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Mechanisms for Critical Sections Locks Very primitive, minimal semantics, used to build others Semaphores Basic, easy to get the hang of, hard to program with Monitors High-level, requires language support, implicit operations Easy to program with: Java synchronized Messages Simple model of communication and synchronization based on (atomic) transfer of data across a channel Direct application to distributed systems 6.13 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Locks Very primitive, minimal semantics, used to build others Software Solutions Peterson s Solution for two process Bakery Algorithm for n processes Hardware Solutions Mutual Exclusion solution using TestAndSet Mutual Exclusion Solution using Swap Instruction Bounded Mutual Exclusion solution using TestAndSet 6.14 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Locks A lock is an object (in memory) that provides the following two operations: acquire(): wait until lock is free, then grab it (lock 가해제될때까지가다린후해제되면잡는다 ) release(): unlock, and wake up any thread waiting in acquire() ( 해제, 대기중인쓰레드를활성화한다 ) Using locks Lock is initially free Call acquire() before entering a critical section, and release() after leaving it Between acquire() and release(), the thread holds the lock acquire() does not return until the caller holds the lock At most one thread can hold a lock at a time Locks can spin (a spinlock) or block (a mutex) A mutex is an object in a program that serves as a lock and used to negotiate mutual exclusion among threads. 6.15 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Using Locks 6.16 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Implementing Locks (Cont d) Problem Implementation of locks has a critical section, too! The acquire/release must be atomic A recursion, huh? Atomic operation Executes as though it could not be interrupted Code that executes all or nothing Solutions Software-only algorithms Algorithm for two processes Bakery algorithm for more than two processes Hardware atomic instructions Test-and-set, compare-and-swap, etc. Disable/re-enable interrupts To prevent context switches 6.17 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Initial Attempts to Solve Problem Only 2 processes, P0 and P1 General structure of process Pi (other process Pj) do { entry section critical section exit section remainder section while (1); Processes may share some common variables to synchronize their actions Entry section Acquire a lock Exit section Release a lock 6.18 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Peterson s Solution(software) 2개프로세스의 S/W 임계구역문제해법 LOAD 와 STORE 명령은원자적 (atomic) 즉, 수행도중절대인터럽트되지않음 2개프로세스가아래 2개변수공유 : int turn; Boolean flag[2] 변수 turn 은어느임계구역진입순번표시 The flag 배열은임계구역진입준비됨표시 flag[i] = true 는 process P i 가준비되었음! 6.19 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Algorithm for Process P i in Peterson s solution The structure of process Pi do { flag[i] = TRUE; turn = j; //trigger Pj while (flag[j] && turn == j); critical section flag[i] = FALSE; remainder section while (TRUE); The structure of process Pj do { flag[j] = TRUE; turn = i; //trigger Pi while (flag[i] && turn == i); flag[j] = FALSE; while (TRUE); critical section remainder section Pi enter CS only when frag[j]==false or turn==i 동시시도시 frag[i]==frag[j]==true => turn 값배타적, 상대방 trigger 6.20 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Bakery Algorithm Critical section for n processes(n 개프로세스에대한임계구역문제 ) Before entering its critical section, process receives a number. Holder of the smallest number enters the critical section If processes Pi and Pj receive the same number, if i < j, then Pi is served first; else Pj is served first The numbering scheme always generates numbers in increasing order of enumeration; i.e., 1,2,3,3,3,3,4,5... 최소번호수령 작은번호를받은프로세스가먼저실행한다. 6.21 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Bakery Algorithm Notation < lexicographical order (ticket #, process id #) (a,b) < (c,d) if a < c or if a = c and b < d max (a 0,, a n-1 ) is a number, k, such that k >= a i for i = 0,, n 1 Shared data boolean choosing[process]; // 우선순위받는기간의미 int priority[process]; // process : process id # Data structures are initialized to false and 0 respectively 6.22 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Bakery Algorithm Shared Varialbes boolean choosing[p]; // 우선순위받기위한대기상태 int priority[p]; // p : process id initially choosing[..]=false; prioty[..]=0; do { choosing[p] = true; // 프로세스 p 가우선순위받는모드진입 priority [p] = max(priority[0], priority[1],, priority[n 1])+1; choosing[p] = false; // // 프로세스 p 가우선순위받는모드종료 for (j = 0; j < n; j++) { while (choosing[j]) ; // 우선순위받는중이면대기 while ((priority[j]!= 0) && ((priority[j],j)< (priority[p], p))) ; critical section priority[p] = 0; remainder section while (1); // 다른프로세스가우선하면그프로세스의처리까지대기 6.23 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Synchronization Hardware Many systems provide hardware (instruction) support for critical section code Uniprocessors could disable interrupts( 입터럽트무력화 ) Currently running code would execute without preemption Generally too inefficient on multiprocessor systems Operating systems using this not broadly scalable Modern machines provide special atomic hardware instructions Atomic = non-interruptable Either test memory word and set value Or swap contents of two memory words 6.24 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Synchronization Hardware General s/w solution to Critical-section Problem Using Locks do { acquire lock critical section release lock remainder section while (TRUE); 6.25 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Mutual Exclusion solution using TestAndSet Mutual Exclusion using TestAndSet (hardware) instruction Shared boolean variable lock., initialized to false. Process Pi for mutual exclusion using TestAndSet atomic instruction initially lock =false; // global variable do { while ( TestAndSet (&lock )) ; // critical section lock = FALSE; // remainder section while (TRUE); //hardware, Atomic instruction boolean TestAndSet (boolean *target { boolean rv = *target; *target = TRUE; return rv: do { while ( TestAndSet (&lock )) ; // critical section lock = FALSE; // remainder section while (TRUE); 6.26 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Mutual Exclusion Solution using Swap Instruction Mutual Exclusion Solution using Swap Shared Boolean variable lock initialized to FALSE; Each process has a local Boolean variable key Process Pi for mutual exclusion using Swap atomic instruction: initially lock=false //shared do { key = TRUE; //local variable while ( key == TRUE) Swap (&lock, &key ); // critical section lock = FALSE; // remainder section while (TRUE); void Swap (boolean *a, boolean *b) //hardware { boolean temp = *a; *a = *b; *b = temp: do { key = TRUE; //local variable while ( key == TRUE) Swap (&lock, &key ); // critical section lock = FALSE; // remainder section while (TRUE); 6.27 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Bounded-waiting Mutual Exclusion with TestandSet() ( 유한대기상호배제소루션 ) do { waiting[i] = TRUE; // key = TRUE; while (waiting[i] && key) //proceed when waiting[i]==false or key(lock)=false key = TestAndSet(&lock); waiting[i] = FALSE; // critical section j = (i + 1) % n; while ((j!= i) &&!waiting[j]) // i다음의대기중인프로세스를활성화한다. Bounded waiting 보장 j = (j + 1) % n; if (j == i) lock = FALSE; // lock= false로하여다른프로세스에게허용 else waiting[j] = FALSE; // lock==true 인상태에서 Pj에서 wile문장을지나 critical section 진입하게한다. // remainder section while (TRUE); 6.28 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

세마포어 (Semaphore concept) Semaphore is A kind of general synchronization tool Aslo is able to be sued as a synchronization tool that does not require busy waiting Semaphore( 신호기 ) S : 원자적함수 wait() 과 signal() 로접근되는정수변수 S originally called P() and V(), (P from Duch proberen, to test. V from verhogen, to increment ) wait (S) { //atomic operation S:semaphor variable while (S <= 0) ; // S>0 때까지대기 S--; signal (S) { //atomic operation S++; 6.29 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Usage of Semaphor Two types of semaphore Counting semaphore 무제한정수처리, N 개의자원관리공유시 Binary semaphore 정수 0,1,mutex locks An example of Binary semaphore Process p with mutual exclusion using semaphore mutex. Semaphore mutex=1; // initialized to 1 Shared data do { wait (mutex); // 1->0 or 다른프로세스가 1 로설정할때까지 busy waiting // Critical Section signal (mutex); // 0->1 // remainder section while (TRUE); An example of Counting semaphore N 개의공유자원을이용하기위한상호배제 Semaphore res=n ; // 공유자원수 : N do { Wait(res) //res 자원이용하기전 N==0이면모든자원이사용중 // Critical Section Signal(res) //res++ 자원이용후 // remainder section while(true); 6.30 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Semaphore Implementation with no Busy waiting 기본개념 Wait 연산의대기를무한반복대신에대기큐에서수행되도록하여시스템의효율을증가시킨다. Semaphore 구조 typedef struct { int value; // struct process *L; //pointer to next record in the list semaphore; Two operations: block 프로세스를대기큐에추가하고일시중지 suspends the process, place the process invoking the operation on the appropriate waiting queue. wakeup 대기중인큐의포세스한개를분리하여 ready 큐에삽입하여실행을재개한다. resumes the execution of a blocked process, remove one of processes in the waiting queue and place it in the ready queue. 6.31 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Semaphore Implementation with no Busy waiting (Cont.) Implementation of wait: wait(semaphore *S) { S->value--; //-value 의 value 는대기중인 process 의수이다. if (S->value < 0) { add this process to S->list; //add itself onto waiting list block(); // 자신의프로세스는대기큐로이동 / 실행중지 // 0 : 다른프로세스실행방지시키고자신은계속실행 Implementation of signal: signal(semaphore *S) { S->value++; if (S->value <= 0) { remove a process P from S->list; wakeup(p); // OS scheduler 의 ready queue 로이동시킨다. // >=1 : 다른프로세스실행을허용 6.32 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Deadlock and Starvation Deadlock 예 two or more processes are waiting indefinitely for an event(signal()) that can be caused by only one of the waiting processes ( 둘또는그이상의프로세스들이대기중인프로세스중하나가발생시킬이벤트를무한정기다리고있는상태 ) Let S and Q be two semaphores initialized to 1 where two processes P1,P2 ( 프로세스 P1,P2 가 3 개의세마포 S,M 를다음과같이사용하면발생가능 ) P 0 P 1 wait (S); wait (Q); wait (Q); wait (S);.... signal (S); signal (S); signal (Q); Starvation signal (Q); indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended. (P0,P1 모두세마포대기큐에추가된상태면영원히재실행이불가하다.) 6.33 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

6.6 Classical Problems of Synchronization Bounded-Buffer Problem Readers and Writers Problem Dining-Philosophers Problem Semaphore 변수사용 6.34 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Bounded Buffer Problem Synchronization with critical problem initially in=out=counter=0 35 6.35 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Bounded Buffer Problem (Cont d) Implementation with semaphores 36 6.36 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

C# Implementation with semaphores using C# language Mutex mutex = new Mutex() Semaphore empty = new Semaphore(N,N): Semaphore full =new Semaphore(0,N): void Produceer { while (true) { T t = Produce(); empty.waitone(); //empty mutex.waitone(); //mutex Append(t); mutex.releasemutex(); //mutex++ full.release(); //full++ void Consume er { while (true) { full.waitone(); //full mutex.waitone(); //mutex T t = Take(); mutex.releasemutex(); //mutex++ empty.release(); //empty-- Consume(t); 37 6.37 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Semaphore 와 mutex 를이용한생산자 - 소비자문제 (C#) using System.Text; using System.Threading; abstract class ProCon<T> { public ProCon(int maxbuffersize) { this.maxbuffersize = maxbuffersize; mutex = new Mutex(); full = new Semaphore(0, maxbuffersize); empty = new Semaphore(maxBufferSize, maxbuffersize); public void Producer(){ public void Consumer(){ abstract public T Take(); abstract public void Append(T t); abstract public T Produce(); abstract public void Consume(T t); class MyProCon : ProCon<string> { protected List<string> list; public MyProCon(int maxsize) : base(maxsize) { list = new List<string>(maxSize); override public T Take() { override public void Append(T t) { override public T Produce() { override public void Consume(T t) { class Program { public static void Main(string[] args) { MyProCon m = new MyProCon(4); Thread pro = new Thread(m.Producer); pro.start(); // Thread pro2 = new Thread(m.Producer); //pro2.start(); Thread con = new Thread(m.Consumer); con.start(); Thread.Sleep(10000); //10 초정지 pro.suspend(); con.suspend(); //pro.join(); //con.join(); 6.38 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

abstract class ProCon<T> { protected readonly int maxbuffersize; protected Mutex mutex; protected Semaphore full; protected Semaphore empty; public ProCon(int maxbuffersize) { this.maxbuffersize = maxbuffersize; mutex = new Mutex(); full = new Semaphore(0, maxbuffersize); empty = new Semaphore(maxBufferSize, maxbuffersize); public void Producer() { while (true) { T t = Produce(); empty.waitone(); //empty-- mutex.waitone(); //mutex-- Append(t); mutex.releasemutex(); //mutex++ full.release(); //full++ public void Consumer() { while (true) { full.waitone(); //full-- mutex.waitone(); //mutex-- T t = Take(); mutex.releasemutex(); //mutex++ empty.release(); //empty++ Consume(t); //codes of critical section abstract public T Take(); abstract public void Append(T t); //non critical section abstract public T Produce(); abstract public void Consume(T t); class MyProCon : ProCon<string> { protected List<string> list; public MyProCon(int maxsize) : base(maxsize) { list = new List<string>(maxSize); // 데이터추가 ( 저장 ) //critical codes override public void Append(string t) { list.add(t); string s = ""; foreach (string a in list) s += a + " "; Console.WriteLine(Thread.CurrentThread.ManagedThreadId + "\tadd : " + list.count + "\t:" + s); //Thread.Sleep(1000); // 데이터소비 //critical codes : override public string Take() { string t = list[0]; list.removeat(0); string s=""; foreach (string a in list) s += a + " "; Console.WriteLine(Thread.CurrentThread.ManagedThreadId+"\tTake: " + list.count + "\t:" +s); Thread.Sleep(2000); return t; // 데이터생성 override public string Produce() { Random r = new Random(); int i = r.next(10); Console.WriteLine(Thread.CurrentThread.ManagedThreadId + "\tpro: " +i); return i.tostring(); // 데이터처리 override public void Consume(string t) { Console.WriteLine(Thread.CurrentThread.ManagedThreadId + "\tcon: " + t); 6.39 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

실행결과분석 void Main() { MyProCon m = new MyProCon(4); Thread pro = new Thread(m.Producer); Thread con = new Thread(m.Consumer); pro.start(); con.start(); Thread.Sleep(10000); //10 초정지 pro.suspend(); con.suspend(); Producer while (true) { 1 T t = Produce(); 2 empty.waitone(); //empty-- 3 mutex.waitone(); //mutex-- 4 Append(t); 5 mutex.releasemutex(); //mutex++ 6 full.release(); //full++ Consumer while (true) { 1 full.waitone(); //full 2 mutex.waitone(); //mutex 3 T t = Take(); 4 mutex.releasemutex(); //mutex++ 5 empty.release(); //empty++ 6 Consume(t); 3 1 Pro: 4 3 4 add : 1 :4 3 1 Pro: 4 4 3 Take: 0 : 3 4 add : 1 :4 3 1 Pro: 2 3 4 add : 2 :4 2 3 1 Pro: 2 3 4 add : 3 :4 2 2 3 Pro: 2 3 add : 4 :4 2 2 2 3 Pro: 2 4 Con: 4 4 Take: 3 :2 2 2 4 Con: 4 3 add : 4 :2 2 2 2 4 Take: 3 :2 2 2 3 Pro: 1 4 Con: 2 3 add : 4 :2 2 2 1 4 Take: 3 :2 2 1 3 Pro: 9 4 Con: 2 3 add : 4 :2 2 1 9 3 Pro: 8 4 Take: 3 :2 1 9 4 Con: 2 6.40 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Readers-Writers Problem 복수의 reader 및 writer 프로세스들이데이터집합을공유하는문제 Readers 읽기전용, 복수의프로세스읽기가능, 수정불가능 Writers 읽고쓰기가능, writer 프로세스들끼리배타적공유 6.41 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Shared Data, initially Readers-Writers Problem (Cont.) Semaphore mutex =1 //readcount 갱신시상호배제용 Semaphore wrt = 1 //writer 상호배제 Integer readcount =0 // reading process The structure of a writer process do { wait (wrt) ; //writing is performed //wrt=0 signal (wrt) ; //wrt=1 while (TRUE); The structure of a reader process do { wait (mutex) ; //mutex=0 readcount ++ ; if (readcount == 1) wait (wrt); // 첫번째 reading 시부터읽는동안 write 금지 signal (mutex) // reading is performed, // 복수프로세스가동시읽기가능 wait (mutex) ; readcount - - ; if (readcount == 0) signal (wrt) ; // 모두 (process) 읽으면쓰기허용 signal (mutex) ; //mutex=1 while (TRUE); 6.42 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Dining-Philosophers Problem Dining philosopher problem Dijkstra, 1965 Life of a philosopher: Repeat forever Thinking Getting hungry Getting two chopsticks Eating The structure of Philosopher i: Shared Data Semaphor chopstick [5] initialized to 1 philosohphor pi do { wait ( chopstick[i] ); wait ( chopstick[ (i + 1) % 5] ); // eat signal ( chopstick[i] ); signal (chopstick[ (i + 1) % 5] ); // think while (TRUE); 6.43 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Problems with Semaphores Correct use of semaphore operations: signal (mutex). wait (mutex) wait (mutex) wait (mutex) Omitting of wait (mutex) or signal (mutex) (or both) 6.44 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Monitors concept 프로세스에서세마포변수를잘못사용하면다양한문제가발생된다. 이런문제를해결하기위하여세마포변수및프로시듀어를구조체 (struct) 안에정의하고추상화하고프로그래머는이프로시듀어를사용하여세마포변수를제어하므로서프로그램머의오류를줄일수있다. Signal(mutex) //critical section wait(mutex) 상호배제위반, 여러프로세스가동시실행,.. Wait(mutex) //critical section wait(mutex) 교착상태 6.45 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Monitors Monitor 는멤버를을캡슐화는 software module 이다. 소프트웨어모듈 ( 구조체, 클래스 ) 이다. 공유데이터구조들과공유데이터구조에서실행되는프로시주어들을캡슐화한다. 이들프로시쥬어를호출하는동시실행주인프로세스간의동기화 한번에하나의프로세스만인활성화된다. 추상화된데이터타입의안전한공유 Monitor syntax(struct) monitor monitor-name { shared variable declarations procedure P1 ( ) {. procedure Pn ( ) { Initialization code (.) { 6.46 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Monitors Condition variable( 개체 ) 모니터의멤버개체 ( 일종의 struct) condition x, y; 프로세스들이모니터내에서대기할수있는수단 condition 개체의멤버 operations wait and signal x.wait(); 프로세스가호출, suspended 상태진입 x.signal(); one suspended process 를재개시킨다. 만일 suspended 프로세스가없으로무시된다. 6.47 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Schematic view of a Monitor waiting queue of processes trying to enter the monitor at most one process in monitor at a time 6.48 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Monitor with Condition Variables 6.49 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Solution to Dining Philosophers 좌우의이웃철학자가젓가락을얻을수있을때만잡도록강제한다. 양쪽의철학자가식사를하지않을때만식사한다. 전체구조 monitor DP { pick(); putdown();.. while(1) { for all i in process Pi { think(); DP.pickup (i); eat(); DP.putdown (i); 6.50 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

monitor DP { Monitor Solution to Dining Philosophers enum { THINKING; HUNGRY, EATING) state [5] ; condition self [5]; void pickup (int i) { // state[i] = HUNGRY; // 상태를 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 () ; void initialization code() { for (int i = 0; i < 5; i++) state[i] = THINKING; // 내상태를식사모드로설정 // 대기중이었으면자신을활성화 // 모든프로세스의상태를생각모드로 6.51 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

An example of a Monitor to Allocate Single Resource 하나의자원을할당해주는모니터 monitor ResourceAllocator { boolean busy; condition x; void acquire(int time) { if (busy) x.wait(time); //time 과함께저장큐에 busy = TRUE; void release() { busy = FALSE; x.signal(); initialization code() { busy = FALSE; 프로세스에서자원접근하는방법 R.acquire(t) 자원접근 R.release() t: 자원접근요청시간 6.52 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Synchronization Examples Solaris Windows XP Linux Pthreads 6.53 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Solaris Synchronization Implements a variety of locks to support multitasking, multithreading (including real-time threads), and multiprocessing Uses adaptive mutexes for efficiency when protecting data from short code segments Uses condition variables and readers-writers locks when longer sections of code need access to data Uses turnstiles to order the list of threads waiting to acquire either an adaptive mutex or reader-writer lock 6.54 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Windows XP Synchronization Uses interrupt masks to protect access to global resources on uniprocessor systems Uses spinlocks on multiprocessor systems Also provides dispatcher objects which may act as either mutexes and semaphores Dispatcher objects may also provide events An event acts much like a condition variable 6.55 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Linux Synchronization Linux: Prior to kernel Version 2.6, disables interrupts to implement short critical sections Version 2.6 and later, fully preemptive Linux provides: semaphores spin locks 6.56 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Pthreads Synchronization Pthreads API is OS-independent It provides: mutex locks condition variables Non-portable extensions include: read-write locks spin locks 6.57 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

End of Chapter 6, Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010