How Do I Queue My Python Locks?

Question

Is there a way to make python locks queued? I have been assuming thus far in my code that threading.lock operates on a queue. It looks like it just gives the lock to a random locker. This is bad for me, because the program (game) I'm working is highly dependent on getting messages in the right order. Are there queued locks in python? If so, how much will I lose on processing time?

Answer 1

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, collections

class 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 sleep
if 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 run
for 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:

BACDEFGHIJKLMNOPQRSTUVWXYZ
ABCDEFGHIJKLMNOPQRSUVWXYZT
ABCEDFGHIJKLMNOPQRSTUVWXYZ

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

ABCDEFGHIJKLMNOPQRSTUVWXYZ