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

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

    }
</font></pre>
The keyword <samp><font color="0f0fff">monitor</font></samp> tells the compiler to add a field
<pre><font color="0f0fff">
        Semaphore mutex = 1;
</font></pre>
to the class, add a call of <samp><font color="0f0fff">mutex.down()</font></samp> to the beginning of each method,
and put a call of <samp><font color="0f0fff">mutex.up()</font></samp> at each return point in each method.
<p>
The other way semaphores are used is to block a process when it cannot
proceed until another process does something.
For example, a consumer, on discovering that the buffer is empty, has to
wait for a producer;
a philosopher, on getting hungry, may have to wait for a neighbor to
finish eating.
To provide this facility, monitors can have a special kind of variable
called a <em>condition variable</em>.
<pre><font color="0f0fff">
    class Condition {
        public void signal();
        public void wait();
    }
</font></pre>
A condition variable is like a semaphore, with two differences:
<ol>
<li>
A semaphore counts the number of excess <samp><font color="0f0fff">up</font></samp> operations, but a
<samp><font color="0f0fff">signal</font></samp> operation on a condition variable has no effect unless some
process is waiting.
A <samp><font color="0f0fff">wait</font></samp> on a condition variable <em>always</em> blocks the calling
process.
<li>
A <samp><font color="0f0fff">wait</font></samp> on a condition variable <em>atomically</em> does an <samp><font color="0f0fff">up</font></samp> on
the monitor mutex and blocks the caller.
In other words if <samp><font color="0f0fff">c</font></samp> is a condition variable <samp><font color="0f0fff">c.wait()</font></samp> is rather
like <samp><font color="0f0fff">mutex.up(); c.down();</font></samp> except that both operations are done
together as a single atomic action.
</ol>
Here is a solution to the Bounded Buffer problem using monitors.
<pre><font color="0f0fff">
    monitor BoundedBuffer {
        Buffer b;
        Condition nonfull, nonempty;
        public void enter_item(Object item) {
            if (b.isFull())
                nonfull.wait();
            b.enter_item(item);
            nonempty.signal();
        }
        public Object remove_item() {
            if (b.isEmpty())
                nonempty.wait();
            item result = b.remove_item();
            nonfull.signal();
            return result;
        }
    }
</font></pre>
In general, each condition variable is associated with some logical condition
on the state of the monitor (some expression that may be either true or false).
If a process discovers, part-way through a method, that some logical condition
it needs is not satisfied, it waits on the corresponding condition
variable.
Whenever a process makes one of these condtions true, it signals the
corresponding condition variable.
When the waiter wakes up, he knows that the problem that caused him
to go to sleep has been fixed, and he may immediately proceed.
For this kind of reasoning to be valid, it is important that nobody
else sneak in between the time that the signaller does the signal
and the waiter wakes up.
Thus, calling <samp><font color="0f0fff">signal</font></samp> blocks the signaller on yet another queue
and immediately wakes up the waiter (if there are multiple processes
blocked on the same condition variable, the one waiting the longest
wakes up).
When a process leaves the monitor (returns from one of its methods),
a sleeping signaller, if any, is allowed to continue.
Otherwise, the monitor mutex is released, allowing a new process to
enter the monitor.
In summary, waiters are give precedence over signallers.
<p>
This strategy, while nice for avoiding certain kinds of errors, is
very inefficient.
As we will see when we consider implemenation, it is expensive to swith
processes.
Consider what happens when a consumer is blocked on the <samp><font color="0f0fff">nonempty</font></samp>
condition variable and a producer calls <samp><font color="0f0fff">enter_item</font></samp>.
<ul>
<li> The producer adds the item to the buffer and calls <samp><font color="0f0fff">nonempty.signal()</font></samp>.
<li> The producer is immediately blocked and the consumer is allowed to
continue.
<li>The consumer removes the item from the buffer and leaves the monitor.
<li>The producer wakes up, and since the <samp><font color="0f0fff">signal</font></samp> operation was the last
statement in <samp><font color="0f0fff">enter_item</font></samp>, leaves the monitor.
</ul>
There is an unnecessary switch from the producer to the consumer and back 
again.
<p>
To avoid this inefficiency, all recent implementations of monitors replace
<samp><font color="0f0fff">signal</font></samp> with <samp><font color="0f0fff">notify</font></samp>.
The <samp><font color="0f0fff">notify</font></samp> operation is like <samp><font color="0f0fff">signal</font></samp> in that it awakens a process
waiting on the condition variable if there is one and otherwise does
nothing.
But as the name implies, a <samp><font color="0f0fff">notify</font></samp> is a ``hint'' that the associated logical
condition might be true, rather than a guarantee that it is true.
The process that called <samp><font color="0f0fff">notify</font></samp> is allowed to continue.
Only when it leaves the monitor is the awakened waiter allowed to continue.
Since the logical condition might not be true anymore, the waiter needs
to recheck it when it wakes up.
For example the Bounded Buffer monitor should be rewritten to replace
<pre><font color="0f0fff">
    if (b.isFull())
        nonfull.wait();
