UNO CSCI 4500 - Classic Interprocess Communication Problems

Unformatted text preview:

1Computer Science 4500Operating Systems© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 1Operating SystemsModule 5Classic Interprocess Communication ProblemsIn This Module…Dining PhilosophersReaders and Writers© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 2Dining PhilosophersIn this problem, we simulate N(4 or more) philosophers sitting around a circular table.The philosophers spend their entire lives alternating between two states: eating and thinking.© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 3Eating requires the use of a pair of forks. Once a philosopher picks up one fork, it is held until the other fork is picked up and eating is completed.One fork is placed between each pair of philosophers.Can you develop an algorithm that will allow these philosophers to think and eat harmoniously?Four Philosophers at the Table© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 4Dining Philosophers: First Attempt/* Assume the forks are numbered 0 to N-1, with *//* fork 0 to the left of philosopher 0, and fork *//* 1 to the right. Each philosopher executes this *//* function, called with the philosopher number. */#define N 4void philosopher (int i) {hil ( ) {© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 5while (TRUE) {think();pick_up_fork(i); pick_up_fork((i+1) % N);eat();put_down_fork(i); put_down_fork((i+1) % N);}}Unfortunately, this obvious attempt at a solution has a serious problem. Can you see it?The Starving PhilosophersThe key to finding problems in proposed solutions to IPC problems is to consider every allowable sequence of event occurrences, regardless of how unlikely they might be (think of S. Holmes!)© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 6In the proposed solution, consider what would happen if each philosopher simultaneously picked up their left fork.Each philosopher would then wait forever for their right fork, which is being held by their neighbor to the right. All philosophers will then eventually starve!2Another Solution AttemptObserve that each philosopher must have two forks before beginning to eat.We need some way to guarantee the © 2008 Stanley A. Wileman, Jr. Operating Systems Slide 7ygavailability of both forks before proceeding to pick up either one.In this solution, each pair of forks is controlled by a semaphore.Each philosopher now has an additional state, hungry, in which they express their desire to eat.Dining Philosopher’s Solution (Part I)Global Declarations#define N 4 /* # of philosophers */#define LEFT (i-1)%N /* left neighbor # */#define RIGHT (i+1)%N /* right neighbor # *///© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 8#define THINKING 0 /* philosopher states */#define HUNGRY 1#define EATING 2int state[N]; /* each philosopher’s state */semaphore mutex = 1; /* to modify state */semaphore s[N]; /* fork pair availability */Dining Philosopher’s Solution (Part II)Each philosopher executes this code, with the parameter i set to the philosopher’s unique code (in the range 0 to N-1).void philosopher (int i) {© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 9while(TRUE) {think();pick_up_forks(i);eat();put_down_forks(i);}}Dining Philosopher’s Solution (Part III)To get the forks, each philosopher atomically sets its state to HUNGRY, then tests for the availability of the forks, doing an “up” on the fork availability semaphore s[i] if both are available. After leaving the critical section, a “down” on s[i] will succeed if both forks were available. Otherwise the © 2008 Stanley A. Wileman, Jr. Operating Systems Slide 10philosopher will wait for a neighbor to do an “up” on s[i].void pick_up_forks (int i) {down(&mutex); /* state, s mods are atomic */state[i] = HUNGRY; /* say I’m now hungry */test(i); /* up s[i] if I’m hungry & forks free */up(&mutex); /* allow others to change state, s */down(&s[i]); /* continue when forks available */}Dining Philosopher’s Solution (Part IV)A philosopher relinquishes its forks and resumes thinking, but also tests to see if its neighbors are hungry, and if a fork it put down will enable them to eat now.© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 11void put_down_forks (int i) {down(&mutex); /* atomic action */state[i] = THINKING;test(LEFT); /* check left philosopher */test(RIGHT); /* and right philosopher */up(&mutex);}Dining Philosopher’s Solution (Part V)If philosopher i is hungry, and neither of its neighbors are eating, then both forks are available. An “up” is done on the appropriate semaphore (s[i]) in this case. This code is only called from within a critical section.© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 12void test (int i) {if (state[i] == HUNGRY &&state[LEFT] != EATING &&state[RIGHT] != EATING) {state[I] = EATING;up(&s[i]);}}3Readers and WritersIn this problem there are two classes of processes, readers and writers. Each wants to access a shared resource (e.g. a database).Readers will never modify the resource, so many© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 13Readers will never modify the resource, so many of them may be “inside” the database at any time.Writers, of course, will modify the database, so only one writer can be “inside” the database at any instant.The ProblemThe problem is to write code for a generic reader and a generic writer that will permit them to share access to the database, permit multiple access by readers, and atomic access by writers.There are multiple variations on this problem:© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 14There are multiple variations on this problem: Waiting readers have priority over writersWaiting writers have priority over readersFirst-come first-served (a single queue for all waiting processes)…and othersWe will consider only the reader priority problem here.Semaphores in the SolutionThe solution uses two semaphores:db is a binary semaphore (one whose count will always be zero or one) used to guarantee © 2008 Stanley A. Wileman, Jr. Operating Systems Slide 15mutually exclusive access to the database (by either one or more readers or one writer).mutex is another binary semaphore used to guarantee mutually exclusive access to the global variable rc, which holds a count of the number of active reader processes.The Reader’s Codedown(&mutex); /* access rc*/rc = rc + 1; /* one more reader */if (rc == 1)


View Full Document

UNO CSCI 4500 - Classic Interprocess Communication Problems

Download Classic Interprocess Communication Problems
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 Classic Interprocess Communication Problems 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 Classic Interprocess Communication Problems 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?