The Dining Philosophers

Welcome » NERWous C » Examples

1. Current Literature
2. NERWous C Samples

---

Current Literature

This classic problem of resource competition is best explained by this Wikipedia article:

Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers.

Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when they have both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After an individual philosopher finishes eating, they need to put down both forks so that the forks become available to others. A philosopher can take the fork on their right or the one on their left as they become available, but cannot start eating before getting both forks.

Eating is not limited by the remaining amounts of spaghetti or stomach space; an infinite supply and an infinite demand are assumed.

For our discussion, we will change the unlimited "spaghetti" to limited, per this Oracle deadlock analysis:

The process is repeated until there are no more noodle.

Issues

The dining philosophers problem touches on three issues of resource competition:

1. Mutual exclusion
2. Deadlocks and livelocks
3. Resource starvation

On mutual exclusion, the forks are shared resources. Once a philosopher has grabbed a fork, it cannot be grabbed by his neighbor. Our philosopher has exclusive use of this shared resource.

Deadlocks appear when each philosopher has grabbed his left fork and is waiting for his right fork. Since nobody yields (philosophers are known to hold on to their principles), all the philosophers will wait until eternity. One way to break the deadlocks is to allow the philosophers to hold a fork for only 10 minutes and wait 5 minutes to grab a fork again. This solution can introduce livelocks where all philosophers come to the table at the same time, grab their left forks at the same time (which introduces deadlocks), wait 10 minutes, put down their forks at the same time (deadlocks are broken), wait the same 5 minutes, and grab their left forks again. The philosophers are not sitting idle waiting (i.e. stuck in deadlocks), but their grab-release make work actions are like hamsters in spinning wheels, without allowing them to eat and think.

There are several solutions to the deadlocks and livelocks issue. These solutions must also resolve the issue of resource starvation. One philosopher may also be a part-time magician and is quick with his hands. He may grab his forks faster than his left or right neighbors, "starving" them the opportunity to have the necessary forks to get to eat and think.

Solutions

There is an abundance of solutions and discussions on this classic problem on parallelism (see Google or Bing searches).

Here are some of the references:

• Cunningham & Cunningham, Inc -- philosophical discussion on the Dining Philosophers problem
• Oracle Sun Studio -- an implementation in the C language using POSIX threads
• Rosetta Code -- the Dining Philosophers solution in a number of programming languages

---

NERWous C Samples

Here are the Dining Philosophers solutions in NERWous C. We will start with one where the resources are localized, and then expand the solution to distributed resources.

Localized Resources

We follow the current literature where the forks are in the same local area and thus, can be presented by an array. For NERWous C, the array is a mel array:

