The idea for this article came from a query posted in the C# forum. The poster basically wanted a
System.Threading.Monitor like lock, but wanted the lock to be released to threads based on priority, instead of a FIFO/random order. For example, if thread 1 with priority 1 and thread 2 with priority 2 are contending for a lock, the poster wanted thread 2 to get the lock, regardless of the order in which the threads tried to acquire the lock.
PriorityLock does exactly that, allowing the users of the class to provide a priority parameter when locking. It then makes sure that the threads get to acquire the lock based on priority. It does not require users of the class to fiddle with the priority of threads.
Before looking into the details of the implementation, here is a simple example that demonstrates its usage.
static PriorityLock priorityLock = new PriorityLock();
public static void Main()
static void ThreadProc(object target)
int x = (int)target;
This simple example just creates three threads, passing an integer that will be interpreted as the priority by
ThreadProc. To simulate contention, the
ThreadProc methods sleeps for a second, thereby making it reasonably possible for the second and third threads to run and try to acquire
priorityMonitor. Let's assume the first thread acquires the lock and sleeps. Let's also assume that threads 2 and 3 run and contend for the lock. Had there been a normal
System.Threading.Monitor lock, there would be no guarantee as to which of the two threads will acquire the lock first.
PriorityMonitor, however, makes sure that thread 3 gets to acquire the lock first, followed by thread 2 (because thread 3 attempted to acquire the lock with the higher priority).
PriorityMonitor() - creates a new instance of
Lock(int priority) - attempts to acquire the lock with the specified
Unlock() - releases the lock held by the current thread.
How it Works
PriorityLock internally uses a priority queue (implemented by BenDi) to take care of ordering by priority. To block and release threads, it uses the
Monitor.Pulse methods. Here's how the pseudocode for the
Lock method looks like:
public void Lock(int priority)
if NoThreadHasAcquiredLock OR CurrentThreadHoldsLock
As you can see, if the lock is free or is already held by the current thread, there is no blocking involved at all. The pseudocode for the
Unlock method looks like this:
public void Unlock()
CheckIfCurrentThreadHoldsLock, If Not, Throw Exception
If NoThreadHasAcquiredLock AND PriorityQueueHasItems
The first statement is only a sanity check that makes sure that only a thread that holds the lock can call
Unlock. The rest of the code simply checks if there are items to be scheduled, and if available, picks it from the priority queue and signals it to run.
The possibility of recursive acquisitions makes the logic a bit more complex.
PriorityLock now needs to track the number of recursive calls to
Lock and make sure that the lock is released only when there is an equivalent number of
Unlock method calls on the same thread. This is the reason why the pseudocode for
Unlock actually checks if the lock is available immediately after releasing the lock, as the thread could have called the method anywhere in the recursive stack.
To take care of counting the number of recursive acquisitions/releases of the lock,
PriorityLock uses a
Dictionary keyed by the thread ID. The
Lock method increments the lock count for the thread in the dictionary, and the
Unlock method decrements it, removing the entry once the count hits zero.
Note that the lock sequencing would take effect only when there is lock contention. If threads don't contend for a lock, i.e., threads execute almost one by one, then the priorities provided to
PriorityLock would have no effect. In the example above, if thread 2 and thread 3 ran one after the other (or thread 3 ran after thread 2 acquired the lock), then the priorities would be meaningless.
Profiling with the built-in profiler in VS.NET 2005 showed that performance is comparable to that of code that uses
System.Threading.Monitor. For the example mentioned, it actually performed better than
Monitor. Code using
PriorityMonitor took 228634.416314 msec, whereas code using
System.Threading.Monitor took 229491.008955 msec to complete. The source code download comes with performance reports generated by Visual Studio's profiler, so you can take a look to verify the claim :).
- 20:57 30-11-2006 - Initial submission.