DOC PREVIEW
UE CS 470 - LECTURE NOTES

This preview shows page 1-2-3-25-26-27 out of 27 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 11Questions?Friday, February 4 CS 470 Operating Systems - Lecture 11 2OutlineMonitorsDining philosophers problem, againImplementing monitorsResource allocation problemFriday, February 4 CS 470 Operating Systems - Lecture 11 3MonitorsRecall: 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 VariablesWhile 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 VariablesCondition 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 signalx.signal( ) - resume exactly one process; if none are waiting this is a no-opThe 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 IssuesEven 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 arePi executes and Pj waits until Pi leaves the monitorPj continues and Pi waits until Pj leaves the monitorFriday, February 4 CS 470 Operating Systems - Lecture 11 8Monitor IssuesThe 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 PhilosophersTo 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 PhilosophersIn 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 PhilosophersThe 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 PhilosophersPhilosopher 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 PhilosophersThe 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 PhilosophersPutDown - 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 PhilosophersTo 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. ThinkAs 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 MonitorsJust to show there is no magic here, can show how semaphores can be used


View Full Document

UE CS 470 - LECTURE NOTES

Download LECTURE NOTES
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view LECTURE NOTES and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view LECTURE NOTES 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?