codebytes: Dining Philosophers Problem [Code] : [Java Concurrency]

https://www.cnblogs.com/grandyang/p/5394611.html

16.3 In the famous dining philosophers problem, a bunch of philosophers are sitting around a circular table with one chopstick between each of them. A philosopher needs both chopsticks to eat, and always picks up the left chopstick before the right one. A deadlock could potentially occur if all the philosophers reached for the left chopstick at the same time. Using threads and locks, implement a simulation of the dining philosophers problem that prevents deadlocks.

经典的哲学家聚餐问题，说是有一堆哲学家围着一个圆桌子坐着吃饭，每两个人之间都有一根筷子，每个人吃饭需要都需要左右两边的筷子，而且是先拿起左边的筷子，再拿右边的筷子，那么如果当所有的哲学家都拿着左边的筷子，那么就会产生死锁的情况。如果我们先不考虑死锁的问题，先来实现这个问题。我们可以把每个哲学家都当做一个线程，然后筷子被哲学家拿起后可以调用锁，当被放下后调用解锁，参见代码如下：

public class Chopstick {

    private Lock lock;
    public Chopstick() {
        lock = new ReentrantLock();
    }
    public void pickUp() {
        lock.lock();
    }
    public void putDown() {
        lock.unlock();
    }
}

public class Philosopher extends Thread {
    private final int maxPause = 100;
    private int bites = 10;
    private Chopstick left;
    private Chopstick right;
    private int index;
    
    public Philosopher(int i, Chopstick left, Chopstick right) {
        this.left = left;
        this.right = right;
    }
    
    public void eat() {
        System.out.println("Philosopher" + index + ": start eating");
        pickUp();
        chew();
        putDown();
        System.out.println("Philosopher " + index + ": done eating");
    }
    
    public void pickUp() {
        pause();
        left.pickUp();
        pause();
        right.pickUp();
    }
    
    public void chew() {
        System.out.println("Philosopher " + index + ": eating");
        pause();
    }
    
