Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Lock Manager for .NET

, 11 Aug 2003
Deadlock resolver for muti-threading applications.
lockmanager.zip
Free
bin
LockManager.csproj.user
obj
Step1
App.ico
bin
obj
Step1.csproj.user
Step2
App.ico
bin
obj
Step2.csproj.user
Step3
App.ico
bin
obj
Step3.csproj.user
Step4
App.ico
bin
obj
Step4.csproj.user
Step5
App.ico
bin
obj
Step5.csproj.user
ThreeObjectsTest
App.ico
bin
obj
ThreeObjectsTest.csproj.user
/// <disclaimer>
/// This software is protected by your own conscience (c).
/// You can use it however you want and wherever you want.
/// You are allowed to change this code, copy this code, or delete this code.
/// You can buy this code; sell this code; present this code to your mom on her birthday.
/// You can replace author�s name with your own. You also can replace all the code with your own leaving
/// only author�s name.
/// The only thing you cannot do, is to violate this license agreement. You simply are not able to.
/// </disclaimer>
/// <author>
/// Sergei Zotin 
/// szotin@shaw.ca
/// Burnaby, BC, Canada
/// Feel free to contact me for bug reports, feature requests and contract offers.
/// </author>
/// <version>1.6</version>

using System;
using System.Collections;
using System.Threading;
using System.IO;

namespace ZEN.Threading
{
	/// <summary>
	/// LockManager is a thread synchronization object like Monitor, or Mutex.
	/// The difference is that LockManager saves internal info about locks to be analysed by it's internal
	/// DeadlockCollector thread. If DeadlockCollector finds a deadlock, it interrupts one of the threads
	/// and makes it to throw DeadlockException.
	/// LockManager is compatible with Monitor. Which means, when one thread calls LockManager.Lock()
	/// and another thread calls Monitor.Enter() at the same object, Monitor.Enter waits until the first
	/// thread releases the lock using LockManager.Unock(). The opposite is also true: when the first
	/// thread calls Monitor.Enter and the second LockManager.Lock(), the second thread is waiting untill
	/// the first thread calls Monitor.Exit. Use Monitor when no recursive locks are expected; use
	/// LockManager when there are recursive locks (deadlock is possible).
	/// Monitor is always much faster than LockManager. Although LockManager is faster than Mutex in most
	/// cases.
	/// </summary>
	/// <remarks>
	/// 	created by - Sergei Zotin
	/// 	created on - 7/28/2003 3:34:45 PM
	/// </remarks>
	public class LockManager
	{
		#region private constants
		
		/// <summary>Default sleep timeout for DeadlockCollector. <see cref="CollectorSleepTimeout"/></summary>
		private const int DEFAULT_SLEEP_TIME = 10000;
		
		/// <summary>The initial capacity for events array (both current and history)</summary>
		private const int EVENT_ARRAY_CAPACITY = 64;
		
		#endregion
		
		#region private data structures
		
		/// <summary>Event type for synchronization events.</summary>
		private enum EventType
		{
			Waiting,
			Locked,
			Unlocked,
			Interrupted
		}
		
		/// <summary>Synchronization event info to be saved for future analysis of DeadlockCollector.</summary>
		private struct Event
		{
			/// <summary>Event type: eather Waiting (wait for the lock), Locked, or Unlocked</summary>
			public EventType m_type;
			/// <summary>The thread that generated an event.</summary>
			public Thread m_thread;
			/// <summary>The lock object.</summary>
			public object m_object;
		}
		
		/// <summary>
		/// An array for holding synchronization events.
		/// Sergei: I made Lock to work 3 times faster by changing System.Collections.ArrayList to this self-implementation
		/// and changing Event to struct. The idea is that we don't have to allocate Event every time we create it.
		/// </summary>
		private class EventArray
		{
			/// <summary>The array of events.</summary>
			private Event[] m_events = new Event[EVENT_ARRAY_CAPACITY];
			
