MSDN Magazine - October 2007 - (Page 137)

Deadlock Monitor STEPHEN TOUB Q A I’m using locks in my application to synchronize work on a bunch of threads. Unfortunately, I’m doing something incorrectly and my threads seem to just stop sometimes. I think I’m running into deadlocks, but I’m not sure how to find them. Is there any way I can do so programmatically? I’d like an exception to be thrown when a deadlock is encountered. First, it’s important to understand what a deadlock among threads is and the conditions that lead to one. Threads deadlock when waiting on each other to release some resources, but by performing that blocking wait, they’re not releasing the resources the other threads need in order to unblock. The threads can’t make any progress until the resources are released, but because they’re not making progress, the resources will never be released, the threads are locked up, and thus “deadlock.” Many OS course textbooks will cite the four conditions necessary for a deadlock to occur: • A limited number of a particular resource. In the case of a monitor in C# (what you use when you employ the lock keyword), this limited number is one, since a monitor is a mutualexclusion lock (meaning only one thread can own a monitor at a time). • The ability to hold one resource and request another. In C#, this is akin to locking on one object and then locking on another before releasing the first lock, for example: lock(a) { lock(b) { } } • No preemption capability. In C#, this means that one thread can’t force another thread to release a lock. • A circular wait condition. This means that there is a cycle of threads, each of which is waiting for the next to release a resource before it can continue. If any one of these conditions is not met, deadlock is not possible. The first condition is inherent to what a monitor is, so if you’re using monitors, this one is set in stone. The second condition could be avoided by ensuring that you only ever lock one object at a time, but that’s frequently not a feasible requirement in a large software project. The third condition could possibly be avoided in the Microsoft® .NET Framework by aborting or interrupting the thread holding the resource your thread requires, but a) that would require knowing which thread owned the resource, and b) that’s an inherently dangerous operation (for the many reasons why, see msdn.microsoft.com/msdnmag/issues/05/10/Reliability). Thus, the way to avoid deadlocks is to avoid (or thwart) condition four. In his article in the April 2006 issue (available at msdn.microsoft.com/ msdnmag/issues/06/04/Deadlocks), Joe Duffy discusses several techniques for avoiding and detecting deadlocks, including one Rather than prevent known as lock leveling. In deadlocks wholesale, lock leveling, locks are assigned numerical values, many systems attempt to and threads must only aceliminate them once found. quire locks that have higher numbers than locks they have already acquired. This prevents the possibility of a cycle. It’s also frequently difficult to do well in a typical software application today, and a failure to follow lock leveling on every lock acquisition invites deadlock. Rather than prevent deadlocks wholesale, many systems attempt to detect them and then eliminate them once found. For example, SQL Server® can detect when deadlocks occur and abort one of the tasks involved in the cycle, thereby removing the deadlock. In his article, Joe builds a common language runtime (CLR) host that is capable of this form of deadlock detection in .NET applications that use monitors, a very cool feat. Unfortunately, using a custom CLR host isn’t always practical for many .NET apps, including those that already have a custom host, like ASP.NET applications. As such, it would be beneficial to be able to utilize similar deadlock detection capabilities, without the need for a custom CLR host, such that these types of deadlocks could be detected at run time. This would be beneficial during development and testing phases, to identify coding errors where locks are being used incorrectly. It could also be used in production to detect and eliminate deadlocks as they occur (preventing a thread from causing one by blocking it from attempting the critical wait that would complete a cycle), however typical deadlock detection algorithms are costly and may not be appropriate in production systems for performance reasons. (I’ll have a few comments on performance at the end of this column.) To address this need, I’ve built a sample wrapper for the .NET System.Threading.Monitor class that includes deadlock detection capabilities. As with Monitor, my DdMonitor class provides october2007 137 http://msdn.microsoft.com/msdnmag/issues/05/10/Reliability http://msdn.microsoft.com/msdnmag/issues/06/04/Deadlocks http://msdn.microsoft.com/msdnmag/issues/06/04/Deadlocks

Table of Contents Feed for the Digital Edition of MSDN Magazine - October 2007

Cover Contents Toolbox CLR Inside Out Basic Instincts Data Points Cutting Edge Pooled Threads WPF Threads Parallel Linq Parallel Performance Mobile Apps Test Run Foundations Windows with C++ Netting C++ .NET Matters { End Bracket } Net Nuptials

MSDN Magazine - October 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.