Introduction
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.
Using PriorityLock
Before looking into the details of the implementation, here is a simple example that demonstrates its usage.
using Senthil.Concurrency.Utilities;
class PriorityMonitorTest
{
static PriorityLock priorityLock = new PriorityLock();
public static void Main()
{
new Thread(ThreadProc).Start(1);
new Thread(ThreadProc).Start(2);
new Thread(ThreadProc).Start(3);
}
static void ThreadProc(object target)
{
int x = (int)target;
try
{
priorityLock.Lock(x);
Console.WriteLine(x);
Thread.Sleep(1000);
}
finally
{
priorityLock.Unlock();
}
}
}
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).
The API
PriorityMonitor()
- creates a new instance of PriorityMonitor
.
Lock(int priority)
- attempts to acquire the lock with the specified priority
.
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.Wait
and Monitor.Pulse
methods. Here's how the pseudocode for the Lock
method looks like:
public void Lock(int priority)
{
if NoThreadHasAcquiredLock OR CurrentThreadHoldsLock
{
SetCurrentThreadAsOwner
}
else
{
PushRequestIntoPriorityQueue
WaitForPriorityQueueSignal
}
}
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
ReleaseLock
If NoThreadHasAcquiredLock AND PriorityQueueHasItems
{
PopNextRequestFromPriorityQueue
SignalRequestToProceed
}
}
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.
Recursive Acquisitions?
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.
Contention Required
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.
Performance
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 :).
History
- 20:57 30-11-2006 - Initial submission.