理发师问题课设说明书

1、目录前言 2摘要 3正文 41. 设计思想 42. 算法用到的主要数据结构（采用类 C语言定义）63. 相关的各模块的伪码算法 64. 调试分析 85. 测试结果 9总 结 1.1.参考文献 12致 谢 13附件I部分源程序代码14、八前言在早期的操作系统中一次只允许一个程序。这种执行方式使得程序在执行期 间对系统有完全的控制权，每个程序能访问系统中的所有资源。随着多道批处理 系统和分时系统的出现，程序在系统中的运行不再是独立的，作为资源分配和独 立运行的基本单位是进程，而且操作系统所具有的基本特征也是基于进程而形成 的，故应从进程的观点来研究操作系统。随着操作系统的进一步发展，许多现代 的操

2、作系统为了提高并发力度和降低兵法开销，又引进了线程的概念。由于进程具有动态性和异步性，以及各个进程对资源的共享和为完成一向共 同的任务需要彼此合作等原因，产生了进程间的相互制约关系。如果对进程的活 动不加约束，就会使系统出现混乱，如多个进程的输出结果混在一起，数据处理 的结果不一，系统中某些空闲的资源无法得到利用等问题。为了保证系统中所有 进程都能正常活动，是程序的执行具有可再现性，就必须提供进程同步机制。操作系统中实现进程同步和互斥的机制都称为同步机制，通常采用某个标志 实体来实现同步，如信号量机制，一个控制这些同步机构的程序被称为同步原语。 信号量被作为一种控制进程互斥和同步的物理变量，对

3、信号量的操作，采用了一 对严格设计的程序原语称为 P，V 原语。信号量被定义为整形或记录型变量，当它 的值大于 0 时，表示当前可用资源的数量；当它的值小于 0 时，表示已无可用资 源，其绝对值表示等待使用该资源的进程个数，即在该信号量队列上排队的进程 数即每一个信号量有一个等待队列。理发师问题是一个经典同步问题，本次课设采用信号量机制P，V 原语描述，用 C+ 实现算法。摘要理发师问题是经典进程同步问题，即一个理发店里有间配 n 个椅子的等候室 和一个有理发椅的理发室，如果没有顾客，理发师就去睡觉，如果有顾客来时所 有的椅子上都有人，顾客离去，如果等候室有空闲的椅子，顾客就会坐在其中一 个椅

4、子上，如果理发师在睡觉顾客会摇醒他。本次设计采用信号量机制P、 V 原语来描述问题，并用C+编程实现P、V操作。通过该题的设计过程，可以掌握理发 师问题的原理，软件开发方法并解决实际问题的能力，以及理解进程同步概念学 习如何分配资源。关键字：理发师问题，进程同步，信号量机制正文1. 设计思想1.1 在此问题中可利用三个信号量和一个控制量来协调理发师，理发椅和顾客之 间的活动，即：。(1) , 信号量 customer 用来记录正在等待理发的顾客数，并用作阻塞俩法师进 程，初值为 0；(2) , 信号量 barbers 记录正在等候理发的顾客数， 初值为 0；并用作阻塞顾客进程。(3) , 信号

5、量 waitting 用来记录等候理发的顾客数，初值为 0。(4) , 信号量 mutex 用于互斥初值为 1；1.2 此问题可抽象为 n 个生产者和 1 个消费者问题 , 顾客作为生产者每到来一个 就使计数器 count 加 1，以便让理发师理发 (相当于消费) 至最后一个顾客 (产 品)，并且第一个到来的顾客负责唤醒理发师，而后到来的顾客在有空椅子的 情况下坐下等待，否则离开。在设计过程中用随机函数来产生进入理发店的顾客，定义理发师的理发函 数用来实现理发操作，定义顾客被理发的函数来定义顾客被理发的操作，用顾 客线程实现对顾客行为的控制，用理发师线程实现对理发师行为的控制。定义主函数实现对

6、两个线程的控制和执行操作。1.3 算法流程图2. 算法用到的主要数据结构(采用类 c 语言定义)本程序用到了数据结构中的队列，理发的顾客由随机函数产生，顾客遵从先 到先立法的原则，但队列的长度限制为理发店中椅子的个数，当理发店中没有空 闲的椅子时，到来的顾客主动退出加入队列，理发师对队列中的顾客以先到先服 务的原则理发。while(true)/p(customers),等待顾客/等待互斥量/等待的人数减 1/释放信号量/唤醒顾客进程/v(mutex);/理发/理发完毕的顾客数目加 1:WaitForSingleObject(customers,INFINITE); :WaitForSingle

7、Object(Mutex,INFINITE); waiting-;:ReleaseSemaphore(barbers,1,NULL);:ResumeThread(barbers);:ReleaseMutex(Mutex);cuthair();finish+;3. 相关的各模块的伪码算法(1)定义各种变量：int long waiting(0);等待理发的顾客数intchairs;店中的椅子数intcount(0);顾客的序号intfinish(0);已经理完发的顾客数理发师理发函数 void cuthair( );顾客被理发函数 void gethaircut( ); 随机函数 int ran