</font></pre>
with
<pre><font color="0f0fff">
    while (b.isFull())
        nonfull.wait();
</font></pre>
<a name="java_monitors">
<p>
</a>
Java has built into it something like this, but with two key differences.
First, instead of marking a whole class as <samp><font color="0f0fff">monitor</font></samp>, you have to
remember to mark each method as <samp><font color="0f0fff">synchronized</font></samp>.
Every object is potentially a monitor.
Second, there are no explicit condition variables.
In effect, every monitor has exactly one anonymous condition variable.
Instead of writing <samp><font color="0f0fff">c.wait()</font></samp> or <samp><font color="0f0fff">c.notify()</font></samp>, where <samp><font color="0f0fff">c</font></samp> is a
condition variable, you simply write <samp><font color="0f0fff">wait()</font></samp> or <samp><font color="0f0fff">notify()</font></samp>.
A solution to the Bounded Buffer problem in Java might look like this:
<pre><font color="0f0fff">
    class BoundedBuffer {
        Buffer b;
        synchronized public void enter_item(Object item) {
            while (b.isFull())
                wait();
            b.enter_item(item);
            notifyAll();
        }
        synchronized public Object remove_item() {
            while (b.isEmpty())
                wait();
            item result = b.remove_item();
            notifyAll();
            return result;
        }
    }
</font></pre>
Instead of waiting on a specific condition variable corresponding to
the condition you want (buffer non-empty or buffer non-full),
you simply <samp><font color="0f0fff">wait</font></samp>, and whenever you make either of these conditions true,
you simply <samp><font color="0f0fff">notifyAll</font></samp>.
The operation <samp><font color="0f0fff">notifyAll</font></samp> is similar to <samp><font color="0f0fff">notify</font></samp>, but it wakes up
all the processes that are waiting rather than just the one that
has been waiting the longest.
In general, a process has to use <samp><font color="0f0fff">notifyAll</font></samp> rather than <samp><font color="0f0fff">notify</font></samp>, since
the process that has been waiting the longest may not
necessarily be waiting for the condition that the notifier just made true.
In this particular case, you can get away with <samp><font color="0f0fff">notify</font></samp> because there
cannot be both producers and consumers waiting at the same time.

<a name="messages"> <h4> Messages </h4> </a>
<p>
Since shared variables are such a source of errors, why not get rid of
them altogether?
In this section, we assume there is no shared memory between processes.
That raises a new problem.
Instead of worrying about how to keep processes from interferring with
each other, we have to figure out how to let them cooperate.
Systems without shared memory provide message-passing facilities that
look something like this:
<pre><font color="0f0fff">
    send(destination, message);
    receive(source, messsage_buffer);
