Dining-Philosophers Problem 세마포사용 Semaphore chopstick[5] = {1,1,1,1,1} ; // initially all values are 1 Philosopher i while (true) { P(chopStick[i]); // get left chopstick P(chopStick[(i+1) % 5]); // get right chopstick eat V(chopStick[i]); // return left chopstick V(chopStick[(i+1) % 5]); // return right chopstick think }; 이코드는교착상태의가능성이있음 (not deadlock-free) 모든철학자가왼쪽젓가락을집으면? 오른쪽젓가락을무한히대기 해결책 : (1) 젓가락두개를모두집을수있을때에집게함 (2) 홀수철학자는왼쪽먼저, 짝수철학자는오른쪽먼저집는다. (3) 최대 4 명의철학자가앉는다. 37
6.8 모니터 (Monitors) Semaphore 사용의문제점 프로그래머가잘못사용하면다양한유형의오류발생가능 잘못된 Semaphore 사용예 P와 V 연산의순서를반대로사용 V(mutex) critical section 상호배제위반 P(mutex) V대신에 P를사용 P(mutex) critical section P(mutex) deadlock P 또는 V를누락 deadlock P(mutex) critical section critical section V(mutex) 상호배제위반 이러한실수가아니어도동작의정확성을증명하기어렵고식사하는철학자문제와같이교착상태를유발할수있다. 38
모니터 (Monitor) 병행프로그래밍 (Concurrent Programming) 을위한지원 병행프로그래밍이순차프로그래밍보다어려움 세마포와같은기능을직접사용하지않고병행프로그래밍을위해고수준의상호배제를지원하는기능이개발됨 잘못사용할위험성을줄임 모니터 (Monitor) 프로세스동기화를위한편리하고, 효율적이고, 안전한방법을제공하는고수준의동기화추상화데이터형 (ADT) data 와 procedure 를포함 monitor 에서정의된 procedure 만에 monitor 내의 local data 를접근가능 monitor 의 procedure 들은한번에하나의프로세스만진입하여실행할수있음 상호배제보장 39
Monitor 구문 Monitor 구문 monitor monitor_name { // shared variable declarations procedure p1( ) { } procedure p2( ) { } initialization code (...) { } } shared data p1 p2 operations initialization code entry queue monitor 를지원하는프로그래밍언어 Concurrent Pascal, Ada, Mesa, Concurrent Euclid, Modula-3, D, C# Java, Python 40
조건변수 (Condition Variables) Condition: 모니터에서동기화에사용되는특별한자료형 condition x, y; Condition 변수를사용하는연산 - wait, signal wait(), signal() wait(x) 를호출한연산은프로세스는다른프로세스가 signal(x) 을호출할때까지일시중지 (suspend) 됨 signal(x) 연산은정확히하나의프로세스만재개시킴. 일시중지된프로세스가없으면, 아무런영향이없음 condition x wait wait wait signal (cf) 세마포의 V 연산은세마포값에영향을줌 모니터내에서의동기화 조건변수에대한두연산 (wait, signal) 을사용하여수행함 41
condition 변수를갖는모니터 42
Dining Philosophers 문제 monitor 사용 monitor diningphilosophers { // pseudo-code int state[5]; // THINKING(0), HUNGRY(1), EATING(2) condition self[5]; // condition variables diningphilosophers { // initialization code for (int i = 0; i < 5; i++) state[i] = THINKING; } procedure pickup(int i) { /* see next slides */ } procedure putdown(int i) { /* see next slides */ } private test(int i) { /* see next slides */ } } 양쪽젓가락모두사용가능할때에만양쪽젓가락을집고, 그렇지않으면 wait 상태가됨 젓가락을내려놓을때에옆의철학자의상태를확인하여철학자가 HUNGRY상태에있고, 양쪽젓가락사용이가능하면 signal을보내 wait 상태를해제함 43
Dining Philosophers 문제 monitor 사용 ( 계속 ) procedure pickup(int i) { state[i] = HUNGRY; test(i); if (state[i]!= EATING) wait(self[i]); } procedure putdown(int i) { state[i] = THINKING; // test left and right neighbors test((i + 4) % 5); test((i + 1) % 5); } 이해결안은 deadlock-free이지만 starvation-free는아님 private test(int i) { if ( (state[(i+4) % 5]!= EATING) && (state[i] == HUNGRY) && (state[(i+1) % 5]!= EATING) ) { state[i] = EATING; signal(self[i]); signal } test left/right } putdown pickup test OK T H E test fail H: wait signal 44
Dining Philosophers 문제 monitor 사용 ( 계속 ) // initially, monitor dp = new diningphilosophers(); philosopher i while (true) { dp.pickup(i); eat(); dp.putdown(i); think(); } 45
Java Monitors - Java Synchronization Synchronized method wait(), notify() statements Multiple Notifications: notifyall() 46
synchronized Statement Synchronized method Java 의모든 object 는자신과연관된 lock 을가짐 synchronized method 호출은 lock 의소유를필요로함 object 에대한 lock 을소유하지않은 thread 가 object 의 synchronized method 를호출하면 object lock 에대한 entry set 에놓임 synchronized method 를사용하는 thread 가 method 사용을종료하면 lock 을해제함 공유데이터에대한병행접근을직렬화 (serialize) 하여경쟁조건발생을방지함 47
wait() 와 notify() Method wait() method object lock 을해제하고 thread 를 Block 상태로설정하고 wait set 에놓임 notify() method wait set에서임의의 thread T를선택하여 entry set으로이동하고 thread를 Runnable상태로설정 thread T 는다시object lock을얻으려고경쟁할수있음 Java 의 wait(), notify() 는모니터의 wait(), signal() 과유사하지만 condition variable 은사용하지않음 (object 당 1 개의조건변수를사용하는것과같음 ) 48
wait/notify methods 를사용한 insert() 와 remove() public synchronized void insert(object item) { while (count == BUFFER_SIZE) // full try { wait(); } catch (InterruptedException e) { } ++count; buffer[in] = item; in = (in + 1) % BUFFER_SIZE; notify(); // notify threads waiting for non-empty buffer } public synchronized Object remove() { insert() Object item; while (count == 0) // empty wait() try { wait(); } catch (InterruptedException e) { } - - count; notify() item = buffer[out]; out = (out + 1) % BUFFER_SIZE; notify(); // notify threads waiting for non-full buffer return item; } remove() wait() notify() 49
6.9 동기화 (Synchronization) 사례 Windows Synchronization Linux Synchronization Solaris Synchronization pthread library 50
Windows Synchronization Window kernel의 global resources에대한접근보호 단일프로세서시스템 일시적으로 interrupt mask 다중프로세서시스템 spinlock 사용 spinlock을가지고있는동안선점되지않음 Kernel 외부의 thread 동기화 dispatcher objects 제공 - mutex, semaphores, events( 조건변수 ) critical-section object user-mode mutex, kernel 개입없음 다중프로세서시스템에서, 처음에 spinlock 사용. 오랫동안기다리면 kernel mutex 를할당하고 block 됨 경쟁이있을때만 kernel mutex 가할당되어효율적 51
Linux Synchronization Linux kernel 에서의동기화 atomic 정수연산제공 mutex locks, semaphore, reader-writer locks spinlocks ( 다중프로세서시스템에서 ) 짧은시간만유지될때사용 disable/enable kernel preemption 52
Solaris Synchronization Solaris Synchronization 적응적 (adaptive) mutex : spinlock 또는 sleeping lock lock 을다른 CPU 에서실행중인 thread 가소유 spinlock 사용 lock을소유한 thread가수행중이아니면 lock이방출될때까지 sleep (sleeping lock) 짧은코드세그먼트 ( 수백개이하의명령어사용 ) 에서접근되는데이터를보호하기위해서사용 condition variables, semaphores 긴코드세그먼트용으로사용 reader-writer locks 빈번히사용되지만주로 read-only로접근되는데이터보호에사용 turnstile lock 을대기하는상태에있는 thread 들의큐 객체가아닌커널 thread 마다한개의 turnstile 을가지게함 53
Pthread Synchronizations Pthreads 동기화 Pthreads API는사용자수준에서프로그래머에게제공. 운영체제에독립적 API Pthread 동기화기능 mutex locks condition variables non-portable extensions semaphore, read-write lock, spin locks 54
Pthread mutex #include <pthread.h> int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *mutexattr); int pthread_mutex_lock(pthread_mutex_t *mutex); int pthread_mutex_unlock(pthread_mutex_t *mutex); int pthread_mutex_destroy(pthread_mutex_t *mutex); pthread_mutex_t mutex (mutual exclusive lock) type pthread_mutex_init initialize mutex (mutual exclusive lock) mutexattr: attributes (usually NULL) alternative intialization code pthread_mutex_init(&mutex, NULL); mutex = PTHREAD_MUTEX_INITIALIZER; /* same code */ 55
Example: job-queue2.c initialize mutex variable 56
lock() unlock() 57
58
Pthread semaphore #include <semaphore.h> int sem_init(sem_t *sem, int pshared, unsigned int value); int sem_wait(sem_t *sem); int sem_post(sem_t *sem); int sem_destroy(sem_t *sem); sem_t semaphore type sem_init intialized a semaphore object sem: pointer to the semaphore pshared: a sharing option (0: local) value: initial value to the semaphore sem_post: V operation (atomically increment) sem_wait: P operation (atomically decrement) 59
job-queue3.c 60
61
62
63
64
Pthread condition variables #include <pthread.h> pthread_cond_t cond = PTHREAD_COND_INITIALIZER; int pthread_cond_init(pthread_cond_t *cond, pthread_condattr_t *cond_attr); int pthread_cond_signal(pthread_cond_t *cond); int pthread_cond_broadcast(pthread_cond_t *cond); int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex); int pthread_cond_destroy(pthread_cond_t *cond); pthread_cond_init initialize a condition variable cond_attr: usually NULL a condition variable must always be associated with a mutex 65
pthread_cond_t cv; pthread_mutex_t mutex;... pthread_mutex_init (&mutex, NULL); pthread_cond_init(&cv, NULL);... pthread_mutex_lock(&mutex) pthread_cond_wait( &cv, &mutex); pthread_mutex_unlock(&mutex)... pthread_mutex_lock(&mutex) pthread_cond_signal(&cv); pthread_mutex_unlock(&mutex) 66