下载文档原格式
哲学家进餐问题问题描述：有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; }。
哲学家就餐问题哲学家就餐问题模拟数学与计算机学院课程设计说明书课程名称: 操作系统原理-课程设计课程代码: 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 程序类的说明........................................... 错误!未定义书签。
哲学家进餐问题-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)]);)就全被阻塞了，这就出现了死锁。
4.10经典进程互斥同步问题：哲学家进餐问题（the dining philosophers problem）问题描述：（由Dijkstra首先提出并解决）5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支，哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。
要考虑的问题是如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子。
在这里，哲学家的生活规律是：Repeat思考；取fork[i];取fork[(i+1) mod 5]；进食；放fork[i];放fork[(i+1) mod 5]；Until false;实现方法：一个信号量表示一根筷子，五个信号量构成信号量数组chop[5]，所有信号量初始值为1。
第i个哲学家的进餐过程为：思考问题P(chop[i]);P(chop(i+1) mod 5]);进餐V(chop[i]);V(chop[(i+1) mod 5]);该算法可保证两个相邻的哲学家不能同时进餐，但不能防止五位哲学家同时拿起各自左边的筷子、又试图拿起右边的筷子，这会引起死锁。
这里给出可以防止死锁发生的一种解决方案：Semaphore fork[5] = {1};Semaphore room = 4;Void philospher (int i) {while (true) {thinking();P( room );P(fork[i]);P(fork[(i+1) mod 5])eating();V(fork[i]);V(fork[(i+1) mod 5])V(room); }。
哲学家进餐问题(操作系统)哲学家进餐问题(操作系统)1.简介1.1 背景介绍哲学家进餐问题是计算机科学中一个经典的并发问题，最早由Edsger Dijkstra在1965年提出。
1.2 问题描述问题的场景是五位哲学家围坐在一张圆桌前，每个哲学家面前有一碗饭和一根筷子。
哲学家需要交替地思考和进餐，但是他们只能使用左右两边的筷子来进餐。
1.3 目标设计一个算法来保证哲学家们能够交替地进餐，同时避免死锁和饥饿现象的发生。
2.解决方案2.1 简单解法一个简单的解法是给每个哲学家编号，规定奇数号哲学家先拿左边的筷子，偶数号哲学家先拿右边的筷子。
当一个哲学家需要拿筷子时，他会先检查他的两边是否有其他哲学家正在使用，如果没有，他就可以拿起两边的筷子进餐。
否则，他需要等待直到两边的筷子都可用。
2.2 改进解法上述简单解法可能会导致死锁问题。
为了避免死锁，我们可以引入资源分级的概念。
每个筷子被分为两个等级，分别是主要资源和次要资源。
哲学家需要按照顺序来获取资源，例如，先获取主要资源，然后获取次要资源。
3.算法实现3.1 数据结构我们可以使用一个数组来表示圆桌上的五个筷子，同时使用一个锁数组来表示每个筷子的状态（是否被占用）。
3.2 算法流程在哲学家进餐问题中，每个哲学家都需要经历思考和进餐两个过程，我们可以使用线程来模拟这两个过程。
4.算法分析4.1 死锁问题通过引入资源分级的概念，我们成功避免了死锁问题的发生。
每个哲学家按照顺序获取资源，不会出现他们都在等待同一个资源的情况。
4.2 饥饿问题在我们的算法中，每个哲学家都会交替地进餐和思考，因此不会出现饥饿问题。
5.附件本文档暂无附件。
6.法律名词及注释6.1 死锁死锁是指在并发系统中，两个或多个进程或线程无限期地互相等待对方所占有的资源的情形。
6.2 饥饿饥饿是指某个进程或线程因无法获得所需的资源而无法继续执行的情况。
一、需求分析有一个故事是这样的：假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。
吃东西的时候，他们就停止思考，思考的时候也停止吃东西。
餐桌中间有一大碗意大利面，每两个哲学家之间有一只餐叉。
因为用一只餐叉很难吃到意大利面，所以假设哲学家必须用两只餐叉吃东西。
他们只能使用自己左右手边的那两只餐叉。
上边的故事里有五个哲学家(不过我们写的程序可以有N个哲学家)，这些哲学家们只思考或吃饭，他们思考的时候不需要任何共享资源，但是吃饭的时候就必须使用餐具，而餐桌上的餐具是有限的，故事里，餐具是叉子，吃饭的时候要用两把叉子把面条从碗里捞出来。
很显然把叉子换成筷子会更合理，因为一个哲学家需要两根筷子才能吃饭。
现在引入问题：有六个哲学家很穷，只买得起六根筷子。
他们坐成一圈，两个人的中间放一根筷子。
哲学家吃饭的时候必须同时得到左手边和右手边的筷子。
如果他身边的任何一位正在使用筷子，那他只有等着。
如下图：AA 4 A1、2、3、4、5、6为哲学家A为一根筷子以上就为我们要处理的哲学家就餐问题，接下来将编写程序模拟解决这个问题。
二、系统概要设计2.1设计一个程序，能够显示当前各哲学家的状态和桌上餐具的使用情况，并能无死锁的推算出一状态各哲学家的状态和桌上餐具的使用情况。
即设计一个能安排哲学家正常生活的程序。
为哲学家设计3种状态，即“等待”“进餐”“思考”。
每个哲学家重复进行“等待”->“进餐”->“思考”的行动循环。
其中：“等待”->“进餐”：只有一个哲学家处于等待进餐状态，且左右手两边的餐具都处于“空闲”状态时，可以发生这种状态改变。
此状态改变发生后，哲学家拿起左右手两边的餐具。
“进餐”->“思考”：此状态改变发生后，哲学家放下左右手上的餐具。
餐具状态由“使用中”转变为“空闲”。
“思考”->“等待”：哲学家思考结束后，无条件转入等待状态。
由上所述，程序中应设置6个元素的信号量数组用来保持哲学家之间的同步。
哲学家就餐问题是在计算机科学中的一个经典问题，用来演示在并行计算中多线程同步(Synchronization)时产生的问题。
在1971年，著名的计算机科学家艾兹格·迪科斯彻提出了一个同步问题，即假设有五台计算机都试图访问五份共享的磁带驱动器。
稍后，这个问题被托尼·霍尔重新表述为哲学家就餐问题。
这个问题可以用来解释死锁和资源耗尽。
哲学家就餐问题可以这样表述，假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。
吃东西的时候，他们就停止思考，思考的时候也停止吃东西。
餐桌中间有一大碗意大利面，每两个哲学家之间有一只餐叉。
因为用一只餐叉很难吃到意大利面，所以假设哲学家必须用两只餐叉吃东西。
他们只能使用自己左右手边的那两只餐叉。
哲学家就餐问题有时也用米饭和筷子而不是意大利面和餐叉来描述，因为很明显，吃米饭必须用两根筷子。
哲学家从来不交谈，这就很危险，可能产生死锁，每个哲学家都拿着左手的餐叉，永远都在等右边的餐叉（或者相反）。
即使没有死锁，也有可能发生资源耗尽。
例如，假设规定当哲学家等待另一只餐叉超过五分钟后就放下自己手里的那一只餐叉，并且再等五分钟后进行下一次尝试。
这个策略消除了死锁（系统总会进入到下一个状态），但仍然有可能发生“活锁”。
如果五位哲学家在完全相同的时刻进入餐厅，并同时拿起左边的餐叉，那么这些哲学家就会等待五分钟，同时放下手中的餐叉，再等五分钟，又同时拿起这些餐叉。
在实际的计算机问题中，缺乏餐叉可以类比为缺乏共享资源。
一种常用的计算机技术是资源加锁，用来保证在某个时刻，资源只能被一个程序或一段代码访问。
当一个程序想要使用的资源已经被另一个程序锁定，它就等待资源解锁。
当多个程序涉及到加锁的资源时，在某些情况下就有可能发生死锁。
例如，某个程序需要访问两个文件，当两个这样的程序各锁了一个文件，那它们都在等待对方解锁另一个文件，而这永远不会发生。
[编辑]服务生解法一个简单的解法是引入一个餐厅服务生，哲学家必须经过他的允许才能拿起餐叉。
操作系统（哲学家进餐问题）哲学家进餐问题：有五个哲学家，他们的⽣活⽅式是交替地进⾏思考和进餐。
哲学家们共⽤⼀张园桌，分别坐在周围五张椅⼦上。
在圆桌上五⽀筷⼦，平时⼀个哲学家进⾏思考，饥饿时便试图取⽤其左右最靠近他的筷⼦，只有在他拿到两⽀筷⼦时才能进餐。
进程毕，放下筷⼦⼜继续思考。
问题分析：筷⼦是临界资源，⼀次只能被⼀个哲学家使⽤。
因此，五个⼈不能同时拿起左边的筷⼦（或右边）否则或引起死锁。
解决⽅案：（1）⾄多只允许四位哲学家同时拿左边的筷⼦，最终保证有⼀位哲学家能够进餐，并且⽤完能够释放筷⼦，让更多的哲学家进餐。
（2）仅当哲学家左右两只筷⼦都可以⽤的时候，才允许拿筷⼦进餐。
semaphore chopstick[5]={1,1,1,1,1};//五个信号量，⼀个信号量代表⼀只筷⼦semaphore mutex=1;Pi(){while(1){wait(mutex);//设置信号量，防⽌其它⼈争夺资源wait(chopstick[i]);wait(chopstick[(i+1)%5]);signal(mutex);//拿到两只筷⼦后释放信号量吃饭;signal(chopstick[i]);//吃过饭后，释放筷⼦资源signal(chopstick[(i+1)%5]);}}（3）奇数号哲学家先拿左边的，再拿右边的；偶数则相反。
即五位哲学家都先竞争奇数号筷⼦，获得后再去竞争偶数号筷⼦，最终总会有⼀位哲学家有两只筷⼦。
semaphore chopstick[5]={1,1,1,1,1};Pi(){while(1){if(i%2！=0){//奇数号哲学家wait(chopstick[i]);//拿左边的wait(chopstick[(i+1)%5]);//右边的}else{//偶数号哲学家wait(chopstick[(i+1)%5]);//右边的wait(chopstick[i]);//左边的}进餐;signal(chopstick[i]);//释放筷⼦资源signal(chopstick[(i+1)%5]);}}。
