Does Lock() Guarantee Acquired in Order Requested

Does lock() guarantee acquired in order requested?

IIRC, it's highly likely to be in that order, but it's not guaranteed. I believe there are at least theoretically cases where a thread will be woken spuriously, note that it still doesn't have the lock, and go to the back of the queue. It's possible that's only for Wait/Notify, but I have a sneaking suspicion it's for locking as well.

I definitely wouldn't rely on it - if you need things to occur in a sequence, build up a Queue<T> or something similar.

EDIT: I've just found this within Joe Duffy's Concurrent Programming on Windows which basically agrees:

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.

The "roughly-FIFO" bit is what I was thinking of before, and the "sneaky thread" bit is further evidence that you shouldn't make assumptions about FIFO ordering.

Do mutexes guarantee ordering of acquisition? Unlocking thread takes it again while others are still waiting

Known problem. C++ mutexes are thin layer on top of OS-provided mutexes, and OS-provided mutexes are often not fair. They do not care for FIFO.

The other side of the same coin is that threads are usually not pre-empted until they run out of their time slice. As a result, thread A in this scenario was likely to continue to be executed, and got the mutex right away because of that.

Does Python's asyncio lock.acquire maintain order?

When we talk about how something works it's important to distinguish guarantee expressed in specification and side-effect of implementation. First one shouldn't be changed (at least, within major version), second one can be changed any time in the future.

Martijn's answer clearly shows that current implementation preserves order. What about guarantee for future?

Official documentation for Python 3.6 provides guarantee:

only one coroutine proceeds when a release() call resets the state to unlocked; first coroutine which is blocked in acquire() is being processed.

Interesting thing is that neither documentation for Python 3.7 nor documentation for Python 3.8 dev have this line, not sure if it's intentional though. However class's docstring on github has guarantee.

It's also worth mentioning that threading.Lock (prototype for asyncio's lock) explicitly says that order is undefined:

only one thread proceeds when a release() call resets the state to unlocked; which one of the waiting threads proceeds is not defined, and may vary across implementations.

---

Long story short, right now only class's docstring promises to maintain order. It's also fair to note that implementation of lock is unlikely to being changed in the nearest future.

Yet imagine however someone will change it (to increase performance, for example). Will docstring be enough to prevent from implementing lock with undefined order? It's up to you to decide.

If your code critically depends on preserving order and expected to have long life cycle nothing bad if you create your own lock (sub)class which will explicitly guarantee order (OrderedLock or something). You may just vendorize current implementation.

If situation is simpler you may choose not to bother with it and use current implementation.

Does a lock around a write guarantee fresh read in another thread? (.Net, memory model)

No, since the read does not have the explicit memory barrier, it is not "guaranteed" to see the new value.

You can use a ReaderWriterLockSlim to insure that a) the writes lock each other and b) the reads always pickup the new value.

private readonly ReaderWriterLockSlim _myFieldLock = new ReaderWriterLockSlim();
private long _myField;
public long MyProperty
{
    get 
    {
        _myFieldLock.EnterReadLock();
        try
        {
            return _myField;
        }
        finally
        {
            _myFieldLock.ExitReadLock();
        }
    }
    set
    {
        _myFieldLock.EnterWriteLock();
        try
        {
            _myField = value;
        }
        finally
        {
            _myFieldLock.ExitWriteLock();
        }
    }
}

Understanding multi-threading and locks in Python (concept and example)

1. It's also quite common to use global variables for locks. It depends on what the lock is protecting.
2. True, although somewhat meaningless. Any function can use a lock, not just the function that's the target of a thread.
3. If you mean there's no direct link between a lock and the data it protects, that's true. But you can define a data structure that contains a value that needs protecting and a reference to its lock.
4. True. Although as I say in 3, you can define a data structure that packages the data and lock. You could make this a class and have the class methods automatically acquire the lock as needed.
5. Correct. But see 4 for how you can automate this.
6. Correct.
7. Correct.
8. Correct.
9. Correct if it's not a global lock.
10. Partially correct. You should also often acquire the lock if you're merely reading the variable. If reading the object is not atomic (e.g. it's a list and you're reading multiple elements, or you read the same scalar object variable times and expect it to be stable), you need to prevent another thread from modifying it while you're reading.
11. Correct.
12. Correct.
13. Correct. This is an example of what I described above in 3 and 4.
14. Correct. Which is why the design in 13 is often better.
15. This is tricky, because the granularity of the locking needs to reflect all the objects that need to be protected. Your class only protects the assignment of that one variable -- it will release the lock before all the other steps associated with the caller-provided lock have been completed.

Is there a synchronization class that guarantee FIFO order in C#?

You'll need to write your own class to do this, I found this example (pasted because it looks as though the site's domain has lapsed):

using System.Threading;

public sealed class QueuedLock
{
    private object innerLock;
    private volatile int ticketsCount = 0;
    private volatile int ticketToRide = 1;

    public QueuedLock()
    {
        innerLock = new Object();
    }

    public void Enter()
    {
        int myTicket = Interlocked.Increment(ref ticketsCount);
        Monitor.Enter(innerLock);
        while (true)
        {

            if (myTicket == ticketToRide)
            {
                return;
            }
            else
            {
                Monitor.Wait(innerLock);
            }
        }
    }

    public void Exit()
    {
        Interlocked.Increment(ref ticketToRide);
        Monitor.PulseAll(innerLock);
        Monitor.Exit(innerLock);
    }
}

Example of usage:

QueuedLock queuedLock = new QueuedLock();

try
{
   queuedLock.Enter();
   // here code which needs to be synchronized
   // in correct order
}
finally
{
    queuedLock.Exit();
}

Source via archive.org

---

Related Topics