Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Design

The Many Faces of Deadlock


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.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.