Semaphores and Monitors High level Synchronization Constructs 1 Synchronization Constructs Synchronization Coordinating execution of multiple threads that share data structures Past few lectures Locks provide mutual exclusion Condition variables provide conditional synchronization Today Historical perspective Monitors M i Alternate high level language constructs Semaphores Introduced by Dijkstra in 1960s Main synchronization primitives in early operating systems 2 Introducing Monitors Separate the concerns of mutual exclusion and conditional synchronization What is a monitor One lock and Zero or more condition variables for managing concurrent access to shared data General approach Collect related shared data into an object module Define methods for accessing the shared data Monitors first introduced as programming language construct Calling a method defined in the monitor automatically acquires the lock Examples Mesa Java synchronized methods Monitors also define a programming convention Can be used in any language C C 3 Critical Section Monitors Basic idea Restrict programming model Permit access to shared variables only within a critical section General program structure Entry section Lock before entering critical section Wait if already locked Key point synchronization may involve wait Critical section code Exit section Unlock the critical U l k when h lleaving i th iti l section ti Object oriented programming style Associate a lock with each shared object Methods that access shared object are critical sections Acquire release locks when entering exiting a method that defines a critical section 4 Remember Condition Variables Locks Provide mutual exclusion Support two methods Lock Acquire wait until lock is free free then grab it Lock Release release the lock waking up a waiter if any Condition variables Support conditional synchronization Three operations Wait Release lock wait for the condition to become true reacquire lock upon return Java wait Signal Wake up a waiter if any Java notify Broadcast Wake up all the waiters Java notifyAll Two semantics for implementation of wait and signal Hoare monitor semantics Hansen Mesa monitor semantics 5 Coke Machine Example Monitor Class CokeMachine Lock lock int count 0 C diti notFull Condition tF ll notEmpty tEm t CokeMachine Deposit lock acquire while count n notFull wait lock notFull wait lock Add coke to the machine count notEmpty signal lock release Does the order of aquire while wait matter Order of release signal matter CokeMachine Remove lock acquire while count 0 notEmpty wait lock notEmpty wait lock Remove coke from to the machine count notFull signal lock release 6 Every monitor function should start with what A wait B signal B i l C lock acquire D lock release E signalAll 7 Hoare Monitors Semantics Hoare monitor semantics Assume thread T1 is waiting on condition x Assume thread T2 is in the monitor Assume thread T2 calls x signal T2 g gives up p monitor T2 blocks T1 takes over monitor runs T1 gives up monitor T2 takes over monitor resumes Example fn1 x wait T1 blocks T1 resumes Lock release fn4 x signal T2 blocks T2 resumes 8 Hansen Mesa Monitors Semantics Hansen monitor semantics Assume thread T1 waiting on condition x Assume thread T2 is in the monitor Assume thread T2 calls x signal wake up g p T1 T2 continues finishes When T1 get a chance to run T1 takes over monitor runs T1 finishes gives up monitor Example fn1 x wait T1 blocks fn4 x signal T2 continues T2 finishes T1 resumes T1 finishes 9 Tradeoff Hoare Claims Cleaner good for proofs When a condition variable is signaled it does not change Used in most textbooks but Inefficient implementation Not modular correctness depends on correct use and implementation of signal CokeMachine Deposit lock acquire l k i if count n notFull wait lock Add coke to the machine count notEmpty signal lock release Hansen Signal is only a hint that the condition may be true Need to check condition again before proceeding bugs Can lead to synchronization y g Used by most systems e g Java Benefits Efficient implementation Condition guaranteed to be true once you are out of while CokeMachine Deposit lock acquire l k while count n notFull wait lock Add coke to the machine count notEmpty signal lock release 10 Problems with Monitors Nested Monitor Calls What happens when one monitor calls into another What happens to CokeMachine lock if thread sleeps in CokeTruck Unload What happens if truck unloader wants a coke CokeMachine Deposit lock acquire while count n notFull wait lock truck unload Add coke to the machine count notEmpty signal lock release CokeTruck Unload lock acquire while soda atDoor coke cokeAvailable wait lock Unload soda closest to door soda pop Signal for soda atDoor Si l availability il bilit f d tD lock release 11 More Monitor Headaches The priority inversion problem Three processes P1 P2 P3 and P1 P3 communicate using a monitor M P3 is the highest priority process followed by P2 and P1 1 P1 enters M 2 P1 is preempted by P2 3 P2 is preempted by P3 4 P3 tries to enter the monitor and waits for the lock 5 P2 runs again preventing P3 from running g the p y system y subverting priority A simple way to avoid this situation is to associate with each monitor the priority of the highest priority process which ever enters that monitor 12 Other Interesting Topics Exception handling What if a process waiting in a monitor needs to time out Naked notify How do we synchronize with I O devices that do not grab monitor locks but can notify condition variables Butler Lampson and David Redell Experience with Processes and Monitors in Mesa Mesa 13 Semaphores Study these for history and compatibility Don t use semaphores in new code A non negative integer variable with two atomic and isolated operations Semaphore P Passeren wait If sem 0 then decrement sem by 1 Otherwise wait until sem 0 and then decrement Semaphore V Vrijgeven signal Increment sem by 1 Wake up a thread waiting in P We assume that a semaphore is fair No thread t that is blocked on a P operation remains blocked if the V operation on the semaphore is invoked infinitely often In practice FIFO is mostly used transforming the set into a queue 14 Important properties of Semaphores Semaphores are non negative integers The only operations you can use to change the value of a semaphore are P and V except for the initial setup P can block but V never blocks Semaphores are used both for Mutual exclusion and Conditional synchronization Two