排队论及其应用浅析.pdf

《排队论及其应用浅析.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、排队论及其应用浅析——QueueingTheory网易杭研：何登成新浪微博：何_登成H1391大纲(一)•排队–现实生活中–计算机领域•排队论浅析–排队论问题分析–OperationalLaw•UtilizationLaw•Little’sLaw–D.G.Kendall–Little’sLaw–Erlang’sFormula大纲(二)•排队论应用分析–更好的理解系统监控•LinuxI/OStats–更好的架构选型–排队论与Performance•什么是Performance？•何谓平衡的系统？•如何监控系统？•如何进行高性能程序设计？–容量规划（入门）排队问题•在排队过

2、程中，人们会关心哪些问题？–什么时候过去，排队的时间会比较短？–不排队的话，需要多少时间？–是否需要排队？–(不)包括正在被服务的人，我前面一共还有几人？–排到我需要多少时间？等我服务结束，又需要多少时间？–这次排队是否合算？–队伍长队达到什么程度，我就会放弃本次排队？–系统有多少个窗口？是否已经高负荷运转了？•无论是现实中的排队，电话通讯领域的排队，还是计算机领域的排队，最后都能够抽象化为一个经典的理论——排队论(QueuingTheory)。•排队论起源于20世纪初的电话通话。1909—1920年丹麦数学家、电气工程师爱尔兰（A.K.Erlang）用概率论方法研究电

3、话通话问题，从而开创了这门应用数学学科，并为这门学科建立许多基本原则...•Erlang在电话通讯领域，解决了两个基本问题：电话损失率(Erlang-BFormula)，电话等待概率(Erlang-CFormula)。在介绍这些之前，让我们先来认识D.G.Kendall与J.D.C.Little...QueueingTheory•排队论用于解决什么问题？–核心问题•对用户来说：响应时间(满意度)•对服务提供者来说：利用率(成本)•在保障用户满意度的前提下，最大限度的控制成本，充分挖掘系统的潜力。QueueingTheory(形式化)•什么时候过去，排队的时间会比较短？–

4、达到请求的分布；单位时间平均到达请求数量：•不排队的话，需要多少时间？–服务时间(ServiceTime)；单位时间平均完成的服务数量：•是否需要排队？•(不)包括正在被服务的人，我前面一共还有几人？–平均队列长度L(不包括正在服务的人：L)q•排到我需要多少时间？等我服务结束，又需要多少时间？–WaitTimeWvsReponseTimeWorRq•队伍长队达到什么程度，我就会放弃本次排队？–服务丢失率：PB；队列最大长度；•系统有多少个窗口？是否已经高负荷运转了？–窗口数量；利用率U；UtilizationLaw•UtilizationLawU/•排队系统

5、中，Server的利用率，为平均到达速率与平均服务速率的比值；–UtilizationLaw解读•保持Server的平均服务速率不变，平均到达速率越高->Server利用率越高；•保持平均到达速率不变，Server的平均服务速率越高->Server利用率越低；–一个简单的证明(求下面这个系统的利用率)Little’sLaw•Little’sLawLW•排队系统中，队列长度(包括正在接受服务的人)=到达率*平均响应时间•由J.D.C.Little在1961年的论文【AProoffortheQueuingFormulaL=λW】中给出形式化的证明；•证明：略1•变种：L

6、qWq排队长度=到达率*平均等待时间（WqW）–Little’sLaw解读•Little’sLaw/UtilizationLaw，均属于OperationalLaws中的一种；•平均响应时间越长，队列长度也越长；•单位时间到达的请求越多，队列长度越长；•符合日常的理解；•平均请求数量，已知L,Lq,W,W中的任何一个，都可以计算出另外三个；Little’sLaw（续）•Little’sLaw的应用场景–最基础的Law，对请求到达/离开的分布没有特殊要求；–超市、银行、KFC等管理•SixSigma（六西格玛管理法）–系统性能监控–...Little’sLaw

7、（例1）•一个小酒馆，客户平均访问频率为40人/小时；–客户在小酒馆的平均消费时间是15分钟；•问题：请问小酒馆的平均客户数量是多少？•解答：–：40人/小时–W：0.25小时/人–LW：40*0.25=10Little’sLaw（例2）•一证券经纪公司，其网站有110万注册用户。高峰期，同时有20000用户在线。同时观察到，在高峰期网站一小时处理360万笔业务。•问题：请问处理每笔业务的响应时间是多少？•解答：–：3600000/3600=1000笔/秒–L：20000–WL/：20000/1000笔/秒=20秒/笔Litt