排队论与计算机系统-网络.ppt

《排队论与计算机系统-网络.ppt》由会员分享，可在线阅读，更多相关《排队论与计算机系统-网络.ppt（89页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Introduction排队论与计算机系统/网络性能评价计算机系统计算机系统性性能评价主要目的n1选择n 在众多的系统中选择一个最需要的系统（计算机，网络，其他），或在众多的方案中选择一个较好的方案，即在一定的价格范围内选择性能最好的系统（或方案），达到较好的性能/价格比。n2改进n 对已有系统的性能缺陷进行改进，以便提高其运行效率。n3.设计n 对未来设计的系统进行性能预测，在性能成本方面实现最佳设计或配置。性能参数性能参数1可靠性或可利用性系统能正常工作的时间，其指标可以是能够持续工作的时间长度，如平均无故障时间,也可以是在一段时间内,能正常工作的时间所占的百分比。2处理能力或效率l吞吐率

2、：系统在单位时间内能处理正常作业的个数。l响应的时间：系统得到输入到给出输出之间的时间。l利用率：在给定的时间区间中，各种部件(包括硬设备和软系统)被使用的时间与整个时间之比。l丢失率(或阻塞率)：信息传输(用户呼叫)丢失量与信息传输(用户呼叫)总量之比。性能评价方法性能评价方法(1)计算机和网络系统性能评价常用的有以下三种方法：1 测量方法（测量方法（measurement）l测量：通过一定的测量设备或一定的测量程序直接从系统测得各项性能指标或与之密切相关的量；l运算：求出相应的性能指标。优缺点：l最直接、最基本的方法，其它方法也要依赖于测量的量l测量方案和测量手段是测量方法的关键l比较费时

3、间l适用于已经存在并运行的系统性能评价方法(2)2 仿真（仿真（simulation）/模拟模拟(emulation)方法方法用程序动态地模拟系统及其负载。l描述：模拟语言建立系统模型；l执行：事件或时间驱动系统模型；l统计分析：性能参数。优缺点l详细地刻划系统l较精确的性能指标l费时、费用较高性能评价方法(3)3 分析方法分析方法(analysis)用数学模型工具的理论与方法描述性能与系统、负载之间的关系。l(StochasticProcessAlgebras)随机过程代数l(StochasticPetriNets)随机Petri网l(QueueingTheory)排队论优缺点优缺点l模型进

4、行简化和假设l刻划系统的详细程度较低l与实际性能指标有差距l理论基础强、刻划各种因素之间的关系l省时、费用也较低本课程的主要内容：排队论及其模型本课程的主要内容：排队论及其模型重点讲述排队模型、排队网络模型及在计算机中的应用本课程的预修课程为：概率论和随机过程、计算机体系结构Introduction随机过程&排队论初步内容提要n两个重要分布：指数分布、Poisson分布n随机过程简介n排队论初步ExponentialDistributionnAcontinuousR.V.Xfollowstheexponentialdistributionwithparameter,ifitspdfis:n=P

5、robabilitydistributionfunction:nUsuallyusedformodelingservicetimeExponentialDistribution(contd.)MemorylessPropertyn无后效性无后效性 不管多长时间不管多长时间(t)已经过去，逗留时间的概率分已经过去，逗留时间的概率分布与下一个事件的概率相同布与下一个事件的概率相同nPasthistoryhasnoinfluenceonthefuturenProof:nExponential:theonlycontinuousdistributionwiththememorylessproperty

