CSE 120 Principles of Operating Systems Spring 2009 Lecture 6 Semaphores and Monitors Geoffrey M Voelker Higher Level Synchronization We looked at using locks to provide mutual exclusion Locks work but they have some drawbacks when critical sections are long Instead we want synchronization mechanisms that Block waiters Leave interrupts enabled inside the critical section Look at two common high level mechanisms Spinlocks inefficient Disabling interrupts can miss or delay important events Semaphores binary mutex and counting Monitors mutexes and condition variables Use them to solve common synchronization problems April 21 2009 CSE 120 Lecture 6 Semaphores and Monitors 2 Semaphores Semaphores are an abstract data type that provide mutual exclusion to critical sections Semaphores can also be used as atomic counters Block waiters interrupts enabled within CS Described by Dijkstra in THE system in 1968 More later Semaphores are integers that support two operations wait semaphore decrement block until semaphore is open Also P after the Dutch word for test or down signal semaphore increment allow another thread to enter Also V after the Dutch word for increment or up That s it No other operations not even just reading its value exist Semaphore safety property the semaphore value is always greater than or equal to 0 April 21 2009 CSE 120 Lecture 6 Semaphores and Monitors 3 Blocking in Semaphores Associated with each semaphore is a queue of waiting processes When wait is called by a thread If semaphore is open thread continues If semaphore is closed thread blocks on queue Then signal opens the semaphore If a thread is waiting on the queue the thread is unblocked If no threads are waiting on the queue the signal is remembered for the next thread In other words signal has history c f condition vars later This history is a counter April 21 2009 CSE 120 Lecture 6 Semaphores and Monitors 4 Semaphore Types Semaphores come in two types Mutex semaphore or binary semaphore Represents single access to a resource Guarantees mutual exclusion to a critical section Counting semaphore or general semaphore Represents a resource with many units available or a resource that allows certain kinds of unsynchronized concurrent access e g reading Multiple threads can pass the semaphore Number of threads determined by the semaphore count mutex has count 1 counting has count N April 21 2009 CSE 120 Lecture 6 Semaphores and Monitors 5 Using Semaphores Use is similar to our locks but semantics are different struct Semaphore int value Queue q S withdraw account amount wait S balance get balance account balance balance amount put balance account balance signal S return balance wait S balance get balance account balance balance amount Threads block critical section It is undefined which thread runs after a signal April 21 2009 wait S wait S put balance account balance signal S signal S signal S CSE 120 Lecture 6 Semaphores and Monitors 6 Semaphores in Nachos wait S Disable interrupts while S value 0 enqueue S q current thread thread sleep current thread S value S value 1 Enable interrupts thread sleep assumes interrupts are disabled signal S Disable interrupts thread dequeue S q thread start thread S value S value 1 Enable interrupts Note that interrupts are disabled only to enter leave critical section How can it sleep with interrupts disabled Need to be able to reference current thread What happens if while value 0 is an if value 0 April 21 2009 CSE 120 Lecture 6 Semaphores and Monitors 7 Using Semaphores We ve looked at a simple example for using synchronization Mutual exclusion while accessing a bank account Now we re going to use semaphores to look at more interesting examples Readers Writers Bounded Buffers April 21 2009 CSE 120 Lecture 6 Semaphores and Monitors 8 Readers Writers Problem Readers Writers Problem An object is shared among several threads Some threads only read the object others only write it We can allow multiple readers but only one writer Let r be the number of readers w be the number of writers Safety r 0 0 w 1 r 0 w 0 How can we use semaphores to control access to the object to implement this protocol Use three variables int readcount number of threads reading object Semaphore mutex control access to readcount Semaphore w or r exclusive writing or reading April 21 2009 CSE 120 Lecture 6 Semaphores and Monitors 9 Readers Writers number of readers int readcount 0 mutual exclusion to readcount Semaphore mutex 1 exclusive writer or reader Semaphore w or r 1 writer wait w or r lock out readers Write signal w or r up for grabs April 21 2009 reader wait mutex lock readcount readcount 1 one more reader if readcount 1 wait w or r synch w writers signal mutex unlock readcount Read wait mutex lock readcount readcount 1 one less reader if readcount 0 signal w or r up for grabs signal mutex unlock readcount CSE 120 Lecture 6 Semaphores and Monitors 10 Readers Writers Notes w or r provides mutex between readers and writers If a writer is writing where will readers be waiting Once a writer exits all readers can fall through writer wait signal reader wait signal when readcount goes from 0 to 1 or from 1 to 0 Which reader gets to go first Is it guaranteed that all readers will fall through If readers and writers are waiting and a writer exits who goes first Why do readers use mutex Why don t writers use mutex What if the signal is above if readcount 1 April 21 2009 CSE 120 Lecture 6 Semaphores and Monitors 11 Bounded Buffer Problem There is a set of resource buffers shared by producer and consumer threads Producer inserts resources into the buffer set Output disk blocks memory pages processes etc Consumer removes resources from the buffer set Whatever is generated by the producer Producer and consumer execute at different rates No serialization of one behind the other Tasks are independent easier to think about The buffer set allows each to run without explicit handoff Safety Sequence of consumed values is prefix of sequence of produced values If nc is number consumed np number produced and N the size of the buffer then 0 np nc N April 21 2009 CSE 120 Lecture 6 Semaphores and Monitors 12 Bounded Buffer 2 0 np nc N and 0 nc np N N Use three semaphores empty count of empty buffers Counting semaphore empty nc np N full count of full buffers Counting semaphore np nc full mutex mutual exclusion to shared set of buffers Binary semaphore April 21 2009 CSE 120 Lecture 6 Semaphores and Monitors 13 Bounded Buffer 3
View Full Document
Unlocking...