Lecture4-M-G-1-system-and-priority-queue资料

M/G/1系统和优先级队列内容提要M/G/1队列P-K公式有休假期的队列（QueueswithVacations）优先级队列（PriorityQueueing）1.(P-K)公式Poisson到达,到达率λ.单服务器,无穷buffer.服务时间:独立、同分布,任意分布函数,均值1/μ,二阶矩E(X2)存在;独立于到达过程.PASTA定理可用于M/G/1.稳定(stablesystem):ρ=λ/μ1.计算客户在队列中的平均等待时间(Pollaczek-KhinchinFormula).Wi=第i个客户排队等待时间.Ri=第i个客户到达时server的剩余服务时间,如果队列空,则Ri=0.Xi=第i个客户的服务时间.Ni=第i个客户到达时队列内客户数M/G/1队列-符号表示假定客户i在队列内的等待延迟为Wi,当服务为FCFS时,其值为因为服务规则为FCFS,独立于队列内客户的服务时间Xj,所以Ni也与队列内客户的服务时间Xj独立.当服务规则为其他时，P-K公式同样成立Pollaczek-KhinchinFormula(P-K公式)P-K公式（Contd.）但是如果使用大客户(要求的服务时间长)优先的服务规则,则不可以用E(N)乘服务时间的均值加以计算.令i→∞,得其中，R和NQ分别为顾客到达时，所看见的系统上顾客的平均剩余时间和队列中的平均顾客数（PASTA定理）][][][)()|(][)|(][][1ijjjijniiinijjiiNEXREWEXXEnNXEnNPnNXEREWEP-K公式(Contd.)Little’s定理NQ=λW得解之得W=R/(1-ρ)ρ=λ/μ1.确定平均剩余服务时间R:因为稳定系统是遍历的,可以用时间平均代替统计平均.剩余服务时间R(t)的图形如下WRW图中三角形斜边代表的函数为R(t)(server内剩余服务时间).2X1X1X()DtXt()Rt平均剩余服务时间平均剩余服务时间的图形计算在时间区间[0,t]上的平均剩余服务时间为:10()ttRsds假定在时间t,R(t)=0.令D(t)为[0,t]时间内离开的客户数量，并假定R(0)=0（计算结果对于R（0）≠0及R（t）≠0的情况同样成立）.从图形可以看到:()22()101()210111()()22()11()lim()limlim2()DtDttiiiiDttiitttXXDtRsdstttDtXDtRsdsttDt遍历性:长时间平均=稳态平均(以概率1)01[]lim[]lim()tiitERERRsdst2X1X1X()DtXt()Rt平均剩余服务时间(Contd.)平均剩余服务时间(cont.)()21011()lim()limlim2()DttiitttXDtRsdsttDtlim()/tDtt:长时间平均离开率.应该等于长时间平均的到达率.:()limtDtt大数定律:()22211limlim[]()DtniiiitnXXEXDtn平均剩余时间:21[][]2EREXP-K公式:2[][][]12(1)EREXEWP-K公式2[][][]12(1)EREXEW顾客在系统中的平均花费时间21[][][][]2(1)EXETEXEW系统中等待的顾客平均数:22[][][]2(1)EXEQEW系统中的平均顾客数(等待或正在接受服务):22[][][]2(1)EXENET均值E[W],E[T],E[Q],E[N]依赖于服务时间的一阶矩和二阶矩P-K公式例:M/D/1Queue:确定的服务时间1/μ2211[],[]EXEX2222[][][],[]2(1)2(1)2(1)2(1)EXEXEWEQ21[]12(2)[],[][]2(1)2(1)2(1)2(1)EXETENETM/M/1Queue:指数服务时间，均值为1/μ2212[],[]EXEX2222[][][],[]2(1)(1)2(1)(1)EXEXEWEQ21[]11[],[][]2(1)(1)EXETENET例题3.15ARQ(自动请求重传)系统延迟定长包,传输时间为系统时间单位.gobackn策略指:如第i个包传输出错,不直接进行重传，需要等待第i+1,…,i+n-1个包都传输之后，然后返回去重传第i个包。令p=包出错概率;如果一个包传输出错k次,在第k+1次方才成功,则须重传k次,则这个包的有效传输时间是1+kn.令X表示包的有效传输时间.X的概率分布为:P(X=1+kn)=(1-p)pk包到达服从Poisson分布可以用M/G/1系统来分析上述ARQ系统的排队延迟W.根据X的分布函数可算出E(X)和E(X2)pnpppknXkk11)1)(1(02222)1()(121pppnpnpX使用P-K公式，得WXTXXW)1(22详细计算过程见书191－192页.有休假期的队列QueuewithvacationM/G/1withVacation有休假期的排队系统定义以前讲的排队系统都是workconserving系统:只要队列内有等待的客户server就要工作。在有休假期的排队系统中当系统由忙转为闲时server开始一段时间的休假,在休假期内,即使队列内有客户,server也不服务。设server的休假时间为有任意分布的随机变量V,均值为E(V),二阶矩为E(V2)。当休假期满时,如系统内仍无客户,则server继续下一个休假期。假定这些休假期是i.i.d随机变量。有休假期排队系统中的平均剩余服务时间将P-K公式推广到这类系统客户到达时,若server忙,则该客户需要等一段剩余服务时间;若server在休假期中,则该客户要等一段剩余休假期.上述两类时间统称为server剩余时间r(τ),如图所示.有休假期排队系统中的平均剩余服务时间时间平均的server剩余时间为L(t)为t以前完成的休假期数(见书(3.54)式).2)(12)(1211211)(1itLiitMiVtXtdrt需确定:当t→∞时,L(t)/t的极限.L(t)/t为server休假频率(平均单位时间休假次数),设其极限值为ν.Server处于休假状态的时间比例为1-ρ用Little’s定理,有1-ρ=νE(V).ν=(1-ρ)/E(V)有休假期排队系统中的平均剩余服务时间最后得到使用(P-K)公式,得到(见194页(3.55)式):VVXR2)1(222VVXW2)1(222例:时隙M/D/1系统时隙长度=单个包的传输时间=1/μ仅在时隙的开始，进行一个数据包的传输若系统在时隙开始为空,则该时隙为空闲时隙注：从式子可以看出1/2时隙的时间将用于等待一个时隙开始FDM系统假定m个固定包长的Poisson流，到达率分别为λ/m，以FDM方式复用m个子信道。总的到达速率为λ假定花费m时间单位传输一个数据包，所以μ=1/m.总的系统利用率:ρ=λ每个子信道是一个M/D/1系统，顾客在队列中的平均等待时间为W=λE[X2]/(2(1-ρ))时隙FDM假定系统是时隙的，仅在m个时隙开始传输一个数据包这是一个有休假期的M/D/1系统–若无数据包传输，服务器将空闲m个时间单位E[V]=m;E[V2]=m2.WSFDM=WFDM+E[V2]/(2E[V])=WFDM+m/2TDM系统TDM：分成m个时隙，每个时隙传输一个数据包，–一个session必须等待自己对应的时隙进行传输–这种情况与时隙FDM相同，针对每个session的剩余服务/等待时间为TDM与FDM比较WTDM=WFDM+m/2Addingthepackettransmissiontime,TDMcomesoutbestbecausetransmissiontimeis1insteadofmTFDM=[WFDM]+mTSFDM=[WFDM+m/2]+mTTDM=[WFDM+m/2]+1=TFDM-[m/2-1]2.系统内工作量(习题3.30)3.M/G/1忙周期平均长度统一用时间来度量系统内的工作量V(t).在workconserving系统中V(t)不依赖系统服务规则,FCFS,LCFS,抢先或非抢先的优先级服务等.令B1,B2,…为系统忙周期长度，在每个忙周期,过程V(t)重新开始自己,所以B1,B2,…为独立同分布的随机变量.M/G/1忙周期平均长度（cont.）闲周期长度有指数分布,参数,平均长度令B为忙周期的平均长度,而且是不依赖服务规则的不变量.111XBIBI1I11XB4.M/G/1中的不变量(习题3.32)因V(t)不依赖于服务规则,从而时间平均也不依赖服务规则.剩余服务时间r(t)依赖于服务规则（图3.16），但时间平均与服务规则无关,所以,也不依赖于服务规则.ttdVtV0)(1limttdrtR0)(1lim221XRM/G/1中的不变量设Vq(t)=V(t)-R(t)为队列中的工作量,则Vq(t)的时间平均Vq也是不变量,且Vq=V-R如服务规则是不可中断的且与队列内的服务时间独立,则Vq=NQE(X)=ρW,W为客户在队列中平均延迟.=对服务不可中断的系统,W也是独立于服务规则的不变量.M/G/1排队延迟W是不变量在M/G/1FCFS系统中,W=R/(1-ρ),应用不变关系V=R+ρW,有V=R/(1-ρ).V和R是不变量,所以对任何服务规则(抢先或不抢先)的M/G/1系统都有V=R/(1-ρ)应用不变关系V=R+ρW,解出平均队列延迟W=R/(1-ρ).当服务规则和队列内客户的服务时间独立且服务不可中断时,W=R/(1-ρ)也是不依赖服务规则的不变量.5.多客户类M/G/1(习题3.40)设队列的到达流由独立的n类客户的到达流组成,每个到达流为Poisson,第i类客户的到达率为λi,类i客户的服务时间分布为Gi,i＝1，2，…，n，二阶矩为2iX多客户类M/G/1聚集流的到达客户属于类i的概率为λi/λ,服务时间有分布平均服务时间为利用率二阶矩2121iniiXXiiXX1niiX1niiixGxG1)(1)(多客户类M/G/1同样用图形方式（图3.19）可以证明平均剩余服务时间为niinnttRXXdrtR12211021)(1lim多客户类M/G/1的不变关系(习题3.40)当服务不可中断,每类内使用FCFS服务时是不依赖类优先级的守恒量.如果服务对类i优先,从而相应的Wi较小,必然另一类j的队列延迟Wj较大.RVWWXNXNVnnnnQQq11116.M/G/1优先级队列静态(fixed)优先级队列;同一优先级的客户按FCFS服务;不可中断的优先级队列指:对低优先级客户的服务不被高优先级客户的到达而中断,也称之为不可抢先的.否则称为抢先的优先级队列.M/G/1非抢先优先级队列=队列内类k客户的平均数;=类k客户的平均排队时间;=类k客户的利用率;R=平均剩余服务时间;假定按(P-K)公式,类1客户在队列内的等待时间为kQNkWkkk121n1111QNRWniiiXR1221M/G