Avian Solution – Dining Philosophers Problem

In the next few blogs, we’ll look at some of the classic thought problems for parallel programming, including the Producer-Consumer problem, the Dining Philosophers problem, and the Barbershop problem. In this blog, we’ll look at the Dining Philosophers problem and see how it becomes an easy task to solve using the Avian Computing environment and the Concurrency Explorer (ConcX).

diningPhilsThe Dining Philosophers problem has been a classic in parallel programming since the 1980’s when it was first proposed. In this scenario, five philosophers are seated around a table with one fork between them, one fork on their left and one on their right. To eat, they need to get the fork to their left (which is shared with their neighbor on their left) and then get the fork on their right (which is shared with their neighbor on their right). If they don’t have both forks, they can’t eat.

Several solutions have been proposed over the years:

  • Waiter controls who eats
  • Resource hierarchy – forks requested in order
  • Philosophers monitor their neighbors – eat when they are not eating

In ConX, the solution is actually quite simple. All five of the birds are different instances of the same type of Philosopher birds and they all just try to eat, just like in any other Avian scenario. The only differences between each of the philosophers is which forks they try to use to eat. The hardest part of the solution is making sure that each philosopher is trying to access the correct two forks.

In the original Avian solution, a Waiter (helperBird) was used to set the table and put the correct forks out on the table. And conceptually this makes sense because in the real world a waiter really would set the table. Once the Waiter has done his job, he has nothing else to do or eat and eventually starves and dies off.

phil1thumbIn Avian 2.0, the firstTime method is used to have each philosopher try to put out the forks that he cares about (the ones that are at the sides of his own plate) before sitting down. If a fork is already in position between plates, the philosopher does not put out a second. The philosopher then begins to eat whenever both forks are available; if no other philosophers join him, the first one is free to make a pig of himself.

Click on the screenshot and the full size image will show that Aquinas uses Fork1 and Fork2. Burke, sitting next to him, uses Fork2 and Fork3. Chomsky, sitting next to Burke, uses Fork3 and Fork4, and so on.

phil5thumbAs philosophers are added, the contention for forks begins. Each philosopher is trying to get the two forks beside his plate, effectively making him compete with his immediate neighbors for them. Fortunately, this contention is handled easily and automatically in ConcX. Because all five philosophers are based on the Philosopher bird, they are all configured the same so they share forks (and dinner) nicely and all eat about the same amount, moderated by the random lengths of each of their naps.

Each philosopher is set up to need both the left fork AND the right fork; in the above image, Aquinas needs Fork1 and Fork2 to eat. If Aquinas cannot get both forks, he can’t eat so he puts down any fork that he might have. It’s all handled by configuring the behavior of the Philosopher birds. And since the Philosopher bird extends the StdBird just to override two functions, it’s pretty easy to do.

What is extremely interesting in Avian Computing is that once the problem is set up and running, you can adjust parameters and study the effects of the changes. For example, if you reduce the length of time that the philosopher waits before trying to get a fork, will they be better at getting two forks and eat more? It’s easy to try; just stop them and shorten the Nap Length of Aquinas or Diogenes and restart them all and see who eats the most.

In the original Dining Philosophers description, a philosopher who has eaten will then be rejuvenated enough begin speaking at length on a philosophical subject near and dear to his heart before putting down his forks. This can be accomplished by incorporating a mandatory delay into the Philosopher birds; the birds sitting on either side of the speaking philosopher will patiently wait until he finishes speaking before snatching up one of his forks.

What if a sixth philosopher joins them, how will this affect the dinner party? It’s pretty easy to add another philosopher by clicking the Add New Bird button and having the new Philosopher bring another fork. The hard part is setting which philosophers share which forks. Adding 2 or 3 more philosophers is just as easy, as long as you keep straight who uses which fork. How much will the other diners be affected?  Will the philosophers eat less when 9 of them are seated at the table?

What if Aquinas and Chomsky get mad at Bacon and team up and try to prevent Bacon from getting a fork? That could be configured without any problems just by changing which forks they try to get.  What if Bacon got mad and teamed up with Diogenes? Would Emerson be able to “rise above” their pettiness and eat unaffected or would he be affected, even though he wasn’t on either team.

What if one of the philosophers is exceptionally hungry (or greedy)? By shortening his nap times, he’ll eat more frequently, but to the detriment of his neighbors. If they also shorten up their nap times to better compete with the first hungry philosopher, their neighbors will also suffer. The greed of the first philosopher eventually spreads thru all the philosophers seated at the table. And in this state, with every philosopher trying to eat as often as possible, the overall amount that is eaten at the table is reduced because it is so much harder to successfully get both forks.

It is tempting to extend this simple example to society at large and speculate that as long as greed is isolated and not excessive, everyone can eat OK. However, once greed is commonplace, the actual amount eaten as a group goes down because too much time is wasted competing.

Using ConcX, it is much easier to think about a parallel problem than using traditional code methods. It’s also much easier and try out different solutions. It also allows you to explore different possibilities than when using traditional coding approaches. The birds in ConcX map directly to the dining philosophers, so thinking about the Avian model makes it easy to develop a solution (and feed the hungry philosophers).

Leave a Reply

Your email address will not be published. Required fields are marked *