http:^^www.cs.wisc.edu^~cs537-1^processes.html

This data set contains WWW-pages collected from computer science departments of various universities

<li> The value is never permitted to be negative.  If the value is
zero when a process calls <samp><font color="0f0fff">down</font></samp>, that process is forced to wait
(it goes into <em>blocked</em> state) until some other process calls <samp><font color="0f0fff">up</font></samp>
on the semaphore.
<li> The <samp><font color="0f0fff">up</font></samp> and <samp><font color="0f0fff">down</font></samp> operations are <em>atomic</em>:
A correct implementation must make it appear that they occur
<em>instantaneously</em>.
In other words, two operations on the same semaphore attempted at the
same time must not be interleaved.
(In the case of a <samp><font color="0f0fff">down</font></samp> operation that blocks the caller, it is
the actual decermenting that must be atomic; it is ok if other things happen
while the calling process is blocked).
</ol>
Our first example uses semaphores to fix the <samp><font color="0f0fff">deposit</font></samp> function above.
<pre><font color="0f0fff">
    shared Semaphore mutex = new Semaphore(1);
    void deposit(int amount) {
        mutex.down();
        balance += amount;
        mutex.up();
    }
</font></pre>
We assume there is one semaphore, which we call <samp><font color="0f0fff">mutex</font></samp> (for ``mutual
exclusion'') shared by all processes.
The keyword <samp><font color="0f0fff">shared</font></samp> (which is <em>not</em> Java) will be omitted if it
is clear which variables are shared and which are private (have a separate
copy for each process).
Semaphores are useless unless they are shared, so we will omit <samp><font color="0f0fff">shared</font></samp>
before <samp><font color="0f0fff">Semaphore</font></samp>.
Also we will abreviate the declaration and initialization as
<pre><font color="0f0fff">
    Semaphore mutex = 1;
</font></pre>
Let's see how this works.
If only one process wants to make a deposit, it does <samp><font color="0f0fff">mutex.down()</font></samp>, decreasing
the value of <samp><font color="0f0fff">mutex</font></samp> to zero, adds its amount to the balance, and returns
the value of <samp><font color="0f0fff">mutex</font></samp> to one.
If two processes try to call <samp><font color="0f0fff">deposit</font></samp> at about the same time, one
of them will get to do the <samp><font color="0f0fff">down</font></samp> operation first (because <samp><font color="0f0fff">down</font></samp> is atomic!).
The other will find that <samp><font color="0f0fff">mutex</font></samp> is already zero and be forced to wait.
When the first process finishes adding to the balance, it does <samp><font color="0f0fff">mutex.up()</font></samp>,
returning the value to one and allowing the other process to complete
its <samp><font color="0f0fff">down</font></samp> operation.
If there were three processes trying at the same time,
one of them would do the <samp><font color="0f0fff">down</font></samp> first, as before, and the other two
would be forced to wait. When the first process did <samp><font color="0f0fff">up</font></samp>, one of the other
two would be allowed to complete its <samp><font color="0f0fff">down</font></samp> operation, but then <samp><font color="0f0fff">mutex</font></samp>
would be zero again, and the third process would continue to wait.

<a name="bounded_buffer"> <h4> The Bounded Buffer Problem </h4> </a>
Suppose there are <em>producer</em> and <em>consumer</em> processes.
There may be many of each.
Producers somehow produce objects, which consumers then use for something.
There is one <samp><font color="0f0fff">Buffer</font></samp> object used to pass objects from producers to
consumers.
We will not show the implementation of <samp><font color="0f0fff">Buffer</font></samp> (it is an easy 367 exercise).
A <samp><font color="0f0fff">Buffer</font></samp> can hold up to <samp><font color="0f0fff">N</font></samp> objects.
The problem is to allow concurrent access to the <samp><font color="0f0fff">Buffer</font></samp> by producers
and consumers, while ensuring that
<ol>
<li>The shared <samp><font color="0f0fff">Buffer</font></samp> data structure is not screwed up by race conditions
in accessing it.
<li>Consumers don't try to remove objects from <samp><font color="0f0fff">Buffer</font></samp> when it is empty.
<li>Producers don't try to add objects to the <samp><font color="0f0fff">Buffer</font></samp> when it is full.
</ol>
When condition (3) is dropped (the <samp><font color="0f0fff">Buffer</font></samp> is assumed to have infinite
capacity), the problem is called the <em>Producer-Consumer Problem</em>
(but Tanenbaum calls the Bounded-Buffer problem ``the Producer-Consumer
Problem'').
Here is a solution.
<pre><font color="0f0fff">
    shared Buffer b;
    Semaphore
        mutex = 1,
        empty = N,
        full = 0;
    
    class Producer implements Runnable {
        public void run() {
            Object item;
            for (;;) {
                item = produce();
                empty.down();
                mutex.down();
                b.enter_item(item);
                mutex.up();
                full.up();
            }
        }
    }
    class Consumer implements Runnable {
        public void run() {
            Object item;
            for (;;) {
                full.down();
                mutex.down();
                item = b.remove_item();
                mutex.up();
                empty.up();
            }
        }
    }
