操作系统课程设计 理发师问题的实现

《操作系统课程设计 理发师问题的实现》由会员分享，可在线阅读，更多相关《操作系统课程设计 理发师问题的实现（22页珍藏版）》请在装配图网上搜索。

1、#J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J*实践教学#J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J*兰州理工大学计算机与通信学院2011 年秋季学期操作系统 课程设计题 目：理发师问题的实现 专业班级：计算机科学与技术 姓 名：学 号:指导教师：成 绩：摘要理发师问题是一个利用信号量进行PV操作的经典问题。设计程 序实现此问题，要使得理发师的活动与顾客的活动得到各自真实的模 拟。所执行的程

2、序应体现：理发师在没有顾客的时候去睡觉，有顾客 则工作；顾客在理发师工作时坐下等待，无座时离开，直至等到理发 师自己理发。关键字：理发师，顾客，PV操作。目录摘 要 21 设计要求41.1 初始条件41.2 技术要求42 总体设计思想及开发环境与工具42.1 总体设计思想42.2 多线程编程原理52.2.1 创建一个线程52.2.2 等待一个线程结束52.2.3 信号量62.3 伪码实现62.4 开发环境与工具83 数据结构与模块说明83.1 数据结构83.2 函数的调用关系图83.2.1 主函数模块83.2.2 理发师模块93.2.3 顾客模块105 运行结果105.1 运行步骤105.2

3、测试结果 115.2.1 编辑，编译和运行的过程图115.2.2 错误部分截图125.2.3 正确运行结果图12设计总结16参考文献17致谢 18附录（源程序代码）191 设计要求1.1 初始条件(1) 操作系统：Linux( 2 )程序设计语言： C 语言( 3)设有一个理发师， 5 把椅子(另外还有一把理发椅)，几把椅子可用连续 存储单元。1.2 技术要求( 1 )为每个理发师顾客产生一个线程，设计正确的同步算法(2) 每个顾客进入理发室后，即时显示Entered”及其线程自定义标识，还同时显示理发室共有几名顾客及其所坐的位置。(3) 至少有10 个顾客，每人理发至少 3秒钟。( 4)多个

4、顾客须共享操作函数代码。2 总体设计思想及开发环境与工具2.1 总体设计思想题目中要求描述理发师和顾客的行为，因此需要两类线程barber()和customer ()分别描述理发师和顾客的行为。其中，理发师有活动有理发和睡觉两 个事件；等待和理发二个事件。店里有固定的椅子数，上面坐着等待的顾客，顾 客在到来这个事件时，需判断有没有空闲的椅子，理发师决定要理发或睡觉时， 也要判断椅子上有没有顾客。所以，顾客和理发师之间的关系表现为：(1) 理发师和顾客之间同步关系：当理发师睡觉时顾客近来需要唤醒理发师 为其理发，当有顾客时理发师为其理发，没有的时候理发师睡觉。(2) 理发师和顾客之间互斥关系：由

5、于每次理发师只能为一个人理发，且可 供等侯的椅子有限只有 n 把，即理发师和椅子是临界资源，所以顾客之间是互斥 的关系。(3) 故引入 3 个信号量和一个控制变量：i控制变量waiting用来记录等候理发的顾客数，初值为0;ii信号量customers用来记录等候理发的顾客数，并用作阻塞理发师进程，初值为 0；iii信号量barbers用来记录正在等候顾客的理发师数，并用作阻塞顾客进程，初值为1;iv信号量mutex用于互斥，初值为12.2 多线程编程原理此次在Linux下进行多线程编程需要用到pthread_create和pthread_join这两 个函数。2.2.1 创建一个线程pthr

6、ead_create 用来创建一个线程，原型为：extern int pthread_create(pthread_t *_thread, _const pthread_attr_t *_attr,void *(*_start_routine) (void *), void *_arg)第一个参数为指向线程标识符的指针，第二个参数用来设置线程属性，第三 个参数是线程运行函数的起始地址，最后一个参数是运行函数的参数。函数 thread 不需要参数时，最后一个参数设为空指针。第二个参数设为空指针时，将 生成默认属性的线程。创建线程成功后，新创建的线程则运行参数三和参数四确 定的函数，原来的线程则继

7、续运行下一行代码。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 *

8、_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_tr

9、ywait ( sem_t *sem )是函数sem_wait ()的非阻塞版本，它直接 将信号量 sem 的值减一。2.3 伪码实现difine n 5；/为顾客准备的椅子数为5semaphore mut ex=l；/用于互斥semaphore customers=0； /等候理发的顾客数semaphore barbers=1； /正在等候顾客的理发师数int wai ti ng=0；/等候理发的顾客数/理发师线程void barber()/判断有无顾客while(true)wait(customers);wait(mut ex);waiting; signal(m ut ex); sign

