Starvation in the dining philosopher problem

Question

I've been looking at a solution for the dining philosopher problem on wikipedia. The resource hierarchy solution

I understand how it works and how breaking the circular structure prevents deadlocks but how does the solution prevent starvation? Couldn't one or a few threads keep going while a few wont get to make progress?

If not, what prevents this from happening?

The implementation:

public class DinningphilMain {



    public static void main(String[] args) throws InterruptedException {


        int numPhil = 3;

        Philosopher[] phil = new Philosopher[numPhil];

        Fork[] forkArr=new Fork[numPhil];


        for (int i = 0; i < numPhil; i ++) {
            forkArr[i]= new Fork(i);
        }

        for (int i = 0; i < numPhil-1; i++) {
            phil[i]=new Philosopher(i, forkArr[i], forkArr[i+1]);
        }
        phil[numPhil-1]= new Philosopher(numPhil-1, forkArr[0], forkArr[numPhil-1]);

        for (Philosopher p : phil)
            new Thread(p).start();


    }
}

This is the philosopher class

import java.util.Random;

public class Philosopher implements Runnable {

    int sleep = 1000;
    int id;
    int eatTime= 500;
    Random rand = new Random();
    Fork left;
    Fork right;


    public Philosopher(int id,  Fork left, Fork right) {
        this.id = id;
        this.left = left;
        this.right = right;

    }


    private void think() {
        System.out.println("Philosopher " + id + " is thinking");
        try {
            int thinkingTime = rand.nextInt(sleep);
            Thread.sleep(thinkingTime);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    private void getForks() {
        System.out.println("Philosopher " + id + " is picking up forks");
        try {
            left.get();
            right.get();
            System.out.println("Philosopher " + id + " has both forks");
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

    }

    private void releaseForks() {
        System.out.println("Philosopher " + id + " is putting down forks");
        left.release();
        right.release();
    }

    private void eat()  {
        System.out.println("Philosopher " + id + " is eating");
        try {
            Thread.sleep(eatTime);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }



    @Override
    public void run() {
            while (true) {
                getForks();
                eat();
                releaseForks();
                think();
            }

    }
}

This is the fork class

public class Fork {

    private int id;
    private Thread thread;

    public Fork(int id) {
        this.id = id;
        thread = null;
    }

    public int getId() {
        return id;
    }

    public synchronized void get() throws InterruptedException {
        if (thread != null) 
            this.wait();
        thread = Thread.currentThread();
    }

    public synchronized void release() {
        if (thread == Thread.currentThread())
            thread = null;
        this.notify();
    }

}

score 4 · Answer 1 · answered Sep 02 '18 at 19:39

4

The resource hierarchy solution solves deadlocks but doesn't solves starvation.

In order to prevent starvation you either need:

A guarantee from the thread system that threads will be unblocked from monitors and condition variables in the same order that they are blocked.

To do it yourself. In other words, you must guarantee that no philosopher may starve. For example, suppose you maintain a queue of philosophers. When a philosopher is hungry, he/she gets put onto the tail of the queue. A philosopher may eat only if he/she is at the head of the queue, and if the chopsticks are free.

This is taken from C560 Lecture notes -- Dining Philosophers

answered Sep 02 '18 at 19:39

Shmulik Klein

3,754
19
34

My confusion comes from when I implemented the solution in Java the philosophers seem to be eating in order (1 then 2 then 3...) and there seems to be no starvation. I'm using wait() and notify() to get access to forks but I'm pretty sure those methods in Java make no guarantees on the order, so it seems odd – John Slaine Sep 02 '18 at 22:13
1

Can you share your implementation ? – Shmulik Klein Sep 03 '18 at 10:26
I've edited the post with the implementation. I'm thinking it could be the Thread.sleep() calls that's making sure that no thread is hogging all the forks – John Slaine Sep 03 '18 at 11:08

score 1 · Answer 2 · answered Sep 02 '18 at 19:26

The short answer is that it doesn't. The dining philosophers problem is used to discuss the problem of concurrency; it in itself is not a single solution for anything (hence why it's called a problem).

The wikipedia page for the dining philosophers itself shows a few implementations. The first one shows how a poor implementation for a solution will cause starvation.

https://en.wikipedia.org/wiki/Dining_philosophers_problem

Starvation in the dining philosopher problem

2 Answers2