Concurrency in Java: The Dining Philosophers Problem

Timilehin Bakare — Thu, 24 Feb 2022 11:44:57 +0000

Introduction
Problem Statement
- The Philosopher
- Unto The Chopstick
- The Feast
- So then where is the problem
Solutions
- The Reset Solution
- The Asymmetric Solution
Conclusions.

Introduction.

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.

Problem Statement.

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.

The Philosopher.

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.

Unto The Chopstick.



 private static class Chopstick{
        public Semaphore semaphore = new Semaphore(1);
        void grabChopstick(){
            try {
                semaphore.acquire();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        void dropChopstick(){
            semaphore.release();
        }
 }

A feature in the Chopstick class is the Semaphore. Here the semaphore is used to secure a chopstick once it has been grabbed by a philosopher. This prevents other philosophers from snatching a chopstick that has already been picked up.

Now that we have created the Philosopher class and the Chopstick class, we can now dig in.

(Let the feast begin)

The Feast.



     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.

So then where is the problem.

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.

To make matters worse p3, p4 and p5 are in a similar struggle. The whole feast grinds to a halt as no philosopher is able to eat.
This scenario is called a Deadlock.

(Ladies and Gents, I believe we've found our problem.)

The Solutions.

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

The Reset solution.

It uses a reset function to force all philosophers drop their chopsticks and restart the iteration.
While this could help resolve the immediate deadlock, there is no assurance that the next iteration would not also lead to a deadlock.
When a deadlock continues to repeat it is called a live-lock.

The Asymmetric solution.

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)

Conclusion

(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.

for the full code implementation: https://github.com/plainsight16/Java-Concurrency/blob/main/dinningPhilosphers/DinningPhilosophers.java

A Guide to writing to better comments

Timilehin Bakare — Sun, 16 Jan 2022 23:22:24 +0000

Introduction

You're probably thinking," what's new with comments?" and you'll be right to think that.
Often times, not much thought is put into writing a comment. They are mostly ignored and considered secondary(albeit as they should be) but this negligence has led many programmers into writing very awful comments.
for example:

In order to avoid writing comments like this, I have written this article to serve as a guide to writing better comments.

Here are some guides to writing better comments

Avoid writing redundant comments
Comments should be updated
Do not excuse bad code with commenting
Comments should not reference other codes
Comments should be informative
Comments could be used to provide links to original source code
Comments should not be used for attribution

The rest of this article explains these guides and provides examples to them.

1. Avoid writing redundant comments

The above is common among early-beginners as they're introduced to code, While this could be very helpful with teaching beginners. Its considered redundant as it adds no information and merely causes visual clutter.

2. Comments should be updated.

Overtime comments silently degrade. While code is continuously updated, the comments are forgotten. For a code cryptic in nature, readers turn to the comments to provide an explanation, and when that explanation is false it leaves the readers confused or worse mislead.
for example:

The asterisks in the regex pattern show that it matches a whole lot more than it was stated by the comments which could be very misleading to the readers who do not bother to check the regex pattern.

3. Do not excuse bad code with commenting

Commenting should be used as a last resort. Every comment serves as a failure to express yourself clearly in code. Always try to clean the code to express yourself better before resulting to commenting.
for example the code snippet below could have been cleaned up rather than using a comment.

After cleaning it up

4. Comments should not reference other codes

A comment should not reference a code that is not present or local because the reference code could change but the comment wouldn't
for example

The comment above references a "default" that is not present in the code block, this confuses the reader as they don't know what default in the comment means.

5. Comments should be informative

The comment above informs the reader that SimpleDateFormat is not thread-safe, if the code is to be modified, the programmer would be well informed of its limitations.

6. Comments could be used to provide links to original source code

Readers can follow the link provided in the comments to learn more

7. Comments should not be used for attribution

Comments like these are unacceptable especially in production. The source code control systems can always tell who the author was.

Conclusion

I hope this article has been helpful in highlighting the importance of writing proper comments and the guides provided were well understood.

References: Clean code(A handbook of Agile Software Craftsmanship)

DEV Community: Timilehin Bakare

Concurrency in Java: The Dining Philosophers Problem

Table of Contents

Introduction.

Problem Statement.

The Philosopher.

Unto The Chopstick.

The Feast.

So then where is the problem.

The Solutions.

The Reset solution.

The Asymmetric solution.

Conclusion

A Guide to writing to better comments

Introduction

Here are some guides to writing better comments

1. Avoid writing redundant comments

2. Comments should be updated.

3. Do not excuse bad code with commenting

4. Comments should not reference other codes

5. Comments should be informative

6. Comments could be used to provide links to original source code

7. Comments should not be used for attribution

Conclusion