10.3 Rendezvous

10.3 Rendezvous

Rendezvous, sometimes called request-reply, is a message-passing protocol used to support client – server interaction. Client processes send request messages to a server process requesting the server to perform some service. These request messages are queued to an entry in FIFO order. The server accepts requests from the entry and on completion of the requested service sends a reply message to the client that made the request. The client blocks waiting for the reply message. Rendezvous involves many-to-one communication in that many clients may request service from a single server. The reply to a request is a one-to-one communication from the server process to the client that requested the service. The protocol is depicted in Figure 10.10.

Figure 10.10: Rendezvous message-passing protocol.

The abstraction that supports rendezvous is termed an entry. The operations on entries are defined as follows:

res = call(e, req) – send the value req as a request message which is queued to the entry e. The calling process is blocked until a reply message is received into the local variable res.

req = accept(e) – receive the value of the request message from the entry e into the local variable req. If there are no request messages queued to the entry, then the server process is blocked.

reply(e,res)–send the value res as a reply message to entry e.

The term “rendezvous” for this form of interaction was coined by the designers of the Ada programming language (Department of Defense, 1983) in which it is the main process interaction mechanism. Rendezvous captures the essence of the interaction since client and server meet and synchronize when the server performs a service for the client.

As with channels and ports, a server process may selectively wait for messages from a set of entries using the select construct described in section 10.1.1.

10.3.1 Rendezvous in Java

We implement the rendezvous entry abstraction using the port and channel abstractions defined in the previous sections. Remembering that request communication is many-to-one, we use a port to implement it. Since reply communication is one-to-one, we can use a channel. Each client that communicates with a server via an entry requires its own channel to receive replies. The entry implementation is depicted in Program 10.7.

Program 10.7: Entry class.

 class Entry<R,P> extends Port<R> {   private CallMsg<R,P> cm;   private Port<CallMsg<R,P>> cp = new Port<CallMsg<R,P>>();   public P call(R req) throws InterruptedException {     Channel<P> clientChan = new Channel<P>();     cp.send(new CallMsg<R,P>(req,clientChan));     return clientChan.receive();   }   public R accept() throws InterruptedException {     cm = cp.receive();     return cm.request;   }   public void reply(P res) throws InterruptedException {     cm.replychan.send(res);   }   private class CallMsg<R,P> {     R  request;     Channel<P> replychan;     CallMsg(R m, Channel<P> c)       {request=m; replychan=c;}   } }

The Entry class extends Port, which in turn extends Selectable. Consequently, Entry objects can be added to a Select object in the same way as Channels and Ports. The call method creates a channel object on which to receive the reply message. It then constructs a message, using the CallMsg class, consisting of a reference to this channel and a reference to the req object. After the Client thread has queued this message using send, it is suspended by a receive on the channel. The server calls accept to get a message from the entry. The accept method keeps a copy of the channel reference on which to reply in the local variable cm. The reply method sends the reply message to this channel. Note that although the reply method performs a synchronous send operation, this does not suspend the server since the client must always be blocked waiting on the reply channel. Call, accept and reply are not synchronized methods since Client and Server threads do not share any variables within Entry. The cm variable is only accessed by the Server thread. Client and Server threads interact via Port and Channel objects, which are thread-safe.

Runtime systems for Ada have much more efficient implementations of rendezvous than the implementation described here. They exploit the fact that, since the client is blocked during a rendezvous, when client and server are on the same computer messages can be copied directly between client memory and server memory without buffering.

The applet display of Figure 10.11 demonstrates the operation of rendezvous using the Entry class. The display depicts the situation where both clients have called the server and are waiting for a reply. The server is currently servicing the request from Client A. The color of the rotating segment of the server is set to the same color as the client it is servicing.

Figure 10.11: Rendezvous message-passing applet display.

The code for Client and Server threads is given in Program 10.8. The threads and entry for the demonstration program are created by the following Java code:

 Entry<String,String> entry = new Entry<String,String>(); clA.start(new Client(entry,clientAdisp,"A")); clB.start(new Client(entry,clientBdisp,"B")); sv.start(new Server(entry,serverdisp));

where clA, clB and sv are instances of ThreadPanel, and clientAdisp, clientBdisp and serverdisp are instances of SlotCanvas.

Program 10.8: Client and Server threads.

 class Client implements Runnable {   private Entry<String,String> entry;   private SlotCanvas display;   private String id;   Client(Entry<String,String> e, SlotCanvas d, String s)     {entry=e; display =d; id=s;}   public void run() {     try {       while(true) {         ThreadPanel.rotate(90);         display.enter(id);         String result = entry.call(id);         display.leave(id); display.enter(result);         ThreadPanel.rotate(90);         display.leave(result);         ThreadPanel.rotate(180);       }     } catch (InterruptedException e){}   } } class Server implements Runnable {   private Entry<String,String> entry;   private SlotCanvas display;   Server(Entry<String,String> e, SlotCanvas d)     {entry=e; display =d;}   public void run() {     try {       while(true) {         while(!ThreadPanel.rotate());         String request = entry.accept();         display.enter(request);         if (request.equals("A"))            ThreadPanel.setSegmentColor(Color.magenta);         else            ThreadPanel.setSegmentColor(Color.yellow);         while(ThreadPanel.rotate());         display.leave(request);         entry.reply("R");       }     } catch (InterruptedException e){}   } }