8、dom( )产生顾客；(2) 实现进程的互斥及定义信号量来进行线程间的同步伪码：DWORD a;HANDLE Mutex 二：CreateMutex(NULL,FALSE, ”Mutex”);用来实现进程 的互斥HANDLE barbers=: :CreateSemaphore(NULL,1,1 ；'barberS');定义信号量来 进行线程间的同步HANDLE customer=: :CreateSemaphore(; NULL,0,3, ”customers”); 定义 信号量来进行线程间的同步(3) 顾客线程伪码：DWORD WINAPI customer(LPVOID

9、pParm2):WaitForSi ngleObject(Mutex INFINITE);P(mutex )来进行互斥操作count+;/来的是第几个顾客cout«"顾客敲门！第 "<<count<<"个顾客到来"<<endl;if (waiting<chairs)/如果有空椅子if (waiting!=0)cout«"现在有"waiting <<"个人在等待理发"<<endl; elsecout«"无人在等待

10、理发"<<endl;输出有多少人在等待waiting+;cout«"剩余"chairs-waiting+1<<"个座位"<<endl;cout«"有空位，顾客已坐下"<<endl; :ReleaseSemaphore(customers,1,NULL);/V(customer) :ResumeThread(customers);/唤醒理发师进程:ReleaseMutex(Mutex);/释放互斥量， 以便其他线程使用:WaitForSingleObject(

11、barbers,INFINITE); /等待理发gethaircut();/理发并离开elsecoutvv"没有空椅子，第"vvcount<<"个顾客离开理发店"<<endl; /没有椅子， 顾客直接离开:ReleaseMutex(Mutex);return 0;(4) 理发师线程伪码：DWORD WINAPI barber(LPVOID pParm1)while(true)p(customers等 待顾客/等待互斥量:WaitForSingleObject(customers,INFINITE);:WaitForSingleOb

12、ject(Mutex,INFINITE);waiting-;/等待的人数减 1:ReleaseSemaphore(barbers,1,NULL);/释放信号量:ResumeThread(barbers);/唤醒顾客进程:ReleaseMutex(Mutex);/v(mutex);cuthair();/理发finish+;/理发完毕的顾客数目加 1return 0;(5) 主函数实现线程操作：int main(int argc, char* argv)4. 调试分析调试中遇到的问题及对问题的解决方法1) 在运行过程中，头文件出错，头文件#include "stdafx.h"为

13、 MFC文件，此次设计未用 MFC。(2) P、V 的操作要相互对应，P (Mutex)对应 V(Mutex) , P (customer) 对应 V (customer)。5.测试结果.顾客己坐下=iH!“: Documen七呂 and Set七口呂sA<lnii.ni strator'Dbu'ba.严舸 ZSI发己 屠理上客 囂顾门业等理 墜吕在M位 容在人羣 顾正无剩有 进进1发S 顾 个请请第理客 :热顾 业业专怀 在在®人書 正正顾无剩有nahs"1 證 Si. 顾客魏裁囊侏p; C:Documents and Sett ingsAdmini

14、stratorDebugba銖讒；里发完 丄个顾客理发完在营业，请进！茬营业请进I f客敲门！ 引个顾客到来 在為个英在等待理发 g龛1个座位全算顾客己坐下私个顾客理发完毕，离开门业齧tiit仏 mi 在 项E见國5进杞发 弓- S 特 等请请第V- J 1- 业业门 营昔i' 在在客C：c *C : Documents and SettingsAdministratorI>ebugba.没有空椅子，第丘个顾客离开理发店正在营业，请进I正在賣业，请进I顾客敲门I第7个顾客到来 没有車粘子，第?个顾客离开理发店 理发當東r第3个顾客理发完毕，离开正在营业，请进I正在書业，请进！顾客

15、談门|笫8个顾客到来或在看丄个人在等特理发離悻1个座位有空位，顾客己坐下理发结東r第4个顾客理发完毕离开正在营业，请进I正在買业，请曲！顾客議门I第贞驾到来现；在着丄必在等特理发 剩畲丄个座位有空位，顾客己坐下CA *C;Docunient呂 and SettingsAdministratorDebugba顾春戟门I第13个顾客到来 现在議个入在等持理爰 剩船个座位 有空位，顾客已坐下正在营业，请进！ 正在賞业，W!顾容融口第14个顾客到来 没有錨子,第14个顾宮离开理发店 理发结東?孰个顾客理发完毕.离开正在营业，请进!正在買业，tsi顾各敲门！瞬15个顾客到来己君为8个顾客理岌了，是否停止

16、营业? 现在有i个人在等糅理发 剩余个座位有空位，顾客已坐下y理发结衷»第9个顾玄理发完牝离开理发结東* 第仙个顾客理发気毕.离开 理发结東？总结进程的概念是操做系统中最基本，最重要的概念。它是多道程序设计出现以 后，为了刻画系统内部出现的动态情况，描述系统内部各道程序的活动规律而引 进的一个新概念，所有多道程序设计的操作系统都建立在进程的基础上。操作系 统中引进进程的概念，从理论角度讲，是对正在运行的程序活动规律的抽象；从 实际角度讲，则是一种数据结构，目的在于清楚的刻画系统的动态规律，有效管 理计算机系统中程序的运行。在多道程序环境下，同一时刻可能有多个进程在计 算机中运行，所以

17、为了保证所有进程都正常活动就必须提供进程同步机制。理发师问题是重要的进程同步问题，用于解决一个理发师和多个顾客之间的 进程互斥和进程同步问题，理发师和顾客之间要协调工作，在本次课设中采用信 号机制实现问题。通过这次课设，我加深了对操作系统基础知识的理解，尤其是 对进程、线程、进程同步内容的进一步掌握，以及学会了如何合理的分配系统资 源。总的来说，此次课设不但是我巩固了操作系统方面的知识，而且还是我收到 了很多启发，懂得了怎样在今后更好的学习这门课程 .参考文献1. 汤子瀛，哲凤屏 .计算机操作系统 .西安电子科技大学学出版社2. 王清，李光明 .计算机操作系统 .冶金工业出版社 .3. 孙钟秀

18、等 . 操作系统教程 . 高等教育出版社4. 曾明 . Linux 操作系统应用教程 . 陕西科学技术出版社 .5. 张丽芬，刘利雄 .操作系统实验教程 . 清华大学出版社 .6. 孟静， 操作系统教程原理和实例分析 . 高等教育出版社7. 周长林，计算机操作系统教程 . 高等教育出版社8. 张尧学，计算机操作系统教程，清华大学出版社9. 任满杰，操作系统原理实用教程，电子工业出版社致谢这次课设需要各方面的的基础知识，首先感谢王旭阳老师这一学期来不辞辛 劳地给我们教授知识以及对课设的指导，在课设过程中，我不可避免的遇到了很 多问题，这些问题在同学的帮助下才得以解决，在此感谢他们为这次课设提供了

19、 重要的建议附件I部分源程序代码/ babe.cpp : Defines the entry point for the console application.#include "windows.h"#include "iostream.h"#include "math.h"int long waiting(0);/等待理发的顾客人数intchairs;/店中椅子的总数目charopen_door;/开门charclose_door;/关门intcount(0);/顾客的序号intfinish(0);/已经理完发的顾客人数DWORD

20、 a;HANDLE Mutex =:CreateMutex(NULL, FALSE, "Mutex"); / 用来实现进 程的互斥HANDLE barbers =:CreateSemaphore(NULL, 1,1, "barbers"); /定义信号量 来进行线程间的同步HANDLE customers =:CreateSemaphore(NULL,0,3,"customers"); /定义信号量 来进行线程间的同步int random()/定义随机函数来产生顾客，并使两个顾客间的时间少于 15 秒return (rand()*50

21、00)/RAND_MAX;void cuthair()/理发师的理发函数，用时 15 秒 :Sleep (5000);cout<<" 理发结束 !"<<endl;void gethaircut()/ 顾客被理发的函数:Sleep (5001);/顾客被理发的函数，为了和理发师之间有所区别，比理发师理发时间长 1 毫秒coutvv"第"vvfinishvv"个顾客理发完毕，离开"<<endl;DWORD WINAPI customer(LPVOID pParm2)/ 顾客线程:WaitForSi ng

22、leObject(Mutex INFINITE);P(mutex)来进行互斥操作count+;/来的是第几个顾客cout«"顾客敲门！第"<<count<<"个顾客到来"<<endl;if (waiting<chairs)/如果有空椅子if (waiting!=0)cout«"现在有"vvwaiting <<"个人在等待理发"<<endl;elsecout«"无人在等待理发"<<endl;

23、输出有多少人在等待waiting+;cout«"剩余"vvchairs-waiting+1<<"个座位"<<endl;coutvv"有空位，顾客已坐下"<<endl;:ReleaseSemaphore(customers,1,NULL); /V(customer) :ResumeThread(customers);/唤醒理发师进程:ReleaseMutex(Mutex);/释放互斥量， 以便其他线程使用:WaitForSi ngleObject(barbers,INFINITE); 等待理

24、发 gethaircut();/理发并离开elsecoutvv"没有空椅子，第"vvcountvv"个顾客离开理发店"<<endl; 没有椅子,顾客直接离开:ReleaseMutex(Mutex);return 0;DWORD WINAPI barber(LPVOID pParm1)/理发师线程 while(true):WaitForSi ngleObject(customers,INFINITE); /p(customers)等待顾客:WaitForSingleObject(Mutex,INFINITE);/等待互斥量waiting-;/等待的人数减 1:ReleaseSemaphore(barbers,1,NULL);:ResumeThread(barbers);:ReleaseMutex(Mutex);cuthair();finish+;return 0;int main(int argc, char* argv)/实现线程的操作coutvv"输入理发店中的椅子个数:"cin>>chairs;coutvv"店中有"vvchai