排队系统仿真及应用

文章编号:1005-3751(2002)03-0047-03

排队系统仿真及应用

SimulationandApplicationofQueueModel

朱　军,李晓辉,罗长青(安徽大学电子工程与信息科学院,安徽合肥230039)

ZHUJun,LIXiao2hui,LUOChang2qing(Dept.ofElectr.Eng.&Inf.Sci.,AnhuiUniv.,HefeiAH230039,China)摘　要:根据排队论的单窗口和多窗口排队模型,利用MAT2

LAB语言对模型进行仿真。仿真结果表明,多窗口混合制排

入过程可以是平稳、马氏、齐次的。

队模型优于单窗口模型,适合在现代通信网中加以应用。关键词:排队模型;多窗口;混合制;MATLAB语言

Abstract:Somekindsofqueuemodelarepresentedbasedonthetheoryofqueue.Matlablanguageisusedtosimulatethesequeuemodel.Amongthesemodel,thequeuemodleofmultil2windowsandmixedsystemisbetterthanothers.Wepresentsimulationre2sultstodemonstrateitsapplicationinmoderncommunicationnet2work.

Keywords:queuemodel;multi2windows;mixedsystem;matlab

图1　排队系统组成

●排队规则　　(1)损失制———顾客到达系统时,若系统中所有服务窗均被占用,则到达的顾客随即离去,比如打电话时碰到占线,计算机限定的内存等均为

此种情况;(2)等待制———顾客到达系统时,虽发现服务窗均忙着,但系统设有场地供顾客排队等待之用,于是到达系统的顾客按排队规则进行排队等候服务;(3)混合制———它是损失制与等待制混合组成的排队系统,此系统仅允许有限个顾客排队等候排队。

●服务机构(处理机构)　　(1)系统可以一个窗口或多个窗口为顾客进行服务;(2)各窗口的服务时间可以是确定性或随机型,顾客在系统内逗留的时间均值Ws;顾客排队等候服务的时间均值Wq;服务时间的均值t;显然Ws=Wq+t。

3　单窗口M/M/1损失制模型仿真

M/M/1损失制排队模型是指系统内只设一个服

中图分类号:TP301.63;TP393　　文献标识码:A

1　引　言

排队论(又称随机服务系统)是研究系统由于随机

因素的干扰而出现排队(或拥塞)现象的规律的一门学科,它适用于一切服务系统,包括通信系统、计算机系统等。可以说,凡是出现拥塞现象的系统,都属于随机服务系统。排队论渗透到军事、经济、生产与服务和管理等多种部门。随着电子计算机的不断发展和更新,通信网的建立和完善,信息科学及控制理论的蓬勃发展均涉及到最优设计与最佳服务问题,从而使排队论理论与应用得到发展。本文针对排队系统进行仿真,分析系统的各项性能,并提出改进措施,如增加服务窗、提高服务窗处理速度、加大存储器容量等。仿真采用MATLAB语言实现。

2　排队理论

务窗,仅有一个排队位置而无排队等待位置,顾客到达和窗口服务时间均为负指数分布。且它们的各自参数

为λ和μ的排队系统。如顾客到达时发现服务窗正忙着则离去。其仿真流程如图2所示。其中arrive是到达时刻数组,left是离开时刻数组,free是空闲时间,lost是损失实体,tfree是总共空闲时间,N为仿真系统最多允许到达的实体个数。10个仿真实体中第2、3、5、7、

9实体损失。

4　多服务窗混合制模型M/M/n/m仿真及分析

信息通过网络必须经过三个环节,即信息到达、排

队等候处理(服务)、离去。如图1所示为排队系统的模型。

●输入过程　　(1)顾客相继到达时间间隔可分为确定型和随机型;(2)顾客到达系统的方式可以逐个或成批;(3)顾客到达系统可以是的或相关的,输

收稿日期:2001-08-24

单纯的单服务窗制是不实际的。在不丢失到达实体的同时,又要在经济上合理,这就要对服务窗个数,存储器的容量(最大排队队长)和实体到达流、处理时

© 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.

微　机　发　展　　　　　　　　　　　　　　　　2002年第3期　48　　　　　　　　　　　　　　　　　　　　　

间综合考虑。多服务窗混合制就是一个例子。合理选择服务窗个数后,当实体损失了,就调整最大队列长度,直到实体都得到服务。为了满足电话业务发展的要求,在排队理论的基础上,采用多窗口混合制的排队模型,可以设计全数字、大容量、多功能专用排队机。

图2　单窗口M/M/1损失制仿真流程

设系统有n个服务窗,顾客按泊松流到达系统,

其到达强度为λ;又各窗口工作相互,服务时间均为负指数分布,其强度为μ。系统容量为m,即系统最多可容纳m个顾客(m>n>1)。显然,系统内有m-n个供顾客排队等待的位置。我们采用仿真时钟和未

