经典同步问题(哲学家进餐等)

红河学院课程设计报告操作系统课程名称：6个哲学家进餐设计题目：院系：工学院专业：计算机科学与技术班级：11计科班曹永前设计者：学号：201101030466指导教师：韦相2013 年 5 月26 日1. 问题描述：一个房间内有6个哲学家，他们的生活就是思考和进食。

哲学家思考后，过一定的时间就会饥饿，饥饿之后就想吃饭，吃饭后再思考。

房间里有一张圆桌，桌子周围放有五把椅子，分别属于五位哲学家每两位哲学家之间有一把叉子，哲学家进食时必须同时使用左右两把叉子。

2. 问题分析1、写出哲学家进餐的算法描述。

用六只筷子解决需要用两双筷子来进餐的六个哲学家,由于每个哲学家都需要其周围的两只筷子,所以筷子是公用信号量,这久需要设置一个互斥信号量,来使六个哲学家互斥的进餐.具体做法将六个信号量设置为0-5,用pv 源于来控制信号量,并将六个哲学家分别编号为0-5.经过仔细分析我们会发现,有这样一个问题存在,就是当每个哲学家都申请到他周围的一只筷子时,由于他们每人都只有一只筷子无法进餐,没有进餐他们就无法释放他们已经得得到的筷子,这样是进餐出于一种僵局,无法继续下去,这就是死锁问题.2、死锁问题的分析与具体的解决方法。

死锁问题就是当每个哲学家都拿到且只拿到一只筷子,这样每个哲学家都无法进餐,也无法释放所得到的筷子,所以解决死锁我们就要从这入手,就是怎样去预防使所有哲学家不要同时去申请他们同一方向的筷子.根据这解决死锁的方法有以下几种:a.每一次最多只能有五个哲学家申请进餐.这样其中的一个哲学家就能申请到两只筷子,就能够进餐,再将筷子释放给其他哲学家进餐.b.用AND信号量,就是哲学家需同时申请其左右两边的筷子,两边都有资源的时候,才能让这个哲学家得到资源,这样哲学家只要申请到筷子就能进餐, 再将筷子释放给其他哲学家进餐.c.用管程机制来实现。

d.我们前面已经将每个哲学家都分配了一个编号,我们可以编号为奇数的哲学家首先去申请其左边的筷子,再去申请其右手边的筷子;让编号为偶数的哲学家,先去申请其右边的筷子,再去申请其左边的筷子.我们可以看出编号为奇数的哲学家左边,与编号为偶数的哲学家的右边为同一只筷子,当其中一个哲学家拿到此筷子后,他另一边的筷子也是空闲的,这样就能避免死锁.主程序中我使用的是最后一种避免死锁的方法.3、用C程序实现哲学家进餐。

哲学家进餐问题问题描述：有5个哲学家共用一张圆桌，分别坐在周围的5张椅子上。

在桌上有5支筷子和5个碗，他们的生活方式是交替的进行思考和进餐。

平时，一个哲学家进行思考，饥饿时便试图取用他左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。

进餐完毕放下筷子继续思考。

解决方法：1)至多只允许4位哲学家同时去拿他左边的筷子，最终能保证至少有一个哲学家能够进餐，并在用毕时能够释放他用过的两支筷子，从而使更多的哲学家能够进餐。

2)规定奇数号哲学家先拿他左边的筷子然后再拿右边的筷子；而偶数号哲学家则与此相反。

3)仅当哲学家的左右两边的筷子都能用时才允许他拿起筷子进餐。

用第3）种方法解决代码如下：#include <stdio.h>#include <stdlib.h>#include <windows.h>#include <time.h>#define PHILOSOPHERS 5HANDLE gchopStick[PHILOSOPHERS];DWORD WINAPI PhilosopherThread(LPVOID pVoid) {HANDLE myChopsticks[2];DWORD result;int iPhilosopher = (int) pVoid;int iLeftChopstick = iPhilosopher;int iRightChopstick = iLeftChopstick + 1;if (iRightChopstick > PHILOSOPHERS-1)iRightChopstick = 0;myChopsticks[0] = gchopStick[iLeftChopstick];myChopsticks[1] = gchopStick[iRightChopstick];result=WaitForMultipleObjects(2,myChopsticks,TR UE,-1);printf("the %d PHILOSOPHER begin to eat\n",iPhilosopher);Sleep(200);printf("the %d PHILOSOPHER finishedeating",iPhilosopher);ReleaseMutex(myChopsticks[0]);ReleaseMutex(myChopsticks[1]);return EXIT_SUCCESS;}int main(int argc,char *argv[]){DWORD dwThreadId,wait_for_all;HANDLE hThread[PHILOSOPHERS];for (int i=0; i < PHILOSOPHERS; i++){gchopStick[i] = CreateMutex(NULL, FALSE, NULL);}for (i = 0; i < PHILOSOPHERS; i++)hThread[i] = CreateThread(NULL, 0, PhilosopherThread, (LPVOID) i, 0, &dwThreadId);wait_for_all=WaitForMultipleObjects(PHILOSOPHER S,hThread,TRUE,-1);printf("All PHILOSOPHERs finished eating\n");return 0; }。

