计算机操作系统哲学家进餐问题的研究
姓名：陆文静
学号： 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、算法的总结
哲学家就餐问题是个经典的同步问题，题中的演示哲学家从来不交谈，这就可能产生死锁，每个哲学家都拿着左手的餐叉，永远都在等右边的餐叉（或者相反）。即使没有死锁，也有可能发生资源耗尽。例如，假设规定当哲学家等待另一只餐叉超过五分钟后就放下自己手里的那一只餐叉，并且再等五分钟后进行下一次尝试。这个策略消除了死锁（系统总会进入到下一个状态），但仍然有可能发生“活锁”。如果五位哲学家在完全相同的时刻进入餐厅，并同时拿起左边的餐叉，那么这些哲学家就会等待五分钟，同时放下手中的餐叉，再等五分钟，又同时拿起这些餐叉。
在实际的计算机问题中，缺乏餐叉可以类比为缺乏共享资源。一种常用的计算机技术是资源加锁，用来保证在某个时刻资源只能被一个程序或一段代码访问。当一个程序想要使用的资源已经被另一个程序锁定，它就等待资源解锁。当多个程序涉及到加锁的资源时，在某些情况下就有可能发生死锁。例如，某个程序需要访问两个文件，当两个这样的程序各锁了一个文件，那它们都在等待对方解锁另一个文件，而这永远不会发生。
[解法] 服务生解法
一个简单的解法是引入一个餐厅服务生，哲学家必须经过他的允许才能拿起餐叉。因为服务生知道哪只餐叉正在使用，所以他能够作出判断避免死锁。
为了演示这种解法，假设哲学家依次标号为A至E。如果A和C在吃东西，则有四只餐叉在使用中。B坐在A和C之间，所以两只餐叉都无法使用，而D和E之间有一只空余的餐叉。假设这时D想要吃东西。如果他拿起了第五只餐叉，就有可能发生死锁。相反，如果他征求服务生同意，服务生会让他等待。这样，我们就能保证下次当两把餐叉空余出来时，一定有一位哲学家可以成功的得到一对餐叉，从而避免了死锁。
[解法] 资源分级解法
另一个简单的解法是为资源（这里是餐叉）分配一个偏序或者分级的关系，并约定所有资源都按照这种顺序获取，按相反顺序释放，而且保证不会有两个无关资源同时被同一项工作所需要。在哲学家就餐问题中，资源（餐叉）按照某种规则编号为1至5，每一个工作单元（哲学家）总是先拿起左右两边编号较低的餐叉，再拿编号较高的。用完餐叉后，他总是先放下编号较高的餐叉，再放下编号较低的。在这种情况下，当四位哲学家同时拿起他们手边编号较低的餐叉时，只有编号最高的餐叉留在桌上，从而第五位哲学家就不能使用任何一只餐叉了。而且，只有一位哲学家能使用最高编号的餐叉，所以他能使用两只餐叉用餐。当他吃完后，他会先放下编号最高的餐叉，再放下编号较低的餐叉，从而让另一位哲学家拿起后边的这只开始吃东西。
尽管资源分级能避免死锁，但这种策略并不总是实用的，特别是当所需资源的列表并不是事先知道的时候。例如，假设一个工作单元拿着资源3和5，并决定需要资源2，则必须先要释放5，之后释放3，才能得到2，之后必须重新按顺序获取3和5。对需要访问大量数据库记录的计算机程序来说，如果需要先释放高编号的记录才能访问新的记录，那么运行效率就不会高，因此这种方法在这里并不实用。
这种方法经常是实际计算机科学问题中最实用的解法，通过为分级锁指定常量，强制获得锁的顺序，就可以解决这个问题。
2、拓展应用
读者-写者问题
第一和第二读者-写者问题是并行计算的模拟。这两个问题描述的是有许多线程必须同时访问共享的内存地址，有的要读，有的要写。在通常的限制条件下，在一个进程正在写入的时候，其它的进程不能读，也不能写那个共享的内存块。特别要说的是，两个或多个读者可以同时访问同一内存地址。一般来说，会使用一种叫“读-写锁”（readers-writer lock）的数据结构来解决这类问题。
第一读者-写者问题
假设我们有一个共享内存区，使用了限制技术。使用一个互斥信号标（mutex）来保护共享的数据是可能的，这时很显然当一个过程在写入时其它进程不能访问。但是这个方案不是很经济。因为如果一个读者R1拿到了“锁”，而另一个读者R2应该也可以要求访问。如果R2非得等到R1完成了才能去操作是很不合
理的，所以，R2就直接去读了。这就是第一读者-作者问题的动机。限制条件变成了“如果共享内存正在被读，其它的读者不应该苦等”。这就是读者优先法则。第二读者-写者问题
假如我们有一个受到互斥信号标（Mutex）保护的共享内存区。上面那个方案也是不经济的。因为很可能会发生当读者R1锁住了内存，而写者W必须等着拿到那个锁后才能写入。然后又有一个读者R2要求访问。于是R2挤到W前面去了。如果这情况一直继续下去，我们会把W“饿死”。实际上，W应该马上动手操作。这就是第二读者-作者问题的动机。限制条件变成了“如果一个写者在排队，就不应该让它等得太久”。这就是写者优先法则。
第三读者-写者问题
实际上，以上两个方案都会导致“饿死”的情况发生。第一读者-写者问题的方法可能会“饿死”队列中的写者；第二读者-写者问题的方法可能会“饿死”读者。所以，人们提出了第三读者-写者问题的解决方案，即“不能允许有线程被饿死”。即取得一个共享内存区的锁定权的操作要在一个限定的时间内结束。这个解决方案会在共享内存区可以读的时候让读者等待，或者让写者等更长一段时间。
3、个人体会
这次的操作系统论文报告让我深刻的体会到了操作系统理论知识的作用，在这次论文的研究整理借鉴过程中，培养了我综合运用知识的能力，让我对进程的互斥和同步有了更深的了解。
在完成本次论文的过程中，我遇到了许多的困难，因为是第一次写论文，各方面都没有经验，论文形式的不熟悉，加上对课题的不理解，一些知识方面遇到了困难，比如说，哲学家进餐问题死锁的预防，分析一个哲学家连续进餐的可能和哲学家依次进餐的可能，但好在通过同学的帮助以及自己仔细的翻阅资料，困难都一一解决了，而且在其中我发现了自己在学习中许多的不足之处，对以前学习的知识理解不够透彻，对现有操作系统的知识掌握还不到位等等。
总的来说，哲学家就餐问题是一个经典的课题，此次的实践带给我的收获绝不止实现这一个课题这么简单。
参考文献：计算机操作系统（第四版）；
五个经典同步问题：
https://www.doczj.com/doc/2618021712.html,/naruto_ahu/article/details/8672376
哲学家进餐问题一种解法的改进：
https://www.doczj.com/doc/2618021712.html,/link?url=5GKOgGEW86Uo1Xti8ptNMU097BiPn-UEDb0-N mISZLOzcqWwcfZGYZCix8pnN7iPaSlQ7-J6gbwqaAes_k8eGzUWduMMzdXMHllkiWuGaJ O
实验一 一、实验名称：哲学家就餐问题的实现 二、实验学时：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 操作系统 实验报告 实验名称：哲学家就餐问题 班级：信卓1201班 姓名：钟远维 学号：U201213500 日期：2014年10月30日 一、实验目的 1、熟练使用VC6.0编译环境，调试并正确运行程序。 2、理解哲学家就餐问题中出现的问题，进而掌握死锁的必要条件。 3、理解源程序中产生和防止死锁的算法，及相关窗口操作。 4、熟悉哲学家就餐问题流程并写出其伪代码 二、实验内容 有五个哲学家围坐在一圆桌旁（如图1），桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子。每个哲学家的行为是思考，感到饥饿，然后吃通心粉。为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子。 图1 图2 三、实验要求 1、程序需有防止死锁发生采取的措施； 2、程序要有产生死锁的分配方式； 四、实验算法实现 1、不发生死锁的方式 由源码gChopstickState[iLeftChopstick] = iPhilosopher; gChopstickState[iRightChopstick] = iPhilosopher; 知基本思路是要么一下子占用两支筷子要么不占用，先确定两只筷子均没被占用才获取筷子，这样就打破了死锁的必要条件。 伪代码如下; var mutexleftchopstick,mutexrightchopstick; beging: resting; waiting; p(mutexleftchopstick); //先改变左手筷子信号量 p(mutexrightchopstick); //马上改变右手筷子信号量 GetResource(leftchopstick,rightchopstick); //同时占用左右手筷子 eating; v(mutexleftchopstick); //释放资源 v(mutexrightchopstick); end 2、发生死锁的方式 基本思路是有筷子即占用，看似效率很高，但因为资源有限，且不可抢占，很容易发生死锁。 源码理解: gDinerState[iPhilosopher] = WAITING; //wants chopsticks result = WaitForSingleObject(gchopStick[iLeftChopstick], INFINITE); gChopstickState[iLeftChopstick] = iPhilosopher; //得到左手筷子 Sleep(P_DELAY/4); //休眠状态 gDinerState[iPhilosopher] = WAITING; //继续等待另一只手筷子 result = WaitForSingleObject(gchopStick[iRightChopstick], INFINITE); gChopstickState[iRightChopstick] = iPhilosopher; //直到等到右手筷子 伪码书写： var mutexleftchopstick,mutexrightchopstick; beging: 操作系统哲学家问题实验报告 实验报告三 实验名称:一、调试验证“有限缓冲”经典同步问题 二、利用Java同步解决“哲学家进餐”问题 日期：2015-11-5 班级：13级计科学号: 姓名： 一、实验目的 1.了解信号量的使用 2.掌握正确使用同步机制的方法 3.实现生产者消费者进程的互斥与同步 4.实现java同步解决“哲学家进餐”问题 二、实验内容 1.调试验证“有限缓冲”经典同步问题 2.利用Java同步解决“哲学家进餐”问题 三、项目要求与分析 1.“有限缓冲”经典同步问题 （1）问题描述 有一群生产者进程在生产产品，此产品提供给消费者去消费。为使生产者和消 费者进程能并发执行，在它们之间设置一 个具有n个缓冲池，生产者进程可将它所 生产的产品放入一个缓冲池中，消费者进 程可从一个缓冲区取得一个产品消费。 （2）问题分析 设两个同步信号量:一个说明空缓冲区的数目，用empty表示，初值为有界缓 冲区的大小N，另一个说明已用缓冲区的 数目，用full表示，初值为0。由于在 执行生产活动和消费活动中要对有界缓 冲区进行操作。有界缓冲区是一个临界资 源，必须互斥使用，所以另外还需要设置 一个互斥信号量mutex，其初值为1。2.“哲学家进餐”问题 （1）问题描述 假如所有的哲学家都同时拿起左侧筷子，看到右侧筷子不可用，又都放下左 侧筷子，等一会儿，又同时拿起左侧筷子，如此这般，永远重复。对于这种情况，即 所有的程序都在无限制地运行，但是都无 法得到任何进展，即出现饿死，所有的哲 学家都吃不上饭。 规定在拿起左侧的筷子后，先检查右面的筷子是否可用。如果不可用，则放下左 侧的筷子，等一段时间后再重复整个过 程。 （2）问题分析 当出现以下情形，在某一瞬间，所有的哲学家都同时启用这个算法，拿起左侧 课程设计报告书 课程名称：计算机操作系统 题目：用多线程同步方法解决哲学家就餐问题系名： 专业班级： 姓名： 学号： 指导教师: 2016 年 6 月 24 日 武汉华夏理工学院信息工程系 课程设计任务书 课程名称：操作系统原理课程设计指导教师： 班级名称：开课系、教研室：自动化与计算机 一、课程设计目的与任务 操作系统课程设计是《操作系统原理》课程的后续实践课程，旨在通过一周的实践训练，加深学生对理论课程中操作系统概念，原理和方法的理解，加强学生综合运用操作系统原理、Linux系统、C语言程序设计技术进行实际问题处理的能力，进一步提高学生进行分析问题 和解决问题的能力，包含系统分析、系统设计、系统实现和系统测试的能力。 学生将在指导老师的指导下，完成从需求分析，系统设计，编码到测试的全过程。 二、课程设计的内容与基本要求 1、课程设计题目 用多线程同步方法解决哲学家就餐问题 2、课程设计内容 本课程设计要求在Linux操作系统，GCC编译环境下开发。 用c/c++语言在Linux操作系统环境下，通过研究Linux的线程机制和信号量实现哲学家就餐问题的并发控制。为避免死锁，可采用只许4个哲学家入席且桌上有5支筷子的办法。几把椅子可用连续存储单元。 1 每个哲学家取得一双筷子开始用餐后，即时显示“Dining…”和该哲学家的标识符以 及餐桌上有几位哲学家及其所坐的位置。 2 设定共有10个哲学家需用餐。每位用餐耗时10秒钟以上。 3 多个哲学家须共享操作函数代码。 提示: 1 有界缓冲区/连续存储区可用数组实现。 2 编译命令可用： gcc -lpthread -o 目标文件名源文件名 3 多线程编程方法参见电子文档。 3、设计报告撰写格式要求： 1设计题目与要求 2 设计思想 3系统结构 4 数据结构的说明和模块的算法流程图 5 使用说明书（即用户手册）：内容包含如何登录、退出、读、写等操作说明 6 运行结果和结果分析（其中包括实验的检查结果、程序的运行情况） 7 自我评价与总结 8 附录：程序清单，注意加注释（包括关键字、方法、变量等），在每个模块前加注释； 哲学家进餐问题代码(JAVA) (2010-10-12 15:24:12) 转载 标签： 分类：Java it 问题描述： 一个哲学家围坐在一张圆桌周围，每个哲学家面前都有一碟通心面。由于面条很滑，所以 要两把叉子才能夹住。相邻两个碟子之间有一把叉子。 哲学家的生活包括两种活动：即吃饭和思考。当一个哲学家觉得饿时，他就试图分两次去 取他左边和右边的叉子，每次拿一把，但不分次序。如果成功地获得了两把叉子，他就开 始吃饭，吃完以后放下叉子继续思考。 问题是： 为每一个哲学家写一段程序描述其行为。要求不能死锁。 class kuai{ String name; boolean Enable = true; public kuai(String name) { https://www.doczj.com/doc/2618021712.html, = name; } public synchronized void pickup() { this.Enable =false; } public synchronized void putdown() { this.Enable =true; this.notifyAll(); } } class Philosopher extends Thread { String name; kuai left; kuai right; public Philosopher(String name, kuai l, kuai r) { https://www.doczj.com/doc/2618021712.html, = name; left = l; right = r; } public void run() { if(left.Enable) { left.pickup(); } else { while(!left.Enable) { 南昌大学实验报告 学生姓名：倪焕学号：8000114018 专业班级：软件工程141班 实验类型：■验证□综合□设计□创新实验日期：2016.5.24 实验成绩： 一、实验项目名称 哲学家就餐问题 二、实验目的 利用PV操作解决哲学家就餐问题 三、软硬件环境 软件：Visual Studio2010 硬件：PC机一台 四、实验内容结果 //哲学家就餐问题的解法 #include 操作系统实习 报告 一、设计目的： 死锁是进程并发执行过程中可能出现的现象，所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局。哲学家就餐问题是描述死锁的经典例子。为了防止死锁，可以采用资源预分配法或者资源按序分配法。资源预分配法是指进程在运行前一次性地向系统申请它所需要的全部资源，如果系统当前不能够满足进程的全部资源请求，则不分配资源, 此进程暂不投入运行，如果系统当前能够满足进程的全部资源请求, 则一次性地将所申请的资源全部分配给申请进程。 二、设计内容 哲学家进餐问题的模拟。 三、开发环境 windows环境，Myeclipse平台。 四、分析设计 ＜一＞实验原理 哲学家进餐问题描述的是五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五只碗和五只筷子。他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右的最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐完毕放下筷子继续思考。 由于：①只有拿到两只筷子时，哲学家才能吃饭；②如果筷子已经在他人手上，则该哲学家必须等到他人吃完之后才能拿到筷子；③任何一个哲学家在自己 没有拿到两只筷子吃饭之前，决不放下自己手中的筷子。则可能出现五个哲学家都饥饿时都拿着一直筷子。这样就可能五个哲学家都用不上餐。 该问题可用记录型信号量解决，经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用，为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量组成信号量数组。当哲学家饥饿时总是先拿其左边的筷子，成功后，再去拿右边的筷子，又成功后方可就餐。进餐完，又先放下他左边的筷子，再放下右边筷子。这个算法可以保证不会有两个相邻的哲学家同时就餐，但有可能引起死锁。 对于死锁问题可采取这样的几种解决方法： (1)至多只允许四个哲学家同时进餐，以保证至少有一个哲学家可以进餐，最终总会释放出他所用过的两只筷子，从而可使更多的哲学家进餐； (2)仅当左右两只筷子均可用时，才允许哲学家拿起筷子就餐 (3)规定奇数号哲学家先拿起右边筷子，然后再去拿左边筷子，而偶数号哲学家则相反。 (4)把筷子顺序编号0, 1, 2, 3, 4，给每个哲学家分配筷子时，必须依从小号到大号（或者相反顺序）进行。 在本次实习里采用第二种方法解决该问题。 ＜二＞数据及程序结构 总共创建有四个类：哲学家进餐问题类，Philosopher类，ChopstickArray 类，Chopstick类。 Chopstick类来表示筷子，其中包括的布尔型成员变量available来表示该筷子是否可用，成员方法setnum()获取其编号；boolean型成员方法isAvailable()返回其当前available的值。setAvailable(boolean available)这一成员方法是对筷子的available的值进行设置，即设置筷子是否可用。 ChopstickArray类用其中的数组chopsticks[i]来存放五只筷子，并通过哲学家的编号及筷子的编号确定该筷子属于当前哲学家的左右哪边的筷子。 Philosopher类，用来描述哲学家，通过实现Runnable接口的方式来创建线程对象，该类中的方法thinking()，eating()来描述哲学家的状态。通过使用关键词synchronized来给共享资源即Philosopher对象上锁，当一个线问程访问Philosopher中的Thinking()时锁定Philosopher对象，这时其他线程就无法访问其另一个方法eating()，即说明哲学家不能同时处于思考和吃饭的状态中。 public synchronized void thinking() { if(state) /* 如果在思考,说明这个哲学家两边的筷子没用 */ { chopstickArray.getnum(num).setAvailable(true); chopstickArray.getLast(num).setAvailable(true); /*这时哲学家两边的筷子只为可用*/ 潍坊学院计算机工程学院 课程设计说明书 课程名称：____操作系统课程设计_________________设计项目：____哲学家就餐问题____________________学生姓名：_____XXXXXX _________________________学号：____ ___________________专业：______计算机科学与技术________________班级：______一班___________________________指导教师：_______ ___________________________ _2016年__3___月 一、任务与具体要求 哲学家有N个，规定全体到齐后开始讨论，在讨论的间隙哲学家进餐，每人进餐时都需使用刀、叉合一把，所有哲学家刀和叉都拿到后才能进餐。哲学家的人数、餐桌上的布置自行设定，实现刀和叉的互斥使用算法的程序实现。 二、设计说明书包括的内容 1.需求分析 2.系统概要设计 3.系统详细设计 4.系统的主要源代码 5.系统测试及调试 6.总结 7.主要参考文献 三、应完成的图纸 四、评语及成绩 指导教师（签字）_____________ ________年____月____日目录 一、需求分析 __________________________________________________________ 1 二、系统概要设计 ______________________________________________________ 2 三、系统详细设计 ______________________________________________________ 3 四、系统的主要源代码 __________________________________________________ 4 五、系统测试及调试 ____________________________________________________ 9 六、总结 _____________________________________________________________ 13 七、主要参考文献 _____________________________________________________ 13 实践15 哲学家进餐问题 1.实践内容说明 （1）在函数中使用图形方式显示哲学家进餐问题,每个哲学家使用一个线程控制,随机进行进餐或者思考,使用互斥量与事件进行同步与互斥控制。 2.程序性质 （1）Windows 与控制台混合应用程序 （2）多线程 3.运行环境设置 (1)建立项目在Visual C++ 6、0 开发环境,单击New 菜单,弹出New 对话框; 在New 对话框中选择Project 标签切换至Project 标签页; 在Project 标签页得项目列表中选择Win32 Application 选项,Location 输入框输入项目所在得路径,或者单击输入框右侧得按钮,在弹出得Choose Directory 对话框中选择项目所在得磁盘分区与所在得目录;在Project 标签页得Project name 输入框中输入项目名称; Project 标签页中得其她选项保持默认选择(单选框Create new workspace 前有黑点, Platforms 选项框中Win32 前打勾),完成设置界面如图10 所示。 图10 设置项目为Windows 应用 完成设置后单击OK,New 对话框关闭,弹出Win32 Console Application –Step 1 of 1 对话框。在Win32 Console Application –Step 1 of 1 对话框中选择An empty project 单选项。Win32 Console Application –Step 1 of 1 对话框如图11 所示。 图11 说明刚建立得项目为空项目 完成Win32 Console Application –Step 1 of 1 对话框后单击Finish 按钮,Win32 Console Application –Step 1 of 1 对话框关闭,弹出New Project Information 对话框。New Project Information 对话框中显示了当前建立项目得一些信息。New Project Information 对话框如图12 所示。 图12 显示新项目信息 单击New Project Information 对话框中得OK 按钮,关闭New Project Information 对话框, 项目建立步骤完成。 (2)建立文件单击File 菜单中得New 菜单项,弹出New 对话框。在New 对话框中单击Files 标签,切换至Files 标签页; 在Files 标签页得文件列表中选择C++ Source File 选项,在File 输入框中输入文件名。New 对话框设置如图13 所示。 实验一哲学家就餐问题 一、实验目的 1.熟练使用VC++6.0编译环境，调试并正确运行程序。 2.熟悉哲学家就餐问题流程。 3.理解哲学家就餐问题中出现的问题，进而掌握死锁的必要条件。 4.熟悉源程序中产生和防止死锁的算法，及其相关窗口操作。 二、实验原理 1.问题描述： 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每 两人之间放一只筷子，每个哲学家的行为时思考，饥饿，然后吃通心粉，每个哲学 家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边取筷子。 2.防止死锁发生的分配方式： 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子。这样要么一次占有两 只筷子（所有线程需要的资源）进行下一步吃通心粉，然后释放所有的资源；要么 不占用资源，这样就不可能产生死锁了。 3.产生死锁的分配方式： 当筷子（资源）可用时，先分配左边的筷子，等待一会后再分配右边的筷子，由于 这个过程中，左边的筷子一直没有释放，就可能产生死锁了。 4.程序运行说明： 程序运行过程中会弹出一个MessageBox提示操作者操作： 1）第一个对话框用于选择运行模式 a．选择yes表示采用的是运行的防止死锁的方式，这样的话整个程序可以一直运行下去，不会产生死锁。 b．选择no表示运行产生死锁的方式会弹出第二个对话框。 2）第二个对话框用于选择运行时，线程运行的时间 a．选择yes线程时间比较短，很快就可以死锁。 b．选择no线程时间跟选择yes时的时间差不多，产生死锁的时间稍微长一点。 三、实验过程及分析 1.PhilosopherThread(LPVOID pVoid)函数伪代码 1）不死锁方式 Var mutexleftchopstick,mutexrightchopstick; Beging: Resting; Waiting; P{mutexleftchopstick}; P{mutexrightchopstick}; GetResource{leftchopstick,rightchopstick}; Eating; V{mutexleftchopstick}; /*inux进程的实现:哲学家就餐问题在 linux 上的程序实现 设有5个哲学家,共享一张放油把椅子的桌子,每人分得一吧椅子.但是桌子上总共只有5支筷子,在每个人两边分开各放一支.哲学家只有在肚子饥饿时才试图分两次从两边拾起筷子就餐. 就餐条件是: 1)哲学家想吃饭时,先提出吃饭的要求; 2)提出吃饭要求,并拿到2支筷子后,方可吃饭; 3)如果筷子已被他人获得,则必须等待该人吃完饭之后才能获取该筷子; 4)任一哲学家在自己未拿到2支筷子吃饭之前,决不放下手中的筷子; 5)刚开始就餐时,只允许2个哲学家请求吃饭. 试问: 1)描述一个保证不会出现两个邻座同时要求吃饭的算法; 2)描述一个既没有两邻座同时吃饭,又没有人饿死的算法; 3)在什么情况下,5个哲学家全都吃不上饭? 哲学家进餐问题是典型的同步问题.它是由Dijkstra提出并解决的.该问题是描述有五个哲学家,他们的生活方式是交替地进行思考和进餐.哲学家们共用一张圆桌,分别坐在周围的五张椅子上.在圆桌上有五个碗和五支筷子,平时一个哲学家进行思考,饥饿时便试图取用其左右岁靠近他的筷子,只有在他拿到两支筷子时才能进餐.进餐完毕,放下筷子继续思考. */ #include 计算机操作系统哲学家进餐问题的研究 姓名：陆文静 学号： 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) 目录 1．设计题目与要求 (2) 设计目的 设计要求 2．总体设计思想与相关知识 (2) 总体设计思想 问题描述 解决方案 3．数据结构、流程图 (2) 数据结构 流程图 4．源代码 (3) 5．运行结果 (6) 6．结果分析 (7) 7．总结及心得体会 (7) 1．设计题目与要求 设计目的 掌握进程同步问题的解决思路及方法，熟练使用Windows操作系统提供的信号量机制解决各种进程同步问题。 设计要求 设有五个哲学家,共用一张放有五把椅子的餐桌,每人坐在一把椅子上,桌子上有五个碗和五只筷子,每人两边各放一只筷子。哲学家们是交替思考和进餐,饥饿时便试图取其左右最靠近他的筷子。条件: (1) 只有拿到两只筷子时,哲学家才能吃饭。 (2) 如果筷子已被别人拿走,则必须等别人吃完之后才能拿到筷子。 (3) 任意一个哲学家在自己未拿到两只筷子吃饭前,不会放下手中拿到的筷子。 2．总体设计思想与相关知识 总体设计思想 哲学家的生活就是思考和吃饭，即思考，饿了就餐，再思考，循环往复。要求是：每一个哲学家只有在拿到位于他左右的筷子后，才能够就餐；哲学家只能先拿左边的筷子，再去拿右边的筷子，而不能同时去抓他两边的筷子，也不能从其他哲学家手中抢夺筷子；哲学家每次就餐后必须放下他手中的两把筷子后恢复思考，不能强抓住餐具不放。 设计一个程序，能够显示当前各哲学家的状态和桌上餐具的使用情况，并能无死锁的推算出下一状态各哲学家的状态和桌上餐具的使用情况。即设计一个能安排哲学家正常生活的程序。 问题描述 可能出现死锁问题，因为当五个哲学家都饥饿时，都拿着一支筷子，这样就可能五个哲学家都用不上餐。 解决方案 最多允许4个哲学家同时坐在桌子周围。 给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之。 为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子，并且一次拿到两只筷子，否则不拿。3．数据结构及流程图 哲学家就餐问题 实验一 一、实验名称：哲学家就餐问题的实现 二、实验学时：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 哲学家进餐问题 一、需求分析 有一个故事是这样的：假设有五位哲学家围坐在一张圆形餐桌旁，做以下 两件事情之一：吃饭，或者思考。吃东西的时候，他们就停止思考，思考的时候也停止吃东西。餐桌中间有一大碗意大利面，每两个哲学家之间有一只餐叉。因为用一只餐叉很难吃到意大利面，所以假设哲学家必须用两只餐叉吃东西。他们只能使用自己左右手边的那两只餐叉。 上边的故事里有五个哲学家(不过我们写的程序可以有N个哲学家)，这些哲学家们只思考或吃饭，他们思考的时候不需要任何共享资源，但是吃饭的时候就必须使用餐具，而餐桌上的餐具是有限的，故事里，餐具是叉子，吃饭的时候要用两把叉子把面条从碗里捞出来。很显然把叉子换成筷子会更合理，因为一个哲学家需要两根筷子才能吃饭。 现在引入问题：有六个哲学家很穷，只买得起六根筷子。他们坐成一圈，两个人的中间放一根筷子。哲学家吃饭的时候必须同时得到左手边和右手边的 筷子。如果他身边的任何一位正在使用筷子，那他只有等着。如下图： 1 A A 6 5 3 以上就为我们要处理的哲学家就餐问题，接下来将编写程序模拟解决这个问题。 二、系统概要设计 2.1设计一个程序，能够显示当前各哲学家的状态和桌上餐具的使用情况，并能无死锁的推算出一状态各哲学家的状态和桌上餐具的使用情况。即设计一个能安排哲学家正常生活的程序。 为哲学家设计3种状态，即“等待”“进餐”“思考”。每个哲学家重复进行“等待”->“进餐”->“思考”的行动循环。其中：“等待”->“进餐”：只有一个哲学家处于等待进餐状态，且左右手两边的餐具都处于“空闲”状态时，可以发生这种状态改变。此状态改变发生后，哲学家拿起左右手两边的餐具。“进餐”->“思考”：此状态改变发生后，哲学家放下左右手上的餐具。餐具状态由“使用中”转变为“空闲”。“思考”->“等待”：哲学家思考结束后，无条件转入等待状态。由上所述，程序中应设置6个元素的信号量数组用来保持哲学家之间的同步。 2.2系统平台、语言及工具 （1）操作系统：Windows （2）程序设计语言：C++ (2013-2014学年 第二学期)重庆理工大学研究生课程论文 课程论文题目：基于ucos-ii操作系统解决哲学家就餐问题 (Problem of Philosophers’ Dining) 课程名称嵌入式系统实验与实践 课程类别□学位课□非学位课 任课教师万文略 所在学院电子学院 学科专业仪器仪表工程 姓名王小辉 学号51307260101 基于ucos-ii的哲学家就餐解决方案 摘要：针对经典的哲学家进餐问题，对多任务同步运行进行了研究。介绍了基于ucos-ii的多任务程序设计和任务间的通信机制，列举了可行的实现方法。并给出了最后的运行结果，使得哲学家能够正常进餐，不被饿死。 关键词：互斥同步多任务任务间通信顺序 一、问题陈列 哲学家进餐问题是荷兰学者Dijkstra 提出的经典问题之一,它是一个信号量机制问题的应用,在操作系统文化史上具有非常重要的地位。假设有5个哲学家，他们花费一生中的时光思考和吃饭。这些哲学家共用一个圆桌，每个哲学家都有一把椅子。在桌子中央是一碗通心面，在桌子上放着5只筷子。哲学家感到饥饿时，并试图拿起与他相近的两只筷子（他与邻近左、右之间的筷子）吃饭。要求： ①哲学家一次只能拿一只筷子,且必须拥有两只筷子才能吃饭。 ②如果筷子已被别人拿走，必须等到别人吃完放下才能拿到筷子。 ③每个哲学家在没拿到第二只筷子时，不会放弃手中已拿到的一只筷子。 ④假定哲学家每次吃饭的时间长度为单位1，吃完一次后则放下两只筷子。如果等待l0个单位时间长度之后，哲学家仍没有得到筷子吃饭，则被饿死。 设计一种方法使得任何一个哲学家都不被饿死。 二、问题分析 对问题分析可知，目前问题的瓶颈在于：死锁。 死锁的发生必须满足以下四个必要条件： ①互斥：至少有一个资源每次只能被一个进程使用，即非共享模式。这里指每只筷子只能被一个哲学家持有。 ②占有并等待。一个进程因请求资源而阻塞时，对已获得的资源保持不放。这里指哲学家在没拿到第二只筷子时，不会放弃手中已拿到的一只筷子。 /*方法1：规定奇数号哲学家先拿左边筷子，偶数号哲学家先拿右边筷子*/ semaphore chopstick[i]={1,1,1,1,1}/*定义信号量数组表示5支筷子，初值为1*/ 第i位哲学家的活动描述为： void philosopher (int i) { do { if (i mod 2) /*如果是奇数号哲学家*/ { wait(chopstick[i]); /*先拿左边筷子，再拿右边筷子*/ wait(chopstick[(i+1)mod 5]); } else /*如果是偶数号哲学家*/ { wait(chopstick[(i+1)mod 5]); /*先拿右边筷子，再拿左边筷子*/ wait(chopstick[i]); } eat; signal(chopstick[i]); signal(chopstick[(i+1)mod 5]); think; while(TRUE); } /*方法2：定义新的信号量room，控制同时就餐的哲学家数目不能超过4人。*/ semaphore chopstick[i]={1,1,1,1,1}/*定义信号量数组表示5支筷子，初值为1*/ semaphore room =4; /*控制最多有4人同时就餐，初值为4*/ 第i位哲学家的活动可以描述为： void philosopher(int i) { while(true) do{ think(); wait(room); //请求进入房间进餐 wait(chopstick[i]); //请求左手边的筷子 wait(chopstick[(i+1)%5]); //请求右手边的筷子 eat(); signal(chopstick[(i+1)%5]); //释放右手边的筷子 signal(chopstick[i]); //释放左手边的筷子 signal(room); //退出房间释放信号量room } }哲学家就餐问题报告
操作系统哲学家问题
用多线程同步方法解决哲学家就餐问题报告
哲学家进餐问题代码
哲学家就餐问题实验报告
操作系统哲学家进餐问题
操作系统课程设计-哲学家进餐问题
实践 哲学家进餐问题
实验一 哲学家就餐问题
哲学家就餐问题
哲学家就餐问题
哲学家吃饭问题 实验报告 操作系统
哲学家就餐问题教学内容
哲学家进餐问题讲课教案
哲学家就餐问题
哲学家就餐问题参考
相关主题
文本预览