6、(exp(x+t)=exp(x)exp(t)nExample:problem3.5指数分布例题-习题3.53.5 记性不好的教授在同一时间约了两个学生记性不好的教授在同一时间约了两个学生(应应分别约见分别约见).第一个学生准时到达第一个学生准时到达,第二个学生第二个学生迟到迟到5分钟分钟.假定和每个学生谈话的时间为指数假定和每个学生谈话的时间为指数分布的随机时间分布的随机时间,均值为均值为30分钟分钟.试计算整个试计算整个谈话的平均谈话的平均(expected)时间时间.习题3.5（Contd.）n解解:如果和第一个学生的谈话在如果和第一个学生的谈话在5分钟内没分钟内没结束，剩余的谈话时间仍为

7、均值结束，剩余的谈话时间仍为均值30分钟的分钟的指数分布时间指数分布时间.如果如果5分钟内谈完了则和他剩分钟内谈完了则和他剩余的谈话时间为余的谈话时间为0.所以和第一个学生剩余谈所以和第一个学生剩余谈话时间平均为话时间平均为:PX530+PX50=PX530.所以和第一个学生谈话的平均时间为所以和第一个学生谈话的平均时间为:n 5+PX530=30.38n 整个谈话的平均整个谈话的平均(expected)时间为时间为60.38习题3.6n假设某一银行有假设某一银行有4个服务窗口个服务窗口.某人进到银行时某人进到银行时,看看到有到有4个客户在个客户在4个窗口接受服务个窗口接受服务,而且没有其它客

8、而且没有其它客户等待户等待.假定每个客户的服务时间都是独立的相同假定每个客户的服务时间都是独立的相同的指数分布的指数分布(平均平均1分钟分钟,=1).(1)这个人最后离开银行的概率是多少这个人最后离开银行的概率是多少?(2)这个人平均在银行里停留多长时间这个人平均在银行里停留多长时间?习题3.6（Contd.）n(1)这个人最后离开银行的概率是多少这个人最后离开银行的概率是多少?n 当这当这4个人中有一个人离开时该人接受服务个人中有一个人离开时该人接受服务,这时其它这时其它3人的人的剩余服务时间仍有相同的指数分布剩余服务时间仍有相同的指数分布.从对称性可知从对称性可知,这这4个人中个人中任何一

9、个最后离开的概率都是任何一个最后离开的概率都是1/4.n(2)这个人平均在银行里停留多长时间这个人平均在银行里停留多长时间?n 这个人从进入银行到接受服务的时间等于这个人从进入银行到接受服务的时间等于min(X1,X2,X3,X4),X1,X2,X3,X4为正在接受服务的为正在接受服务的4个客个客户的剩余服务时间户的剩余服务时间,都是指数分布的随机变量都是指数分布的随机变量.n 随机变量随机变量 min(X1,X2,X3,X4)有以下分布有以下分布:n Pmin(X1,X2,X3,X4)x=exp(-4x),n 仍为指数分布仍为指数分布,均值均值=1/(4)=0.25分钟分钟.n 所以这个人平

10、均在银行停留的时间为所以这个人平均在银行停留的时间为1.25分钟分钟.n作业：习题作业：习题3.6（c）,3.8(a)(Try to prove!)PoissonDistributionPoissonDistribution(contd.)SumofPoissonRandomVariablesSumofPoissonRandomVariables(cont.)SamplingaPoissonVariableSamplingaPoissonVariable(contd.)Howcome?PoissonApproximationtoBinomialSmallIntervalProbabilitie

11、s内容提要n两个重要分布：指数分布、Poisson分布n随机过程简介n排队论初步随机过程n随机变量X，分布函数不变n如果随机变量的分布函数随时间变化，对时间集合T，得到一组随机变量，称之为随机过程随机过程n如果时间集合T离散，如T=0,1,2,，称为离散离散时间的随机过程时间的随机过程，Xn:nTn如果时间集合T连续，称为连续时间的随机过程连续时间的随机过程，X(t):tTn如果Xn或者X(t)离散/连续，称这个随机过程离散随机过程离散/连续连续n例：n某路由器的IP包t时刻进入缓存等待转发，等待时间W(t):t0是一个连续时间的连续随机过程n从时间0到t到达路由器的IP包个数N(t):t0是

12、一个连续时间的离散随机过程nXn表示一周7天中某一天某计算机启动的进程数，n1,2,3,4,5,6,7。Xn是一个离散时间的离散随机过程。nXn表示一周7天中某一天某计算机的工作时间，n1,2,3,4,5,6,7。Xn是一个离散时间的连续随机变量。计数过程n令N(t)表示在时间段0,t)内的某种事件发生的次数。N(t)称为该事件的计数过程计数过程。计数过程是一种随机过程。n事件：数据包到达路由器；顾客到达商店n性质：1.N(0)=02.N(t)非负3.如果s0内事件发生的个数，则n证明：定义，取h0代入初始条件，得到参数为t的泊松分布对时间t+h时n个事件发生的情况Pn(t+h)，三种情况1.

