计算机系统性能评价2-1 中科院 课件

第2讲第三章排队模型(M/M/1)排队论（queueingtheory），或称随机服务系统理论，作为运筹学研究的一种有力手段，在计算机系统和计算机网络的性能评价中占有相当重要的地位。在现实生活中，为了接受某种服务，排队等待是常见的现象。从排队等待得到抽象的物理模型，进一步建立数学模型的一整套理论就是所谓的排队论。排队论不仅在理论上达到了成熟阶段，而且其应用范围不断增加。概括起来，它已在电话交换网、公路、铁路、航空运输、工程管理、公共服务、货物存储和生产流水线过程等方面得到了广泛的应用。特别地，排队论是计算机通信网络和计算机系统中通信信息量研究的基础理论，信息系统通信问题的定量研究往往要求借助于排对论才能得到解决。典型排队系统模型3.1排队的基本形式3.1.1排队系统的组成和特征1．顾客到达顾客到达的方式通常是一个一个到达的，也可能是成批的。顾客的到达总是有一定规律，即到达过程或到达时间间隔符合一定的分布，称到达分布。顾客的到达或到达时间通常假定为相互独立的且遵从同一分布的随机变量。2．队列排队队列的大小？排队的方式如何？队列容量的大小分为有限和无限两种。对于一个有限大小的队列来说，顾客可能从队列中丢失。有什么样的服务协议就有什么样的与之对应的排队方式。常见的排队方式包括：单队列、并联式多队列、串联式多队列以及杂乱队列等。3.服务员服务主要考虑如下几个方面：（1）服务规律一般服务员对顾客是一个一个进行服务的，且对每一个顾客的服务时间长短不一。将服务时间看作随机变量，那么它们是相互独立的且遵循同一分布。因此描述服务规律时，采用服务时间的概率分布，即服务分布。服务分布同到达分布一样，到底属于哪一种概率分布，要根据具体排队问题进行分析。服务协议和服务员的数量和质量（2）服务协议（a）先来先服务顾客到达的先后次序排队接受服务，用FCFS（first－come－first－served）表示。（b）后来先服务（或称先来后服务）队列是一种堆栈形式。当某一顾客服务结束时，如果在队列中有两个以上等待的顾客，则把最后到达的顾客作为下一个服务的对象。用LCFS（last－come—first－served）表示。（c）随机选择服务在服务时从等待顾客中随意抽取一个进行服务。（d）优先服务和动态优先服务预先规定优先顺序位的类别、且给到达顾客规定优先顺序位作为标记的优先权。通常按FCFS进行服务。优先权分为三类：排队优先权、中断优先权、动态优先权。如计算机中断的优先级。（e）处理器共享（processorsharing，PS）服务员的处理能力被平均分配给队列中的所有顾客，没有排队现象出现，当顾客的数量增加时，只是顾客的服务时间变长。如：网络服务系统。（f）无限服务员（infiniteserver，Is）在这种情况下，队列中的每个顾客接受完全相同的服务，而且就好像它是唯一的一个顾客一样。好像对于每个顾客都可以“克隆”出一个新的服务员，而且克隆的数目可以无限。（3）服务员的数量和质量按服务员数量的多少，服务系统可分为单服务员系统、多服务员系统、无限服务员系统。3.1.2排队系统的到达和服务1到达规律的描述（1）主要描述参数（a）到达时点将某一时刻设为t0，顾客依次到达的时刻用…≤t-1≤t0≤t1≤t2≤…表示，如果在时刻tk到达的顾客为Nk，则到达时点可用{tk、Nk）表示。（b）平均到达间隔一个顾客到达时刻之间的时宽为到达间隔。（c）到达速率单位时间到达顾客的平均数叫到达速率，也称到达密度或输入速率。（2）到达规律顾客的到达规律可以用概率来描述，两个顾客到达的时间间隔是独立的随机变量，服从同一概率分布时。常用的分布规律有：（a）一般到达（b）泊松到达（c）爱尔朗到达（d）等间隔到达2服务规律的描述(1)主要描述参量（a）平均服务时间设服务时间的分布函数为F（t），则服务时间的平均表示为:1/μ=∫tdF(t)其中μ称为平均服务速率。（b）服务速率一般指平均服务速率，用μ来表示。(2)服务规律服务规律通常是就服务时间的分布而言的。服务时间分布典型地有指数分布、爱尔朗数分布、一般分布等。结论：顾客到达规律和服务规律都是通过概率来描述的，所以概率论是排队论的基础。经典排队模型它的格式为：A／B／n／S／Z其中符号的含义如下：A：顾客到达的规律；B：服务时间分布；n：服务员的数目；S：队列容量的大小；Z：服务规程。当队列的大小为无穷大、且服务规程为先来先服务时，经典排队模型可简化为A／B／n不同类型的排队，A、B可用如下约定的字母表示。M：如果用于描述到达，表示泊松到达过程，到达时间间隔符合指数分布；如果用于描述服务，则指具有指数分布的时间。M表示Markov的第一个字母。G：一般分布。表示到达间隔时间或服务时间服从一般分布。G是General的第一个字母。Ek：k-爱尔朗分布。表示到达间隔时间或服务时间服从k-爱尔朗分布。E是Erlang的第一个字母。H：超几何分布。L：H项式分布。Z代表的服务规程典型的有：FCFS：先来先服务；LCFS：后来先服务；RSS：随机选择服务；PR：优先权服务。GD：一般规约服务，即通用规约服务。Ba：集体（批量）服务。练习1要对一个实际系统用排队理论进行分析，首先要确定顾客和服务员，指出下列排队系统中的顾客和服务员：（1）自行车修理店；（2）按客户订单进行加工的加工车间（3）机场起飞的客机（4）十字路口红灯前的车辆从上面分析中，你能得到什么结论？3.2排队分析3.2.1队列的数量关系给出如下输入信息（概率分布）：到达速率（λ）、服务时间（Ts)求出如下输出信息（均值、标准差）：等待顾客的数量（w,σw）、等待时间（Tw，σTw）队列中顾客的数量（q，σq）、排队时间（Tq，σTq）。1。单服务员队列2多服务员队列3基本排队关系在对排队进行分析时，为了便于分析，经常做一些简化假设。对一个排队系统，若满足以下三个条件：（1）排队系统能够进入统计平衡状态；（2）服务员的忙期与闲期交替出现，即系统不是总处于忙的状态；（3）系统中任一顾客不会永远等待，系统也不会永无顾客到达。则下列Little公式成立（排队论中的通用公式）：（1）w=λTw我们知道一个顾客的平均排队等待时间是Tw，且顾客是以平均速率λ到达，所以在时间Tw时间内有λTw个顾客到达，w表示排队等待服务的平均顾客数量，所以有：w=λTw（2）q=λTq系统中的平均顾客数（包括等待的和正在被服务的顾客）等于顾客的平均到达速率乘以一个顾客在系统中花费的平均时间。（3）Tq=Tw+Ts一个顾客在系统中花费的时间，就是它等待服务的时间加上被服务的时间。4队列分析的任务和假设条件队列分析的基本任务是：给出如下输入信息（概率分布）：到达速率（λ）服务时间（Ts)求出如下输出信息（均值、标准差）：等待顾客的数量（w,σw）等待时间（Tw，σTw）队列中顾客的数量（q，σq）排队时间（Tq，σTq）排队论中的假设：在排队分析中，最重要的一个假设是到达速率服从泊松分布，等效的说法是到达间隔时间服从指数分布，这又等价于说到达是随机的并彼此独立。我们几乎一直要作这一假定。没有它，大部分的排队分析是不可能的。在这个假定的条件下，我们会发现仅仅知道到达速率和服务时间的均值和标准差就可以得到许多有用的结果。3.2.2M/M/1排队模型假定顾客到达为泊松流，到达速率为λ，有1个服务员，服务员的服务时间服从指数分布，速率为μ，服务规则为FCFS。则该排队过程为M/M/1模型，表示如下：在计算机系统性能评价中,顾客常表示到达计算机系统的作业任务，服务员代表计算机系统;在通信或网络系统中顾客代表消息，而服务员代表通信信道。M/M/1模型公式推导泊松分布（Poisson）：P{X=k}=λke-λ/k!k=0,1,2,…，μx=σx=λ泊松分布是最重要的离散型概率分布之一，它作为表述随机现象的一种形式，在计算机性能评价中扮演了重要的角色。在实际系统模型中，一般都要假定任务（或顾客）的到来是泊松分布的。实践也证明：这种假设是有效。在排队论中的泊松到达：如果顾客按照速率为λ的泊松过程到达，即在时间T内到达有k个顾客到达的概率为:p=（λT）ke-λT/k!，在时间T内顾客到达的平均顾客数=λT，平均到达速度（顾客数/秒）=λ服从泊松分布过程的到达被认为是随机到达，因为当顾客根据泊松过程到达时，顾客在各个时刻到达的可能性相同并与其它顾客的到达无关。M/M/1模型公式推导指数分布：它是一种连续型的概率分布，它的概率密度：f（x）=λe-λxx≥0它的分布函数：F（x）=1-e-λxx≥0指数分布的一个有用的性质是它的数学期望等于标准差：μx=σx=1/λ定理:设N(t)为时间[0,t]内到达系统的顾客数,则{N(t),t≥0}为参数为λ的泊松过程的充要条件是:相继到达时间间隔服从相互独立的参数为λ的负指数分布.由此定理,可推出泊松分布和指数分布的有如下关系：如果顾客的到达服从参数为λ的泊松分布，则顾客到达的时间间隔Ta服从指数分布，即：P{Tat}=1-e-λt,E[Ta]=1/λ因此，平均到达的时间间隔时到达速率的倒数。M/M/1模型公式推导把排队过程看成生灭过程顾客按参数为λ的泊松分布到达,如果顾客到达系统时服务员正忙,则排队等待服务;服务员为每个顾客服务的速率均为均值为μ的指数分布,如果N（t）表示时刻t系统中的顾客数，则{N（t），t≥0}就构成了一个随机过程。如果用“生”表示顾客的到达，“灭”表示顾客的离去，则对许多排队过程来说，{N（t），t≥0}是一类特殊的随机过程---生灭过程。服务员忙的时间比率：ρ=λ/μ=顾客到达速率/服务速率，也称为通信量强度u，在排队论中，假定ρ1,即：λμ。由生灭过程得到几何分布根据连续生灭过程稳定的条件，要求ρ1，根据连续时间生灭过程的计算公式，可以得到系统在稳定状态下，系统中有k个顾客的概率如下：μk=(1-ρ)ρk,μ0=1-ρM/M/1模型公式推导定理（随机过程中结论）:对于稳定的排队系统(ρ1),系统中有k个顾客的概率服从参数为1-ρ的改进型几何分布:μk=(1-ρ)ρk,μ0=1-ρ问题：在M/M/1中，假定已知λ，μ，输出参数为W,Twq,Tq，如何求解？排队论中通用的Little公式：q=λTq，w=λTwTq=Tw+Tsρ=λTsq=w+ρ提示：求出W,Twq,Tq中的一个，其它用Little公式就可以求出。M/M/1模型公式推导由几何分布可以得到系统中平均顾客数量和等待时间几何分布：P{X=k}=p(1-p)k-1,k=1,2,…几何分布的数学期望为：1/p对系统中有k个顾客的概率服从参数为1-ρ的改进型几何分布:μk=(1-ρ)ρk,μ0=1-ρk≥1令p=1-ρ,计算出系统中顾客数量的均值：E[N]=ρ/(1-ρ)也可以直接根据定义计算出改进型几何分布的均值.令随机变量R代表稳定状态的响应时间，即一个顾客在系统中花费的时间，则Tq=E[R]，根据q=λTq，,由q=E[N]=ρ/(1-ρ)可以得到:Tq=1/μ(1-ρ)M/M/1模型公式推导由系统中顾客平均数量和等待时间得队列中顾客数量w和等待时间Tw令随机变量W代表等待时间，S代表服务时间，则：R=W+SE[R]=E[W]+E[S]=E[W]+1/μ所以顾客的平均等待时间Tw=E[W]=E[R]-1/μ=ρ/μ(1-ρ)即：Tw=ρ/μ(1-ρ)令随机变量L表示队列中正在等待的顾客数量，再根据little公式，W=E[L]=λ*E[W]=λ*ρ/μ(1-ρ)=ρ2/(1-ρ)即：W=ρ2/(1-ρ)M/M/1队列常用公式系统中平均顾客数：q=E[N],顾客在系统中平均等待时间：Tq=1/μ(1-ρ)队列中平均顾客数：W=ρ2/(1-ρ)顾客在队列中平均等待时间：Tw=ρ/μ(1-ρ)在单服务员系统中的lit