Are threads waiting on a lock FIFO?

Question

Let's say I have the following code

static class ...
{
    static object myobj = new object();

    static void mymethod()
    {
        lock(myobj)
        {
            // my code....
        }
    }
}

Then let's say that while thread1 has the lock thread2 tries to run mymethod. Will it wait for the lock to be released or throw an exception?

If it does wait, is order ensured so that if additional threads come in they are FIFO?

Answer 1

Updated my answer: They are queued, but the order is not guaranteed to be FIFO.

Check out this link: http://www.albahari.com/threading/part2.aspx

Answer 2

It is not clear from your code how does myobj get to be visible inside mymethod. Looks like var myobj is a local stack variable at the declaration scope (since is var). In that case it may be that each thread will have a separate instance of it and the mymethod will not block.

Update

About the whole FIFO argument, some background info is necessary: the CLR does not provide syncronization. It is the CLR host that provides this as a service to the CLR runtime. The host implements IHostSyncManager and other interfaces and provides the various syncronisation primitives. This may seem irelevant as the most common host is the typical application host (ie. you compile into and exe) and this deffers all synchronization to the OS (your old Petzold book primitives in Win32 API). However there are at least two more major hosting evironments: the ASP.Net one (I'm not sure what this does) and SQL Server. What I can tell for sure is that SQL Server provides all primitives on toop of the SOS (which is basically an user more operating system), never touching the OS primitives, and the SOS primitives are unfair by design to avoid lock convoys (ie. guranteed no FIFO). As the link in the other response already pointed out, the OS primitives have started also to provide unfair behavior, for the same reason of avoiding lock convoys.

For more information about lock convoys you should read the Rick Vicik articles at Designing Applications for High Performance:

Lock Convoy

FIFO locks guarantee fairness and forward progress at the expense of causing lock convoys. The term originally meant several threads executing the same part of the code as a group resulting in higher collisions than if they were randomly distributed throughout the code (much like automobiles being grouped into packets by traffic lights). The particular phenomenon I’m talking about is worse because once it forms the implicit handoff of lock ownership keeps the threads in lock-step.

To illustrate, consider the example where a thread holds a lock and it gets preempted while holding the lock. The result is all the other threads will pile up on the wait list for that lock. When the preempted thread (lock owner at this time) gets to run again and releases the lock, it automatically hands ownership of the lock to the first thread on the wait list. That thread may not run for some time, but the “hold time” clock is ticking. The previous owner usually requests the lock again before the wait list is cleared out, perpetuating the convoy

Answer 3

A simple example tell us that order is not guaranteed to be FIFO

    using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Diagnostics;


namespace ConsoleApplication
{
    class Program
    {
        private static Info info = new Info();

        static void Main(string[] args)
        {
            Thread[] t1 = new Thread[5];
            for (int i = 0; i < 5; i++)
            {
                t1[i] = new Thread(info.DoWork);
            }

            Thread[] t2 = new Thread[5];
            for (int i = 0; i < 5; i++)
            {
                t2[i] = new Thread(info.Process);
            }

            for (int i = 0; i < 5; i++)
            {
                t1[i].Start();
                t2[i].Start();
            }

            Console.ReadKey();
        }
    }

    class Info
    {
        public object SynObject = new object();

        public void DoWork()
        {
            Debug.Print("DoWork Lock Reached: {0}", Thread.CurrentThread.ManagedThreadId);
            lock (this.SynObject)
            {
                Debug.Print("Thread Lock Enter: {0}", Thread.CurrentThread.ManagedThreadId);
                Thread.Sleep(5000);
                Debug.Print("Thread Lock Exit: {0}", Thread.CurrentThread.ManagedThreadId);
            }
        }

        public void Process()
        {
            Debug.Print("Process Lock Reached: {0}", Thread.CurrentThread.ManagedThreadId);
            lock (this.SynObject)
            {
                Debug.Print("Process Lock Enter: {0}", Thread.CurrentThread.ManagedThreadId);
                Thread.Sleep(5000);
                Debug.Print("Process Lock Exit: {0}", Thread.CurrentThread.ManagedThreadId);
            }
        }
    }
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Diagnostics;


namespace ConsoleApplication
{
    class Program
    {
        private static Info info = new Info();

        static void Main(string[] args)
        {
            Thread[] t1 = new Thread[5];
            for (int i = 0; i < 5; i++)
            {
                t1[i] = new Thread(info.DoWork);
            }

            Thread[] t2 = new Thread[5];
            for (int i = 0; i < 5; i++)
            {
                t2[i] = new Thread(info.Process);
            }

            for (int i = 0; i < 5; i++)
            {
                t1[i].Start();
                t2[i].Start();
            }

            Console.ReadKey();
        }
    }

    class Info
    {
        public object SynObject = new object();

        public void DoWork()
        {
            Debug.Print("DoWork Lock Reached: {0}", Thread.CurrentThread.ManagedThreadId);
            lock (this.SynObject)
            {
                Debug.Print("Thread Lock Enter: {0}", Thread.CurrentThread.ManagedThreadId);
                Thread.Sleep(5000);
                Debug.Print("Thread Lock Exit: {0}", Thread.CurrentThread.ManagedThreadId);
            }
        }

        public void Process()
        {
            Debug.Print("Process Lock Reached: {0}", Thread.CurrentThread.ManagedThreadId);
            lock (this.SynObject)
            {
                Debug.Print("Process Lock Enter: {0}", Thread.CurrentThread.ManagedThreadId);
                Thread.Sleep(5000);
                Debug.Print("Process Lock Exit: {0}", Thread.CurrentThread.ManagedThreadId);
            }
        }
    }
}

Execution will procede something like this

Process Lock Reached: 15
Process Lock Enter: 15
DoWork Lock Reached: 12
Process Lock Reached: 17
DoWork Lock Reached: 11
DoWork Lock Reached: 10
DoWork Lock Reached: 13
DoWork Lock Reached: 9
Process Lock Reached: 18
Process Lock Reached: 14
Process Lock Reached: 16
Process Lock Exit: 15
Thread Lock Enter: 9
Thread Lock Exit: 9
Process Lock Enter: 14
Process Lock Exit: 14
Thread Lock Enter: 10
Thread Lock Exit: 10
Thread Lock Enter: 11
Thread Lock Exit: 11
Process Lock Enter: 16
Process Lock Exit: 16
Thread Lock Enter: 12
Thread Lock Exit: 12
Process Lock Enter: 17
Process Lock Exit: 17
Thread Lock Enter: 13
Thread Lock Exit: 13
Process Lock Enter: 18
Process Lock Exit: 18

As you ca see the process of reach lock is different that lock enter.