13、时间t时已经发生了n个事件，2.时间t时发生了n-1个事件，t,t+h)这段时间发生了1个事件3.时间t时发生了n-k个事件，t,t+h)这段时间发生了k个事件，k1取h0，初始条件，迭代求解得到n定理：N(t)，t0是一个速率为的泊松过程。令0t1t2t3s，N(tn-1+s)-N(tn-1)=0所以，Pns=PN(tn-1+s)-N(tn-1)=0=PN(s)=0=e-s指数分布n定理：N(t)，t0是一个计数过程，事件发生间隔记为n。如果n为独立同分布的随机变量，且服从参数的指数分布，则N(t)是一个泊松过程。n证明：略Merging&SplittingPoissonProcessesM

14、odelingArrivalStatisticsnPoissonprocesswidelyusedtomodelpacketarrivalsinnumerousnetworkingproblemsnJustification:providesagoodmodelforaggregatetrafficofalargenumberof“independent”usersnntrafficstreams,withindependentidenticallydistributed(iid)interarrivaltimeswithPDFF(s)notnecessarilyexponentialnArr

15、ivalrateofeachstream/nnAsn,combinedstreamcanbeapproximatedbyPoissonundermildconditionsonF(s)e.g.,F(0)=0,F(0)0nMostimportantreasonforPoissonassumption:Analytictractabilityofqueueingmodelsn总结泊松过程n从时间0到时间t发生的事件个数是参数t的泊松分布n事件发生间隔n是指数分布泊松过程36n例:某商店，假设顾客按照以下比例单个或者成双到达，f(1)=p，f(2)=1-p。客户到达批次间隔服从以下分布证明时间0,t

16、)内累计到达的客户数量服从分布n如果总共有n个客户，假设其中发生k次成对到达，n-2k次单个到达，分别可以用速率为(1-p)和p的泊松过程表示。nk次成对到达，nn-2k次单个到达，nk的取值范围从0到n例:给定两个泊松过程，事件发生速率分别为1，2。从时间t=0开始，问首先观察到第一个过程事件发生的概率。n假定过程1的第一个事件发生的时间是t1，过程2的第一个事件发生的时间是t2。t1和t2是参数为1和2的指数分布n内容提要n两个重要分布：指数分布、Poisson分布n随机过程简介n排队论初步排队问题n排队随处可见n顾客在超市收银柜台排队n飞机在机场排队等待起飞n进程在操作系统排队等待调度n

17、n排队的原因：由于服务需求大于服务能力n规范用语n客户（Customer），请求并接受服务者，例如顾客、飞机、进程、等等n服务器（Server），提供服务的设施，例如收银员、机场跑道、CPU、等等n(Kleinrock)“We study the phenomena of standing,waiting,and serving,and we call this study Queueing Theory.Any system in which arrivals place demands upon a finite capacity resource may be termed a queu

18、eing system.”nLeonard.Kleinrock is Distinguished Professor of Computer Science at UCLA.Known as a Father of the Internet,he developed the mathematical theory of packet networks,the technology underpinning the Internet,while a graduate student at MIT.n他在其博士论文中最早用排队论证明了分组交换网络的优越性(1961)。并在1969年12月，参与了美

19、国四所大学使用接口消息处理器（IMP)建立起阿帕网(ARPANet)。LeonardKleinrock关于排队的定义nBook：Queueing systems:Computer applications by Leonard Kleinrock,published by John Wiley&sons,1975一般性定义n排队论是专门研究带有排队论是专门研究带有随机随机因素，产生拥因素，产生拥挤现象的优化理论。挤现象的优化理论。n排队系统也称为排队系统也称为随机随机服务服务系统系统nIncomputerscience,queueingtheoryisthestudyofqueuesasate

20、chniqueformanagingprocessesandobjectsinacomputer.nAqueuecanbestudiedintermsof:nthesourceofeachqueueditem,nhowfrequentlyitemsarriveonthequeue,nhowlongtheycanorshouldwait,nwhethersomeitemsshouldjumpaheadinthequeue,nhowmultiplequeuesmightbeformedandmanaged,ntherulesbywhichitemsareenqueuedanddequeued.Qu

21、eueingtheoryforcomputerscienceQueueingtheoryforstudyingnetworksnView network as collections of queues nFIFO data-structures nQueuing theory provides probabilistic analysis of these queuesnExamples:nAverage length(buffer)nAverage waiting timenProbability that queue is at a certain length nProbability

22、 that a packet will be lost SourcesofNetworkDelaynProcessingDelaynAssumeprocessingpowerisnotaconstraintnQueueingDelaynTimebufferedwaitingfortransmissionnTransmissionDelaynPropagationDelaynTimespendonthelinktransmissionofelectricalsignalnIndependentoftrafficcarriedbythelinknFocus:Queueing&Transmissio

