CSE 120 Spring 2002 Homework 2
Due 30 April 2002
Problem 1
Consider a problem in which there is a producer p
and two consumers c1 and c2. The producer produces pairs
of values <a, b>. Consumer c1 consumes the a
values of these pairs and c2 consumes the b values of these
pairs.
More precisely, let P be the sequence of
values produced by p, let A be the sequence of values consumed
by c1 and let B be the sequence of values consumed by c2.
Let Pa and P.b be the sequence of a and of b
values in P respectively. Then, for some value of max (which
is the number of buffers),
-
A is a prefix of P.a.
-
B is a prefix of P.b.
-
|P| - |A|
£
max.
-
|P| - |B|
£
max.
-
Each produced value is eventually consumed.
Write a Hoare-style monitor for this problem. It
should have three entry methods: void Put(int a, b) that p
would use to produce values, int GetA(void) that c1 would
use to consume values, and int GetB(void) that c2 would
use to consume values.
Problem 2
Give a semaphore-based implementation of Java monitors. You should give
the code that precedes and follows the invocation of an entry (i.e.,
synchronized)
method, and give the semaphore code for wait,
notify, and
notifyAll.
Problem 3
Annabelle, Bertrand, Chloe and Dag are working on
their term papers in CSE 120, which is a 10,000 word essay on My All-Time
Favorite Race Conditions. To help them work on their papers, they have
one dictionary, two copies of Roget's Thesaurus, and two coffee cups.
-
Annabelle needs to use the dictionary and a thesaurus
to write her paper;
-
Bertrand needs a thesaurus and a coffee cup to write
his paper;
-
Chloe needs a dictionary and a thesaurus to write
her paper;
-
Dag needs two coffee cups to write his paper (he
likes to have a cup of regular and a cup of decaf at the same time to keep
himself in balance).
Consider the following state:
-
Annabelle has a thesaurus and need the dictionary.
-
Bertrand has a thesaurus and a coffee cup.
-
Chloe has the dictionary and needs a thesaurus.
-
Dag has a coffee cup and needs another coffee cup.
-
Is the system deadlocked in this state? Explain using
a resouce allocation graph.
-
Is this state reachable if the four people allocated
and released their resources using the Banker's algorithm? Explain.
last edited 16 April 2002 by kam