15 October 2007 - 20:34Traffic deadlock

Traffic was extra terrible this weekend. I’m not going to claim that Atlanta has the worst drivers in the country (practically everyone claims their city of residence deserves that title), but Atlanta is often ranked among the worst traffic cities in the country.

However, the point of this post is not to complain about Atlanta traffic in general, because that would be unoriginal and not nearly nerdy enough. To me, it is always interesting to observe CS concepts at work in real life, like a pipelined drive-through with separate payment and food windows to provide better customer throughput (the Checkers around here even has a superscalar drive-through, with two independent paths on separate sides of the building). Anyway, in that vein and continuing on the theme of parallel programming, recently I observed classic example of deadlock in traffic. Atlanta drivers seem to block intersections as standard operating procedure, which resulted in the following deadlock:

Neither car is able to turn and make progress because the cars traveling in the opposite direction are blocking the intersection (which are themselves blocked behind the turning cars). This is a good reason why people should not block intersections (or driveways), because it’s not just a matter of courtesy. This deadlock was resolved by one of the cars – the one trying to turn into the driveway – giving up and turning around a bit further up the street (after being honked at by a line of cars sitting in a major intersection after the light changed). Anyway, I’m sure Atlantans will read my blog and adjust their behavior accordingly.

As an aside, I always liked Dijkstra’s colorful “deadly embrace” terminology for referring to a two-process deadlock.