队列的应用——单服务台排队系统的模拟研究

1、队列的应用：单服务台排队系统的模拟一、三个模拟1.离散事件模拟系统在排队系统中，主要有两类事件：顾客的到达事件和服务完毕后顾客的离去事件，整个系统就是不断有到达事件和离开事件的发生，这些事件并不是连续发生的，因此这样的系统被称为离散事件模拟系统。（1）事件处理过程当生成一个到达事件时，表示有一个新顾客到达。如果服务员没空，就去队列中排队；否则就为这个顾客生成服务所需的时间t，表示服务员开始为它服务，所需的服务时间是t。经过这段时间后会产生一个顾客离开事件，每当一个离开事件发生，就检查有没有顾客在排队，如果有顾客在排队，则让队头顾客离队，为它提供服务，如果没有顾客排队，则服务员可以休息。（2）如

2、何产生顾客到达事件和离开事件在一个排队系统中，顾客的到达时间和为每个顾客服务的时间并不一定是固定的。但从统计上来看是服从一定的概率分布。假设到达的间隔时间和服务时间都满足均匀分布，则可以用随机数产生器产生的随机数。以生成顾客到达事件为例子如顾客到达的间隔时间服从a,b之间的均匀分布，则可以生成一个a,b之间的随机数x，表示前一个顾客到达后，经过了x的时间后又有一个顾客到达。a,b之间的随机数可以按照下面的过程产生：假如系统的随机数生成器生成的随机数是均匀分布在0到RAND_MAX之间，可以把0到RAND_MAX之间的区间等分成b-a+1个，当生成的随机数落在第一个区间，则表示生成的是a，当落在

3、第二个区间，则表示生成的是a+1当落在最后一个区间，则表示生成的是b。这个转换可以用rand()*(b-a+1)/( RAND_MAX+1)+a实现，rand表示系统的随机数生成函数。2.离散的时间驱动模拟在得到了在x秒后有一个事件生成的信息时，并不真正需要让系统等待x秒再处理该事件。在模拟系统中，一般不需要使用真实的精确事件，只要用一个时间单位即可，这个时间单位是嘀嗒tick，可以表示1秒，也可以表示1min1h.沿着时间轴，模拟每一个嘀嗒中发生了什么事件并处理该事件。模拟开始时时钟是0嘀嗒，随后每一步都把时钟加1嘀嗒，并检查这个时间内是否有事件发生，如果有，则处理并生成统计信息。3.离散的

4、事件驱动模拟离散的时间驱动模拟连续地处理每个事件单位，如果在很长一段时间内没有任何事件发生，程序海必须检查每个嘀嗒中是否有事件发生，这很浪费计算机的时间。因此，可以将事件按照发生时间排队，当一个事件处理结束后，直接将时间拨到下一个事件的发生时间，处理下一事件，这就是事件驱动模拟。二、模拟一个单服务台排队系统1.原理模拟银行中只有一个服务台，顾客到达的时间间隔服从arrivalLow, arrivalHigh的均匀分布，服务时间长度服从serviceLow,serviceHigh的均匀分布，一共模拟custNum个顾客，要求统计顾客的平均服务时间。整个模拟由3个步骤组成：首先生成所有的顾客到达事

5、件，按到达时间排成一个队列；其次，服务员一旦有空，就为队头元素服务，在提供服务前先检查该顾客等待了多少时间，记入累计值；最后，在所有顾客服务完以后，返回累计值除以顾客数的结果。2.伪代码totalWaitTime=0;设置顾客开始到达的时间currentTime=0;for(i=0;i当前时间）直接将时钟拨到事件发生的时间； else 收集该顾客的等待时间；生成服务时间；将时钟拨到服务完成的时刻；返回 等待时间/顾客数3.代码分析4-6代码分析 链接队列类的定义template class linkQueue private:struct node/定义一个结点结构体 elemType dat

6、a; /存储数据部分node* next; /存储指向下一个数据的指针部分node(const elemType &x,node*N=NULL) /定义一个node，它包含数据部分和指针部分 data=x;next=N; /给data和next赋值 node():next(NULL) /什么参数都没有，就令为空node()/析构函数，释放空间;node*front,*rear; /结点的队头和队尾public:linkQueue() front=rear=NULL; /空队列，队头和队尾都为空linkQueue();/析构函数，释放空间bool isEmpty() return front=N

7、ULL; /判队列空void enQueue(const elemType &x); /进队 elemType deQueue();/出队elemType getHead() return front-data; /返回队头元素值;4-7代码分析 析构函数的实现template linkQueue :linkQueue()node*tmp; /定义一个跟随指针，确保能够找到头结点while(front!=NULL) /当头结点不为空，进行下列循环tmp=front; /tmp指向头结点front=front-next; /头结点指向下一位delete tmp; /删除tmp所指结点4-8代码分

8、析 链接队列类中enQueue和deQueue运算的实现template void linkQueue :enQueue(const elemType &x) /进队if(rear=NULL) /如果队尾为空front=rear=new node(x); /则队头=队尾=新结点elserear-next=new node(x); /否则队尾的后继指针指向新结点rear=rear-next; /更新队尾，现在队尾为新添加的结点template elemType linkQueue :deQueue()/出队node *tmp=front; /定义一个指针指向队头 elemType value=f

9、ront-data; /队头元素值用value保存front=front-next; /队头往后移一个，队头更新if(front=NULL) rear=NULL;delete tmp; /删除原来的队头return value; /返回原来队头元素值4-10代码分析 模拟类simulator的定义class simulator int arrivalLow; /到达间隔时间下限int arrivalHigh; /到达间隔时间上限int serviceTimeLow; /服务时间下限int serviceTimeHigh; /服务时间上限int customNum; /模拟的顾客数public:

10、simulator();int avgWaitTime() const; /平均等待时间（常数）;4-11代码分析 构造函数的实现simulator:simulator()cout arrivalLow arrivalHigh; /计算机读入输入的参数cout serviceTimeLow serviceTimeHigh; cout customNum;srand(time(NULL); /初始化随机数发生器4-12代码分析 avgWaitTime函数的实现int simulator:avgWaitTime() constint currentTime=0; /当前时间int totalWai

11、tTime=0; /总的等待时间int evenTime; /顾客到达时间，根据到达时间入队linkQueue customerQueue; /定义一个链接队列，存放顾客到达时间，生成到达事件int i;for(i=0;icustomNum;+i) /生成所有的到达事件currentTime+=arrivalLow+(arrivalHigh-arrivalLow+1)* rand()/(RAND_MAX+1);customerQueue.enQueue(currentTime);/循环体的含义是生成所有顾客的到达时间，并按照到达时间的次序存入队列currentTime=0;while(! cu

12、stomerQueue.isEmpty() evenTime=customerQueue.deQueue();/队头元素if(evenTimecurrentTime) totalWaitTime+=currentTime-evenTime;/判断顾客的到达时间和当前时间，如果到达时间比当前时间要小，说明顾客已经等待了一段时间，则统计总的等待时间 else currentTime=evenTime; /如果到达时间不小于当前时间，说明顾客还没到达，还没入队，可以将时钟直接拨到事件发生的时间。 currentTime+=serviceTimeLow+ (serviceTimeHigh-serviceTimeLow+1)*rand()/(RAND_MAX+1); /随机生成服务时间return totalWaitTime/customNum; /返回平均等待时间4-13代码分析 simulator类的使用#include stdafx.h#include simulator.h