    public void pause() {
        try {
            int pause = (int)(Math.random() * maxPause);
            Thread.sleep(pause);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    
    public void putDown() {
        left.putDown();
        right.putDown();
    }
    
    public void run() {
        for (int i = 0; i < bites; ++i) {
            eat();
        }
    }
}

public class j {
    public static int size = 3;
    
    public static int leftOf(int i) {
        return i;
    }
    
    public static int rightOf(int i) {
        return (i + 1) % size;
    }
    
    public static void main(String[] args) {
        Chopstick[] chopsticks = new Chopstick[size + 1];
        for (int i = 0; i < size + 1; ++i) {
            chopsticks[i] = new Chopstick();
        }
        
        Philosopher[] philosophers = new Philosopher[size];
        for (int i = 0; i < size; ++i) {
            Chopstick left = chopsticks[leftOf(i)];
            Chopstick right = chopsticks[rightOf(i)];
            philosophers[i] = new Philosopher(i, left, right);
        }
        
        for (int i = 0; i < size; ++i) {
            philosophers[i].start();
        }
    }
}

上面的代码在执行中基本都会陷入死循环，因为发生了死锁的情况，所以我们应该想机制来避免死锁的发生，那么怎么做呢，我们首先想想死锁是怎么形成的，是因为每个人都拿着左边的筷子不放，又无法拿到右边的筷子，所以就一直僵持着，那么我们换个思路想想，如果每个人在拿了左筷子，发现没法取得右筷子后，就把左筷子放下，这样就可以避免死锁的形成。那么我们在Chopstik类中的pickUp函数中就应该使用tryLock()来代替lock，这样只有在有左筷子的时候才能锁上左筷子，而且在Philosopher类中的pickUp函数中，先判断能不能拿左筷子，不能拿直接返回false，能拿的话再来看能不能拿右筷子，不能拿的话，先把左筷子放下，再返回false，能拿的话返回true。这样在eat函数中先看pickUp是否能返回true，能返回的话再继续运行之后的东西，参见代码如下：

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

public class Chopstick {
    private Lock lock;
    public Chopstick() {
        lock = new ReentrantLock();
    }
    public boolean pickUp() {
        return lock.tryLock();
    }
    public void putDown() {
        lock.unlock();
    }
}

public class Philosopher extends Thread {
    private final int maxPause = 100;
    private int bites = 10;
    private Chopstick left;
    private Chopstick right;
    private int index;
    
    public Philosopher(int i, Chopstick left, Chopstick right) {
        index = i;
        this.left = left;
        this.right = right;
    }
    
    public void eat() {
        System.out.println("Philosopher" + index + ": start eating");
        if (pickUp()) {
            chew();
            putDown();
            System.out.println("Philosopher " + index + ": done eating");
        } else {
            System.out.println("Philosopher " + index + ": gave up on eating");
        }
    }
    
    public boolean pickUp() {
        pause();
        if (!left.pickUp()) {
            return false;
        }
        pause();
        if (!right.pickUp()) {
            left.putDown();
            return false;
        }
        pause();
        return true;
    }
    
    public void chew() {
        System.out.println("Philosopher " + index + ": eating");
        pause();
    }
    
    public void pause() {
        try {
            int pause = (int)(Math.random() * maxPause);
            Thread.sleep(pause);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    
    public void putDown() {
        left.putDown();
        right.putDown();
    }
    
    public void run() {
        for (int i = 0; i < bites; ++i) {
            eat();
        }
    }
}

public class j {
    public static int size = 3;
    
    public static int leftOf(int i) {
        return i;
    }
    
    public static int rightOf(int i) {
        return (i + 1) % size;
    }
    
    public static void main(String[] args) {
        Chopstick[] chopsticks = new Chopstick[size + 1];
        for (int i = 0; i < size + 1; ++i) {
            chopsticks[i] = new Chopstick();
        }
        
        Philosopher[] philosophers = new Philosopher[size];
        for (int i = 0; i < size; ++i) {
            Chopstick left = chopsticks[leftOf(i)];
            Chopstick right = chopsticks[rightOf(i)];
            philosophers[i] = new Philosopher(i, left, right);
        }
        
        for (int i = 0; i < size; ++i) {
            philosophers[i].start();
        }
    }

codebytes: Dining Philosophers Problem [Code] : [Java Concurrency]
For a deadlock to occur, the following four conditions must be met: 
1. Mutual exclusion. At least one resource used by the tasks must not be shareable. In this case, a Chopstick can be used by only one Philosopher at a time. 
2. At least one task must be holding a resource and waiting to acquire a resource currently held by another task. That is, for deadlock to occur, a Philosopher must be holding one Chopstick and waiting for another one. 
3. A resource cannot be preemptively taken away from a task. Tasks only release resources as a normal event. Our Philosophers are polite and they don’t grab Chopsticks from other Philosophers. 
4. A circular wait can happen, whereby a task waits on a resource held by another task, which in turn is waiting on a resource held by another task, and so on, until one of the tasks is waiting on a resource held by the first task, thus gridlocking everything.

Now to make the code deadlock free we can make the last philosopher get the left chopstick first and then the right chopstick so that the circular chain is broken. The deadlock never occurs now. There are many other ways for avoiding the deadlock in this case, this is just one of them.


Exercise: Change DeadlockingDiningPhilosophers.java so that when a philosopher is done with its chopsticks, it drops them into a bin. When a philosopher wants to eat, it takes the next two available chopsticks from the bin. Does this eliminate the possibility of deadlock? Can you reintroduce deadlock by simply reducing the number of available chopsticks? 

Does this eliminate the possibility of deadlock? No. Consider the case when each philosopher takes a single chopstick from the bin so that now the bin contains 0 chopsticks. Nobody has the second chopstick to eat the spaghetti.

Java code: https://orajavasolutions.wordpress.com/2014/05/05/dining-philosoper-problem-in-java/

enum Status {

    THINKING, HUNGRY, EATING

}

public class DiningPhilosopher {

    public static void main(String a[])

    {

        Chopstick cs[]=new Chopstick[5];

         

        for(int i=0;i<5;i++)

            cs[i] = new Chopstick();

         

        Thread thPhilosoper[] = new Thread[5];

        for(int i=0;i<5;i++)

        {

            Philosopher ph = new Philosopher(i+1,cs);

            thPhilosoper[i] = new Thread(ph);

        }

        for(int i=0;i<5;i++)

        {

            thPhilosoper[i].start();

        }

    }

}

class Chopstick

{

    private final Lock cslock = new ReentrantLock();

     

     

    public Lock getCslock() {

        return cslock;

    }

}

class Philosopher implements Runnable

{

    private int n;

    private Chopstick cs[];

    private Status status;

     

    public  Philosopher(int n, Chopstick [] cs)

    {

        this.n = n;

        this.cs = cs;

        this.status = Status.THINKING;

    }

     

    public void run()

    {

        Lock csreqd1, csreqd2;

         

        csreqd1 = cs[n%5].getCslock();

        csreqd2 = cs[(n-1)%5].getCslock();

         

        while(true)

        {

                status = Status.HUNGRY;

                System.out.printf("Philosoper %d is hungry and waiting for chopsticks %d and %d \n",n,(n%5),(n-1)%5);

                if(csreqd1.tryLock())

                {

                    if(csreqd2.tryLock())

                    {

                        System.out.printf("Philosoper %d got chopsticks %d and %d \n",n,(n%5),(n-1)%5);

                        status = Status.EATING;

                    }

                    else

                    {

                        csreqd1.unlock();

                    }

                }

                 

                if(status == Status.HUNGRY)

                {

                    try

                    {

                        TimeUnit.SECONDS.sleep((long)(Math.random()*10));

                    }

                    catch(InterruptedException iex)

                    {

                        iex.printStackTrace();

                    }

                }

            if(status == Status.EATING)

            {        

                eat();

                csreqd1.unlock();

                csreqd2.unlock();

                System.out.printf("Philosoper %d has finished eating and relesed chopsticks %d and %d \n",n,(n%5),(n-1)%5);

                status = Status.THINKING;

                think();

            }

        }

    }

    private void think()

    {

        try

        {

            System.out.printf("Philosoper %d is thinking.\n",n);

            TimeUnit.SECONDS.sleep((long)(Math.random()*10));

        }

        catch(InterruptedException iex)

        {

            iex.printStackTrace();

        }

    }

     

    private void eat()

    {

        try

        {

            System.out.printf("Philosoper %d is eating rice\n",n);

            TimeUnit.SECONDS.sleep((long)(Math.random()*10));

        }

        catch(InterruptedException iex)

        {

            iex.printStackTrace();

        }

    }

}

http://everythingcomputerscience.com/projects/java_programs/DiningPhilosophers.txt

public class DiningPhilosophers {
 // The number of philosophers
 private static final int NUM_PHILOSOPHERS = 5;
 
 /**
  * Test the dining philosophers solution
  * @param args Not used
  */
 public static void main (String[] args) {
  // Model each chopstick with a lock
  Lock[] chopsticks = new ReentrantLock[NUM_PHILOSOPHERS];
  
  for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
   chopsticks[i] = new ReentrantLock();
  }
  
  // Create the philosophers and start each running in its own thread.
  Philosopher[] philosophers = new Philosopher[NUM_PHILOSOPHERS];
  
  for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
   philosophers[i] = new Philosopher(i, chopsticks[i], chopsticks[(i+1)%NUM_PHILOSOPHERS]);
   new Thread(philosophers[i]).start();
  }
 }

}

/**
 * A philosopher alternates between thinking and eating.  To eat, the philosopher needs to pick
 * up the left chopstick and then the right chopstick sequentially.  The phillosopher shares 
 * chopsticks with its neighbors, so it cannot eat at the same time as either neighbor.
 * 
 * @author Barbara Lerner
 * @version Oct 5, 2010
 *
 */
class Philosopher implements Runnable {
 // Used to vary how long a philosopher thinks before eating and how long the
 // philosopher eats
 private Random numGenerator = new Random();
 
 // The philosopher's unique id
 private int id;
 
 // The chopsticks this philosopher may use
 private Lock leftChopstick;
 private Lock rightChopstick;
 
 /**
  * Constructs a new philosopher
  * @param id the unique id
  * @param leftChopstick chopstick to the left
  * @param rightChopstick chopstick to the right
  */
 public Philosopher (int id, Lock leftChopstick, Lock rightChopstick) {
  this.id = id;
  this.leftChopstick = leftChopstick;
  this.rightChopstick = rightChopstick;
 }
 
 /**
  * Repeatedly think, pick up chopsticks, eat and put down chopsticks
  */
 public void run() {
  try {
   while (true) {
    think();
    pickUpLeftChopstick();
    pickUpRightChopstick();
    eat();
    putDownChopsticks();
   }
  } catch (InterruptedException e) {
   System.out.println("Philosopher " + id + " was interrupted.\n");   
  }
 }

 /**
  * Lets a random amount of time pass to model thinking.
  * @throws InterruptedException
  */
 private void think() throws InterruptedException {
  System.out.println("Philosopher " + id + " is thinking.\n");
  System.out.flush();
  Thread.sleep (numGenerator.nextInt(10));
 }
 
 /** 
  * Locks the left chopstick to signify that this philosopher is holding it
  */
 private void pickUpLeftChopstick() {
  leftChopstick.lock();
  System.out.println("Philosopher " + id + " is holding 1 chopstick.\n");
  System.out.flush();
 }

 /** 
  * Locks the right chopstick to signify that this philosopher is holding it
  */
 private void pickUpRightChopstick() {
  rightChopstick.lock();
 }

 /**
  * Lets a random amount of time pass to model eating.
  * @throws InterruptedException
  */
 private void eat() throws InterruptedException {
  System.out.println("Philosopher " + id + " is eating.\n");
  System.out.flush();
  Thread.sleep (numGenerator.nextInt(10));
 }
 
 /**
  * Releases the locks on both chopsticks to model putting them down so the
  * other philosophers can use them.
  */
 private void putDownChopsticks() {
  leftChopstick.unlock();
  rightChopstick.unlock();
 }
}

Read full article from codebytes: Dining Philosophers Problem [Code] : [Java Concurrency]