Deadlock ... and How To Avoid It

In an earlier article, four untestable dynamic problems were discussed:

• race conditions
• deadlock
• livelock
• thread starvation

There is no panacea to solve these problems. However, there are quite usable steps that can be taken to deal with such situations.

Race Conditions

Although this article is about deadlocks, you wouldn’t have any if race conditions (instability due to concurrent threads changing shared data without sufficient protective locking) were not a concern. If shared memory is to be written concurrently by more than one thread, or written and read at the same time, corrupted values often result. Memory locks are the traditional solution (there are other appproaches too); race conditions occur when there is too little locking. But locking can seriously impair performance and may lead to deadlocks.

Asynchrony - a fool's hope?

A popular trend in concurrency is to avoid locking by a so-called ‘asynchronous’ coding style - all reactions to events occur in callbacks. This is popular not least because it seems easy - although purely callback-based code can become hard to understand quite quickly.

But there is a hidden problem: the callbacks essentially have to be queued in some way. If there is a design error, the queues may be filled faster than they are consumed leading to memory exhaustion. This is mostly a problem suffered by the actor model.

The Welch-Justo-Willcock Theorems

High-Level Paradigms for Deadlock-Free High-Performance Systems

Client-Server Theorem

Any network of client-server connections that is acyclic with respect to the client-server ordering is deadlock/livelock free.

Client-Server Closure

Any collection of processes that communicate only using the client-server paradigm and has an acyclic topology (with respect to client-server relationships) itself communicates with its environment by the client-server paradigm.

I/O-PAR Theorem

Any network of I/O-PAR normal form processes is deadlock-free.

I/O-PAR/SEQ Theorem

Any I/O-SPnet is deadlock/livelock-free.

comments powered by Disqus