23、nDelay排队系统六要素n一个排队系统包括六要素n客户到达过程n服务过程n服务器数量n系统容量n顾客源数量n排队规则排队系统六要素n客户到达过程n耐心客户/非耐心客户：中途离开？n客户到达时间间隔可以看作一个随机变量n用一个随机过程描述客户到达模式n例如：可以用一个泊松过程表示客户到达，到达间隔服从指数分布n平稳/非平稳（stationary）到达模式n例如：突发大批到达客户n服务过程n状态无关/状态相关n服务时间可以看作一个随机变量n例如：可以用一个指数分布描述服务时间n平稳/非平稳（stationary）服务时间n例如：服务器可以学习，提高服务效率n服务器数量n单个/多个服务器n多服务器

24、多队列，多服务器单队列多服务器多队列多服务器单队列n系统容量n客户不能立即获得服务时选择等待/离开n有限/无限个等待位n系统的顾客源数量n有限n无限n排队规则nFCFS，LCFS，优先级n抢占优先（Preemptive），非抢占优先（Nonpreemptive）52排队系统命名法则(Kendallnotation)n一个排队系统表示为A/B/C/X/Y/ZnA：客户到达模式nB：服务模式nC：服务器数量nX：排队系统的最大容量n当队列缓冲区容量无限时可省略nY：顾客源数量n当顾客源数量无限时可省略nZ：排队规则n缺省值是FCFS53符号取值解释A、BM、D、Ek，Hk，G客户到达间隔/服务时间

25、的概率分布，M表示指数分布（马尔可夫），G表示任意分布，D表示固定值C，X，Y1,2,服务器/系统容量/顾客源数量ZFCFS，LCFS，RSS，PR，GD先到先服务，先到后服务，随机，优先级，任意n例：M/D/2/FCFS，客户到达符合泊松过程;固定服务时间;2个服务器；系统容量无限；First-come-first-serven通常假定系统容量无穷，顾客源数量无穷和FCFS，因此常用A/B/C描述一个排队系统n比如，M/M/1，M/M/c，M/M/m/m，M/G/1，*/D/，等等DistributionsnM:stands for Markovian/Poisson,implying ex

26、ponential distribution for service times or inter-arrival times.nD:Deterministic(e.g.fixed constant)nEk:Erlang with parameter knHk:Hyperexponential with param.knG:General(anything)Thepdf(x0)todifferentsymbolsnM:nD:nEK:nHK:nG:b(x)isarbitrary服务规则FCFS：先来先服务；LCFS：后来先服务；RSS：随机选择服务；PR：优先级服务GD：一般规约服务，即通用规约

27、服务。Ba：集体（批量）服务。57排队系统常见的性能指标n客户等待时间n客户在队列中等待的时间(Wq)n客户在整个排队系统中消耗的时间(W)=队列等待时间+服务时间n客户在排队系统中的累积程度n等待队列中的客户数目(Nq)n整个排队系统中的客户数目(N)=等待队列客户数目+正在接受服务的客户数目n空闲服务器n服务器空闲的时间比例n系统设计目标：提高服务器利用率，缩短客户等待时间等等，目标往往是相互矛盾的n排队论中的假设：排队论中的假设：在排队分析中，最重要的一个假设是到达速率服从泊松分布，等效的说法是到达间隔时间服从指数分布，这又等价于说到达是随机的并彼此独立。我们几乎一直要作这一假定。没有它

28、，大部分的排队分析是不可能的。在这个假定的条件下，我们会发现仅仅知道到达速率和服务时间的均值和标准差就可以得到许多有用的结果。基本排队关系：基本排队关系：Little定理定理nLittle公式是排队论中的通用公式公式是排队论中的通用公式nLittles定理可以对排队系统进行确定性分析.n排队系统是随机过程,但它的一次实现(运行)是确定的过程.nErgodicity:时间平均=随机平均.nLittles定理中时间平均换成处于稳态的随机过程的数学期望值仍成立.LittlesTheoremn:customerarrivalratenN:averagenumberofcustomersinsystem

29、nT:averagedelaypercustomerinsystemnLittlesTheorem:Systeminsteady-staten N=TThe long-term average number of customers in a stable system N,is equal to the long-term average arrival rate,multiplied by the long-term average time a customer spends in the system,T.LittlesTheorem(contd.)GeneralityofLittle

