排队论算法++含.ppt

《排队论算法++含.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、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):t>0}是一个连续时间的连续随机过程从时间0到t到达路由器的IP包个数{N(t):t

2、>0}是一个连续时间的离散随机过程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)称为该事件的计数过程。计数过程是一种随机过程。事件：数据包到达路由器；顾客到达商店性质：N(0)=0N(t)非负如果s

3、，X2，…是独立同分布的伯努力变量，成功的概率为p。令Sn=X1+X2+…+Xn，即前n次伯努力实验的成功次数，{Sn}是一个计数过程，被称为伯努力过程。Sn的分布是二项分布。5泊松过程一个计数过程{N(t),t≥0}如果满足以下条件，则被称为参数λ的泊松过程独立增量过程（即独立时间段上的事件发生的个数是独立的）平稳过程（在任意一段时间内发生的事件个数的分布是不变的）在一小段时间h内发生一个事件的概率为λh+o(h)。在一小段时间h内发生多于一个事件的概率为o(h)λ被称为泊松过程的速率6定理：{N(t)，t≥0}是一个速率为λ的泊松过程。Y表示一段时间

4、t>0内事件发生的个数，则证明：定义，取h→0代入初始条件，得到7参数为λt的泊松分布对时间t+h时n个事件发生的情况Pn(t+h)，三种情况时间t时已经发生了n个事件，时间t时发生了n-1个事件，[t,t+h)这段时间发生了1个事件时间t时发生了n-k个事件，[t,t+h)这段时间发生了k个事件，k>1取h→0，初始条件，迭代求解得到8定理：{N(t)，t≥0}是一个速率为λ的泊松过程。令0

5、独立同分布的，服从参数为λ的指数分布。证明：对任意n和τ，下面两个事件等价{τn>s}，{N(tn-1+s)-N(tn-1)=0}所以，P[τn>s]=P[N(tn-1+s)-N(tn-1)=0]=P[N(s)=0]=e-λs9指数分布定理：{N(t)，t≥0}是一个计数过程，事件发生间隔记为{τn}。如果{τn}为独立同分布的随机变量，且服从参数λ的指数分布，则N(t)是一个泊松过程。证明：略10总结泊松过程从时间0到时间t发生的事件个数是参数λt的泊松分布事件发生间隔{τn}是指数分布泊松过程1112例某商店，假设顾客按照以下比例单个或者成双到达

6、，f(1)=p，f(2)=1-p。客户到达批次间隔服从以下分布证明时间[0,t)内累计到达的客户数量服从分布如果总共有n个客户，假设其中发生k次成对到达，n-2k次单个到达，分别可以用速率为(1-p)λ和pλ的泊松过程表示。k次成对到达，n-2k次单个到达，k的取值范围从0到1314例给定两个泊松过程，事件发生速率分别为λ1，λ2。从时间t=0开始，问首先观察到第一个过程事件发生的概率。假定过程1的第一个事件发生的时间是t1，过程2的第一个事件发生的时间是t2。t1和t2是参数为λ1和λ2的指数分布15排队问题排队随处可见顾客在超市收银柜台排队飞机在机

7、场排队等待起飞进程在操作系统排队等待调度…排队的原因：由于服务需求大于服务能力规范用语客户（Customer），请求并接受服务者，例如顾客、飞机、进程、等等服务器（Server），提供服务的设施，例如收银员、机场跑道、CPU、等等16排队系统六要素一个排队系统包括六要素客户到达模式服务模式排队规则系统容量服务器数量服务阶段17排队系统六要素客户到达模式耐心客户/非耐心客户：中途离开？客户到达时间间隔可以看作一个随机变量用一个随机过程描述客户到达模式例如：可以用一个泊松过程表示客户到达，到达间隔服从指数分布平稳/非平稳（stationary）到达模式例如：

8、突发大批到达客户服务模式状态无关/状态相关：服务可以“换档”服务时间可以看作一个