Dealing With Deadlock
The good news is that we have tools and techniques to detect and prevent many kinds of deadlock. In particular, consider ways to deal with two popular forms of blocking: Waiting to acquire a mutex, and waiting to receive a message.
First, to prevent locking cycles within the code you control, use lock hierarchies and other ordering techniques to ensure that your program always acquires all mutexes in the same order [1]. Note: Not all locks need to participate directly in a lock hierarchy; for example, some groups of related locks already have a total ordering among themselves, such as a chain of locks always traversed in the same order (hand-over-hand locking along a singly linked list, for instance).
Second, to prevent many kinds of message cycles, disciplines have been proposed to express contracts on communication channels, which helps to impose a known ordering on messages. One example is WS-CDL [3]. The general idea is to define rules for the orders in which messages must be sent and received, which can be enforced statically or dynamically to ensure that components communicating via messages won't tie themselves into a knot. A message ordering contract is typically expressed as some form of state machine. For example, here's how we might express a simple interface in pseudocode for a buyer requesting a purchase order:
contract PORequest {
// messages from requester to
// provider (arbitrarily
// choose "in" to be from the
// provider's point of view)
in void Request( Info );
// messages from provider
// to requester
out void Ack();
out void Response( Details );
// now declare states and transitions
state Start {
Request -> RequestSent;
}
state RequestSent {
Ack -> RequestReceived;
}
state RequestReceived {
Response -> End;
}
}
The only valid message order is Request->Ack->Response. If a provider could mistakenly send a Response without first sending an Ack, a requester could hang indefinitely waiting for the missing Ack message. Expressing the message order contract gives us a way to guarantee that a provider fulfills the contract, or at least to detect violations.
