Traffic Control and Deadlock

According to Botkin and Harlow  in their book "A Treasury of Railroad Folklore" (pp. 381), the Kansas State Legislature passed a statute that decreed that

"When two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone."

It is not clear how long this statute lasted, but certainly it did not last long -- otherwise, one would find all US trains stopped at some crossing in Kansas! The reason the above statute is "illogical" stems from the fact that it results in the two trains approaching the crossing to grind to a halt -- none of them is able to make "progress" in its journey. They will be "deadlocked".

Have you ever been stuck in traffic and wondered why is it that nobody around you is moving? Have your computer ever inexplicably stopped working, seemingly freezing for no obvious reason? If you answered "yes" to either of these questions, then it could well be that you were the victim of deadlocks. A deadlock is a situation wherein two or more competing agents (e.g., people, programs, trains, vehicles) are waiting for the other to finish, and thus neither ever does.

For a deadlock to occur, a cycle must occur, whereby agents end up being arranged in a circle with each agent in the waiting on another agent in a particular direction (in the circle). The picture below shows how deadlocks occur in real life (picture courtesy of a Google search). Each car in the deadlock illustrated in the picture below is waiting for a car that is either in front of it, or to its left.

Image courtesy of http://www.glommer.net/blogs/?p=189

[Click for a larger image]


The Dining Philosophers Problem

A classical illustration of deadlocks is the "Dining Philosophers" problem. In that problem, a number of philosophers (say five) are arranged around a table, each with a plate with an infinite supply of noodles in front of him/her and each with access to two chopsticks -- one on the right and one on the left. Each chopstick is placed between two philosophers. To eat, a philosopher, grabs the chopstick on his/her left, then the chopstick on his/her right, and with both chopsticks in hand, the philosopher may eat. When full, the philosopher would simply release both chopsticks (allowing other hungry adjacent philosophers to grab either of these chopsticks and, hopefully, eat). The philosopher life revolves around "Thinking" (i.e., not interested in eating and thus holding no chopsticks), "Hungry" (i.e., waiting for one of the two chopsticks next to his/her plate), or "Eating" (i.e., having secured both chopsticks).

The animation below illustrates the life of five such philosophers.

  • A philosopher who is thinking says "Mmm!"
  • A philosopher who is eating has both hands "up"
  • Otherwise, a philosopher is hungry, with both hands down (waiting for the left chopstick) or with the left hand up and the right one down (waiting for the right chopstick).

Click on the "start/stop" button to start the animation.

As the story goes, the dining philosophers were left secluded in a castle for a week to think about a pressing issue (perhaps global warming or the price of gasoline). Unfortunately, after the week had passed, all five philosophers were found dead around the table. Starvation was the cause of death, even though there was plenty of noodles on each one of the philosophers' plates!

Can you guess what went wrong?   If you let the animation run long enough, you will find out!

Answer: They died because they got themselves in a deadlock situation, whereby each philosopher is waiting for the one to its right. All philosophers are hungry and no one is eating! This is illustrated below -- each of the five philosophers has exactly one chopstick (the one on his/her left) and waiting for the other.

[Deadlocked Philosophers]

Clearly, the number of philosophers could be any general number n (not necessarily five as in the illustration above).


Solutions to the Dining Philosophers Problem

To avoid having dead philosophers, the following two "protocols" were suggested as possible solutions:

Protocol 1: Break the symmetry

It was noted that the philosophers' predicament was the result of all of them following the same exact protocol: going for the right chopstick, then the left one, and then eating. Thus, it was suggested that breaking the symmetry might ensure that no "cycles" would develop. So, the proposed protocol is to "Have at least one of the philosophers grab the chopsticks in an order opposite to the other philosophers (i.e., grab the one on the left first and then the one on the right)."

  • Prove that the above protocol will work. You need to show that deadlocks cannot happen if the above protocol is adopted.
  • With reference to the ill-fated Kansas State statute, can you phrase the statute in such a way that deadlocks would not happen? [Hint: Break the symmetry!]

Protocol 2: Reduce the competition (or congestion) for resources

Another observation was that the deadlock was the result of limited resources (not enough chopsticks) for all philosophers to eat at the same time. Assuming that we cannot get more chopsticks, it was suggested that one way to avoid deadlocks was to have less philosophers compete for the chopsticks at any point in time. So, the proposed protocol is "Do not allow more than k philosophers attempt to eat at the same time. In other words, when a philosopher becomes hungry, he/she should check how many other hungry philosophers are around the table including himself/herself. If that number is more than k, then that philosopher should refrain from competing for chopsticks." Clearly, we want to allow as many philosophers as possible to eat concurrently (without risking deadlocks). 

  • Do you think the above protocol will work? Clearly, it does work for k=1 (since a single philosopher will have no competition and is guaranteed to eat). Does it work for k=2? Does it work for  k=3?
  • What is the largest value of k for which this protocol will work?
  • Going back to the traffic deadlock illustrated above, can you propose a simple rule that would ensure that deadlocks such as that depicted above will not occur? [Hint: Reduce the congestion at the intersection!]

[To be continued -- maybe]