			/// <summary>
			/// The array size (not the allocated size - m_events.Length - also known as capacity, which is always bigger or
			/// equal to the array size).
			/// </summary>
			private int m_size = 0;
			
			/// <returns>Event by index.</returns>
			public Event this[int index]
			{
				get { return m_events[index]; }
			}
			
			/// <returns>Array size.</returns>
			public int Count
			{
				get { return m_size; }
			}
			
			/// <summary>Adds new event to the array.</summary>
			/// <param name="type">Event type: eather Waiting, Locked, or Unlocked.</param>
			/// <param name="thread">The thread that generates the event.</param>
			/// <param name="obj">Lock object.</param>
			/// <returns>Index of the newly created event in the array.</returns>
			public int add ( EventType type, Thread thread, object obj )
			{
				if ( m_size >= m_events.Length )
				{
					Event[] array = new Event[m_events.Length*2];
					Array.Copy ( m_events, 0, array, 0, m_size );
					m_events = array;
				}
				m_events[m_size].m_type = type;
				m_events[m_size].m_thread = thread;
				m_events[m_size].m_object = obj;
				return m_size++;
			}
			
			/// <summary>Appends the content of array to the end of this.</summary>
			/// <param name="array">The array to append.</param>
			public void add ( EventArray array )
			{
				if ( array.m_size > 0 )
				{
					if ( m_size + array.m_size > m_events.Length )
					{
						int newSize = m_events.Length * 2;
						while ( m_size + array.m_size > newSize )
							newSize *= 2;
						
						Event[] a = new Event[newSize];
						Array.Copy ( m_events, 0, a, 0, m_size );
						m_events = a;
					}
					Array.Copy ( array.m_events, 0, m_events, m_size, array.m_size );
					m_size += array.m_size;
				}
			}
			
			/// <summary>Empties the array.</summary>
			public void clear ()
			{
				m_size = 0;
			}
			
			/// <summary>Removes the event at index.</summary>
			/// <param name="index">The index of the event to remove.</param>
			public void remove ( int index )
			{
				if ( index < m_size - 1 )
					Array.Copy ( m_events, index + 1, m_events, index, m_size - index - 1 );
				m_size--;
			}
		}
		
		#endregion
		
		#region private members
		
		/// <summary>Current events array. It is used by Lock and Unlock functions to save info about the state.</summary>
		private static EventArray m_events         = new EventArray();
		
		/// <summary>
		/// History events array. It is used by DeadlockCollector thread to analyse the state. DeadlockCollector
		/// appends m_events to m_history and then analyses m_history. This is done for optimization: to minimize lock
		/// time for m_events preventing blocking (as much as possible) Lock and Unlock functions by DeadlockCollector
		/// thread.
		/// </summary>
		private static EventArray m_history        = new EventArray();
		
		/// <summary>
		/// Counter for the threads currently waiting for the lock. It is used for optimizations only.
		/// When Lock sees that more than one thread is in waiting state, it wakes up DeadlockCollector giving it a
		/// chance to analyze the state. If there is only one (or zero) thread waiting, there is no deadlock danger,
		/// so lock doesn't wake up DeadlockCollector, allowing it to sleep more.
		/// The optimization is: 1) minimize processor load by increasing DeadlockCollector sleep time; 2) minimize
		/// Lock execution time, because Monitor.Pulse (the function we use for waking up) is pretty time consuming.
		/// </summary>
		private static int m_waitingCounter        = 0;
		
		/// <summary><see cref="Log"></see></summary>
		private static TextWriter m_log            = null;
		
		/// <summary>
		/// m_nonameTheadsCounter is used in logging to give names to noname threads.
		/// If a thread doesn't have name and we need to write some info about it to the log, LockManager
		/// assigns the name 'Thread {0}' (where {0} is replaced by the value of m_nonameTheadsCounter) to it,
		/// so log readers could distinct threads.
		/// </summary>
		private static int m_nonameTheadsCounter   = 0;
		
