Blocking Message Passing Operations

• A simple solution to the dilemma 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
   • In the first case, 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. The sending process sends a request to communicate to the receiving process. When the receiving process encounters the target receive, it responds to the request. The sending process upon receiving this response initiates a transfer operation (see Fig. 7.1). Since there are no buffers used at either sending or receiving ends, this is also referred to as a non-buffered blocking operation.

     Figure 7.1: Handshake for a blocking non-buffered send/receive 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. 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, the send at $P_0$ waits for the matching receive at $P_1$ whereas the send at process $P_1$ waits for the corresponding receive at $P_0$, resulting in an infinite wait. Deadlocks are very easy in blocking protocols and care must be taken to break cyclic waits of the nature outlined.
2. Blocking Buffered Send/Receive
   • A simple solution to the idling and deadlocking problem outlined above is to rely on buffers at the sending and receiving ends.

     Figure 7.2: Blocking buffered transfer protocols: (a) in the presence of communication hardware with buffers at send and receive ends; and (b) in the absence of communication hardware, sender interrupts receiver and deposits data in buffer at receiver end.

     
   • Figure 7.2a
     • 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.
     • The actual communication can be accomplished in many ways depending on the available hardware resources. If the hardware supports asynchronous communication (independent of the CPU), then a network transfer can be initiated after the message has been copied into the buffer.
     • 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.
   • Figure 7.2b
     • In the protocol illustrated Fig. 7.2a, buffers are used at both sender and receiver and communication is handled by dedicated hardware. Sometimes machines do not have such communication hardware.
     • In this case, some of the overhead can be saved by buffering only on one side. For example, on encountering a send operation, the sender interrupts the receiver, both processes participate in a communication operation and the message is deposited in a buffer at the receiver end.
     • When the receiver eventually encounters a receive operation, the message is copied from the buffer into the target location.
   • It is easy to see that buffered protocols alleviate idling overheads at the cost of adding buffer management overheads.
   • In general, if the parallel program is highly synchronous (i.e., sends and receives are posted around the same time), non-buffered sends may perform better than buffered sends. However, in general applications, this is not the case and buffered sends are desirable unless buffer capacity becomes an issue.
   • Impact of finite buffers in message passing; consider the following code fragment:

     1     P0                                   P1 
     2 
     3  for (i = 0; i < 1000; i++) {         for (i = 0; i < 1000; i++) { 
     4   produce_data(&a);                    receive(&a, 1, 0); 
     5   send(&a, 1, 1);                      consume_data(&a); 
     6  }                                    }
     

     • In this code fragment, process $P_0$ produces 1000 data items and process $P_1$ consumes them. However, if process $P_1$ was slow getting to this loop, process $P_0$ might have sent all of its data.
     • If there is enough buffer space, then both processes can proceed; however, if the buffer is not sufficient (i.e., buffer overflow), the sender would have to be blocked until some of the corresponding receive operations had been posted, thus freeing up buffer space.
     • This can often lead to unforeseen overheads and performance degradation. In general, it is a good idea to write programs that have bounded buffer requirements.
   • Deadlocks in Buffered Send and Receive Operations: While buffering alleviates 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.