CSE 120 Principles of Operating Systems Winter 2007 Lecture 6 Semaphores and Monitors Keith Marzullo and Geoffrey M Voelker Announcements z z Homework 2 out Email question z Why not have an idle thread in Nachos hint a purely pragmatic reason Any questions on the project January 25 2007 CSE 120 Lecture 6 Semaphores and Monitors 2007 Keith Marzullo and Geoffrey M Voelker 2 1 Higher Level Synchronization Higher z z We looked at using locks to provide mutual exclusion Locks work but they have some drawbacks when critical sections are long z Instead we want synchronization mechanisms that z Block waiters Leave interrupts enabled inside the critical section L k att two Look t common high level hi h l l mechanisms h i z 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 January 25 2007 CSE 120 Lecture 6 Semaphores and Monitors 2007 Keith Marzullo and Geoffrey M Voelker 3 Semaphores z Semaphores are an abstract data type that provides mutual exclusion to critical sections Block Bl k waiters it iinterrupts t t enabled bl d within ithi CS Described by Dijkstra in THE system in 1968 z Semaphores can also be used as atomic counters z Semaphores are integers that support two operations More later wait semaphore decrement block until semaphore is open signal semaphore increment allow another thread to enter That s it No other operations not even just reading its value exist Also P after the Dutch word for test or down Also V after the Dutch word for increment or up z Semaphore safety property a semaphore s value is always greater than or equal to 0 January 25 2007 CSE 120 Lecture 6 Semaphores and Monitors 2007 Keith Marzullo and Geoffrey M Voelker 4 2 Blocking in Semaphores z z Associated with each semaphore is a queue of waiting processes When wait is called by a thread z 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 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 January 25 2007 CSE 120 Lecture 6 Semaphores and Monitors 2007 Keith Marzullo and Geoffrey M Voelker 5 Semaphore Types z z Semaphores come in two types Mutex semaphore or binary semaphore z 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 g reading g Multiple threads can pass the semaphore Number of threads determined by the semaphore count mutex has count 1 counting has count N January 25 2007 CSE 120 Lecture 6 Semaphores and Monitors 2007 Keith Marzullo and Geoffrey M Voelker 6 3 Using Semaphores z 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 put balance account 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 January 25 2007 wait S wait S put balance account balance signal S signal S signal S CSE 120 Lecture 6 Semaphores and Monitors 2007 Keith Marzullo and Geoffrey M Voelker 7 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 z th d l thread sleep assumes iinterrupts t t are disabled di bl d z z 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 January 25 2007 CSE 120 Lecture 6 Semaphores and Monitors 2007 Keith Marzullo and Geoffrey M Voelker 8 4 Using Semaphores z We ve looked at a simple example for using synchronization z Mutual exclusion while accessing a bank account Now we re going to use semaphores to look at more interesting examples Readers Writers Bounded Buffers January 25 2007 CSE 120 Lecture 6 Semaphores and Monitors 2007 Keith Marzullo and Geoffrey M Voelker 9 Readers Writers Problem z Readers Writers Problem An object j is shared among g 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 z z 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 January 25 2007 CSE 120 Lecture 6 Semaphores and Monitors 2007 Keith Marzullo and Geoffrey M Voelker 10 5 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 January 25 2007 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 2007 Keith Marzullo and Geoffrey M Voelker 11 Readers Writers Notes z w or r provides mutex between readers and writers z z If a writer is writing where will readers be waiting Once a writer exits all readers can fall through z z z z 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 g 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 January 25 2007 CSE 120 Lecture 6 Semaphores and Monitors 2007 Keith Marzullo and Geoffrey M Voelker 12 6 Bounded Buffer z Problem There is a set of resource buffers shared by producer and consumer threads P d Producer i
View Full Document
Unlocking...