		/// <summary>
		/// When DeadlockCollector finds a deadlock it adds all involved threads to this hashtable.
		/// The interrupted thread searches itself in this hashtable. If it is there, that means it's interrupted by
		/// DeadlockCollector - it throws DeadlockException. It it's not there, it's interrupted by someone else -
		/// it simply lets ThreadInterruptedException to go through.
		/// For all other threads the presence in this hashtable means that they have to print their stack trace to the
		/// log. So when deadlock happens we have stack traces for all involved threads helping us to analyze the deadlock.
		/// </summary>
		private static Hashtable m_markedThreads   = new Hashtable();
		
		/// <summary>Sleep timeout for DeadlockCollector. <see cref="CollectorSleepTimeout"/></summary>
		private static int m_collectorSleepTimeout = DEFAULT_SLEEP_TIME;
		
		#endregion
		
		#region initialization
		/// <summary>
		/// Starts DeadlockCollector thread.
		/// </summary>
		static LockManager()
		{
			Thread thread = new Thread ( new ThreadStart ( LockManager.run ) );
			//thread.Priority = ThreadPriority.BelowNormal;
			thread.Name = "DeadlockCollector";
			thread.Start ();
		}
		#endregion
		
		#region private functions
		
		/// <summary>
		/// Adds new synchronization event to m_events array.
		/// If event type is EventType.Waiting, it also wakes up DeadlockCollector thread to analyse deadlocks
		/// (although there is an optimization using m_waitingCounter, which allows sometimes avoid waking up DeadlockCollector
		/// <see cref="m_waitingCounter"/>).
		/// </summary>
		/// <param name="type">Event type.</param>
		/// <param name="obj">Lock object.</param>
		private static void addEvent ( EventType type, object obj )
		{
			Thread thread = Thread.CurrentThread;
			
			lock ( m_events )
			{
				m_events.add ( type, thread, obj );
				switch ( type )
				{
					case EventType.Waiting:
						if ( m_waitingCounter > 0 )
						{
							m_waitingCounter++;
							Monitor.Pulse ( m_events );
						}
						else
							m_waitingCounter = 1;
						break;

					case EventType.Locked:
						m_waitingCounter--;
						if ( m_markedThreads.ContainsKey ( thread ) )
						{
							m_markedThreads.Remove ( thread );
							if ( m_log != null )
							{
								m_log.WriteLine ( "Stack trace for the thread '{0}':", thread.Name );
								m_log.WriteLine ( Environment.StackTrace );
								m_log.WriteLine ( "---------------------------------------------------------------------" );
							}
						}
						break;

					case EventType.Interrupted:
						m_waitingCounter--;
						break;
				}
			}
		}
		
		/// <summary>
		/// Searches an event in m_history array.
		/// </summary>
		/// <param name="thread">Event thread.</param>
		/// <param name="obj">Event lock object.</param>
		/// <param name="type">Event type.</param>
		/// <param name="i">
		/// Starting index. The function searches from higher to lower. If i is 3, it will search evens #3, 2, 1, 0.
		/// </param>
		/// <returns>Event index in m_history, or negative if the event is not found.</returns>
		private static int findInHistory ( Thread thread, object obj, EventType type, int i )
		{
			for ( ; i >= 0; i-- )
			{
				Event e = m_history[i];
				if ( e.m_thread == thread && e.m_object == obj && e.m_type == type )
					break;
			}
			return i;
		}

		/// <summary>
		/// Searches for the thread that holds lock for the specific object (in m_history).
		/// </summary>
		/// <param name="obj">Lock object.</param>
		/// <param name="i">
		/// Starting index. The function searches from higher to lower. If i is 3, it will search evens #3, 2, 1, 0.
		/// </param>
		/// <returns>
		/// Event (that contain obj with EventType.Locked status) index in m_history, or negative if the event is not
		/// found.
		/// </returns>
		private static int findObjectHolder ( object obj, int i )
		{
			for ( ; i >= 0; i-- )
			{
				Event e = m_history[i];
				if ( e.m_object == obj && e.m_type == EventType.Locked )
					break;
			}
			return i;
		}

