admin 管理员组文章数量: 887021
原博客网址：哲学家就餐问题-C语言讲解
哲学家问题是操作系统中同步互斥的经典问题。通常使用信号量，管程的方式。这篇文章将会简要介绍问题的定义和类似服务生解法。并且用c语言实现解法。
问题描述：
五个哲学家围绕坐在一个圆形餐桌前，桌上放着五支筷子，每两个哲学家之间放一个筷子。哲学家的动作包括就餐和思考。思考不需要拿筷子，而就餐需要拿到两个筷子才能就餐。两个相邻的哲学家需要共享一个筷子（这个筷子就是一个共享资源）。
这种情况可能产生死锁，比如每个哲学家都拿着左手的筷子，永远都在等右边的筷子（或者相反）。
如何保证哲学家的动作有序进行，使得总有哲学家能拿到两个叉子就餐？
在哲学家问题中，哲学家代表着"线程"，而叉子代表着"共享的对象"(shared object)。哲学家问题在操作系统中的真正含义是"一个线程需要两个共享的对象来完成一些工作"。
要求1:互斥（mutual exclusion）
哲学家问题的有两条互斥前提
- 当一个人在进餐时，别人不能偷走这个人的筷子。（难不成从这个人手上抢过去吗？）
- 一个筷子最多只能被一个人使用。
所以对于一个哲学家来说，当他饿了的时候，他就要检查是否有人在使用他需要的筷子，如果有，那么他等待那人使用完才能获得需要的筷子。在等待的过程中，他不会放下手上已有的筷子。如果他需要的筷子没人在使用，他就获得了指定的筷子。当他结束当前吃的动作（吃了几口就思考。。。），就放下手上所有的筷子。
上图用信号量的方式来保证了互斥条件：chopstick数组是一个信号量数组，每一信号量初始值为1（所以称为binary semaphore，但是在上图中没有表现出来），每个哲学家在调用take_chopsticks函数时其实是在调用信号量的wait函数：将信号量减一，如果信号量运算后的结果小于零则阻塞这个哲学家线程。直到获得了这个筷子的哲学家进程放下筷子，调用信号量post函数唤醒阻塞了的哲学家进程。
死锁情况
如果符合了互斥的要求，可能会出现死锁的情况：
- 每个哲学家在同一时刻完成思考并且都拿到了自己右手边的筷子。在代码中，就是每个线程（或线程）都执行到了第四行代码。程序陷入循环等待过程中。
要求2:同步（Synchronization）
为了解决哲学家问题中的死锁情况。我们需要实现同步。
我们可以给哲学家们设置一些"协议"。比如当任意一个哲学家要进餐时检查所需筷子是否可用，如果不能够获得所有需要的筷子，就放下来。然后随机等待一段时间。时间到后，继续尝试。
忙等待
我们在上面设置的"协议"还是会出现潜在问题的：所有的哲学家同时拿起右手的筷子，放下计时同一段时间，继续拿起来。等待。所有哲学家线程starvation了（以上的情况发生的可能性看起来是很小，但是放到实际情况，发生的情况还是不算少见的）
随便设置一个协议，可能会造成效率低下。或着忙等待。
总结
- 用信号量方法来控制筷子满足互斥条件可能会造成死锁。
- 用同步来解决死锁，还是可能造成忙等待，没有死锁，但还是没有哲学家吃到饭。
所以仅仅是通过信号量互斥和同步，无法完全解决哲学家问题。
解决问题（类似服务生解法）
思路
- 当一个哲学家在吃饭的时候，与她相邻的哲学家不能吃饭。
- 同一时刻，只有一个哲学家可以检查是否满足相邻两个哲学家不在吃饭的条件。（在一些解答中用服务员这个概念来表示。餐桌上只有一个服务员，而且只有服务员有权利指派哲学家拿筷子。服务员只帮哲学家解决餐具的问题，一旦服务的哲学家拿到筷子，服务员就可以服务其他的哲学家）
- 如果满足，则该哲学家获取手边两个筷子就餐。其他的哲学家可以开始检查条件。
- 如果不满足，则将自己挂起，等待相邻的哲学家放下筷子后通知自己。再重复步骤2的检查过程。
- 当哲学家用餐结束。放下两支筷子，通知唤醒相邻的哲学家。
下图用信号量和互斥锁实现了思路里描述的过程
//这段代码还不能直接运行。think(),wait(),post()和eat()尚未定义。
#define N 5
#define LEFT (N+i-1)%N
#define RIGHT (i+1)%N
int state[N];/*存储哲学家状态的数组，EATING,THINKING,HUNGRY*/
semaphore mutex = 1; /*一次只能有一个哲学家操作存储哲学家状态的数组*/
semaphore p[N]={0}; /*哲学家锁,一开始每个哲学家都不占有资源，所以sema都为0，如果现在一个哲学家调用sema_wait(),会被马上阻塞*/
void take_chopsticks(int i){
wait(&mutex);
state[i] = HUNGRY;
scheduler(i);//Critical Section，关键区域。
post(&mutex);
wait(&p[i]);
}
void take_chopsticks(int i){
wait(&mutex);
state[i] = HUNGRY;
scheduler(i);
post(&mutex);
wait(&p[i]);
}
void scheduler(int i){
if(state[i]==HUNGRY && state[LEFT]!= EATING && state[RIGHT]!=EATING){
state[i]=EATING;
post(&p[i]);
}
}
void philosopher(int i){
think();//也许是在思考，也许是在发呆
take_chopsticks(i);//第i个哲学家想要拿筷子
eat();//吃饭
put_chopsticks();//放下筷子
}
常见疑问
-
Hungry 的意义表示你不在思考，但是因为条件不足所以也不能就餐。本质上是线程中blocked（阻塞）的状态。
-
在section_entry中，看到captain觉得很奇怪，因为如果一旦不满足if中的条件，当前线程会被堵塞。看起来没人来恢复它。但是看到section_exit就知道这个代码设计的精妙之处了。
-
mutex是什么？保证scheduler这个critical section的同步的互斥锁。
参考
- 南方科技大学2019春季操作系统课Synchronization(2)
- 学堂在线：清华操作系统课
- 理解Semaphore及其用法详解
- 哲学家就餐问题
- 三种不同的方式解决‘’哲学家就餐‘’这个经典的问题
版权声明：本文标题：哲学家就餐问题-C语言讲解 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1727379277h1111365.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论