哲学家进餐问题及解决方案.pdf

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

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

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

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

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

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

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

模拟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之间的随机数字。

哲学家问题解决死锁的方法(一)哲学家问题解决死锁引言哲学家问题是一个典型的并发编程问题，它涉及到五位哲学家围坐在一张圆桌旁，每人面前有一盘饭和一只叉子。

哲学家的生活有两种状态：思考和进餐。

每个哲学家进餐时需要两只叉子，但是一次只能拿起一只，在他左右两边的哲学家也需要使用叉子。

这个问题的挑战在于如何避免死锁的发生。

方法一：使用死锁避免算法使用死锁避免算法是一种解决哲学家问题的常见方法。

该算法的基本思想是通过限制某些哲学家的进餐行为，以避免产生死锁。

1.限制偶数编号的哲学家先拿左手边的叉子，再拿右手边的叉子。

2.限制奇数编号的哲学家先拿右手边的叉子，再拿左手边的叉子。

3.对于哲学家的进餐过程，需要先检查叉子的可用性，如果叉子被其他哲学家使用，则等待。

方法二：使用资源分级策略资源分级策略是另一种解决哲学家问题的方法，它通过划分资源的优先级来避免死锁的发生。

1.将五只叉子按照优先级从高到低排序。

2.每个哲学家在进餐前需要先请求相应优先级的叉子。

3.偶数编号的哲学家优先请求左手边的叉子，再请求右手边的叉子。

4.奇数编号的哲学家优先请求右手边的叉子，再请求左手边的叉子。

方法三：使用资源分配策略资源分配策略是一种更加灵活的解决哲学家问题的方法，它通过动态分配资源来避免死锁。

1.创建一个共享的资源管理器，用于管理叉子的分配和释放。

2.每个哲学家在进餐前向资源管理器请求两只叉子。

3.资源管理器根据当前可用的叉子数量进行分配。

4.当一个哲学家进餐结束后，释放叉子，并通知资源管理器。

结论哲学家问题是一个复杂的并发编程问题，需要谨慎设计解决方案以避免死锁的发生。

通过使用死锁避免算法、资源分级策略和资源分配策略等方法，可以有效地解决哲学家问题，并保证系统的稳定性和高效性。

在实际应用中，可以根据具体需求选择适合的方法来解决死锁问题。

哲学家就餐问题哲学家就餐问题模拟数学与计算机学院课程设计说明书课程名称: 操作系统原理-课程设计课程代码: 8404061题目: 哲学家就餐问题模拟年级/专业/班: 09级信息与计算科学三班学生姓名: 徐磊学号: 312009********* 开始时间: 2012 年 05 月 14 日完成时间: 2012 年 05月 31 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总分（100）指导教师签名：年月日哲学家就餐问题模拟I 目录1 引言................................................. 错误!未定义书签。

1.1问题的提出 ................................................................................... 错误!未定义书签。

1.2任务与分析........................................................................................ 错误!未定义书签。

2.总体设计思想及相关知识.............................. 错误!未定义书签。

2.1总体设计思想 ......................................... 错误!未定义书签。

2.2临界区互斥编程原理........................................................................ 错误!未定义书签。

3 程序运行平台........................................... 错误!未定义书签。

4 程序类的说明........................................... 错误!未定义书签。

哲学家就餐问题实验报告姓名：何绍金班级：自动化1202学号：201203870408指导教师:张健2014年11月22日一．实验题目经典的同步问题——哲学家就餐问题设计。

二．实验内容1.实验要求有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子每个哲学家的行为是思考，感到饥饿，然后吃通心粉.为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子。

2.程序流程图图1.主程序模块流程图开始定义信号量tools[5] 定义哲学家类对象P1-P5哲学家的状态发生改变；P1.change();P2.change();P3.change();P4.change();P5.change()输出当前状态停止程序结束否图2.状态改变模块流程图哲学家处于的状态否 哲学家处于思考状态是状态改为等待否 哲学家处于等待是 左右手筷子均空闲是 拿起左右手筷子状态改为就餐结束开始是 放下左右手工具 状态为思考 Status==2图3.返回哲学家状态流程图图4返回餐具状态模块流程图3.测试结果图5 测试结果1图6 测试结果2图7 测试结果34.结果分析和小结（1）程序分为四大模块，一步步解决了哲学家状态及状态改变的问题，筷子的“闲”、“用”问题；实现了哲学家等待、吃饭、思考三个过程的转换循环，并且避免了死锁问题；让临界资源得到了充分的利用。

