数学与计算机学院
课程设计说明书
课 程 名 称: 操作系统原理-课程设计
课 程 代 码: 8404061
题 目: 哲学家就餐问题模拟
年级/专业/班: 09级信息与计算科学三班
学 生 姓 名: **
学 号: ***
开 始 时 间: 20** 年 05 月 14 日
完 成 时 间: 20** 年 05月 31 日
指导教师签名: 年 月 日
1 引 言
1.1问题的提出
哲学家进餐问题也是一个经典的同步问题,它是由Dijkstra提出并解决的。哲学家进餐问题是这样的:5个哲学家以思考、吃饭交替进行的方式生活,他们共享一张周围有5把椅子的圆桌,每人一把椅子,在桌子上摆有5个饭碗和5只筷子。当一个哲学家思考时,他不与邻座同事发生联系。当一哲学家饿了,他就试图拿起他左右两边的筷子吃饭。显然,他不能拿起已抓在他的邻座手中的筷子,于是,他可能只拿到一只甚至一只筷子也拿不到。当一个饥饿的哲学家得到了两只筷子,他就可以吃饭。当他用饭毕,就放下筷子并再次开始思考。5个哲学家共享5支筷子,最多只能不相邻的两个哲学家同时就餐。
在多道程序设计环境下,进程同步问题十分重要,其中“哲学家进餐问题”是较有代表性的。通过对该问题的研究学习和实践,可以帮助我们更好的理解和掌握临界资源、进程同步的概念和实现方法。
1.2任务与分析
本课题主要的目的通过实现哲学家进餐问题的同步深入了解和掌握进程同步和互斥的原理。
2.总体设计思想及相关知识
2.1总体设计思想
哲学家的生活就是思考和吃饭,即思考,饿了就餐,再思考,循环往复。要求是:每一个哲学家只有在拿到位于他左右筷子,才能够就餐;哲学家只能先拿一只筷子,再去拿另一只筷子,而不能同时去抓他旁边的两只筷子,也不能从其他哲学家手中抢夺筷子;哲学家每次就餐后必须放下他手中的两只筷子后恢复思考,不能强抓住筷子不放。
设计一个程序,能够显示当前各哲学家的状态和桌上餐具的使用情况,并能无死锁的推算出下一状态各哲学家的状态和筷子的使用情况。即设计一个能安排哲学家正常生活的程序。
为哲学家设计3种状态,即“等待”“进餐”“思考”。每个哲学家重复进行“等待”->“进餐”->“思考”的行动循环。其中:
“等待”->“进餐”:只有一个哲学家处于等待进餐状态,且左右手两边的筷子都处于“空闲”状态时,可以发生这种状态改变。此状态改变发生后,哲学家拿起左右手两边的筷子。
“进餐”->“思考”:此状态改变发生后,哲学家放下左右手上的筷子。筷子状态由“使用中”转变为“空闲”。
“思考”->“等待”:哲学家思考结束后,无条件转入等待状态。
由上所述,程序中应设置5个元素的信号量数组,chopsticks[5],用来保持哲学家之间的同步。
2.2临界区互斥编程原理
不论是硬件临界资源,还是软件临界资源,多个进程必须互斥地对它进行访问。每个进程中访问临界资源的那段代码称为临界区(Critical Section)。
每个进程中访问临界资源的那段程序称为临界区(Critical Section)(临界资源是一次仅允许一个进程使用的共享资源)。每次只准许一个进程进入临界区,进入后不允许其他进程进入。不论是硬件临界资源,还是软件临界资源,多个进程必须互斥地对它进行访问。
本程序主要使用了EnterCriticalSection (&cs)和LeaveCriticalSection (&cs)两个函数实现临界区互斥。
EnterCriticalSection (&cs)用来进入临界区,LeaveCriticalSection (&cs)用来离开临界区。
3 程序运行平台
Visual Studio 2008。
具体操作如下:新建项目,添加相应的源文件,再编译,链接,执行等。
4 程序类的说明
程序中定义一个哲学家类,包含两个私有对象和四个公有对象。
Philosopher |
-number:int -status:int |
+Philosopher(in num:int) +find() const:int +getinfo() const:int +Change():void |
图4-1 哲学家类的UML图
Number对象:哲学家的编号。
Status对象:用于保存当前该哲学家的状态,0表示正在等待(即处于饥饿状态)1表示得到餐具正在吃饭,2表示正在思考
Philosopher(int num)方法:哲学家类构造函数,参数num表示哲学家编号
find() const方法:返回该哲学家编号
getinfo() const方法:返回哲学家当前状态
Change()方法:根据题目要求改变哲学家的状态(等待->进餐->思考->等待…………)
另外,程序中包含一个公有对象,bool类型数组chopsticks[5],用来保存5只筷子当前状态:true表示该餐具当前空闲,false表示该餐具当前正被使用。
程序中还包含两个公有函数:print和chopstickstatus。Print用来返回一个哲学家的状态,chopstickstatus用来返回一个餐具的状态。
5 程序各个模块流程图
5.1主程序模块
图5-1 主程序模块流程图
5.2 状态改变模块
图5-2状态改变模块Change()流程图
5.3 返回哲学家状态图
图5-3 返回哲学家状态模块print()流程图
5.4返回餐具状态模块
图5- 4返回餐具状态模块chopsticksstatus(bool a)流程图
6系统测试
首先进入Visual Studio 2008,进入源程序。生成称解决方案,然后运行。
图6-1哲学家开始状态1
图6-2哲学家状态2
图6-3哲学家状态3
图6-4哲学家状态4
8 结论
对自己完成的题目进行总结,包括程序的功能、创新点(与众不同的地方)及程序存在的问题和修改对策。
通过本次课程设计的过程,我了解了金典的同步问题哲学家就餐问题。发现自己对互斥变量把握不太清楚。及在编程过程中自己对C++语法的不熟悉。
本程序通过定义一个哲学家类,模拟了哲学家就餐,思考和等待的不同状态。
附 录
附录1 源程序清单
#include<stdio.h>
#include<stdlib.h>
#include <windows.h>
#include <string>
#include <iostream>
using namespace std;
bool chopsticks[5]; //全局变量,用餐工具
CRITICAL_SECTION cs; //信号量, 在线程中使用,临界区
class Philosopher
{
private:
int number;
int status; /*标记当前哲学家的状态,0表示正在等待(即处于饥饿状态),1表示得到两支筷子正在吃饭,2表示正在思考*/
public:
Philosopher(int num=1): status(2), number(num) { }
int find()//定义常成员函数返回该哲学家编号
const
{
return number;
}
int getinfo()//定义常成员函数返回哲学家当前状态
const
{
return status;
}
void Change() ; //状态改变函数
};
void Philosopher::Change()
{
EnterCriticalSection (&cs) ; //进入临界区
if(status==1) //正在进餐
{
chopsticks[(number)%5]=true; //放下左手工具
chopsticks[(number+1)%5]=true; //放下右手工具
status=2; //改变状态为思考
}
else if(status==2) //思考中
{
status=0; //改变状态为等待
}
else if(status==0) //等待中
{
if(chopsticks[number%5]&&chopsticks[(number+1)%5]) //左右手两边筷子均为空闲状态
{
chopsticks[number%5]=false; //拿起左边的筷子
chopsticks[(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 chopstickstatus(bool a)//返回筷子状态
{
string state;
if(a==true)
state="闲";
if(a==false)
state="用";
return state;
}
int main()
{
char con = 'y'; //判断是否继续
for(int i=1;i<=5;i++)
chopsticks[i]=true; //5根筷子都未使用,初始化
Philosopher P1(1),P2(2),P3(3),P4(4),P5(5);
InitializeCriticalSection (&cs) ; //初始化初始化临界区
cout<<"-----------------------状态说明示意图:-----------------------"<<endl;
cout<<"哲学家号的状态"<<" "<<"筷子的状态"<<" "<<"筷子的状态"<<" "<<"哲学家号的状态"<<endl;
cout<<" "<<"筷子的状态"<<endl;
cout<<"哲学家号的状态"<<" "<<"筷子的状态"<<" "<<"筷子的状态"<<" "<<"哲学家号的状态"<<endl;
cout<<" "<<"哲学家号的状态"<<" "<<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)<<" "<<chopstickstatus(chopsticks[1])<<" "<<chopstickstatus(chopsticks[2])<<" "<<P2.find()<<print(&P2)<<endl;
cout<<" "<<chopstickstatus(chopsticks[5])<<" "<<endl;
cout<<P3.find()<<print(&P3)<<" "<<chopstickstatus(chopsticks[3])<<" "<<chopstickstatus(chopsticks[4])<<" "<<P4.find()<<print(&P4)<<endl;
cout<<" "<<P5.find()<<print(&P5)<<" "<<endl;
cout<<"--------------------------"<<endl;
cout<<"若要继续下一状态,输入y;输入其他,结束程序:";
cin>>con;
Sleep(20);
}
DeleteCriticalSection (&cs) ; //退出资源区
return 0;
}
第二篇:操作系统哲学家就餐问题课程设计
课 程 设 计
题 目:用多线程同步方法解决哲学家就餐问题(Dining-Philosophers Problem)
学 院:计算机科学与技术学院
专 业:
班 级:
姓 名:
指导教师
20**年6月28日
目录
一、课程设计任务书…………………………………………………………………………………..………….2
二、设计题目与要求………………………………………………………………………………………………4
三、总体设计思想及系统平台、语言、工具……………………………………………………………………4
四、数据结构与模块说明…………………………………………………………………………………………5
五、用户名、源程序名、目标程序名和源程序…………………………………………………………………6
六、运行结果与运行情况.…………………………………………………………………………………………7
七、调试记录……………………………………………………………………………………………………… 9
八、自我评析和总结………………………………………………………………………………………………14
九、参考文献………………………………………………………………………………………………………14
十、评分表…………………………………………………………………………………………………………15
课程设计任务书3
学生姓名:
专业班级:
指导教师:
工作单位: 计算机科学与技术学院
题目: 用多线程同步方法解决哲学家就餐问题(Dining-Philosophers Problem)
初始条件:
1.操作系统:Linux
2.程序设计语言:C语言
3.共有5个哲学家需用餐。只许4个哲学家入席且桌上有5支筷子。
要求完成的主要任务: (包括课程设计工作量及其技术要求,以及说明书撰写等具体要求)
1.技术要求:
1)为每个哲学家产生一个线程,设计正确的同步算法
2)每个哲学家取得一双筷子开始用餐后,即时显示“Dining…”和该哲学家的自定义标识符以及餐桌上所有几位哲学家标识符及其所坐的位置。
3)设定共有5个哲学家需用餐。每位用餐耗时10秒钟以上。
4)多个哲学家须共享操作函数代码。
2. 设计说明书内容要求:
1)设计题目与要求
2)总的设计思想及系统平台、语言、工具等。
3)数据结构与模块说明(功能与流程图)
4)给出用户名、源程序名、目标程序名和源程序及其运行结果。(要注明存储各个程序及其运行结果的Linux主机IP地址和目录。)
5)运行结果与运行情况
(提示: (1)连续存储区可用数组实现。
(2)编译命令可用: cc -lpthread -o 目标文件名 源文件名
(3)多线程编程方法参见附件。)
3. 调试报告:
1) 调试记录
2)自我评析和总结
上机时间安排:
18周一 ~ 五 08:0 - 12:00
指导教师签名: 年 月 日
系主任(或责任教师)签名: 年 月 日
用多线程同步方法解决哲学家就餐问题
(Dining-Philosophers Problem)
1.设计题目与要求
1.1设计题目描述:
用多线程同步方法解决哲学家就餐问题(Dining-Philosophers Problem)
1.2要求:
1)为每个哲学家产生一个线程,设计正确的同步算法
2)每个哲学家取得一双筷子开始用餐后,即时显示“Dining…”和该哲学家的自定义标识符以及餐桌上所有几位哲学家标识符及其所坐的位置。
3)设定共有5个哲学家需用餐。每位用餐耗时10秒钟以上。
4)多个哲学家须共享操作函数代码。
2.总体设计思想及系统平台、语言、工具
2.1总体设计思想
哲学家就餐问题,即共有5个哲学家绕一个圆桌做在5个位置上,他们每2个人中间有一只筷子,共5只筷子,只有当每个哲学家取得他左右两边的筷子时,哲学家才能开始就餐,其它时间,哲学家只能思考或等待筷子。为避免哲学家互相等待对方的筷子发生死锁,本次课程设计要求只许4个哲学家入席,以保证至少有一个哲学家能够进餐。
本课程设计将room 作为信号量,将其初始化为4,以保证只允许4个哲学家同时入席就餐,这样就能保证至少有一个哲学家可以就餐。针对每个哲学家,通过共享操作函数代码,分别建立5个线程,以实现同步哲学家就餐,而申请进入餐厅的哲学家进入room 的等待队列,根据FIFO 的原则,总会进入到餐厅就餐,因此不会出现饿死和死锁的现象,针对5只筷子分别设置了5个互斥信号量,以保证每只筷子每次只能被取得一次。
2.2系统平台、语言及工具
(1)操作系统:Linux
(2)程序设计语言:C语言
(3)工具:编辑工具Vi、编译器gcc
3.数据结构与模块说明
线程创建函数pthread_create声明如下:
#include <pthread.h>
int pthread_create (pthread_t *thread,pthread_attr_t *attr,Void* (*start_routine)(void *),void *arg);
等待其它线程结束函数pthread_join声明如下:
#include <pthread.h>
int pthread_join (pthread_t th,void *thread_return);
信号量的数据类型为结构sem_t,它本质上是一个长整型的数。
初始化信号量函数sem_init声明如下:
#include <semaphore.h>
sem_init (sem_t *sem, int pshared, unsigned int value);
增加信号量值函数sem_post声明如下:
#include <semaphore.h>
Sem_post ( sem_t *sem );
减少信号量值函数sem_wait声明如下
#include <semaphore.h>
Sem_wait ( sem_t *sem );
主要数据结构声明:
#define NUMBERS 5 //将哲学家人数NUMBERS定义为5
sem_t chopstics[NUMBERS] //定义5只筷子的互斥信号量chopstics
sem_t room //定义避免死锁的同步信号量room
线程共享函数伪代码:
void *Share(int i)
{
think();
wait(room); //请求入席进餐
wait(chopstick[i]); //请求左手边的筷子
wait(chopstick[(i+1)%5]); //请求右手边的筷子
eat();
signal(chopstick[i]); //释放左手边的筷子
signal(chopstick[(i+1)%5]); //释放右手边的筷子
signal(room); //退出席位释放信号量chairs
}
4.用户名、源程序名、目标程序名和源程序
4.1用户名、源程序名、目标程序名
用户名:
源程序名:
目标程序名:
4.2源程序
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>
#define NUMBERS 5
sem_t chopstics[NUMBERS];
sem_t room;
sem_t mutex;
int flag[NUMBERS]={0,0,0,0,0};
int chairs[NUMBERS]={0,1,2,3,4};
int i,j;
void *Share(int threadid);
int main()
{
int error;
pthread_t threads[NUMBERS];
for(i=0;i<NUMBERS;i++)
{
sem_init(&chopstics[i],0,1);
}
sem_init(&room,0,NUMBERS-1);
sem_init(&mutex,0,1);
for(i=0;i<NUMBERS;i++)
{
error = pthread_create(&threads[i],NULL,(void*)Share,(void *)i);
if(error)
{
printf("ERROR: thread create failed!!!");
//exit(-1);
}
}
for(i=0;i<NUMBERS;i++)
{
pthread_join(threads[i],NULL);
}
}
void *Share(int threadid)
{
int i = threadid;
sem_wait(&room);
flag[i]=1;
sem_wait(&chopstics[i]);
printf("philosopher %d get chopstics %d\n",i,i);
sem_wait(&chopstics[(i+1)%NUMBERS]);
printf("philosopher %d get chopstics %d\n",i,(i+1)%NUMBERS);
sem_wait(&mutex);
printf("\n*********************************************\n");
printf("Dining...\n");
printf("philosopher: %d ,on chairs %d and eating\n",i,chairs[i]);
for(j=0;j<NUMBERS;j++)
{
if((j!=i)&&flag[j])
printf("philosopher %d ,on chairs %d and hungry\n",j,chairs[j]);
}
sleep(3);
sem_post(&mutex);
sem_post(&chopstics[i]);
sem_post(&chopstics[(i+1)%NUMBERS]);
printf("philosopher %d is full and put down chopstics %d and %d and left\n",i,i,(i+1)%NUMBERS);
printf("*********************************************\n\n");
flag[i]=0;
sem_post(&room);
}
5.运行结果
6.调试记录
(1)将写好的代码进行编译,出现如下错误提示:
1.c:(.text+0x37): undefined reference to `sem_init'
1.c:(.text+0x6a): undefined reference to `sem_init'
1.c:(.text+0x86): undefined reference to `sem_init'
1.c:(.text+0xc8): undefined reference to `pthread_create'
1.c:(.text+0x108): undefined reference to `pthread_join'
/tmp/ccq8XD3O.o: In function `Share':
1.c:(.text+0x13f): undefined reference to `sem_wait'
1.c:(.text+0x160): undefined reference to `sem_wait'
1.c:(.text+0x1b0): undefined reference to `sem_wait'
1.c:(.text+0x1f7): undefined reference to `sem_wait'
1.c:(.text+0x2ad): undefined reference to `sem_post'
1.c:(.text+0x2c0): undefined reference to `sem_post'
1.c:(.text+0x2f5): undefined reference to `sem_post'
1.c:(.text+0x35d): undefined reference to `sem_post'
collect2: ld returned 1 exit status
检查发现,pthread库不是Linux系统默认的库,连接时需要使用库libpthread.a,所以在使用pthread_create创建线程时,在编译中 要加-lpthread参数:
gcc -lpthread -o 1 1.c
(2)重新编译代码,出现如下错误提示:
1.c:9: error: invalid initializer
1.c:10: error: invalid initializer
1.c: In function ‘main’:
1.c:35: warning: incompatible implicit declaration of built-in function ‘exit’
1.c: In function ‘Share’:
1.c:48: error: incompatible types when assigning to type ‘sem_t’ from type ‘int’
1.c:71: error: expected ‘;’ before ‘sem_post’
1.c:76: error: incompatible types when assigning to type ‘sem_t’ from type ‘int’
仔细查看代码,发是对信号灯初始不能在定义的时候直接初始化,改用sem_init()函数对room,mutex 和flag[]进行初始化,去掉exit()函数,找到缺少‘;’的地方,添加‘;’
(3)重新编译、连接、运行程序,出现如下错误提示:
1.c: In function ‘Share’:
1.c:48: error: incompatible types when assigning to type ‘sem_t’ from type ‘int’
1.c:76: error: incompatible types when assigning to type ‘sem_t’ from type ‘int’
查看代码,发现对信号灯flag[]使用出错,将flag[i]=1改为sem_wait(&flag[i]);flag[i]=0改为sem_post(&flag[i])
(4)重新编译、连接、运行程序,没有错误提示,但是结果有误:
philosopher 0 get chopstics 0
I'm philosopher 0 get chopstics 0
程序程出现死锁,无法正常进行,查看代码,发现不应该把flag[]设置为信号
(5)改正后,重新编译、连接,运行程序,得到正确结果
philosopher 0 get chopstics 0
philosopher 1 get chopstics 1
philosopher 2 get chopstics 2
philosopher 3 get chopstics 3
philosopher 3 get chopstics 4
*********************************************
Dining...
philosopher: 3 ,on chairs 3 and eating
philosopher 0 ,on chairs 0 and hungry
philosopher 1 ,on chairs 1 and hungry
philosopher 2 ,on chairs 2 and hungry
philosopher 3 is full and put down chopstics 3 and 4 and left
*********************************************
philosopher 2 get chopstics 3
*********************************************
Dining...
philosopher: 2 ,on chairs 2 and eating
philosopher 0 ,on chairs 0 and hungry
philosopher 1 ,on chairs 1 and hungry
philosopher 4 ,on chairs 4 and hungry
philosopher 4 get chopstics 4
philosopher 2 is full and put down chopstics 2 and 3 and left
*********************************************
philosopher 1 get chopstics 2
*********************************************
Dining...
philosopher: 1 ,on chairs 1 and eating
philosopher 0 ,on chairs 0 and hungry
philosopher 4 ,on chairs 4 and hungry
philosopher 1 is full and put down chopstics 1 and 2 and left
*********************************************
philosopher 0 get chopstics 1
*********************************************
Dining...
philosopher: 0 ,on chairs 0 and eating
philosopher 4 ,on chairs 4 and hungry
philosopher 0 is full and put down chopstics 0 and 1 and left
*********************************************
philosopher 4 get chopstics 0
*********************************************
Dining...
philosopher: 4 ,on chairs 4 and eating
philosopher 4 is full and put down chopstics 4 and 0 and left
7.自我评析与总结
通过本次课程设计,我对哲学家就餐这一操作系统经典问题有了进一步的了解,尤其是在设计进程同步算法方面有了新的认识。通过亲自动手和查询资料,我知道了通过Linux系统的线程机制和信号量控制来实现哲学家就餐问题的并发控制。在这次课程设计中,由于没有掌握好进程同步中的一些关键知识,导致在实际操作中遇到了很多问题,比如说对信号灯初始化,可以用sem_init函数来很好的实现,而不需要在定义的时候就进行初始化。在整个程序设计和完善中,遇到很多问题,有些是由于对知识不了解引起的,有些是由于粗心引起的。此次课程设计使我明白,在程序设计中,我们需要有一个清晰的整体结构,然后针对每个模块逐步实现其功能,在设计中也需要有严谨和认真的态度,才会更好的完成一项任务。
8.参考文献
[1]《操作系统概念》(第七版) ,Abraham Silberschatz等著,高等教育出版社出版
[2]《Linux C 编程实践》,童永清著,人民邮电出版社
[3]《操作系统》(第3版)(中译本),OPERATING SYSTEMS(3RD EDITION),(美)HARVETM.DEITEL;PAUL J.DEITEL;DAVID R.CHOFFNES,清华大学出版社
本科生课程设计成绩评定表
班级: 姓名: 学号:
注:最终成绩以五级分制记。优(90-100分)、良(80-89分)、中(70-79分)、
及格(60-69分)、60分以下为不及格
指导教师签名:
20xx 年 月 日