操作系统实验报告
实验名称:哲学家就餐问题
院系:电子与信息工程系 班级:通信1004
学号:U201013086 姓名:张建佳
2012-6-20
一.实验目的
1、读懂mfc编写的科学家就餐程序,对C语言加深理解。
2、理解哲学家就餐问题中出现的问题,进而掌握死锁的必要条件。
3、理解源程序中产生和防止的算法,及相关窗口操作。
二.实验原理:
1、问题描述
有五个哲学家围坐在一圆桌旁,桌中央有一盘通心粉,每人面前有一只空盘子,每两人之间放一只筷子。每个哲学家的行为是思考,感到饥饿,然后吃通心粉。为了吃通心粉,每个哲学家必须拿到两只筷子,并且每个人只能直接从自己的左边或右边去取筷子。
2、本程序防止死锁发生采取的措施
仅当一个哲学家左右两边的筷子都可用时,才允许他拿筷子。这样要么一次占有两只筷子(所有线程需要的资源)进行下一步的吃通心粉,然后释放所有的资源;要么不占用资源,这样就不可能产生死锁了。
3、产生死锁的分配方式
当筷子(资源)可用时,先分配左边的筷子,等待一会后再分配右边的筷子,由于这个过程中,左边的筷子一直没有释放,就有可能产生死锁了。
4、程序运行说明
程序运行过程中会弹出一个MessageBox提示操作者操作: 1)第一个对话框用于选择运行模式 a.选择 yes 表示采用的是运行的防止死锁的方式,这样的话整个程序可以一直运行下去,不会产生死锁。 b.选择 no 表示运行产生死锁的方式会弹出第二个对话框。 2)第二个对话框用于选择运行时,线程运行的时间 a. 选择 res 线程时间比较短,很快就可以死锁 b.选择 no 线程时间跟选择 yes 时候的时间差不多,产生死锁的时间稍微长一点。
三.实验过程及分析:
1、伪代码:
(1) 不发生死锁的方式(要么一下占用两支筷子,要么不占用) varmutexleftchopstick,mutexrightchopstick;
beging: resting;
waiting;
p(mutexleftchopstick); //先改变左手筷子信号量
p(mutexrightchopstick); //马上改变右手筷子信号量
GetResource(leftchopstick,rightchopstick);
eating;
v(mutexleftchopstick);
v(mutexrightchopstick);
end
(2) 发生死锁的方式(一旦可以占用筷子,就马上占用)
varmutexleftchopstick,mutexrightchopstick;
beging: resting;
waiting;
p(mutexleftchopstick); //改变左手筷子信号量
GetResource(leftchopstick); //获取左手筷子
p(mutexrightchopstick); //改变右手筷子信号量
GetResource(rightchopstick); //获取右手筷子
eating;
v(mutexleftchopstick);
v(mutexrightchopstick);
end
2、代码分析
(1)不发生死锁的方式:先确定两只筷子均没被占用才获取筷子,这样就打破了死锁的必要条件。
(2)发生死锁的方式:有筷子即占用,看似效率很高,但因为资源有限,且不可抢占,很容易发生死锁。
四.思考题:
其他解决死锁的方案
1. 引入一个餐厅服务生,哲学家必须经过他的允许才能拿起餐叉。因为服务生知道哪只餐叉正在使用,所以他能够作出判断避免死锁。
为了演示这种解法,假设哲学家依次标号为A至E。如果A和C在吃东西,则有四只餐叉在使用中。B坐在A和C之间,所以两只餐叉都无法使用,而D和E之间有一只空余的餐叉。假设这时D想要吃东西。如果他拿起了第五只餐叉,就有可能发生死锁。相反,如果他征求服务生同意,服务生会让他等待。这样,我们就能保证下次当两把餐叉空余出来时,一定有一位哲学家可以成功的得到一对餐叉,从而避免了死锁
2.为资源(这里是餐叉)分配一个偏序或者分级的关系,并约定所有资源都按照这种顺序获取,按相反顺序释放,而且保证不会有两个无关资源同时被同一项工作所需要。在哲学家就餐问题中,资源(餐叉)按照某种规则编号为1至5,每一个工作单元(哲学家)总是先拿起左右两边编号较低的餐叉,再拿编号较高的。用完餐叉后,他总是先放下编号较高的餐叉,再放下编号较低的。在这种情况下,当四位哲学家同时拿起他们手边编号较低的餐叉时,只有编号最高的餐叉留在桌上,从而第五位哲学家就不能使用任何一只餐叉了。而且,只有一位哲学家能使用最高编号的餐叉,所以他能使用两只餐叉用餐。当他吃完后,他会先放下编号最高的餐叉,再放下编号较低的餐叉,从而让另一位哲学家拿起后边的这只开始吃东西。
3.编号可以是任意的。
(1).对每一对竞争一个资源的哲学家,新拿一个餐叉,给编号较低的哲学家。每只餐叉都是“干净的”或者“脏的”。最初,所有的餐叉都是脏的。
(2).当一位哲学家要使用资源(也就是要吃东西)时,他必须从与他竞争的邻居那里得到。对每只他当前没有的餐叉,他都发送一个请求。
(3).当拥有餐叉的哲学家收到请求时,如果餐叉是干净的,那么他继续留着,否则就擦干净并交出餐叉。
(4).当某个哲学家吃东西后,他的餐叉就变脏了。如果另一个哲学家之前请求过其中的餐叉,那他就擦干净并交出餐叉。
这个解法允许很大的并行性,适用于任意大的问题。
五.实验总结:
本次实验是自己第一次阅读MFC程序,自己花了很多时间来阅读程序,争取能将程序完全搞懂。通过这次实验对哲学家就餐这个经典问题有了更深的了解,对老师上课讲的内容也是一次很好的消化,对自己操作系统课程的学习也是很好的推动。
第二篇:操作系统哲学家就餐问题课程设计C语言
武汉理工大学《操作系统》课程设计
题目: 用多线程同步方法解决哲学家就餐问题(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
1
武汉理工大学《操作系统》课程设计
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
线程共享函数伪代码:
2
武汉理工大学《操作系统》课程设计
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);
3
武汉理工大学《操作系统》课程设计
int main()
{
int error; pthread_t threads[NUMBERS]; for(i=0;i<NUMBERS;i++) { } 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 sem_init(&chopstics[i],0,1); *)i);
}
void *Share(int threadid)
{
} if(error) { printf("ERROR: thread create failed!!!"); //exit(-1); } for(i=0;i<NUMBERS;i++) { } pthread_join(threads[i],NULL); int i = threadid; sem_wait(&room); 4
武汉理工大学《操作系统》课程设计
flag[i]=1;
sem_wait(&chopstics[(i+1)%NUMBERS]); printf("philosopher %d get chopstics %d\n",i,(i+1)%NUMBERS); sem_wait(&mutex); printf("\n*********************************************\n"); sem_wait(&chopstics[i]); printf("philosopher %d get chopstics %d\n",i,i); 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)将写好的代码进行编译,出现如下错误提示:
5
武汉理工大学《操作系统》课程设计
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 6
武汉理工大学《操作系统》课程设计
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
7
武汉理工大学《操作系统》课程设计
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
*********************************************
8
武汉理工大学《操作系统》课程设计 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,清华大学出版社
本科生课程设计成绩评定表
班级: 姓名: 学号: 9
武汉理工大学《操作系统》课程设计
分)、
及格(60-69分)、60分以下为不及格
指导教师签名:
200 年 月 日
10