（2）这次实验让我学会分模块解决问题，怎样运用互斥锁对临界资源进行管理；此外自己在编程上及一些函数的认识仍存在较大的问题，以后应该多多实践，提高自己的反应速度，加强逻辑思维能力。

三．程序源代码#include <windows.h>#include <time.h>#include <string>#include <iostream>#include <assert.h>using namespace std;bool tools[5]; //全局变量，用餐工具CRITICAL_SECTION cs; //信号量, 在线程中使用，临界区class Philosopher{private:int number;int status; /*标记当前哲学家的状态,0表示正在等待(即处于饥饿状态),1表示得到两支筷子正在吃饭,2表示正在思考*/public:Philosopher(int num=0): status(2), number(num) { }const int find(){return number;}const int getinfo(){ return status; }void Change() ; //状态改变函数void dead_lock();};/////////void Philosopher::dead_lock(){EnterCriticalSection (&cs) ; //进入临界区string s;if(status==1){tools[number%5]=true;// tools[(number-1)%5]=true;status=2;}else if(status==2){status=0;//tools[(number-1)%5]=false;//tools[(number-1)%5]=true;}else if(status==0){tools[number%5]=false;tools[(number-1)%5]=false;status=1;}LeaveCriticalSection (&cs) ;// cout<<"*********";}/////////void Philosopher::Change(){EnterCriticalSection (&cs) ; //进入临界区if(status==1) //正在进餐{tools[number%5]=true; //放下左手工具tools[(number-1)%5]=true; //放下右手工具status=2; //改变状态为思考}else if(status==2) //思考中{status=0; //改变状态为等待}else if(status==0) //等待中{if(tools[number%5]&&tools[(number-1)%5]) //左右手两边工具均为空闲状态{tools[number%5]=false; //拿起左手工具tools[(number-1)%5]=false; //拿起右手工具status=1;}}LeaveCriticalSection (&cs) ;}string print(Philosopher *pA){//pA->Change();int i=pA->getinfo();string str;if(i==0)str="等待";else if(i==1)str="就餐";else str="思考";return str;}string toolstatus(bool a){string state;if(a==true)state="闲";if(a==false)state="用";return state;}int main(){char con='y'; //判断是否继续// con = 'n';for(int i=0;i<5;i++)tools[i]=true; //筷子都未使用，初始化Philosopher P1(1),P2(2),P3(3),P4(4),P5(5);InitializeCriticalSection (&cs) ; //初始化初始化临界区cout<<"-----------------------状态说明示意图：-----------------------"<<endl; cout<<" "<<"哲学家1号的状态"<<" "<<endl;cout<<" 筷子0的状态"<<" "<<"筷子1的状态"<<endl;cout<<"哲学家5号的状态"<<" "<<"哲学家2号的状态"<<endl; cout<<" 筷子4的状态"<<" "<<"筷子2的状态"<<endl;cout<<" 哲学家4号的状态"<<" "<<"哲学家3号的状态"<<endl; cout<<" "<<"筷子3的状态"<<endl;//cout<<" "<<"哲学家3号的状态"<<" "<<endl;cout<<"筷子的状态，用表示使用中，闲表示空闲中。

专利号：0015 翻版必究《哲学家进餐问题》课程设计报告姓名：学号班级：专业：指导教师：时间计算机科学与信息学院目录1 课程设计目的 (1)2 课程设计题目描述和要求 (1)问题描述 (1)题目要求 (1)3 课程设计报告内容 (1)实验分析 (1)相关变量函数说明 (2)程序流程图 (2)源程序代码 (3)运行结果 (8)4 总结 (12)参考文献 (12)附录 (12)一、课程设计目的通过设计，编写，调试一个简单的进程调度模拟系统，对进程调度，进程运行状态变换及wait原语和signal原语加深理解和掌握。

二、课程设计题目描述和要求1、问题描述：有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子，每个哲学家的行为是思考，感到饥饿，然后吃通心粉。

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

2、题目要求：(1)．分析设计内容，给出解决方案（要说明设计实现的原理，采用的数据结构）。

