操作系统售票员与乘客

操作系统课程设计报告院（系）：专业：计算机科学与技术姓名:班级：＿＿学号:题目：售票员与乘客指导教师:2019年11月20日至12月28日目录一、需求分析 31.1问题概述 31.2理论分析 31.3问题分析 3二、概要设计 42.1售票流程分析 42.2进程分析 52.3信号量机制实现设计 5三、详细设计 63.1设计思路 63.2程序设计核心要点 73.3主要函数分析 73.4具体函数实现分析： 7四、测试分析、测试结果 14五、用户使用说明 165.1运行环境 165.2程序语言 165.2使用说明 16六、总结体会 186.1遇到的问题及解决方法 186.2总结心得 18七、参考资料 19一、需求分析1.1问题概述了解进程同步的概念，理解信号量机制的原理，掌握运用信号量解决进程同步问题的方法，进而学会运用进程的同步和互斥。设计要求：编程序模拟车站售票厅进程同步问题，售票厅任何时刻最多可容纳20名购票者进入，否则需要在外面等待。每个购票者可以看成一个进程。1.2理论分析在多道程序环境下，系统中可能存在许多的进程，在这些进程之间必定存在一些制约关系，这种制约关系表现为以下两种形式：①资源共享关系。进程之间不知道其他进程的存在，而这些进程又处在同一个系统中，对系统资源必须共享使用，而有些资源不允许进程同时访问，例如打印机。系统只能保证进程间互斥地使用这种临界资源，称这种资源共享关系叫做互斥；②相互合作关系。在某些进程间还存在一种相互合作的关系。例如在某个系统中存在两个进程，输入进程A和计算进程B，A负责向B提供数据，当缓冲区空时，B进程因不能获得所需数据而等待。当A把数据送入缓冲区后，并向B发送一个信号将B唤醒，B才能取走数据。同样，当B没有提取数据，也就是说缓冲区满时，进程A也无法向其中投入数据而等待。这就是一种相互合作关系，称之为进程间的同步关系。1.3问题分析在售票大厅买票与卖票的过程其实是有共享缓存去的合作进程而引起的同步，而售票大厅就是这个缓存区，购票者进入售票大厅，由售票者给购票者票后，购票者离开，如图所示。二、概要设计2.1售票流程分析售票厅任何时刻最多可容纳20名购票者进入，当售票大厅超过20人时，系统提示乘客需退出大厅等待；当大厅中人数少于或等于20人时，售票员开始售票，并提示等待的乘客进入大厅；1、乘客购票操作过程：①乘客先在售票厅外等候排队购票;②当提示售票厅内人数不足20人时，则按排队顺序进入售票厅内进行购票动作;③乘客购票完后则离开售票厅内，并提示等待的乘客进入大厅。售票流程如图所示：2.2进程分析由于售票大厅是缓存区，最大容量为20，因此会出现3中情况：①若此时售票厅里人数为零时，则程序会提醒售票大厅为空，售票员的进程阻塞，直到购票者的进程运行完才唤醒该进程；②当进入售票厅内的人数还没有20时，进程将继续执行，则表示售票者的进程和购票者的进程都能执行;③由于程序中的售票厅最大只能容纳20个人，所以，当售票厅内的人数进入将20时，则程序会提醒用户售票大厅的人数已满，请排队等候，购票者进程阻塞，直到售票者的进程运行完才唤醒该进程。由于是多个购票者和多个售票者对应多个缓存区，因此，设置3个信号量：同步信号量empty表示空缓存单元的个数，初值为20；同步信号量full表示满缓冲单元的个数，初值为0；互斥信号量mutex表示互斥使用的整个缓存池，初值为1；售票员-乘客进程PV关系如图：乘客售票员P(empty)P(full)P(mutex)P(mutex)将数据放入有界缓冲区从有界缓冲区中取数据V(mutex)V(mutex)V(full)V(empty)2.3信号量机制实现设计2.2.1功能实现原理定义下列信号量：（1）信号量mutex，初始值为1，用于控制互斥访问售票大厅。（2）信号量full，初始值为0，用于同步控制，full值表示当前售票大厅的人数。（3）信号量empty，初始值为20，用于同步控制，empty表示当前售票大厅还可容下的人数。（4）B=20为可以使用的空缓存区数。（5）in=0，out=0为整型变量，用于控制售票大厅的进入和出去的位置指针。M个售票员和N个乘客共20个单元售票大厅的售票员—乘客问题描述如下：ProcessPassengerDo{ Produceapeople; //乘客 P(empty); //售票大厅的人数为20时，购票者进程阻塞 P(mutex);//控制互斥使用临界资源 B[in]=people;//乘客放入售票大厅 in=（in+1）mod20;//指针推进 people=B[in]; //乘客离开售票大厅 V(mutex);//退出缓存区 V(full);//若售票大厅由空，则乘客进入，并唤醒售票者}while(1)ProcessConductorDo{ P（full）;//售票大厅的人为空时，售票员进程阻塞 P（mutex）;//控制互斥使用临界资源 nextc=B[out]; //将票给乘客 out=(out+1)mod20;//指针推进 V(mutex);//退出临界区 V(empty);//若售票大厅已满，则售票给乘客，并唤醒乘客}while(1);三、详细设计3.1设计思路我们从三个方面依次进行分析：

（1）该问题中包括的进程都有哪些？该问题包括售票员进程和乘客进程这两个。

（2）这些进程都是什么关系，怎么设置信号量，怎么给信号量赋初值？进程之间存在同步和互斥这两种关系。当售票大厅人数为0时，售票员无法售票，只有当乘客进入后，售票员才能开始售票。当售票大厅多于20人时，乘客排队等侯，只有当售票员售票完一个人后，乘客才能继续进入。我们设置两个信号量，full=0（表示满缓冲区的个数），empty=n（表示空缓冲区的个数）。售票员和乘客必须互斥，不允许售票员和乘客在同一个缓冲区，因此设置互斥信号量mutex（当mutex=1时，表示有使用缓冲区临界资源的使用权限；当mutex=0时，表示没有缓冲区临界资源的使用权限）。除此之外，还要设置两个辅助变量。

in表示下一个乘客进入大厅的缓冲区位置；out表示下一个乘客退出大厅的缓冲区位置。（3）用PV原语怎么实现该问题？第一步：确定进程之间的关系。售票厅是各进程共享的公有资源，当售票厅中多于20名购票者时，其他的购票者需要在外面等待，所以进程之间是同步互斥的关系。第二步：确定信号量。只有一个公有资源：售票厅，所以设置一个信号量N，售票厅最多可容纳20个进程，即可用资源实体数为20。3.2程序设计核心要点为了能够动态的建立售票员和乘客的进程，增加了动态链表添加乘客和售票员的进程方法储存，使用单链表头结点进入的存储方式，Buffer中是动态分配（指针）的。缓冲区为售票大厅，缓冲区的设计：（1）缓冲区是一个先进先出队列，写入模块将信息插入队列；读出模块将信息弹出队列。（2）写入模块与读出模块需要进行信息的协调和同步。（3）对于多线程和多进程的写入或读出模块，写入模块间以及读出模块间需要进行临界区处理。3.3主要函数分析1、创建的函数：void*purchaser()；乘客void*seller()；售票员2、系统函数：main()主函数；主函数通过链表指针来实现数据的放入和取出，运行线程池，但线程池的运行时随机的pthread_exit();终止调用它的线程并返回一个指向某个对象的指针。pthread_create(&temp,NULL,purchaser,NULL);第一个参数为指向线程标识符的指针。第二个参数用来设置线程属性。第三个参数是线程运行函数的起始地址。最后一个参数是运行函数的参数。是类Unix操作系统（Unix、Linux、MacOSX等）的创建线程的函数pthread_join(threadPool[i],&result);第一个参数为被连接线程的线程号第二个参数为一个指向被连接线程的返回码的指针的指针3.4具体函数实现分析：1、建立信号量typedefintsemaphore;typedefintitem;itembuffer[N]={0};//缓存区intin=0;//进来缓存区的位置intout=0;//出去的缓存区的位置intnum=0;//此时缓存区的人数intproCount=0;//intpurchaserNum,sellerNum;//售票者的人数，乘客的人数semaphoremutex=1,empty=N,full=0,proCmutex=1;//信号量的定义，empty=空的缓存区数量，full=满的缓存区的数量，proCmutex=1//生产乘客的信号量因为要了解进入售票大厅此时的购票者的号码，所以需要号码牌，并且当前一个号码还没有执行完时，不能发号码牌，这是为了防止因为进程的随机调用，导致号码发到了后面，而中途的号码还没有执行购票操作，就执行后面的号码情况的出现。2、定义链表为了能够动态的建立售票员和乘客的进程，增加了动态链表添加乘客和售票员的进程方法储存，使用单链表头结点进入的存储方式。typedefstructNode{pthread_ttemp;//进程structNode*next;//指针域}Node,*LinkList;//定义链表3、建立乘客进程1、乘客进程产生一个乘客：用一个数纪录乘客的号码：表示这是第几个乘客，产生一个乘客则这个数加一，同时为了不落掉中间乘客，设置一个阻塞，当此乘客进程没有结束时，不能产生一个乘客，因此可以使用循环来表示。判断进程是否结束则用一个信号量标记，当进程结束则为1，进程未结束则为0，初始值设为1。因此当循环结束时需要改变信号量的值，由1变为0。当进程结束时，也改变信号量的值，由1变为0.while(proCmutex<=0);//判断乘客是否产生proCmutex--;//已产生proCount++;//乘客的数量proCmutex++;//乘客已经进入售票大厅完，可再产生一名新的乘客2、乘客的进程P(empty)的实现：随着乘客进入售票大厅后，人数增加，还可容纳的人数减少，则empty--。当empty为空时，进程阻塞，表示不能运行后面的程序。因此可以使用循环来表示这个功能。乘客的进程V(full)的实现：同时释放full的值，则根据乘客进入售票大厅，售票大厅的乘客数增加，所以full++。while(empty<=0){printf("售票大厅已满！请排队等候\n");}//P(empty),判断缓存区是否为满empty--; //空的缓存区减少，乘客进来了缓存区full++; //V(full)，表示满的缓存区增加3、乘客进程P(mutex)的实现：当使用缓存区时，则阻塞，不能运行下面的程序；没有使用缓存区时，则运行。因此使用循环来表示这个功能。设置了mutex信号量，用来标记是否使用缓存区，正在使用缓存区表示为0，没有使用表示为1。当跳出循环时，则表示缓存区没有被占用，因此需要把信号量从没有使用变成正在使用，由1变成0。乘客进程V(mutex)的实现：进程结束时，释放缓存区，信号量由使用缓存区变成没有使用缓存区，由0到1。while(mutex<=0);//P(mutex)，判断缓冲区是否被占用mutex--;//将缓存区的状态变为正在被调用mutex++;//V(mutex)，释放缓冲区4、乘客进程放入有界缓存区的实现：缓存区由数组表示，放入则表示缓存区的某个位置被放入某个数。用in表示放入的位置，乘客号为放入的数。位置会改变，又因为是从数组下标0开始，所以向前推进，同时避免超出缓存区最大值，取余计算。同时，售票大厅的总人数增加一个。if(buffer[in]==0)buffer[in]=proCount;//将进来的乘客序号放入缓冲区in=(in+1)%N;//进来的指针推进一位full++;//满的缓存区增加，乘客进来了缓存区num++;//缓冲区的人数加一printf("第%d乘客已进,此时售票大厅的人数为%d\n",proCount,num);5、乘客进程的代码流程图： 乘客开始判断售票大厅人数是否已满，若为满，则进程阻塞；若没有满，则进程接着判断售票大厅是否被占用，若有，则进程阻塞；若没有，则售票大厅被乘客占用，进程接着表示乘客进行购票，乘客进入售票大厅，通过全局变量num来统计售票大厅的人数，因为进来，所以num++，更改售票大厅人数；4、售票员进程1、线程结束的标志：当乘客全部购票完，且离开售票大厅。所以乘客的进程运行完后结束。而售票者的进程结束是线程结束的标志。乘客全部购票完则表示乘客号码等于输入的乘客数且此时最后一个乘客已经完成购票，全部离开售票大厅则表示售票大厅的人数为0.while(full<=0){printf("售票大厅为空！\n");if(proCount==purchaserNum&&proCmutex==1)//判断售票员进程结束的标志：乘客全部离开售票大厅exit(0);//进程结束}//P(full)，判断缓冲区是否为空2、售票者进程离开有界缓存区的实现：缓存区由数组表示，离开则表示缓存区的某个位置的某个数变为0。用out表示放入的位置，因为要知道离开的乘客，所以先取出乘客号，然后将该位置的值变为0。位置会改变，又因为是从数组下标0开始，所以向前推进，同时避免超出缓存区最大值，取余计算。同时，售票大厅的总人数减少一个。intnextc=buffer[out];//找出离开位置的序号buffer[out]=0;//售票完将离开售票大厅，此时该位置为0out=(out+1)%N;//离开的指针加一if(nextc!=0){num--;//此时售票大厅的人数减一full--;//V(empty)，表示满的缓冲区减少printf("\t\t\t\t第%d乘客已走,此时售票大厅的人数为%d\n",nextc,num);}3、售票员进程的代码流程图：售票者开始判断售票大厅是否为空，若为空，则进程阻塞；若不为空，则进程接着判断售票大厅是否被占用，若有，则进程阻塞；若没有，则售票大厅被售票者占用，进程接着表示对乘客进行售票，乘客离开售票大厅，通过全局变量num来统计售票大厅的人数，因为离开，所以num--，更改售票大厅人数；5、乘客进程与售票员进程之间的关系：售票员的进程P(full)的实现：随着乘客离开售票大厅后，人数减少，售票大厅人数减少，则full--。当full为空时，进程阻塞，表示不能运行后面的程序。因此可以使用循环来表示这个功能。乘客的进程V(empty)的实现：同时释放empty的值，则根据乘客离开售票大厅，售票大厅的乘客数减少，所以empty++。while(full<=0){printf("售票大厅为空！\n");} //P(full)，判断缓冲区是否为空full--; //表示满的缓存区数减少empty++; //V(empty),表示空的缓存区增加6、主函数主函数通过链表指针来实现数据的放入和取出，运行线程池，但线程池的运行时随机的。1、由于是多个购票者进程和多个售票者进程：输入两个人数：购票者人数和售票者人数（表示购票者进程数量，和售票者进程数量）cin>>purchaserNum>>sellerNum；2、建立对用的进程动态放入线程池：pthread_create//类Unix操作系统的创建进程的函数pthread_join//当调用函数时，当前线程会处于阻塞状态，直到被调用的线程结束后，当前线程才会重新开始执行。用于控制线程池的进程并行运行3、把进程动态放入线程池中：用链表表示线程池，建立进程链表，使用尾插入法放入不断往链表中添加进程p->temp=temp;p->next=s->next;s->next=p;//往链中增加新的进程s=s->next;//指向下一个结点4、售票大厅最大的人数已确定，而且我们的结果展示为大厅情况，所以最好使用数组来表示售票大厅，表示有多少个位置，可以根据数组位标确定进入和出去为哪号人,并且初始值设为0表示此位置没有人。itembuffer[N]={0};//缓存区5、主函数实现：当线程池运行时，随机调用存入线程池的进 程，因为当购票者人数没有购票完时，售票者的进 程无法停止，所以当售票大厅为空时，售票者的进 程停止；当购票者全部进来时，购票者进程可 以停止，所以每一个购票者的进程运行完后就停 止，直到所有购票者进入售票大厅，购票者的进 程就全部停止。四、测试分析、测试结果1、当乘客大于20人时，输入售票员与乘客数量(以售票员1名，乘客25名为例):此时，因为乘客的人数为25，所以会出现“售票大厅已满！请排队等候”的字体，而当第25为乘客全部进入后，乘客的进程才会结束。因为售票者的人数为1，而售票者只有当乘客全部购买完票，使售票大厅为空时，售票者的进程才会结束。因此最后显示为“售票大厅为空”。2、当乘客小于售票员的人数时(以乘客10名，售票员15名为例)： 当售票大厅人数为0时，会出现“售票大厅为空！”的字体，当售票者人数大于购票者的人数时，我们在乘客全部走出售票大厅时，线程结束。3、当售票员与乘客人数相等时(以乘客和售票员都为10人时为例)：当售票员与乘客的相等时，我们以购票者全部进入售票大厅，全部出去售票大厅为结束。五、用户使用说明5.1运行环境VS2013及以上版本；Codeblocks5.2程序语言C++5.2使用说明用户操作距离：1、输入。输入项：乘客人数售票者人数如图，以在程序框中输入乘客10名，售票员15名为例(输入项为1015)：2、输出，回车得到输出结果如图。输出项：进入大厅的乘客，大厅中的乘客人数；推出大厅的乘客，此时大厅中的人数；售票大厅的空间使用情况。输入乘客10，售票员15，第1~7名乘客依次进入售票大厅，售票员开始售票，第1~7名乘客购票成功后退出大厅，系统显示此时售票大厅的人数，在大厅外等待的顾客可以进入大厅，第8名乘客进入大厅，第8~10名乘客购票完成退出大厅，系统显示大厅中人数为零，此时大厅中人数为零，运行结束。总结体会6.1遇到的问题及解决方法1、产生的乘客不是一个一个的，比如第一个乘客产生后，然后就跳到第五，六个乘客产生的情况发生。解决方法：增加了一个新的信号量，使乘客产生一个以后，运行完乘客进程后，才能再产生新的乘客，保证乘客一个一个的进入售票大厅。2、因为进程的随机运行，导致售票大厅的总数不对。会有乘客进入后，但是会显示“售票大厅为空”的句子。解决方法：把对售票大厅满的信号量和空的信号量的值的改变放入了mutex的信号量改变的变化中间，保证在该进程还没结束时，其他进程阻塞。当该进程结束后，空和满的信号量一定会发生相应的改变。3、当遇到乘客大于20时且售票员远小于乘客，会发现出现“售票大厅已满”的句子，并且陷入死循环。解决方法：因为建立的进程运行没有停止，当建立的售票员的进程远小于乘客时，且乘客大于20时，容易出现“售票大厅已满”，而较少的运行售票员的乘客，所有容易出现死循环。在售票员和乘客的进程后加了停止该进程的语句，后面会发现当售票员人数大于乘客人数时，会出现“售票大厅为空”，并且陷入死循环；当乘客人数大于售票员人数，会出现“售票大厅已满”，并且陷入死循环。于是又在P(empty)和P(full)语句中加了停止语句。后面发现当乘客人数大于售票者人数时，乘客未全部离开售票大厅就已经结束。当售票者人数大于乘客人数时，乘客未全部进入就停止了运行。最后总结发现线程池的停止乘客需全部进入售票大厅并且离开售票大厅，所有乘客的进程后加了进程结束，售票者的进程在P(full）中加了条件判断，当乘客的离开是乘客的数量，并且此时售票大厅为空时，线程结束。4、为了能够动态的建立售票员和乘客的进程，增加了动态链表添加乘客和售票员的进程方法储存，使用单链表头结点进入的存储方式。5、程序中的while()不符合临界区让权等待