10、al(barber); cut_hair;/顾客线程void cus to mer()wait(mut ex);if (waitingn)waiting+;signal(mutex); signal(customers); wait(barber); get_haircut;elsesignal(m ut ex);/若无顾客，理发师睡眠/互斥/等候顾客数少一个/释放临界资源/理发师去为一个顾客理发/正在理发/互斥/如果有空椅子，则等待/等候顾客数加1/释放临界资源/如果理发师睡觉，唤醒理发师/理发师在理发，顾客等候/顾客坐下等理发师/店里人满了，顾客离开2.4 开发环境与工具系统平台：LINU

11、X环境实现语言： C 语言开发工具： NANO 编辑器3数据结构与模块说明3.1 数据结构通过分析课程设计要求，定义以下的数据:semaphores:sem_t mutex,customers,barbers; /design three mutex,customer,barbersint waiting=0; /the number of waiting customersint chair5;3.2 函数的调用关系图3.2.1 主函数模块主函数流程图如下：开始屮创建信号壘初始化信号壘falsetrue创建理发师线程true3. 2.2理发师模块 创建顾客进程亠理发师模块函数流程图如下开始*

12、变壘初始化1waittcustomersJ+Jwaittmutex*-1waiting-*-1sign alfmutexp sign al(muitex)3.2.3 顾客模块顾客模块函数流程图如下：5 运行结果5.1 运行步骤(1) 打开桌面上的 putty.exe ，输入 IP 地址 192.168.1.254 ，进入开发环境。创 建一个用来写程序的文件，这里用的是 nano 编辑器来编写 c 程序。创建SleepingBarber.c的命令为：nano进入编辑环境，输入代码，结束后按ctrl+x 保存为 SleepingBarber.c ，进入文件的命令为： nano SleepingBa

13、rber.c ，然后可以对其进行修改。(2) 编译源程序，编译命令为：cc -lpthread -o SleepingBarber SleepingBarber.c(3) 编译无错误后，运行程序，命令为：./ SleepingBarber5.2 测试结果5.2.1 编辑，编译和运行的过程图5.2.2 错误部分截图5.2.3 正确运行结果图第一次运行结果如下图：口叵I区！Number6curnes _rtherearenochairsthecustomer6isleavingNumb已匸7curci已曰therearenochairsthecustomer7isleavingNumb已匸8cur

14、ci已曰therearenochairsthecustomer8isleavingNumb已匸9curci已曰therearenochairsthecustomer9isleavingNumb已匸10 com已Sr th已匸已 are no chairs the customer 10is丄已aving仝 rj0T0234jsjserver:rjO7O234jsjserver$ cc -lpthread - SleepingBarher 丄已已pingBarb已匸.cr jO7O234 jsjserver. /SleepingBarkier古古古古古古古古古古古古古古击击击击击击击击击击击击击

15、击击击击击击击击击击击击击击击击击击击击击击击击Entered:Number 1 customer conies, and sits at 1 chairThere are 1 customer on the chairThe customers1 location are:1古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古Ent.ereel:Ni.mfcier 2 custutner cninesr and sits at 2 chairThere are 2 c us turner on the c ha i rThe cu5 turn

16、er a 1 lucat ion are : 12 U U U古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古才才才才才才才才才才Enterecl:Ni.mfcier 3 custcurier ccuries_r and sits at 3 chai匸There are 3 custcurier cm the chairThe cu5 turner a 1 lucat ion are : 123 U U吉吉吉吉吉吉吉吉吉吉吉吉吉吉古古古古古古古古古古古古古吉吉吉吉吉吉吉吉吉吉吉吉吉吉吉吉吉吉吉吉吉吉吉吉Enterecl:Ni.mfcier 4 custcuri

17、er ccuries f and sits at 4 chai匸 There are 4 cust.curier cm the chairThe cus匸口niers 1 lucat. ion are : 1234 U古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古Entered:Number 5 customer coniesand sits at 5 chairThere are 5 customer on the chairThe customers 1 locat ion are:12345Th已barb已匸iscuttingTh已

18、barb已匸iscuttingTh已barb已匸iscuttingThebarberiscuttingT 二次运行结果c;下图：!rj070234jsjserver1th customer 1s hair 2th customer 1s hair 3th customer 1s hair 4th customer 1s hair Sth customer 1s hair第三次运行结果如下图；设计总结两周的的操作系统课程设计终于完成了，回想这两周的努力，感触良多。拿 到题目时我不知从何下手，想想自己对 Liunx 一无所知，无奈，只好去查阅相关 书籍，并在网上查找了相关资料，了解了 linux多