模拟5位哲学家进餐的问题2008-04-21 21:241）问题描述学操作系统的进程同步都要涉及到三个经典问题：生产者-消费者问题、读者-写者问题和哲学家就餐问题。

下面来介绍一下哲学家就餐问题：哲学家就餐问题中，一组哲学家围坐在一个圆桌旁，每个哲学家的左边都只有一只筷子（当然他的右边也有一只筷子，但是这是他右边哲学家的左边的筷子），他们吃完了就思考，思考了一会就会饿，饿了就想吃，然而，为了吃饭，他们必须获得左边和右边的筷子。

当每个哲学家只拿有一只筷子的时候，会坐者等另一只筷子，在每个哲学家都只拿一个筷子的时候，就会发生死锁。

用C或C++, 来模拟5位哲学家进餐的问题。

2）关于源码的一点说明：vc6下源码测试通过运行，不过不能模拟死锁为每个哲学家使用POSIX线程(pthread)建立独立的线程(有独立的id)，用互斥(叉子其他哲学家使用时，另一个哲学家不能使用)和条件(哲学家饿了才尝试去得到叉子，得到相邻的左右两把叉子才能进餐)来分到叉子。

关键事件：1. 哲学家饿了就要尝试去得到叉子。

2. 哲学家得到相邻的左右两把叉子才可以进餐3. 吃完了就要释放两把叉子每个事件发生就打印一行。

并用gettimeofday()显示毫秒。

A. 用'X' 表示哲学家在进餐B. 用'O' 表示哲学家在思考C. 用'!' 表示哲学家饿了例子：1 2 3 4 50 ms: O O O O O95 ms: ! O O O O95 ms: X O O O O214 ms: X O O O !327 ms: X O O ! !328 ms: X O O X !444 ms: O ! O O !444 ms: O X O O X(注意：肯定不会有两个X出现在相邻的列中)程序在运行“50次成功进餐”发生后停止。

哲学家在“进餐”和“思考”的“时间周期”是一个0.1到0.5之间的随机数字。

课程设计题目进程同步模拟设计—哲学家就餐学院计算机科学与技术专业计算机科学与技术班级计算机姓名指导教师20011 年 1 月19 日需求分析1.1问题描述有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子，即共5只筷子。

每个哲学家的行为是思考和进餐。

为了进餐，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子。

思考时则同时将两支筷子放回原处（此图中以叉子代表筷子）规则：只有拿到两只筷子时，哲学家才能吃饭；如果筷子已经在他人手上，则该哲学家必须等到他人吃完之后才能拿到筷子；任何一个哲学家在自己没有拿到两只筷子吃饭之前，决不放下自己手中的筷子。

由此出现的问题：可能出现死锁问题，因为当五个哲学家都饥饿时，都拿着一支筷子，这样就可能五个哲学家都用不上餐1.2问题分析该问题可用记录型信号量或者是AND型信号量解决。

记录型信号量解决：经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用，为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量组成信号量数组。

当哲学家饥饿时总是先拿其左边的筷子，成功后，再去拿右边的筷子，又成功后方可就餐。

进餐完，又先放下他左边的筷子，再放下右边筷子。

这个算法可以保证不会有两个相邻的哲学家同时就餐，但有可能引起死锁。

AND型信号量解决：在哲学家就餐过程中，要求每个哲学家先获得两个临界资源后方能就餐，这在本质上就是AND同步问题，故用AND信号量机制可获得最简洁的解法。

1.3解决方法对于死锁问题可采取这样的几种解决方法：(1)至多只允许四个哲学家同时进餐，以保证至少有一个哲学家可以进餐，最终总会释放出他所用过的两只筷子，从而可使更多的哲学家进餐；(2)仅当左右两只筷子均可用时，才允许哲学家拿起筷子就餐(3)规定奇数号哲学家先拿起右边筷子，然后再去拿左边筷子，而偶数号哲学家则相反。

(4)把筷子顺序编号 fk0, fk1, fk2, fk3, fk4，给每个哲学家分配筷子时，必须依从小号到大号（或者相反顺序）进行。

