deadlock prevention solution

[Gytis Jakutonis]

I'm considering to add the following deadlock(A holds lock on 1 and waits for a lock on 2, while B holds lock on 2 and waits for a lock on 1) prevention logic:
in lock() parse all locks for this client and throw exception if lock with higher record number then the specified one is detected
This checking ensures, that locks are gained in ascending order, so no deadlock as described at the begining can occur. I'm just not sure about that locks parsing, because all locks needs to be checked and this may lead to performance downgrade. Any comments? Thanks.

[Philippe Maquet]

Hi Gytis,
Deadlock detection/prevention... a hard topic!
Look at this thread, where nobody agrees, including two past and two current moderators of this forum.
I still believe that deadlock detection and/or prevention is desirable (along with George at the end of this thread, who BTW got a score of 100%.
In this discussion, we talked about multiple ways of handling the deadlock issue.
You suggest to enforce clients of the data layer to claim locks in ascending order, and it's a defendable position. Another approach is to take into account the fact that any lock claimer cannot enter in deadlock with anyone but a thread *waiting* for a lock and which owns another lock already. In other words, if you know "who" owns what and "who" is waiting, it's quite easy to *detect* a deadlock situation (hence to break it), without even restrict the system to serve locks in any order.
If you're interested, I suggest you to read a few threads on the topic, and/or think some more about the issue by yourself. Anyway, I'm willing to discuss it further with you.
Regards,
Phil.

[Gytis Jakutonis]

Hi Philippe,
I've found this post of yours regarding deadlock issue:

1. Ignore the issue - just make sure that the client you write can only lock one record. It's a very acceptable solution IMO, but I would document that a deadlock - at the db level - may occure, while it cannot happen in this application (because users cannot book more than one record at a time).
2. Force the database to reject any lock() requests if the given client attempts to lock a record while it currently owns a lock : at the db level it is a restriction in comparison with what the instructions ask.
3. Stop the possibily of deadlocks by forcing locks to be requested by a client in numerical order. It is a restriction. Nowhere instructions talk us about any required order in lock claiming.
4. Stop the possibility of deadlocks by writing a deadlock detection routine : there is no restriction to the instructions, because the given lock interface may freely be used as exposed (including the grant of multiple locks to the same client), while in the same time deadlocks cannot happen.

Lets try to step over these options.
1. Seems like many developers have used this approache and passed with 100% for locking(correct my if I'm wrong). And this one is he most logical, since assignment states that systems will not be reused in future, so why should we bother with functionality, which will not be used at all(we lock one record at a time)?
2. I do not like this one, since it adds additional restriction and gives no reusability(if we want reusability at all).
3. This is that I was going to implement, but as you've said, it adds additional restriction(yet not so painful as 2 one). But if we supply lock(int[]) and unlock(int[]), which internally would sort records before locking/unlocking them, then this restriction would not be so unreusable, would it?
4. This is that you are suggesting. But it seems quite complicated - we need to track not only lock owners, but also clients waiting for locks and handle them. Too complicated? Also how about this situation: A locked 1 and waits for 2, B locked 2 and waits for 3, C locked 3 and tries to lock 1. I'm not sure if it is possible to implement easy way to detect this deadlock, also on deadlock detection C should be forced to unlock 3 - not so nice from client C point of view. Maybe I'm missing smth here?

[Philippe Maquet]

Hi Gytis,
Thank you to have found that thread of mine that I couldn't find myself . Can you post the link to let me bookmark it? Thank you in advance.
I cannot enter in discussion right now, but I'll reply in detail tonight, Brussels time.
Best regards,
Phil.

[Gytis Jakutonis]

Philippe,
just figured out how can I implement deadlock detection. Just a sketch below:

validateDeadlock(client, record) {
    owner = lockedRecords.get(record);
    ownerConcern = waitingClients(owner);
    if (lockedRecords.get(ownerConcer) == client) {
        deadlock detected;
    } else {
        validateDeadlock(client, ownerConcern);
    }
}

How about this? there is no null checking, int wrapping etc., but the main idea should be clear. And another question - should I throw exception or just return false from lock() (I can do this since it is my lock manager)? Exception seems to be more obvious I guess. Thanks.

[Philippe Maquet]

Hi Gytis,

1. (Ignore the issue) Seems like many developers have used this approache and passed with 100% for locking(correct my if I'm wrong). And this one is he most logical, since assignment states that systems will not be reused in future, so why should we bother with functionality, which will not be used at all(we lock one record at a time)?

I think that many candidates uploaded without having implemented any plan for deadlock prevention/detection. Did they pass with 100% for locking? Probably some of them, but who actually knows? Many people here get a 44/80 score for locking and we still don't know the reason of those bad locking scores (despite our collective numerous efforts ).
Now any deadlock - whatever the cause - obviously is the worst situation that any multithreads application can encounter: the app just "hangs" sometimes and ... rare are the customers who appreciate that.
In her "Questions to Ask Youself" section about locking (Sun Certified Programmer & Developer for Java 2 Study Guide), Kathy Sierra put this one:
"Is there any possibility of a deadlock? Where two or more clients are waiting for each other's locks?". It's clear that she doesn't think that deadlock prevention is out of scope for our assignment.

4. (writing a deadlock detection routine) This is that you are suggesting. But it seems quite complicated - we need to track not only lock owners, but also clients waiting for locks and handle them. Too complicated? Also how about this situation: A locked 1 and waits for 2, B locked 2 and waits for 3, C locked 3 and tries to lock 1. I'm not sure if it is possible to implement easy way to detect this deadlock, also on deadlock detection C should be forced to unlock 3 - not so nice from client C point of view. Maybe I'm missing smth here?

Yes, that's what I'm suggesting and did implement myself. And you're right about deadlocks caused indirectly. This can easily be solved by a recursive algorithm, though.
And BTW, it's just what you found out by yourself as proves the pseudocode you posted just above.
I'm not sure to correctly interpret your pseudocode, so here is mine:

    void checkDeadLock(waitingThread, claimingThread)
        waitingForRec = the_record_waitingThread_is_supposed_to_wait_for
        // if waitingThread is really waiting 
        if waitingForRec_is_not_null then
            if waitingForRec_is_owned_by_claimingThread then 
                // dealock situation
                unlock_waitingForRec // (the blocking lock)
                notify_as_usual
                throw a DeadLockException
            else 
                // check further (recursively) in the blocking chain...
                checkDeadLock(waitingForRec.ownerThread, claimingThread)

Best regards,
Phil.

[Gytis Jakutonis]

Hi Philippe,
seems like your pseudo solution is similar to mine . So I'm going to include it into my locking implementation. BTW, maybe you can give me more hints how to test deadlock detection logic besides that A,B,C locking situation. I can not figure out more complicated one(more clients do not make that situation more complicated since code is recursive ). IMO any attempts to test that logic with many running threads may miss some situations. Any ideas? Thanks.
BTW - that pseudo code came into my mind just after reading in this thread that it took for you only 15 lines of recursive code to check for deadlock. So I've kind of plagiarized from you

[Philippe Maquet]

Hy Gytis,

BTW, maybe you can give me more hints how to test deadlock detection logic besides that A,B,C locking situation. I can not figure out more complicated one(more clients do not make that situation more complicated since code is recursive ). IMO any attempts to test that logic with many running threads may miss some situations. Any ideas? Thanks.

Other cases are not more complex than your A-B-C example, they are just "deeper" cases. That's where recursion comes to help. To be honest (but I wrote it here multiple times), I owe Andrew the half of my final recursive algorithm: he pointed out a flaw in my first implementation, and I did correct it. Andrew, if you read me, thanks again.

BTW - that pseudo code came into my mind just after reading in this thread that it took for you only 15 lines of recursive code to check for deadlock. So I've kind of plagiarized from you

Hey, you better know my posts than I do! Thanks for the link.
Regards,
Phil.
[ April 27, 2004: Message edited by: Philippe Maquet ]

[Gytis Jakutonis]

Hi Philippe,
just finished to implement that deadlock detection. 43 lines with javadocs, comments and empty lines . And yet another issue arised - should I check for deadlock at the begining of lock() method before wait() loop or in wait() loop itself:

  
validate_deadlock
while(true)
    if (record_locked) wait else break;
or
while(true)
    if (record_locked) validate_deadlock;wait else break;

he second solution is 100% safe, but adds additional validation, which IMO may be unnecessary. Currently I've found only one case then it is usefull - then client spawns multiple treads. With multiple threads it is possible for deadlock to occur while client is in wait() loop. So should I be very cautios or take bet on performance? Thanks(hope you enjoy this quite interesting post as I am).

[Philippe Maquet]

Hi Gytis,
My own deadlock detection happens *before* the claimed lock is granted, but *within* the same synchronized block (and this is mandatory I think).

hope you enjoy this quite interesting post as I am

Of course, I do!
Regards,
Phil.