排队论算法++(含ppt)

1排队论及其应用Lecture2随机过程&排队论初步中国科学技术大学计算机科学与技术学院田野随机过程随机变量X，分布函数不变如果随机变量的分布函数随时间变化，对时间集合T，得到一组随机变量，称之为随机过程如果时间集合T离散，如T={0,1,2,…}，称为离散时间的随机过程，{Xn:n∈T}如果时间集合T连续，称为连续时间的随机过程，{X(t):t∈T}如果Xn或者X(t)离散/连续，称这个随机过程离散/连续2例：某路由器的IP包t时刻进入缓存等待转发，等待时间{W(t):t0}是一个连续时间的连续随机过程从时间0到t到达路由器的IP包个数{N(t):t0}是一个连续时间的离散随机过程Xn表示一周7天中某一天某计算机启动的进程数，n∈{1,2,3,4,5,6,7}。{Xn}是一个离散时间的离散随机过程。Xn表示一周7天中某一天某计算机的工作时间，n∈{1,2,3,4,5,6,7}。{Xn}是一个离散时间的连续随机变量。3计数过程令N(t)表示在时间段[0,t)内的某种事件发生的次数。N(t)称为该事件的计数过程。计数过程是一种随机过程。事件：数据包到达路由器；顾客到达商店性质：1.N(0)=02.N(t)非负3.如果st，N(s)≤N(t)，N(t)-N(s)是时间[s,t)内发生的事件个数4例，伯努力过程X1，X2，…是独立同分布的伯努力变量，成功的概率为p。令Sn=X1+X2+…+Xn，即前n次伯努力实验的成功次数，{Sn}是一个计数过程，被称为伯努力过程。Sn的分布是二项分布。5[](1)knknnPSkppk泊松过程一个计数过程{N(t),t≥0}如果满足以下条件，则被称为参数λ的泊松过程1.独立增量过程（即独立时间段上的事件发生的个数是独立的）2.平稳过程（在任意一段时间内发生的事件个数的分布是不变的）3.在一小段时间h内发生一个事件的概率为λh+o(h)。4.在一小段时间h内发生多于一个事件的概率为o(h)λ被称为泊松过程的速率60()lim0hohh注意定理：{N(t)，t≥0}是一个速率为λ的泊松过程。Y表示一段时间t0内事件发生的个数，则证明：定义，取h→0代入初始条件，得到7()[],0,1,2,!kttPYkekk()[()]nPtPNtn000()()[()()0]()(1())PthPtPNthNtPthoh0000()()()lim()hPthPtohPthh00()()dPtPtdt0(0)1P0()tPte参数为λt的泊松分布000()()()()PthPtohPthh对时间t+h时n个事件发生的情况Pn(t+h)，三种情况1.时间t时已经发生了n个事件，2.时间t时发生了n-1个事件，[t,t+h)这段时间发生了1个事件3.时间t时发生了n-k个事件，[t,t+h)这段时间发生了k个事件，k1取h→0，初始条件，迭代求解得到81()()(1())()()nnnPthPttohhPtoh10()()()lim()()nnnnhPthPtohPtPthh1()()()nnndPtPtPtdt(0)0nP()()!tnnetPtn定理：{N(t)，t≥0}是一个速率为λ的泊松过程。令0t1t2t3…为事件发生的一系列时间。定义事件发生的间隔τ0=t1-0，τ1=t2-t1，τ2=t3-t2，…，τk=tk+1-tk，…。时间间隔{τi}是独立同分布的，服从参数为λ的指数分布。证明：对任意n和τ，下面两个事件等价{τns}，{N(tn-1+s)-N(tn-1)=0}所以，P[τns]=P[N(tn-1+s)-N(tn-1)=0]=P[N(s)=0]=e-λs9[]1,0snPses指数分布定理：{N(t)，t≥0}是一个计数过程，事件发生间隔记为{τn}。如果{τn}为独立同分布的随机变量，且服从参数λ的指数分布，则N(t)是一个泊松过程。证明：略10总结泊松过程从时间0到时间t发生的事件个数是参数λt的泊松分布事件发生间隔{τn}是指数分布泊松过程1112例某商店，假设顾客按照以下比例单个或者成双到达，f(1)=p，f(2)=1-p。客户到达批次间隔服从以下分布证明时间[0,t)内累计到达的客户数量服从分布如果总共有n个客户，假设其中发生k次成对到达，n-2k次单个到达，分别可以用速率为(1-p)λ和pλ的泊松过程表示。()tate/220(1)()()(2)!!nnkknktnkpptptenkkk次成对到达，n-2k次单个到达，k的取值范围从0到13(1)((1))()!kptkptptek22()()(2)!nkptnkptptenk/2n/22(1)0/220((1))()()!(2)!(1)()(2)!!nknkptptnknnkknktkptptpteeknkpptenkk14例给定两个泊松过程，事件发生速率分别为λ1，λ2。从时间t=0开始，问首先观察到第一个过程事件发生的概率。假定过程1的第一个事件发生的时间是t1，过程2的第一个事件发生的时间是t2。t1和t2是参数为λ1和λ2的指数分布122212220211212[](1)1ttPtteedt15排队问题排队随处可见顾客在超市收银柜台排队飞机在机场排队等待起飞进程在操作系统排队等待调度…排队的原因：由于服务需求大于服务能力规范用语客户（Customer），请求并接受服务者，例如顾客、飞机、进程、等等服务器（Server），提供服务的设施，例如收银员、机场跑道、CPU、等等16排队系统六要素一个排队系统包括六要素客户到达模式服务模式排队规则系统容量服务器数量服务阶段ServerQueueCustomerQueueingsystem17排队系统六要素客户到达模式耐心客户/非耐心客户：中途离开？客户到达时间间隔可以看作一个随机变量用一个随机过程描述客户到达模式例如：可以用一个泊松过程表示客户到达，到达间隔服从指数分布平稳/非平稳（stationary）到达模式例如：突发大批到达客户服务模式状态无关/状态相关：服务可以“换档”服务时间可以看作一个随机变量例如：可以用一个指数分布描述服务时间平稳/非平稳（stationary）服务时间例如：服务器可以学习，提高服务效率1819排队规则FCFS，LCFS，优先级先占优先（Preemptive），非先占优先（Nonpreemptive）系统容量客户不能立即获得服务时选择等待/离开有限/无限个等待位服务器数量单个/多个服务器多服务器多队列，多服务器单队列20Server1QueueCustomerServer2QueueServer1QueueCustomerServer2多服务器多队列多服务器单队列服务阶段完整的服务由多个服务阶段（服务器）组成可能有回路比如：体检，产品生产过程（有回路）2122排队系统命名法则一个排队系统表示为A/B/X/Y/ZA：客户到达模式B：服务模式X：服务器数量Y：等待位数量Z：排队规则23符号取值解释A、BM、D、Ek，Hk，PH，G客户到达间隔/服务时间的概率分布，M表示指数分布（马尔科夫），G表示任意分布，D表示固定值X，Y1,2,…,∞服务器/等待位数量ZFCFS，LCFS，RSS，PR，GD先到先服务，先到后服务，随机，优先级，任意例：M/D/2/∞/FCFS，客户到达符合泊松过程;固定服务时间;2个服务器；无限个等待位；First-come-first-serve通常假定无限个等待位和FCFS，因此常用A/B/X描述一个排队系统比如，M/M/1，M/M/c，…，等等24排队系统常见的性能指标客户等待时间客户在队列中等待的时间(Lq)客户在整个排队系统中消耗的时间(L)=队列等待时间+服务时间客户在排队系统中的累积程度等待队列中的客户数目(Nq)整个排队系统中的客户数目(N)=等待队列客户数目+正在接受服务的客户数目空闲服务器服务器空闲的时间比例系统设计目标：提高服务器利用率，缩短客户等待时间等等，目标往往是相互矛盾的2526G/G/1和G/G/c上的一般性结论单位时间λ个客户到达，一个服务器单位时间能够服务μ个客户，客户到达时间间隔和服务时间任意分布，1个或者c个服务器，无限等待位。G/G/1或者G/G/c。定义ρ1：客户不断累积，越来越多ρ1：排队系统达到平稳态，系统不随时间变化ρ=1：除非客户到达和离开时间固定且匹配，否则无稳态。/c27一些定义N(t)系统在时刻t的规模Nq(t)队列在时刻t的规模Ns(t)时刻t正在接受服务的客户数量pn(t)P[N(t)=n]pn稳态pn(t)，即limt→∞pn(t)L系统平均规模Lq队列平均规模W客户在系统内平均耗时Wq客户在队列中平均耗时0[]()qqnnLENncp0[]nnLENnp[]WET[]qqWET28Little等式(Little’slaw)Little等式（Little’sformula）系统规模=客户达到率×客户在系统中消耗时间“系统”可以是整个排队系统，也可以是一个队列对于队列，这个结果适用于排队模型，与客户到达模式和服务模式无关！LWqqLW单服务器G/G/1排队系统客户在系统时间=排队时间+服务时间正在接受服务的客户数同时，所以服务器繁忙的概率为pb=1-p0=λ/μ291/qWW()(1/)qqLLWW单服务器，稳态下λ/μ不可能大于1。0111(1)1qnnnnnnLLnpnppp30多服务器G/G/c排队系统每台服务器繁忙的概率为pb=λ/cμ共c个服务器，平均λ/μ个客户接受服务，平均每个服务器λ/cμ个客户，或者单位时间中λ/cμ服务器繁忙λ/μ很重要。定义ρ=λ/μ为一个排队系统的提交负载（offeredload）：服务器完成一个客户服务的时间平均到达的客户数量1/qWW()(1/)qqLLWW31G/G/c排队系统总结提交负载Little等式Little等式服务器繁忙概率接受服务的客户数量G/G/1系统为空的概率c/WLqqWL/bpc/r01p例：某快餐店在高峰时每小时到达40位客人，每个客人平均在柜台用5.5分钟点餐。至少需要设置多少个柜台？每小时到达40位客人，假设有c个柜台，则柜台繁忙概率λ/cμ=40/c×(60/5.5)1c40×5.5/60，客人才不至于在柜台累积c至少为432/1bpc33例某公司安排接线员接听顾客电话。由于人手不够，顾客必须等待才能被接听。公司希望顾客平均等待时间为75秒，估计每分钟打进3个客户电话。问需要多少线路用于保持电话等待？λWq=Lq，Lq=3×75/60=3.75，需要4条线路34例考虑一个M/G/1/K排队系统，其阻塞概率为pK=0.1，并且λ=μ=1，L=5。计算λeff，W，Wq，p0和ρeff。0(1)0.9,5/0.95.561/4.56/0.910.1effiKieffqeffeffeffppWL生灭过程（Birth-and-deathprocess）考虑一个群体（比如，海岛上的海鸟群），群体数量取决于两种事件，出生和死亡。当群体个数为n