排队论及其应用浅析.pdf

排队论及其应用浅析.pdf

ID:48055697

大小:1.90 MB

页数:70页

时间:2019-10-08

排队论及其应用浅析.pdf_第1页
排队论及其应用浅析.pdf_第2页
排队论及其应用浅析.pdf_第3页
排队论及其应用浅析.pdf_第4页
排队论及其应用浅析.pdf_第5页
资源描述:

《排队论及其应用浅析.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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。