Chapter 5 Mutual Exclusion and Synchronization 5.1 Principles of Concurrency ·5.2 Mutua|EXc| usion 5.3 Semaphores 5. 4 Monitors 5.5 Message Passing 5.6 Readers /writers problem .5. Summary
2 Chapter 5 Mutual Exclusion and Synchronization • 5.1 Principles of Concurrency • 5.2 Mutual Exclusion • 5.3 Semaphores • 5.4 Monitors • 5.5 Message Passing • 5.6 Readers/Writers Problem • 5.7 Summary
Last Class: Semaphores A semaphore S supports two atomic operations SPO: get a semaphore, wait if busy semaphore s is available SVO: release the semaphore, wake up a process if one is waiting for s Types of semaphore Binary or Mutex Semaphore: grants mutual exclusive access to a resource Counting Semaphore: useful for granting mutually exclusive access for a set of resources Semaphores are difficult to use: orders are important
Last Class: Semaphores • A semaphore S supports two atomic operations • S→P(): get a semaphore, wait if busy semaphore S is available. • S→V(): release the semaphore, wake up a process if one is waiting for S. • Types of semaphore • Binary or Mutex Semaphore: grants mutual exclusive access to a resource • Counting Semaphore: useful for granting mutually exclusive access for a set of resources • Semaphores are difficult to use: orders are important 3
Solution higher level primitive oS codes and concurrent applications High-Level Mutex Semaphores Monitors Send/Recv Atomic API LoW-Level Load/store Interrupt Test& Set Other atomic Atomic Ops disable/enable instructions interrupts CPU (1/0, timer) Multiprocessors scheduling
Solution：higher level primitive 4
5.4 Monitors .5 4.1 Concept of monitors 5.4.2 Producer-Consumer with monitors
5.4 Monitors • 5.4.1 Concept of Monitors • 5.4.2 Producer-Consumer with Monitors 5
5.4.1 Concept of Monitors(1/10) Monitor(管程) A high-level abstraction that provides a convenient and effective mechanism for process synchronization Only one process/thread may be executing in the monitor at a time
5.4.1 Concept of Monitors(1/10） • Monitor（管程） • A high-level abstraction that provides a convenient and effective mechanism for process synchronization. • Only one process/thread may be executing in the monitor at a time. 6
5.4.1 Concept of Monitors(2/10) .a Formal definition A monitor defines a lock and zero or more condition variables for managing concurrent access to shared data The monitor uses the lock to insure that only a single thread is active in the monitor at any instance The lock also provides mutual exclusion for shared data Condition variables enable threads to go to sleep inside of critical sections, by releasing their lock at the same time it puts the thread to sleep
5.4.1 Concept of Monitors(2/10） • A Formal Definition • A Monitor defines a lock and zero or more condition variables for managing concurrent access to shared data. • The monitor uses the lock to insure that only a single thread is active in the monitor at any instance. • The lock also provides mutual exclusion for shared data. • Condition variables enable threads to go to sleep inside of critical sections, by releasing their lock at the same time it puts the thread to sleep. 7
5.4.1 Concept of Monitors(3/10) · Monitor operations: Encapsulates the shared data you want to protect Acquires the mutex at the start Operates on the shared data Temporarily releases the mutex if it can't complete Reacquires the mutex when it can continue Releases the mutex at the end
5.4.1 Concept of Monitors(3/10） • Monitor operations: • Encapsulates the shared data you want to protect. • Acquires the mutex at the start. • Operates on the shared data. • Temporarily releases the mutex if it can't complete. • Reacquires the mutex when it can continue. • Releases the mutex at the end. 8
5.4.1 Concept of Monitors(4/10) Structure of a monitor queue entering processes monitor waiting area Entrance Lock MONITOR condition cl local data waitre I condition variables Procedure l Condition Variables condition er ewalt(cn) Procedure k 工兽 urgent queue initialization code Lxi量 re s.1s Structure of a Monitor
5.4.1 Concept of Monitors(4/10） • Structure of a Monitor 9 Lock Condition Variables
5.4.1 Concept of Monitors (5/10) Procedures are mutual exclusive Shared data Queue of waiting processes trying to enter the monitor procedures
5.4.1 Concept of Monitors(5/10） • Procedures are mutual exclusive 10
5.4.1 Concept of Monitors(6/10) It is simple to turn a java class into a monitor Make all the data private Make all methods synchronized or at least the non private ones) class Queuet private…;∥/ queue data public void synchronized Add( object item t put item on queue public object synchronized removed i if queue not empty i remove item return item
5.4.1 Concept of Monitors(6/10） • It is simple to turn a Java class into a monitor: • Make all the data private • Make all methods synchronized (or at least the non - private ones) 11 class Queue{ private ...; // queue data public void synchronized Add( Object item ) { put item on queue; } public Object synchronized Remove() { if queue not empty { remove item; return item; } }