(2)．画出程序的基本结构框图和流程图。

(3)．对程序的每一部分要有详细的设计分析说明。

(4)．源代码格式要规范。

(5).熟练掌握wait原语和signal原语；通过对信号量的控制实现进程的互斥与等待；模拟多个进程之间的并发执行；(6)．设计合适的测试用例，对得到的运行结果要有分析。

(7)．设计中遇到的问题，设计的心得体会。

(8)．按期提交完整的程序代码、可执行程序和课程设计报告。

三、课程设计报告内容1、实验分析利用AND信号量机制解决哲学家进餐问题在哲学家进餐问题中，要求每个哲学家先获得两个临界资源(筷子)后方能进餐，这在本质上就是前面所介绍的AND同步问题，故用AND信号量机制可获得最简洁的解法。

描述如下：Var chopsiick array of semaphore:=(1,1,1,1,1)；processirepeatthink；Sswait(chopstick[(i+1)mod 5]，chopstick[i])；eat；Ssignat(chopstick[(i+1)mod 5]，chopstick[i])；until false；2、相关变量函数说明#define n5n");scanf("%d",&i); }return(1);}［1］intmain()京：清华大学出版社………………………………………………………………………….. 附录：。

进程通信-经典进程问题哲学家进餐哲学家进餐1.至多只能允许有四个哲学家同时进餐,保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。

伪码：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}}2.仅当哲学家的左右两支筷子都可使用时,才允许他拿起两只筷子进餐。

伪码：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]);}}读者和写者Reader:beginrepeatwait(s);wait(rmutex);if readcount=0 then wait(wmutex);readcount:=readcount+1;signal(rmutex);signal(s);Perform read operation;wait(rmutex)readcount:=readcount-1;if readcount=0 then signal(wmutex);signal(rmutex);until false;endWrite:beginrepeatwait(mutex)if writecount=0 then wait(s);writecount:=Writecount+1;signal(mutex);wait(wmutex);Perform write operation;signal(wmutex);wait(mutex);writecount:=writecount-1;if writecount=0 then signal(s);signal(mutex);until false;end（1）情况一：当读者A正在运行时，读者B、写者A、写者B三个进程被阻塞在哪里？读者B被阻塞在wait(s)写者A、写者B被阻塞在wait(wmutex)（2）情况二：当写者A正在运行时，读者A、读者B、写者B三个进程被阻塞在哪里？读者A、读者B被阻塞在wait(s)写者B被阻塞在wait(wmutex)。

哲学家就餐问题实验⼀⼀、实验名称：哲学家就餐问题的实现⼆、实验学时：2三、实验内容和⽬的：实验⽬的：实现哲学家就餐问题，要求不能出现死锁。

通过本实验熟悉Linux系统的基本环境，了解Linux下进程和线程的实现。

实验内容：在Unix系统下实现教材2.4.2节中所描述的哲学家就餐问题。

要求显⽰出每个哲学家的⼯作状态，如吃饭，思考。

连续运⾏30次以上都未出现死锁现象。

四、实验原理：由Dijkstra提出并解决的哲学家进餐问题(The Dinning Philosophers Problem)是典型的同步问题。

该问题是描述有五个哲学家共⽤⼀张圆桌，分别坐在周围的五张椅⼦上，在圆桌上有五个碗和五只筷⼦，他们的⽣活⽅式是交替地进⾏思考和进餐。

平时，⼀个哲学家进⾏思考，饥饿时便试图取⽤其左右最靠近他的筷⼦，只有在他拿到两只筷⼦时才能进餐。

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

五、实验器材（设备、元器件）（1）学⽣每⼈⼀台PC，安装WindowsXP/2000操作系统。

（2）局域⽹络环境。

（3）个⼈PC安装VMware虚拟机和Ubuntu系统。

六、实验内容：（⼀）熟悉Ubuntu系统下的多线程编程。

（⼆）实现哲学家就餐问题1. 算法思想规定奇数号哲学家先拿他左边的筷⼦，然后再去拿右边的筷⼦，⽽偶数号哲学家则相反。

按此规定，将是1、2号哲学家竞争1号筷⼦；3、4号哲学家竞争3号筷⼦。

