《排队论与计算机系统-网络性能评价》由会员分享，可在线阅读，更多相关《排队论与计算机系统-网络性能评价（89页珍藏版）》请在金锄头文库上搜索。
1、Introduction排队论与计算机系统/网络性能评价,计算机系统性能评价主要目的,1 选择在众多的系统中选择一个最需要的系统（计算机，网络，其他），或在众多的方案中选择一个较好的方案，即在一定的价格范围内选择性能最好的系统（或方案），达到较好的性能 / 价格比。 2 改进对已有系统的性能缺陷进行改进，以便提高其运行效率。 3. 设计对未来设计的系统进行性能预测，在性能成本方面实现最佳设计或配置。,性能参数,1 可靠性或可利用性系统能正常工作的时间，其指标可以是能够持续工作的时间长度，如平均无故障时间, 也可以是在一段时间内, 能正常工作的时间所占的百分比。2 处理能力或效率 l 吞吐率：系
2、统在单位时间内能处理正常作业的个数。 l 响应的时间：系统得到输入到给出输出之间的时间。 l 利用率：在给定的时间区间中，各种部件(包括硬设备和软系统)被使用的时间与整个时间之比。 l 丢失率(或阻塞率)：信息传输(用户呼叫)丢失量与信息传输(用户呼叫)总量之比。,性能评价方法(1),计算机和网络系统性能评价常用的有以下三种方法： 1 测量方法（measurement） l 测量：通过一定的测量设备或一定的测量程序直接从系统测得各项性能指标或与之密切相关的量； l 运算：求出相应的性能指标。优缺点： l 最直接、最基本的方法，其它方法也要依赖于测量的量 l 测量方案和测量手段是测量方法的关键
3、l 比较费时间 l 适用于已经存在并运行的系统,性能评价方法(2),2 仿真（simulation）/模拟(emulation)方法用程序动态地模拟系统及其负载。 l 描述：模拟语言建立系统模型； l 执行：事件或时间驱动系统模型； l 统计分析：性能参数。优缺点 l 详细地刻划系统 l 较精确的性能指标 l 费时、费用较高,性能评价方法(3),3 分析方法(analysis)用数学模型工具的理论与方法描述性能与系统、负载之间的关系。 l (Stochastic Process Algebras)随机过程代数 l (Stochastic Petri Nets)随机Petri网 l (Queue
4、ing Theory)排队论 优缺点 l 模型进行简化和假设 l 刻划系统的详细程度较低 l 与实际性能指标有差距 l 理论基础强、刻划各种因素之间的关系 l 省时、费用也较低本课程的主要内容：排队论及其模型 重点讲述排队模型、排队网络模型及在计算机中的应用 本课程的预修课程为：概率论和随机过程、计算机体系结构,Introduction随机过程&排队论初步,内容提要,两个重要分布：指数分布、Poisson分布 随机过程简介 排队论初步,Exponential Distribution,A continuous R.V. X follows the exponential distributio
5、n with parameter , if its pdf is:= Probability distribution function:Usually used for modeling service time,Exponential Distribution (contd.),Memoryless Property,无后效性 不管多长时间(t)已经过去，逗留时间的概率分布与下一个事件的概率相同 Past history has no influence on the futureProof: Exponential: the only continuous distribution wi
6、th the memoryless property(exp(x+t)=exp(x)exp(t) Example : problem 3.5,指数分布例题-习题3.5,3.5 记性不好的教授在同一时间约了两个学生(应分别约见). 第一个学生准时到达, 第二个学生迟到5分钟. 假定和每个学生谈话的时间为指数分布的随机时间, 均值为30分钟. 试计算整个谈话的平均(expected)时间.,习题3.5 （Contd.）,解: 如果和第一个学生的谈话在5分钟内没结束，剩余的谈话时间仍为均值30分钟的指数分布时间.如果5分钟内谈完了则和他剩余的谈话时间为0.所以和第一个学生剩余谈话时间平均为:PX53
7、0+PX50=PX530.所以和第一个学生谈话的平均时间为:5+PX530=30.38整个谈话的平均(expected)时间为60.38,习题3.6,假设某一银行有4个服务窗口. 某人进到银行时,看到有4个客户在4个窗口接受服务,而且没有其它客户等待.假定每个客户的服务时间都是独立的相同的指数分布(平均1分钟, =1). (1)这个人最后离开银行的概率是多少? (2)这个人平均在银行里停留多长时间?,习题3.6 （Contd.）,(1)这个人最后离开银行的概率是多少?当这4个人中有一个人离开时该人接受服务,这时其它3人的剩余服务时间仍有相同的指数分布.从对称性可知,这4个人中任何一个最后离开的
8、概率都是1/4. (2)这个人平均在银行里停留多长时间?这个人从进入银行到接受服务的时间等于min(X1,X2,X3,X4), X1,X2,X3,X4为正在接受服务的4个客户的剩余服务时间,都是指数分布的随机变量. 随机变量 min(X1,X2,X3,X4)有以下分布:Pmin(X1,X2,X3,X4)x=exp(-4x), 仍为指数分布, 均值=1/(4)=0.25分钟.所以这个人平均在银行停留的时间为1.25分钟. 作业：习题3.6（c）,3.8(a),(Try to prove!),Poisson Distribution,Poisson Distribution (contd.),Su
9、m of Poisson Random Variables,Sum of Poisson Random Variables (cont.),Sampling a Poisson Variable,Sampling a Poisson Variable (contd.),How come?,Poisson Approximation to Binomial,Small Interval Probabilities,内容提要,两个重要分布：指数分布、Poisson分布 随机过程简介 排队论初步,随机过程,随机变量X，分布函数不变 如果随机变量的分布函数随时间变化，对时间集合T，得到一组随机变量，称
10、之为随机过程 如果时间集合T离散，如T=0,1,2,，称为离散时间的随机过程，Xn: nT 如果时间集合T连续，称为连续时间的随机过程，X(t): tT 如果Xn或者X(t)离散/连续，称这个随机过程离散/连续,例： 某路由器的IP包t时刻进入缓存等待转发，等待时间W(t): t0是一个连续时间的连续随机过程 从时间0到t到达路由器的IP包个数N(t): t0是一个连续时间的离散随机过程 Xn表示一周7天中某一天某计算机启动的进程数，n1,2,3,4,5,6,7。Xn是一个离散时间的离散随机过程。 Xn表示一周7天中某一天某计算机的工作时间， n1,2,3,4,5,6,7。Xn是一个离散时间的
11、连续随机变量。,计数过程,令N(t)表示在时间段0, t)内的某种事件发生的次数。N(t)称为该事件的计数过程。计数过程是一种随机过程。 事件：数据包到达路由器；顾客到达商店 性质： N(0)=0 N(t)非负 如果s0内事件发生的个数，则证明：定义 ， 取h0 代入初始条件 ，得到,参数为t的泊松分布,对时间t+h时n个事件发生的情况Pn(t+h)，三种情况 时间t时已经发生了n个事件， 时间t时发生了n-1个事件，t,t+h)这段时间发生了1个事件 时间t 时发生了n-k个事件， t,t+h)这段时间发生了k个事件，k1取h0， 初始条件 ，迭代求解得到,定理： N(t)，t0是一个速率为
12、的泊松过程。令0s，N(tn-1+s)-N(tn-1)=0 所以，Pns=PN(tn-1+s)- N(tn-1)=0=PN(s)=0=e-s,指数分布,定理： N(t)，t0是一个计数过程，事件发生间隔记为n。如果n为独立同分布的随机变量，且服从参数的指数分布，则N(t)是一个泊松过程。 证明：略,Merging & Splitting Poisson Processes,Modeling Arrival Statistics,Poisson process widely used to model packet arrivals in numerous networking problems
13、 Justification: provides a good model for aggregate traffic of a large number of “independent” usersn traffic streams, with independent identically distributed (iid) interarrival times with PDF F(s) not necessarily exponentialArrival rate of each stream /n As n, combined stream can be approximated b
14、y Poisson under mild conditions on F(s) e.g., F(0)=0, F(0)0 Most important reason for Poisson assumption: Analytic tractability of queueing models,总结泊松过程 从时间0到时间t发生的事件个数是参数t的泊松分布 事件发生间隔n是指数分布泊松过程,36,例:某商店，假设顾客按照以下比例单个或者成双到达，f(1)=p，f(2)=1-p。客户到达批次间隔服从以下分布 证明时间0,t)内累计到达的客户数量服从分布如果总共有n个客户，假设其中发生k次成对到达，
15、n-2k次单个到达，分别可以用速率为(1-p)和p的泊松过程表示。,k次成对到达，n-2k次单个到达，k的取值范围从0到,例: 给定两个泊松过程，事件发生速率分别为1，2。从时间t=0开始，问首先观察到第一个过程事件发生的概率。 假定过程1的第一个事件发生的时间是t1，过程2的第一个事件发生的时间是t2。t1和t2是参数为1和2 的指数分布,内容提要,两个重要分布：指数分布、Poisson分布 随机过程简介 排队论初步,排队问题,排队随处可见 顾客在超市收银柜台排队 飞机在机场排队等待起飞 进程在操作系统排队等待调度 排队的原因：由于服务需求大于服务能力 规范用语 客户（Customer），请求并接受服务者，例如顾客、飞机、进程、等等 服务器（Server），提供服务的设施，例如收银员、机场跑道、CPU 、等等,