10.3.2 Modeling Rendezvous

To model rendezvous communication, we can reuse the models for ports and channels in the same way as we reused the implementation classes Port and Channel in implementing the Entry class. In modeling the demonstration program, we ignore the message data values and concentrate on interaction. Consequently, the message that is sent by a client to the server consists of only the reply channel. This message is defined by:

 set M = {replyA,replyB}

The PORT process queues messages of this type. An entry is modeled by:

 ||ENTRY = PORT/{call/send, accept/receive}.

This reuses the PORT definition from the previous section and relabels send to be call and receive to be accept. The Server thread is modeled by:

 SERVER = (entry.accept[ch:M]->[ch]->SERVER).

The server accepts a message from the entry consisting of the name of the reply channel and then replies using this channel name. Remember that we model synchronous communication by a single shared action which is the name of the channel. The client is modeled by:

 CLIENT(CH=′reply) = (entry.call[CH]                      ->[CH]->CLIENT).

where CH is a parameter initialized to the action label reply. In FSP, action labels used as parameter values or in expressions must be prefixed with a single quote to distinguish them from variables. The CLIENT process sends this parameter, which names the reply channel, to the entry and then waits for the reply. The composite model describing the demonstration program is shown in Figure 10.12.

Figure 10.12: Rendezvous applet model.

We do not need to prefix the CLIENT processes since their parameter values lead to each having a distinct alphabet. For example, the alphabet of CLIENT(′replyA) is {entry.call.replyA, replyA}. The following trace is the scenario in which both clients request service and the server has accepted the request for client A and replied:

 entry.call.replyA entry.call.replyB entry.accept.replyA replyA

A safety analysis of EntryDemo reveals no deadlocks or errors. Rendezvous communication means that each client can only have one outstanding request queued to the server entry at any one time. Consequently, in our demonstration program with two clients, the maximum entry queue length is two. In the model, we have used a port capable of queuing three messages. We can redefine this to be a queue with maximum capacity two by redefining the set S to be {[M]}. A safety analysis of this system reveals that the entry queue does not overflow.

10.3.3 Rendezvous and Monitor Method Invocation

From the viewpoint of a client, apart from syntactic differences, a call on an entry is the same as calling a monitor access method. The difference between rendezvous and monitor method invocation is to do with how the call from the client is handled. In the case of a rendezvous, the call is handled by a server thread that accepts the call from an entry. In the case of method invocation, the call is serviced by execution of the body of the method. The method body is executed by the client thread when it acquires the monitor lock. We saw how a bounded buffer can be implemented by a monitor in Chapter 5. The same buffer semantics from the viewpoint of the client can be implemented using rendezvous communication as sketched in outline below:

 Buffer::     entry put, get;     int count = 0;          //number of items in buffer     while(true)      select      when (count<size) and o=accept(put)=>       ++count;    //insert item o into buffer     reply(put,signal)     or     when (count>0) and accept(get)=>        --count;        //get item o from buffer     reply(put,o);     end 

Mutual exclusion is ensured by the fact that the buffer state is encapsulated in the server thread. Since the server thread processes only one request at a time, mutual exclusion is guaranteed. Which implementation is more efficient, monitor or rendezvous? In considering this question, we should compare rendezvous as implemented in Ada rather than the example implementation presented in this chapter. However, even with an efficient implementation, in a local context, where the client is located on the same computer as the server, the monitor implementation is more efficient since the rendezvous implementation always involves two context switches. For each rendezvous, there is a switch from client thread to server thread and then back from server to client. A method call to a monitor may require no context switch: for example, a get from a non-empty buffer when the producer does not currently have the monitor lock. However, the situation is not so clear-cut when the client is located on a different computer to the server. In this situation, the rendezvous may be better for the following reasons. If the client is remote from the monitor, then a protocol such as Java’s Remote Method Invocation (RMI) must be used to transfer the client’s invocation to the remote computer on which the monitor is located. At this location, RMI creates a new thread to perform the invocation on the monitor on behalf of the client. This thread creation is not required by a remote rendezvous.

We have used the issue of efficiency to focus on the differences in implementation between rendezvous and monitor method invocation. However, we can model programs at a sufficiently abstract level that the model can be implemented by either mechanism. For example, the model for the bounded buffer presented in Chapter 5 captures the behavior of both the monitor implementation and the rendezvous implementation we have outlined in this section. This illustrates a more general point. The modeling techniques we are using to describe and analyze concurrent programs are not restricted to programs implemented in Java. They can be used to model message-passing programs with equal facility.