哲学家进餐问题的趣味例子
哲学家进餐问题是一个经典的计算机科学问题，用来展示并发编程中可能出现
的资源竞争和死锁问题。

这个问题的描述是：五位哲学家围坐在一张圆桌前，每位哲学家面前有一碗意面，但他们之间共享一把只能被一个人同时使用的餐叉。

每位哲学家需要先拿起右手边的餐叉，再拿起左手边的餐叉才能吃饭，吃完后放下餐叉继续思考问题。

如果哲学家之间同时试图拿起自己左右手边的餐叉，就会导致死锁问题，无法继续进餐。

这个问题的趣味例子在于通过这种抽象的场景，展现了并发编程中常见的竞争
和死锁问题。

实际上，哲学家进餐问题也可以被看作是对资源管理和同步机制的一种考验。

如果每位哲学家都按照固定的顺序拿餐叉，就不会发生死锁；而如果哲学家们都随机地尝试拿餐叉，就可能会出现资源竞争的问题，导致无法进餐。

这个问题的趣味之处在于，通过一个简单的场景，展示了复杂的并发编程中可
能出现的问题，让人们更加深入地理解并发编程中的挑战和技巧。

通过哲学家进餐问题的讨论，人们可以思考如何设计合理的同步机制和资源管理策略，避免竞争和死锁问题的发生，提高程序的并发性能和稳定性。

总的来说，哲学家进餐问题是一个充满趣味和启发的例子，能够帮助人们更好
地理解并发编程中的难点，同时也能够激发人们对于解决问题的创造力和思考能力。

通过这个例子的讨论，人们可以不仅仅学到技术知识，更能够培养出解决问题的能力和思维方式，为未来的学习和工作打下坚实的基础。

愿每位哲学家都能够顺利进餐，思考问题，探索未知的世界。

五个哲学家吃饭问题详细解答在一个阳光明媚的下午，五个哲学家聚在一起，准备享用一顿丰盛的午餐。

听起来很简单吧？但实际上，这顿饭可没那么容易！让我们来看看这群头脑发达的哲学家是如何在吃饭问题上纠结的。

1. 场景设定1.1 哲学家的基本设定这五位哲学家，一个比一个聪明。

他们分别是苏格拉底、柏拉图、康德、尼采和海德格尔。

你可以想象，他们脑袋里装的全是复杂的哲学思想，而不是食物的搭配。

所以，当这五位坐下来，面对一桌子美味的食物时，事情就开始变得有趣了。

1.2 吃饭的挑战问题来了：他们每个人都必须遵守一个规则——不可以同时吃饭，得轮流。

你想想，五个哲学家加上一个轮流吃饭的规则，这可真是“见鬼了”的挑战！想要吃上一口美味的菜，简直比推理一个哲学命题还难。

他们轮流吃饭的原则，真是把这顿饭变成了一场智力的较量。

2. 各自的哲学观2.1 苏格拉底的理性苏格拉底首先站出来，他一边抚摸着自己的胡须，一边说：“吃饭嘛，首先得用理性来解决问题。

”他鼓励大家先讨论，谁应该先吃，谁应该后吃。

他认为，只有通过理性对话，才能达到最佳的吃饭方案。

可是，你能想象吗？这一讨论持续了整整一个小时，食物都快冷掉了！2.2 柏拉图的理想接着柏拉图出场，他满脸严肃地说：“我们要追求理想的吃饭方式。

”他想出了一个绝妙的主意：每个人都应该依照自己的德性来决定吃的顺序。

结果，大家一顿争论，谁的德性更高？苏格拉底说他是智者，康德坚持说自己是道德之父，而尼采则跳出来，吼着“超人才能吃超好的饭！”搞得大家乱成一团，吃的机会又飞了。

3. 饥饿的对抗3.1 食物的诱惑这时，桌子上的食物开始散发出诱人的香气，真是令人垂涎欲滴。

五位哲学家每个人的肚子都开始抗议，仿佛在唱着“我们要吃饭”的歌。

吃饭这件事，从理性讨论变成了一场生存竞争。

每个人都在默默地想着：“快点！要是再不吃，我的哲学思想就要被饿死了！”3.2 轮流的尴尬最终，他们决定采取轮流吃饭的方式。

可当轮到康德的时候，他又开始喋喋不休，讲起了“绝对命令”的哲学，让其他人都想打瞌睡。

哲学家吃通心面包哲学家就餐问题是在计算机科学中的一个经典问题，用来演示在并行计算中多线程同步(Synchronization)时产生的问题。

在1971年，著名的计算机科学家艾兹格·迪科斯彻提出了一个同步问题，即假设有五台计算机都试图访问五份共享的磁带驱动器。

稍后，这个问题被托尼·霍尔重新表述为哲学家就餐问题。

