How does the Lock statement determines the order of granting object access?

Question

I require a section of the code to be run by only one thread at time (single resource lock).

the lock(object) statement in C# allows this. It doesn't however, preserve the order of requests to the lock.

For example, consider the 100 threadstarts below where numbered threads try to lock on padlock in order:

    for (int i = 0; i < 100; i++)
             {

            (new Thread(delegate(object index) 
               {
                  int name = (int) index;
                  byte[] len = new byte[2];

                  Console.WriteLine(string.Format("Thread:{0} going for lock. ",
                      name));
                  lock (padlock)
                  {

                     rnd.GetBytes(len);
                     ushort l = BitConverter.ToUInt16(len, 0);
                     Console.WriteLine(string.Format("Thread:{0} sleeping: {1}", 
                       name, l));
                     Thread.Sleep(l);
                  }
            })).Start(i);

The actual granting of the access is not in perfect order (1->100) or NOT FIFO. However there does seem to be an "early-in-early-out" EIEO pattern (run by a heap perhaps?).

The Question is: What determines the lock granting order and can it be relied on not starving an unlucky thread?

Update: this answer explains it. Here is the pertinent quote (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.

http://stackoverflow.com/q/5111779/34397 http://stackoverflow.com/q/4228864/34397 — SLaks, May 21 '13 at 20:14
@SLaks the Jon Skeet answer in the second one renders this as duplicate. — MandoMando, May 21 '13 at 20:21
Hah, apparently you were looking up Joe's quote at the same time as I was. — Eric Lippert, May 21 '13 at 20:31
I feel like you are suffering from the X Y problem. Anyhow, maybe just stuff your requests into a [`BlockingCollection`](http://msdn.microsoft.com/en-us/library/dd267312.aspx)? — Brian, May 22 '13 at 13:58
@Brian it's nice to know BlockingCollection is available. But I don't see it as the same problem. — MandoMando, May 22 '13 at 14:14

Eric Lippert · Answer 1 · 2018-07-26T22:40:00.527

5

Servy's answer is of course correct. A few additional details:

What determines the lock granting order?

Ultimately, the operating system.

Can it be relied on not starving an unlucky thread?

Starvation is unlikely but possible. If you cannot abide even a small chance of starvation, you'll need something more complicated than a lock.

I note also that locks are "unfair" in that you can have one thread in the lock, eight threads waiting, the thread in the lock leaves, and a tenth thread that was not waiting at all asks for the lock and gets it, effectively "cutting the line". Joe gives an interesting analysis of why Windows now uses "unfair" lock allocation strategies here, if this subject interests you:

http://joeduffyblog.com/2006/12/14/anticonvoy-locks-in-windows-server-2003-sp1-and-windows-vista/

edited Jul 26 '18 at 22:40

answered May 21 '13 at 20:29

Eric Lippert

647,829
179
1,238
2,067

Interesting bit about the unfair. I always assumed windows was unfair (not in a moral way). Are there "fair" locking objects outside a complex sync queue? – MandoMando May 21 '13 at 20:32
@MandoMando: I'm not aware of any but I am far from an expert on this topic. – Eric Lippert May 21 '13 at 20:34
@MandoMando You can build a fair system out of an unfair system if you're suitably motivated (Just create a `Queue` and synchronize access, as a simple example), it just lowers the throughput of the application as a result of that overhead. Since it's rarely an issue the throughput is usually "worth more" than the fairness. – Servy May 21 '13 at 20:34
@Servy I built one a while back based on the queue and felt guilty since there _should_ be a fair version built-in the framework. Was curious what I'm missing which, you confirmed. – MandoMando May 21 '13 at 20:44

score 3 · Answer 2 · answered May 21 '13 at 20:13

3

What determines the lock granting order

There is no order defined in the specs. You cannot rely on any order.

can it be relied on not starving an unlucky thread?

No. You would need to manage that manually if it's a potential problem in your application.

Also note that the order that the threads will run in is undetermined for several different reasons. You know that all of the threads are going to be started in a particular order, but once they're started you have no idea how they'll be scheduled. They could each hit the lock block in any order. Even if it was FIFO based on when they hit the lock, it'd still be undefined.

answered May 21 '13 at 20:13

Servy

202,030
26
332
449

1

Extending the point a bit: If you want precise control of when something runs, you usually don't want a thread. You'd do well to think of threads as trying to enforce Murphy's Law, running whenever they damn well please, which is invariably at exactly the wrong times. – cHao May 21 '13 at 20:28
@cHao no, these are requests coming from the network and just don't want to starve them. It's ok if the OS takes a little bribery and favoritism. Seems to happen everywhere these days. – MandoMando May 21 '13 at 20:46

How does the Lock statement determines the order of granting object access?

2 Answers2

Linked