</font></pre>
As before, we surround operations on the shared <samp><font color="0f0fff">Buffer</font></samp> data structure
with <samp><font color="0f0fff">mutex.down()</font></samp> and <samp><font color="0f0fff">mutex.up()</font></samp> to prevent interleaved changes by
two processes (which may screw up the data structure).
The semaphore <samp><font color="0f0fff">full</font></samp> counts the number of objectx in the buffer,
while the semphore <samp><font color="0f0fff">empty</font></samp> counts the number of free slots.
The operation <samp><font color="0f0fff">full.down()</font></samp> in <samp><font color="0f0fff">Consumer</font></samp> atomically waits until there is
something in the buffer and then ``lays claim'' to it by decrementing the
semaphore.
Suppose it was replaced by
<pre><font color="0f0fff">
    while (b.count == 0) { /* do nothing */ }
    mutex.down();
    /* as before */
</font></pre>
It would be possible for one process to see that the buffer was non-empty,
and then have another process remove the last item before it got a chance
to grab the <samp><font color="0f0fff">mutex</font></samp> semapore.
<p>
There is one more fine point to notice here:
Suppose we revesed the <samp><font color="0f0fff">down</font></samp> operations in the consumer
<pre><font color="0f0fff">
    mutex.down();
    full.down();
</font></pre>
and a consumer tries to do these operation when the buffer is empty.
It first grabs the <samp><font color="0f0fff">mutex</font></samp> semaphore and then blocks on the <samp><font color="0f0fff">full</font></samp>
semaphore.
It will be blocked forever because no other process can grab the <samp><font color="0f0fff">mutex</font></samp>
semaphore to add an item to the buffer (and thus call <samp><font color="0f0fff">full.up()</font></samp>).
This situation is called <em>deadlock</em>.
We will study it in length later.

<a name="dining_philosophers"> <h4>The Dining Philosophers</h4> </a>
There are five philosopher processes numbered 0 through 4.
Between each pair of philosophers is a fork.
The forks are also numbered 0 through 4, so that fork <samp><font color="0f0fff">i</font></samp> is between
philosophers <samp><font color="0f0fff">i-1</font></samp> and <samp><font color="0f0fff">i</font></samp> (all arithmetic on fork numbers and philosopher
numbers is <em>modulo</em> 5 so fork 0 is between philosophers 4 and 0).
<center>
<!WA13><!WA13><!WA13><!WA13><!WA13><img align=top src="http://www.cs.wisc.edu/~cs537-1/dphil1.gif">
</center>
Each philosopher alternates between thinking and eating.
To eat, he needs exclusive access to the forks on both size of him.
<pre><font color="0f0fff">
    class Philosopher implements Runnable {
        int i;    // which philosopher
        public void run() {
            for (;;) {
                think();
                take_forks(i);
                eat();
                put_forks(i)
            }
        }
    }
</font></pre>
A first attempt to solve this problem represents each fork as a semaphore:
<pre><font color="0f0fff">
    Semaphore fork[5] = 1;
    void take_forks(int i) {
        fork[i].down();
        fork[i+1].down();
    }
    void put_forks(int i) {
        fork[i].up();
        fork[i+1].up();
    }
