Example: Two Modules, One Lock Each

One fine day, you decide to write a new web browser that lets users write plug-ins to customize the behavior or rendering of individual page elements. Consider the following possible code, where we simply protect all the data structures representing elements on a given page using a single mutex mutPage:

// Example 1: Thread 1 of a potential deadly embrace
//
class CoreBrowser {
  ... other methods ...
  private void RenderElements() {
    mutPage.lock();  // acquire exclusion on the page elements
    try {
      for( each PageElement e on the page ) {
        DoRender( e );	      // do our own default processing
        plugin.OnRender( e ); // let the plug-in have a crack at it
      }
    } finally {
      mutPage.unlock();	// and then release it
    }
  }
}

Do you see the potential for deadlock? The trouble is that if inside the call to plugin.OnRender the plug-in might acquire some internal lock of its own, which could be one arm of a potential deadly embrace. For example, consider this plug-in implementation that does some basic instrumentation of how many times certain actions have been performed and protects its internal data with a single mutex mutMyData:

class MyPlugin {
   ... other methods ...
  public void OnRender( PageElement e ) {
    mutMyData.lock();  // acquire exclusion on some internal shared data
    try {
      renderCount[e]++;	// update #times e has been rendered
    } finally {
      mutMyData.unlock(); // and then release it
    }
  }
}

Thread 1 can therefore acquire mutPage and mutMyData in that order. Thread 1 is potential deadlock-bait, but the trouble will only manifest if some other Thread 2 that could run concurrently with the aforementioned code performs something like the following:

// Example 2: Thread 2 of a potential deadly embrace
//
class MyPlugin {
   ... other methods ...
  public void RefreshDisplay( PageElement e ) {
    mutMyData.lock();  // acquire exclusion on some internal shared data
    try {		// display stuff in a debug window
      for( each element e we've counted ) {
        listRenderedCount.Add( e.Name(), renderCount[e] );
      }
      textHiddenCount = browser.CountHiddenElements();
    } finally {
      mutMyData.unlock();  // and then release it
    }
  }
}

Notice how the plugin calls code unknown to it, namely browser.CountHiddenElements? You can probably see the trouble coming on like a steamroller:

class CoreBrowser {
  ... other methods ...
  public int CountHiddenElements() {
    mutPage.lock();  // acquire exclusion on the page elements
    try {
      int count = 0;
      for( each PageElement e on the page ) {
        if( e.Hidden() ) count++;
      }
      return count;
    } finally {
      mutPage.unlock();	// and then release it
    }
  }
}

Threads 1 and 2 can therefore acquire mutPage and mutMyData in the opposite order, so this is a deadlock waiting to happen if Threads 1 and 2 can ever run concurrently. For added fun, note that each mutex is purely an internal implementation detail of its module that is never exposed in the interface; neither module knows anything about the internal lock being used within the other. (Nor, in a better programming world than the one we now inhabit, should it have to.)