9 December 2009 - 1:46Traffic starvation

One of my first posts on this blog was titled, “Traffic Deadlock”. Deadlock is a classic pitfall when dealing with mutual exclusion, and another pitfall is “starvation.” Starvation occurs when a process cannot acquire a shared resource (and thus cannot make progress). Typical implementations of locks (like pthread’s mutexes) do not preserve FIFO ordering of acquisition requests, so the locks are not fair. If you have three threads — A, B, and C — and they all want access to the same shared resource, B might starve as follows: A holds the lock and B blocks trying to acquire it. Right as A releases the lock, C also tries to acquire it and wins over B because the lock does not enforce fairness. Then B is still waiting on the lock while C uses it. Right as C releases the lock, A tries to acquire the lock and wins over B. This could continue indefinitely before B gets the lock. In practice B’s “bad luck” usually doesn’t happen for too long, because thread scheduling and fluctuations in computation time perturb the system enough to make this rare. So fair FIFO locks are usually only used when you need lower variance and more predictability (since there is more overhead associated with them).

But sometimes there are structural asymmetries in the system that make starvation more likely and fairness more important. For example, reader-writer locks make it easier to starve writers if more readers can always enter while the lock is in reader mode (because writers must wait until all readers are done before acquiring). This brings me to the traffic scenario below:

A popular drive-through (Chick-fil-a) gets backed up at meal times. The driveway in the picture above is the drive-through entrance. Now, once the driveway gets backed up to the road, new cars cannot enter until the line moves forward some. A car turning right into the entrance must wait if the line is backed up too far, but a car turning left across traffic must wait for both 1) no immediate oncoming traffic and 2) space in the line. Since the left turning car must yield to all right turns, you get an interesting starvation phenomenon: the line backs up so no car can enter and the left turning car waits. The line moves forward some so now there is room, but the traffic in the other lane continues to move and blocks the turn. Eventually a right turning car fills the space in the line, so when the next break in traffic occurs the left turning car still cannot complete the turn. All of the right turning cars occupy any freed space in line and starve out the left turning ones.

This was a frustration I encountered first hand, and it reminded me of an article I read a few weeks ago (on Slashfood) about increasingly unreasonable fast food drive-through wait times and the traffic problems a poorly-placed drive-through can cause.

“In Peabody, Mass., the opening of the first New England Sonic in August drew excited customers from across the region anticipating their first extra-long chili-cheese Coney hot dog. In the first month, it wasn’t unusual for customers to wait in their cars for up to four hours.”

Not exactly “fast food,” is it?