Dr. Dobb's Journal - December 2007 - (Page 57)

d12sutt_p4ma 10/11/07 9:47 AM Page 57 by Herb Sutter Effective Concurrency Avoid Calling Unknown Code While Inside a Critical Section Don’t walk blindly into a deadly embrace… OUR WORLD IS built on modular, composable software. We routinely expect that we don’t need to know about the internal implementation details of a library or plug-in to be able to use it correctly. The problem is that locks, and most other kinds of synchronization we use today, are not modular or composable. That is, given two separately authored modules, each of which is provably correct but uses a lock or similar synchronization internally, we generally can’t combine them and know that the result is still correct and will not deadlock. There are only two ways to combine such a pair of lock-using modules safely: • Option 1. Each module must know about the complete internal implementation of any function it calls in the other module (generally impossible for code you don’t control). • Option 2. Each module must be careful not to call into the other module while the calling code is inside a critical section (while holding a lock, for example). Let’s examine why Option 2 is generally the only viable choice, and what consequences it has for how we write concurrent code. For convenience, I’m going to cast the problem in terms of locks, but the general case arises whenever: • The caller is inside one critical section. • The callee directly or indirectly tries to enter another critical section, or performs another blocking call. • Some other thread could try to enter the two critical sections in the opposite order. you can use a lock hierarchy and guarantee that the code you control follows the discipline, but you can’t guarantee that other people’s code will know anything about your lock levels, much less follow them correctly. 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 } } } Quick Recap: Deadlock A deadlock (or deadly embrace) can happen anytime two different threads can try to acquire the same two locks (or more generally, acquire exclusive use of the resources protected by the same two synchronization objects) in opposite orders. Therefore, anytime you write code where a thread holds one lock L1 and tries to acquire another lock L2, that code is liable to be one arm of a potential deadly embrace—unless you can eliminate the possibility that some other thread might try to acquire the locks in the other order. We can use techniques such as lock hierarchies to guarantee that locks are taken in order. Unfortunately, those techniques do not compose either. For example, 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: December 2007 l www.ddj.com l Dr. Dobb’s Journal 57 http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - December 2007

Dr. Dobb's Journal - December 2007 Contents Hmmmm Alia Vox Developer Diaries Developer’s Notebook Computer Books: Reading Between the Lines Conversations Query Anything with SQLite XQuery Web Maps with the Google Map API OpenALM and Its Manifesto Transactional Programming Effective Concurrency The Agile Edge Swaine’s Flames

Dr. Dobb's Journal - December 2007

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.