		/// <summary>
		/// Searches for an object that holds specific thread in m_history (in the other words an object which
		/// this thread is trying to lock).
		/// </summary>
		/// <param name="thread">The waiting thread.</param>
		/// <returns>
		/// Event (that contain the thread with EventType.Waiting status) index in m_history, or negative if the
		/// event is not found.
		/// </returns>
		private static int findThreadHolder ( Thread thread )
		{
			for ( int i = m_history.Count - 1; i >= 0; i-- )
			{
				Event e = m_history[i];
				if ( e.m_thread == thread && e.m_type == EventType.Waiting )
					return i;
			}
			return -1;
		}

		/// <summary>
		/// Checks is the event on index i in m_history is involved in deadlock.
		/// i must point to an event of the type EventType.Waiting, if not - results are unpredicatble.
		/// </summary>
		/// <param name="i">Index of the event to check.</param>
		/// <returns>true - if the event is involved in deadlock; false - if not.</returns>
		private static bool checkDeadLock ( int i )
		{
			Event e = m_history[i];
			Thread thread = e.m_thread;

			i = findObjectHolder ( e.m_object, i - 1 );
			if ( i < 0 )
				return false;
			Thread initialLockHolder = m_history[i].m_thread;
			Thread lockHolder = initialLockHolder;
			
			do
			{
				i = findThreadHolder ( lockHolder );
				if ( i < 0 )
					return false;

				i = findObjectHolder ( m_history[i].m_object, m_history.Count - 1 );
				if ( i < 0 )
					return false;
				lockHolder = m_history[i].m_thread;
				
				if ( lockHolder == thread )
					return true;
				
			}
			while ( lockHolder != initialLockHolder );
			
			return false;
		}
		
