Monitor Solutions to Classical ProblemsAnnouncementsGoals for TodayReview: MonitorsReview: Producer-consumer with a bounded bufferProducer-Consumer using SemaphoresDiscussion about Bounded Buffer SolutionReview: Motivation for Monitors and Condition VariablesCondition VariablesProducer Consumer using MonitorsReminders: Subtle aspectsReview: Mesa vs. Hoare monitorsReview: Can we construct Monitors from Semaphores?Construction of Monitors from Semaphores (con’t)Construction of Hoare Monitors using SemaphoresRevisits: Readers/Writers ProblemRevisit: Readers/Writers ProblemRevisit: Readers-Writers ProblemReaders and WritersSlide 20Slide 21Slide 22Understanding the SolutionSlide 24Slide 25Slide 26Slide 27Slide 28Slide 29Subtle aspects?Comparison with SemaphoresMonitor Solutions to Classical Problems2Announcements•CS 415 Projects graded.–Mean 80.7, High 90 out of 90•CS 414 Homework due Monday.3Goals for Today•Continue with Synchronization Abstractions–Monitors and condition variables•Producer Consumer with Monitors•Readers-Writers problem and solution with Monitors4Review: Monitors•Monitors represent the logic of the program–Wait if necessary–Signal when change something so any waiting threads can proceed•Basic structure of monitor-based program:lock while (need to wait) { unlock condvar.wait(); lock }do something so no need to waitcondvar.signal();unlockCheck and/or updatestate variablesWait if necessaryCheck and/or updatestate variables5Review: Producer-consumer with a bounded buffer•Problem Definition–Producer puts things into a shared buffer (wait if full)–Consumer takes them out (wait if empty)–Use a fixed-size buffer between them to avoid lockstep•Need to synchronize access to this buffer•Correctness Constraints:–Consumer must wait for producer to fill buffers, if none full•scheduling constraint–Producer must wait for consumer to empty buffers, if all full•scheduling constraint–Only one thread can manipulate buffer queue at a time•mutual exclusion•Remember why we need mutual exclusion–Because computers are stupid•General rule of thumb: Use a separate semaphore for each constraint–Semaphore not_empty; // consumer’s constraint–Semaphore not_full; // producer’s constraint–Semaphore mutex; // mutual exclusion6Producer-Consumer using SemaphoresInit: Semaphore mutex = 1; /* for mutual exclusion*/ Semaphore not_full = N; /* number empty buf entries */ Semaphore not_empty = 0; /* number full buf entries */ any_t buf[N]; int tail = 0, head = 0;Producervoid put(char ch) { P(not_full); P(mutex); // add ch to buffer buf[head%N] = ch; head++; V(mutex); V(not_empty);}Consumerchar get() { P(not_empty); P(mutex); // remove ch from buffer ch = buf[tail%N]; tail++; V(mutex); V(not_full); return ch;}7Discussion about Bounded Buffer Solution•Why asymmetry?–Producer does: P(not_full), V(not_empty)–Consumer does: P(not_empty), V(not_full)•Is order of P’s important?–Yes! Can cause deadlock•Is order of V’s important?–No, except that it might affect scheduling efficiency•What if we have 2 producers or 2 consumers?–Do we need to change anything?8Review: Motivation for Monitors and Condition Variables•Semaphores are a huge step up, but:–They are confusing because they are dual purpose:•Both mutual exclusion and scheduling constraints•Example: the fact that flipping of P’s in bounded buffer gives deadlock is not immediately obvious–Cleaner idea: Use locks for mutual exclusion and condition variables for scheduling constraints•Definition: Monitor: a lock and zero or more condition variables for managing concurrent access to shared data–Use of Monitors is a programming paradigm–Some languages like Java provide monitors in the language•The lock provides mutual exclusion to shared data:–Always acquire before accessing shared data structure–Always release after finishing with shared data–Lock initially free9Condition Variables•How do we change the get() routine to wait until something is in buffer?–Could do this by keeping a count of the number of things on the queue (with semaphores), but error prone•Condition Variable: a queue of threads waiting for something inside a critical section–Key idea: allow sleeping inside critical section by atomically releasing lock at time we go to sleep–Contrast to semaphores: Can’t wait inside critical section•Operations:–Wait(&lock): Atomically release lock and go to sleep. Re-acquire lock later, before returning. –Signal(): Wake up one waiter, if any–Broadcast(): Wake up all waiters•Rule: Must hold lock when doing condition variable ops!10Producer Consumer using MonitorsMonitor Producer_Consumer { any_t buf[N]; int n = 0, tail = 0, head = 0; condition not_empty, not_full; void put(char ch) {while(n == N) wait(not_full);buf[head%N] = ch;head++;n++; signal(not_empty); }char get() {while(n == 0) wait(not_empty);ch = buf[tail%N];tail++; n--;signal(not_full);return ch; }11Reminders: Subtle aspects•Notice that when a thread calls wait(), if it blocks it also automatically releases the monitor’s mutual exclusion lock•This is an elegant solution to an issue seen with semaphores–Caller has mutual exclusion and wants to call P(not_empty)… but this call might block–If we just do the call, the solution deadlocks…–But if we first call V(mutex), we get a race condition!12Review: Mesa vs. Hoare monitors•Need to be careful about precise definition of signal and wait. Consider a piece of our dequeue code:while (n==0) {wait(not_empty); // If nothing, sleep}ch = buf[tail%N]; // Get next item–Why didn’t we do this?if (n==0) {wait(not_empty); // If nothing, sleep}ch = buf[tail%N]; // Get next item•Answer: depends on the type of scheduling–Hoare-style (most textbooks):•Signaler gives lock, CPU to waiter; waiter runs immediately•Waiter gives up lock, processor back to signaler when it exits critical section or if it waits again–Mesa-style (Java, most real operating systems):•Signaler keeps lock and processor•Waiter placed on ready queue with no special priority•Practically, need to check condition again after wait13Review: Can we construct Monitors from Semaphores?•Locking aspect is easy: Just use a mutex•Can we implement condition variables this way?Wait() { P(x_sem); }Signal() { V(x_sem); }–Doesn’t work: Wait() may sleep with lock
View Full Document
Unlocking...