OPERATING SYSTEMS 1 龚玲 lgong@sjtu.edu.cn
OPERATING SYSTEMS 龚玲 lgong@sjtu.edu.cn 1
Chapter 6:Process Synchronization
Chapter 6: Process Synchronization
REVIEW o Semaphores o http://wenku.baidu.com/course/study/77f1dcccda38376ba flfae94#665ea0c7aa00b52acfc7ca94
REVIEW Semaphores http://wenku.baidu.com/course/study/77f1dcccda38376ba f1fae94#665ea0c7aa00b52acfc7ca94
Goals for today o Classic Problems of Synchronization o Monitors
Goals for today Classic Problems of Synchronization Monitors
Semaphore o Synchronization tool that does not require busy waiting o Semaphore S-integer variable o Two standard operations modify S:acquire0 and release( Originally called PO and VO o Less complicated o Can only be accessed via two indivisible(atomic)operations acquire(){ while value <=0 ;/no-op value--; release(){ value++;
Semaphore Synchronization tool that does not require busy waiting Semaphore S – integer variable Two standard operations modify S: acquire() and release() Originally called P() and V() Less complicated Can only be accessed via two indivisible (atomic) operations
Semaphore as General Synchronization Tool o Counting semaphore-integer value can range over an unrestricted domain o Binary semaphore-integer value can range only between 0 and 1;can be simpler to implement Also known as mutex locks Semaphore S=new Semaphore(); S.acquire(); /critical section S.release(); /∥remainder section
Semaphore as General Synchronization Tool Counting semaphore – integer value can range over an unrestricted domain Binary semaphore – integer value can range only between 0 and 1; can be simpler to implement Also known as mutex locks
Semaphore Implementation o Must guarantee that no two processes can execute acquire and release on the same semaphore at the same time o Thus,implementation becomes the critical section problem where the wait and signal code are placed in the critical section. Could now have busy waiting in critical section implementation oBut implementation code is short oLittle busy waiting if critical section rarely occupied Note that applications may spend lots of time in critical sections and therefore this is not a good solution
Semaphore Implementation Must guarantee that no two processes can execute acquire () and release () on the same semaphore at the same time Thus, implementation becomes the critical section problem where the wait and signal code are placed in the critical section. Could now have busy waiting in critical section implementation But implementation code is short Little busy waiting if critical section rarely occupied Note that applications may spend lots of time in critical sections and therefore this is not a good solution
Semaphore Implementation with no Busy waiting o With each semaphore there is an associated waiting queue.Each entry in a waiting queue has two data items: value (of type integer) pointer to next record in the list o Two operations: block-place the process invoking the operation on the appropriate waiting queue. wakeup-remove one of processes in the waiting queue and place it in the ready queue
Semaphore Implementation with no Busy waiting With each semaphore there is an associated waiting queue. Each entry in a waiting queue has two data items: value (of type integer) pointer to next record in the list Two operations: block – place the process invoking the operation on the appropriate waiting queue. wakeup – remove one of processes in the waiting queue and place it in the ready queue
Semaphore Implementation with no Busy waiting (Cont.) o Implementation of acquire(): acquire(){ value--; if (value 0){ add this process to list block; o Implementation of release(: release(){ value++; if (value <=0){ remove a process P from list wakeup(P);
Semaphore Implementation with no Busy waiting (Cont.) Implementation of acquire(): Implementation of release():
Mutual Exclusion with Semaphores semaphore mutex 1; cobegin /1 pi:while (1){ mutex.acquire(); CSi; mutex.release(); programi; // coend
Mutual Exclusion with Semaphores semaphore mutex = 1; cobegin ... // pi: while (1) { mutex.acquire(); CSi; mutex.release(); programi; } // ... coend;
