class PriorityLock(object):

     def __init__(self):
         self._lock = threading.Lock()
         self._waiter_queue = []
         self._queue_lock = threading.Lock()

     def acquire(self, importance=0):
         this_thread = threading.currentThread()

         # Add this thread to the queue
         with self._queue_lock:
             self._waiter_queue.append((importance, this_thread))
             self._waiter_queue.sort(reverse=True, key=lambda pair:
pair[0]) # Move the most important to the start.

         # Acquire and retain the lock when this thread is at the start
of the queue.
         while True:
             self._lock.acquire()

             with self._queue_lock:
                 if self._waiter_queue[0][1] == this_thread: # We win.
                     del self._waiter_queue[0] # Not waiting anymore.
                     return # Return with lock acquired.

             self._lock.release() # We are not most important: release
and retry.
             time.sleep(0.01) # Give the other threads a chance.

import threading
from Queue import PriorityQueue, Empty

class PriorityLock(object):

    def __init__(self):
        self._is_available = True
        self._mutex = threading.Lock()
        self._waiter_queue = PriorityQueue()

    def acquire(self, priority=0):
        self._mutex.acquire()
        # First, just check the lock.
        if self._is_available:
            self._is_available = False
            self._mutex.release()
            return True
        condition = threading.Condition()
        condition.acquire()
        self._waiter_queue.put((priority, condition))
        self._mutex.release()
        condition.wait()
        condition.release()
        return True

    def release(self):
        self._mutex.acquire()
        # Notify the next thread in line, if any.
        try:
            _, condition = self._waiter_queue.get_nowait()
        except Empty:
            self._is_available = True
        else:
            condition.acquire()
            condition.notify()
            condition.release()
        self._mutex.release()

def test():
    import random, time

    def thread(lock, priority):
        lock.acquire(priority)
        print("Thread %d running" % priority)
        time.sleep(1)
        lock.release()
    lock = PriorityLock()
    threads = [threading.Thread(target=thread, args=(lock, x)) for x
in range(10)]
    random.shuffle(threads)
    for thread in threads:
        thread.start()
    for thread in threads:
        thread.join()

if __name__ == "__main__":
    test()

Output:

Thread 9 running
Thread 0 running
Thread 1 running
Thread 2 running
Thread 3 running
Thread 4 running
Thread 5 running
Thread 6 running
Thread 7 running
Thread 8 running

Note that with the PriorityQueue, lower priority values are retrieved
first.  Thread 9 ran first just by virtue of being first to the gate,
and after that you can see that everything went in order.

The PriorityQueue is also probably unnecessary, since it's always
accessed with the mutex held.  A heapq would be fine.

import threading
import Queue

class PriorityLock(object):

    def __init__(self):
        self._is_available = True
        self._mutex = threading.Lock()
        self._waiter_queue = Queue.PriorityQueue()

    def acquire(self, priority=0):
        self._mutex.acquire()
        # First, just check the lock.
        if self._is_available:
            self._is_available = False
            self._mutex.release()
            return True
        event = threading.Event()
        self._waiter_queue.put((priority, event))
        self._mutex.release()
        event.wait()
        # When the event is triggered, we have the lock.
        return True