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

d12sutt_p4ma 10/11/07 9:47 AM Page 58 Effective Concurrency 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.) Because of the interference of the plug-in code, which does not even have any locks of its own, this code has a latent deadlock if any other concurrently running thread (including perhaps another instance of Thread 1 itself) can take any two adjacent elements’ locks in any order. The deadlock-proneness is inherent in the design, which fails to guarantee a rigorous ordering of locks. In this respect, the original Example 1 was better, even though its locking was coarse-grained and less friendly to concurrent rendering of different page elements. Consequences: What Is “Unknown Code”? It’s one thing to say “avoid calling unknown code while holding a lock” or while inside a similar kind of critical section. It’s another to do it, because there are so many ways to get into “someone else’s code.” Let’s consider a few. While inside a critical section, including while holding a lock: • Avoid calling library functions. A library function is the classic case of “someone else’s code.” Unless the library function is documented to not take any locks, deadlock problems can arise. • Avoid calling plug-ins. Clearly, a plug-in is “someone else’s code.” • Avoid calling other callbacks, function pointers, functors, delegates, and so on. C function pointers, C++ functors, C# delegates, and the like can also fairly obviously lead to “someone else’s code.” Sometimes, you know that a function pointer, functor, or delegate will always lead to your own code, and calling it is safe; but if you don’t know that for certain, avoid calling it from inside a critical section. • Avoid calling virtual methods. This may be less obvious and quite surprising, even Draconian; after all, virtual functions are common and pervasive. But every virtual function is an extensibility point that can lead to executing code that doesn’t even exist today. Unless you control all derived classes (for example, the virtual function is internal to your module and not exposed for others to derive from), or you can somehow enforce or document that overrides must not take locks, deadlock problems can arise if it is called while inside a critical section. • Avoid calling generic methods, or methods on a generic type. When writing a C++ template or a Java or .NET generic, we have yet another way to parameterize and intentionally let “someone else’s code” be plugged into our own. Remember that anything you call on a generic type or method can be provided by anyone, and unless you know and control all the types with which your template or generic can be instantiated, avoid calling something generic from within a critical section. Some of these restrictions may be obvious to you; others may be surprising at first. Example: Two Modules, But Only One Has Locks Note that this kind of thing can happen even if both locks are in the same module, but control flow passes through another module so that you don’t know what locks are taken. Consider the following modification, where the browser protects each page element using a separate mutex, which can be desirable to allow different parts of the page to be rendered concurrently: // Example 3: Thread 1 of an alternative potential deadly embrace // class CoreBrowser { other methods private void RenderElements() { for( each PageElement e on the page ) { e.mut.lock(); // acquire exclusion on this page element try { DoRender( e ); // do our own default processing plugin.OnRender( e );// let the plug-in have a // crack at it } finally { e.mut.unlock(); // and then release it } } } } And consider a plug-in that does no locking of its own at all: class MyPlugin { other methods public void OnRender( PageElement e ) { GuiCoord cPrev = browser.GetElemPosition( e.Previous() ); GuiCoord cNext = browser.GetElemPosition( e.Next() ); Use( e, cPrev, cNext ); // do something with the coords } } But which calls back into: class CoreBrowser { other methods public GuiCoord GetElemPosition( PageElement e2 ) { e2.mut.lock(); // acquire exclusion on this page element try { return FigureOutPositionFor( e2 ); } finally { e2.mut.unlock(); // and then release it } } } Avoidance: Noncritical Calls So you want to remove a call to unknown code from a critical section. But how? What can you do? Four options are: (a) move the call out of the critical section if you didn't need the exclusion anyway; (b) make copies of data inside the critical section and later pass the copies; (c) reduce the granularity or power of the critical section being held at the point of the call; or (d) instruct the callee sternly and hope for the best. We can apply the first approach directly to Example 2. There is no reason the plugin needs to call browser.CountHiddenElements() while holding its internal lock. That call should simply be moved to before or after the critical section. The order of mutex acquisition is: for each element e acquire e.mut acquire e.Previous().mut release e.Previous().mut acquire e.Next().mut release e.Next().mut release e.mut Perhaps the most obvious issue is that any pair of locks on adjacent elements can be taken in both orders by Thread 1; so this cannot possibly be part of a correct lock hierarchy discipline. 58 Dr. Dobb’s Journal l www.ddj.com l December 2007 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.