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: 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
    

