1CSE 120CSE 120Principles of Operating Principles of Operating SystemsSystemsSystemsSystemsWinter 2007Winter 2007Lecture 6: Semaphores and MonitorsLecture 6: Semaphores and MonitorsKeith Keith MarzulloMarzullo and Geoffrey M. and Geoffrey M. VoelkerVoelkerAnnouncementsAnnouncementsz Homework #2 outzEmail questionzEmail question Why not have an idle thread in Nachos? [hint: a purely pragmatic reason]z Any questions on the project?January 25, 2007CSE 120 – Lecture 6 – Semaphores and Monitors© 2007 Keith Marzullo and Geoffrey M. Voelker22HigherHigher--Level SynchronizationLevel Synchronizationz We looked at using locks to provide mutual exclusionzLocks work, but they have some drawbacks whenzLocks work, but they have some drawbacks when critical sections are long Spinlocks – inefficient Disabling interrupts – can miss or delay important eventsz Instead, we want synchronization mechanisms that Block waiters Leave interrupts enabled inside the critical sectionLktt hihll hiJanuary 25, 2007CSE 120 – Lecture 6 – Semaphores and Monitors© 2007 Keith Marzullo and Geoffrey M. Voelker3zLook at two common high-level mechanisms Semaphores: binary (mutex) and counting Monitors: mutexes and condition variablesz Use them to solve common synchronization problemsSemaphoresSemaphoresz Semaphores are an abstract data type that provides mutual exclusion to critical sectionsBl k it i t t bl d ithi CSBlock waiters, interrupts enabled within CS Described by Dijkstra in THE system in 1968z Semaphores can also be used as atomic counters More laterz 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 enterJanuary 25, 2007CSE 120 – Lecture 6 – Semaphores and Monitors© 2007 Keith Marzullo and Geoffrey M. Voelker4signal(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.z Semaphore safety property: a semaphore's value is always greater than or equal to 0.3Blocking in SemaphoresBlocking in Semaphoresz Associated with each semaphore is a queue of waiting processesprocessesz When wait() is called by a thread: If semaphore is open, thread continues If semaphore is closed, thread blocks on queuez Then signal() opens the semaphore: If a thread is waiting on the queue, the thread is unblockedIf no threads are waiting on the queue the signal isJanuary 25, 2007CSE 120 – Lecture 6 – Semaphores and Monitors© 2007 Keith Marzullo and Geoffrey M. Voelker5If 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 counterSemaphore TypesSemaphore Typesz Semaphores come in two typeszMutexsemaphore (orbinarysemaphore)zMutexsemaphore (or binarysemaphore) Represents single access to a resource Guarantees mutual exclusion to a critical sectionz 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)January 25, 2007CSE 120 – Lecture 6 – Semaphores and Monitors© 2007 Keith Marzullo and Geoffrey M. Voelker6(g, g) Multiple threads can pass the semaphore Number of threads determined by the semaphore “count”» mutex has count = 1, counting has count = N4Using SemaphoresUsing Semaphoresz Use is similar to our locks, but semantics are differentstruct Semaphore {wait(S);struct Semaphore {int value;Queue q;} S;withdraw (account, amount) {wait(S);balance = get_balance(account);balance = balance – amount;put balance(account balance);wait(S);balance = get_balance(account);balance = balance – amount;wait(S);put_balance(account, balance);signal(S);wait(S);Threads blockcritical sectionJanuary 25, 2007CSE 120 – Lecture 6 – Semaphores and Monitors© 2007 Keith Marzullo and Geoffrey M. Voelker7put_balance(account, balance);signal(S);return balance;}signal(S);…signal(S);…signal(S);It is undefined which thread runs after a signalSemaphores in NachosSemaphores in Nachoswait (S) {Disable interrupts;signal (S) {Disable interrupts;th d l() it t di bldwhile (S->value == 0) {enqueue(S->q, current_thread);thread_sleep(current_thread);}S->value = S->value – 1;Enable interrupts;}thread = dequeue(S->q);thread_start(thread);S->value = S->value + 1;Enable interrupts;}January 25, 2007CSE 120 – Lecture 6 – Semaphores and Monitors© 2007 Keith Marzullo and Geoffrey M. Voelker8zthread_sleep() assumes interrupts are disabled Note that interrupts are disabled only to enter/leave critical section How can it sleep with interrupts disabled?z Need to be able to reference current threadz What happens if “while (value !=0)” is an “if (value != 0)”?5Using SemaphoresUsing Semaphoresz We’ve looked at a simple example for using synchronizationsynchronization Mutual exclusion while accessing a bank accountz Now we’re going to use semaphores to look at more interesting examples Readers/Writers Bounded BuffersJanuary 25, 2007CSE 120 – Lecture 6 – Semaphores and Monitors© 2007 Keith Marzullo and Geoffrey M. Voelker9Readers/Writers ProblemReaders/Writers Problemz Readers/Writers Problem:An object is shared among several threadsjg 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 How can we use semaphores to control access to the object to implement this protocol?zUse three variablesJanuary 25, 2007CSE 120 – Lecture 6 – Semaphores and Monitors© 2007 Keith Marzullo and Geoffrey M. Voelker10zUse three variables int readcount – number of threads reading object Semaphore mutex – control access to readcount Semaphore w_or_r – exclusive writing or reading6// number of readersReaders/WritersReaders/Writersreader {int readcount = 0;// mutual exclusion to readcountSemaphore mutex = 1;// exclusive writer or readerSemaphore w_or_r = 1;writer {wait(w_or_r); // lock out readerswait(mutex); // lock readcountreadcount += 1; // one more readerif (readcount == 1)wait(w_or_r); // synch w/
View Full Document
Unlocking...