CS241 System ProgrammingProcess Synchronization (3)ContentAdministrativeSemaphoresWhat’s Up? What’s Down?Mutex: Binary SemaphoreMutex Implementation using TSLMutex Implementation using TSLProducer-Consumer Problem using SemaphoresUsing Mutex to Implement SemaphoresCounting Semaphore Implementation using Binary Semaphores(for Mutual Exclusion)Counting Semaphore Implementation (2)Implementations of Semaphore using Sleep & WakeupImplementations of Semaphore using Sleep & WakeupTradeoffsPossible Deadlocks with SemaphoresBe Careful When Using SemaphoresImplementation of Simple Synchronization Primitives in POSIXPOSIX Mutex Locks FunctionsMutex Locks (1)Mutex Locks (2)UseCounter exampleCounter Example (2)Monitor – Sync PrimitiveMonitor PropertiesSummaryCS241 System ProgrammingProcess Synchronization (3)Klara NahrstedtLecture 82/6/20062/6/2006CS 241 - System Programming, Klara Nahrstedt2ContentzMutexz Semaphoresz Monitorsz Summary2/6/2006CS 241 - System Programming, Klara Nahrstedt3AdministrativezRead: T: Chapter 2.2z Read: R&R 13.1-13.4 (Mutex Locks and Conditional Variables)z Read: R&R 14.1- 14.5 (Semaphores)z MP1 is runningz Quiz 2: Friday, February 10, 2006 (topic –processes/threads and synchronization)2/6/2006CS 241 - System Programming, Klara Nahrstedt4Semaphores zA semaphore count represents count number of abstract resources. z New variable having 2 operations–The Down/P operation is used to acquire a resource and decrements count. –The Up/V operation is used to release a resource and increments count. zAny semaphore operation is indivisible (atomic)z Semaphores solve the problem of the wakeup-bit2/6/2006CS 241 - System Programming, Klara Nahrstedt5What’s Up? What’s Down?zDefinitions of Down/P and Up/V (P and V is a different notation for operations Down and Up): Down(S): S. value:=S.value -1if S.value <0 then {add process to queue S.L ; block;}Up(S): S.value = S.value+1if S.value <= 0 then {remove process from queue S.L; wakeup;}zCounting semaphores: 0..N zBinary semaphores: 0,12/6/2006CS 241 - System Programming, Klara Nahrstedt6Mutex: Binary SemaphorezVariable with only 2 states–Lock–UnlockzSimplified version of semaphorez Mutex is used for mutual exclusion2/6/2006CS 241 - System Programming, Klara Nahrstedt7Mutex Implementation using TSLzUsing Test_and_Set (TSL) instruction to implement–Mutex_lock–Mutex_unlock2/6/2006CS 241 - System Programming, Klara Nahrstedt8Mutex Implementation using TSLImplementation of mutex_lock and mutex_unlock2/6/2006CS 241 - System Programming, Klara Nahrstedt9Producer-Consumer Problem using Semaphores2/6/2006CS 241 - System Programming, Klara Nahrstedt10Using Mutex to Implement SemaphoreszUsing mutex_lock and mutex_unlock to implement a counting semaphore–Up–Down2/6/2006CS 241 - System Programming, Klara Nahrstedt11Counting Semaphore Implementation using Binary Semaphores(for Mutual Exclusion)class Semaphore {Mutex m1; // Mutual exclusion to protect countMutex m2; // Mutual exclusion to protect critical regionint count; // Resource count.public:Semaphore( int count );void Up();void Down();};static inline Semaphore::Semaphore( int count ){ count = count; }2/6/2006CS 241 - System Programming, Klara Nahrstedt12Counting Semaphore Implementation (2)voidSemaphore::Down(){ mutex_lock(m1);count--;if ( count < 0 ){ mutex_unlock(m1);mutex_lock(m2);}mutex_unlock(m1);}voidSemaphore::Up(){ mutex_lock(m1);count++;if (count <=0) then mutex_unlock(m2);else mutex_unlock(m1); }2/6/2006CS 241 - System Programming, Klara Nahrstedt13Implementations of Semaphore using Sleep & Wakeup type Semaphore = record value:integer;L: list of processes;Semaphore S;Down(S):S.value:= S.value - 1;if S. value < 0 then { add this process to the S.L;sleep; };Up(S):S.value:= S.value + 1;if S.value > 0 then { remove process P from S.L;wakeup(P);}Does it work?2/6/2006CS 241 - System Programming, Klara Nahrstedt14Implementations of Semaphore using Sleep & Wakeup type Semaphore = record value:integer;L: list of processes;Semaphore S;Down(S):S.value:= S.value - 1;if S. value < 0 then { add this process to the S.L;sleep; };Up(S):S.value:= S.value + 1;if S.value <= 0 then { remove process P from S.L;wakeup(P);}Does it work?2/6/2006CS 241 - System Programming, Klara Nahrstedt15TradeoffszBusy waiting (spinlock)–Waste CPU cycleszSleep&Wakeup (blocked lock)–Context switch overheadzHybrid competitive solution (spin-block)–Apply spinlocks if the waiting time is shorter than the context switch time–Use sleep & wakeup if the waiting time is longer than the context switch time2/6/2006CS 241 - System Programming, Klara Nahrstedt16Possible Deadlocks with SemaphoresExample: P0 P1share two semaphores S and QS:= 1; Q:=1;Down(S); // S=0 ------------> Down(Q); //Q=0Down(Q); // Q= -1 <----------------------------> Down(S); // S=-1// P0 blocked // P1 blockedDEADLOCKUp(S); Up(Q);Up(Q); Up(S);2/6/2006CS 241 - System Programming, Klara Nahrstedt17Be Careful When Using Semaphores// Violation of Mutual ExclusionUp(mutex); mutexUnlock();critical section criticalSection();Down(mutex); mutexLock();// Deadlock SituationDown(mutex); mutexLock();critical section criticalSection();Down(mutex); mutexLock(P);// Violation of Mutual Exclusion (omit wait(mutex)/mutexLock())critical section critical Section();Up(mutex); mutexUnlock();// Deadlock Situation (omit signal(mutex)/mutexUnlock())Down(mutex); mutexLock();critical section criticalSection();2/6/2006CS 241 - System Programming, Klara Nahrstedt18Implementation of Simple Synchronization Primitives in POSIXzMutex Lock (use <pthread.h>) – discussed this week in discussion sections–Mutex lock (pthread_mutex_lock)–Mutex Unlock (pthread_mutex_unlock)zSemaphore (use <semaphore.h> - discussed this week in discussion sections–Initialize semaphore (sem_init)–Destroy semaphore (sem_destroy)–Signal (Up) semaphore (sem_post)–Wait (Down) semaphore (sem_wait)zCondition Variables–Waiting on condition (pthread_cond_wait)2/6/2006CS 241 - System Programming, Klara Nahrstedt19POSIX Mutex Locks Functionsint pthread_mutex_destroy(pthread_mutex_t *mutex); int pthread_mutex_init(pthread_mutex_t *restrict mutex,); int pthread_mutex_lock(pthread_mutex_t *mutex); int
View Full Document