哲学家进餐问题

1.问题描述：

哲学家进餐问题描述有五个哲学家，他们的生活方式是交替地进行思考和进餐，哲学家们共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五支筷子，平时哲学家进行思考，饥饿时便试图取其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐，该哲学家进餐完毕后，放下左右两只筷子又继续思考。

约束条件

(1)只有拿到两只筷子时，哲学家才能吃饭。

(2)如果筷子已被别人拿走，则必须等别人吃完之后才能拿到筷子。

(3)任一哲学家在自己未拿到两只筷子吃完饭前，不会放下手中已经拿到的筷子。

2.求解方法

(1).信号量的设置

放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用，为了实现对筷子的互斥访问，可以用一个信号量表示筷子，由这五个信号量构成信号量数组。

semaphore chopstick[5] = {1,1,1,1,1};while(true){

/*当哲学家饥饿时，总是先拿左边的筷子，再拿右边的筷子*/ wait(chopstick[i]);

wait(chopstick[(i+1)%5]);

// 吃饭

/*当哲学家进餐完成后，总是先放下左边的筷子，再放下右边的筷子*/ signal(chopstick[i]);

signal(chopstick[(i+1)%5]);}

上述的代码可以保证不会有两个相邻的哲学家同时进餐，但却可能引起死锁的情况。

假如五位哲学家同时饥饿而都拿起的左边的筷子，就会使五个信号量chopstick都为0，当他们试图去拿右手边的筷子时，都将无筷子而陷入无限期的等待。

(2)避免死锁

策略一

原理：至多只允许四个哲学家同时进餐，以保证至少有一个哲学家能够进餐，最终总会释放出他所使用过的两支筷子，从而可使更多的哲学家进餐。定义信号量count，只允许4个哲学家同时进餐，这样就能保证至少有一个哲学家可以就餐。

semaphore chopstick[5]={1,1,1,1,1};

semaphore count=4; // 设置一个count，最多有四个哲学家可以进来void philosopher(int i){

while(true) {

think();

wait(count); //请求进入房间进餐 当count为0时 不能允许哲学家再进来了 wait(chopstick[i]); //请求左手边的筷子

wait(chopstick[(i+1)%5]); //请求右手边的筷子 eat();

signal(chopstick[i]); //释放左手边的筷子

signal(chopstick[(i+1)%5]); //释放右手边的筷子 signal(count); //退出房间释放信号量 }}

策略二

原理：仅当哲学家的左右两支筷子都可用时，才允许他拿起筷子进餐。可以利用AND 型信号量机制实现，也可以利用信号量的保护机制实现。利用信号量的保护机制实现的思想是通过记录型信号量mutex对取左侧和右侧筷子的操作进行保护，使之成为一个原子操作，这样可以防止死锁的出现。描述如下：

semaphore chopstick[5]={1,1,1,1,1};void philosopher(int i)

{

while(true) {

/* 这个过程中可能只能由一个人在吃饭 */ think();

wait(mutex); // 保护信号量

wait(chopstick[(i+1)%5]); // 请求右手边的筷子 wait(chopstick[i]); // 请求左手边的筷子 signal(mutex); // 释放保护信号量 eat();

signal(chopstick[(i+1)%5]); // 释放右手边的筷子 signal(chopstick[i]); // 释放左手边的筷子 }}

策略三

原理：规定奇数号的哲学家先拿起他左边的筷子，然后再去拿他右边的筷子；而偶数号的哲学家则先拿起他右边的筷子，然后再去拿他左边的筷子。按此规定，将是1、2号哲学家竞争1号筷子，3、4号哲学家竞争3号筷子。即五个哲学家都竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一个哲学家能获得两支筷子而进餐。

semaphore chopstick[5]={1,1,1,1,1};void philosopher(int i){

while(true) {

think();

if(i%2 == 0) //偶数哲学家，先右后左。 {

wait (chopstick[(i + 1)%5]) ; wait (chopstick[i]) ; eat();

signal (chopstick[(i + 1)%5]) ; signal (chopstick[i]) ; }

else //奇数哲学家，先左后右。 {

wait (chopstick[i]) ;

wait (chopstick[(i + 1)%5]) ; eat();

signal (chopstick[i]) ;

signal (chopstick[(i + 1)%5]) ; } }

3.代码实现

用java代码实现第二种方法：

public class ThreadTest{

public static void main(String[] args) { Fork fork = new Fork();

new Philosopher(\"0\ new Philosopher(\"1\ new Philosopher(\"2\ new Philosopher(\"3\ new Philosopher(\"4\ }

}

class Philosopher extends Thread{ private String name; private Fork fork;

public Philosopher(String name, Fork fork) { super(name);

this.name = name; this.fork = fork; }

@Override

public void run() { while (true){ thinking();

fork.takeFork(); eating();

fork.putFork(); } }

public void eating(){

System.out.println(\"I am Eating:\"+name); try {

sleep(1000);//模拟吃饭，占用一段时间资源 } catch (InterruptedException e) {

// TODO Auto-generated catch block e.printStackTrace(); } }

public void thinking(){

System.out.println(\"I am Thinking:\"+name); try {

sleep(1000);//模拟思考

} catch (InterruptedException e) {

// TODO Auto-generated catch block e.printStackTrace(); } }

public Fork getFork() { return fork; }

public void setFork(Fork fork) { this.fork = fork; }}

class Fork{

/*5只筷子，初始为都未被用*/

private boolean[] used={false,false,false,false,false,false}; public synchronized void takeFork(){

String name = Thread.currentThread().getName(); int i = Integer.parseInt(name); while(used[i]||used[(i+1)%5]){ try {

wait();//如果左右手有一只正被使用，等待 } catch (InterruptedException e) {

// TODO Auto-generated catch block e.printStackTrace(); } }

used[i ]= true;

used[(i+1)%5]=true; }

public synchronized void putFork(){

String name = Thread.currentThread().getName(); int i = Integer.parseInt(name); used[i]= false;

used[(i+1)%5]=false;

notifyAll();//唤醒其他线程 }}