操作系统专业课程设计哲学家进餐问题.doc

目录
1．设计题目和要求 1
1.1试验目标和设计要求 1
1.2 初始条件 1
2 总体设计思想及相关知识 2
2.1总体设计思想 2
2.2 临界区互斥编程原理 3
2.3开发环境和工具 3
3数据结构和模块说明 4
3.1 数据结构 4
3.2程序各模块步骤图 5
3.2.1 主程序模块 5
3.2.2 状态改变模块 6
3.2.3 返回哲学家状态模块 7
3.2.4 返回餐具状态模块 8
4. 源程序代码 9
5. 测试及结果 14
6. 课设总结 16
参考文件 17

1．设计题目和要求
1.1试验目标和设计要求
试验目标：经过实现哲学家进餐问题同时深入了解和掌握进程同时和互斥原理。
设计要求：哲学家有N个,也定全体到齐后开始讨论:在讨论间隙哲学家进餐,每人进餐时全部需使用刀、叉各一把，全部哲学家刀和叉全部拿到后才能进餐。哲学家人数、餐桌上部署自行设定，实现刀和叉互斥使用算法程序实现。
1.2 初始条件
（1）操作系统：windows
（2）程序设计语言：C++
（3）设定圆桌上有六个哲学家，三对刀叉，以下图摆放：

图1-1 哲学家进餐问题设定图
2 总体设计思想及相关知识
2.1总体设计思想
哲学家生活就是思索和吃饭，即思索，饿了就餐，再思索，循环往复。要求是：每一个哲学家只有在拿到在她左右刀叉后，才能够就餐；哲学家只能先拿一把刀或叉，再去拿另一把刀或叉，而不能同时去抓她旁边两把餐具，也不能从其它哲学家手中抢夺餐具；哲学家每次就餐后必需放下她手中两把餐具后恢复思索，不能强抓住餐具不放。
设计一个程序，能够显示目前各哲学家状态和桌上餐具使用情况，并能无死锁推算出下一状态各哲学家状态和桌上餐具使用情况。即设计一个能安排哲学家正常生活程序。
为哲学家设计3种状态，即“等候”“进餐”“思索”。每个哲学家反复进行“等候”->“进餐”->“思索”行动循环。其中：
“等候”->“进餐”：只有一个哲学家处于等候进餐状态，且左右手两边餐具全部处于“空闲”状态时，能够发生这种状态改变。此状态改变发生后，哲学家拿起左右手两边餐具。
“进餐”->“思索”：此状态改变发生后，哲学家放下左右手上餐具。餐具状态由“使用中”转变为“空闲”。
“思索”->“等候”：哲学家思索结束后，无条件转入等候状态。
由上所述，程序中应设置6个元素信号量数组，tools[6]，用来保持哲学家之间同时。

2.2 临界区互斥编程原理
不管是硬件临界资源，还是软件临界资源，多个进程必需互斥地对它进行访问。每个进程中访问临界资源那段代码称为临界区（Critical Section）。
每个进程中访问临界资源那段程序称为临界区（Critical Section）（临界资源是一次仅许可一个进程使用共享资源）。每次只准许一个进程进入临界区，进入后不许可其它进程进入。不管是硬件临界资源，还是软件临界资源，多个进程必需互斥地对它进行访问。
本程序关键使用了EnterCriticalSection (&cs)和LeaveCriticalSection (&cs)两个函数实现临界区互斥。
EnterCriticalSection (&cs)用来进入临界区，LeaveCriticalSection (&cs)用来离开临界区。

2.3开发环境和工具
系统平台：WINDOW环境
实现语言：C++
开发工具：VC++6.0

3数据结构和模块说明
3.1 数据结构
Philosopher
-number:int
-status:int
+Philosopher(in num:int)
+find() const:int
+getinfo() const:int
+Change():void
图3-1 哲学家类UML图

程序中定义一个哲学家类，包含两个私有对象和四个公有对象。
Number对象：报讯哲学家编号。
Status对象：用于保留目前该哲学家状态，0表示正在等候（即处于饥饿状态）1表示得到餐具正在吃饭，2表示正在思索
Philosopher(int num)方法：哲学家类结构函数，参数num表示哲学家编号
find() const方法：返回该哲学家编号
getinfo() const方法：返回哲学家目前状态
Change()方法：依据题目要求改变哲学家状态（等候->进餐->思索->等候…………）

另外，程序中包含一个公有对象，bool类型数组tools[6]，用来保留6把餐目前状态：true表示该餐具目前空闲，false表示该餐具目前正被使用。

程序中还包含两个公有函数：print和toolstatus。Print用来返回一个哲学家状态，toolstatus用来返回一个餐具状态。
3.2程序各模块步骤图
3.2.1 主程序模块

图3-2 主程序模块步骤图

3.2.2 状态改变模块
图3-3 状态改变模块Change()步骤图

3.2.3 返回哲学家状态模块

图3-4 返回哲学家状态模块print()步骤图

3.2.4 返回餐具状态模块

图3-5 返回餐具状态模块toolstatus(bool a)步骤图

