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 am interested in research that detects and recover from deadlocks. In other words the system is able to recover from deadlock faults. I'm interested in shared memory multicore processors. Uptill now I have only seen research for distributed systems. Can anyone guide me on this.

share|improve this question

migrated from stackoverflow.com Sep 16 '11 at 10:19

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

1  
If an algorithmic scheme allows by some trick to recover when a deadlock occurs, by definition such a situation must be detectable beforehand and can thus entirely avoided. Or said otherwise, if you have an algorithm that potentially goes into deadlock, change your design. –  Jens Gustedt Sep 16 '11 at 6:16
    
Jens, I am talking about a system which detects and recover from deadlocks at runtime, in other words a fault tolerant system. –  MetallicPriest Sep 16 '11 at 6:19
1  
this is just wishful thinking, stop writing code that deadlocks is the real solution –  David Heffernan Sep 16 '11 at 6:36
1  
@David Heffernan: Not necessarily. I've heard of a few cases of fault-tolerant software being able to recover from dead-locks. But either way, it's very difficult and would probably make a decent Masters or Ph.D thesis. –  Mysticial Sep 16 '11 at 6:41
1  
Deadlocks and their prevention/avoidance/recovery used to be mandatory topics in the mandatory undergraduate operating systems class. Indeed, they were among the most important topics in that class. Dekker's Algorithm, semaphores, monitors, all that stuff. –  John R. Strohm Jan 6 '12 at 17:12

5 Answers 5

I'm not sure what do you mean by recover, because since you're in a deadlock - you're obviously in a state where two threads depend on each other to complete their current tasks. So the recovery would be for one of them (or both...) not to complete the task.

In many cases, especially in embedded event-driven systems the detection is done through hardware watchdog that reboots the system. This can be considered as a recovery mechanism.

You can of course be less rigorous and instead of rebooting the system, shut down one of the offending threads (or all of them) and restart them, making sure that the deadlock situation can be avoided in the future (purging the bad input for example).

Or you can just unlock the blocking call and let the threads run with (potentially) corrupt data. Again, depends on your system and the reasons for deadlock.

Bottom line - watchdog (hardware, or software) is the solution, but if you're using the software version - you need to make sure that it itself is never locked out (i.e.: run on a dedicated CPU for example).

Ah, and the best of all is of course not to get into a deadlock situation entirely. You can verify your code using model checking or simulations, but it is of course easier said then done, even if you verified the model, you might still have bugs in the actual code implementation....

share|improve this answer

The best way to recover from a deadlock condition is to never get into it in the first place.

Techniques such as Tony Hoare's Communicating sequential processes give you the ability to formally reason about your system, detect the potential for deadlock and design it out of your system. I would highly recommend looking into some of the work done on CSP over the years to see if these techniques could be incorporated into your systems.

share|improve this answer

One example of deadlock avoidance is the use of reader-writer locks. The basic pattern is that if you have one lock (the reader) and try to acquire the other (writer) but can't, then you have to abandon and retry your entire operation.

This could in principle be used as a deadlock recovery mechanism - in a classic lock inversion situation, where two threads each hold a lock that the other one wants, then one or both could back out to the point where they acquired the first lock and retry (not both at the same time, or they'll just lock-invert again!). But this is limited as a means of fault tolerance, since it requires co-operation from the threads. In a bad case, each thread might have put some data structure into an inconsistent state that it doesn't know how to back out of, only how to complete. So the fault is un-recoverable. In many cases it's harder to avoid that than it is just to avoid lock inversion.

Those distributed systems you've seen research for, might have the advantage that if a set of nodes gets into an unfortunate deadlocked state, they can all just be shot dead and their contributions ignored. To do that in the bad case I describe above, you'd need some form of transactional memory, which is difficult (and actively researched). But of course you can always write your multi-core code as if it were distributed code (share nothing between threads), then use the techniques for distributed code.

Detecting a locking inversion for mutexes is trivial in principle, since you can draw a directed graph of each thread's dependencies on other threads (A depends on B if B holds a lock that A is waiting on) and check for cycles. Detecting deadlock on semaphores or condition variables is impossible unless you can do enough static analysis to determine which thread is "supposed" to post each semaphore that another thread is waiting on, or supposed to make true a condition that another thread needs to be true before continuing.

share|improve this answer

I'd take a look into Real-Time Systems and Programming Languages by Burns and Wellings. It discusses ways to prevent deadlocks in real time and does a good job with citing papers.

I don't have to book with me at work, but glancing at the ToC you have:

     4.7   Multiprocessor and distributed systems
     5.10  Shared memory multiprocessors
    11.14  Multiprocessor scheduling
share|improve this answer

I know in database systems (where all locks are held in one place and can be analyzed), the common practice is to make one thread the "deadlock victim" and kill it, thereby releasing the lock. This could be complicated in an operating system environment, since a single thread/process could have several locks on disparate parts of the system, so picking a deadlock victim could require some significant introspection and analysis. Also, retrying a failed transaction due to a deadlock is a pretty standard database idiom, but not so common in application programming.

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.