Nice analysis and demonstration that even relaxing concurrency requirements is not as easy as it looks.
Interestingly, when trying to reason about and verify correct synchronisation of data structures, I immediately start drawing boxes with lots of arrows for pointers (just like those in the article) even though I don't normally need any visual aids to design my code. Somehow, holding a complex data structure in my head is no problem, but as soon as I try to think about concurrent access to something as simple as a linked list, I need to draw each state. Anyone else got any good strategies for concurrency analysis?
I used to have do something similar (on a whiteboard, though) whenever I needed to write some slightly complicated concurrency code (I'm a systems developer). However, after years of writing multi-threaded and synchronization code, I've learned that the trick is to.... abstract (?) the representation in your head.
If you try to "flatten out" the concurrency, it'll be this HUGE representation that'll never fit in your skull. The trick is to think in multiple dimensions instead of flattening it out. Sort of queue the other threads in the back of your head, and pretend you're the OS. Whenever you reach a line of code for the current thread you're "imagining/debugging in your head", loop over the other consumers/producers in your model and ask yourself "what happens to this guy at this moment, or what happens if this guy was doing x, y, or z?"
Basically, don't hold the structure, hold the events. Expand the other objects as needed in your head, then stash them away. Don't try to hold them all in there, because they'll never fit.
Incidentally, since adapting to this I many times still get the urge to pick up a pen or marker and scribble down the concurrency model - except 2 seconds later I give up because it's so hard to efficiently represent multi-threaded environments/code in 2d. And that's the same difficulty you have trying to jam that representation in your head.
Remember the description of the components, not the components themselves, I guess. I hope this isn't as confusing as I fear I've made it out to be!
Yeah, I do that for simpler things (a bunch of mutexes, condition variables, etc.) but as soon as I look at anything lock-free, by brain just fails to take it all in.
That looks seriously cool. Too bad it's Win32/.NET only. (the Visual Studio Team System price tag is probably hefty, too, but may well be worth it for this alone).
Anyone else got any good strategies for concurrency analysis?
Probably not what you're really looking for but, maybe you could try to eschew shared state when at all possible?
I, myself, am absolutely no good with threaded code. Message-passing between multiple processes is just such a nicer way to reason about things, without worrying about race conditions. I've been using 0MQ recently, and it's really great for this, since it's easy to get it working across machines even, as well as having common messaging patterns "just work". Try it out sometime.
When I have the choice, I use Clojure's STM or multiprocessing or whatever other means possible for concurrency. Unfortunately, I often can't avoid "hard" multithreading, e.g. in kernel code or on game consoles. I've managed to get fairly good at it in general (and try to avoid being too clever), but I'm always on the lookout for better ways.
Interestingly, when trying to reason about and verify correct synchronisation of data structures, I immediately start drawing boxes with lots of arrows for pointers (just like those in the article) even though I don't normally need any visual aids to design my code. Somehow, holding a complex data structure in my head is no problem, but as soon as I try to think about concurrent access to something as simple as a linked list, I need to draw each state. Anyone else got any good strategies for concurrency analysis?