		/// <summary>
		/// DeadlockCollector entry point.
		/// </summary>
		private static void run ()
		{
			// This flag is used for possible situation when m_history contains two (or more) independent deadlocks.
			// After the first loop itteration finds and resolves one of them, the second itteration likely will 
			// fall into waiting state. Which is not good, because the second deadlock will be resolved only after
			// wait expiration. To prevent this we use checkAgain (see how it's used later).
			bool checkAgain = false;
			while ( true )
			{
				lock ( m_events )
				{
					// Sleep until timeout (CollectorSleepTimeout) is expired or some other thread wakes it up
					// (addEvent function). If m_events.Count is 0 (no new events happened) - continue sleeping.
					if ( !checkAgain )
					{
						while ( m_events.Count == 0 )
							Monitor.Wait ( m_events, m_collectorSleepTimeout );
					}
					else
						checkAgain = false;
 					
					// Append m_events to m_history and clear m_events. Release the lock for m_events allowing
					// other threads to call Lock/Unlock functions while DeadlockCollector performs deadlock analysis.
					lock ( m_history )
					{
						m_history.add ( m_events );
					}
					m_events.clear ();
				}
				
				// Note that we don't lock m_history unless m_history is changed
				// the only thread that can change m_history is this thread, so there is nobody 
				// who can change m_history while we read it.
				
				// garbage collect - remove all unlocked locks and all locked waits.
				for ( int i = m_history.Count - 1; i >= 0; i-- )
				{
					Event e = m_history[i];
					int j;
					switch ( e.m_type )
					{
						case EventType.Unlocked:
							lock ( m_history )
							{
								m_history.remove ( i );
								j = findInHistory ( e.m_thread, e.m_object, EventType.Locked, i - 1 );
								if ( j >= 0 ) 
								{
									m_history.remove ( j );
									i--;
									j = findInHistory ( e.m_thread, e.m_object, EventType.Waiting, j - 1 );
									if ( j >= 0 ) 
									{
										m_history.remove ( j );
										i--;
									}
								}
							}
							break;

						case EventType.Locked:
							j = findInHistory ( e.m_thread, e.m_object, EventType.Waiting, i - 1 );
							if ( j >= 0 )
							{
								lock ( m_history )
								{
									m_history.remove ( j );
									i--;
								}
							}
							break;

						case EventType.Interrupted:
							j = findInHistory ( e.m_thread, e.m_object, EventType.Waiting, i - 1 );
							lock ( m_history )
							{
								m_history.remove ( i );
								if ( j >= 0 )
								{
									m_history.remove ( j );
									i--;
								}
							}
							break;

					}
				}
				
				// Check deadlocks
				for ( int i = m_history.Count - 1; i >= 0; i-- )
				{
					Event e = m_history[i];
					if ( e.m_type == EventType.Waiting && checkDeadLock ( i ) )
					{
						// yes there is a deadlock

						// Set checkAgain to true preventing the loop from waiting state on the next itteraction.
						// We need this because may be m_history contains another independent deadlock, which
						// also needs to be resolved.
						checkAgain = true;

						lock ( m_events )
						{
							if ( m_log != null )
							{
								string threadName;

								// write deadlock traces to a log
								m_log.WriteLine ( "---------------------------------------------------------------------" );
								m_log.WriteLine ( "Deadlock history:" );
								for ( int j = 0; j < m_history.Count; j++ )
								{
									Event ev = m_history[j];

									threadName = ev.m_thread.Name;
									if ( threadName == null || threadName.Length == 0 )
									{
										threadName = ev.m_thread.Name = "" + m_nonameTheadsCounter;
										m_nonameTheadsCounter++;
									}
									
									// Mark thread to make Lock function (called from it) know
									// that we want it to print stack trace to a log.
									if ( !m_markedThreads.ContainsKey ( ev.m_thread ) )
										m_markedThreads.Add ( ev.m_thread, string.Empty );
									
									switch ( ev.m_type )
									{
										case EventType.Locked:
											m_log.WriteLine ( "Thread '{0}' locks the object '{1}'", threadName, ev.m_object );
											break;
										case EventType.Unlocked:
											m_log.WriteLine ( "Thread '{0}' unlocks the object '{1}'", threadName, ev.m_object );
											break;
										case EventType.Waiting:
											m_log.WriteLine ( "Thread '{0}' waits for the object '{1}'", threadName, ev.m_object );
											break;
										case EventType.Interrupted:
											m_log.WriteLine ( "Thread '{0}' was interrupted during waiting for the object '{1}'", threadName, ev.m_object );
											break;
									}
								}

								threadName = e.m_thread.Name;
								if ( threadName == null || threadName.Length == 0 )
								{
									threadName = e.m_thread.Name = "" + m_nonameTheadsCounter;
									m_nonameTheadsCounter++;
								}
								
								m_log.WriteLine ( "Deadlock collector interrupts thread '{0}' to resolve the deadlock", e.m_thread.Name );
								m_log.WriteLine ( "---------------------------------------------------------------------" );
							}
							
							// Mark thread to make Lock function (called from it) know
							// that we interrupt the thread because of the deadlock (it should throw DeadlockException
							// rather than rethrowin ThreadInterruptedException).
							// It also  signals that we want it to print stack trace to a log.
							if ( !m_markedThreads.ContainsKey ( e.m_thread ) )
								m_markedThreads.Add ( e.m_thread, string.Empty );
						}
						
						// interrupt deadlocked thread
						e.m_thread.Interrupt ();
						
						// remove the event telling that the thread is waiting from m_history.
						lock ( m_history )
						{
							m_history.remove ( i );
						}
						break;
					}
				}
			}
		}
		
		#endregion
		
		#region public functions and properties
		