</font></pre>
The problem with this solution is that it can lead to deadlock.
Each philosopher picks up his right fork before he tried to pick up his
left fork.
What happends if the timing works out such that all the philosophers
get hungry at the same time, and they all pick up their right forks
before any of them gets a chance to try for his left fork?
Then each philosopher <samp><font color="0f0fff">i</font></samp> will be holding fork <samp><font color="0f0fff">i</font></samp> and waiting
for fork <samp><font color="0f0fff">i+1</font></samp>, and they will all wait forever.
<center>
<!WA14><!WA14><!WA14><!WA14><!WA14><img align=top src="http://www.cs.wisc.edu/~cs537-1/dphil2.gif">
</center>
<p>
There's a very simple solution:
Instead of trying for the <em>right</em> fork first, try for the <em>lower
numbered</em> fork first.
We will show later that this solution <em>cannot</em> lead to deadlock.
You will be implementing a generalization of this technique in
<!WA15><!WA15><!WA15><!WA15><!WA15><a href="http://www.cs.wisc.edu/~cs537-1/project2.html">project 2</a>.
<p>
This solution, while deadlock-free, is still not as good as it could be.
Consider again the situation in which all philosophers get hungry at the
same time and pick up their lower-numbered fork.  Both philosopher
<samp><font color="0f0fff">0</font></samp> and philosopher <samp><font color="0f0fff">4</font></samp> try to grab fork <samp><font color="0f0fff">0</font></samp> first.
Suppose philosopher <samp><font color="0f0fff">0</font></samp> wins.
Since philosopher <samp><font color="0f0fff">4</font></samp> is stuck waiting for fork <samp><font color="0f0fff">0</font></samp>, philosopher <samp><font color="0f0fff">3</font></samp>
will be able to grab both is forks and start eating.
<center>
<!WA16><!WA16><!WA16><!WA16><!WA16><img align=top src="http://www.cs.wisc.edu/~cs537-1/dphil3.gif">
</center>
Philosopher <samp><font color="0f0fff">3</font></samp> gets to eat, but philosophers <samp><font color="0f0fff">0</font></samp> and <samp><font color="0f0fff">1</font></samp> are waiting,
even though neither of them shares a fork with philosopher <samp><font color="0f0fff">3</font></samp>, and
hence one of them could eat right away.
<p>
Dijkstra suggests a better solution.
He shows how to <em>derive</em> the solution by thinking about
two goals of any synchronization problem:
<dl>
<dt>
<strong>Safety</strong>
<dd>
Make sure nothing <em>bad</em> happens.
<dt>
<strong>Liveness</strong>
<dd>
Make sure as much <em>good</em> happens, consistent with the safety criterion.
</dl>
For each philosopher <samp><font color="0f0fff">i</font></samp> let <samp><font color="0f0fff">state[i]</font></samp> be the <em>state</em> of
philosopher <samp><font color="0f0fff">i</font></samp>--one of <samp><font color="0f0fff">THINKING</font></samp>, <samp><font color="0f0fff">HUNGRY</font></samp>, or <samp><font color="0f0fff">EATING</font></samp>.
The safety requirement is that no to adjacent philosophers are simultaneously
eating.
The liveness criterion is that there is no philosopher is hungry unless
one of his neighbors is eating (a hungry philosopher should start eating
unless the saftey criterion prevents him).
More formally,
<dl>
<dt>
<strong>Safety</strong>
<dd>
For all <samp><font color="0f0fff">i</font></samp>, <samp><font color="0f0fff">!(state[i]==EATING && state[i+1]==EATING)</font></samp>
<dt>
<strong>Liveness</strong>
<dd>
For all <samp><font color="0f0fff">i</font></samp>, <samp><font color="0f0fff">!(state[i]==HUNGRY && state[i-1]!=EATING && state[i+1]!=EATING)</font></samp>
</dl>
<p>
With this observation, the solution almost writes itself
(See also Figure 2-20 on page 59 of Tanenbaum.)
<pre><font color="0f0fff">
    Semaphore mayEat[5] = { 0, 0, 0, 0, 0};
    Semaphore mutex = 1;
    int state[5] = { THINKING, THINKING, THINKING, THINKING, THINKING };
    void take_forks(int i) {
        mutex.down();
        state[i] = HUNGRY;
        test(i);
        mutex.up();
        mayEat[i].down();
    }
    void put_forks(int i) {
        mutex.down();
        state[i] = THINKING;
        test(i-1);
        test(i+1);
        mutex.up();
    }
    void test() {
        if (state[i]==HUNGRY &amp;&amp; state[i-1]!=EATING &amp;&amp; state[i+1] != EATING) {
            state[i] = EATING;
            mayEat[i].up();
        }
    }
</font></pre>
The method <samp><font color="0f0fff">test()</font></samp> checks for a violation of liveness at position
<samp><font color="0f0fff">i</font></samp>.
Such a violation can only occur when philosopher <samp><font color="0f0fff">i</font></samp> gets hungry
or one of his neighbors finishes eating.

<a name="monitors"> <h4>Monitors</h4> </a>
<p>
Although semaphores are all you need to solve lots of synchronization
problems, they are rather ``low level'' and error-prone.
As we saw before, a slight error in placement of semaphores (such as
switching the order of the two <samp><font color="0f0fff">down</font></samp> operations in the Bounded Buffer
problem) can lead to big problems.
It is also easy to forget to protect shared variables (such as the bank
balance or the buffer object) with a <samp><font color="0f0fff">mutex</font></samp> semaphore.
A better (higher-level) solution is provided by the <em>monitor</em> (also
invented by Dijkstra).
<p>
If you look at the example uses of semaphores above, you see that
they are used in two rather different ways:
One is simple mutual exclusion.
A semephore (always called <samp><font color="0f0fff">mutex</font></samp> in our examples) is associated with
a shared variable or variables.
Any piece of code that touches these variables is preceded by <samp><font color="0f0fff">mutex.down()</font></samp>
and followed by <samp><font color="0f0fff">mutex.up()</font></samp>.
Since it's hard for a programmer to remember to do this, but easy for
a compiler, why not let the compiler do the work?<!WA17><!WA17><!WA17><!WA17><!WA17><a href="#footnote">
<sup>2</sup></a>
<pre><font color="0f0fff">
    monitor class BankAccount {
        private int balance;
        public void deposit(int amount) {
            balance += amount;
        }
        // etc