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

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.

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.

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?

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); } } 

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 ); } } 

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 

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 } 

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 } }