		/// <summary>
		/// The timeout for DeadlockConnector. Most time the DeadlockConnector thread is sleeping
		/// waiting for other threads to wake it up when deadlock becomes possible (Lock function desides it).
		/// But internal events array continues to grow even if there is no deadlock danger. So sometimes
		/// DeadlockConnector thread wakes up itself to garbage collect this unnecessary info.
		/// CollectorSleepTimeout specifies time period (in milliseconds) between these automatic wakeups.
		/// Default value is 10 sec (10000).
		/// </summary>		
		public static int CollectorSleepTimeout
		{
			get
			{
				lock ( m_events )
				{
					return m_collectorSleepTimeout;
				}
			}

			set
			{
				lock ( m_events )
				{
					m_collectorSleepTimeout = value;
				}
			}
		}
		
		/// <summary>
		/// Text writer to write log info (deadlock traces). If null - no traces are written.
		/// </summary>
		public static TextWriter Log
		{
			get
			{
				lock ( m_events )
				{
					return m_log;
				}
			}
			
			set
			{
				lock ( m_events )
				{
					m_log = value;
				}
			}
		}
		
		/// <summary>
		/// Number of locks for current thread.
		/// Note that getting this property is pretty 'heavy' operation. If you are going to use it a couple of times
		/// in the same program block, you'd better assign it to local variable once, and use it instead.
		/// </summary>
		public static int LockCount
		{
			get
			{
				int count = 0;
				Thread thread = Thread.CurrentThread;
				lock ( m_history )
				{
					for ( int i = m_history.Count - 1; i >= 0; i-- )
						if ( m_history[i].m_thread == thread )
							switch ( m_history[i].m_type )
							{
								case EventType.Locked:
									count++;
									break;
								case EventType.Unlocked:
									count--;
									break;
							}
				}
				
				lock ( m_events )
				{
					for ( int i = m_events.Count - 1; i >= 0; i-- )
						if ( m_events[i].m_thread == thread )
							switch ( m_events[i].m_type )
							{
								case EventType.Locked:
									count++;
									break;
								case EventType.Unlocked:
									count--;
									break;
							}
				}
				
				return count;
			}
		}
		
		/// <summary>
		/// Locks the object.
		/// </summary>
		/// <param name="obj">The object to lock.</param>
		public static void Lock ( object obj )
		{
			Thread currentThread = Thread.CurrentThread;
			addEvent ( EventType.Waiting, obj );
			try
			{
				Monitor.Enter ( obj );
			}
			catch ( ThreadInterruptedException exc )
			{
				lock ( m_events )
				{
					if ( m_markedThreads.ContainsKey ( currentThread ) )
					{
						m_markedThreads.Remove ( currentThread );
						if ( m_log != null )
						{
							m_log.WriteLine ( "Stack trace for the thread '{0}':", currentThread.Name );
							m_log.WriteLine ( Environment.StackTrace );
							m_log.WriteLine ( "---------------------------------------------------------------------" );
						}
						throw new DeadlockException ( exc );
					}
					else
					{
						addEvent ( EventType.Interrupted, obj );
						throw exc;
					}
				}
			}
			catch ( Exception exc )
			{
				addEvent ( EventType.Interrupted, obj );
				throw exc;
			}
			addEvent ( EventType.Locked, obj );
		}
		
		/// <summary>
		/// Unocks the object.
		/// </summary>
		/// <param name="obj">The object to unlock.</param>
		public static void Unlock ( object obj )
		{
			Monitor.Exit ( obj );
			addEvent ( EventType.Unlocked, obj );
		}
		#endregion
	}
		
	/// <summary>
	/// This exception is thrown by LockManager.Lock function if deadlock occures.
	/// </summary>
	public class DeadlockException : Exception
	{
		/// <param name="exc">
		/// Exception thrown by Monitor.Enter, caused by DeadlockCollector Thread.Interrupt call.
		/// </param>
		public DeadlockException ( ThreadInterruptedException exc ) : base ( "Deadlock", exc )
		{
		}
	}
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

SZotin

Canada Canada
No Biography provided

| Advertise | Privacy | Mobile
Web01 | 2.8.140827.1 | Last Updated 12 Aug 2003
Article Copyright 2003 by SZotin
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid