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
Summary Background( 배경 ) 개념 2 examples of a problem caused by wrong synchronization between processes Producer-Consumer problem Withdraw money from a bank account The Critical-Section Problem( 임계구역문제 ) 임계구역이란? / 3 requirements / 임계구역를다루는구조 Mechanism for the critical section problems: Locks, Semaphores, Monitors, Locks Acquire(a lock), Release(the lock), atomic operation(load, Store) Solution using Software Algorithm Peterson s Solution for two processes Bakery algorithm for more than two processes Solution using hardware atomic instructions(test-and-set, compare-and-swap) Mutual Exclusion solution Bounded mutual exclusion solution Disable/enable interrupts 6.3 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Summary Semaphores( 세마포 ) Semaphore S, wait, signal Binary semaphore and Counting Semaphore and implementation examples Solution without Busy-Waiting : Block and Wakeup operations Deadlock and Starvation Classic Problems of Synchronization( 고전적동기화문제들 ) Bounded-Buffer producer-consumer Problem Reader-writer problem Dining-Philosophers problem Monitors( 모니터 ) Synchronization Examples ( 동기화사례 ) Atomic Transactions( 원자적트랜잭션 ) 6.4 / 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) Examples Produce-Consumer Problem Withdraw money from a bank account 6.5 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Bounded Shared Buffer Previous Producer-Consumer (3.4.1) 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; 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 Shared Data #define BUFFER_SIZE 10 typedef struct... item; item buffer[buffer_size]; int in = 0; //used by producer int out = 0; //used by consumer 6.6 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Producer-Consumer 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; counter++; Consumer process while (true) while (count == 0) ; // do nothing nextconsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; counter--; /* 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.7 / 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.8 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Race Condition( 경합상태 ) 경합상태 (race condition) : 두개의프로세스가경쟁적으로한변수를조작 두프로세스가공유변수 count(shared memory) 의변경명령이동시에수행될경우불일치발생 생산자의 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.9 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
An Example- Withdraw money from a bank account 은행계좌인출문제 (Withdraw money from a bank account) 잔고 100 만원을가진은행계좌를두친구가공유하고있다고가정한다. (Suppose you and your girl(boy) friend share a bank account with a balance of 1,000,000won) 두친구가 ATM 에가서동시에 10 만원을인출하려고할때어떤문제가발생할수있을까? (What happens if both go to separate ATM machines, and simultaneously withdraw 100,000won from the account?) int withdraw (account, amount) balance = get_balance (account); balance = balance - amount; put_balance (account, balance); return balance; 6.10 / 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.11 / 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.12 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Solution to Critical-Section Problem 임계구역 G 문제의해결을위한전형적인프로세스의일반적인구조 (General structure for a typical process Pi) do entry section exit section critical section remainder section while (TRUE); 6.13 / 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.14 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Locks Lock 의두개연산. (A lock is an object (in memory) that provides the following two operations) acquire() : lock 가해제될때까지기다린후해제되면잡는다 (wait until lock is free, then grab it) release(): 해제, 대기중인한쓰레드를활성화한다 (unlock, and wake up any thread waiting in acquire) Lock 의사용법 초기에 free 이다.(Lock is initially free) 임계구역진입전에 acquire() 를호출하고, 벗어날때 release() 를호출한다. (Call acquire() before entering a critical section, and release() after leaving it) acquire() and release() 사이에쓰레드는 lock 을잡고있다. (Between acquire() and release(), the thread holds the lock) 한호출자가 lock 를잡고있으면 acquire() 함수는반환되지않는다. (acquire() does not return until the caller holds the lock) 한순간최대한개의쓰레드가 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 0 1 0 6.16 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Locks 의문제점 class Program static public bool lock1 = false; static void Main(string[] args) Console.WriteLine("Is Mutual Exclisive?"); Console.WriteLine("Test1 : "); Thread T1 = new Thread(new ThreadStart(Method)); Thread T2 = new Thread(new ThreadStart(Method)); Thread T3= new Thread(new ThreadStart(Method)); T1.Start(); T2.Start(); T3.Start(); T1.Join(); T2.Join(); T3.Join(); static void acquire(ref bool lock1) while (lock1) ; lock1 = true; static void release(ref bool lock1) lock1 = false;; Console.WriteLine("Test2 : "); T1 = new Thread(new ThreadStart(Method1)); T2 = new Thread(new ThreadStart(Method1)); T3 = new Thread(new ThreadStart(Method1)); T1.Start(); T2.Start(); T3.Start(); T1.Join(); T2.Join(); T3.Join(); static void Method() acquire(ref lock1); Console.WriteLine("0 ", Thread.CurrentThread.ManagedThreadId); Console.WriteLine("0 ", Thread.CurrentThread.ManagedThreadId); release(ref lock1); static void Method1() acquire(ref lock1); Console.WriteLine("0 ", Thread.CurrentThread.ManagedThreadId); Thread.Sleep(100); Console.WriteLine("0 ", Thread.CurrentThread.ManagedThreadId); release(ref lock1); 6.17 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Implementing Locks (Cont d) Problem Lock의구현시역시임계문제를가지고있다.(Implementation of locks has a critical section, too!) acquire/release 는원자적이어야한다.(The acquire/release must be atomic) 원자적연산 (Atomic operation) 인터럽트되지않는연산 (Executes as though it could not be interrupted) 전부실행되든지전혀실행되지말아야하는연산 (Code that executes all or nothing ) Solutions Software-only algorithms Peterson s Solution for two processes Bakery algorithm for more than two processes Hardware atomic instructions Mutual Exclusion solution Test-and-set compare-and-swap, etc. Bounded Mutual Exclusion solution Test-and-set Disable/re-enable interrupts To prevent context switches 6.18 / 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.19 / 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.20 / 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.21 / 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.22 / 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.23 / 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.24 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Synchronization Hardware 임계구역문제를해결하기위하여하드웨어 ( 명령 ) 가있다 (Many systems provide hardware (instruction) support for critical section code) 인터럽트무력화 현실행코드는선점되지않는다. 다른분제를야기 스케줄링등등 원자적하드웨어명령 최근의프로세서들의지원하고있다. Atomic = non-interruptable 예 TestAndSet(a) : test memory word and set value Swap(a,b) : swap contents of two memory words 6.25 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Mutual Exclusion solution using TestAndSet TestAndSet 윈자명령을이용한상호배제알고리즘 (Mutual Exclusion using TestAndSet (hardware) instruction) 공유변수 : boolean lock., initialized to false. 프로세스 Pi 들은상호배제된다. initially lock =false; // global variable do while ( TestAndSet (&lock )) ; // critical section lock = FALSE; // remainder section while (TRUE); 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: 6.26 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Mutual Exclusion Solution using Swap Instruction SWAP 명령을이용한상호배제알고리즘 (Mutual Exclusion Solution using Swap) 공유변수 : Boolean lock=false; 지역변수 : Boolean key 프로세스 Pi 들이상호배제된다. initially lock=false //shared do key = TRUE; //local variable while ( key == TRUE) Swap (&lock, &key ); // critical section lock = FALSE; // remainder section while (TRUE); 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: 6.27 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Bounded-waiting Mutual Exclusion with TestandSet() TestAndSet 명령을이용한유한대기상호배제알고리즘 프로세스 Pi 들이상호배제된다. do waiting[i] = TRUE; key = TRUE; while (waiting[i] && key) key = TestAndSet(&lock); waiting[i] = FALSE; // critical section //proceed when waiting[i]==false or key(lock)=false j = (i + 1) % n; while ((j!= i) &&!waiting[j]) // 대기중인다음프로세스를활성화한다. j = (j + 1) % n; // Bounded waiting 보장 if (j == i) else lock = FALSE; // lock= false로하여다른프로세스에게허용 waiting[j] = FALSE; // lock==true 인상태에서 Pj에서 while문장을지나 critical // remainder section while (TRUE); //section 진입하게한다. 6.28 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
세마포어 (Semaphore concept) Semaphore is 일종의동기화도구이다. A kind of general synchronization tool Also is able to be used 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
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 wait(s) // remainder section while (TRUE); while(s<=0); S--; signal(s) S++; Semaphore mutex Process1 Process2 process3 1------0----------10----------10----------1---------------------- wc s w c s w c s 6.31 / 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 Counting semaphore N 개의공유자원을이용하기위한상호배제 Semaphore res=n ; // 공유자원수 : N do Wait(res) //res 자원이용하기전 N==0이면모든자원이사용중 // Critical Section Signal(res) // remainder section while(true); //res++ 자원이용후 wait(s) while(s<=0); S--; signal(s) S++; Semaphore res Process1 Process2 process3 2 1 0 10 1 2 wc s wc s w c s 6.32 / 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.33 / 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는대기중인 process의수이다. if (S->value < 0) add this process to S->list; //add itself onto waiting list block(); // 자신의프로세스는대기큐로이동 / 실행중지 // value=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로이동시킨다. //value >=1 : 다른프로세스의실행을허용 6.34 / 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) 두개의프로세스 P1,P2 가두세마포 S,Q 가 1 인상태에서다음과같이대기중일때발생한다. (Let S and Q be two semaphores initialized to 1 where two processes P1,P2) P 0 P 1 wait (S); wait (Q); wait (Q); Starvation wait (S);.... signal (S); signal (S); signal (Q); signal (Q); indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended. (P0,P1 모두세마포대기큐에추가된상태면영원히재실행이불가하다.) 6.35 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
6.6 Classical Problems of Synchronization 동기화문제의대표적사례 Bounded-Buffer Problem Readers and Writers Problem scheduling Dining-Philosophers Problem deadlock 6.36 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Synchronization with critical problem initially in=out=counter=0 Bounded Buffer Problem 37 6.37 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Bounded Buffer Problem (Cont d) Implementation with semaphores 38 6.38 / 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 Consumer while (true) full.waitone(); //full mutex.waitone(); //mutex T t = Take(); mutex.releasemutex(); //mutex++ empty.release(); //empty-- Consume(t); 39 6.39 / 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.40 / 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("0,2 Append List:[1] 2", Thread.CurrentThread.ManagedThreadId,list.Count,s); // 데이터소비 //critical codes : override public string Take() string t = list[0]; list.removeat(0); string s=""; foreach (string a in list) s += a + " "; Console.WriteLine("0,2 Take List:[1] 2 item:3", Thread.CurrentThread.ManagedThreadId,list.Count,s,t); return t; // 데이터생성 override public string Produce() Random r = new Random(); int i = r.next(10); Console.WriteLine("0,2 Produce Item:1", Thread.CurrentThread.ManagedThreadId,i); return i.tostring(); // 데이터처리 override public void Consume(string t) Console.WriteLine("0,2 Consume Item:1", Thread.CurrentThread.ManagedThreadId, t); 6.41 / 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 (thread no=3) 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 (thread no=4) 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); 6.42 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Readers-Writers Problem 복수의 reader 및 writer 프로세스들이데이터집합을공유하는문제 Readers : 읽기전용, 복수의프로세스읽기가능, 수정불가능 Writers : 읽고쓰기가능, writer 프로세스들끼리배타적공유 Algorithm Shared Data, initially - 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 시부터 signal (mutex) // 읽는동안 write 금지 // reading is performed, // 복수프로세스가동시읽기가능 wait (mutex) ; readcount - - ; if (readcount == 0) signal (wrt) ; // 모두읽으면쓰기허용 signal (mutex) ; //mutex=1 while (TRUE); 6.43 / 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); 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 개념 프로세스에서세마포변수를잘못사용하면다양한문제가발생된다. 이런문제를해결하기위하여세마포변수및프로시듀어를구조체 (struct) 안에정의하고추상화하고프로그래머는이프로시쥬어를사용하여세마포변수를제어하므로서프로그램머의오류를줄일수있다. Monitor 는멤버를을캡슐화는 software module 이다. 소프트웨어모듈 ( 구조체, 클래스 ) 이다. 공유데이터구조들과공유데이터구조에서실행되는프로시듀어들을캡슐화한다. 이들프로시듀어를호출하는동시실행중인프로세스간의동기화 한번에하나의프로세스만인활성화된다. 추상화된데이터타입의안전한공유 General Structure of Monitor monitor monitor-name shared variable declarations procedure P1 ( ). procedure Pn ( ) Initialization code (.) 6.45 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
개요 Shared Data In Process i Monitor Solution to Dining Philosophers 좌우의이웃철학자가젓가락을얻을수있을때만잡도록강제한다. 양쪽의철학자가식사를하지않을때만식사한다. Monitor DP DP.Initialization(); while(1) for all i in process Pi think(); DP.pickup (i); eat(); DP.putdown (i); monitor DP 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() // 모든프로세스의상태를생각모드로 for (int i = 0; i < 5; i++) state[i] = THINKING; 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
Monitor with Condition Variables 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
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.49 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Synchronization Examples Solaris Windows XP Linux Pthreads 6.50 / 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.51 / 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(kind of busy waiting locks) on multiprocessor systems Also provides dispatcher objects which may act as either mutexes and semaphores Dispatcher objects include timer objects, event objects, semaphore objects, mutex objects, and thread objects Dispatcher objects may also provide events. An event acts much like a condition variable 6.52 / 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.53 / 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.54 / 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