操作系统课程设计理发师问题的实现
*******************
实践教学
*******************
兰州理工大学
计算机与通信学院
2011年秋季学期
课程设计
题 目:理发师问题的实现 专业班级:计算机科学与技术
姓 名:学 号:
指导教师:成 绩:
摘 要
理发师问题是一个利用信号量进行PV操作的经典问题。设计程序实现此问题,要使得理发师的活动与顾客的活动得到各自真实的模拟。所执行的程序应体现:理发师在没有顾客的时候去睡觉,有顾客则工作;顾客在理发师工作时坐下等待,无座时离开,直至等到理发师自己理发。
关键字:理发师,顾客,PV操作。
目录
摘 要 .............................................................................................................................................. 2
1 设计要求....................................................................................................................................... 4
1.1初始条件 .................................................................................................................... 4
1.2技术要求 .................................................................................................................... 4
2 总体设计思想及开发环境与工具 ............................................................................................... 4
2.1 总体设计思想 ................................................................................................................... 4
2.2 多线程编程原理 ............................................................................................................... 5
2.2.1 创建一个线程 ....................................................................................................... 5
2.2.2 等待一个线程结束 ............................................................................................... 5
2.2.3 信号量 ................................................................................................................... 6
2.3 伪码实现 ........................................................................................................................... 6
2.4 开发环境与工具 ............................................................................................................... 8
3数据结构与模块说明 .................................................................................................................... 8
3.1 数据结构 ........................................................................................................................... 8
3.2函数的调用关系图 ............................................................................................................ 8
3.2.1主函数模块 ............................................................................................................ 8
3.2.2 理发师模块 ........................................................................................................... 9
3.2.3 顾客模块 ............................................................................................................. 10
5运行结果...................................................................................................................................... 10
5.1运行步骤 .......................................................................................................................... 10
5.2测试结果 .......................................................................................................................... 11
5.2.1 编辑,编译和运行的过程图 ............................................................................... 11
5.2.2 错误部分截图 ....................................................................................................... 12
5.2.3 正确运行结果图 ................................................................................................... 12
设计总结......................................................................................................................................... 16
参考文献......................................................................................................................................... 17
致谢 ................................................................................................................................................ 18
附录(源程序代码) ..................................................................................................................... 19
1 设计要求
1.1初始条件
(1)操作系统:Linux
(2)程序设计语言:C语言
(3)设有一个理发师,5把椅子(另外还有一把理发椅),几把椅子可用连续存储单元。
1.2技术要求
(1)为每个理发师/顾客产生一个线程,设计正确的同步算法
(2)每个顾客进入理发室后,即时显示“Entered” 及其线程自定义标识,还同时显示理发室共有几名顾客及其所坐的位置。
(3)至少有10个顾客,每人理发至少3秒钟。
(4)多个顾客须共享操作函数代码。
2 总体设计思想及开发环境与工具
2.1 总体设计思想
题目中要求描述理发师和顾客的行为,因此需要两类线程barber()和customer ()分别描述理发师和顾客的行为。其中,理发师有活动有理发和睡觉两个事件;等待和理发二个事件。店里有固定的椅子数,上面坐着等待的顾客,顾客在到来这个事件时,需判断有没有空闲的椅子,理发师决定要理发或睡觉时,也要判断椅子上有没有顾客。所以,顾客和理发师之间的关系表现为:
(1)理发师和顾客之间同步关系:当理发师睡觉时顾客近来需要唤醒理发师为其理发,当有顾客时理发师为其理发,没有的时候理发师睡觉。
(2)理发师和顾客之间互斥关系:由于每次理发师只能为一个人理发,且可
供等侯的椅子有限只有n把,即理发师和椅子是临界资源,所以顾客之间是互斥的关系。
(3)故引入3个信号量和一个控制变量:
ⅰ控制变量waiting用来记录等候理发的顾客数,初值为0;
ⅱ信号量customers用来记录等候理发的顾客数,并用作阻塞理发师进程,初值为0;
ⅲ信号量barbers用来记录正在等候顾客的理发师数,并用作阻塞顾客进程,初值为1; ⅳ信号量mutex用于互斥,初值为1
2.2 多线程编程原理
此次在Linux下进行多线程编程需要用到pthread_create和pthread_join这两个函数。
2.2.1 创建一个线程
pthread_create用来创建一个线程,原型为:
extern int pthread_create((pthread_t *__thread, __const pthread_attr_t *__attr,void *(*__start_routine) (void *), void *__arg))
第一个参数为指向线程标识符的指针,第二个参数用来设置线程属性,第三个参数是线程运行函数的起始地址,最后一个参数是运行函数的参数。函数thread不需要参数时,最后一个参数设为空指针。第二个参数设为空指针时,将生成默认属性的线程。创建线程成功后,新创建的线程则运行参数三和参数四确定的函数,原来的线程则继续运行下一行代码。
2.2.2 等待一个线程结束
pthread_join用来等待一个线程的结束,函数原型为:
extern int pthread_join __P ((pthread_t __th, void **__thread_return));
第一个参数为被等待的线程标识符,第二个参数为一个用户定义的指针,它
可以用来存
储被等待线程的返回值。这个函数是一个线程阻塞的函数,调用它的函数将一直等待到被
等待的线程结束为止,当函数返回时,被等待线程的资源被收回。
2.2.3 信号量
(1)函数sem_init()用来初始化一个信号量,函数原型为:
extern int sem_init __P ((sem_t *__sem, int __pshared, unsigned int __value));
sem为指向信号量结构的一个指针;pshared不为0时此信号量在进程间共享,否则只能为当前进程的所有线程共享;value给出了信号量的初始值。
(2)函数sem_post( sem_t *sem )用来增加信号量的值。
当有线程阻塞在这个信号量上时,调用这个函数会使其中的一个线程不在阻塞,选择机制同样是由线程的调度策略决定的。
(3)函数sem_wait( sem_t *sem )被用来阻塞当前线程直到信号量sem的值大
于0,解除阻塞后将sem的值减一,表明公共资源经使用后减少。函数sem_trywait ( sem_t *sem )是函数sem_wait()的非阻塞版本,它直接将信号量sem的值减一。
2.3 伪码实现 difine n 5; //为顾客准备的椅子数为5
semaphore mutex=1; //用于互斥
semaphore customers=0;//等候理发的顾客数
semaphore barbers=1;//正在等候顾客的理发师数
int waiting=0; //等候理发的顾客数
//理发师线程
void barber()
{
while(true) //判断有无顾客
{
wait(customers); //若无顾客,理发师睡眠
wait(mutex); //互斥
waiting--; //等候顾客数少一个
signal(mutex); //释放临界资源
signal(barber); //
cut_hair; //
}
}
//顾客线程
void customer()
{
wait(mutex); //
if (waiting
{
waiting++; //
signal(mutex); //
signal(customers); //
wait(barber); //
get_haircut; //
}
else
signal(mutex); //
}
} 理发师去为一个顾客理发 正在理发 互斥 如果有空椅子,则等待 等候顾客数加1 释放临界资源 如果理发师睡觉,唤醒理发师理发师在理发, 顾客等候 顾客坐下等理发师 店里人满了,顾客离开
2.4 开发环境与工具
系统平台:LINUX环境
实现语言:C语言
开发工具:NANO编辑器
3数据结构与模块说明
3.1 数据结构
通过分析课程设计要求,定义以下的数据:
sem_t mutex,customers,barbers; //design three
mutex,customer,barbers
int waiting=0; //the number of waiting customers
int chair[5];
3.2函数的调用关系图
3.2.1主函数模块
主函数流程图如下: semaphores:
3.2.2 理发师模块
理发师模块函数流程图如下:
3.2.3 顾客模块
顾客模块函数流程图如下:
5运行结果
5.1运行步骤
(1) 打开桌面上的putty.exe,输入IP地址192.168.1.254,进入开发环境。创建一个用来写程序的文件,这里用的是nano编辑器来编写c程序。创建SleepingBarber.c的命令为:nano 进入编辑环境,输入代码,结束后按ctrl+x保存为SleepingBarber.c,进入文件的命令为:nano SleepingBarber.c,然后
可以对其进行修改。
(2) 编译源程序,编译命令为:
cc -lpthread -o SleepingBarber SleepingBarber.c
(3) 编译无错误后,运行程序,命令为:
./ SleepingBarber
5.2测试结果
5.2.1 编辑,编译和运行的过程图
\
5.2.2 错误部分截图
5.2.3 正确运行结果图
第一次运行结果如下图:
第二次运行结果如下图:
第三次运行结果如下图;
设计总结
两周的的操作系统课程设计终于完成了,回想这两周的努力,感触良多。拿到题目时我不知从何下手,想想自己对Liunx一无所知,无奈,只好去查阅相关书籍,并在网上查找了相关资料,了解了linux多线程编程的原理,应注意的问题,及一些常用命令
第一周先设计出了该程序的伪代码即其wait、signal操作。然后,根据其要求进行编程,由于使用的是多线程编程,开始进行编译的时候,编译命令输入错误,没有输入-lpthread,程序总是出现错误。同时,创建线程函数时,由于对其格式输入错误导致程序无法运行。例如sb.c,sb1.c等都为本次调试时的程序。
第二周主要是不断的调试并完善程序。程序可以运行,但与要求总有些不符,故不断的进行修改,并对其输出的格式进行完善,使其输出看起来美观一些,容易观察一些。例如s.c,b.c等程序为此次调试结果。
然后是在原有代码的基础上,使程序更完整些。并进行结果的截图,开始设计并编写课程设计说明书。
通过本次编程我熟悉了linux 下的多线程编程和信号量实现wait、signal操作的全过程,对同步和互斥问题也有了更深一步的理解,同时,也使我对linux编程有了更多的了解,在很多方面,它与在windows下编程有着很大的不同,对与多线程来说更方便一些。
设计过程中也遇到不少困难,尤其是对于多线程的实现,结果总是不如想象中完美。比如其顾客编号的输出有时会不按顺序,输入有点乱。另外,有时,输出结束后,程序仍无法结束,必须强制性关闭终端才可以结束程序,这是本程序的一个不足之处。
在本次课程设计中我深深感觉到自己掌握的知识还远远不够,我明白光是知道书本上的知识是远远不够的,一定要把理论知识和实践结合起来。同时,要多多学习linux的操作。
参考文献
1. 汤子瀛,哲凤屏.《计算机操作系统》.西安电子科技大学学出版社.
2. 王清,李光明.《计算机操作系统》.冶金工业出版社.
3.孙钟秀等. 操作系统教程. 高等教育出版社
4.曾明. Linux操作系统应用教程. 陕西科学技术出版社.
5. 张丽芬,刘利雄.《操作系统实验教程》. 清华大学出版社.
6. 孟静, 操作系统教程--原理和实例分析. 高等教育出版社
7. 周长林,计算机操作系统教程. 高等教育出版社
8. 张尧学,计算机操作系统教程,清华大学出版社
9. 任满杰,操作系统原理实用教程,电子工业出版社
致谢
在此次课程设计的过程中,我首先要感谢我的指导老师张永老师,给了我很大的帮助,与此同时感谢宿舍的舍友,对此次课程设计的程序的调试工作给予了大力的帮助。
附录(源程序代码)
#include
#include
#include
#include
#include
#include
#include
#define n 5 //the shop have five chairs
//design three semaphores: mutex,customer,barbers
sem_t mutex,customers,barbers;
int waiting=0; //the number of waiting customers
int chair[5];
void * barber();
void * customer(void *arg);
int main(int argc,char *argv[])
{
//create 10 semaphores and one Barber semaphore
pthread_t Customer_id[10],Barber_id;
int i;
sem_init(&mutex,0,1); //init mutex semaphore to 1 sem_init(&customers,0,0);//init semaphore customers to 0 sem_init(&barbers,0,1);
for(i=0;i
pthread_create(&Barber_id,NULL,(void*)barber,NULL);
for (i=0;i
pthread_create(&Customer_id[i],NULL,(void*)customer,(void*)(i+1)); for (i=0;i
pthread_join(Customer_id[i],NULL);
for(i=0;i
pthread_join(Barber_id,NULL);
return 0;
}
//creat barber pthread
void * barber()
{
int i;
int next;
//wait(customers),if no customers,barber sleeping
sem_wait(&customers);
sem_wait(&mutex); //wait(mutex)
waiting--; //the numer of waiting reduce one
for(i=0;i
{
if (chair[i]!=0)
{
next= chair[i];
chair[i]=0;
break;
}
}
printf(
sleep(3);
sem_post(&mutex);
sem_post(&barbers);
}
//creat customer pthread
void * customer(void *arg)
{
int i;
sem_wait(&mutex); //wait(mutex) if(waiting
if(waiting
{
waiting++; //the numer of waiting plus one
for(i=0;i
{
if (chair[i]==0)
{
chair[i]=(int)arg;
break;
}
}
printf(
printf(
printf(
for(i=0;i
printf(
printf(
sleep(1);
sem_post(&mutex); //signal(mutex)
sem_post(&customers); //signal(customers)
sem_wait(&barbers); //wait(barbers)
}
else
{
printf(
sem_post(&mutex);
}
}