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.

Gray
  • 115,027
  • 24
  • 293
  • 354
montag
  • 243
  • 1
  • 3
  • 14

3 Answers3

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.

Gray
  • 115,027
  • 24
  • 293
  • 354
  • I would agree that it is, I just don't know if the professor would be okay with me using the account IDs in that context to determine the solution since we weren't given them. In the real world, however, I don't see why this wouldn't work perfectly. – montag Apr 09 '12 at 21:30
  • Obviously you can use some other unique field that is comparable on the `Account` @montag. But I understand the requirements of the question. Moving the locks inside of the transaction is another solution. – Gray Apr 09 '12 at 21:57
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

Community
  • 1
  • 1
Rafał Rawicki
  • 22,324
  • 5
  • 59
  • 79
  • So you couldn't use the synchronized keyword in Java to ensure that transaction will never be called by two threads at the same time? – montag Apr 09 '12 at 18:26
  • If you will use synchronized with `Account` objects (and you will select these objects before locking, so that they will be locked in order) it should work, but I don't know Java good enough to give you more detailed answer. – Rafał Rawicki Apr 09 '12 at 19:15
  • This is true. I believe you're correct. So basically the only reason this solution works is because no one would ever have to deposit or withdraw funds at the same time, therefore you could put one after the other. I think I understand. Thank you for your help. – montag Apr 09 '12 at 19:24
  • This is surprising. Won't this cause a situation where the total amount of money in the system has decreased? – usr Apr 09 '12 at 19:42
  • Temporarily, yes. But there is no interleave, that leads to permanent decreasing of total amount of money (like there were no locks). – Rafał Rawicki Apr 09 '12 at 19:45
  • you still have some possible problem -> if your server dies after withdraw and before deposit you will have an inconsistence. Of course this is only a problema if this 2 block is not in a single transaction (but if they are, then i think you will have this deadlock problem in anyway that dont guarantee you lock the accounts in some deterministic way) I believe Gray have the current best solution – Plínio Pantaleão Apr 09 '12 at 19:45
  • @PlínioPantaleão this not the problem for concurrency, but persistency. Dealing with server deaths requires, for example, to have some kind of journaling. Any of the solutions presentend here will not survive a hardware error. – Rafał Rawicki Apr 09 '12 at 19:47
  • Yeah, I think server death is beyond the scope of my class, however you make a valid point. If I were coding this into a database, I'd probably get fired for not accounting for that. – montag Apr 09 '12 at 21:32
  • @Rafał Rawicki i'm not worried about surviving a hardware error, but if your hardware fails I expect to let my database in a consistent state. By that I mean everything is on database or nothing is on database. And that is really important – Plínio Pantaleão Apr 10 '12 at 13:20
  • Yes, and I was talking about this specific situation. No solution presented here guarantees that database will be left in consistent state. Hardware **can die inside critical section**, and you cannot prevent this from happening using mutexes :) – Rafał Rawicki Apr 10 '12 at 14:06
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.

Philip Sheard
  • 5,789
  • 5
  • 27
  • 42
  • How should the application be structured, then? How can we avoid taking two locks? – usr Apr 09 '12 at 19:43