Deadlock is an often-encountered situation in parallel processing. It results when two or more processes are in contention for the same set of resources. In communications, a typical scenario involves two processes wishing to exchange messages: each is trying to give a message to the other, but neither of them is ready to accept a message. We will look at some strategies that can help insure against this happening.

Not surprisingly, the deadlock phenomenon is most common with blocking communication. It is relatively easy to get into a situation where multiple tasks are waiting for events that haven't been initiated yet—and never can be. The following diagram represents two SPMD tasks. We see that both are calling standard blocking sends at the same point of the program, but the receive that would match each task's send occurs later in the other task's program.

The receives for these two processes are positioned after the sends. If the sends do not complete and return, the receives can never be executed, and both sets of communications will stall indefinitely.