3.3.1 EXCHANGE

EXCHANGE($LinkNo$, $nWords$, $SendData$, $RecvData$)

Exchange of data between processes $p$ and $q$ via link $LinkNo$.

Variant a)

• Works only in case of non-blocking communication, i.e., the sending process does not require an acknowledgment that the message was received.
• Blocking communication ends with a deadlock.

Figure 3.12: EXCHANGE non-blocking

Variant b)

In case of a blocking communication, a deadlock free EXCHANGE between $p$ and $q$ needs a unique function determining which one of the two processes may send/receive first. The function BTEST($k,link$)$=$XOR( $k,2^{link 1}$) tests whether the $link-1$ $^{\text{st}}$ bit is set or not. The definition that this process, whose appropriate bit is set first sends and then receives (vice versa on the other process) allows a deadlock-free EXCHANGE procedure.

Figure 3.13: EXCHANGE blocking