30、stheoremnLittles Law is a pretty general resultnIt does not depend on the arrival process distributionnIt does not depend on the service process distribution nIt does not depend on the number of servers and buffers in the system.nApplies to any system in equilibrium,as long as nothing in black box i

31、s creating or destroying tasksCountingProcessesofaQueuenN(t):numberofcustomersinsystemattimetn(t):numberofcustomerarrivalstilltimetnb(t):numberofcustomerdeparturestilltimetnTi:timespentinsystembytheithcustomer(t)N(t)tb(t)TimeAveragesnTimeaverageoverinterval0,tnSteadystatetimeaveragesnLittlestheoremN

32、=TnAppliestoanyqueueingsystemprovidedthat:LimitsT,anddexist,and=d Aboveassumptions:stablesystemWegiveasimplegraphicalproofunderasetofmorerestrictiveassumptionsProofofLittlesTheoremforFCFSnAssumption:N(t)=0,infinitelyoften.ForanysuchtnIflimitsNtN,TtT,t exist,LittlesformulafollowsnWewillrelaxthelastas

33、sumption(N(t)=0,infinitelyoften).nFCFSsystem,N(0)=0n(t)andb(t):staircasegraphsnN(t)=(t)-b(t)nShadedareabetweengraphst(t)T1N(t)T2Tiib(t)ProofofLittlesTheoremforFCFS(cont.)nIngeneralevenifthequeueisnotemptyinfinitelyoften:nResultfollowsassumingthelimitsTt T,t,anddtdexist,and=d(t)T1N(t)T2Tiib(t)Proofof

34、LittlesTheoremwithoutFCFSiDelayT1delayDelayT3DelayT4DelayT5(t)tt1t2t4AssumeD(t)isthesetofcustomerswhohavedepartedthesystembytimetAssumeisthesetofcustomerswhoarestillinthesystemattimetThedelayexperienceduptotimetbyacustomerstillinthesystemattimetist-tiSoThereforeProofofLittlesTheoremwithoutFCFS(cont.

35、)ProbabilisticFormofLittlesTheoremnHaveconsideredasinglesamplefunctionforastochasticprocessnNowwillfocusontheprobabilitiesofthevarioussamplefunctionsofastochasticprocessnProbabilityofncustomersinsystemattimetnExpectednumberofcustomersinsystemattProbabilisticFormofLittlestheorem(cont.)npn(t),EN(t)dep

36、endontandinitialdistributionatt=0nWewillconsidersystemsthatconvergetosteady-statenthereexistpnindependentofinitialdistributionnExpectednumberofcustomersinsteady-statestochasticaver.nForanergodicprocess,thetimeaverageofasamplefunctionisequaltothesteady-stateexpectation,withprobability1.ProbabilisticF

37、ormofLittlesTheorem(cont.)nInprinciple,wecanfindtheprobabilitydistributionofthedelayTi forcustomeri,andfromthattheexpectedvalueETi,whichconvergestosteady-statenForanergodicsystemnProbabilisticFormofLittlesFormula:nArrivalratedefineasTimevs.StochasticAveragesn“Timeaverages=Stochasticaverages,”foralls

38、ystemsofinterestinthiscoursenItholdsifasinglesamplefunctionofthestochasticprocesscontainsallpossiblerealizationsoftheprocessattnCanbejustifiedonthebasisofgeneralpropertiesofMarkovchains结论：nLittles定理在任何调度规则下都成立Littles 定理可用于系统的任一部分，只定理可用于系统的任一部分，只要该部分有客户到达和离开要该部分有客户到达和离开.nLittles 定理可用于系统的任一特定的客定理可用于系统

39、的任一特定的客户类户类.Little定理应用举例1：Little定理可用于排队系统的任何部分2:队列内平均客户数和利用率队列内平均客户数和利用率(example3.1)n设设是传输线内数据包的到达速率，是传输线内数据包的到达速率，设设NQ为队列内为队列内等待传输的包数，等待传输的包数，W 是数据包在队列中的平均等待是数据包在队列中的平均等待时间（不包括传输时间），则按时间（不包括传输时间），则按Littles 定理，有定理，有 NQ=W n设设 正在传输线上传输的平均顾客数，正在传输线上传输的平均顾客数，为包的平均为包的平均传输时间传输时间,则则 n在排队系统中在排队系统中 通常称为系统的利用

