优先级队列的应用.docx

《优先级队列的应用.docx》由会员分享，可在线阅读，更多相关《优先级队列的应用.docx（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、多服务台排队系统的模拟一、与单服务台排队系统相比在多服务台系统中，先到达的顾客先获得服务，这个规章仍旧存在；但后获得服务的顾客可能先离开，这是由于每个顾客要求的服务时间是不一样的。假如各科i要 求的是一个简单业务，服务台j供应服务；而顾客i+1要求的是一个简洁业务，服务台k供应服 务，那么顾客i+1虽然比顾客i晚到达，却比顾客i先离开。1. 在单服务台系统中，到达次序和离开次序是全都的，所以只需要一个先进先出的队列；在多服务台系统中，离开大事不再与到达大事保持全都，先处理的到达大事对应的离开大事可能 比后处理的到达大事对应的离开大事发生得晚，因此需要一个优先级队列，将大事发生得时间作 为优先级

2、，发生时间早的大事先处理，发生时间晚的大事后处理。二、多服务台排队系统模拟过程.模拟开头时，产生全部的到达大事，存入优先级队列，此时队列只有到达大事。1 .模拟器开头处理大事。首先从队列中取出一个大事，这是第一个顾客的到达大事，依据各科的 服务要求生成对应的服务时间，当前时间+服务时间=这个顾客的离开时间，生成一个这个时候离 开的大事插入队列，这样在队列中就有了两类大事：到达大事和离开大事。2 .这样模拟器从队列中取出的大事也可能是离开大事，这时只要将这个离开大事从队列中删去， 为它服务的服务台就可以为别的顾客服务。综上：（1）产生全部的顾客到达大事，存入大事队列；（2）模拟器从大事队列中取大

3、事，依据不同的大事类型处理大事。若是到达大事，先检查有没有空闲的服务台，假如有，则为此顾客生成服务时间，并产生 一个离开大事，插入大事队列。假如处理到达大事时，没有空闲的服务台，则该顾客进入到等待队列排队。等待队列是一 个一般的先进先出的队列。（3）假如处理的是离开大事，则释放该服务台。假如此时等待队列有人排队，则服务台为他服 务，并统计等待时间，假如等待队列没有人排队则置服务台为空闲。三、伪代码产生CustomNum个顾客的到达大事，按时间的大小存入大事队列;置等待队列为空；置全部柜台为空闲；设置等待时间为0;While（大事队列非空）队头元素出列；设置当前时间为该大事发生的时间；switc

4、h （大事类型）case到达：if （柜台有空）柜台数T；生成所需的服务时间；修改大事类型为“离开”；设置大事发生时间为当前时间+服务时间；重新存入大事队列；else将该大事存入等待队列；case离开：if （等待队列非空）队头元素出队；统计该顾客的等待时间；生成所需的服务时间；修改大事类型为“离开”；设置大事发生时间为当前时间+服务时间；存入大事队列；else空闲柜台+1；计算平均等待时间;返回；四、代码分析代码清单6-9模拟类的定义class simulator以下定义了保存模拟参数的数据成员int noOfServer; /服务台的个数int arrival Low; 到达间隔时间的下界

5、int arrivalHigh; /到达间隔时间的上界int serviceTimeLow; 服务间隔时间的下界int serviceTimeHigh; 服务间隔时间上界int customNum; 模拟的顾客数struct eventT定义了一个私有内嵌类eventT,用于保存一个大事信息，是大事队列和等待队 列中的元素类型，eventT有两个数据成员，time表示大事发生的时间，type表示大事类型 int time; 大事的大小取决于大事发生的时间，发生时间早的大事优先级高，发生时间晚的 大事优先级低int type; 大事类型，0为到达，1为离开bool operator(const

6、eventT &e)constreturn timenoOfServer;cout请输入到达时间间隔的上下界(最小间隔时间最大间隔时间)：；cinarrivalLowarrivalHigh;coutserviceTimeLow serviceTimeHigh;cout请输入模拟的顾客数：;cincustomNum;srand (time (NULL);完成随机数发生器的初始化代码清单6Tl avgWaitTime函数的实现int simulator: :avgWaitTime()依据模拟参数进行模拟，并统计出平均等待时间 int serverBusy=O; 正在工作的服务台数int curre

7、ntTime; 表示现在模拟到了什么时间int totalWaitTime=0; 纪录整个模拟过程中全部顾客的等待时间总和1 inkQueuewaitQueue; 定义了一个类型为 eventT 的链接队列 waitQueue,这个队 列是等待队列，用来保存正在排队的顾客信息priorityQueueeventQueue; 定义了一个类型为 eventT 的优先级队列 eventQueue, 保存的是整个模拟过程中发生的全部大事eventT currentEvent;依据模拟参数中指定的顾客数生成全部顾客的到达大事，并存入大事队列int i;currentEvent. time=0;curre

8、ntEvent. type=0;for (i=0;icustomNum;+i) currentEvent. time+=arrivalLow+ (arrivalHigh-arrivalLow+1) *rand () /(RAND MAX+l); 每 个顾客的到达时间为前一顾客的到达时间加上随机生成的到达时间间隔eventQueue. enQueue(currentEvent);while(!eventQueue. isEmpty()只要队列非空,就要处理大事，直到队列为空currentEvent=eventQueue. deQueue();先从大事队列中取出一个大事current?ime=cu

9、rrentEvent. time; 把模拟时钟直接拨到大事发生的时间switch(currentEvent. type) 然后依据大事发生类型进行不同的处理case 0: 假如是到达大事if(serverBusy! =no0fServer) 首先检查有没有空闲的服务台+serverBusy; 假如有空闲的，则安排服务台currentEvent. time+=serviceTimeLow+(serviceTimeHigh-serviceTimeLow+1)*rand()/ (RAND MAX+l); 离开时间二服 务时间+当前时间currentEvent. type=l; 服务完后，生成一个离开

10、大事eventQueue. enQueue (currentEvent); 入队，大事队列 )else waitQueue. enQueue(currentEvent); 否假如没有空闲的服务台，这位顾客要到 等待队列排队，入队，等待队列break;case 1: 若是离开大事if(!waitQiieue. isEmpty()检查有没有顾客在排队，即等待队列是否为空currentEvent二waitQueue. deQueue();若有顾客在排队，则为等待队列队头的顾客 服务，即让等待队列队头元素出队totalWaitTime+=currentTime-currentEvent. time;

11、把这位顾客的等待时间加入 到总的等待时间，currentTime为当前时间，currentEvent. time为顾客进入到等待队列的时间， 即大事发生的大事currentEvent. time=currentTime+serviceTimeLow+(serviceTimeHigh-serviceTimeLow+1)*rand()/(RAND MAX+l);/currentEvent. time在这指离开时间二当前时间+随机数生成的服务时间currentEvent. type=l; 服务完后，生成一个离开大事eventQueue. enQueue (currentEvent); 入队，大事队列)else-serverBusy; 若没有人排队，则服务台可以休息，所以正在工作的服务台-1 return totalWaitTime/customNum; 计算并返回平均等待时间