How Do I Queue My Python Locks?

I wholly agree with the comments claiming that you're probably thinking about this in an unfruitful way. Locks provide serialization, and aren't at all intended to provide ordering. The bog-standard, easy, and reliable way to enforce an order is to use a Queue.Queue

CPython leaves it up to the operating system to decide in which order locks are acquired. On most systems, that will appear to be more-or-less "random". That cannot be changed.

That said, I'll show a way to implement a "FIFO lock". It's neither hard nor easy - somewhere in between - and you shouldn't use it ;-) I'm afraid only you can answer your "how much will I lose on processing time?" question - we have no idea how heavily you use locks, or how much lock contention your application provokes. You can get a rough feel by studying this code, though.

import threading, collectionsclass QLock:    def __init__(self):        self.lock = threading.Lock()        self.waiters = collections.deque()        self.count = 0    def acquire(self):        self.lock.acquire()        if self.count:            new_lock = threading.Lock()            new_lock.acquire()            self.waiters.append(new_lock)            self.lock.release()            new_lock.acquire()            self.lock.acquire()        self.count += 1        self.lock.release()    def release(self):        with self.lock:            if not self.count:                raise ValueError("lock not acquired")            self.count -= 1            if self.waiters:                self.waiters.popleft().release()    def locked(self):        return self.count > 0

Here's a little test driver, which can be changed in the obvious way to use either this QLock or a threading.Lock:

def work(name):    qlock.acquire()    acqorder.append(name)from time import sleepif 0:    qlock = threading.Lock()else:    qlock = QLock()qlock.acquire()acqorder = []ts = []for name in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":    t = threading.Thread(target=work, args=(name,))    t.start()    ts.append(t)    sleep(0.1) # probably enough time for .acquire() to runfor t in ts:    while not qlock.locked():        sleep(0)  # yield time slice    qlock.release()for t in ts:    t.join()assert qlock.locked()qlock.release()assert not qlock.locked()print "".join(acqorder)

On my box just now, 3 runs using threading.Lock produced this output:

BACDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSUVWXYZTABCEDFGHIJKLMNOPQRSTUVWXYZ

So it's certainly not random, but neither is it wholly predictable. Running it with the QLock instead, the output should always be:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

I stumbled upon this post because I had a similar requirement. Or at least I thought so.

My fear was that if the locks didn't release in FIFO order, thread starvation would be likely to happen, and that would be terrible for my software.

After reading a bit, I dismissed my fears and realized what everyone was saying: if you want this, you're doing it wrong. Also, I was convinced that you can rely on the OS to do its job and not let your thread starve.

To get to that point, I did a bit of digging to understand better how locks worked under Linux. I started by taking a look at the pthreads (Posix Threads) glibc source code and specifications, because I was working in C++ on Linux. I don't know if Python uses pthreads under the hood, but I'm gonna assume it probably is.

I didn't find any specification, on the multiple pthreads references around, relating to the order of unlocks.

What I found is: locks in pthreads on Linux are implemented using a kernel feature called futex.

http://man7.org/linux/man-pages/man2/futex.2.html

http://man7.org/linux/man-pages/man7/futex.7.html

A link on the references of the first of these pages leads you to this PDF:

https://www.kernel.org/doc/ols/2002/ols2002-pages-479-495.pdf

It explains a bit about unlocking strategies, and about how futexes work and are implemented in the Linux kernel, and a lot lot more.

And there I found what I wanted. It explains that futexes are implemented in the kernel in a way such that unlocks are mostly done in FIFO order (to increase fairness). However, that is not guaranteed, and it is possible that one thread might jump the line one in a while. They allow this to not complicate too much the code and allow for the good performance they achieved without losing it due to extreme measures to enforce the FIFO order.

So basically, what you have is:

The POSIX standard doesn't impose any requirement as to the order of locking and unlocking of mutexes. Any implementation is free to do as they want, so if you rely on this order, your code won't be portable (not even between different versions of the same platform).

The Linux implementation of the pthreads library rely on a feature/technique called futex to implement mutexes, and it mostly tries to do a FIFO style unlocking of mutexes, but it is not guaranteed that it will be done in that order.

Yes you could create a FIFO queue using a list of the thread IDs:

FIFO = [5,79,3,2,78,1,9...]

You would try to acquire the lock and if you can't, then push the attempting thread's ID (FIFO.insert(0,threadID)) onto the front of the queue and each time you release the lock, make sure that if a thread wants to acquire the lock it must have the thread ID at the end of the queue (threadID == FIFO[-1]). If the thread does have the thread ID at the end of the queue, then let it acquire the lock and then pop it off (FIFO.pop()). Repeat as necessary.