You’re writing a multithreaded program where threads need to acquire more than onelock at a time while avoiding deadlock.
In multithreaded programs, a common source of deadlock is due to threads that attemptto acquire multiple locks at once. For instance, if a thread acquires the first lock, butthen blocks trying to acquire the second lock, that thread can potentially block theprogress of other threads and make the program freeze.One solution to deadlock avoidance is to assign each lock in the program a uniquenumber, and to enforce an ordering rule that only allows multiple locks to be acquiredin ascending order. This is surprisingly easy to implement using a context manager asfollows:
import threadingfrom contextlib import contextmanager
@contextmanagerdef acquire(*locks):
Sort locks by object identifierlocks = sorted(locks, key=lambda x: id(x))
Make sure lock order of previously acquired locks is not violatedacquired = getattr(_local,'acquired',[])if acquired and max(id(lock) for lock in acquired) >= id(locks[0]):
raise RuntimeError(‘Lock Order Violation')
Acquire all of the locksacquired.extend(locks)_local.acquired = acquired
try:for lock in locks:lock.acquire()> yield
finally:> # Release locks in reverse order of acquisitionfor lock in reversed(locks):
lock.release()
del acquired[-len(locks):]
To use this context manager, you simply allocate lock objects in the normal way, but usethe acquire() function whenever you want to work with one or more locks. Forexample:
import threadingx_lock = threading.Lock()y_lock = threading.Lock()
def thread_1():while True:with acquire(x_lock, y_lock):print(‘Thread-1')def thread_2():while True:with acquire(y_lock, x_lock):print(‘Thread-2')
t1 = threading.Thread(target=thread_1)t1.daemon = Truet1.start()
t2 = threading.Thread(target=thread_2)t2.daemon = Truet2.start()
If you run this program, you’ll find that it happily runs forever without deadlock—eventhough the acquisition of locks is specified in a different order in each function.The key to this recipe lies in the first statement that sorts the locks according to objectidentifier. By sorting the locks, they always get acquired in a consistent order regardlessof how the user might have provided them to acquire().The solution uses thread-local storage to solve a subtle problem with detecting potentialdeadlock if multiple acquire() operations are nested. For example, suppose you wrotethe code like this:
import threadingx_lock = threading.Lock()y_lock = threading.Lock()
def thread_1():
while True:with acquire(x_lock):with acquire(y_lock):print(‘Thread-1')
def thread_2():while True:with acquire(y_lock):with acquire(x_lock):print(‘Thread-2')
t1 = threading.Thread(target=thread_1)t1.daemon = Truet1.start()
t2 = threading.Thread(target=thread_2)t2.daemon = Truet2.start()
If you run this version of the program, one of the threads will crash with an exceptionsuch as this:
Exception in thread Thread-1:Traceback (most recent call last):
File “/usr/local/lib/python3.3/threading.py”, line 639, in _bootstrap_innerself.run()File “/usr/local/lib/python3.3/threading.py”, line 596, in runself._target(*self._args, **self._kwargs)File “deadlock.py”, line 49, in thread_1with acquire(y_lock):File “/usr/local/lib/python3.3/contextlib.py”, line 48, in enterreturn next(self.gen)File “deadlock.py”, line 15, in acquireraise RuntimeError(“Lock Order Violation”)
RuntimeError: Lock Order Violation>>>
This crash is caused by the fact that each thread remembers the locks it has alreadyacquired. The acquire() function checks the list of previously acquired locks and en‐forces the ordering constraint that previously acquired locks must have an object IDthat is less than the new locks being acquired.
The issue of deadlock is a well-known problem with programs involving threads (aswell as a common subject in textbooks on operating systems). As a rule of thumb, aslong as you can ensure that threads can hold only one lock at a time, your program willbe deadlock free. However, once multiple locks are being acquired at the same time, allbets are off.
Detecting and recovering from deadlock is an extremely tricky problem with few elegantsolutions. For example, a common deadlock detection and recovery scheme involvesthe use of a watchdog timer. As threads run, they periodically reset the timer, and aslong as everything is running smoothly, all is well. However, if the program deadlocks,the watchdog timer will eventually expire. At that point, the program “recovers” bykilling and then restarting itself.Deadlock avoidance is a different strategy where locking operations are carried out ina manner that simply does not allow the program to enter a deadlocked state. Thesolution in which locks are always acquired in strict order of ascending object ID canbe mathematically proven to avoid deadlock, although the proof is left as an exercise tothe reader (the gist of it is that by acquiring locks in a purely increasing order, you can’tget cyclic locking dependencies, which are a necessary condition for deadlock to occur).As a final example, a classic thread deadlock problem is the so-called “dining philoso‐pher’s problem.” In this problem, five philosophers sit around a table on which thereare five bowls of rice and five chopsticks. Each philosopher represents an independentthread and each chopstick represents a lock. In the problem, philosophers either sit andthink or they eat rice. However, in order to eat rice, a philosopher needs two chopsticks.Unfortunately, if all of the philosophers reach over and grab the chopstick to their left,they’ll all just sit there with one stick and eventually starve to death. It’s a gruesomescene.Using the solution, here is a simple deadlock free implementation of the dining philos‐opher’s problem:
import threading
while True:with acquire(left,right):print(threading.currentThread(), ‘eating')
t = threading.Thread(target=philosopher,args=(chopsticks[n],chopsticks[(n+1) % NSTICKS]))> t.start()
Last, but not least, it should be noted that in order to avoid deadlock, all locking oper‐ations must be carried out using our acquire() function. If some fragment of codedecided to acquire a lock directly, then the deadlock avoidance algorithm wouldn’t work.