Deadlock Solutions: Lock Ordering

Question

This is from a textbook on operating systems. This is not homework, just part of the chapter on deadlocks.

transaction(Account from, Account to, Number amount):
    mutex lock1 = getlock(from)
    mutex lock2 = getlock(to)

    acquire(lock1)
    acquire(lock2)
        withdraw(from, amount)
        deposit(to, amount)
    release(lock2)
    release(lock1)

Deadlock is possible if two threads simultaneously invoke thetransaction() function, transposing different accounts. That is, one thread might invoke

transaction(checkingaccount, savingsaccount, 25)

and another might invoke

transaction(savingsaccount, checkingaccount, 50)

What is a good solution to this problem? One I can think of is to use a witness program that will alert the user that a deadlock has occurred, but there must be a better solution implementable by modifying the code. Any ideas?

Answer 1

You simply need to place a total order on the accounts and always lock the accounts in that order.

You define a < operator on Accounts and then change the beginning like this:

mutex lock1 = getlock(from)
mutex lock2 = getlock(to)
if (from < to)
    mutex lockSwap = lock1
    lock1 = lock2
    lock2 = lockSwap

It doesn't matter what order you choose, it just has to stay the same through the whole program. In C, and other low level languages it is particularly easy to make this kind of < operator because you can just convert the addresses of the objects to integers and do the < on the integers.