4. 源程序代码
//试验目标：经过实现哲学家进餐问题同时深入了解和掌握进程同时和互斥原理。
//设计要求：哲学家有N个，也定全体抵达后开始讨论：在讨论间隙哲学家进餐，
//每人进餐时全部需使用刀、叉各一把，全部哲学家刀和叉全部拿到后才能进餐。哲学家人数、
//餐桌上部署自行设定，实现刀和叉互斥使用算法程序实现。

#include <windows.h>
#include <time.h>
#include <string>
#include <iostream>
#include <assert.h>

using namespace std;

bool tools[6]; //全局变量，用餐工具

CRITICAL_SECTION cs; //信号量, 在线程中使用，临界区

class Philosopher
{
private:
int number;
int status; /*标识目前哲学家状态,0表示正在等候(即处于饥饿状态),1表示得到两支筷子正在吃饭,2表示正在思索*/

public:
Philosopher(int num=0): status(2), number(num) { }
int find() const { return number; }
int getinfo() const { return status; }
void Change() ; //状态改变函数
};

void Philosopher::Change()
{
EnterCriticalSection (&cs) ; //进入临界区
if(status==1) //正在进餐
{
tools[number%6]=true; //放下左手工具
tools[(number-1)%6]=true; //放下右手工具
status=2; //改变状态为思索
}
else if(status==2) //思索中
{
status=0; //改变状态为等候
}
else if(status==0) //等候中
{

if(tools[number%6]&&tools[(number-1)%6]) //左右手两边工具均为空闲状态
{
tools[number%6]=false; //拿起左手工具
tools[(number-1)%6]=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'; //判定是否继续

for(int i=0;i<6;i++)
tools[i]=true; //3组刀叉全部未使用，初始化

Philosopher P1(1),P2(2),P3(3),P4(4),P5(5),P6(6);

InitializeCriticalSection (&cs) ; //初始化初始化临界区

cout<<"-----------------------状态说明示意图：-----------------------"<<endl;
cout<<" "<<"哲学家0号状态"<<" "<<endl;
cout<<"哲学家5号状态"<<" "<<"叉3状态"<<" "<<"刀1状态"<<" "<<"哲学家1号状态"<<endl;
cout<<" "<<"刀3状态"<<" "<<"叉1状态"<<endl;
cout<<"哲学家4号状态"<<" "<<"叉2状态"<<" "<<"刀2状态"<<" "<<"哲学家2号状态"<<endl;
cout<<" "<<"哲学家3号状态"<<" "<<endl;
cout<<"餐具状态，“用”表示使用中，“闲”表示空闲中。"<<endl;
cout<<"--------------------------"<<endl;
cout<<"哲学家们开始生活："<<endl;
cout<<endl;
cout<<endl;

while(con=='y')
{
P1.Change();
P2.Change();
P3.Change();
P4.Change();
P5.Change();
P6.Change();
cout<<"目前状态为："<<endl;
cout<<" "<<P1.find()<<print(&P1)<<" "<<endl;
cout<<P6.find()<<print(&P6)<<" "<<toolstatus(tools[0])<<" "<<toolstatus(tools[1])<<" "<<P2.find()<<print(&P2)<<endl;
cout<<" "<<toolstatus(tools[5])<<" "<<toolstatus(tools[2])<<endl;
cout<<P5.find()<<print(&P5)<<" "<<toolstatus(tools[4])<<" "<<toolstatus(tools[3])<<" "<<P3.find()<<print(&P3)<<endl;
cout<<" "<<P4.find()<<print(&P4)<<" "<<endl;
cout<<"--------------------------"<<endl;
cout<<"若要继续下一状态，输入y；输入其它，结束程序：";
cin>>con;
Sleep(20);
}
DeleteCriticalSection (&cs) ; //退出资源区
return 0;
}
5. 测试及结果

图5-1 程序运行开始界面

图5-2 哲学家状态1

图5-3 哲学家状态2

图5-4 哲学家状态3

图5-5 哲学家状态4

图5-6 退出程序
6. 课设总结
经过了前后共2周时间，我完成了这次课程设计。
经过这次课程设计，我学到了很多书本上学不到知识，注意到了很多书本上没有提到东西。
而且，经过这次设计，我得到了一个很好理论联络实际机会，锻炼了经过理论处理实际问题能力。正所谓“实践出真知”，有些代码看上去没什么问题，不过实际运行起来就是不出正确结果。代码内部可能存在逻辑或语法等方面我们平时不会注意到小问题，经过这次课程设计，我积累了不少这么小问题处理方法。
设计中总会碰到这么那样问题，碰到问题势必需自己分析问题，经过多种渠道处理问题，比如利用互联网。这次课程设计也加强了我上网查数检索问题能力。有些时候，学习到知识是次要，关键是学习知识方法。

参考文件
[1]宗大华，宗涛，陈吉人著. 操作系统. 北京：人民邮电出版社，
[2]李爱华，程磊著. 面相对象程序设计（C++语言）. 北京: 清华大学出版社，