Dealing with Deadlocks/Stale Locks

[Reza Rahman]

From reading past posts, it seems a lot of people with really good scores have ignored the deadlock/stale lock issue. On the other hand, I am seeing people who have attempted to deal with deadlocks/stale locks scenarios but still have not received spectacular scores in locking.

This is leading me to the following (extremely confusing) conclusion: Dealing with dealocks/stale locks are not a major factor in scoring.

If this is the case, I would be very happy to ditch the convoluted deadlock coding and significantly simplify my logic/focus on other issues (at least for now).

What do you guys think?

FYI: In a real world app, there is no way I would ignore deadlock/stale lock scenarios. In the end, I might go back to this once I isolate all other issues anyway, provided I am confident locking is fine otherwise. This just might serve as little more than a thought experiment (isn't that the point of the exam anyway?)...

[Andrew Monkhouse]

Hi Reza,

Deadlock handling does not need to be convoluted - the logic for "one client can only lock one record at a time" can be done simply, as can "clients can only lock multiple records if they lock them in numerical order". Allowing infinite locks to be granted in any order to any client can require more complex deadlock detection, but it can still be done cleanly and elegantly.

Regardless, if you feel that deadlock detection is not required, then by all means, leave it out. But make sure you explain why you left it out in your design choices document. I would also recommend you describe why you left it out in the comments near the locking code itself.

I personally don't believe stale lock detection (where you clear locks after a certain amount of time) is allowable according to the comments for the lock method in the provided interface.

Orphaned lock detection (where the client has crashed / disconnected without releasing the lock) is not required for the assignment, however many candidates feel that this is something they would do in real life, so they do it for the assignment. It has lead to some interesting discussions here.

Regards, Andrew

[John Smith]

This is leading me to the following (extremely confusing) conclusion: Dealing with dealocks/stale locks are not a major factor in scoring.

You are confused because you are trying to mix two different things here.

The deadlock is one of those conditions resulting from the sloppy thread programming where Thread1 waits for the monitor on object A before it can release the monitor on object B, while Thread2 waits for the monitor on object B before it can release the monitor on object A. The result is that nothing can move forward. If you have even a slight hint in you code that such a condition may happen in your code, you are guaranteed to fail.

The stale lock is something completely unrelated. In the context of this assignment, it usually refers to a client who was in the middle of booking a record and suddenly disconnected, never releasing a lock on that record. Note that in this circumstance, the worst that could possibly happen is that other client would not be able to book that record, but otherwise everything would be normal. I would venture to say that you requirements say nothing at all about this condition, and it's perfectly fine not to do anything about it in your code. In the real life situation, you would probably handle it by implementing the Unreferenced interface or perhaps by holding your locks in some sort of collection with weak/soft keys so that the locks can be released automatically, but in this assignment, you are taking risks if you opt to implement these bells and whistles. Stay away from 'em. Just release the locks in the traditional finally block and you'll graduate on top of your class. I bet my 98% score on it.
[ May 31, 2005: Message edited by: John Smith ]

[Ken Boyd]

John you are right on target

[Frans Janssen]

Originally posted by John Smith:
in this circumstance, the worst that could possibly happen is that other client would not be able to book that record, but otherwise everything would be normal.

John,

I agree that stale locks and deadlocks are two different things. However, I disagree that stale locks are more innocent than deadlocks. In the example above, the worst thing would not be that clients cannot book the record, the worst thing would be that if a client attempts to lock the record, it will be waiting forever, unless measures are taken to clean up the stale lock.

Frans.

[Reza Rahman]

John, with all due respect, I do know the difference between deadlocks and stale locks (hence the purpose of separating the two)...

So I take it you dealt with deadlocks and not stale locks for your implementation? What logic did you follow for deadlock detection? Was it lock ordering, limiting the number of locks or some other heuristic? Thanks in advance for sharing your thoughts...

My biggest problem with disallowing locks under certain circumstances is that the provided interface does not provide a natural interface for it. For example, what would you do if you detect a lock is about to be attempted out of order? Throw an exception or wait until the order is corrected on its own? As usual, thanks for all the input.

Reza

[Paul Bourdeaux]

Hi Reza,

I cannot speak for John, but in my implementation I did not deal with stale or orphaned locks... although it can be done relatively simply if you are using RMI.

As far as deadlocks... I had no deadlock detection in place. I simply ensured that my code could never result in such a condition (one client can only lock one record at a time). Granted, in a real world application I would certainty introduce some kind of detection on the server side. But then again, there are a lot of things I would do differently in a real world application! As I often say in this forum, I believe that is outside the scope of this assignment.

I did, however, make sure I mentioned both orphaned locks and deadlocks in my choices.txt.
[ June 01, 2005: Message edited by: Paul Bourdeaux ]

[John Smith]

What logic did you follow for deadlock detection?

Well, the first obvious thing is to understand and be comfortable with your own code. Once you do, here is a good test to run:

Start 50 threads each representing a distinct client and have each of them book the same record 1000 times in a row (by decrementing one of its fields). At the end of the run, the field value should be exactly 50000 below the level at the start of the run. This "meta-test" will test for deadlocks, concurrency, thread starvation, race conditions, and all those evils with a fair degree of certainty.

[Reza Rahman]

Paul:

Thanks for your thoughtful response. Not to belabor the issue to the point of inanity, but how did you ensure that each client only held one lock at a time? Did you introduce a wait if you detected that a particular client is about to attempt more than one lock or did you employ some kind of synchronization scheme that stopped this from happening?

Reza

[Reza Rahman]

John,

OK, I understand the need to run concurrency tests and fully plan to do so. Thank you for the advice to comfortable with my code (FYI, I am but tend not to take things for granted). However, do you really belive this is an effective way to formulate an effective deadlock detection technique? As I mentioned, there are two popular choices: lock ordering and limiting the client to one lock. Which one would be your preference and why?

Reza
[ June 03, 2005: Message edited by: Reza Rahman ]

[John Smith]

As I mentioned, there are two popular choices: lock ordering and limiting the client to one lock. Which one would be your preference and why?

In my implementation, the client can only lock one record at a time (the book() method would simply block until the record is booked). Thus, the deadlock you are talking about would not be a possibility. Now the deadlcoks that I am talking about are the ones occuring because of bad thread programming. Those need to be addressed heuristically as well as empirically (such as running a test which creates many threads booking the same record for some period of time).

[Reza Rahman]

Actually, upon further analysis, I am convinced that this requirement is out of scope for my implementation since the lock and unlock methods are never invoked by the client and are hidden behind the network abstraction layer.

My network server clients will invoke RMI methods that look like the following for update/delete:

    lock;
    udate/delete;
    unlock; // In a finally block and invoked only if lock was placed.

Thanks to the way RMI threads are handled (an unused thread from the thread pool is assigned for each invocation of these methods), deadlocks will never happen.

Hope this helps the rest of the people implementing thin clients...