</font></pre>
The details vary substantially from system to system.
<dl>
<dt>
<strong>Naming</strong>
<dd>
How are <samp><font color="0f0fff">destination</font></samp> and <samp><font color="0f0fff">source</font></samp> specified?
Each process may directly name the other, or there may be some sort of
<em>mailbox</em> or <em>message queue</em> object to be used as the
<samp><font color="0f0fff">destination</font></samp> of a <samp><font color="0f0fff">send</font></samp> or the <samp><font color="0f0fff">source</font></samp> of a <samp><font color="0f0fff">receive</font></samp>.
Some systems allow a <em>set</em> of destinations (called <em>multicast</em>
and meaning ``send a copy of the message to each destination'')
and/or a <em>set</em> of sources, meaning ``receive a message from any
one of the sources.''
A particularly common feature is to allow <samp><font color="0f0fff">source</font></samp> to be ``any'', meaning
that the reciever is willing to receive a message from any other process
that is willing to send a message to it.
<dt>
<strong>Synchronization</strong>
<dd>
Does <samp><font color="0f0fff">send</font></samp> (or <samp><font color="0f0fff">receive</font></samp>) block the sender, or can it immediately continue?
One common combination is non-blocking <samp><font color="0f0fff">send</font></samp> together with blocking
<samp><font color="0f0fff">receive</font></samp>.
Another possibility is <em>rendezvous</em>, in which both <samp><font color="0f0fff">send</font></samp> and
<samp><font color="0f0fff">receive</font></samp> are blocking.
Whoever gets there first waits for the other one.
When a sender and matching receiver are both waiting, the message is
transferred and both are allowed to continue.
<dt>
<strong>Buffering</strong>
<dd>
Are messages copied directly from the sender's memory to the receiver's
memory, or are first copied into some sort of ``system'' memory in between?
<dt>
<strong>Message Size</strong>
<dd>
Is there an upper bound on the size of a message?
Some systems have small, fixed-size messages to send signals or status
information and a separate facility for transferring large blocks of data.
</dl>
These design decisions are not independent.
For example, non-blocking <samp><font color="0f0fff">send</font></samp> is generally only available in systems
that buffer messages.
Blocking <samp><font color="0f0fff">receive</font></samp> is only useful if there is some way to say
``receive from any'' or receive from a set of sources.
<p>
Message-based communication between processes is particularly attractive
in distributed systems (such as computer networks) where processes are
on different computers and it would be difficult or impossible to allow
them to share memory.
But it is also used in situations where processes <em>could</em> share
memory but the operating system designer chose not allow sharing.
One reason is to avoid the bugs that can occur with sharing.
Another is to build a wall of protection between processes that don't
trust each other.
Some systems even combine message passing with shared memory.
A message may include a pointer to a region of (shared) memory.
The message is used as a way of transferring ``ownership'' of the region.
There might be a convention that a process that wants to access some
shared memory had to request permission from its current owner (by sending
a message).  The second algorithm of project 2 has this flavor.
<p>
Unix is a message-based system (at the user level).
Processes do not share memory but communicate through
<em>pipes</em>.<!WA18><!WA18><!WA18><!WA18><!WA18><a href="#footnote"><sup>3</sup></a>
A pipe looks like an output stream connected to an input stream by
a chunk of memory used to make a queue of bytes.
One process sends data to the output stream the same way it would
write data to a file, and another reads from it the way it would
read from a file.
In the terms outlined above,
naming is indirect (with the pipe acting as a mailbox or message queue),
<samp><font color="0f0fff">send</font></samp> (called <samp><font color="0f0fff">write</font></samp> in Unix) is non-blocking, while <samp><font color="0f0fff">recieve</font></samp> (called
<samp><font color="0f0fff">read</font></samp>) is blocking, and there is buffering in the operating system.
At first glance it would appear that the message size is unbounded, but
it would actually be more accurate to say each ``message'' is one byte.
The amount of data sent in a <samp><font color="0f0fff">write</font></samp> or recieved in a <samp><font color="0f0fff">read</font></samp> is unbounded,
but the boundaries between writes are erased in the pipe:
If the sender does three writes of 60 bytes each and the receive does
two reads asking for 100 bytes, it will get back the first 100 bytes the
first time and the remaining 80 bytes the second time.
<p>

<!WA19><!WA19><!WA19><!WA19><!WA19><a href="http://www.cs.wisc.edu/~cs537-1/deadlock.html">Continued...</a>

<hr>
<a name="footnote">
<sup>1</sup>In the original semaphore, the <samp><font color="0f0fff">up</font></samp> and <samp><font color="0f0fff">down</font></samp> operations
were called <samp><font color="0f0fff">V()</font></samp> and <samp><font color="0f0fff">P()</font></samp>, respectively, but people had trouble
remembering which was which.
Some books call them <samp><font color="0f0fff">signal</font></samp> and <samp><font color="0f0fff">wait</font></samp>, but we will be using those
names for other operations later.
<p>
<sup>2</sup>Monitors are <em>not</em> available in this form in Java.
We are using Java as a vehicle for illustrating various ideas present
in other languages.  See <!WA20><!WA20><!WA20><!WA20><!WA20><a href="#java_monitors">below</a> for a similar
feature that <em>is</em> available in Java.
<p>
<sup>3</sup>There are so many versions of Unix that just about any blanket
statement about it is sure to be a lie.
Some versions of Unix allow memory to be shared between processes,
and some have other ways for processes to communicate other than pipes.
</a>
<hr>

<address>
<i>
<!WA21><!WA21><!WA21><!WA21><!WA21><a HREF="mailto:[e-mail]">
[e-mail]
</a>
<br>
Thu Oct 31 15:38:53 CST 1996
</i>
</address>
<br>
Copyright &#169; 1996 by Marvin Solomon.  All rights reserved.

</body>

</html>