Click here to Skip to main content
Click here to Skip to main content
Go to top

PriorityLock - Release locks by priority

, 30 Nov 2006
Rate this:
Please Sign up or sign in to vote.
A Monitor like class that releases locks by priority.

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 Smile | :) .

History

  • 20:57 30-11-2006 - Initial submission.

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

S. Senthil Kumar
Software Developer Atmel R&D India Pvt. Ltd.
India India
I'm a 27 yrs old developer working with Atmel R&D India Pvt. Ltd., Chennai. I'm currently working in C# and C++, but I've done some Java programming as well. I was a Microsoft MVP in Visual C# from 2007 to 2009.
 
You can read My Blog here. I've also done some open source software - please visit my website to know more.

Comments and Discussions

 
GeneralSilly question Pinmemberknocte22-Mar-07 21:53 
GeneralRe: Silly question PinmemberTim Arheit7-Feb-14 8:07 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web03 | 2.8.140921.1 | Last Updated 30 Nov 2006
Article Copyright 2006 by S. Senthil Kumar
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid