Is there a synchronization class that guarantee FIFO order in C#?

Question

What is it and how to use?

I need that as I have a timer that inserts into DB every second, and I have a shared resource between timer handler and the main thread. I want to gurantee that if the timer handler takes more than one second in the insertion the waited threads should be executed in order. This is a sample code for my timer handler:

private void InsertBasicVaraibles(object param)
{
    try
    {
        DataTablesMutex.WaitOne();//mutex for my shared resources
         //insert into DB
    }
    catch (Exception ex)
    {
        //Handle
    }
    finally
    {
        DataTablesMutex.ReleaseMutex();
    }
}

But currently the mutex does not guarantee any order.

Bumf

by definition a lock is FIFO. One thread goes in, and noone else gets in until it gets out! – Nut

@Mitch: But there's no guarantee that the first thread that had to wait is the one that gets unblocked immediately afterwards. So no, locks aren't FIFO. – Insensate

(i.e. if T1 currently holds the lock, then T2 attempts to acquire it, then T3 attempts to acquire it, there's no guarantee that T3 will get it before T2 does.) – Insensate

There aren't any FIFO locks in .NET. You could probably build one, but that could be a tedious (and bug prone) process. – Submarginal

Perhaps a better description of the problem should be posted, there are probably other ways to achieve what Ahmed needs. – Rage

Answer 1

You'll need to write your own class to do this, I found this example (pasted because it looks as though the site's domain has lapsed):

using System.Threading;

public sealed class QueuedLock
{
    private object innerLock;
    private volatile int ticketsCount = 0;
    private volatile int ticketToRide = 1;

    public QueuedLock()
    {
        innerLock = new Object();
    }

    public void Enter()
    {
        int myTicket = Interlocked.Increment(ref ticketsCount);
        Monitor.Enter(innerLock);
        while (true)
        {

            if (myTicket == ticketToRide)
            {
                return;
            }
            else
            {
                Monitor.Wait(innerLock);
            }
        }
    }

    public void Exit()
    {
        Interlocked.Increment(ref ticketToRide);
        Monitor.PulseAll(innerLock);
        Monitor.Exit(innerLock);
    }
}

Example of usage:

QueuedLock queuedLock = new QueuedLock();

try
{
   queuedLock.Enter();
   // here code which needs to be synchronized
   // in correct order
}
finally
{
    queuedLock.Exit();
}

Source via archive.org

Tyus

This would be prettier if QueuedLock was IDisposable – Galoot

Nowdays passing volatile by ref is not encouraged by C# compiler, gives it the warning that it won't be treated as volatile. Other than that a perfect solution to my today's problem! – Eldridgeeldritch

Can I Enter() twice on the same thread (before the first one exits, e.g. in a nested function)? – Mace

@AntonDuzenko No, this answer doesn't support nested locks in the same thread. – Trisyllable

Answer 2

Just reading Joe Duffy's "Concurrent Programming on Windows" it sounds like you'll usually get FIFO behaviour from .NET monitors, but there are some situations where that won't occur.

Page 273 of the book says: "Because monitors use kernel objects internally, they exhibit the same roughly-FIFO behavior that the OS synchronization mechanisms also exhibit (described in the previous chapter). Monitors are unfair, so if another thread sneaks in and acquires the lock before an awakened waiting thread tries to acquire the lock, the sneaky thread is permitted to acquire the lock."

I can't immediately find the section referenced "in the previous chapter" but it does note that locks have been made deliberately unfair in recent editions of Windows to improve scalability and reduce lock convoys.

Do you definitely need your lock to be FIFO? Maybe there's a different way to approach the problem. I don't know of any locks in .NET which are guaranteed to be FIFO.

Insensate

Jon Skeet is as usual, correct - Win2k3 SP2(ish?) and up do not have 100% fair locking, and this is intentional. – Nosography

What's really fun is when the "sneaky thread" also happens to be the one which just released the Monitor. And, thus, it continues forever in a loop, starving out the other thread. Just ran into this behavior with some old code in .Net Compact Framework on CE 5. – Vickeyvicki

Answer 3

You should re-design your system to not rely on the execution order of the threads. For example, rather than have your threads make a DB call that might take more than one second, have your threads place the command they would execute into a data structure like a queue (or a heap if there is something that says "this one should be before another one"). Then, in spare time, drain the queue and do your db inserts one at a time in the proper order.

Tepid

Answer 4

There is no guaranteed order on any built-in synchronisation objects: http://msdn.microsoft.com/en-us/library/ms684266(VS.85).aspx

If you want a guaranteed order you'll have to try and build something yourself, note though that it's not as easy as it might sound, especially when multiple threads reach the synchronisation point at (close to) the same time. To some extent the order they will be released will always be 'random' since you cannot predict in which order the point is reached, so does it really matter?

Forklift

The link is of course about the OS primitives... at some point the .NET ones will be built on top of these, so I guess that implies FIFO cannot be guaranteed... see also Jon's answer. – Forklift

The problem isn't generally with threads entering the lock in a random order when they all try to grab the lock at the same time. The problem arises when threads that have been waiting to enter the lock for a long time get cut in line by threads that tried to enter the lock much later. Imagine a busy web server where 1000 requests are constantly trying to access a shared resource, and the first thread to wait on a lock keeps waiting because later requests keep stealing the lock ahead of their turn. – Jackhammer

Answer 5

Actually the answers are good, but I solved the problem by removing the timer and run the method (timer-handler previously) into background thread as follows

    private void InsertBasicVaraibles()
    {
         int functionStopwatch = 0;
         while(true)
         {

           try
           {
             functionStopwatch = Environment.TickCount;
             DataTablesMutex.WaitOne();//mutex for my shared resources
             //insert into DB 
           }
           catch (Exception ex)
           {
             //Handle            
           }
           finally            
           {                
              DataTablesMutex.ReleaseMutex();
           }

           //simulate the timer tick value
           functionStopwatch = Environment.TickCount - functionStopwatch;
           int diff = INSERTION_PERIOD - functionStopwatch;
           int sleep = diff >= 0 ?  diff:0;
           Thread.Sleep(sleep);
        }
    }

Bumf

Answer 6

Follow up on Matthew Brindley's answer.

If converting code from

lock (LocalConnection.locker) {...}

then you could either do a IDisposable or do what I did:

public static void Locking(Action action) {
  Lock();
  try {
    action();
  } finally {
    Unlock();
  }
}

LocalConnection.Locking( () => {...});

I decided against IDisposable because it would creates a new invisible object on every call.

As to reentrancy issue I modified the code to this:

public sealed class QueuedLock {
    private object innerLock = new object();
    private volatile int ticketsCount = 0;
    private volatile int ticketToRide = 1;
    ThreadLocal<int> reenter = new ThreadLocal<int>();

    public void Enter() {
        reenter.Value++;
        if ( reenter.Value > 1 ) 
            return;
        int myTicket = Interlocked.Increment( ref ticketsCount );
        Monitor.Enter( innerLock );
        while ( true ) {
            if ( myTicket == ticketToRide ) {
                return;
            } else {
                Monitor.Wait( innerLock );
            }
        }
    }

    public void Exit() {
        if ( reenter.Value > 0 ) 
            reenter.Value--;
        if ( reenter.Value > 0 ) 
            return;
        Interlocked.Increment( ref ticketToRide );
        Monitor.PulseAll( innerLock );
        Monitor.Exit( innerLock );
    }
}

Mace

It would be amazing if you could explain about the changes you did :) – Raby

Since it's been two years I can't remember the rationale. But this is what I ended up with. – Mace

Answer 7

In case anyone needs Matt's solution in F#

    type internal QueuedLock() =
        let innerLock = Object()
        let ticketsCount = ref 0
        let ticketToRide = ref 1
        member __.Enter () =
            let myTicket = Interlocked.Increment ticketsCount
            Monitor.Enter innerLock
            while myTicket <> Volatile.Read ticketToRide do
                Monitor.Wait innerLock |> ignore
        member __.Exit () =
            Interlocked.Increment ticketToRide |> ignore
            Monitor.PulseAll innerLock
            Monitor.Exit innerLock

Ferromagnetic

Answer 8

Elaborating on Matt Brindley's great answer so that it works with the using statement:

public sealed class QueuedLockProvider
{
  private readonly object _innerLock;
  private volatile int _ticketsCount = 0;
  private volatile int _ticketToRide = 1;

  public QueuedLockProvider()
  {
    _innerLock = new object();
  }

  public Lock GetLock()
  {
    return new Lock(this);
  }

  private void Enter()
  {
    int myTicket = Interlocked.Increment(ref _ticketsCount);
    Monitor.Enter(_innerLock);
    while (true)
    {

      if (myTicket == _ticketToRide)
      {
        return;
      }
      else
      {
        Monitor.Wait(_innerLock);
      }
    }
  }

  private void Exit()
  {
    Interlocked.Increment(ref _ticketToRide);
    Monitor.PulseAll(_innerLock);
    Monitor.Exit(_innerLock);
  }

  public class Lock : IDisposable
  {
    private readonly QueuedLockProvider _lockProvider;

    internal Lock(QueuedLockProvider lockProvider)
    {
      _lockProvider = lockProvider;
      _lockProvider.Enter();
    }

    public void Dispose()
    {
      _lockProvider.Exit();
    }
  }
}

Now use it like this:

QueuedLockProvider _myLockProvider = new QueuedLockProvider();

// ...

using(_myLockProvider.GetLock())
{
  // here code which needs to be synchronized
  // in correct order
}

Secretary

Answer 9

NOTE: The examples provided are susceptible to Deadlocks. Example:

QueuedLock queuedLock = new QueuedLock();
void func1()
{
    try
    {
       queuedLock.Enter();
       fubc2()
    }
    finally
    {
        queuedLock.Exit();
    }
}

void func2()
{
    try
    {
       queuedLock.Enter();  //<<<< DEADLOCK

    }
    finally
    {
        queuedLock.Exit();
    }
}

Re. optional solution (inc. an optional IDisposable usage):

public sealed class QueuedLock
{
    private class SyncObject : IDisposable
    {
        private Action m_action = null;
        public SyncObject(Action action)
        {
            m_action = action;
        }

        public void Dispose()
        {
            lock (this)
            {
                var action = m_action;
                m_action = null;
                action?.Invoke();
            }
        }
    }

    private readonly object m_innerLock = new Object();
    private volatile uint m_ticketsCount = 0;
    private volatile uint m_ticketToRide = 1;

    public bool Enter()
    {
        if (Monitor.IsEntered(m_innerLock))
            return false;

        uint myTicket = Interlocked.Increment(ref m_ticketsCount);
        Monitor.Enter(m_innerLock);
        while (true)
        {
            if (myTicket == m_ticketToRide)
                return true;

            Monitor.Wait(m_innerLock);
        }
    }

    public void Exit()
    {
        Interlocked.Increment(ref m_ticketToRide);
        Monitor.PulseAll(m_innerLock);
        Monitor.Exit(m_innerLock);
    }

    public IDisposable GetLock()
    {
        if (Enter())
            return new SyncObject(Exit);

        return new SyncObject(null);
    }
}

Usage:

QueuedLock queuedLock = new QueuedLock();
void func1()
{
    bool isLockAquire = false;
    try
    {
       isLockAquire = queuedLock.Enter();
       // here code which needs to be synchronized in correct order
    }
    finally
    {
        if (isLockAquire)
           queuedLock.Exit();
    }
}

or:

QueuedLock queuedLock = new QueuedLock();
void func1()
{
    using (queuedLock.GetLock())
    {
       // here code which needs to be synchronized in correct order
    }
}

Heeled