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.
Top comments (0)