Dining Philosophers' Problem

general
,
1

I have to implement a deadlock-free solution using semaphores to dining philosophers’ problem.
Can anyone help me on how I should do it.

1 Like
2

what’s the problem?

3

Dining phil’s problem can be solved using monitors or semaphores,

For Semaphores, you keep a semaphore for every fork(more specifically , a mutex), since that is your shared resource

After which you execute a thread for each philosopher, and try to acquire the 2 forks by checking the semaphore status.
If one cannot, it should release the acquired semaphores to prevent deadlocks.

Here is a java implementation

public class Philosopher implements Runnable {


private static Table table;
private int ID;
private int N = 5;
private static Semaphore s1 = new Semaphore(1) ;
private static Semaphore[] sarray = new Semaphore[5];
private int[] array = new int[5];
private int thinking = 0;
private int hungry = 1;
private int eating = 2;
private int left = (ID + N - 1) % N;
private int right = (ID + 1) % N;

void test(int i)
{
    if((array[i] == hungry) && (array != eating) && (array[right] != eating))
    {
        table.ForkTake_GUI(i);
        array[i] = eating;
        sarray[i].release();

    }   
}

void take_forks(int i)
{
    try {
        s1.acquire();
    } catch (InterruptedException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }
    array[i] = hungry;
    table.Hungry_GUI(i);
    test(i);
    s1.release();
    table.Eating_GUI(i);
    sarray[i].release();
}

void put_forks(int i)
{
    table.StopEating_GUI(i);
    try {
        s1.acquire();
    } catch (InterruptedException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }
    array[i] = thinking;
    test(left);
    test(right);
    table.ForkPut_GUI(i);
    s1.release();

}

public Philosopher(int i)
{
    setID(i);
}

public void run()
{
    while(true)
    {
        Random RandomGenerator = new Random();
        int randomNum = RandomGenerator.nextInt(10);
        try {
            Thread.sleep((randomNum * 1000));
        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }


        take_forks(ID);
        //table.Eating_GUI();
        put_forks(ID);      
    }

}

public static void main(String args[]) {

    EventQueue.invokeLater(new Runnable() {
        public void run() {
            try {
                table = new Table();
                table.frame.setVisible(true);
            }
            catch(Exception e){
                e.printStackTrace();
            }

        }
    });

    Philosopher p1 = new Philosopher(1);
    Philosopher p2 = new Philosopher(2);
    Philosopher p3 = new Philosopher(3);
    Philosopher p4 = new Philosopher(4);
    Philosopher p5 = new Philosopher(5);
    Thread pt1 = new Thread(p1);
    Thread pt2 = new Thread(p2);
    Thread pt3 = new Thread(p3);
    Thread pt4 = new Thread(p4);
    Thread pt5 = new Thread(p5);

    sarray[0] = new Semaphore(1);
    sarray[1] = new Semaphore(1);
    sarray[2] = new Semaphore(1);
    sarray[3] = new Semaphore(1);
    sarray[4] = new Semaphore(1);

    pt1.start();
    pt2.start();
    pt3.start();
    pt4.start();
    pt5.start();

}
public int getID() {
    return ID;
}
public void setID(int iD) {
    ID = iD;
}
}

credits : java - Dining Philosopher Thread and Semaphore - Stack Overflow