6

I have read many websites talking about how to avoid and how to design etc. I completely understand those strategies.

My question is based on the following preconditions:

  1. You have a company with 1000's of developers.
  2. There are different teams working on the same product but as modules.
  3. New developers writing new code not knowing the overall system, please consider an Enterprise application.
  4. High available software development where a downtime of 15 mins is considered as an SLA violation.

I could write few more preconditions but I thought these could be strong enough to support my question about why I might need a recovering strategy for a "Deadlock" in a software.

Please note that re-designing the modules whenever we find a deadlock is not realistic.

Now this being said.

Can someone take sometime to provide an input or brainstorm on an idea of how to resolve a deadlock if at all it happens, so that we can report it and move forward, instead of halting completely.

  1. Run a deadlock detector that runs periodically to look for deadlocks in the system.
  2. If a deadlock is detected, notify with an event to resolve the deadlock.
  3. The deadlock event listener will then kick in and act upon the deadlocked threads.
  4. For each thread identify the contention.
  5. Write an intelligent algorithm that could either release the locks and kill the thread or release the locks and re-evaluate the thread.
  6. In step 2 we handle the notification in multiple ways, out of which logging is one of the listener.

I know how to go about steps 1,2,6. Will need help with 3,4 and 5.

I know that Oracle RDBMS already has a deadlock detection and resolution strategy in place, I wonder if they would ever share their strategies in this thread :)

Can't add my comment as an answer so adding it as a comment here.

=================================================================

I completely understand the risk of killing the threads. I was 100% certain that I would get answers like this but I was also hoping that someone would suggest something new. I'll keep the thread open as there is no answer in here that I already do not know, thank you very much for trying though.

5
  • 9
    Your "pre-conditions" imply that you have reasons to care about code quality, but then you state that "re-designing the modules whenever we find a deadlock is not realistic". Well, which is it? Does your software matter, or does it not?
    – ruakh
    Mar 12, 2012 at 1:09
  • 2
    What is your definition of "deadlock"?
    – user1249
    Mar 14, 2012 at 7:38
  • What about livelocks? Mar 14, 2012 at 14:34
  • There are some simple things to look for (theoretically simply, though isn't a easy task): locks that are not reentrant, or a task that held locks had failed and did not cleanly release all locks it held.
    – rwong
    Oct 28, 2015 at 6:13
  • For this question to be answerable, one must first investigate the possible causes of the deadlocks in that system, and try to recreate that by reproducing the deadlock (possibly with repeated trials). (I understand that this question has been abandoned and will not have new activities.)
    – rwong
    Oct 28, 2015 at 6:16

3 Answers 3

20

I don't think you can do this in the general case - detecting arbitrary deadlocks/livelocks in a complex system is equivalent to the halting problem so you haven't got a hope of solving it. Recovery from such situations can also be arbitrarily complex, and it's almost impossible to return the system to a "safe" state. My overall advice would be to fix the underlying architectural issues rather than trying to paper over the problem with some flawed form of automatic deadlock/livelock detection and recovery.

Basically you are trying to solve the wrong problem - the deadlocks aren't the issue, your architecture and development approach is.

By the way, if you are concerned about clients with availability SLAs, then implementing an automated deadlock detection and resolution system is one of the worst things you can do, since this could potentially corrupt your client's data (the reason you have locks in the first place is to stop data getting corrupted by concurrent transactions!).

Think about how the conversation will so: "so let me get this straight - you implemented a deadlock resolution strategy which silently corrupts our data and pretends everything is ok so that you were able to hit your SLA target?" You could be in for a pretty big lawsuit if this happens, a missed SLA is peanuts in comparison....

FWIW, I think that lock-based programming is the wrong approach anyway for complex systems. Ideally you want to make everything stateless, but if you really need mutable state then a software transactional memory based approach is IMHO the right way to handle this. STMs used correctly can't deadlock since they don't require locks. This excellent video presentation describes Clojure's STM system which is an example of what is possible in this space.

8
  • 4
    +1 for halting problem mention, and pointing out how much worse this solution is than missing an SLA target.
    – I82Much
    Mar 12, 2012 at 3:04
  • 2
    He isn't trying to do it in the general case. The problem may be hard or easy in his particular case. Mar 12, 2012 at 14:32
  • 1
    @WW have a look at this paper: cs.utexas.edu/users/gouda/papers/conference/cp58-whole.pdf
    – mikera
    Oct 28, 2015 at 3:14
  • 1
    @Brian We are talking at cross-purposes. I assert that: Given the current state of the JVM, we can determine if it is deadlocked now (via cyclic deadlock graph). I am not asserting that we can take the source code and assert anything about a deadlock eventuating. I agree this is the halting problem. The original question is asking about periodically running deadlock detection, not solving this based on source.
    – WW.
    Oct 28, 2015 at 3:41
  • 1
    @WW: Fair enough. Apparently I made a common mistake, since Wikipedia calls it out explicitly in Deadlock prevention algorithms: Issues Not addressed above
    – Brian
    Oct 28, 2015 at 3:47
4

Given arbitrary code that is deadlocked, there is no safe way to release locks/kill threads and resume processing. Probably your best course is to detect and log deadlocks.

If you impose limitations on the software, such as all memory updates need to use something like clojure's software transactional memory, then it may be possible to avoid deadlocks altogether, or at least recover when they occure. That is how database software can recover from deadlocks, all modifications are happening within a transaction, so if a deadlock is detected, one transaction can be rolled back, and the other can proceed.

Avoiding deadlocks does not have to be that difficult, make sure locks are acquired in order, don't do much work while holding locks, or try to structure your code using actors or SEDA.

1

One option would be to never wait for a lock without a timeout, thus your system will never get stuck.

Another way is custom locks everywhere. Enforce that by static checking. Then:

  • If your lock class(es) register themselves in some DeadlockManager,
  • that same manager knows which locks are held by which thread
  • Threads report at regular interval that they're running properly
  • If a thread fails to report, check what locks are held/waiting by it and other threads.
  • What you could do to resolve this is to have the manager unlock the lock and have the lock throw and exception (DeadLockException). That gives the surrounding code a chance to recover and retry whatever it did.

Note that it is hard to figure out which locks and what order caused the deadlock (A,B), in general.

However, if you do know what locks you will be locking and in what order, the DeadLockManager could check that it's possible. I suppose the locking order could be "reserved" and checked for so that no other thread causes a deadlock.

It will be tricky to do, and maybe impossible to coordinate on a large project, but if you can't change the architecture much, this is one option.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.