这个问题可以用来解释死锁和资源耗尽。

问题描述哲学家就餐问题可以这样表述，假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。

吃东西的时候，他们就停止思考，思考的时候也停止吃东西。

餐桌中间有一大碗意大利面，每两个哲学家之间有一只餐叉。

因为用一只餐叉很难吃到意大利面，所以假设哲学家必须用两只餐叉吃东西。

他们只能使用自己左右手边的那两只餐叉。

哲学家就餐问题有时也用米饭和筷子而不是意大利面和餐叉来描述，因为很明显，吃米饭必须用两根筷子。

哲学家就餐问题的演示哲学家从来不交谈，这就很危险，可能产生死锁，每个哲学家都拿着左手的餐叉，永远都在等右边的餐叉（或者相反）。

即使没有死锁，也有可能发生资源耗尽。

例如，假设规定当哲学家等待另一只餐叉超过五分钟后就放下自己手里的那一只餐叉，并且再等五分钟后进行下一次尝试。

这个策略消除了死锁（系统总会进入到下一个状态），但仍然有可能发生“活锁”。

如果五位哲学家在完全相同的时刻进入餐厅，并同时拿起左边的餐叉，那么这些哲学家就会等待五分钟，同时放下手中的餐叉，再等五分钟，又同时拿起这些餐叉。

在实际的计算机问题中，缺乏餐叉可以类比为缺乏共享资源。

一种常用的计算机技术是资源加锁，用来保证在某个时刻，资源只能被一个程序或一段代码访问。

当一个程序想要使用的资源已经被另一个程序锁定，它就等待资源解锁。

当多个程序涉及到加锁的资源时，在某些情况下就有可能发生死锁。

例如，某个程序需要访问两个文件，当两个这样的程序各锁了一个文件，那它们都在等待对方解锁另一个文件，而这永远不会发生。

哲学家进餐问题-3中解决⽅案问题描述⼀张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆⼀根筷⼦，桌⼦的中间是⼀碗⽶饭，如图2-10所⽰。

哲学家们倾注毕⽣精⼒⽤于思考和进餐，哲学家在思考时，并不影响他⼈。

只有当哲学家饥饿的时候，才试图拿起左、右两根筷⼦（⼀根⼀根地拿起）。

如果筷⼦已在他⼈⼿上，则需等待。

饥饿的哲学家只有同时拿到了两根筷⼦才可以开始进餐，当进餐完毕后，放下筷⼦继续思考。

问题分析1) 关系分析。

5名哲学家与左右邻居对其中间筷⼦的访问是互斥关系。

2) 整理思路。

显然这⾥有五个进程。

本题的关键是如何让⼀个哲学家拿到左右两个筷⼦⽽不造成死锁或者饥饿现象。

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

⼀共５个哲学家，编号0 ~4, ５⽀筷⼦编号也是0 ~4, 0号哲学家右⼿的筷⼦编号是0号,逆时针增加,哲学家的编号也是逆时针增加所以:0号哲学家对应的是: 4号和1号筷⼦.1号哲学家对应的是: 0号和2号筷⼦.2号哲学家对应的是: 1号和3号筷⼦.3号哲学家对应的是: 2号和4号筷⼦.4号哲学家对应的是: 3号和0号筷⼦.所以有宏定义:#define left(phi_id) (phi_id+N-1)%N#define right(phi_id) (phi_id+1)%NN = 55⽀筷⼦对应５个互斥锁,所以:pthread_mutex_t forks[N]={PTHREAD_MUTEX_INITIALIZER};哲学家线程需要执⾏的动作是：void take_forks(int id){//获取左右两边的筷⼦printf("Pil[%d], left[%d], right[%d]\n", id, left(id), right(id));pthread_mutex_lock(&forks[left(id)]);pthread_mutex_lock(&forks[right(id)]);//printf("philosopher[%d] take_forks...\n", id);}void put_down_forks(int id){printf("philosopher[%d] is put_down_forks...\n", id);pthread_mutex_unlock(&forks[left(id)]);pthread_mutex_unlock(&forks[right(id)]);}void* philosopher_work(void *arg){int id = *(int*)arg;printf("philosopher init [%d] \n", id);while(1){thinking(id);take_forks(id);eating(id);put_down_forks(id);}}该算法存在以下问题：当五个哲学家都想要进餐，分别拿起他们左边筷⼦的时候（都恰好执⾏完pthread_mutex_unlock(&forks[left(id)]);）筷⼦已经被拿光了，等到他们再想拿右边的筷⼦的时候（执⾏pthread_mutex_unlock(&forks[right(id)]);)就全被阻塞了，这就出现了死锁。