淮北师范大学
课程设计报告
哲学家就餐问题
学 院 专 业 学 号 学 生 姓 名 指导教师姓名
20xx年3月 14日
1.实验目的与设计要求
实验目的:通过实现哲学家进餐问题的同步深入了解和掌握进程同步和互斥的原理。
设计要求:哲学家有N个,也定全体到齐后开始讨论:在讨论的间隙哲学家进餐,每人进餐时都需使用两双筷子,所有哲学家两双筷子都拿到后才能进餐。哲学家的人数、餐桌上的布置自行设定,实现筷子互斥使用算法的程序实现。
2.总体设计思想
哲学家的生活就是思考和吃饭,即思考,饿了就餐,再思考,循环往复。要求是:每一个哲学家只有在拿到位于他左右的筷子后,才能够就餐;哲学家只能先拿一个筷子,再去拿另一个筷子,而不能同时去抓他旁边的两把餐具,也不能从其他哲学家手中抢夺餐具;哲学家每次就餐后必须放下他手中的两把餐具后恢复思考,不能强抓住餐具不放。
设计一个程序,能够显示当前各哲学家的状态和桌上餐具的使用情况,并能无死锁的推算出下一状态各哲学家的状态和桌上餐具的使用情况。即设计一个能安排哲学家正常生活的程序。
为哲学家设计3种状态,即“等待”“进餐”“思考”。每个哲学家重复进行“等待”->“进餐”->“思考”的行动循环。其中:
“等待”->“进餐”:只有一个哲学家处于等待进餐状态,且左右手两边的餐具都处于“空闲”状态时,可以发生这种状态改变。此状态改变发生后,哲学家拿起左右手两边的餐具。
“进餐”->“思考”:此状态改变发生后,哲学家放下左右手上的餐具。餐具状态由“使用中”转变为“空闲”。
“思考”->“等待”:哲学家思考结束后,无条件转入等待状态。
由上所述,程序中应设置6个元素的信号量数组,tools[6],用来保持哲学家之间的同步。
程序中定义一个哲学家类,包含两个私有对象和四个公有对象。
Number对象:哲学家的编号。
Status对象:用于保存当前该哲学家的状态,0表示正在等待(即处于饥饿状态)
1表示得到餐具正在吃饭,2表示正在思考
Philosopher(int num)方法:哲学家类构造函数,参数num表示哲学家编号 find() const方法:返回该哲学家编号
getinfo() const方法:返回哲学家当前状态
Change()方法:根据题目要求改变哲学家的状态(等待->进餐->思考->等
待????)
另外,程序中包含一个公有对象,bool类型数组tools[5],用来保存5个筷子当前状态:true表示该餐具当前空闲,false表示该餐具当前正被使用。
程序中还包含两个公有函数:print和toolstatus。Print用来返回一个哲学家的状态,toolstatus用来返回一个餐具的状态。
3.程序各模块流程图
3. 1 主程序模块
3.2 状态改变模块
3.3 返回哲学家状态模块
3.4 返回餐具状态模块
4. 源程序代码
#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<<"筷子的状态,用表示使用中,闲表示空闲中。"<<endl;
cout<<"--------------------------------------------------------------"<<endl;
//cout<<"哲学家们开始生活:"<<endl;
//cout<<"当前状态:";
cout<<endl;
//cin>>con;
while(con=='y')
{
P1.Change(); P2.Change(); P3.Change(); P4.Change(); P5.Change(); cout<<"当前状态为:"<<endl;
cout<<" "<<P1.find()<<print(&P1)<<" "<<endl;
cout<<" "<<toolstatus(tools[0])<<" "<<toolstatus(tools[1])<<endl; cout<<" "<<P5.find()<<print(&P5)<<" "<<P2.find()<<print(&P2)<<endl; cout<<" "<<toolstatus(tools[4])<<" "<<toolstatus(tools[2])<<endl; cout<<" "<<P4.find()<<print(&P4)<<" "<<P3.find()<<print(&P3)<<endl;
cout<<" "<<toolstatus(tools[3])<<endl;
cout<<"--------------------------"<<endl;
cout<<"若要继续下一状态,输入y;输入n进入死锁;输入其他,结束程序:"; cin>>con;
Sleep(20);
}
while(con=='n')
{
P1.dead_lock();
P2.dead_lock(); P3.dead_lock(); P4.dead_lock(); P5.dead_lock();
cout<<"死锁情况"<<endl;
cout<<" "<<P1.find()<<print(&P1)<<" "<<endl;
cout<<" "<<toolstatus(tools[0])<<" "<<toolstatus(tools[1])<<endl; cout<<" "<<P5.find()<<print(&P5)<<" "<<P2.find()<<print(&P2)<<endl; cout<<" "<<toolstatus(tools[4])<<" "<<toolstatus(tools[2])<<endl; cout<<" "<<P4.find()<<print(&P4)<<" "<<P3.find()<<print(&P3)<<endl; cout<<" "<<toolstatus(tools[3])<<endl;
cout<<"--------------------------"<<endl;
cout<<"输入n继续;输入其他,结束程序:";
cin>>con;
Sleep(20);
}
DeleteCriticalSection (&cs) ; //退出资源区
return 0;
}
5. 测试及结果
第二篇:5位哲学家进餐的问题
模拟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之间的随机数字。5个哲学家都从思考开始。可以考虑使用usleep()还可以使用旗语(semaphore)的 P() 和 V()来解决互斥、#include <stdlib.h>#include <iostream.h>#include <time.h>enum PhState{Thinking=0,Waiting,Eating};//哲学家状态int stick[5];//筷子状态,1表示使用,0表示空闲PhState phstate[5];//哲学家状态int timerforPh[5];// 定时器,确定状态变化的时刻const int SPAN = 91;//定义思考和进食的最长时间//模拟当i饥饿时,采用的策略。void hungry(int i){int left = (i)%5;int right = (i+1)%5;if(stick[left]==0 && stick[right]==0){stick[left]=stick[right]=1;phstate[i]=Eating;timerforPh[i]=rand()%SPAN+1;//设置吃饭时间}else{phstate[i]=Waiting;}}//从等待中唤醒void wakeup(int i){//唤醒后的操作同思考时饥饿的操作
相同hungry( i);}//模拟吃完后的动作void ate(int i){stick[(i)%5]=0;stick[(i+1)%5]=0;//唤醒左右哲学家的顺序可以改成随机的,这里仅仅是固定顺序if(phstate[(5+i-1)%5]==Waiting)wakeup((5+i-1)%5);if(phstate[(i+1)%5]==Waiting)wakeup((i+1)%5);phstate[i]=Thinking;timerforPh[i]=rand()%SPAN+1;//设置思考时间}//输出当前状态,参数为当前时间void print_state(int cur_time){char state_ch[]={'0','!','X'};cout.width(4);cout<<cur_time<<"ms : ";for(int i=0; i<5; i++){cout.width(2);cout<<state_ch[phstate[i]]<<' ';}cout<<endl;}//模拟器void simulator(){//初始化srand(time(NULL));for(int i=0; i<5;i++){stick[i]=0;timerforPh[i]=rand()%SPAN+1;phstate[i]=Thinking;}//模拟开始long time = 0;//时钟int eating_event_cnt=0;//进食成功事件次数while(eating_event_cnt<50){time++;//检查哪个哲学家的状态需要改变for(int i=0;i<5;i++){switch(phstate[i]){case Waiting:++timerforPh[i];//记录等待时间break;case Thinking:if(--timerforPh[i]<0){hungry(i);print_state(time);}break;default:if(--timerforPh[i]<0){ate(i);print_state(time);eating_event_cnt++;}break;};}}}int main(int argc, char* argv[]){simulator();return 0;}