DOC PREVIEW
U of I CS 241 - Process Synchronization

This preview shows page 1-2-3-25-26-27 out of 27 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

U of I CS 241 - Process Synchronization

Documents in this Course
Process

Process

28 pages

Files

Files

37 pages

File I/O

File I/O

52 pages

C Basics

C Basics

69 pages

Memory

Memory

23 pages

Threads

Threads

14 pages

Lecture

Lecture

55 pages

C Basics

C Basics

24 pages

Signals

Signals

27 pages

Memory

Memory

45 pages

Threads

Threads

47 pages

Threads

Threads

28 pages

LECTURE

LECTURE

45 pages

Threads

Threads

30 pages

Threads

Threads

55 pages

Files

Files

37 pages

SIGNALS

SIGNALS

22 pages

Files

Files

37 pages

Threads

Threads

14 pages

Threads

Threads

13 pages

Load more
Download Process Synchronization
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Process Synchronization and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Process Synchronization 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?