Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

migrated from stackoverflow.com Mar 12 '12 at 13:00

This question came from our site for professional and enthusiast programmers.

8  
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 '12 at 1:09
1  
What is your definition of "deadlock"? –  user1249 Mar 14 '12 at 7:38
    
What about livelocks? –  Bjarke Freund-Hansen Mar 14 '12 at 14:34

3 Answers 3

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.

share|improve this answer

I don't think you can do this in the general case - detecting deadlocks in a complex system is equivalent to the halting problem so you haven't got a hope of solving it. Deadlock recovery 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 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.

share|improve this answer
4  
+1 for halting problem mention, and pointing out how much worse this solution is than missing an SLA target. –  I82Much Mar 12 '12 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. –  Jon Strayer Mar 12 '12 at 14:32

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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