哲学家进餐问题的研究
计算机操作系统
姓 名： 陆文静 学 号： 1310750012 指导老师： 杨婷婷 专业班级： 软件工程1301班 完成时间： 2015年5月4日
哲学家进餐问题研究
摘要：
一、问题的描述
哲学家就餐问题是一种典型的同步问题，它是由Dijkstra提出并解决的。该问题描述如下：有五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替的进行思考和进餐。设五个哲学家分别编号为A，B，C，D，E，桌子上放着五只筷子，筷子分别编号为0，1，2，3，4，桌子中央有一盘饭菜，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐毕，放下筷子继续思考。
二、解决问题的方案 1、算法描述
semaphore chopstick[5]={1，1，1，1，1}; do{
wait(room);
wait(chopstick[i]);
wait(chopstick[(i+1)%5]); eat();
signal(chopstick[i]);
signal(chopstick[(i+1)%5]); signal(room); Think;
} while[ture];
以上描述中，可保证不会有两个相邻的哲学家同时进餐，但却有可能引起死锁。假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量
chopstick均为0；当他们试图拿右边的筷子时，豆浆因无筷子可拿而无限期地等待，进入死锁状态。
2、改进算法描述
描述一种没有人饿死算法，考虑了四种实现的方式（A、B、C、D）
A．原理：至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。以下将room 作为信号量，只允许4 个哲学家同时进入餐厅就餐，这样就能保证至少有一个哲学家可以就餐，而申请进入餐厅的哲学家进入room 的等待队列，根据FIFO 的原则，总会进入到餐厅就餐，因此不会出现饿死和死锁的现象。 伪码：semaphore chopstick[5]={1，1，1，1，1};
semaphore room=4;
void philosopher(int i) {
while(true)
{
think();
wait(room); //请求进入房间进餐
wait(chopstick[i]); //请求左手边的筷子
wait(chopstick[(i+1)%5]); //请求右手边的筷子
eat();
signal(chopstick[(i+1)%5]); //释放右手边的筷子 signal(chopstick[i]); //释放左手边的筷子 signal(room); //退出房间释放信号量room } }
B．原理：仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。
方法1：利用AND 型信号量机制实现：根据课程讲述，在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配，因此不会出现死锁的情形。当某些资源不够时阻塞调用进程;由于等待队列的存在，使得对资源的请求满足FIFO 的要求，因此不会出现饥饿的情形。 伪码：semaphore chopstick[5]={1，1，1，1，1};
void philosopher(int I) {
while(true) {
think();
Swait(chopstick[(I+1)]%5,chopstick[I]); eat();
Ssignal(chopstick[(I+1)]%5,chopstick[I]); } }
方法2：利用信号量的保护机制实现。通过信号量mutex对eat()之前的取左侧和右侧筷子的操作进行保护，使之成为一个原子操作，这样可以防止死锁的出现。 伪码：semaphore mutex = 1 ;
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]); } }
C、原理：规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列，根FIFO原则，则先申请的哲学家会较先可以吃饭，因此不会出现饿死的哲学家。
伪码：semaphore chopstick[5]={1，1，1，1，1};
void philosopher(int i) {
while(true) {
think();
if(i%2 == 0) //偶数哲学家，先右后左。 {
wait (chopstick[ i + 1 ] mod 5) ; wait (chopstick[ i]) ; eat();
signal (chopstick[ i + 1 ] mod 5) ; signal (chopstick[ i]) ; }
else //奇数哲学家，先左后右。 {
wait (chopstick[ i]) ;
wait (chopstick[ i + 1 ] mod 5) ; eat();
signal (chopstick[ i]) ;
signal (chopstick[ i + 1 ] mod 5); } }
* 进一步改进B方法一的操作
算法设计了一个test过程，如果通过了text过程，线程可进入吃饭过程，否则让，线程进入等待状态。通过text过程，则该哲学家左右筷子设置为不可用标志，阻止其相邻哲学家通过text过程，这实际上表示该哲学家需要的两只筷子已指定给他，即预先分配全部资源，公用信号量mutex作用的范围仅限text过程，大大小于改进之前的方法。 改进算法描述如下：
Semabore chopstick[0]=chopstick[1]=chopstick[2]=chopstick[3]= chopstick[4]=1; Semaphore mutex=1;
Boolean chop[0]=chop[1]=chop[2]=chop[3]=chop[4]=ture; Philosopher i’ While(ture){ 思考;
While(!Test(i)){等待};//如果测试不通过，处于等待状态，知道测试通过
P(chopstick[i]);
P(chopstick[(i+1)%5]); 吃饭;
V(chopstick[i]); V(chopstick[i+1]);
chop[i]=chop[(i+1)%5]=ture;//设置这两只筷子可用标志通知；//通知从等待状态进入测试状态 }
boolean test(int i) {
P(mutex);//公用信号量，用于测试过程的互斥 if(chop[i]&&chop[(i+1)%5]){
Chop[i]=chop[(i+1)%5]=false;//设置这两只筷子不可用标志 Return true; } else {
Return false; }
V(mutex); }
三、总结
1、算法的总结
哲学家就餐问题是个经典的同步问题，题中的演示哲学家从来不交谈，这就可能产生死锁，每个哲学家都拿着左手的餐叉，永远都在等右边的餐叉（或者相反）。即使没有死锁，也有可能发生资源耗尽。例如，假设规定当哲学家等待另一只餐叉超过五分钟后就放下自己手里的那一只餐叉，并且再等五分钟后进行下一次尝试。这个策略消除了死锁（系统总会进入到下一个状态），但仍然有可能发生“活锁”。如果五位哲学家在完全相同的时刻进入餐厅，并同时拿起左边的餐叉，那么这些哲学家就会等待五分钟，同时放下手中的餐叉，再等五分钟，又同时拿起这些餐叉。
在实际的计算机问题中，缺乏餐叉可以类比为缺乏共享资源。一种常用的计算机技术是资源加锁，用来保证在某个时刻资源只能被一个程序或一段代码访问。当一个程序想要使用的资源已经被另一个程序锁定，它就等待资源解锁。当多个程序涉及到加锁的资源时，在某些情况下就有可能发生死锁。例如，某个程序需要访问两个文件，当两个这样的程序各锁了一个文件，那它们都在等待对方解锁另一个文件，而这永远不会发生。
[解法] 服务生解法
一个简单的解法是引入一个餐厅服务生，哲学家必须经过他的允许才能拿起餐叉。因为服务生知道哪只餐叉正在使用，所以他能够作出判断避免死锁。