PriorityLock - Release locks by priority

• Download source files - 33.6 Kb
• Download demo project - 6 Kb

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.