Why the mainstream concurrency model is broken

Hehe. This guy sounds like me.

Actually, it’s worse than that. Of the four horsemen of the multithreaded apocalypse (deadlocks, race conditions, live locks, and priority inversions), deadlocks are the easiest to detect, and the easiest to solve. You can easily detect them mechanically (as the original poster thought). The algorithm is simple: you form a directed bipartite graph, where every thread and every lock is a node. Thread nodes can only have outgoing edges to lock nodes, and having an edge from a thread to a lock means that thread is waiting on that lock. Locks can only have outgoing edges to thread nodes, and they mean that the lock is owned by a given thread. If this graph has a cycle (which can be checked in O(N) worse-case), then you have a deadlock.

Detecting that you might have a deadlock is easy- what happens is that some locks never get released, and some lockers wait forever. An easy heuristic is that if some attempt to lock a mutex takes “too long”, then start running the deadlock logic defined above looking for deadlocks. Once the deadlock has been detected, the cycle is broken by choosing one edge from a thread to a lock to be removed- that attempted lock fails (throwing a Would_deadlock exception, or whatever). All the code now has to do is clean up properly in the face of an exception, and life goes on.

In fact, if deadlocks were the only problem multithreaded code faced, I’d declare them a solved problem and move on. The other three problems, however, are not nearly so easy to detect, and do not have nearly so nice a way to recover from when they do happen. Of the four, deadlocks are the easy problem to solve.

Related posts:

1. Additional Evidence That Concurrency Is an Increasing Problem
2. Football Is the Model for Anarchocapitalism?
3. Interesting Information: MPR’s Funding Model