即五位哲学家都⽣竞争奇数号筷⼦，获得后，再去竞争偶数号筷⼦，最后总会有⼀位哲学家能获得两只筷⼦⽽进餐。

2. 流程图3. 程序代码（重要代码请注释）#include#include#include#include#include#define NOC 5 //number of chopstic#define NOP 5 //number of philosopher sem_t chopstic[NOC]; //semaphoreint flag[5]; //philosopher's statusvoid *eat(int i){int position;int temp = 0;int j = (i+1)%NOC;position = i%2;while(1){if(position == 0){ //odd take left first sem_wait(&chopstic[i]);sem_wait(&chopstic[j]);printf("philosopher%d get %d\n", i, j);flag[i] = 1; //philosopher is eatingprintf("waitting:"); //print others' statuswhile(temp < 5){if(!flag[temp])printf("philosopher%d\t", temp);temp++;}temp = 0;printf("\n");printf("eating:");// print others' statuswhile(temp < 5){if(flag[temp])printf("philosopher%d\t", temp);temp++;}printf("\n\n");temp = 0;//printf("\nphilosopher%d is eating\n\n", i); sleep(2);flag[i] = 0;printf("philosopher%d put %d\n", i, i); sem_post(&chopstic[i]); printf("philosopher%d put %d\n", i, j); sem_post(&chopstic[j]); }else{ //even take right firstsem_wait(&chopstic[j]);printf("philosopher%d get %d\n", i, j);sem_wait(&chopstic[i]);printf("philosopher%d get %d\n", i, i);flag[i] = 1;printf("waitting:");while(temp < 5){if(!flag[temp])printf("philosopher%d\t", temp);}temp = 0;printf("\n");printf("eating:");while(temp < 5){if(flag[temp])printf("philosopher%d\t", temp);temp++;printf("\n\n");temp = 0;//printf("\nphilosopher%d is eating\n\n", i);sleep(2);flag[i] = 0;printf("philosopher%d put %d\n", i, j);sem_post(&chopstic[j]);printf("philosopher%d put %d\n", i, i);sem_post(&chopstic[i]);}}}int main(void){int i = 0;int error;pthread_t philosopher[NOP];//init semwhile(i < 5){flag[i] = 0;sem_init(&chopstic[i], 0, 1);i++;}i = 0;//create threadwhile(i < 5){error = pthread_create(&philosopher[i], NULL, (void *)eat, (void *)i);printf("error:create thread failed!!\n");exit(0);}i++;}//destroy threadwhile(i < 5){pthread_join(philosopher[i], NULL);i++;}i = 0;//destroy semwhile(i < 5){sem_destroy(&chopstic[i]);i++;}return 0;}七、实验及结果分析：运⾏结果：udbwxfso@ubuntu:~/Desktop/sy2$ gcc gphilosopher.c -pthread udbwxfso@ubuntu:~/Desktop/sy2$ ./a.out philosopher4 get 4philosopher4 get 0waitting:philosopher0 philosopher1 philosopher2 philosopher3 eating:philosopher4philosopher2 get 2philosopher2 get 3waitting:philosopher0 philosopher1 philosopher3eating:philosopher2 philosopher4philosopher4 put 4philosopher4 put 0philosopher4 get 4philosopher4 get 0waitting:philosopher0 philosopher1 philosopher3eating:philosopher2 philosopher4philosopher2 put 3philosopher2 get 2philosopher2 get 3waitting:philosopher0 philosopher1 philosopher3eating:philosopher2 philosopher4philosopher4 put 4philosopher3 get 4philosopher4 put 0philosopher0 get 0philosopher0 get 1waitting:philosopher1 philosopher3 philosopher4eating:philosopher0 philosopher2philosopher2 put 2philosopher2 put 3philosopher2 get 2philosopher2 get 3waitting:philosopher1 philosopher3 philosopher4eating:philosopher0 philosopher2philosopher2 put 2philosopher2 put 3philosopher2 get 2philosopher2 get 3waitting:philosopher1 philosopher3 philosopher4eating:philosopher0 philosopher2经分析可知，放在桌⼦上的筷⼦是临界资源，在⼀段时间内只允许⼀位哲学家使⽤，为了实现对筷⼦的互斥使⽤，⽤⼀个信号量表⽰⼀只筷⼦，由这五个信号量组成信号量数组。