1、123第四章第四章 排队论在计算机系统排队论在计算机系统 性能评价中的应用性能评价中的应用223一一、基本思路和方法简单排队模型：输入过程输入过程 排队规则排队规则 服务机构服务机构到达者到达者离去者离去者队列队列服务装置服务装置在一个时间段内，到达者与离去者保持相对一致，使系在一个时间段内，到达者与离去者保持相对一致，使系统达到相对平衡和稳定。统达到相对平衡和稳定。323WLWLWLiitiii系统内平均顾客数：lim内系统内平均顾客数：在均时间内每个顾客在系统的平在内顾客平均到达速率在),0(),0(:),0(:tLtWtiii）差（和离去者人数）（内到达者人数在时刻系统内的顾客数为在tt
2、tttttL),0()()()(423计算机中的许多现象都可以以顾客，排队及服务的形式表示:如：资源问题资源问题数据、存储数据、存储 、计算机、计算机通信问题通信问题信号、信道、传输信号、信道、传输网络路由网络路由数据包、通道、传送数据包、通道、传送并行处理并行处理任务、处理机、计算、调度任务、处理机、计算、调度523由于：数据到达的时间间隔分布，数据到达的时间间隔分布，处理或传输部件的时间间隔分布处理或传输部件的时间间隔分布 处理部件的个数处理部件的个数产生了对应不同特征的概率分布应用的分析。产生了对应不同特征的概率分布应用的分析。如泊松分布可以对应并行处理中的多任务多处理机的分配；如泊松分
3、布可以对应并行处理中的多任务多处理机的分配；多线程，多核的调度效率等多线程，多核的调度效率等网络路由中的数据包与网络通道服从爱网络路由中的数据包与网络通道服从爱尓尓朗分布。朗分布。623二、I/O性能与系统响应时间 1.1.模型模拟和实际测量的方法来衡量。模型模拟和实际测量的方法来衡量。对对I/OI/O系统建立模型后，可以使用排队理论进系统建立模型后，可以使用排队理论进 行分析。行分析。设计出来的设计出来的I/OI/O系统还可以通过基准测试程序系统还可以通过基准测试程序 进行实际测量。进行实际测量。7232.衡量I/O系统的性能的标准 I/OI/O系统的多样性：哪些系统的多样性：哪些I/OI/
4、O设备可以和计算设备可以和计算 机系统相连接。机系统相连接。I/OI/O系统的容量：系统的容量：I/OI/O系统可以容纳多少系统可以容纳多少I/OI/O 设备。设备。I/OI/O吞吐量吞吐量有时也被称为有时也被称为I/OI/O带宽。带宽。I/OI/O响应时间响应时间有时被称为响应延迟。有时被称为响应延迟。8233.吞吐量和响应时间 0501001502002503000%20%40%60%80%100%实际吞吐量实际吞吐量/最大吞吐量最大吞吐量响应时间（响应时间（msms）923 获得较大吞吐率和较小响应时间是相互矛获得较大吞吐率和较小响应时间是相互矛盾的，如何进行折衷是计算机体系结构要研究盾
5、的，如何进行折衷是计算机体系结构要研究的问题。的问题。051015图形系统（图形系统（0.3s0.3s）图形系统（图形系统（1s1s）键盘系统（键盘系统（0.3s0.3s）键盘系统（键盘系统（1s1s）时间（时间（s s）进入时间系统响应时间思考时间键盘输入系统和图形输入系统的事务处理时间键盘输入系统和图形输入系统的事务处理时间 1023Little定律1.黑箱（Black Box）黑箱黑箱到达任务到达任务离开任务离开任务稳定状态：稳定状态：系统的输入速率系统的输入速率=输出速率输出速率 2.Little定律系统中的平均任务数到达率系统中的平均任务数到达率平均响应时间平均响应时间11233.证
6、明 假定对系统一个任务测量时间假定对系统一个任务测量时间:T Tobserveobserve统计在此期间统计在此期间:完成的任务数完成的任务数:N Ntaskstasks 每个任务的实际完成时间每个任务的实际完成时间 将这些时间求和得到将这些时间求和得到T Taccumulatedaccumulated1223Little定律：定律：系统中的平均任务数为到达率与平系统中的平均任务数为到达率与平 均响应时间的乘积。均响应时间的乘积。observedaccumulateTT=平均任务数平均任务数tasksdaccumulateNT=平均响应时间平均响应时间observetasksTN=任务到达率任
7、务到达率observetaskstasksdaccumulateobservedaccumulateTNNTTT=1323对于一个排队系统，如果在它达到统计平衡状态对于一个排队系统，如果在它达到统计平衡状态后，系统中任一时刻的平均队长后，系统中任一时刻的平均队长 、平均等待、平均等待队长队长 ，与每一顾客在系统中的平均逗留时，与每一顾客在系统中的平均逗留时间间 、平均等待时间、平均等待时间 之间有关系式：之间有关系式：sLqLsWqWqeqsesWLWL,成立，则称该排队系统满足成立，则称该排队系统满足LittleLittle公式。其中公式。其中 e e表示单位时间内实际进入系统的平均顾客数。
8、表示单位时间内实际进入系统的平均顾客数。1423服务的顾客，在他后面排队等待服务的平均顾客服务的顾客，在他后面排队等待服务的平均顾客数等于在他的平均等待时间内实际进入系统的平数等于在他的平均等待时间内实际进入系统的平均顾客数，即均顾客数，即 ；又考虑一个刚服务结束；又考虑一个刚服务结束的顾客，在他离开系统时留在系统中的平均顾客的顾客，在他离开系统时留在系统中的平均顾客数等于在他的平均逗留时间内实际进入系统的平数等于在他的平均逗留时间内实际进入系统的平均顾客数，即均顾客数，即 。在系统达到统计平衡下，考虑一个刚开始接受qeqWLsesWL 显然，显然，M/M/1/排队系统中，排队系统中，Litt
9、le公式是成立公式是成立的的，且，且 e等于泊松过程的参数等于泊松过程的参数。1523 例例1 1、对于一个稳定系统，即、对于一个稳定系统，即客户到达该系统的平均速率客户到达该系统的平均速率=客户离开该系统的平均速率客户离开该系统的平均速率 设：一个并发服务器，并发的访问速率是设：一个并发服务器，并发的访问速率是10001000客户客户/分钟，分钟，每个客户在该服务器上将花费平均每个客户在该服务器上将花费平均0.50.5分钟，根据分钟，根据littles lawlittles law规则，在任何时刻，服务器将承担规则，在任何时刻，服务器将承担 100010000.50.5500 500 个客户
10、量的业务处理。假定过了一段时个客户量的业务处理。假定过了一段时间，由于客户群的增大，并发的访问速率提升为间，由于客户群的增大，并发的访问速率提升为 20002000客客户户/分钟。在这样的情况下，我们该如何改进我们系统的分钟。在这样的情况下，我们该如何改进我们系统的性能？性能？根据根据littles lawlittles law规则，有两种方案：规则，有两种方案：第一：提高服务器并发处理的业务量，即提高到第一：提高服务器并发处理的业务量，即提高到200020000.50.510001000。第二：减少服务器平均处理客户请求的时间，即减少到：第二：减少服务器平均处理客户请求的时间，即减少到：20
11、0020000.250.25500500。1623三、M/M/1排队模型1、简单的排队系统(M/M/1/FCFS）应用）应用I/O控制器及外设队列队列服务员服务员任务到达任务到达 假定假定I/OI/O请求的到达时间和服务员的服务时请求的到达时间和服务员的服务时间服从指数分布。间服从指数分布。1723排队系统参数 S：任务的平均服务时间任务的平均服务时间 ：任务的服务速率，任务的服务速率，=1/S Wq：平均排队时间平均排队时间 Ws：平均响应时间；平均响应时间；Ws=Wq+S ：任务的到达率任务的到达率 ：服务员利用率（服务强度），服务员利用率（服务强度），=/ns：正在服务的平均任务数正在服
12、务的平均任务数1823Lq：队列的平均长度队列的平均长度Ls：平均任务数，平均任务数，n=ns+nq；n=Rm：服务员个数服务员个数3.M/M/1排队系统的一般假设 系统为一个平衡系统；系统为一个平衡系统；连续两个到达请求的间隔时间服从指数分连续两个到达请求的间隔时间服从指数分 布，其均值为平均到达时间；布，其均值为平均到达时间；请求的个数不受限制；请求的个数不受限制；1923 队列的长度不受限制，排队规则为队列的长度不受限制，排队规则为FCFSFCFS；系统只有一个服务员。系统只有一个服务员。若M/M/1模型的到达率为，服务率为，1个服务员。根据稳定的生灭过程，有状态转换和状态方程：1n 0
13、)(0n 01110nnnPPPPP2023相关的分析结论有：相关的分析结论有：系统服务强度系统服务强度 =/系统中没有任务的概率系统中没有任务的概率 P0=1-P0=1-系统中有系统中有n n个任务的概率个任务的概率 Pn=(1-Pn=(1-)*n n ，n=0,1,2,n=0,1,2,系统中平均任务数量系统中平均任务数量 E(n)=Ls=E(n)=Ls=/(1-/(1-)队列中平均任务数队列中平均任务数 E(nE(nq q)=Lq=)=Lq=2 2/(1-/(1-)系统平均响应时间系统平均响应时间 E(R)=Ws=(1/E(R)=Ws=(1/)/(1-)/(1-)任务在队列中的平均等待时间
14、任务在队列中的平均等待时间 E(W)=Wq=E(W)=Wq=1/11.)2(.)32()1()(3232321n0nnnsnnPLnE2123 LsLsLLqs 12WsLs WqLq 四个指标的关系为四个指标的关系为(Little Little 公式公式)：系统处于空闲状态的概率：系统处于空闲状态的概率：10P 系统处于繁忙状态的概率：系统处于繁忙状态的概率：010P)N(P服服务务强强度度2223例1：一个CPU及具有n个中断源的中断系统。设CPU处理中断的时间是指数分布，平均时间为500ms(500ns)。一个中断源的两个相邻中断请求时间间隔服从指数分布，其平均值为20ms。求：最大中断
15、源的个数及在相应中断源个数的中断响应时间。解：服从指数分布，属于M/M/1队列，其响应时间有：40)1(1nTE若要保持系统平衡，若要保持系统平衡，1i，共享源增多当i，共享源减少3123 进一步处理 eMule网络中文件的共享源个数取决于文件的流行程度，以及用户的共享意愿11/10101(/)1!nninniipen /(/)!nnpen 这是一个泊松分布32232、限定系统容量、限定系统容量(M/M/1/N/FCFS(M/M/1/N/FCFS）模型应用模型应用 当系统容量最大为当系统容量最大为N N时，排队多于时，排队多于N N个的顾客将被拒绝。当个的顾客将被拒绝。当N=1N=1时，时，即
16、为瞬时制，即为瞬时制，NN时，即为容量无限制的情况。时，即为容量无限制的情况。可对应路由器，键盘等带有缓冲队列的系统分析；侧重缓冲队列可对应路由器，键盘等带有缓冲队列的系统分析；侧重缓冲队列长度对系统的影响。长度对系统的影响。排 队 系 统 服 务 台顾 客 N 4 3 2 1被 拒 绝3323状态转移方程 Nn 1-Nn )(0n 11101NNnnnPPPPPPPN N2 20 01 1 状态转移图3423 解式得：解式得：01PP022PP0PPNN NnnNnnNnnPPP000001 而等比数列而等比数列10111NnNn35231)1(20NP求排队系统顾客数的分布状况求排队系统顾
17、客数的分布状况3623 队长队长 队列长队列长 1101)1(1NNNnnsNnPL)1()1(00PLPnLsNnnq有关指标有关指标3723 逗留时间逗留时间 等待时间等待时间111Little1 100）（）（公式根据）（）或（有效到达率：NqsesseNePLPLLWPP1sqWW系统已满顾客不能系统已满顾客不能到达的概率到达的概率-损失损失率率/10eP）服务强度：（3823 有有Buf深度为深度为6，数据包等待排队，数据包等待排队，超过超过6个包就丢失，平均包到达率个包就丢失，平均包到达率3/分钟分钟，转发需时平均，转发需时平均15秒。秒。7为系统中的最大包数。为系统中的最大包数。
18、先看例：路由Buf数据包排队问题3923 数据包到达就能转发的概率到达就能转发的概率 -相当于路由中无数据包相当于路由中无数据包 待发数据包的期望值待发数据包的期望值2778.0)4/3(14/3111810NP39.1)2778.01(11.2)1(11.2)4/3(1)4/3(84/314/31)1(108811PLLNLsqNNs4023 求有效到达率求有效到达率 顾客在路由器中内逗留的期望时间顾客在路由器中内逗留的期望时间8.4373.089.2/11.2/essLW小时小时分钟分钟89.2)2778.01(41 10eeNePP）（）或（包包/分分4123 可能的数据包有百分之几不等
19、待就丢失可能的数据包有百分之几不等待就丢失 -求系统中有求系统中有7 7个数据包的概率个数据包的概率%7.3)4/3(14/31)43()/(1/1)(87877P4223例：键盘缓冲队列，缓冲队列长度15，Int 9接收键盘字符送入缓冲队列，Int 16输出进入系统。设键入字符速率符合指数分布，求其损失率若给定171616)/(1/1)(P/类似：类似：4323例：设虫孔寻径中的交叉开关（路由器）。路由器中的缓冲器，直接影响到数据片丢失。例：网站等访问的负载平衡问题4423 以机器修理模型为例，设有以机器修理模型为例，设有m台机器台机器(总体总体)，故障待修表，故障待修表示机器到达，修理工是
20、服务员。机器修好后有可能再坏，示机器到达，修理工是服务员。机器修好后有可能再坏，形成循环。虽然系统没有容量限制，但系统中的顾客也不形成循环。虽然系统没有容量限制，但系统中的顾客也不会超过会超过m，故又可写成：，故又可写成：M/M/1/mm M/M/1/m/FCFS模型可以考虑对应处理具有循环状态的模型可以考虑对应处理具有循环状态的数据处理过程。数据处理过程。4523 对于有限源应按每个顾客单独考虑，求出其有效到达率对于有限源应按每个顾客单独考虑，求出其有效到达率e。)1()(0PLmse 这样这样e是随系统内顾客数而变化的。其状态转移图为：是随系统内顾客数而变化的。其状态转移图为：设系统内顾客
21、数为设系统内顾客数为Ls，则系统外的顾客为，则系统外的顾客为m-Ls。设每个顾客的平均到达率是相同的设每个顾客的平均到达率是相同的。(这里这里的含义是单台机器在单位时间里发生故障的概率的含义是单台机器在单位时间里发生故障的概率或平均次数或平均次数)4623状态转移方程状态转移方程 mn 1-mn )()1(0n 11101mmnnnPPPnmPnmPPmP11mnnPF注意到注意到 ，4723求解状态转移方程得求解状态转移方程得m1,2,.,n )()!(!)()!(!1010PnmmPimmPnnimi有效到达率有效到达率)(seLm）（01 Pe求解顾客数概率分布求解顾客数概率分布4823
22、 等待时间等待时间 正常运转的平均设备台数正常运转的平均设备台数1sqWW)1(0PLms计算有关指标计算有关指标4923 队长队长 队列长队列长 逗留时间逗留时间)1(0PmLs)1(0PLLsq1)1(0PmWs5023设定设定：各服务台工作是相互独立的，且平均服务率相同，均为各服务台工作是相互独立的，且平均服务率相同，均为 。整个服务机构的平均服务率为：整个服务机构的平均服务率为：c c (当当n n c)c)，n n (当当n c);n c);记记 =/,s s=/c c =/c/c 为服务系统的平均利用率为服务系统的平均利用率 当当 /c c 1 1时，不会排成无限队列。时，不会排成
23、无限队列。广泛应用于多操作部件，多资源分配调度等并行系统分析广泛应用于多操作部件，多资源分配调度等并行系统分析5123 1 2 c.系统人数系统人数n n人人5223 1 2 c.系统人数系统人数n n人人n=c5323 1 2 c.服务台服务台C C个个系统人数系统人数n n人人 542301n-1nn(n+1)n+1.22n-1nccn+1.n=c 5523 状态转移方程状态转移方程 n )(cn 1 )()1(0n 111101cPcPPcPnPPnPPnnnnnn5623解差分方程，求得状态概率为解差分方程，求得状态概率为 )(!1)(!1)(11!1)(!1001100cnPcccn
24、PnPckPncnnnckck5723 顾客等候的概率顾客等候的概率 )(!1)(!1010cnPcccnPnPnnnn0)1(!)(PcPcnPsccnn计算有关指标计算有关指标 平均正接受服务的顾客数平均正接受服务的顾客数=正忙的服务台数正忙的服务台数cnncnnPcnPc10qsLL解释解释?5823 )(!1)(!1010cnPcccnPnPnnnn 队长队长 队列长队列长 逗留时间及等待时间逗留时间及等待时间qqsLLL021)1(!)()(PcPcnLssccnnqssqqLWLW ;唯一唯一5923 某售票所有三某售票所有三个窗口，顾客到达个窗口，顾客到达服从服从Poisson过
25、程，过程，到达到达 =0.9 人人/分分钟，服务钟，服务 =0.4人人/分钟。设顾客到分钟。设顾客到达后依次排成一队达后依次排成一队向空闲的窗口购票，向空闲的窗口购票，如图如图 窗口窗口1 =0.4 窗口窗口2 =0.4 窗口窗口3 =0.4 =0.96023 窗口窗口1 =0.4 窗口窗口2 =0.4 窗口窗口3 =0.4 =0.3 =0.3 =0.3 =0.9 窗口窗口1 =0.4 窗口窗口2 =0.4 窗口窗口3 =0.4 =0.96123 属于M/M/c型系统 c=3,=/=2.25,s=/c=2.25/3 1,符合要求.整个售票所空闲概率整个售票所空闲概率平均队长平均队长95.370
26、.10748.0)4/1(!34/3)25.2(23qsqLLL0748.03/25.211!325.2!25.212030nnnp6223平均等待时间和逗留时间平均等待时间和逗留时间分钟分钟39.44.0/189.1/189.19.0/70.1qsqqWWLW57.00748.04/1!3)25.2()3(3nP顾客到达后必须等待概率顾客到达后必须等待概率6323 以上例说明以上例说明,设顾设顾客到达后在每个窗口前客到达后在每个窗口前各排一队各排一队(其它条件不其它条件不变变),),共三队共三队,每队平均每队平均到达率为到达率为:3.03/9.0321 窗口窗口1 =0.4 窗口窗口2 =0
27、.4 窗口窗口3 =0.4 =0.3 =0.3 =0.3 =0.9图图 b6423 模型模型指标指标 M/M/33个个(M/M/1)P0LqLsWsWq必须等待概率必须等待概率0.07481.703.954.39(分钟分钟)1.89(分钟分钟)0.570.25(子系统子系统)2.25(子子)9.00(整整)10(分钟分钟)7.5(分钟分钟)0.75结果比较单队列好结果比较单队列好65235.若M/M/m模型将M/M/1模型的服务员修改为m个，相关的分析结论有：系统服务强度系统服务强度 =/(m/(m*)系统中没有任务的概率系统中没有任务的概率 P P0 0=系统中有系统中有n n个任务的概率个
28、任务的概率 P Pn n=11m1nnm!n)m()1(!m)m(1 mn,!mmPmn,!n)m(Pnm0n06623 队列中有顾客的概率队列中有顾客的概率 P Pe e=系统中平均任务数量系统中平均任务数量 E(n)=mE(n)=m+P+Pe e/(1-/(1-)队列中平均任务数队列中平均任务数 E(nE(nq q)=P)=Pe e/(1-/(1-)系统平均响应时间系统平均响应时间 E(R)=E(R)=队列中的平均等待时间队列中的平均等待时间 E(W)=PE(W)=Pe e/m/m(1-(1-)0mP)1(!m)m()1(mP1(1e 6723 例：例：在例在例2 2的基础上，给磁盘的基础
29、上，给磁盘I/OI/O系统增加一个系统增加一个磁盘，该磁盘是另一个磁盘的镜像，故访问可以从磁盘，该磁盘是另一个磁盘的镜像，故访问可以从任意一个磁盘上得到数据。假定对磁盘的任意一个磁盘上得到数据。假定对磁盘的I/OI/O操作均操作均为读操作，重新计算。为读操作，重新计算。解解 使用两个磁盘，该系统为使用两个磁盘，该系统为M/M/2M/M/2系统。系统。磁盘磁盘I/OI/O请求的到达率请求的到达率 =40(=40(个个/s)/s)完成完成I/OI/O请求的服务率请求的服务率 =1/0.02=50(=1/0.02=50(个个/s)/s)磁盘的平均利用率磁盘的平均利用率 =(=(/)/2=0.4)/2
30、=0.4 6823该系统可以用该系统可以用M/M/mM/M/m排队模型的结论：排队模型的结论：系统中没有任务的概率系统中没有任务的概率 P P0 0=395.08.0533.01!n)2()1(!2)2(1 1111nn2 队列中有顾客的概率队列中有顾客的概率 P Pe e=229.0395.0)4.01(!2)4.02(P)1(!2)2(202 6923平均等待时间平均等待时间 E(W)=PE(W)=Pe e/m/m(1-(1-)=0.229/2 =0.229/25050(1-0.4)=0.0038(1-0.4)=0.0038平均响应时间平均响应时间 =平均等待时间平均等待时间+平均服务时间
31、平均服务时间 =0.02+0.0038=0.0238(s)=0.02+0.0038=0.0238(s)两个慢速磁盘的等待时间是两个慢速磁盘的等待时间是1 1个慢速硬盘的个慢速硬盘的1/211/21，是，是1 1个快速硬盘的等待时间的个快速硬盘的等待时间的1/1.761/1.76。7023设有一个信息交换中心，信息流为泊松流，每分钟到达240份，线路输出率为每秒800个字符，信息长度（包括控制字符）近似负指数分布，平均长度176个字符。要使在任何瞬间缓冲器充满的概率不超过0.005，问缓冲器的容量K至少应取多大？7123信息平均到达率信息平均到达率 240份份/分分4份份/秒，秒，800/176
32、 800/176 4.5464.546份份/秒，秒，/0.880.88。按。按M/M/1/KM/M/1/K系统处理，缓冲器充满的概率系统处理，缓冲器充满的概率p pK K应满足应满足005.01)1(1kKkp计算有：计算有：p p25250.0090450.009045，p p26260.0044640.004464。所以所以K26K26，即缓冲器的容量至少应为，即缓冲器的容量至少应为2626个单位。个单位。7223设某计算机有设某计算机有4 4个终端，用户按泊松流到达，平均个终端，用户按泊松流到达，平均每每1010分钟到达分钟到达1.51.5个用户。假定每个用户平均用机个用户。假定每个用户
33、平均用机时间为时间为2020分钟，用机时间服从负指数分布，如果分钟，用机时间服从负指数分布，如果4 4个终端被占用，则用户到其它计算机处接受服务，个终端被占用，则用户到其它计算机处接受服务，求此系统的各项指标。求此系统的各项指标。7323这是这是M/M/4/4损失制系统，损失制系统，9（人（人/小时），小时），3 3（人（人/小时）小时）,/3 3。235.0)!43!33!2331(!43p43244 顾客损失的概率为：顾客损失的概率为：单位时间内实际进入系统的平均顾客数为：单位时间内实际进入系统的平均顾客数为：)/(885.6)235.01(9)p1(4e小时小时人人 平均忙的终端数为：平
34、均忙的终端数为：)(295.2)235.01(3)p1(N4c个个 74232、M/M/c/K混合制：混合制：一种混合制排队系统，系统中有一种混合制排队系统，系统中有K K个位置，个位置，c c个服务台独立并行服务，个服务台独立并行服务，ccK K。当。当K K个位置已被顾个位置已被顾客占用时，新到的顾客就自动离开，当系统中有空客占用时，新到的顾客就自动离开，当系统中有空位置时，新到的顾客就进入系统排队等待服务。位置时，新到的顾客就进入系统排队等待服务。7523v 顾客到达为参数(0)的泊松过程；v 每个顾客所需的服务时间独立、服从参数为(0)的负指数分布，且到达过程与服务过程彼此独立；v 容
35、量为K，即系统中有K个位置；v 系统中有c个服务台独立地平行工作，cK；v 当K个位置已被顾客占用时，新到的顾客就自动离开，当系统中有空位置时，新到的顾客就进入系统排队等待服务。7623平均等待时间为：在统计平衡下，在统计平衡下，进入系统接受服务的进入系统接受服务的顾客的等顾客的等待时间分布函数为：待时间分布函数为：0,)!()(0,PWq(t)W011010qtdxecjxccqqtqttxccjkcjjcjjcjj 1Kcjjqqc1cjW平均响应时间为：1WWq7723例3、磁盘阵列的预取分析：7823 这是一个带有Cache的磁盘阵列的性能分析。I/O请求经过Cache 管理平滑输入速
36、率。对应Cache的性能分析包括：cache读、Cache写、读命中率、Cache的满替换等，影响到Cache的服务响应。可应用M/M/1模型 对应磁盘阵列，具有磁盘的读写等响应，可采用M/M/C模型。由于经过Cache，到达磁盘的速率不是负指数分布，实际可采用M/G/C模型或多个M/G/1模型。类似前端带有缓冲，后端带有负载平衡过程的系统都可以以此进行分析。7923例4：网络并行系统的互连路由存储转发，对于到达的数据包经过队列缓冲，按照优先权进行转发。经过统计，网络中包的到达速率符合泊松分布，对于包的大小一致，处理过程简单，符合一般分布，采用M/G/1/PS这里需要考虑优先级的问题。8023
37、例5：目前多核结构CMP 采用共享二级Cache的CMP结构，即每个核拥有私有的一级Cache，且所有处理器核共享二级Cache。基于总线的Cache一致性带来总线的压力。由于一级私有Cache的的命中率和一致性以及一致性协议都会影响到总线的性能。利用M/M/1模型可以分析总线的响应。但对总线的访问请求率等都需要另外分析。Hydra多核结构多核结构8123例6：Web服务与调度策略1.静态调度静态资源 对应不同的应用，Web请求的速率分布不同；服务的响应因素：CPU时间，网络时间等2.动态调度动态资源（如程序，轮循的时间片等）服务的响应受到多种因素的影响8223例7：可靠性分析平均无故障时间，
38、修复时间，冗余对可靠性的影响8323例：并行系统的资源分配和调度 属于动态资源的调度 资源的可用性 路径延迟的影响8423三、排队模型分析小结三、排队模型分析小结1 1、传统排队模型的应用，该系统主要设定：、传统排队模型的应用，该系统主要设定：输入为泊松过程；输入为泊松过程；服务时间为负指数分布服务时间为负指数分布在这种系统中，到达和服务具有无后效性，可用生在这种系统中，到达和服务具有无后效性，可用生灭过程灭过程(或称生死过程或称生死过程)描述。描述。对于此类的应用分析，可以使用标准的状态方程式对于此类的应用分析，可以使用标准的状态方程式进行计算；进行计算；对于其他输入和服务的概率分布，仍具有
39、无后效性，对于其他输入和服务的概率分布，仍具有无后效性，能采用生灭过程描述（稳定系统），可以按照概率分能采用生灭过程描述（稳定系统），可以按照概率分布计算布计算85232、排队模型的应用1）经典排队模型的应用：根据实际应用计算，值，代入模型，计算响应时间等2）根据实际情况，排队模型的6个参数的综合应用3）分析研究新的概率分布在排队模型的应用4）对于复杂系统分别应用排队模型，综合分析86233、排队模型分析的扩展、排队模型分析的扩展若输入或服务不再具有无后效性时，不能直接应用若输入或服务不再具有无后效性时，不能直接应用生灭过程理论求解。可以寻求扩展或转换的其他方生灭过程理论求解。可以寻求扩展或转
40、换的其他方式解决。式解决。扩大状态空间法：扩大状态空间法：可以采用补充变量，用扩大状态空间的方法将非马尔柯夫过可以采用补充变量，用扩大状态空间的方法将非马尔柯夫过程的排队化成一个状态空间为多维的马尔柯夫过程求解。这程的排队化成一个状态空间为多维的马尔柯夫过程求解。这类方法统称为扩大状态空间法。处理类方法统称为扩大状态空间法。处理M/Er/1/M/Er/1/和和Er/M/1/Er/M/1/等排队系统便可以采用这种方法。我们经常提到的相位法属等排队系统便可以采用这种方法。我们经常提到的相位法属于此类方法。于此类方法。8723近似逼近法近似逼近法对于更一般的排队系统，如对于更一般的排队系统，如G/G
41、/1G/G/1排队系统，其队长变化过程排队系统，其队长变化过程是一般的随机过程。这时，要求出平稳分布极为困难。可采用是一般的随机过程。这时，要求出平稳分布极为困难。可采用积分微分方程法近似求解。不等式定界法近年来也用于分析一积分微分方程法近似求解。不等式定界法近年来也用于分析一般的排队系统，可将之看作近似逼近法的一种。另外的近似逼般的排队系统，可将之看作近似逼近法的一种。另外的近似逼近法包括系统逼近法和过程逼近法。流体流方法就是一种过程近法包括系统逼近法和过程逼近法。流体流方法就是一种过程逼近法。逼近法。8823马氏马氏当一个排队系统的服务过程不是马尔柯夫过程，但到达或服当一个排队系统的服务过程不是马尔柯夫过程，但到达或服务二者之间有一个具有无后效性时，往往可以采用嵌入马氏务二者之间有一个具有无后效性时，往往可以采用嵌入马氏链法。当可以用半马氏过程描述排队队长变化过程，或输入链法。当可以用半马氏过程描述排队队长变化过程，或输入过程过程(或服务时间或服务时间)本身即为一个半马氏过程时，或可嵌入一本身即为一个半马氏过程时，或可嵌入一个半马氏过程时，往往采用半马尔柯夫个半马氏过程时，往往采用半马尔柯夫(Semi-Markov)(Semi-Markov)理论理论对这类系统进行分析。这种方法称为半马氏分析法。对这类系统进行分析。这种方法称为半马氏分析法。
