CSE 120 Principles of Operating Systems Fall 2002 Lecture 7 Semaphores and Monitors Geoffrey M Voelker Announcements z Programming Contest X z Good turnout perhaps a bit more difficult than expected Race Condition X X Chancellor s 5K Run Walk on Fri 10 18 How can you resist that gold star October 15 2002 CSE 120 Lecture 7 Semaphores and Monitors 2002 Geoffrey M Voelker 2 1 Higher Level Synchronization z z We looked at using locks to provide mutual exclusion Locks work but they have some drawbacks when critical sections are long X X z Instead we want synchronization mechanisms that X X z Block waiters Leave interrupts enabled inside the critical section Look at two common high level mechanisms X X 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 October 15 2002 CSE 120 Lecture 7 Semaphores and Monitors 2002 Geoffrey M Voelker 3 Semaphores z Semaphores are another data structure that provides mutual exclusion to critical sections X X z Semaphores can also be used as atomic counters X z Block waiters interrupts enabled within CS Described by Dijkstra in THE system in 1968 More later Semaphores support two operations X wait semaphore decrement block until semaphore is open Also P after the Dutch word for test or down X signal semaphore increment allow another thread to enter Also V after the Dutch word for increment or up October 15 2002 CSE 120 Lecture 7 Semaphores and Monitors 2002 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 X X z If semaphore is open thread continues If semaphore is closed thread blocks on queue Then signal opens the semaphore X X 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 October 15 2002 CSE 120 Lecture 7 Semaphores and Monitors 2002 Geoffrey M Voelker 5 Semaphore Types z z Semaphores come in two types Mutex semaphore X X z Represents single access to a resource Guarantees mutual exclusion to a critical section Counting semaphore X X X 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 October 15 2002 CSE 120 Lecture 7 Semaphores and Monitors 2002 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 signal S return balance wait S balance get balance account balance balance amount Threads block It is undefined which thread runs after a signal October 15 2002 wait S wait S put balance account balance signal S signal S signal S CSE 120 Lecture 7 Semaphores and Monitors 2002 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 thread sleep assumes interrupts are disabled X X 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 October 15 2002 CSE 120 Lecture 7 Semaphores and Monitors 2002 Geoffrey M Voelker 8 4 Using Semaphores z We ve looked at a simple example for using synchronization X z Mutual exclusion while accessing a bank account Now we re going to use semaphores to look at more interesting examples X X Readers Writers Bounded Buffers October 15 2002 CSE 120 Lecture 7 Semaphores and Monitors 2002 Geoffrey M Voelker 9 Readers Writers Problem z Readers Writers Problem X X X X z z 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 How can we use semaphores to control access to the object to implement this protocol Use three variables X X X int readcount number of threads reading object Semaphore mutex control access to readcount Semaphore w or r exclusive writing or reading October 15 2002 CSE 120 Lecture 7 Semaphores and Monitors 2002 Geoffrey M Voelker 10 5 Readers Writers number of readers int readcount 0 mutual exclusion to readcount Semaphore mutex 1 exclusive writer or reading Semaphore w or r 1 writer wait w or r lock out readers Write signal w or r up for grabs October 15 2002 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 7 Semaphores and Monitors 2002 Geoffrey M Voelker 11 Readers Writers Notes z If there is a writer X X z Once a writer exits all readers can fall through X z z Which reader gets to go first The last reader to exit signals a waiting writer X z First reader blocks on w or r All other readers block on mutex If no writer then readers can continue If readers and writers are waiting on w or r and a writer exits who goes first Why doesn t a writer need to use mutex October 15 2002 CSE 120 Lecture 7 Semaphores and Monitors 2002 Geoffrey M Voelker 12 6 Bounded Buffer z z Problem There is a set of resource buffers shared by producer and consumer threads Producer inserts resources into the buffer set X z Consumer removes resources from the buffer set X z Output disk blocks memory pages processes etc Whatever is generated by the producer Producer and consumer execute at different rates X X X No serialization of one behind the other Tasks are independent easier to think about The buffer set allows each to run without explicit handoff October 15 2002 CSE 120 Lecture 7 Semaphores and Monitors 2002 Geoffrey M Voelker 13 Bounded Buffer 2 z Use three semaphores X mutex mutual exclusion to shared set of buffers Binary semaphore X empty count of empty buffers X full count of full buffers Counting semaphore Counting semaphore October 15 2002 CSE 120 Lecture 7
View Full Document
Unlocking...