PV经典问题之哲学家问题

问题描述

(由Dijkstra首先提出并解决)5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子， 每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左 边和右边的两支筷子，思考时则同时将两支筷子放回原处。如何保证哲学家们的动作 有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子。

1. 关系分析。系统中有5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系。
2. 整理思路。这个问题中只有互斥关系，但与之前 遇到的问题不同的事，每个哲学家进程需要同时 持有两个临界资源才能开始吃饭。如何避免临界 资源分配不当造成的死锁现象，是哲学家问题的精髓。

解决⽅法有两个，⼀个是让他们同时拿两个筷⼦:⼆是对每个哲学家的动作制定规则，避免饥饿或者死锁 。

⽅法⼀： ⾄多只允许四位哲学家同时去拿左筷⼦，最终能保证⾄少有⼀位哲学家能进餐，并在⽤完后释放两只筷⼦供他⼈使⽤。

设置⼀个初值为 4 的信号量 r，只允许 4 个哲学家同时去拿左筷⼦，这样就能保证⾄少有⼀个哲学家可以就餐，不会出现饿死和死锁的现象。

原理：⾄多只允许四个哲学家同时进餐，以保证⾄少有⼀个哲学家能够进餐，最终总会释放出他所使⽤过的两⽀筷⼦，从⽽可使更多的哲学家进餐。

代码如下：

semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore r = 4;
Pi() { 
	while (1) {
		P(r); //请求进餐
		P(chopstick[i]); //请求左⼿边的筷⼦
		P(chopstick[(i + 1) % 5]); //请求右⼿边的筷⼦
		eat;
		V(chopstick[i]); //放回左边筷⼦
		V(chopstick[(i + 1) % 5]); //放回右边筷⼦
		V(r);
		think;
	}
}

⽅法⼆： 仅当哲学家的左右⼿筷⼦都拿起时才允许进餐。 原理：多个临界资源，要么全部分配，要么⼀个都不分配，因此不会出现死锁的情形。

代码片段：

semaphore chopstick[5]={1,1,1,1,1};
semaphore mutex = 1; //互斥地取筷子
Pi (){              //i号哲学家的进程 
	while(1){
	P(mutex); 
	P(chopstick[i]); //拿左 
	P(chopstick[(i+1)%5]); //拿右 
	V(mutex); 
	吃饭… 
	V(chopstick[i]); //放左 
	V(chopstick[(i+1)%5]); //放右 
	思考…
	}
}

⽅法三： 规定奇数号哲学家先拿左筷⼦再拿右筷⼦，⽽偶数号哲学家相反。

原理：按照下图，将是 2,3 号哲学家竞争 3 号筷⼦，4,5 号哲学家竞争 5 号筷⼦。1 号哲学家不需要竞争。最后总会有⼀个哲学家能获得两⽀筷⼦⽽进餐。

代码如下：

semaphore chopstick[5] = {1, 1, 1, 1, 1};
Pi() {
  while (1) {
	if (i % 2 == 0) { //偶数号哲学家
	P(chopstick[(i + 1) % 5]); //请求右⼿边的筷⼦ 
	P(chopstick[i]); //请求左⼿边的筷⼦
	} else { //奇数号哲学家
	P(chopstick[i]); //请求左⼿边的筷⼦
	P(chopstick[(i + 1) % 5]); //请求右⼿边的筷⼦
	}
	eat;
	V(chopstick[(i + 1) % 5]); //放回右边筷⼦
	V(chopstick[i]); //放回左边筷⼦
	think;
	}
}

总之，哲学家进餐问题的关键在于解决进程死锁。 这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有 两个临界资源，因此就有“死锁”问题的隐患。