UNDER CONSTRUCTION!

Message Passing

Semaphores and monitors can be used in a shared memory situation but not in a distributed system. For distributed systems, we must use message passing. Primitive operations are: `send(to, message)' and `receive(from, message)'.

Design issues.

blocking versus nonblocking, also called synchronous versus asynchronous
- blocking
  - if no messages available receiver can block until one arrives
  - sender can block if no receive outstanding for message being sent
  - if both send and receive are blocking, then when the message is actually passed from sender to receiver, we have what is called a simple rendezvous
- nonblocking
  - send returns control immediately after message queued
  - receive returns failure indicator if no message available
buffered versus nonbuffered
- unbuffered send blocks until receiver executes a receive
- buffered send usually implies non-blocking send
- usually an upper limit on buffer size above which the sender will block
- not much difference between blocking buffered and blocking un-buffered

So we really have three varieties

for send
1. rendezvous, blocking, wait for receiver or receiver is waiting
2. buffered non-blocking, message will be buffered by OS but receiver hasn't necessarily gotten it yet
3. non-buffered, non-blocking, return error if no receiver ready or waiting, return ok if message was sent and received
for receive
1. rendezvous, blocking, wait for message or sender
2. buffered non-blocking, return error if no message was waiting
3. non-buffered, non-blocking, return error if no sender ready or waiting, return ok if message was sent and received

Message Passing in SR

Use send name(parameters) for non-blocking (asynchronous) sending of a message and call name(parameters) for blocking (synchronous) sending of a message. Use receive name(parameters) for blocking receiving of a message. SR only has blocking receive; when used with blocking send, we have a simple rendezvous. Here is a short example of intra-resource message passing.
SR Program: Simple Message Passing.

Here is an example of inter-resource message passing. Be careful about deadlock: don't have two processes blocked on a receive, each waiting for the other to send a message.
SR Program: More Message Passing.

This example shows a pipeline of filter processes (filtering out non-prime numbers). It illustrated the optype declaration of a user-defined operation type. It also shows that an array of operations can be declared with each entry in the array implemented in a different process: the i-th filter process implements sieve[i] with a receive. The i-th filter process communicates with the next one in the pipeline with send sieve[i+1].
SR Program: Parallel Sieve of Eratosthenes.

Message passing can be used to synchronize two processes in addition to communicating data. We can use message passing (requiring no shared memory) to implement the producers and consumers, with blocking receive and nonblocking send. Sent messages are buffered automatically by the OS until received. This example uses message passing to synchronize the bounded buffer producer and consumer processes. The driver sends a number of empty buffer slots to the producer to represent the bounded buffer. The output of the first sample run shows the producer process filling up the buffer and then waiting for a free slot to become available before inserting any more items into the buffer. The second sample run shows the consumer emptying the buffer and having to wait for new items from the producer. Thus message passing synchronizes the producer and the consumer just as the semaphores elements and spaces do in the semaphore version. Note that the producer and consumer processes can be running on different machines with the messages sent across the network connecting the machines. This program shows how to start processes on different machines.
SR Program: Bounded Buffer Producer and Consumer Using Message Passing.

Here is an implementation of the (unbounded buffer) multiple producers and consumers using message passing. Processes that produce work and processes that consume or do the work can share a bag of tasks. Producers put work into the bag with a message and consumers remove work from the bag by receiving a message. A feature of SR is used to implement the bag: a capability to an operation shared by a collection of processes, some of which send to the capability and some of which use the capability to receive.
SR Program: Unbounded Buffer Producers and Consumers.

Distributed Mutual Exclusion

Programs that share memory can use the following to handle mutual exclusion and condition synchronization:

bakery algorithm
test and set
semaphores
monitors
rendezvous
send/receive message passing

Suppose though the programs don't share memory but have private memories and CPU's on a LAN and suppose they still want to do condition synchronization to coordinate access to some shared resource If all we have is message passing, can we implement some sort of ``distributed mutual exclusion'' algorithm? Suppose we also want to avoid a central server to avoid a bottleneck.

To recap, we want to solve the N program mutual exclusion problem such that it

works in a distributed environment
does not involve a central server

Assumptions:

error-free communication channels between all nodes i.e. no lost or garbled messages
but messages can arrive in a different order than they were sent
nodes do not fail or halt, either inside or outside their critical sections

In other words, nodes eventually respond to all request messages.

Idea:

  do true ->
    non critical-section code
    choose a number
    send it to all other processes
    wait for message from all other processes
    enter critical section
    post-protocol
  od

Each of the N nodes is really three processes executing concurrently (the three processes are executing on the CPU/memory of the node).

one does the above do loop
another handles requests from other processes
another one waits for replies from all other processes

A node will send a ``reply'' or acknowledgement message to a node that has sent a request message i.e. when ``asked''.

immediately if the other node has a lower number (higher priority) or if it is not trying to enter its critical section
deferred (until it gets into then out of its critical section) if the other node has a higher sequence number (lower priority)

ties are broken by node ID

                        non CS
                        pre-protocol:
                          choose number as highest seen so far + 1
         <=============   send it to all other nodes       ===========>
                          represents request to enter CS


         =============> wait for replies                  <============
                        while waiting, reply to other nodes
                          if their number is lower


                        enter CS
                        post-protocol:
                          reply to others (deferreds)
                          if their number was higher before

a node chooses its number by adding 1 to the highest number it has seen so far in incoming messages from other nodes

Why it works.

Mutual exclusion:: a node does not enter its CS until it receives replies from all other nodes to its ``request'' message (sending of chosen number)
No deadlock:: ties are broken using process ID
No starvation in absence contention:: since none of the other nodes want to enter their CS, they reply immediately
No starvation in presence contention:: after a node exits its CS, it will choose a number when it wants to enter again that is higher than other contending processes

SR Program: Distributed Mutual Exclusion.

SJH

shartley@mcs.drexel.edu