Objectives

• To improve your understanding of of how message passing can be implemented using monitors, and how timeouts may be added to receive operations.
• To further your understanding of a synchronous messaging.
• To improve your understanding of how message passing may be used implement concurrent programs - as an alternative to monitors.

Preparation

• read through these exercises to familiarize yourself with their content.
• revise the corresponding lecture notes and corresponding chapter (10) of the Magee&Kramer.
• follow this up by studying with the LTSA tool some examples from Chapters 10 of the textbook. Suggested examples are AsyncMsg, MsgCarPark, EntryDemo, and Program 10.8.

Tutorial Exercises

1. * (Ex 10.3 Magee & Kramer) Consider the definition of a port for asynchronous messaging with buffering of up to N=3 messages:

   const NM = 4
   range M = 0..NM       // messages with values up to 4
   set S = {[M],[M][M]} // queue of up to three messages
   PORT                 // empty state, only send permitted
       = (send[x:M]   -> PORT[x]),
   PORT[h:M]            // one message queued to port
       = ( send[x:M]  -> PORT[x][h]
         | receive[h] -> PORT),
   PORT[t:S][h:M]       //two or more messages queued to port
       = ( send[x:M]  -> PORT[x][t][h]
         | receive[h] -> PORT[t]).
   

   Design a message passing system with a producer and a consumer. The producer may only send up to N messages before it is blocked by waiting for the consumer to receive a message. Verify using the LTSA tool that the system prevents queue overflow (for N=3).
   Show your solution to your tutor when done.

   Hint: you can use an `empty' message to get the desired protocol: the consumer sends `empty' messages asynchronously to the producer; it can send at most N of these before going into a state where it must receive the `main' message from the producer before sending another empty messages. A port for (empty) acknowledge messages may be simply modelled as:

   const N = 3
   PORT_E = PORT_E[0],
   PORT_E[i:0..N]
       =  ( when (i < N) send -> PORT_E[i+1]
          | when (i > 0) receive -> PORT_E[i-1] ).
   

Laboratory Exercises

1. * Implement a synchronous message passing solution of the Dining Savages problem of TuteLab-3. (see the answers for the monitor solution). Model the Savage (Cook) as a thread which repeatedly tries to send a getServing (fillpot message to the Pot thread, which selectively receives them when the conditions are suitable.
   Hint: refer to the Ornamental garden example from the Message passing lecture.
   Show your solution to your tutor when done.

2. (Ex 10.1 Magee & Kramer) Consider the implementation of the Channel class, which is derived from the Selectable class. Ignoring the feature that allows objects of the Channel class to be used in a select, re-write Channel.java as a monitor that just does send and receive operations (keep a copy of the original though). Test your implementation in the synchronous message passing applet.

   Hint: `inline' the block(), signal() and clearReady() calls in Channel.java, using the code path for inchoice == null. Compile and run applet from the book_applets sub-directory:

   javac concurrency/message/Channel.java
   appletviewer SynchMsgDemo.html &

3. (Ex 10.2 Magee & Kramer) Modify your implementation of the previous exercise so that the receive operation can time out. The receive becomes:
   synchronized Object receive(int timeout /*ms*/);
   If the timeout period expires before a message is sent to the channel, the receive operations returns the value null
   Hint: System.nanoTime() returns the system time in nanoseconds (10^-9 seconds).

Challenge Problem!

entry put, get;
int count = 0;
while (true)
  select
    when (count < size) and v = accept(put) =>
      ++count; // insert item v into buffer
      reply(put, ' ');
  or 
    when (count > 0) and accept(get) ->
      --count; // get item v from buffer
      reply(get, v);
  end

Even if you implement this properly, you will probably find that this hangs! Investigate this: is there a bug in the implementation of Entry? If so, can it be rectified so that you can either add new item or remove old items from the buffer when half-full? (this is still not satisfactorily resolved).