#define NUM 5
void main () {
   <mel> int forks[NUM];
   for ( int i=0; i<NUM; ++i ) 
      <?>forks[i] = 1;

   for ( int i=0; i<NUM; ++i ) {
      int j = i+1;
      if ( j == NUM+1 ) j = 0;
      <!> {
         int done;
         ( <? as="leftfork, rightfork"> (forks[i] && forks[j) ) {
            if ( ! eat (leftfork, rightfork) ) done = 1;   /* no more eating */
            else done = 0;
            <checkout skip>;
         } 
         think ();
         if ( !done ) <resume>;
         else <end>;
      }
   }
   printf ("All the philosophers are seated. They will leave when they are done.");
}

The forks are shared resources so they are declared as items of a mel array. The for loop then values all forks so they become available for the philosophers. The value 1 is chosen but any value will do since the philosophers are interested in the availability of the forks and not their values.

The task main then runs the second for loop to create the philosopher tasks. Once the tasks are created, the task main displays the "Philosophers seated" message and ends itself leaving the philosopher tasks to run by themselves. Once a philosopher is done with the eating and thinking, its corresponding task will end. Once all the philosopher tasks have ended, the NERWous C program will exit.

The philosopher task is an inline task started by the <!> pel operator. It declares a local variable done to be used throughout its life. It then waits for its left and right fork using the reader AND zone facility to prevent deadlocks and starvations. Once inside the exclusive zone, it can do the eat'ing in peace.

With the eat'ing done, the philosopher task checks out of the exclusive zone with the skip attribute. This leaves the values of the forks it uses available for other philosopher tasks. Without the skip, the default behavior on checkout is to remove the values, causing the philosopher tasks to wait forever to enter the exclusive zones, since there is no other task to re-value the forks.

After think'ing, the philosopher task has to make a decision to continue or to end. If more eat'ing is wanted, the resume operation loops back to the reader AND zone wait. Note that resume loops back to the latest mel wait, and not to the beginning of the pel inline code. Thus, the declaration of the done variable is not re-executed.

Wrap Consecutive AND Construct

The above example has code to check for the boundary condition to wrap around the fork index for the last philosopher task. This code can be replaced by the wrap consecutive AND construct:

#define NUM 5
void main () {
   <mel> int forks[NUM];
   for ( int i=0; i<NUM; ++i ) 
      <?>forks[i] = 1;

   for ( int i=0; i<NUM; ++i ) {
      <!> {
         int done;
         ( <? as="leftfork, rightfork"> (forks[i] ..&&<wrap lbound=0 ubound=NUM>.. forks[i+1) ) {
            if ( ! eat (leftfork, rightfork) ) done = 1;   /* no more eating */
            else done = 0;
            <checkout skip>;
         } 
         think ();
         if ( !done ) <resume>;
         else <end>;
      }
   }
   printf ("All the philosophers are seated. They will leave when they are done.");
}

The wrap attribute automatically assigns forks[0] to forks[i+1] when i+1 is equal to NUM, since forks[NUM] is out of bound of the mel array forks.

Distributed Resources

Let's now assume that our philosophers are very picky. One fork comes from a warehouse in China, one from a warehouse in Italy, one from a comma-separated-value (CSV) file in a store, one from a corporate database, and one from the shared stash. To support such distributed resources, we have to create individual mel variables in order to assign the cel locality, and use the array of mels to assemble the resources:

#define NUM 5
void main () {
   cel cn = { "Chinese Manufacturers", "https://www.philoforks.cn/nerw/" };
   cel it = { "Italian Artisans", "https://www.philoforks.it/nerw/" };
   cel fs = { "Warehouse", "D:\warehouse\forks\modelXYZ.csv" };
   cel db = { "Ledger", "dbsqlforks" } ;

   <mel at=cn> int fork_cn = 1;
   <mel at=it> int fork_it = 1;
   <mel at=fs> int fork_fs = 1;
   <mel at=db> int fork_db = 1;
   <mel> int fork = 1;
   <mel> forks[NUM] = { fork_cn, fork_it, fork_fs, fork_db, fork };

   for ( int i=0; i<NUM; ++i ) {
      <!> {
         int done;
         ( <? as="leftfork, rightfork"> (forks[i] ..&&<wrap lbound=0 ubound=NUM>.. forks[i+1)) {
            if ( ! eat (leftfork, rightfork) ) done = 1;   /* no more eating */
            else done = 0;
            <checkout skip>;
         } 
         think ();
         if ( !done ) <resume>;
         else <end>;
      }
   }
   printf ("All the philosophers are seated. They will leave when they are done.");
}

In this setup, each mel is localized in a different cel.

For further resource distribution, let's define a cel node to be assigned to run for each philosopher:

  cel philo[NUM] = { 
   ("Philosopher 0", 0), ("Philosopher 1", 1), ("Philosopher 2", 2),
   ("Philosopher 3", 3), ("Philosopher 4", 4) };

   for ( int i=0; i<NUM; ++i ) {
      <! at=philo[i]> {
         int done;
         ( <? as="leftfork, rightfork"> (forks[i] ..&&<wrap lbound=0 ubound=NUM>.. forks[i+1)) {
            if ( ! eat (leftfork, rightfork) ) done = 1;   /* no more eating */
            else done = 0;
            <checkout skip>;
         } 
         think ();
         if ( !done ) <resume>;
         else <end>;
      }
   }
   printf ("All the philosophers are seated. They will leave when they are done.");

Each philosopher task runs on its own philo[i] computer element.

---

Previous Next Top