Lecture 11OutlineMonitorsCondition Variables 1Condition Variables 2Condition Variables 3Monitor Issues 1Monitor Issues 2Dining Philosophers 1Dining Philosophers 2Dining Philosophers 3Dining Philosophers 4Dining Philosophers 5Dining Philosophers 6Dining Philosophers 7Dining Philosophers 8Implementing Monitors 1Implementing Monitors 2Implementing Monitors 3Implementing Monitors 4Implementing Monitors 5Example Execution 1Example Execution 2PrioritiesResource Allocator 1Resource Allocator 2Resource Allocator 3Friday, February 4 CS 470 Operating Systems - Lecture 11 1Lecture 11Questions?Friday, February 4 CS 470 Operating Systems - Lecture 11 2OutlineMonitorsDining philosophers problem, againImplementing monitorsResource allocation problemFriday, February 4 CS 470 Operating Systems - Lecture 11 3MonitorsRecall: a monitor is basically a class with built-in synchronization. All data is private; only one entry function runs at any given time. I.e., ME to data is ensured.monitor MonitorName{ // shared variable decls // constructor inits vars MonitorName( ){...} // entry member functions entry void P(...){...} entry void Q(...){...} ...}Friday, February 4 CS 470 Operating Systems - Lecture 11 4Condition VariablesWhile ME is ensured, this will not handle some synchronization situations. For example, it is possible to enter the monitor and decide that the state is not what is needed. Cannot stay in, but do not want to leave, either, for efficiency.Introduce condition variables.condition x, y;Friday, February 4 CS 470 Operating Systems - Lecture 11 5Condition VariablesCondition variables have two operations also called wait and signal (but not exactly the same as the semaphore operations):x.wait( ) - suspend the process until a signalx.signal( ) - resume exactly one process; if none are waiting this is a no-opThe goal is for x.signal( ) to be called when the condition the other processes are waiting for becomes true.Friday, February 4 CS 470 Operating Systems - Lecture 11 6Condition Variablesentry void P(...){ ... if (<condition not met>) x.wait ( ); // condition should //be true ...}entry void Q(...){ … if (<condition met>) x.signal( ); …}Friday, February 4 CS 470 Operating Systems - Lecture 11 7Monitor IssuesEven with condition variables, there are some design issues for monitors.In particular, if process Pi has entered the monitor via entry function P and has executed x.wait( ), then process Pj enters via Q and executes x.signal( ), which process executes next? (Since only one process can be executing at any given time.)Two choices arePi executes and Pj waits until Pi leaves the monitorPj continues and Pi waits until Pj leaves the monitorFriday, February 4 CS 470 Operating Systems - Lecture 11 8Monitor IssuesThe first choice seems like the right thing to do, otherwise, by the time Pi gets to execute, Pj may have changed the monitor state again, so Pi would have to check and possibly wait again.The second choice seems more efficient, since it does not require a context switch. Concurrent Pascal used this, but required Pj to exit immediately after issuing x.signal( ).Friday, February 4 CS 470 Operating Systems - Lecture 11 9Dining PhilosophersTo use a monitor to solve the Dining Philosopher's problem, we can have a condition variable for each philospher to wait on.The main idea is that if a philosopher's neighbors are eating, then he must wait.P0P4P1P3P2RICEC0C4C3C2C1Friday, February 4 CS 470 Operating Systems - Lecture 11 10Dining PhilosophersIn order to tell if a neighbor wants to eat, we also have a state variable for each philosopher. There are three possible states:enum State = {thinking, hungry, eating};where thinking means in the RS, eating means in the CS, and hungry means want to eat (i.e., in Entry section).Friday, February 4 CS 470 Operating Systems - Lecture 11 11Dining PhilosophersThe monitor definition starts out:monitor DiningPhilosophers { State state[5]; condition self[5]; DiningPhilosophers(){ for (int i=0; i<5; i++) state[i] = thinking; } : :}Friday, February 4 CS 470 Operating Systems - Lecture 11 12Dining PhilosophersPhilosopher k can transition from hungry to eating only when both neighbors are not eating:(state[(k+4)%5] != eating) // left ok && (state[(k+1)%5] != eating) // right okNote: the left neighbor has index k-1, but this may be a negative value, so for modulus arithmetic, -1 is the same as +(arrSize-1).This test also is used by philosophers that are finished eating (i.e., in the Exit section) to determine if a neighbor should be allowed to eat. Need to check if neighbor is hungry.Friday, February 4 CS 470 Operating Systems - Lecture 11 13Dining Philosophers Wrap this into a utility (not entry) function:void Test (int k) { if (state[(k+4)%5] != eating) // left ok && (state[k] == hungry) // k hungry && (state[(k+1)%5] != eating)) // right ok { state[k] = eating; // allow k to eat self[k].signal(); // in case k is waiting }Friday, February 4 CS 470 Operating Systems - Lecture 11 14Dining PhilosophersThe processes interact with the monitor using two entry functions:PickUp - receives the index of the philosopher process and attempts to enter the eating state. It waits if this is not currently possible.entry void PickUp (int i) { state[i] = hungry; // show intention Test(i); // determine if can eat if (state[i] != eating) // still hungry self[i].wait(); // wait for neighbors}Friday, February 4 CS 470 Operating Systems - Lecture 11 15Dining PhilosophersPutDown - receives the index of the philosopher process. Sets philosopher state back to thinking and attempts to allow neighbors to eat.entry void PutDown (int i) { state[i] = thinking;// done eating // let neighbors know Test((i+4)%5); // left Test((i+1)%5); // right}Friday, February 4 CS 470 Operating Systems - Lecture 11 16Dining PhilosophersTo use the monitor, the philosopher processes share one DiningPhilosophers monitor:shared DiningPhilosophers dp;1. Loop 1.1. dp.PickUp(i) 1.2. Eat 1.3. dp.PutDown(i) 1.4. ThinkAs long as the condition variable queues are FIFO, you can show this solution meets the ME and progress criteria, but you can still have starvation.Friday, February 4 CS 470 Operating Systems - Lecture 11 17Implementing MonitorsJust to show there is no magic here, can show how semaphores can be used
View Full Document