1CSE 120CSE 120Principles of Operating Principles of Operating SystemsSystemsFall 2002Fall 2002Lecture 7: Semaphores and MonitorsLecture 7: Semaphores and MonitorsGeoffrey M. VoelkerGeoffrey M. VoelkerOctober 15, 2002 CSE 120 – Lecture 7 – Semaphores and Monitors 2© 2002 Geoffrey M. VoelkerAnnouncementsAnnouncementsz Programming ContestX Good turnout, perhaps a bit more difficult than expectedz Race ConditionX Chancellor’s 5K Run/Walk on Fri 10/18X How can you resist that gold star?2October 15, 2002 CSE 120 – Lecture 7 – Semaphores and Monitors 3© 2002 Geoffrey M. VoelkerHigherHigher--Level SynchronizationLevel Synchronizationz We looked at using locks to provide mutual exclusionz Locks work, but they have some drawbacks when critical sections are longX Spinlocks – inefficientX Disabling interrupts – can miss or delay important eventsz Instead, we want synchronization mechanisms thatX Block waitersX Leave interrupts enabled inside the critical sectionz Look at two common high-level mechanismsX Semaphores: binary (mutex) and countingX Monitors: mutexes and condition variablesz Use them to solve common synchronization problemsOctober 15, 2002 CSE 120 – Lecture 7 – Semaphores and Monitors 4© 2002 Geoffrey M. VoelkerSemaphoresSemaphoresz Semaphores are another data structure that provides mutual exclusion to critical sectionsX Block waiters, interrupts enabled within CSX Described by Dijkstra in THE system in 1968z Semaphores can also be used as atomic countersX More laterz 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()3October 15, 2002 CSE 120 – Lecture 7 – Semaphores and Monitors 5© 2002 Geoffrey M. VoelkerBlocking in SemaphoresBlocking in Semaphoresz Associated with each semaphore is a queue of waiting processesz When wait() is called by a thread:X If semaphore is open, thread continuesX If semaphore is closed, thread blocks on queuez Then signal() opens the semaphore:X If a thread is waiting on the queue, the thread is unblockedX 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 counterOctober 15, 2002 CSE 120 – Lecture 7 – Semaphores and Monitors 6© 2002 Geoffrey M. VoelkerSemaphore TypesSemaphore Typesz Semaphores come in two typesz Mutex semaphoreX Represents single access to a resourceX Guarantees mutual exclusion to a critical sectionz Counting semaphoreX Represents a resource with many units available, or a resource that allows certain kinds of unsynchronized concurrent access (e.g., reading)X Multiple threads can pass the semaphoreX Number of threads determined by the semaphore “count”» mutex has count = 1, counting has count = N4October 15, 2002 CSE 120 – Lecture 7 – Semaphores and Monitors 7© 2002 Geoffrey M. VoelkerUsing SemaphoresUsing Semaphoresz Use is similar to our locks, but semantics are differentstruct 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;wait(S);put_balance(account, balance);signal(S);wait(S);…signal(S);…signal(S);Threads blockIt is undefined which thread runs after a signalOctober 15, 2002 CSE 120 – Lecture 7 – Semaphores and Monitors 8© 2002 Geoffrey M. VoelkerSemaphores in NachosSemaphores in Nachosz thread_sleep() assumes interrupts are disabledX Note that interrupts are disabled only to enter/leave critical sectionX How can it sleep with interrupts disabled?z Need to be able to reference current threadwait (S) {Disable interrupts;while (S->value == 0) {enqueue(S->q, current_thread);thread_sleep(current_thread);}S->value = S->value – 1;Enable interrupts;}signal (S) {Disable interrupts;thread = dequeue(S->q);thread_start(thread);S->value = S->value + 1;Enable interrupts;}5October 15, 2002 CSE 120 – Lecture 7 – Semaphores and Monitors 9© 2002 Geoffrey M. VoelkerUsing SemaphoresUsing Semaphoresz We’ve looked at a simple example for using synchronizationX Mutual exclusion while accessing a bank accountz Now we’re going to use semaphores to look at more interesting examplesX Readers/WritersX Bounded BuffersOctober 15, 2002 CSE 120 – Lecture 7 – Semaphores and Monitors 10© 2002 Geoffrey M. VoelkerReaders/Writers ProblemReaders/Writers Problemz Readers/Writers Problem:X An object is shared among several threadsX Some threads only read the object, others only write itX We can allow multiple readersX But only one writerz How can we use semaphores to control access to the object to implement this protocol?z Use three variablesX int readcount – number of threads reading objectX Semaphore mutex – control access to readcountX Semaphore w_or_r – exclusive writing or reading6October 15, 2002 CSE 120 – Lecture 7 – Semaphores and Monitors 11© 2002 Geoffrey M. Voelker// number of readersint readcount = 0;// mutual exclusion to readcountSemaphore mutex = 1;// exclusive writer or readingSemaphore w_or_r = 1;writer {wait(w_or_r); // lock out readersWrite;signal(w_or_r); // up for grabs}Readers/WritersReaders/Writersreader {wait(mutex); // lock readcountreadcount += 1; // one more readerif (readcount == 1)wait(w_or_r); // synch w/ writerssignal(mutex); // unlock readcountRead;wait(mutex); // lock readcountreadcount -= 1; // one less readerif (readcount == 0)signal(w_or_r); // up for grabssignal(mutex); // unlock readcount}}October 15, 2002 CSE 120 – Lecture 7 – Semaphores and Monitors 12© 2002 Geoffrey M. VoelkerReaders/Writers NotesReaders/Writers Notesz If there is a writerX First reader blocks on w_or_rX All other readers block on mutexz Once a writer exits, all readers can fall throughX Which reader gets to go first?z The last reader to exit signals a waiting writerX If no writer, then readers can continuez If readers and writers are waiting on w_or_r, and a writer exits, who goes first?z Why doesn’t a writer need to use mutex?7October 15, 2002 CSE 120 – Lecture 7 – Semaphores and Monitors 13© 2002 Geoffrey M. VoelkerBounded BufferBounded Bufferz Problem: There is a set of resource buffers shared by producer and
View Full Document
Unlocking...