排队论及其在现代通信中的应用 16522 电子教案.doc

排队论及其在现代通信中的应用30学时/60学时 电子课件/电子教案作者 盛友招提示：每一章 结束均有小结（见教材）每一章 有练习题（见教材）每一章 均有书面答疑（例题，题解等等）本书附录：有综合练习题的详细题解（见教材），供本书中期或期末复习参考。本电子教案阐述每一章的要点或基本点，目的在于帮助读者把握书中的重要理念、应用实例。在课堂讲授的基础上还需要泛读、精读教材，理解例题或题解，再做一定的练习题。要求多想、多问、多练习，做到基本内容融会贯通，并有“举一反三”的潜力。排队论及其在现代通信中的应用30学时（课内） （电子）教学方案 第1章 绪论4.0学时第2章 增与消过程及其排队模型6.0学时第3章 基本的单一服务装置的排队模型6.0学时第4章 非基本单一服务装置的排队模型 10.0学时第8章 排队网络基础4.0学时第1章 绪论 要点归纳 1、为什么要研究排队论（随机服务系统理论）？2、排队系统的组成及其对组成成分的功用描述？3、用原始数据为依据联系相关系统的数学模型进行分析和计算。4、把概率论与随机过程以及有关数学工具作为研究排队系统的数学手段。随机服务系统理论（或排队论）研究的主要内容。研究各种排队系统的概率规律性；研究对系统的最优化设计或研究现有系统的最优化运营；对排队系统的统计推断，即判断现有系统符合那种模型以便按排队论分析。再谈排队问题的求解要研究它属于哪个模型（其中：可用实测的数据确定顾客到达的间隔时间分布和服务时间的分布）。其它问题在求解相关实际问题时给定。要研究所涉及排队、系统运行的效率、评价服务质量，确定系统参数的最优值，以便判断这个系统的结构是否合理，提出设计改进措施等。为此，用以评估系统运行优劣的基本数量指标，要解决排队问题首先要求出这些数量指标的概率分布，其常见的数量指标列举如下：N在系统中的平均顾客数（也称队长） Nq在系统中排队等待服务的顾客数 Ns在系统中正被服务的顾客数 N=Nq+NsT一个顾客在系统中的停留时间 T=w+x（=等待时间+服务时间）举例说：对于购物、诊病等问题，对于等待时间（w）通常为顾客所关注。对于机器出故障问题，无论是等待修理或正在修理都会导致工厂受到停工的损失，故相应于逗留时间（停工时间）是主要的。忙周期从顾客到达空闲服务机构起到服务机构再次为空闲为止这段时间长度。举例： 表1.2 （给出的原始数据）到达的病人数n出现次数fn010128229316410566以上1共计100表1.3为病人完成手术时间v（小时）出现次数fv0.0-0.2380.2-0.4250.4-0.6170.6-0.890.8-1.061.0-1.251.2以上0共计100（1）计算出每小时病人平均到达率=2.1（人/小时）每次手术平均时间=0.4（小时/人）每小时完成手术人数（平均服务率）（人/小时）（2）取入=2.1，M=2.5（ 泊松到达；负指数服务）（3） 服务机构（手术室）被利用有84%，有16%空闲。（4）可进一步计算出：在病房中病人数（期望值）？5.25（人）排队等待病人数（期望值）？4.41（人）病人在病房中逗留时间（期望值）？2.5（小时）病人排队等待时间（期望值）？2.1（小时）书P. 57（书3.2.5）Kendalls 符号A/B/C/D/M/ZG：一般分布（随机）（General）Hk：k级超指数分布Ek：爱尔兰分布（Erlang）M：马尔可夫特性的负指数分布D：常数分布（Deterministic） A B C K M Z到达过程/服务过程/服务装置数/最大缓冲容量/顾客源/服务规则例：M/M/1/FCFS第2章 要 点对马尔可夫特性（含马尔可夫链、马尔可夫过程）的理解及其在排队论中的应用？对转移概率及其状态转移图的理解及其应用？马尔可夫特性的应用举例？（如无记忆特性与无记忆三角形）C-K方程及其应用证明：负指数分布的无记忆特性以及对于“无记忆三角形”的含义？举例：无后效性（无记忆性）“三角形”。（书P.27 图1.7）四种模型（增消过程）完全随机输入的爱尔兰损失系统M/M/S/S/准随机输入的损失系统（Engset）M（准）/M/S/有限/有限完全随机输入的爱尔兰时延系统M/M/S/准随机输入的时延系统M（准）/M/S/有限MM（准）以上 输入 无限有限顾客源 服务：均为“M”以增-消过程为背景，在书第2章讨论了4种模型（见书P.49-P.73页）从输入过程而言：分为完全随机输入和准随机输入两类从服务过程而言：均假设为负指数服务过程从顾客源而言：分为无限的和有限的顾客源两类构成损失或时延的两种不同的系统完全随机输入的爱尔兰损失系统准随机输入的损失系统（Engset），j=0.1，s-1O，0=sj= （2.3.1） j=j，j=1.2，s （2.3.2） 模型符号：M/M/S/S/Erlangs B公式 见*（2.3.4）（n-j）r，j=0.1，s-10，j=sj= （2.7.1） j=j，j=1.2，s （2.7.2） 模型符号： M（准）/M/S/有限/有限完全随机输入的爱尔兰时延系统准随机输入的时延系统j，j=1.2，ss，j=s+1，s+2，j=，j=0.1， （2.4.1） j= （2.4.2） 模型符号：M/M/S/Erlangs C公式j=（n-j），j=0.1，n （2.8.1）j，j=1.2，ss，j=s+1，s+2，n j= （2.8.2） 模型符号： M（准）/M/S/有限书*（2.2.1）式表示当输入过程为泊松时，到达顾客的分布j（t）与外部观察者分布Pj（t）是相等的。j（t）=Pj（t） t0 j=0，1， *（2.2.1）完全随机输入准随机输入泊松输入无限顾客源j（t）=Pj（t）书 *（2.2.1）式有限顾客源j（n）=Pj（n-1）j=0.1，n-1书 （2.6.8）式第3章 基本的单一服务装置的排队模型M/M/1/是最简单又很有用的排队模型。本章将从简单的模型的生成过程入手。 指数分布与服务装置为1的队列分析解释增消过程最简单的和最有用的到达者模式的模型为完全随机到达者过程，通常涉及泊松到达者过程或简称泊松过程。设有限时间间隔（0，T），并寻找在这个周期内到达顾客数的概率分布。 0 h 2h T=mh把（0，T）间隔时间划分为m个小间隔（见书*（1.4.7）式）泊松（Poisson）分布 （也称纯增过程）3.3 泊松过程 h=T/m； ；代表在（0，T）内顾客的平均到达者速率对于任何小间隔（长度为h）一个顾客到达的概率为h+0（h）；两个或两个以上顾客到达为0（h）故无顾客到达为1-h+0（h）。符号0（h）：0（h）0比h0快；或0比h0快0（h）+0（h）=0（h）；0（h）-0（h）=0（h），etc。在m个小间隔中恰好i个顾客到达的概率可用二项式（binomial）分布来近似：N（T）在周期T内到达者数目的R.V。（随机变量）PN（T）=i=Cimh+0（h）i1-h+0（h）m-i= （证明从略） i.e. PN（T）=i= 为泊松分布泊松分布的数学期望和方差（均为T） （证明从略）泊松分布的PDF（概率分布函数）和pdf（概率密度函数）答案： PDF：1-e-xpdf：e-x5. 指数的到达者之间的间隔时间从泊松分布的PDF与pdf可知：若用泊松分布来描述到达者之间的间隔时间，表明到达间隔时间是指数分布的。泊松过程的特性1. 无记忆（Memory/ess）（或称无后效性）特性 x t ti ti+1 y Rti第i个到达者的（任意选择）时间，在下一个到达者来到之前假设已消逝了y时间单元。要寻找：在所剩下的R时间单元内下一个到达者来到的概率，亦即要计算：PRr/xyR=x-y在下一个到达者来到之前所剩下的时间，按条件概率定义：PXY+r/XY=1-e-r可见R的条件分布与Y无关，并且和到达间隔时间的分布相同。为此，泊松过程是具有无记忆特性的。这样，“在下一个到达者之前计算剩下时间的概率就不必考虑上一个到达者来到的情况”。例如： W X PDF t X 相同 0 t此时 Fx（x）=1-e-x （PDF）证明泊松分布有无记忆特性。在实际的系统中，无记忆特性表明：若程序在两次1/0操作之间的CPU时间具有指数分布，则过去10ms（举例说）以后，剩下的CPU时间仍具有同一指数分布。2. 泊松到达的均匀性在随机服务系统中随机事件的出现或者顾客的到达过程通常是按泊松分布，这个过程有两个明显的特点：（1）在不相重迭的时间区间内，随机事件的出现是独立的，相互无关的。（2）对很小的时间t与（t，t+t）内有一个事件出现的概率与t无关，而与t成正比。 （t，t+t） （t+t，T） t (0,t)0 t t+t T t证明：证明：左侧可写成：泊松过程的叠加与分解（证明从略）第4章 基本的单一服务装置的排队模型（在平衡状态下的增消排队系统）（参看书上谈1.5 统计平衡）4.1 一般平衡解1. 概述马尔可夫过程的功用增消过程是马尔可夫过程的一种特殊形式，在“增”之间的时间间隔和在“消”（当系统为“非空”时）之间的时间间隔各自均为负指数分布的，故从马尔可夫过程可直接获得结论。书（1.4.3）式方程经给出具有稳定“增”与“消”速率的涉及一般增消过程的运动方程。这些方程组的解可得到排队过程的瞬时性以及其它重要的专门状况。本章讨论这些方程的极限形式，或者说讨论增消排队系统的平衡性能。本章讨论涉及对基本的排队系统的分析方法，以利下一步研究较为复杂的排队系统或排队网络（Queueing Networks）2. 一般平衡解 在很远的未来的任意时刻，系统等效处于状态k时（或称系统含有k个成员）的极限概率，若pk存在，pk不再是t的一个函数，在极限情况下，过程不会从一种状态转移到另一种状态。在顾客源内的成员数将随时间而改变，但在极限情况下等于pk。若确认上述方程极限存在，则：在平衡状态下，集中观察Ek状态：Flow rate into Ek=k-1pk-1（t）+k+1pk+1（t） 以及Flow rate out of Ek=（k+k）pk（t） 在平衡状态下，以上与两者必须相等，即平衡差分方程：k-1pk-1+k+1pk+1（t）=（k+k）pk（t） （4.6）在增消过程中已建立了pk（t）专门形式即纯增过程，现在要找出在平衡状态下的一般解；找出经过长时间运行后，求出在系统中具有k个成员的概率Pk。已述 =按照增消过程的状态转移速率图 第k个边界流向守恒：k-1pk-1=kpk第k个边界（图中画线，分开相邻状态，并使跨越可得：用书（1.5.10）式可得出书（2.1.1）式在稳态（或极限）情况下，一般增消过程的解。亦即，只需用未知常数p0就可表达出所有平衡概率pk。对于增消过程的所有Ek状态各态遍历的充分必要条件为： 1 对于大多数排队系统均满足这个条件。4.2 M/M/1/ 经典排队系统的模型（创建）最简单而有价值的系统。1. 用增消系数来描述这个系统k=， k=0，1，2，k=， k=1，2，3，设所有增系数等于常数；设所有消系数等于常数；则平均到达间隔时间； 平均服务时间 ；（极限R.VS .均为指数分布）， M/M/1 状态转移速率图 M/M/1/FCFS无限排队空间无限顾客源泊松到达泊松服务1个服务装置FCFS检查是否满足各态遍历条件：若 /1，的条件满足即可。结论：在M/M/1 排队模型中，各态遍历的充分与必要条件（简言之）为。于是可得： p0=1-/ 利用系数（Utilisatio factor） =/，按稳定条件：01确保p00按 k0 可得：pk=（1-）k， k=0，1，2， 书（1.3.7）式书（1.3.7）式为在系统中发现k个顾客时有关稳态概率的解。重要结果：pk只与与（即）有关。 书P.20、1.64节、几何分布几何分布是唯一的离散无记忆分布。可进一步发现M/M/1排队的重要概率分布都具有无记忆型式的几何分布。4.3 M/M/m/m ：m-Server损失系统1、书P.88、4.1.5节M/M/m/m 见书（4.1.12）式2、 M/M/m/m 状态转移速率图3、书P.35、2.3节 爱尔兰损失系统M/M/S/S/书P.89、（4.1.16）式 爱尔兰B公式而M/M/m 为爱尔兰C公式（P排队） 为爱尔兰时延系统4.4 M/M/1/K书P.87、4.1.3节M/M/1/mP.87，书（4.1.7）式4.5 M/G/1模型（书P.81P.89）见书P.81 M/M/1与M/G/1的对照比较M/M/1M/G/1可为排队状态建立一个简单的平衡方程在排队的时间图上可针对任意更新点可直接导出重要计算公式以马尔可夫链为依据不能只可针对顾客离去时的更新点不能，为此要寻找新的算法以嵌入马尔可夫链为依据4.6 书P.93，4.3具有优先级的队列。书P.93P.96排队论及其在现代通信中的应用60学时（课内）教案提示：其中，1-30学时与30学时电子教案相同（指第1-4章教案部分）自31-60学时的教案另行编写：即第5章 计算机系统的性能分析（7.0学时）第6章 ATM网络的拥塞控制（7.0学时）第7章 ATM交换技术及其性能分析（7.0学时）第8章 排队网络基础（7.0学时） 总复习（答题）（2.0学时）注：关于“30学时电子教案补充讲解”（紧接第4章尾）同样也适用于针对60学时（课内）的教案。为了讲清M/G/1模型的难点（与M/M/1的差异）特别安排30学时电子教案的补充讲解（紧接第4章尾）补充讲解（含集体答疑）内容为：（一）关于嵌入马尔可夫链及其M/G/1排队模型分析 （书P.57、3.3节）基础排队模型M/G/1模型提供“N（t）在t时刻在系统中的顾客数”已足够了。具有离散状态空间Markov过程（状态本身是有限的或可数的）。需要提供两维状态描述，在系统中的顾客数N（t）（仍是可数的）以及XO（t）已花费掉的服务时间（连续的），故从离散状态描述进入连续状态描述，使分析复杂化。pk（t）=pN（t）=kpk（t，xo）dxo=pN（t）=k，xoxo（t）xo+dxoxo（t）对于在t时刻正在接受服务的顾客已完成服务的时间xo（t）。用嵌入马尔可夫链方法的基本思想在于简化状态描述，从两维描述N（t），XO（t）进入一维描述N（t）。M/G/1： 泊松到达 B（x）一般/任意的服务时间分布 平均服务时间 的第k次矩可以证明：pk=rk=dk 对M/G/1rkP在t时刻到达者发现在系统内有k个顾客dkP在t时刻顾客离去后剩余k个顾客书P.34（2.2.1）式当泊松到达过程时：pk=rk（或k=pk）若假设在M/G/1系统内的顾客数N（t）最多只作的变化，故pk=dk这样，对M/G/1：pk=rk=dk可以导出： 顾客离去瞬时的排队长度 服务时间的变异系数 （Coefficient & Variation for Service time）则： 书（3.3.13）式（3.3.13）式为在M/G/1系统中有关顾客的平均数的一个较为著名的公式（P-K）平均值公式。在P-K平均值公式中，只与与有关； （线性增加）按照M/G/1 ：pk = rk= dk (nk) (pk)故表达式也表示在顾客到达瞬时在该系统内顾客的平均数。曾用符号：表示在该系统中平均顾客数 在队列（不计正在服务的顾客数）内的平均顾客数。寻找与的关系可求出：=-*其中，可导出M/G/1 ： 又，指数分布的方差为= M/M/1M/G/1： 同理： M/M/1还由于对M/D/1：2=0 M/D/1 M/D/1书P.82P.83 “三个P-K变换方程”：书P.83关于M/G/1重要结果：（二）考虑优先等级的排队系统（Priority Queueing SyStems）书P.93、4.3节到目前为止，在有关排队系统的讨论中，均假设“到达者按FCFS（先到先服务）接受服务”。显然，这不是服务原则的唯一形式，其它的服务形式还有：LCFS（后来先服务）、FIFO（先进先出）、FCFS（先来先服务）、RIRO（随机进随机出）、SJF（短作业先处理）、LJF（长作业先处理）以及优先排队等等不同情况。优先级队列还可进一步划分为两种形式：即：抢占（绝对）优先级和非抢占（简单）优先级队列。对于抢占（绝对）优先级（Preemptive SyStems）优先级别高的到达顾客允许中断优先级别比它低的到达顾客的服务。这种中断有两种情况：其一，被中断的服务以后还可以从中断点继续服务；其二，从头开始服务。对于非抢占优先级系统（Nonpreemptive Systems）中，不存在中断，因为优先级别高的到达顾客必须等待正在进行的服务结束后才能开始接受服务。关于考虑优先等级排队系统的必要性（举例）请参看：书P. 108，所列举的例子。举例 非抢占（简单）优先级的性能分析设在队列中有r个级别的顾客需要服务；其相应到达率为1，2，r，都是泊松流。对第k级，平均服务时间为， K=1，2，r（k=1为最高优先级；k=r为最低优先级）以优先级下降次序进行标定。对于非抢占服务情况下，怎样计算任一级的平均等待时间？考虑优先级p（1pr）设这一级的某一顾客在任意时刻t0到达，从他的到达时刻到他进入服务为止的随机等待时间WP，取决于下列三个因素： 顾客到达 服务开始 Wp 时间 t0 t1 排队系统的等待时间情况1：他必须等待一段随机时间T0，直到正在被服务的顾客完成服务。情况2：他必须等待Tk（一个时间单位），直到在t0时刻已在队列内排队的优先级p的所有k级顾客结束服务（优先级值kp）亦即，k优先级p优先级。情况3：他必须等待Tk（一个随机时间），去为在等待期间Wp内到达的优先级大于p的每一个k级顾客结束服务。 i.e. k优先级比p优先级高，或说优先级值k小于优先级值p。把以上三种情况的观察结果合在一起，可写出： （1）逐项求数学期望，可三等优先级p的平均等待时间： （2）为了求出（2）式中的三项平均时间，要注意到：Emk 在系统中等待的k类顾客的平均数； Emk中的每一位顾客需要单位的服务时间。 （3）按Littles 公式，可得： （4）将（3）和（4）式结合起来，可得： （5）这一项是由于在Ewp时间片内到达的k级顾客的平均数而引起的。因为，到达速率为k，并且每一位顾客需要单位的平均服务时间，可得： （6） 这是一位正在接受服务顾客的剩余服务时间。对于工作守恒非抢占排队系统，只要有顾客等待，SerVer总是不停顿地服务，这是与排队规则无关的，如果所有k级顾客以相同优先级按到达次序受到服务，也是如此。 左右两侧取数学期望右侧： 其中：为kEwk：自p级来到的顾客发现在队列中自k级的顾客数。 其中：为kEwk：自k级的顾客数当自p来到顾客在等待时来到。这样，可导出：按M/G/1：平均等待时间可得： （7） 平均剩余服务时间把（6）和（5）式用于（2）式，从是高优先级“1”级开始，循环地求解每一级的等待时间，很易证明： （8）其中： ETo由（7）式给定对优先级p=1： 对优先级p=2直到对优先级为p 举例：对两个最高优先级的分析，作为一个例子，讨论两个最高优先级： （9）以及 （10） =1+2最高优先级（1级）顾客，排队时就如同在只有一个级别的M/G/1系统中排队一样，只看到他们自己。差别仅仅在于正在接受服务的所有级别的顾客的剩余服务时间ETo。在只有两个优先级的特殊情况下，如同本节开始时谈及Ew1，EW2分别给出这两级的平均等待时间。对于=0.5，以及前面给定的数据，无优先级时的平均等待时间Ew为148ms，对于同一例，由Ew1式得到 Ew1=74.5ms。由Ew2式得到 Ew2=149ms。优先级高的控制分组的平均等待时间下降到差不多是无优先级时的一半；而优先级低的数据分组的等待时间只增加了，变化甚微。显示出利用优先级排队可能得到的性能改进。根据Ewp式，即Ewp= 可简单地证明：等待时间的加权和总是守恒的 可得： （11）其中，Ew由 Ew= 给定，它是FIFO M/G/1排队的等待时间，当某些等待时间下降时，其它的必定上升以便补偿。作为一种校验，在上述的两个优先级例子中，当无优先级时Ew=74ms。有优先级时：1Ew1+2Ew2也等于74ms这个守恒定律是工作守恒排队系统更为通用的守恒定律的一个特例。第5章 计算机系统的性能分析常见的作业调度算法综述调度算法FCFS最简易的一种调度算法，先进入系统的作业先得到服务。通常作业按优先级分类，在同一优先级中仍按FCFS调度，而在不同优先级之间；（1）抢占优先级高的作业一旦来到，立即中断正在服务的作业，而不管它是否已完成。（2）非抢占等待正在服务中的作业完成后再进行调度。对抢占的算法：（1）若被中断的作业重新轮到执行时，是从中断的地方继续执行者称为“抢占恢复的方式”。（2）若是从头开始者称为“抢占不恢复的方式”。通常，I/O设备常用FCFS，不用抢占方式；对于CPU系统的软/硬件均可用抢占调度算法。LCFS每个作业的来到，都将引起新的调度，要考虑是否抢占。通常为LCFS抢占恢复算法（可用于交互方式的处理机调度之中）。RR（循环调度算法）这是一种常见的处理机调度算法，既可以用于批处理方式，也可以用于交互方式（较多地使用此种方式）。这种算法要求把CPU时间划分为时间片，在规定的时间片内作业按FCFS进行调度。当现行作业用完了它的一个时间片后，即使服务尚未完成，也必须被抢占。操作系统（O.S）把它的现场信息保存后（供以后恢复之用）把它放到队列的尾部重新排队，同时，把队列最前面的作业送到CPU处理。在RR情况下，每个作业的服务时间都被分割为不连贯的时间片（最后一次可能不是一个完整的时间片），这样，可以避免由于长作业独占而使短作业长时间等待的情况下，也可以缩短系统的平均响应时间。对RR而言，一个重要的问题是如何合理选择时间片的大小，若时间片过短：会增加系统内部的开销；若时间片过长：会降低分时共享处理机的效果，接近于FCFS的情况。PS（PR）处理机（资源）共享与分时系统的差别：分时系统（Time-Shauing）以部分时间为基础，把处理机的全部能力为这些顾客服务称“分时系统”，这里所谈的“RR”便是典型实例。处理机共享（Processor-Sharing）以全部时间为基础，把部分处理机能力为顾客服务，称为处理机资源共享系统。注意：什么情况下会出现RRPR？若时间片相对于内部开销而言是很大的话，而相对于平均服务时间却很小的话，此时RRPR。作为RR的极限情况此时RR在内部开销和时间片趋于。如同所有作业几乎同时接受处理机的服务（实际不存在）。最短的作业先服务（SJF）从缩短平均响应时间而言，SJF是较好的一种调度算法。一个较短的作业进入系统，就抢占处理机，中断正在服务的作业。问题思考：调度程度如何辨认哪个作业是较短的？方法1：根据作业以前执行的情况进行预测，并分配其优先级称为“先验知识调度方法”，但是，先验知识未必有，服务时间的预测也难以准确。对于一些转动式的I/O（如活动头磁盘），使用最短查找时间先存取的算法，效果较好。有时可以采用下列表达方式：型式#1节点*：FCFS/M/1这个型式的节点含单一服务装置，利用FCFS规则，服务时间为指数分布（具有参数ik，它是k的函数，k为在i节点内的顾客数。型式#2节点*：RR（或分时PS）/G/1这个型式的节点是单一服务装置，利用RR处理机共享算法，服务时间为任意分布。型式#3节点*：/G/这个型式的节点无限Servers，任意服务时间分布。型式#4节点*：LCFS/G/1这个型式的节点有一个单一服务装置，具有抢占恢复LCFS作业调度算法，任意时间分布。以上“G”（指在型式#2#4）容许随顾客等级而变化。书P.114、5.3节“RR调度算法”书P.114图5.3，循环系统。RR为分时计算机系统最著名和广泛使用的调度算法。书主要符号汇集P.3第5章 符号及其含义：qpn为来自优先级p及该顾客第n次进入服务的某顾客所提供的（服务时间）定额。n（x）到目前为止已接受x秒服务的仍处在该系统内的顾客的平均密度。N（x）在队列系统的平均顾客数，这些顾客恰好已获得x秒的服务。（x）已获得x秒服务（寿命/年龄）的完成服务速率。假设qpn=q0亦即所有限额均有相同大小并且缩小到零。新来到的顾客参与单一队列，它们的工作方式（直到队列的头）均为FCFS，然后，接收一个服务限额。当所论限额到期，并且如果他们还需要进一步服务的话，然后，他们就返回到相同队列的尾，并重复循环。在这种处理机共享系统中，某顾客被需要作无限次循环而每次无限地“快”且每次接受无穷小服务，直到最终该顾客所获得的服务等于他的所需的服务（时间）为止，此刻他便离去了。RR的工作方式接受服务的速率某瞬时某一顾客进入一个“空”的系统（接受服务时间/秒）1秒/秒第2个顾客来到并参与循环（接受服务时间/秒）1/2秒/秒第k个顾客来到并参与循环（接受服务时间/秒）1/k秒/秒这个一阶微分方程有其解：（利用）在指数内的积分可求出并且用代入得到：可完成：书P.115（5.3.2）式在书P.113（5.1.11）式可得到：作业返回到队列系统的平均到达速率，这些作业已访问CPU n次，正好接受过n秒服务。按M/G/1：平均响应时间与服务时间分布形式无关（只与平均服务时间有关）（x）已完成x秒服务的速率已获得x秒服务（寿命）的完成服务的速率 （pdf） 服务时间（pdf）与（x）=dB（x）/dxn（x）在系统内已获得x秒服务的顾客的平均密度n（x+x）=n（x）1-（x）x+O（x） 某顾客所需的服务（已接受x秒的服务）（x+x）秒时的概率在RR系统内T（u）=， XO （书P115（5.3.3）式）求出未知常数n（o）？对于非常大的服务时间的响应时间，此时，在长（测试）作业离去之前必须被完成服务。这个长测试作业是作为最低优先级的顾客出现。按书P116，从（5.3.3）式，可求出常数n（o）为最后，可得到RR处理机共享系统的确切解： 书（5.3.4）式即T（x）-x=w（x） 书（5.3.5）式对RR的评估：1、响应时间与服务时间是严格的线性关系，若某一个作业比其它作业长2倍，则平均响应时间T也大2倍。2、平均响应时间与服务时间分布B（x）无关，只与服务时间的平均值（通过）有关，这样，RR处理机共享系统消除了平均响应时间与服务时间方差（或较高阶矩）有关的任何依赖关系。表明平均等待时间 则是有限的（只要）注意到：FCFS系统，若时，导致无边界平均等待时间3、所花费时间/服务时间之比RR（PS）FCFS只需若4、回报函数（Penaly function）5、当服务时间为任意分布“G” =？采用PS调度算法其性能总是与指数分布（=1）时相同。1的分布：采用PS要比采用FCFS有很大的性能改善。1的分布：用PS要比用FCFS稍差一些。（）6、当为相当长的作业时，在抢占HOL（队首）优先级时所得结果：（RR系统）抢占HOL：书P.117 图5.4 5.4节LCFS调度算法第6章 ATM网络的拥塞控制 在ATM网络内的拥塞控制是一个尚未解决的课题，有关ATM网络的一些复杂的控制问题包括以下各个方面：各种可变比特速率（VBR）信源、在不同的速率上生成业务量（如终端到终端通信可以只生成少数kBit/s级的业务量，而HDTV（高清晰变电视）业务，将使用若干Mbits的网络带宽）。还有某些应用的比特生成速率能经常有时变特性。单一信源可以生成具有不同特性的多重业务量的形式（即语音、数据、图像等等）。在现有网络内，除了呼叫拥塞的性能矩阵以及分组丢失概率之外，ATM网络还必须处理信元时延变化，最大时延以及非对称性等问题。不同的业务处在大量可变数量级上，有不同形式的服务质量（QOS）需求。把VBR业务量的统计多路复用进入相同介质，并与面向连续比特（CBO）业务量在一起，这样两种应用形式将会使网络性能的可预见性方面复杂化。对于实时业务而言，一旦出现性能下降，就特别容易受到伤害。对于各种业务形式的业务量特征，尚未很好地理解。随着传输速度增加，呼叫持续时间对信元传输时间之比增加，对所论问题增加了新的因素。如在B-ISDN中，由于宽带传播时延，在该网络内在任何时刻有大量信元处于转发状态，因此，与传输时间相比较，其较大的传播时延，使得通过网络控制元素察觉拥塞条件的开始与发现拥塞之间的周期变长。由于传输速度较高，于是，在跨越中间节点的过程中，用于进行任何其他处理的时间，将会受到限制。 有关ATM网络的两类拥塞控制机制：预防性的控制方式；反应性的控制方式；应该注意到：*预防性的拥塞控制技术，力图在拥塞实际发生之前，设法采取相应的措施来预防拥塞。但此法不能充分地消除拥塞。*反应性控制：是指从拥塞状态到进入恢复状态的技术。问题：某源点接受一个通知，但有可能对此反应太迟缓。书P.131 图6.1针对“预防控制”和“反应控制”对ATM网络的业务是控制方式的选择：例如：预防控制涉及 业务量管辖； 业务量整形； 内部呼叫参数协商； “反应控制”涉及 动态信源编码；适配速率控制； 适配窗口；其它，对于以上两种机制均有用的措施还有提供资源；呼叫接纳控制；呼叫选路；超业务量标记；选择放弃等等。其中，资源供应（或提供资源）对现有网络是一个重要的业务量管理功能，其主要作用在于提供一种可接受的连接及拥塞性能的等级、网络的拓展、链络的数量及其带宽、交换与接入节点的数量等将按照对业务量需求的理解而全部被确定。然而，用户数量，所生成的业务量数量以及在通信网内所采用的应用形式将会发生变化。因此，可能会出现增加新的链路、或用相应较高带宽来置换现有链路，或附加新的节点等等。如果调整这些资源不及时或不适宜就会产生引起拥塞的可能性。书P.132 图6.2 在进入网络的入口处就要完成对连接的控制。有关B-ISDN ATM层业务量控制的目标如下： 灵活性它应支持所有现有的和未来的业务量，使之在ATM层达到足够的QOS等级。 简便性设计一种简单的ATM层业务量控制机制，使之达到简化网络设备，并能提高网络利用率。 健全性在任何业务量环境下，实现对资源的需求是高效率的，并仍保持简单的控制功能。以上谈及：在B-ISDN中对业务量控制的主要作用在于对网络和用户的保护。书P.133 6.2节 “呼叫接纳控制”当在网络上接收新的连接请求时，便会执行呼叫接纳过程，以便确定是否接受或者拒绝这个呼叫。接受这一呼叫的条件为：若该网络有充足的资源，确保提供该连接请求的服务质量（QOS）需求，并不会影响对现有连接所提供的QOS。问题如下：怎样确定某一条新的连接所需的带宽？当和这条新的连接一起被多路复用时，怎样保证对现有连接所需的服务等级不会受到影响？书P.135 6.2.2节 “带宽分配”要确定某一条连接所需的带宽数量，以便网络为其提供相应的QOS。有两种可选途径： 定数论的多路复用：把峰值带宽分配给每条连接，这样对于突发连接，特别是对于大的峰值对于平均比特速率而言，就会造成浪费大量的带宽，定数论的多路复用几乎能完全消除信元级拥塞。然而，缓冲器将会溢出的概率也并非为零，并且信元也会丢失。定数论的多路复用统计多路复用不能吸取ATM多路复用能力的优点，并且限制其利用网络资源。它与ATM结构的原理相抵触。是一种可选用的方法。在该方案中，网络对某一种VBR信源（或称某一条连接的统计带宽）所分配的带宽数量是小于它的峰值的，但大于它的市场比特速率。书P.137 6.3节 UPC与NPCUPC功能：用法参数控制是由这个网络所采取的一组动作来定义的，用以监视和控制业务量，使之与协商的业务量相符以及在用户接入方面与信元有效选路相一致，主要目的在于保护网络资源。UPC和NPC的监视任务是由以下方面来执行的：如上所述，总之，在B-ISDN中对业务量控制的主要作用在于对网络和用户的保护。书P.133 6.2节 呼叫接纳控制书P.136 图6.3现考虑具有相同价值与平均比特速率的两种社会性连接的形式：第1种形式具有长活动的与静止的周期第2种形式这两个周期都很短以上两者均按IBP建模 中断的伯努里过程针对第2种连接形式：设信源利用固定在0.5；在忙周期期间（-1）在每个时隙上有一个信元到达；活动与静止周期的平均持续时间为2个时隙（p1=0.5，q1=0.5）；此时信元到达间隙时间的变异系数的平方C2=0.5针对第1种连接形式活动与静止周期的平均持续时间为4个时隙（p1=0.75，q1=0.75）。此时C2=1.5若