Javaにおける並行性:ダイニング哲学者問題

In Concurrency, resources and the threads that utilize them are at its core. The dining philosophers problem highlights some of the issues that arise when resources are shared among threads and provides the solutions.

In this article, we would be discussing the problem and the solutions alongside their code implementations in java.

The dining philosophers problem states that 5 philosophers in a restaurant sit at a round table for a meal. For the meal, they each require two chopsticks in total 10 chopsticks, but there's a problem, at the table only 5 chopsticks were provided.

(I know I know, just get more chopsticks right?. Bear with me.)

public class DinningPhilosophers {
      static int no_of_philosophers = 5;
      static Philosopher [] philosophers = new 
      Philosopher[no_of_philosophers];
      static Chopstick[] chopsticks = new 
      Chopstick[no_of_philosophers];

Each philosopher is represented as a thread and each chopstick, a resource.

A philosopher can only perform 2 actions, to think and to eat. A philosopher is either thinking or eating and nothing in-between.

• To Think: A philosopher must put down both chopsticks.

• To Eat: A philosopher must be in possession of both chopsticks.

Initially, all philosophers begin with thinking, each philosopher thinks for a variable time length. When thinking ends, they begin eating. Similarly, eating occurs for a variable time length for each philosopher.
It is important to note that these two actions would continue for an infinite amount of time. The problem assumes that the philosophers never get filled from eating or tired from thinking.

(Disclaimer: The writer would not be involved in any form of payment for the food eaten by these bottomless pits of philosophers.)

private static class Philosopher implements Runnable{
      private int number;
      Chopstick leftChopstick;
      Chopstick rightChopstick;
      public Philosopher( int number, Chopstick leftChopstick, 
                        Chopstick rightChopstick){
          this.number = number;
          this.leftChopstick = leftChopstick;
          this.rightChopstick = rightChopstick;
      }
      void performAction(String action){
          try{
          int waitTime = ThreadLocalRandom.current().nextInt(0, 
          1000);
          System.out.println("Philosopher "+ (number + 1) + action 
                            + waitTime +" ms");
          }catch(InterruptedException ex){
              ex.printStackTrace();
          }
      }
      @Override
      public void run(){
           while(true) {
                performAction(" thinks for ");
                leftChopstick.grabChopstick();
                System.out.println("Philosopher " + (number + 1) + 
                                   " picks up leftChopstick");
                rightChopstick.grabChopstick();
                System.out.println("Philosopher " + (number + 1) + 
                                  " picks up rightChopstick");

                performAction(" eats for ");
                leftChopstick.dropChopstick();
                System.out.println("Philosopher " + (number + 1) + 
                                   " drops leftChopstick");
                rightChopstick.dropChopstick();
                System.out.println("Philosopher " + (number + 1) + 
                                   " drops rightChopstick");
            }
      }
}

The variable waitTime is used to determine the variable time length for each action in milliseconds.
Since both eat and think actions require a variable time length, I have used the performAction(action) function in their stead to perform for both actions by passing in a parameter (action) to differentiate both actions.
Also notice in the run function the philosopher must acquire both chopsticks before performing the eat action and must drop both chopsticks after eat action is completed.

     public static void main(String []args){
          for (int i = 0; i < no_of_philosophers; i++){
              chopsticks[i] = new Chopstick();
          }
          ExecutorService executor = 
          Executors.newFixedThreadPool(no_of_philosophers);
          for (int i = 0; i < no_of_philosophers; i++){
               philosophers[i] = new Philosopher(i, chopsticks[i], 
               chopsticks[(i + 1) % no_of_philosophers] );
               executor.execute(philosophers[i]);
          }
     }
}

chopsticks[(i + 1) % no_of_philosophers] used in the second parameter of Philosopher constructor is to prevent chopsticks from going out of bounds.
for example: i starting from 0,
At i = 4, i + 1 = 5 (out of bounds).
Therefore to prevent that,
5 % 5 = 0.
Remember that the philosophers are seated at a roundtable so the chopstick available to the 5th philosopher would be the 5th chopstick and the 1st.

We have commenced our feast and due to having varying time lengths for thinking and eating among the philosophers, the chopsticks can be shared despite having just 5 of them.

However, on a particular iteration Philosopher 1(p1) comes out of thinking and grabs the left-chopstick but before he grabs the right one, p2 comes out of thinking and grabs his left-chopstick which just happens to be p1's right chopstick.

The struggle begins, p1 cannot snatch his right-chopstick from p2(recall the semaphore) and p2 just refuses the drop his chopstick, both sides refusing to succumb.

While there are a number of solutions to the dining philosophers problem, in this article we'll be looking at 2 of them.

This solution ensures that for every odd number philosopher i.e. p1, p3, p5, the left-chopstick is grabbed first before the right and for every even number philosopher (p2, p4), the right chopstick is picked up before the left.

This prevents the conflict when two adjacent philosophers come out of thinking at the almost the same time.

for example: p1 comes out of thinking and grabs his left-chopstick.
At the same moment p2 comes out of thinking. This time, rather than reaching for his left-chopstick which at that moment p1 would also be reaching for, causing a deadlock. It instead reaches for its right-chopstick, giving p1 enough time to reach and acquire his right-chopstick preventing a deadlock.
The same thing occurs in the other adjacent philosophers, where one philosopher takes advantage of the other's re-direction.

   public static void main(String []args){
        for (int i = 0; i < no_of_philosophers; i++){
            chopsticks[i] = new Chopstick();
        }
        ExecutorService executor = 
        Executors.newFixedThreadPool(no_of_philosophers);
        for (int i = 0; i < no_of_philosophers; i++){
            if( i % 2 == 0)
                philosophers[i] = new Philosopher(i, chopsticks[(i 
                + 1) % no_of_philosophers], chopsticks[i] );
            else
                philosophers[i] = new Philosopher(i, 
                chopsticks[i], chopsticks[(i + 1) % 
                no_of_philosophers] );

            executor.execute(philosophers[i]);
        }
    }
}

Notice the slight change in the implementation, where if Even, the order of acquiring a chopstick is reversed.

(Now the feast can really begin)

(A bottomless pit still has a bottom it seems).

We have come to the end of the feast. I hope this article has cleared any confusions you might have had on the dining philosophers problem.

You might ask where the concept could be applied. One of its applications is in Operating Systems where every process needs two resources out of which, one has been acquired and the other is acquired by another process. Till the other process frees the resource, this process cannot proceed. Similarly, the other process is dependent on another process for its resource. Since every process is dependent on each other, it forms a circular-wait and the system goes into a deadlock. This deadlock can then be resolved through various techniques of which, some were discussed in this article.