40、率通常称为系统的利用率:为为server忙的忙的 时间时间(比例比例),1-为为server闲的时间闲的时间(比例比例).3：网络平均延迟(example3.2)设1,.,n为网络的各个结点的packet到达率,N为网络内平均packet数,packet平均延迟设Ni,Ti为结点i的traffc在网络中的平均packet数和平均延迟,将Littles定理用于节点i的traffic流有:4：包到达和服务时间固定时的传输线性能（例题3.3）nApacketarrivesatatransmissionlineeveryKsecondswiththefirstpacketarrivingattime0

41、.AllpacketshaveequallengthandrequireKsecondsfortransmissionwhere1.TheprocessingandpropagationdelayperpacketisPsecondsCalculate：ntheaveragetimeTapacketspendsinthesystemntheaveragenumberNinthesystem性能分析n传输时间小于到达间隔，系统无排队延迟。又因传播延迟P为常数,每个包经历确定的端-端延迟T:接收到的包间隔等于发送方发出的包间隔K(见图3.3)。n应用Littles定理得到链路上的平均分组数N:n假

42、定KK+P2K,则系统中至多2个包.当N(t)=2时线路上有在途中的packet，N(t)=1时仅有packet在传输。注意：1：从图中可以看到系统中顾客数随时间不收敛2：使用Little定理分析的结果是能得到随时间平均的顾客数5：窗口流控系统（example 3.4）n网络使用窗口流控限制进入网络的流量以防止网络拥塞.假定每个session使用的窗口大小为W,则任何时刻网络中该session的packets不会多于W个。n设为每个session中packet的到达速率,T为packet平均延迟.根据Littles定理，packet的平均延迟T满足W*T.n假定网络出现拥塞，每个会话在单位时间

43、内只能传输个数据包，这时有W*T。n在拥塞情况下，增加窗口大小，仅可能导致包的平均延迟增加，不可能得到更大的吞吐率。6：有：有K个个server的排队系统的排队系统（example 3.4）n(1)ConsideraqueueingsystemwithKservers,andwithroomforatmostNKcustomers(eitherinqueueorinservice).nThesystemisalwaysfull:weassumethatitstartswithNcustomersandthatadepartingcustomerisimmediatelyreplacedbyan

44、ewcustomer(closedqueueingsystems).Supposetheaveragecustomerservicetimeis,wewanttofindtheaveragecustomertimeinthesystemT.n(2)Assumethatcustomersarriveatbutareblocked(andlost)fromthesystemiftheyfindthesystemfull(openqueueingsystem).ThenthenumberofserversthatarebusymaybelessthanK.Letnbetheaveragenumber

45、ofbusyserversandletbetheproportionofcustomersthatareblockedfromenteringthesystem.Wewanttofindthelowerboundontheblockingprobability.(1)首先考虑饱和系统(闭系统).将Littles定理用于servers部分有,用于整个系统有闭系统分析常用来建立系统性能的（上下）界！(2)考虑loss系统（开系统）,即到达时系统满则丢掉.设为lossrate,(1-)为接受的到达率（吞吐率）,在server处用Littles定理有:(1-)K，得到的下界估计:6：有：有K个个ser

46、ver的排队系统的排队系统（example 3.4）7：Pollingsystem（example3.6）n卫星通信和局域网中使用polling或预约系统n考虑有m个packet流的预约系统，链路以轮询方式和这些流预约传输时间并为其传输。预约要占用系统时间，设Ai为第i个流的平均预约时间。设i为第i个流的吞吐率，Xi为第i个流的包平均传输时间，求平均轮询周期长度L。n本题将Littles定理分别用于m个数据流和预约流，得出平均轮询周期长度。n在server处应用Littles定理：第i个流的数据包占用server时间为iXi，所以数据流占用的总时间为=iXi,而1-为预约占用的时间n平均每个周期L预约占用的时间A=Ai，所以1-=Ai/L.n上式中解出L，得：7:Pollingsystem(cont.)8：计算机分时系统（example3.7）n这是一个闭排队网络,用于计算系统的饱和吞吐率或系统能支持的最大吞吐率并找出吞吐率的瓶颈。n设D为B-C间的延迟则PDNP；所以A-C间延迟T满足 R+PTR+NP.根据littles定理系统吞吐率满足：n在CPU处用Littles定理1/P，最后得到8：计算机分时系统（example3.7）n按T=N/得到平均用户延迟的界(bound):8：计算机分时系统（example3.7）Homework：nSeehomework1athttp:/