19、线程编程的原理，应注意的问 题，及一些常用命令第一周先设计出了该程序的伪代码即其 wait、signal 操作。然后，根据其 要求进行编程，由于使用的是多线程编程，开始进行编译的时候，编译命令输入 错误，没有输入-lpthread,程序总是出现错误。同时，创建线程函数时，由于 对其格式输入错误导致程序无法运行。例如 sb.c， sb1.c 等都为本次调试时的程 序。第二周主要是不断的调试并完善程序。程序可以运行，但与要求总有些不符， 故不断的进行修改，并对其输出的格式进行完善，使其输出看起来美观一些，容 易观察一些。例如s.c, b.c等程序为此次调试结果。然后是在原有代码的基础上，使程序更完

20、整些。并进行结果的截图，开始设计并编写 课程设计说明书。通过本次编程我熟悉了 linux 下的多线程编程和信号量实现 wait、signal 操作的全过程，对同步和互斥问题也有了更深一步的理解，同时，也使我对linux 编程有了更多的了解，在很多方面，它与在 windows 下编程有着很大的不同，对 与多线程来说更方便一些。设计过程中也遇到不少困难，尤其是对于多线程的实现，结果总是不如想象 中完美。比如其顾客编号的输出有时会不按顺序，输入有点乱。另外，有时，输 出结束后，程序仍无法结束，必须强制性关闭终端才可以结束程序，这是本程序 的一个不足之处。在本次课程设计中我深深感觉到自己掌握的知识还远

21、远不够，我明白光是知 道书本上的知识是远远不够的，一定要把理论知识和实践结合起来。同时，要多 多学习 linux 的操作。参考文献1. 汤子瀛，哲凤屏.计算机操作系统.西安电子科技大学学出版社.2. 王清，李光明.计算机操作系统.冶金工业出版社.3. 孙钟秀等.操作系统教程.高等教育出版社4曾明.Linux操作系统应用教程陕西科学技术出版社.5. 张丽芬，刘利雄.操作系统实验教程. 清华大学出版社.6. 孟静，操作系统教程-原理和实例分析.高等教育出版社7. 周长林，计算机操作系统教程.高等教育出版社8. 张尧学，计算机操作系统教程，清华大学出版社9. 任满杰，操作系统原理实用教程，电子工业出

22、版社致谢在此次课程设计的过程中，我首先要感谢我的指导老师张永老师，给了我很 大的帮助，与此同时感谢宿舍的舍友，对此次课程设计的程序的调试工作给予了 大力的帮助。附录（源程序代码）#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

23、customersint chair5;void * barber();void * customer(void *arg);int main(int argc,char *argv)/create 10 semaphores and one Barber semaphore pthread_t Customer_id10,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(&barber

24、s,0,1);for(i=0;i5;i+)pthread_create(&Barber_id,NULL,(void*)barber,NULL);for (i=0;i10;i+)pthread_create(&Customer_idi,NULL,(void*)customer,(void*)(i+1);for (i=0;i10;i+)pthread_join(Customer_idi,NULL);for(i=0;i5;i+)pthread_join(Barber_id,NULL);return 0;/creat barber pthreadvoid * barber()int i;int nex

25、t;/wait(customers),if no customers,barber sleepingsem_wait(&customers);sem_wait(&mutex); /wait(mutex)waiting-;/the numer of waiting reduce onefor(i=0;i5;i+)if (chairi!=0)next= chairi;chairi=0;break;printf(The barber is cutting %dth customers hairn,next);sleep(3);sem_post(&mutex);sem_post(&barbers);/

26、creat customer pthreadvoid * customer(void *arg)int i;sem_wait(&mutex); /wait(mutex) if(waitingn)if(waitingn)waiting+; /the numer of waiting plus onefor(i=0;i5;i+)if (chairi=0)chairi=(int)arg;break;printf(*n);printf(Entered:Number %d customer comes,and sits at %d chair n,(int)arg,(i+1);printf(There

27、are %d customer on the chairn,waiting); printf(The customers location are:);for(i=0;i5;i+)printf(%d ,chairi);printf(n);sleep(1);sem_post(&mutex); /signal(mutex)sem_post(&customers); /signal(customers)sem_wait(&barbers); /wait(barbers)elseprintf(Number %d comes,there are no chairs,the customer %d is leavingn,(int)arg,(int)arg);sem_post(&mutex);