Jan 01 2008
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.
Popularity: 11% [?]
[...] you’re dealing with concurrency problems in Java (and who isn’t?), check out JConch. I just released the 0.2 version, and there’s some useful [...]
The best you can do in Java is break your problem down into itty bitty, well-known little steps. Define an entire universe that is the one step — basically, make it its own process — and then throw the result out onto some kind of queue.
Anything else and you’re probably toast in a wonderfully non-obvious way.
While I agree with everything in the body, I fail to see how you get from that to: “the mainstream concurrency model is broken”. I don’t see how concurrency being hard leads to the model of it (and how we choose to solve its problems) is completely broken.
wheatie: Concurrency is not hard. The mainstream model of it is, that’s what he’s pointing out. Memory management isn’t hard either, but the old mainstream method of dealing with it (individual programmers having to do it all by hand) was hard. So people moved on to better things. Even back in the days of C, smart people were writing pool allocators and using them, while “average” programmers were mallocing and freeing willy-nilly.
Leaving it up to every programmer to impliment threading manually over and over again is dumb. We’ll move past that too.
Joe pretty much hit the nail on the head. It’s about correctness. And it’s also about effort. You can write a complicated program without garbage collection, but it’s a hell of a lot harder. And it’s even more difficult to get right, to have a program that doesn’t have memory leaks, or dangling pointers. Fast. Right. Easy. I want all three. The current model for threading is, in effect, saying “pick one”. This wouldn’t be so bad if that was just the way things were, and you couldn’t do any better. But we can do better.
[...] is broke. The only good news about all of this is that it gives lots of fodder for bloggers to come in and constructively gripe…although I suppose that statement depends on your definition of “good [...]