来事件进行仿真来实现多窗口的摸拟。程序流程图如图3所示。其中ARRIVE是到达时刻数组,INTER2

VAL是到达时间间隔,LEFT是离开时刻数组,FU2TURE是未来事件数组。T为给定仿真时间,超时则

结束仿真。M是规定仿真的实体个数,W是服务窗的个数,可以调节。在图4的仿真结果中,我们设定了三个服务窗,先后到达的实体个数为60,LEFT数组中包含三列离开实体。由仿真结果可以看出,在窗口一接受服务的实体为37个,在窗口二接受服务的实体为

15个,在窗口三接受服务的实体为8个,所有到达的

实体都得到了服务,没有实体损失。

© 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.

(下转46页)

微　机　发　展　　　　　　　　　　　　　　　　2002年第3期　46　　　　　　　　　　　　　　　　　　　　　

　　DII与DSI体系结构如图2。

3.2　客户DII方创建动态请求的基本流程将请求结果[set-result(…)]或异常[set-exception

(…)]送回客户方。

3.4　动态请求的调用方式

●客户方必须通过名字服务器或其他手段获取服务方动态实现例程的对象引用,并将它转换为一个

Object对象。

为了使DII能适应客户的不同要求,对动态请求的激活提供了三种不同的方式:

●同步方式:激活请求后,客户进程被阻塞,直到请求结果的返回。这是客户常用的调用方式。

●延迟同步方式:激活请求后,客户进程继续执行而不被阻塞,在适当时候再取回请求结果。这样,客户可以并发地激活多个请求。通常用于客户需要激活多个的且运行时间长的请求的情况。

●oneway方式:激活请求后,客户进程继续执行而不需要返回结果。而由服务对象处理完请求后的反馈信息通知客户请求的完成。

为此,在Request对象定义了send-oneway()与send-multiple-requests()操作。与invoke()不同,

send-oneway不需要等待操作结束就把控制返回给调

在CORBA的ORB中定义了Object接口,它是所有接口对象的基接口。Object接口主要完成对象引用上的通用操作,如在客户方创建动态请求对象Request的操作就属于这类操作。

●该Object对象创建Request对象,由它来创建对服务方动态实现例程的动态请求过程。

Object对象根据动态请求的操作名,创建一个ORB请求[create-request()];接着向该动态请求添加

操作参数[add-arg()];然后再激活该动态请求[invoke()];得到返回值判定请求结果[return-value()]与异常[exception()]。

3.3　服务DSI方响应动态请求的基本流程

●激活动态实现例程DIR,响应来自客户方的动态请求。

当服务方ORB收到来自客户方的动态请求后,经

POA派发至动态实现例程的派发,并创建ServerRe2quest对象。

用者。客户通过poll-response()与get-response()或

get-next-response()来判断操作的完成及获取操作结果。

参考文献:

[1]　AndreasVogel,BhaskarVasudevan,MairaBenjamin,TedVillalba.

C+

+

●ServerRequest对象解释动态请求。

由ServerRequest对象获取动态请求的操作名[op2

)],解释操作参数[arguments(…)],调用动eration(…

态实现例程[invoke()]。

●动态实现例程实现对特定对象的请求调用。动态实现例程根据动态请求的操作名与操作参数完成对特定对象的请求调用后,由ServerRequest对象

ProgrammingwithCORBA[M].WileyComputerPublishing,

1999.

[2]　[美]OMG.CORBA系统结构、原理与规范[M].北京:电子工业

出版社,2000.

[3]　[美]OMG.CORBA语言映射[M].北京:电子工业出版社,2001.[4]　[美]MichiHenningsteveVinoski.基于C+

[M].北京:清华大学出版社,2000.

+

CORBA高级编程

(上接48页)5　结束语

参考文献:

[1]　程卫国,冯　峰.MATLAB5.3应用指南[M].北京:人民邮电出

本文介绍的排队系统模型,相当于通信网中一个具有存储-转发功能节点上的业务情况。在通信过程中,往往要经过通信路径上的多个存储-转发节点,因此对通信用户间的整个业务来说,构成了多个连接的排队模型。这个由多队列相互连接的一类排队模型,构成排队网。在存储转发的分组交换网中,数据分组为能在某一节点上出站,就必须在欲去的链路上排队,在本文的基础上可以建立起相应的排队网模型,作进一步的仿真研究。

版社,1999.

[2]　李晓辉.多窗口混合制数字排队机的研究与实现[J].仪器仪表

学报,2000,(2):18-20.

[3]　王承恕.通信网基础[M].北京:人民邮电出版社,1999.

[4]　CyrielMinkenberg.ACombinedInput&OutputQueuedPacket2

SwitchedSystemBasedOnPrizmaSwitch2On2A2ChipTechnology[J].CommunicationsmagazineDecember2000,38(12):22-24.

© 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.