Blocking Message Passing Operations

• As a result, if the send operation programs the communication hardware and returns before the communication operation has been accomplished, process $P_1$ might receive the value 0 in a instead of 100!
• A simple solution to the problem presented in the code fragment above is for the send operation to return only when it is semantically safe to do so.
• Note that this is not the same as saying that the send operation returns only after the receiver has received the data.
• It simply means that the sending operation blocks until it can guarantee that the semantics will not be violated on return irrespective of what happens in the program subsequently.
• There are two mechanisms by which this can be achieved.
  
  1. Blocking Non-Buffered Send/Receive
  2. Blocking Buffered Send/Receive

1

Blocking Non-Buffered Send/Receive

• The send operation does not return until the matching receive has been encountered at the receiving process.
• When this happens, the message is sent and the send operation returns upon completion of the communication operation.
• Typically, this process involves a handshake between the sending and receiving processes (see Figure 4.1).

  Figure 4.1: Handshake for a blocking non-buffered send/receive operation.

  

  
$\bullet$ The sending process sends a request to communicate to the receiving process.
$\bullet$ When the receiving process encounters the target receive, it responds to the request.
$\bullet$ The sending process upon receiving this response initiates a transfer operation.
$\bullet$ Since there are no buffers used at either sending or receiving ends, this is also referred to as a non-buffered blocking operation.

• Idling Overheads in Blocking Non-Buffered Operations: It is clear from the figure that a blocking non-buffered protocol is suitable when the send and receive are posted at roughly the same time (see Figure(b)).
• However, in an asynchronous environment, this may be impossible to predict.
• This idling overhead is one of the major drawbacks of this protocol.

• Deadlocks in Blocking Non-Buffered Operations: Consider the following simple exchange of messages that can lead to a deadlock:

   1   P0                           P1 
   2
   3  send(&a, 1, 1);         send(&a, 1, 0); 
   4  receive(&b, 1, 1);     receive(&b, 1, 0);
  

• The code fragment makes the values of $a$ available to both processes $P_0$ and $P_1$.
• However, if the send and receive operations are implemented using a blocking non-buffered protocol,

    
  $\bullet$ the send at $P_0$ waits for the matching receive at $P_1$
  $\bullet$ whereas the send at process $P_1$ waits for the corresponding receive at $P_0$,
  $\bullet$ resulting in an infinite wait.
  

• Deadlocks are very easy in blocking protocols and care must be taken to break cyclic waits.

2

Blocking Buffered Send/Receive

• A simple solution to the idling and deadlocking problems outlined above is to rely on buffers at the sending and receiving ends.

  Figure 4.2: Blocking buffered transfer protocols: Left: in the presence of communication hardware with buffers at send and receive ends; and Right: in the absence of communication hardware, sender interrupts receiver and deposits data in buffer at receiver end.

  

• On a send operation, the sender simply copies the data into the designated buffer and returns after the copy operation has been completed.
• The sender process can now continue with the program knowing that any changes to the data will not impact program semantics.
• Note that at the receiving end, the data cannot be stored directly at the target location since this would violate program semantics.
• Instead, the data is copied into a buffer at the receiver as well.
• When the receiving process encounters a receive operation, it checks to see if the message is available in its receive buffer. If so, the data is copied into the target location.
• In general, if the parallel program is highly synchronous, non-buffered sends may perform better than buffered sends.
• However, generally, this is not the case and buffered sends are desirable unless buffer capacity becomes an issue.

• Deadlocks in Buffered Send and Receive Operations:
• While buffering relieves many of the deadlock situations, it is still possible to write code that deadlocks.
• This is due to the fact that as in the non-buffered case, receive calls are always blocking (to ensure semantic consistency).
• Thus, a simple code fragment such as the following deadlocks since both processes wait to receive data but nobody sends it.

   1     P0                                  P1 
   2
   3  receive(&a, 1, 1);                receive(&a, 1, 0); 
   4  send(&b, 1, 1);                   send(&b, 1, 0);
  

• Once again, such circular waits have to be broken.
• However, deadlocks are caused only by waits on receive operations in this case.