Eyal Perry Eyal Perry - 1 month ago 9
C# Question

Monitor.Enter(object,ref bool) Implementation and Order of Lock Acquisition

From Reference Source we can see that the aforementioned method is implemented as follows:

public static void Enter(Object obj, ref bool lockTaken)
{
if (lockTaken)
ThrowLockTakenException();

ReliableEnter(obj, ref lockTaken);
Contract.Assert(lockTaken);
}


I have an issue is with the 'if' statement- I understand it's importance, there's no need to explain that. I believe this statement also introduces a very subtle issue.

Consider the following scenario:
One thread calls into the method and evaluates the if statement, at which point a context switch occurs and another calls into the method, successfully obtaining the lock.

This is a feasible scenario which suggests that the order of lock acquisition is not necessarily the same as the order of method invocation.

While it may not really make a difference in some scenarios, it could be of critical importance in others, so my questions are:

1) Am I missing something, or is the Monitor class less suited for use in scenarios where such occurrences are unacceptable?

2) Is it possible that ReliableEnter suffers from a similar condition?

3)Is there a synchronization mechanism which ensures that the order of method invocation is the same as the order of lock acquisition?

Answer

One thread calls into the method and evaluates the if statement, at which point a context switch occurs and another calls into the method, successfully obtaining the lock.

That's totally possible.

Or, there might be no context switch but this still happens. Two threads both get past the "if" and into ReliableEnter, there's no context switch on either, and one wins. Can you think of a scenario in which that happens?

This is a feasible scenario which suggests that the order of lock acquisition is not necessarily the same as the order of method invocation.

Remember the story of the three umpires.

Three umpires are having lunch. The first says "I calls them as I sees them". The second says "I calls them as they are". The third says "They ain't nothing until I calls them."

The first umpire believes that observation is imperfect and that people can disagree as to whether a pitch is a ball or a strike. The second believes that there is a consistent physical world and they have accurate information about it; whether a pitch is a ball or a strike can be determined objectively. The third believes that irrespective of whether the world is consistent and knowable, the rules of baseball say that a strike is anything that the umpire calls a strike.

You're the second umpire. You think there actually is such a thing as "the order in which method calls occur" in a multithreaded world, and that there is a way to know about it. But really the world is more like the first umpire: everyone can see a different world and disagree on it. And locks are more like the third umpire: locks are the things that impose an ordering upon an unordered world. What order were the methods called in? Take a lock and find out.

Abandon the myth that there is a consistent order in which things happen in the multithreaded world. There is no such consistent order. Every processor can reorder code as much as it wants within the memory model constraints. Every thread can see a different ordering of reads and writes.

What every thread agrees on is the order in which locks are taken, so that is the sensible thing to consider "the order" in which methods are called.

So, can locks happen in a different order than method calls? The first umpire says "no one can know for sure". The second says "yes". The third says "there is no order at all until a lock is taken".

I agree with the third umpire. Can a lock be taken in a different order than the methods were called? Since the only way to impose that order is to take a lock, it's not really a sensible question.

1) Am I missing something, or is the Monitor class less suited for use in scenarios where such occurrences are unacceptable?

That's the wrong way to look at it.

If we continue believing the fiction that there is an order in which calls happen, and you have a program which depends for its correctness upon locks being taken in that entirely mythological order, then that program has a bug. Locks are not taken in "the order that the calls happen", end of story, and if you depend on that, then you're depending on a guarantee made by no one and often violated.

2) Is it possible that ReliableEnter suffers from a similar condition?

I don't understand the question. Do you mean, if we replaced every call to Enter with a call to ReliableEnter, would we still have the same issue? Yes, absolutely.

3)Is there a synchronization mechanism which ensures that the order of method invocation is the same as the order of lock acquisition?

There is no such order independent of locks, so no.

I have an issue is with the 'if' statement- I understand it's importance, there's no need to explain that. I believe this statement also introduces a very subtle issue.

Your belief is wrong. The issue is introduced by the fact that there is no such thing as "the order in which method calls happen" in a multithreaded world. The "if" has nothing whatsoever to do with it.

Moreover, even in a world where we can extract ordering information from a lock, locks are not guaranteed to be fair. If you have ten threads all waiting on a lock there is no requirement imposed by the C# language that the thread that has been "waiting longest" or "called first" -- whatever that means -- is the one who gets access to the monitor next. The operating system has broad latitude to schedule threads as it sees fit, and it is within its rights to starve a thread indefinitely.

Now, there are many half-truths in what I've said above. The actual state of the world is very confusing. If you want to know the truth then you should read the section of the C# specification about ordering of side effects in multithreaded programs, which describes the events which are guaranteed to be observed to be in particular orders: locks, creations of threads, certain kinds of reads and writes, exceptions and constructor calls. The ordering guarantees are in some cases very weak.

As I always do when this comes up, I recommend that you read my article on how reorderings can happen in a world without locks. See if you can solve the puzzle I pose in the second part.

http://blog.coverity.com/2014/03/12/can-skip-lock-reading-integer/ http://blog.coverity.com/2014/03/26/reordering-optimizations/