CSE 120 Principles of Operating Systems Fall 2004 Lecture 7 Semaphores and Monitors Geoffrey M Voelker Announcements z UCSD CSE Programming Contest Saturday 10 16 Why should you go To be like John Rapp http www cse ucsd edu users calder UCSDProgramContest October 12 2004 CSE 120 Lecture 7 Semaphores and Monitors 2004 Geoffrey M Voelker 2 1 Announcements z z Homework 2 out Next week z Email question z I ll be in Beijing No class on Tuesday 10 19 work on project Prof Keith Marzullo will give the lecture on 10 21 Why not have an idle thread in Nachos hint a purely pragmatic reason Any questions on the project October 12 2004 CSE 120 Lecture 7 Semaphores and Monitors 2004 Geoffrey M Voelker 3 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 z Instead we want synchronization mechanisms that z Block waiters Leave interrupts enabled inside the critical section Look at two common high level mechanisms 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 12 2004 CSE 120 Lecture 7 Semaphores and Monitors 2004 Geoffrey M Voelker 4 2 Semaphores z Semaphores are another data structure that provides mutual exclusion to critical sections z Semaphores can also be used as atomic counters z Block waiters interrupts enabled within CS Described by Dijkstra in THE system in 1968 More later Semaphores support two operations wait semaphore decrement block until semaphore is open signal semaphore increment allow another thread to enter Also P after the Dutch word for test or down Also V after the Dutch word for increment or up October 12 2004 CSE 120 Lecture 7 Semaphores and Monitors 2004 Geoffrey M Voelker 5 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 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 12 2004 CSE 120 Lecture 7 Semaphores and Monitors 2004 Geoffrey M Voelker 6 3 Semaphore Types z z Semaphores come in two types Mutex semaphore z Represents single access to a resource Guarantees mutual exclusion to a critical section Counting 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 October 12 2004 CSE 120 Lecture 7 Semaphores and Monitors 2004 Geoffrey M Voelker 7 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 12 2004 wait S wait S put balance account balance signal S signal S signal S CSE 120 Lecture 7 Semaphores and Monitors 2004 Geoffrey M Voelker 8 4 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 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 12 2004 CSE 120 Lecture 7 Semaphores and Monitors 2004 Geoffrey M Voelker 9 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 October 12 2004 CSE 120 Lecture 7 Semaphores and Monitors 2004 Geoffrey M Voelker 10 5 Readers Writers Problem z Readers Writers Problem 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 int readcount number of threads reading object Semaphore mutex control access to readcount Semaphore w or r exclusive writing or reading October 12 2004 CSE 120 Lecture 7 Semaphores and Monitors 2004 Geoffrey M Voelker 11 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 12 2004 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 2004 Geoffrey M Voelker 12 6 Readers Writers Notes z If there is a writer z Once a writer exits all readers can fall through z z Which reader gets to go first The last reader to exit signals a waiting writer 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 12 2004 CSE 120 Lecture 7 Semaphores and Monitors 2004 Geoffrey M Voelker 13 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 z Consumer removes resources from the buffer set z Output disk blocks memory pages processes etc 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 October 12 2004 CSE 120 Lecture 7 Semaphores and Monitors 2004 Geoffrey M Voelker 14 7
View Full Document
Unlocking...