Another dining philosophers concurrent issue

Question

This is yet another implementation of dining philosophers problem, this is homework problem and I will show here what I have tried so far:

/**
 * DPServer.java
 * <p>
 * This class implements the methods called by the philosophers
 */
package cc;

import java.util.Random;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class DPServer {

    private static Lock chopstick[] = new Lock[5]; // Create chopstick locks
    private static Lock mutex = new ReentrantLock(true);

    private static int MAX_EAT_TIME = 5000; // maximum eating time in milliseconds
    private static int MAX_THINK_TIME = 5000; // maximum thinking time in milliseconds
    private static Random r = new Random(0);


    // default constructor for DPServer class
    public DPServer() {
        for (int i = 0; i < 5; i++) {
            chopstick[i] = new ReentrantLock(true);
        } // end for

    } // end DPServer default constructor


    // called by a philosopher when they wish to eat
    public void takeChopsticks(int philosopherNumber) {
        // acquire chopstick[philosopherNumber] and chopstick[(philosopherNumber + 1) mod 5]
        System.out.println("Acquiring chopstick[" + philosopherNumber + "] and chopstick[" + ((philosopherNumber + 1) % 5) + "]");
        chopstick[philosopherNumber].lock();
        chopstick[(philosopherNumber + 1) % 5].lock();
        // eat for a random number of milliseconds
        int eatTime = r.nextInt(MAX_EAT_TIME);
        System.out.println("Philosopher " + philosopherNumber + " is eating for " + eatTime + " milliseconds");
        try {
            Thread.sleep(eatTime);
        } catch (InterruptedException ex) {
            System.out.println("Philosopher " + philosopherNumber + " eatTime sleep was interrupted");
        }

    } // end takeChopsticks


    // called by a philosopher when they are finished eating
    public void returnChopsticks(int philosopherNumber) {
        // release chopstick[philosopherNumber] and chopstick[(philosopherNumber + 1) mod 5]
        System.out.println("Releasing chopstick[" + philosopherNumber + "] and chopstick[" + ((philosopherNumber + 1) % 5) + "]");
        chopstick[(philosopherNumber + 1) % 5].unlock();
        chopstick[philosopherNumber].unlock();

        // think for a random number of milliseconds
        int thinkTime = r.nextInt(MAX_THINK_TIME);
        System.out.println("Philosopher " + philosopherNumber + " is thinking for " + thinkTime + " milliseconds");
        try {
            Thread.sleep(thinkTime);
        } catch (InterruptedException ex) {
            System.out.println("Philosopher " + philosopherNumber + " thinkTime sleep was interrupted");
        }
    }
}


// implementation of the Dining Philosopher class
package cc;

public class DPhilosopher {
    private int dpNum;
    private DPServer dpServ;

    // value constructor for the DPhilosopher class
    public DPhilosopher(int num, DPServer d) {
        dpNum = num;
        dpServ = d;
    } // end DPhilosopher value constructor


    public void DPEatThink() {
        while (true) {
            // get ready to eat
            System.out.println("Philosopher " + dpNum + " is getting ready to eat");
            dpServ.takeChopsticks(dpNum);

            // finish eating
            System.out.println("Philosopher " + dpNum + " is finished eating");
            dpServ.returnChopsticks(dpNum);

        }

    }

    public static void main(String[] args) {
        DPServer dps = new DPServer();
        DPhilosopher dp[] = new DPhilosopher[5];
        Thread dpThread[] = new Thread[5];

        // Create and launch the DPhilosopher threads
        for (int i = 0; i < 5; i++) {
            dp[i] = new DPhilosopher(i, dps);
            final int finalI = i;
            dpThread[i] = new Thread(new Runnable() {
                @Override
                public void run() {
                    dp[finalI].DPEatThink();
                }
            });
            dpThread[i].start();
        }

    } // end main
}

most of the code is given ready except takeChopsticks() and returnChopsticks() method need to be changed and all I did was adding this:

chopstick[(philosopherNumber + 1) % 5].lock();
chopstick[philosopherNumber].lock();

and

chopstick[(philosopherNumber + 1) % 5].unlock();
chopstick[philosopherNumber].unlock();

I know this is not thread safe and this link also assures it. what is really myth is teacher is expecting us to solve this using DPServer#mutex lock, I can lock/unlock the mutex in takeChopsticks() and returnChopsticks() around locking and unlocking 2 locks(chopstick[philosopherNumber].lock(); and chopstick[(philosopherNumber + 1) % 5].lock();), but this makes deadlock.

I just do not see how to solve this using just one mutex ReentrantLock.

Can anyone help me on this?

Thanks in advance.

Answer 1

If you put a lock around getting the locks, like this:

// called by a philosopher when they wish to eat
public void takeChopsticks(int philosopherNumber) {
    // acquire chopstick[philosopherNumber] and chopstick[(philosopherNumber + 1) mod 5]
    System.out.println("Acquiring chopstick[" + philosopherNumber + "] and chopstick[" + ((philosopherNumber + 1) % 5) + "]");

    lockLock.lock();
    chopstick[philosopherNumber].lock();
    chopstick[(philosopherNumber + 1) % 5].lock();
    lockLock.unlock();

    // eat for a random number of milliseconds
    int eatTime = r.nextInt(MAX_EAT_TIME);
    System.out.println("Philosopher " + philosopherNumber + " is eating for " + eatTime + " milliseconds");
    try {
        Thread.sleep(eatTime);
    } catch (InterruptedException ex) {
        System.out.println("Philosopher " + philosopherNumber + " eatTime sleep was interrupted");
    }

} // end takeChopsticks

then only one philosopher can be in the process of picking up chopsticks at a time, but everything else continues to work as expected.

Another option is to change the indexing of the chopsticks so that odd-numbered philosophers always start by picking up the left chopstick and even-numbered philosophers always start by picking up the right chopstick. Since this is a homework assignment, I'll leave the details of how to do that as an exercise (it's really not that hard, an if-else statement makes it downright easy).