1
\$\begingroup\$

Dining philosopher problem is one of the classic problems in computer science. I intended to implement it using Java threads. I attempted using the locking framework that came with Java 5 and used the tryLock() method to avoid deadlock. My implementation is fairly simple. I implemented the runnable interface to represent a philosopher and used executor service to run all these runnable.

As a lock, I have used ReentrantLock. I know there are several implementations are already discussed here, but I would like to get some review on my implementation.

import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.Random;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Lock;

public class Philosopher implements Runnable {
    private String name;
    private final Lock leftFork;
    private final Lock rightFork;

    public Philosopher(String name, Lock leftFork, Lock rightFork) {
        this.name = name;
        this.leftFork = leftFork;
        this.rightFork = rightFork;
    }

    public void think() {
        log("thinking");
    }

    public void eat() {
        //assume, eating requires some time.
        //let's put a random number
        try {
            log("eating");
            int eatingTime = getRandomEatingTime();
            TimeUnit.NANOSECONDS.sleep(eatingTime);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }

    @Override
    public void run() {
        while (true) {
            keepThinkingAndEating();
        }
    }

    private void keepThinkingAndEating() {
        think();

        if (leftFork.tryLock()) {
            try {
                log("grabbed left fork");
                if (rightFork.tryLock()) {
                    try {
                        log("grabbed right fork");
                        eat();
                    } finally {
                        log("put down right fork");
                        rightFork.unlock();
                    }
                }
            } finally {
                log("put down left fork");
                leftFork.unlock();
            }
        }
    }

    private void log(String msg) {
        DateTimeFormatter formatter = DateTimeFormatter.ISO_LOCAL_TIME;
        String time = formatter.format(LocalDateTime.now());
        String thread = Thread.currentThread().getName();
        System.out.printf("%12s %s %s: %s%n", time, thread, name, msg);
        System.out.flush();
    }

    private int getRandomEatingTime() {
        Random random = new Random();
        return random.nextInt(500) + 50;
    }
}

And the main method to run this code:

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class PhilosopherMain {
    public static void main(String[] args) {
        Lock[] forks = new Lock[5];
        for (int i = 0; i < forks.length; i++) {
            forks[i] = new ReentrantLock();
        }

        Philosopher[] philosophers = new Philosopher[5];

        ExecutorService executorService = Executors.newFixedThreadPool(5);

        for (int i = 0; i < philosophers.length; i++) {
            Lock leftFork = forks[i];
            Lock rightFork = forks[(i + 1) % forks.length];
            philosophers[i] = new Philosopher("Philosopher " + (i + 1), leftFork, rightFork);
            executorService.execute(philosophers[i]);
        }

        executorService.shutdown();
    }
}
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

Your implementation is minimalistic but it does what it does and it does it good.

Your code consists basically of three elements:

  1. Setup the place
  2. Logging actions of the philosophers
  3. Handling philosopher behaviour

1 and 2 are not that interesting as they may differ slightly from implementation to implementation. And in general you did not reach a code mass to address any modularization issues.

Number 3 is the part I want to address. You chose the egoistic variant of the dining philosophers. A philosopher may face starvation if other philosophers keep taking the forks in unfavorable point of times.

Another variant is cooperative. You have to introduce one more artefact to do so. Philosophers may give aquired forks directly to their neighbors if they registered for usage of a fork while the fork itself is currently unavailabe. This prevents a philosopher from releasing the fork and aquiring it again immediately so other philosophers have no chance to introduce themselves in the process.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.