Locks are not guaranteed to be FIFO

Locks can hold a few surprises for the uninitiated. One of the less than obvious surprises is to assume that if a thread is first to acquire a lock, that the thread will be first to enter a lock. It can be easy to assume that locks operate on a first-in-first-out (FIFO) basis because that's what they seem to do when there is infrequent lock contention.

Sadly threads queued behind a locks (including SemaphoreSlim) are not guaranteed to be queued and acquired in FIFO order.

Let's test this hypothesis by first creating a simple record class...

public class Record
{
  public int ThreadId { get; set; }
  public int QueuedSeqNo { get; set; }
  public int AcquiredSeqNo { get; set; }
}

I wanted to create a race of 10 threads trying to acquire the same lock. I created record and stored the order in which the thread was queued. I then record the sequence in which the lock was acquired. I add this to a list to hold the records in whatever order the lock is acquired in. After the threads have completed, I traverse the list looking for non-FIFO sequencing. Here is the main ...

int seqCounter = 0;
object theLock = new object();
List<Record> sequence = new List<Record>();

int[] threadIds = Enumerable.Range(200, 10).ToArray();

var threads = threadIds.Select(threadId => new Thread(() =>
{
  Record record = new Record {ThreadId = threadId};
  record.QueuedSeqNo = Interlocked.Increment(ref seqCounter);
  lock (theLock)
  {
    record.AcquiredSeqNo = Interlocked.Increment(ref seqCounter);
    sequence.Add(record);
  }
})).ToList();

threads.ForEach(thread => thread.Start());
threads.ForEach(thread => thread.Join());

foreach (var rec1 in sequence)
{
  foreach (var rec2 in sequence)
  {
    if 
    (
      (rec1.QueuedSeqNo < rec2.QueuedSeqNo) 
      && 
      (rec1.AcquiredSeqNo > rec2.AcquiredSeqNo)
    )
    {
      Console.WriteLine(
        $"Error:     {rec1.ThreadId} was queued at       " +
        $"{rec1.QueuedSeqNo:000} which entered at      " + 
        $"{rec1.AcquiredSeqNo:000}\n" +
        $"     : but {rec2.ThreadId} was queued after at " +
        $"{rec2.QueuedSeqNo:000} and entered before at " + 
        $"{rec2.AcquiredSeqNo:000}\n");
      }
    }
  }
}

I used an Interlocked integer to provide a thread-safe increasing sequence number to identify the order of operations. It is my understanding that DateTime.UtcNow will not provide the resolution I need and I am not convinced is is guaranteed to strictly increase (i.e monotonically increasing).

The output of one of my runs of this code is ...

Error:     203 was queued at       002 which entered at      011
     : but 207 was queued after at 008 and entered before at 010

Error:     201 was queued at       003 which entered at      012
     : but 207 was queued after at 008 and entered before at 010

Error:     204 was queued at       004 which entered at      013
     : but 207 was queued after at 008 and entered before at 010

Error:     205 was queued at       005 which entered at      014
     : but 207 was queued after at 008 and entered before at 010

Error:     206 was queued at       006 which entered at      015
     : but 207 was queued after at 008 and entered before at 010

Error:     202 was queued at       007 which entered at      018
     : but 207 was queued after at 008 and entered before at 010

Error:     202 was queued at       007 which entered at      018
     : but 208 was queued after at 016 and entered before at 017

The most authoritative reference I can find for why this is the case comes from this stackoverflow question which quotes Joe Duffy's "Concurrent Programming on Windows"

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 tries to acquire the lock before an awakened waiting thread tries to acquire the lock, the sneaky thread is permitted to acquire a lock.