2

This is a mock bank database problem involving deadlock. I already have what I think is the answer, but I'm curious if this is a good solution. The question posed is the following:

How do you prevent deadlock in the following code?:

void transaction(Account from, Account to, double amount)
{
    Semaphore lock1, lock2;
    lock1 = getLock(from);
    lock2 = getLock(to);

    wait(lock1);
       wait(lock2);

          withdraw(from, amount);
          deposit(to, amount);

       signal(lock2);
    signal(lock1);
 }

The way this can become deadlocked is via two threads (or processes?) calling the transaction() method at the same time with opposing accounts, i.e.:

transaction(savings, checking, 1); in thread 1 and

transaction(checking, savings, 2); in thread 2.

From my poor understanding, I think what is going on and why it is getting deadlocked is because the lock ordering is not obeyed since both threads are trying to get a lock (from each other?).

My quick and dirty solution would be to move the locks outside of the function transaction() to where it would look like this when called:

 //somewhere in main
    Semaphore lock1, lock2;
    lock1 = getLock(from);
    lock2 = getLock(to);

    wait(lock1);
       wait(lock2);

       transaction(checking, savings, 2);

       signal(lock2);
    signal(lock1);
    //.....

with transaction looking like this:

void transaction(Account from, Account to, double amount)
{
   withdraw(from, amount);
   deposit(to, amount);
}

That way they can never be executed at the same time, since transaction is technically the critical section. If this were a java program, could you also use monitors by putting the word synchronized after void in the function declaration? Would that work? That seems like a smarter way to do it.

I also may not be understanding this at all, so feel free to school me, especially if my explanations are not accurate. Thanks.

4

3 回答 3

5

I think what is going on and why it is getting deadlocked is because the lock ordering is not obeyed since both threads are trying to get a lock

The problem here is as you mention that one thread like do:

wait(fromLock);
   wait(toLock);

while another might do:

wait(toLock);
   wait(fromLock);

which might cause deadlock.

What you need to do is insure that they always lock in the same order. You could use the id of the account somehow to figure out the order of the locks:

if (from.id < to.id) {
   wait(fromLock)
     wait(toLock)
       transaction(checking, savings, 2);
     signal(toLock);
   signal(fromLock);
} else {
   wait(toLock)
     wait(FromLock)
       transaction(checking, savings, 2);
     signal(FromLock);
   signal(toLock);
}

I believe that will resolve any deadlocks. You might also want to put a check for the from and to being the same entity.

于 2012-04-09T16:23:58.223 回答
2

Separating this critical section into two sections:

void transaction(Account from, Account to, double amount)
{
    Semaphore lock1, lock2;
    lock1 = getLock(from);
    lock2 = getLock(to);

    wait(lock1);
          withdraw(from, amount);
    signal(lock1);


    wait(lock2);      
          deposit(to, amount);
    signal(lock2);
}

will be the best solution in the real world, because separating this critical section doesn't lead to any unwanted state between them (that is, there will never be a situation, where there is more money withdrawn, than it is possible).

The simple solution to leave the critical section in one piece, is to ensure that lock order is the same in all transactions. In this case you can sort the locks and choose the smaller one for locking first.

For more detailed information about deadlock preventing in these situations see my question - Multiple mutex locking strategies and why libraries don't use address comparison

于 2012-04-09T16:21:01.363 回答
0

No transaction should ever hold on to one lock while waiting for another. If it cannot obtain one of the locks that it needs, then it should release all the ones that it has acquired.

于 2012-04-09T16:42:55.390 回答