CSE 120 Principles of Operating Systems Spring 2009Higher-Level SynchronizationSemaphoresBlocking in SemaphoresSemaphore TypesUsing SemaphoresSemaphores in NachosUsing SemaphoresReaders/Writers ProblemReaders/WritersReaders/Writers NotesBounded BufferBounded Buffer (2)Bounded Buffer (3)Bounded Buffer (4)Semaphore QuestionsSemaphore SummaryMonitorsMonitor SemanticsAccount ExampleMonitors, Monitor Invariants and Condition VariablesCondition VariablesMonitor Bounded BufferMonitor QueuesCondition Vars != SemaphoresSignal SemanticsHoare vs. Mesa MonitorsMonitor Readers and WritersMonitor Readers and WritersMonitor Readers and WritersMonitor Readers and WritersCondition Vars & LocksUsing Cond Vars & LocksMonitors and JavaSummaryNext time…Slide Number 37AnnouncementsElection monitorElection monitorCounting Semaphores with Mutex SemaphoresHow not to do itCSE 120Principles of Operating SystemsSpring 2009Lecture 6: Semaphores and MonitorsGeoffrey M. VoelkerApril 21, 2009 CSE 120 – Lecture 6 – Semaphores and Monitors 2Higher-Level Synchronization We looked at using locks to provide mutual exclusion Locks work, but they have some drawbacks when critical sections are long Spinlocks – inefficient Disabling interrupts – can miss or delay important events Instead, we want synchronization mechanisms that Block waiters Leave interrupts enabled inside the critical section Look at two common high-level mechanisms Semaphores: binary (mutex) and counting Monitors: mutexes and condition variables Use them to solve common synchronization problemsApril 21, 2009 CSE 120 – Lecture 6 – Semaphores and Monitors 3Semaphores Semaphores are an abstract data type that provide mutual exclusion to critical sections Block waiters, interrupts enabled within CS Described by Dijkstra in THE system in 1968 Semaphores can also be used as atomic counters More later 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 enter» Also V() after the Dutch word for increment, or up() That's it! No other operations – not even just reading its value – exist Semaphore safety property: the semaphore value is always greater than or equal to 0April 21, 2009 CSE 120 – Lecture 6 – Semaphores and Monitors 4Blocking in Semaphores Associated with each semaphore is a queue of waiting processes When wait() is called by a thread: 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 counterApril 21, 2009 CSE 120 – Lecture 6 – Semaphores and Monitors 5Semaphore Types Semaphores come in two types Mutex semaphore (or binary semaphore) 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., reading) Multiple threads can pass the semaphore Number of threads determined by the semaphore “count”» mutex has count = 1, counting has count = NApril 21, 2009 CSE 120 – Lecture 6 – Semaphores and Monitors 6Using Semaphores 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 signalcritical section thread_sleep() assumes interrupts are disabled 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)”?April 21, 2009 CSE 120 – Lecture 6 – Semaphores and Monitors 7Semaphores in Nachoswait (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;}April 21, 2009 CSE 120 – Lecture 6 – Semaphores and Monitors 8Using Semaphores We’ve looked at a simple example for using synchronization Mutual exclusion while accessing a bank account Now we’re going to use semaphores to look at more interesting examples Readers/Writers Bounded BuffersApril 21, 2009 CSE 120 – Lecture 6 – Semaphores and Monitors 9Readers/Writers Problem Readers/Writers Problem: 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» Let #r be the number of readers, #w be the number of writers» Safety: (#r ≥ 0) ∧ (0 ≤ #w ≤ 1) ∧ ((#r > 0) ⇒ (#w = 0)) 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 readingApril 21, 2009 CSE 120 – Lecture 6 – Semaphores and Monitors 10// number of readersint readcount = 0;// mutual exclusion to readcountSemaphore mutex = 1;// exclusive writer or readerSemaphore w_or_r = 1;writer {wait(w_or_r); // lock out readersWrite;signal(w_or_r); // up for grabs}Readers/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}} w_or_r provides mutex between readers and writers writer wait/signal, reader wait/signal when readcount goes from 0 to 1 or from 1
View Full Document