Implement run_with_locks(locks, fn):
locksis a list ofthreading.Lockobjects. Acquire all of them, callfn()while holding them, release them all, and return whatfn()returned.- Many threads call it at once with overlapping locks listed in different orders. It must never deadlock.
- If
fn()raises, release every lock and let the exception propagate. - The same lock may appear more than once in
locks; it must still be acquired only once (aLockcan't be acquired twice by the same thread). An empty list just callsfn().
a, b = threading.Lock(), threading.Lock()
# thread 1: run_with_locks([a, b], transfer)
# thread 2: run_with_locks([b, a], transfer)
# Taking them in the order given: 1 holds a and waits for b, 2 holds b and waits for a -> stuck forever.
run_with_locks([a, a], lambda: 7) # 7
Constraints: up to 10 locks per call. Don't sleep, busy-wait or use one global lock for everything.
Show hint
A deadlock needs a cycle of waiting, so break "circular wait": remove duplicates and acquire the locks in one global order that every thread agrees on, such as sorted(set(locks), key=id).