Unclear about the explanation in Problem 19.5

[deveshks]

In problem 19.5: Deadlock, there is a code snippet provided and according to the explanation that follows, the code snippet causes a deadlock. But I am unable to see how a deadlock is happening here

The explanation says

Suppose U1 initiates a transfer to U2, and immediately afterwards, U2 initiates a transfer to U1. Since each transfer takes place in a separate thread, it's possible for the first thread to lock U1 and then the second thread to be scheduled in and take the lock U2. The program is now deadlocked--each of the two threads is waiting for the lock held by the other thread.

If U1 and U2 have separate locks, and the two threads only locks U1's and U2's lock in _move, how is there a deadlock being achieved here.

A similar question was asked on stack overflow, but no answer was provided. https://stackoverflow.com/questions/52237227/deadlock-question-19-5-in-elements-of-programming-interviews.

The following might be a deadlock though

def _move(self, acc_to, amount):

     with self._lock:
         time.sleep(random.random())
         with acc_to._lock:
             if amount > self._balance:
                 return False
             acc_to._balance += amount
             self._balance -= amount
             logging.debug('returning True')
             return True

If we have two accounts a1 and a2, and thread t1 transfers from a1 to a2, and thread t2 transfers from a2 to a1, the following might lead to deadlock

1. t1 locks a1 and goes to sleep
2. t2 locks a2 and goes to sleep
3. After they wake up from sleep, t1 locks a2 and t2 locks a1, which will then cause a deadlock since neither a1 nor a2 can be unlocked.

And this deadlock can surely be resolved by the posted solution as follows

def _move(self, acc_to, amount):

    lock1, lock2 = (self._lock, acc_to._lock) if self._id < acc_to._id else (acc_to._lock, self._lock)

    with lock1:
        time.sleep(random.random())
        with lock2:
            if amount > self._balance:
                return False
            acc_to._balance += amount
            self._balance -= amount
            logging.debug('returning True')
            return True

since now t1 and t2 will always lock a1 and a2 in order, if a1's account id is smaller than a2's.

[deveshks]

Hi @tsunghsienlee Could you please look into this issue if possible and clarify the question?

[tsunghsienlee]

Hi @deveshks ,

I think the explanation here could be better, and we would discuss to let you know. My understanding now is that your code without time.sleep(random.random()) shall be good enough to demonstrate the deadlock. However, I think this definitely shall be more clearly written.