（计算机应用技术专业论文）基于多通道等待排队算法的高校选课系统的资源最优化分析.pdf

硕士学位论文摘要 摘要 在学分制高校中，选课是学校教学管理的不可缺少的重要一环。 选课的顺利实施，对于学校的决策者和管理者以及学生来说都至关 重要，所以高校选课系统应该能够高效、顺利地解决学分制，特别 是完全学分制高校的选课问题，选课系统需要面临的主要问题，不 是系统的开发难度，而是服务器以及网络资源的最优化。 本文在综合考虑以往选课系统中主要应用的算法的基础上，以 概率动态分布为基础，用运筹学中的排队算法为依据提出了基于高 校选课系统的资源最优化分析的多通道等待排队算法；文中对排队 论的概念进行了解释，对排队论的模型进行了研究，并重点阐述了 选课模型的建立过程，对效率指标进行了计算和分析，与单道等待 排队系统的效率指标进行了比较，以切实有力的数据证明了多通道 等待排队算法的高效和实用性。本文同时给出了多通道等待排队算 法的选课系统实现，该系统采用d e l p h i 语言开发的数据分析模块， 用m s n e t + s q l s e r v e r 开发网络上选课系统，并实现多服务器负载均 衡；提高开发速度、降低开发成本、增加系统灵活性、降低软件维 护费用；满足学生选课所需要的大量的各种类型的数据处理，促进 学院完全学分制教务系统的顺利实施。 本文最后对算法实现过程中的研究与开发工作进行了总结，并 阐述了将来进一步对该系统进行扩充与完善的一些工作。 关键词排队算法，多通道，选课，最优化 a bs t r a c t i nt h ec r e d i ts y s t e mu n i v e r s i t i e s ，c o u r s e s e l e c t i o ni s av e r y i m p o r t a n tp a r ti nt h et e a c h i n gm a n a g e m e n t s o ，t h es y s t e ms h o u l df i r s t l y s o l v et h ec o u r s e s e l e c t i o np r o b l e m ，e s p e c i a l l yi nt h ee n t i r e l y c r e d i t s y s t e m t h ep r i m a r yp r o b l e mo ft h es y s t e mi sn o tt h ed e v e l o p m e n t d i f f i c u l t y , b u tt h er e s o u r c eo p t i m i z a t i o n t h i st h e s i sp r e s e n t sam u l t i - c h a n n e lq u e u i n g a l g o r i t h mb a s e do n p r o b a b i l i t yd y n a m i cd i s t r i b u t i n gf o rs e r v e rr e s o u r s eo p t i m i z a t i o n ，w i t h c o m p a r i n gt h em e t h o d su s e di np r e v i o u ss y s t e m s w i t ht h i sa l g o r i t h m t h et h e s i s p r e s e n t s ac o u r s e - s e l e c t i o n m o d e l ，a n df o c u s e so nt h e e s t a b l i s h m e n to ft h em o d e l ，c a l c u l a t i o na n da n a l y s i st h ee f f i c i e n c yo f t h e m o d e lw i t ht h ec o n c e p t i o no fq u e u e i n gt h e o r ya n dq u e u e i n gm o d e l t h et h e s i sa l s oc o m p a r e sw i t ht h ee f f i c i e n c yo f s i n g l e - c h a n n e lq u e u i n g a l g o r i t h m ，t h er e s u l t s s h o wt h e f e a s i b i l i t ya n dt h ee f f i c i e n c yo f m u l t i c h a n n e lq u e u i n ga l g o r i t h m t h et h e s i s d e v e l o p saw e bc o u r s e s e l e c t i o ns y s t e mb yd e l p h i ， m s n e t + s q ls e r v e rb yt h i sa l g o r i t h m t h es y s t e mg e t ss e v e r a l a d v a n t a g e sa sl o a d b a l a n c e d ，l o w e rd e v e l o p i n gt i m ea n dc o s t ，f l e x i b i l i t y , l o w e rm a i n t e n a n c ef a r e ，d a t ap r o c e s s i n ge f f i c a c i o u s l ya n dh e l p i n gt h e d e v e l o p m e n tf o rt h ec r e d i ts y s t e mi nu n i v e r s i t i e s f i n a l l y , t h et h e s i ss u m u r i z e st h ew o r kd u r i n gt h es y s t e md e s i g na n d d e v e l o p m e n t ，a n dd i s c u s s e sh o wt oi m p r o v et 1 1 ep l a t f o r mi nt h ef u t u r e k e y w o r d s ：q u e u i n ga r i t h m e t i c ，m u l t i c h a n n e l ，c o u r s e s e l e c t i o n ， o p t i m i z a t i o n 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他入已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：零；羔日期：掣一年旦月鲨日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论 文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文； 学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：狂导师签名邋日期：阜年月乒日 硕士学位论文第一章绪论 第一章绪论弟一早三百下匕 随着我国教育体制的发展，高校中采用完全学分制的院校越来越多，在学 分制高校中，选课是学校教学活动的不可缺少的重要一环。选课的顺利实施， 对学校的决策者和管理者以及学生来说都至关重要，所以高校选课系统应该能 够高效、顺利地解决学分制。特别是完全学分制高校，选课系统需要面临的问 题，不是系统的开发难度，而是服务器以及网络资源的最优化。 大多数的学分制或完全学分制院校，所上的课程全部由学生自主选定，而 学生感兴趣的课程和上课时间出现大量的冲突，学生在网上选课开放的时间内， 由于大量同时登录系统，造成系统服务器的资源极度紧张，从而导致有的学生 几个小时都无法登录系统，造成选课极不顺利。 为解决学生网上选课期间系统服务器负荷严重超载的问题，适当地增加系 统服务器的数量，但是如果盲目增加服务器，势必会造成投资方的成本增加， 甚至出现因供大于求而使设施经常闲置，导致浪费，因此需要一个合理的算法， 通过分析处理系统的状况，对系统进行调整和改进，以确定最优的服务器数量， 使服务器质量的提高和成本的降低之间取得平衡，找到最适当的解决方法，使 系统处于最优的运行状态。 由于在单位时间内，学生随机向服务器发出服务请求，并且学生选课满足 下列情况： ( 1 ) 当时间间隔取得极短时，只能有0 个或1 个请求失败发生； ( 2 ) 出现一次请求失败的概率大小与时间间隔大小成正比，而与从哪个时 刻开始算起无关； ( 3 ) 各段时间出现请求失败与否，是相互独立的。 对照泊松公布的定义，我们可知实际上学生对选课服务器的请求密度满足 泊松分布，因此我们确定学生到达流为泊松流。 本文根据柯尔莫可洛夫方程n 们的一般法测计算系统的损失概率、相对通过 能力、绝对通过能力口1 和学生的平均排队时间和占用服务器的平均资源，以获 得系统的效率指标，从而现实对系统资源的最大优化，以保证选课系统的顺利 进行。 1 1 课题的研究背景 信息时代，信息技术在高等教育领域起着重要作用。一个突出的表现是， 硕士学位论文 第一章绪论 网络成为高校学习资源不可或缺的载体，起着越来越重要作用，随着高校教学 和管理平台建设的不断深入，网络逐渐承担起教室、教材、教师、管理者等多 项职能而成为高校学习系统的要素之一，基于网络的选课系统即是其中应用最 广泛的部分。 高等教育必须体现时代内容和要求，高校的学习系统必须反映信息时代高 等教育的基本特征，这也是对构建信息时代高校网络选课系统的总体要求。 选课最显著的特征是让学生根据个人智力、兴趣、经济状况等，在课程组合、 学习进度等方面享有一定的自由度和弹性，由被动转为主动，从个性压抑向个性 发展的观念转变，使教育从共性教育向个性教育发展。选课制允许学生在一定的 范隔和程度上自主选择教育教学手段。要充分发挥选课制的优点，就必须最大限 度地扩大学生自主选择的空间，让学生自主选择专业、课程、任课教师、授课时 间和受教育方式等，满足不同的需要和兴趣，发挥个人潜能，同时还必须提供大 量的选修课程以供选择。因此，只有建立在充分选择机会之上的选课制，才能充 分体现其优越性。 现有网络选课系统主要利用i n t e r n e t 的w e b 服务器作为前台用户( 学生) 与数据库服务器交互的中介。通过w e b 服务器将学生的选课请求提交给数据库 服务器，并将数据库服务器的处理结果以w e b 网页的形式返回给用户。基于这 种选课模式，结合具有信息交互能力的动态网页技术，可以基本满足学生的际 选课要求。 然而无论是系统早期设计时普遍采用的“两层体系结构”，还是近年来技术 专家纷纷提倡的“三层体系结构 ，都没有从根本上改变研究生选课系统的总体 格局和功能模块，从而不可避免地遭遇以下问题： 情景单一。现有的网络选课系统，尽管使用了具有信息交互能力的动态网 页技术，仍有一个共同的缺点，就是显示的内容和格式千篇一律，学生只有选 择的权利而没有定制信息的权利。 信息孤立。受传统计算机技术的限制，现有系统往往只注重满足自身的功 能需要，没有与其他部门的信息和其他功能模块进行无缝接i ：l ，从而导致信 息孤立，使用者只能访问和使用本模块的相关数据。 交互方式单调。现代社会日益注重人与人之间的交流和沟通，而现有系统 缺乏的正是这一点。课件制作、网上论坛等一定程度上弥补了师生课余交流机 会的匮乏，但离实际需要仍相去甚远。使用者缺乏自主性，由于信息推送的方 式受系统固有模式的限制，使用者只能根据系统的提示做出相应选择，被动接 受系统提供的信息，无法自主挑选和过滤信息。 利用效率低下。受管理部门职能的限制，现有系统的功能以满足选课需要 2 硕士学位论文第一章绪论 为主，使用具有阶段性，因而往往会在学期初形成高峰，甚至导致网络拥塞， 其他时间却使资源处于闲置状态，使用方式受限。 在现有系统上实现网络选课，第一必须在电脑上操作；第二所用设备必须 与校网相连，这两个条件缺一不可。而事实上，网络资源的载体己远不止校网 和p c 机。 1 2 研究现状 近年来各院校都在大力采用网上选课方法，极大地改进了高校的教学管理， 但是大多数开展网上选课的高校，都有选课时资源和顾客( 学生) 之间无法协调 的问题，造成学生抱怨选课系统承受力有限，无法顺利选课。因此各院校开始研 究排队模型以解决选课过程中的服务器和学生人数过大的矛盾问题，目前传统采 用的排队模型和算法，多为服务器数量为1 的单通道损失制系统的排队模型，或 单通道等待制系统的排队算法。目前单通道的排队1 2 4 】算法可用图1 1 来表示： 不进入系统 离开队列 图1 - 1 单通道排队的一般模式 排队的规则有损失制、等待制和混合制，等顾客( 学生到达时，若所有服务 器均被占用，该顾客离去，这种排队规则称为损失制或即时制。这种情况在选课 时出现机会不大，因为大多数心急如焚的学生会选择长时间地等待，甚至通宵达 旦地选课；当顾客到达时，若所有服务器被占用，顾客并不离去，而是排队等待 服务，这种排队规则称为等待制。而将二者进行结合则称为混合制。而在这三种 规则中，当服务器的数量为1 ( 单一服务器系统) 时，称为单通道损失制或单通道 等待制，目前国内外大多数以此种方式来处理选课的排队问题，这种传统的方法 在一定程度上缓解了选课的压力，当学生人数过多时，采取限制学生人数的方法， 以保证单一的服务器能正常运作。但是随着近期的扩招，高校在校人数近几年激 增，单一的服务器的选课系统已经无法满足日渐增加的选课学生人数，造成选课 系统效率低下，甚至几近瘫痪。 硕士学位论文 第一章绪论 多通道的排队机制则采用多台服务器并行处理选课请求，由于近几年硬件 价格的下调，使一般高校购入多台服务器成为可能，以多购入一台服务器便可 大大减少等待的学生时间，和等待的人数上说，是符合选课系统的效益的，但 是无节制的增加服务器也是不符合经济效益的，因为毕竟选课只是高校管理中 一个短暂的过程，大多数时间内让太多的服务器闲置，势必会引起投资方的不 满，也是对资源的浪费，因此在保证学生不因服务器过忙而失去信心离开的情 况下，采用等待机制，而不是损失制的排队模式，并且采用多服务器的多通道 等待排队机制，是解决目前高校选课系统中资源和请求人数的冲突的瓶颈的最 好方法。 1 3 研究目标 ( 1 ) 研究基本于多服务器排队模型和数学规划，提出在资源数量和资金、 用户人数等多种约束情况下精确的资源配置优化方法。 ( 2 ) 通过本项目的研究，算出校园网的服务系统的主要服务指标，分析校 园网服务系统的使用效率，以便进行相应的调整。 ( 3 ) 为了使选课系统便于扩展，将多通道等待排队算法很方便地引入到选课 系统中，并能对比提供算法的优劣；同时可以与i n t e r n e t 上实现学生选课的资 资最优化，并解决教务管理系统的其他资源分配问题。 ( 4 ) 针对多通道等待排队算选课系统的工作量，沿用已有的开发模式，使 系统能够具备良好的性能，以及有效的利用相应的软件来实现多通道等待排队 算选课系统，并将硬件资料与软件系统较完美地整合，以便将系统的性能发挥到 最佳状态。 1 4 基于高校选课系统的多通道等待排队算法的提出 随着我校学分制改革的不断深入，选课系统的功能正逐步完善。同时选课 的学生人数和课程数据等也急剧增加，选课系统的负载成倍增长，系统的稳定 性受到严峻挑战，对选课系统负载平衡进行研究势在必行。 针对以上问题，本文利用运筹学1 中的排队论乜1 理论，根据所在学校的实 际情况，设计并实现了多通道的排队机制的选课系统，降低开发成本、增加系 统灵活性、提高各服务器的运行效率，并使学生的选课能顺利完成，为本校实行 完全学分制的教务管理系统提供了技术上的支持。 多通道的排队1 机制采用多台服务器并行处理选课请求，由于近几年硬件 价格的下调，使一般高校购入多台服务器成为可能，以多购入一台服务器便可 4 硕士学位论文第一章绪论 大大减少等待的学生时间，和等待的人数上说，是符合选课系统的效益的，但 是无节制的增加服务器也是不符合经济效益的，因为毕竟选课只是高校管理中 一个短暂的过程，大多数时间内让太多的服务器闲置，势必会引起投资方的不 满，也是对资源的浪费，因此在保证学生不因服务器过忙而失去信心离开的情 况下，采用等待机制，而不是损失制的排队模式，并且采用多服务器的多通道 等待排队机制。 采用这种算法的选课系统，是解决目前高校选课系统中资源和请求人数的 冲突的瓶颈的最好方法。通过对排队系统的输入过程、排队、服务规则和服务 机构的研究，为避免服务机构的资源耗尽和顾客的排队等待时间过长，通过柯 尔莫可洛夫方程的一般法则，建立多通道等待排队系统，把排队的时间控制到 一定的限度内，在服务质量的提高和成本上升的降低之间取得平衡，以取得最 优化的解。 选定学生和服务器以及服务规则( 选课操作) 作为研究对象，设系统的学 生到达流为泊松流( 每次随机出现的顾客个数) ，其强度为入，系统内有n 个服 务器，并且服务器具有相同的服务时间服从指数分布，其强度为u 。当学生选 课时，如果服务器忙，学生排队等待服务，一直等到有服务器有空闲并为他服 务为止。 针对以上问题，我们利用生灭图口1 和建立柯尔莫可洛夫方程的一般法则， 设计并实现了基于排队系统对服务器效率的分析处理调整选课服务器，并结合 负载均衡工具优化选课服务。成功的对服务器效率进行分析处理，以计算最优 化的服务器脾副数量，能够实现对选课系统的服务器负载进行最优化处理。系统 采用d e l p h i 语言开发的数据分析模块，用m s n e t + s q l s e r v e r 开发网络上选课 系统，并实现多服务器负载均衡。提高开发速度、降低开发成本、增加系统灵 活性、降低软件维护费用。满足学生选课所需要的大量的各种类型的数据处理， 促进学院完全学分制教务系统的顺利实施。 1 5 论文的组织 论文全文共分七章： 第一章绪论。这一章主要介绍课题的研究背景、研究现状和研究目标，并 阐述了基于排队技术的选课系统的必要性及其重要意义。 第二章系统的总体设计主要介绍系统的体系结构，系统的运行环境，和 各选课系统模块结构。 第三章多通道等待排队算法的数学模型。这一章主要介绍排队算法的原 理，以及运用排队算法在选课系统中的根据，依据原理而创建的选课系统中多 5 硕士学位论文第章绪论 通道等待排队算法的数学模型。 第四章多通道等待排队算法的效率分析。这一章主要介绍两个内容，一个 是多通道等待排队算法的效率指标，一个是多通道等待排队算法的效率与其他 算法效率的比较，从分析中看出多通道等待排队算法的效率高。 第五章基于多通道等待排队算法的选课系统。这一章以系统实现的基于多 通道等待排队算法的选课系统为例，说明利用该算法开发系统的基本步骤。 第六章系统运行与关键技术与评价。这一章讲述系统运行的实现和相关的 功能说明，和系统的评价。 第七章结束语。 6 硕士学位论文第二章系统的总体设计 第二章系统的总体设计 随着我校学分制改革的不断深入，选课系统的功能正逐步完善。同时选课 的学生人数和课程数据等也急剧增加，选课系统的负载成倍增长，系统的稳定 性受到严峻挑战，对选课系统负载的优化势在必行。针对这些问题，我们提出 了多通道等待排队算法实现对系统效率的最优化处理，把排队的时间控制到一 定的限度内，在服务质量的提高和成本上升的降低之间取得平衡，以取得最优 化的选课效果。 多通道等待排队算法是应用于选课系统之上的，本章旨在介绍算法之前， 先阐述该系统的主要结构以及主要功能模块，在通过了解整个框架之后，更进 一步地理解该算法的重要性和有效性 2 1 系统的体系结构 浏览器j 蠢蒌孽蓦 厂、 厂、 蕞优化分 k 服务器 l 学生j 析 | 一 ， ( 学生一二 厂、 ir 、 卜 l 学生j 卜 服务器 、l j 覆嫠均衡、 r 学生一1 1 lj f s 时，有i a 俨- s g 。因此，学生相继到达的平均时 间间隔为1 2 ，平均服务时间为j 伍，令p 利s t t ，则p 为系统的服务强度( 其 中s 为系统中并行的服务器数) 。 3 2 2 选课系统中排队服务的忙期的推导 由前面所述，衡量一个排队系统工作状况的主要指标有： ( 1 ) 系统中平均学生数( l ) 或平均队长( l q ) 。这是学生和服务机构都 关心的指标，在设计排队服务系统时也很重要，因为它涉及到系统需要的空间 的大小。 ( 2 ) 学生从进入到服务完毕离去的平均逗留时间w ( 或学生排队等待服 务的平均等待时间w q ) 。每个学生都希望这段时间越短越好。 1 9 硕士学位论文第三章多通道等待排队算法的数学模型 ( 3 ) 忙期和闲期。忙期定义为从学生到达空闲服务机构开始到服务机构再 一次变成空闲状态为止的时间。它是衡量服务机构工作强度和利用效率的指标。 与忙期相对的是闲期，闲期为服务机构空闲的时间长度，在服务过程中，忙期 和闲期是相互交替出现的。 上述指标实际上是反映了排队服务系统工作状态的几个侧面，是互相联系、 互相转换的，设以九表示单位时间内学生的平均到达数，“表示单位时间内被 服务完毕离去的平均学生数，则1 舰表示相邻两个学生到达的平均间隔时间， j 伍表示对每个学生的平均服务时间，有： = 兄形或形= 专，厶= 名或= 鲁，矽= + 石i 称三= 2 w 和乙= 五为l i t t l e 公式。 将前两式代入最后一式得到 = + 兰 ( 3 1 ) 又由于 三= 圮，厶= ( n - s ) p ( 3 - 2 ) 因此只要求得p n 韵值就可以得l ，l q ，w 和w q ，当n = 0 时，p n 的值即 为p o ，当s = l 时，( 1 - p o ) 即是服务系统的忙期。 以下是关于忙期的推导： 主要结果：对于排队系统m m ，当r - - - - c o ，p i 时，其平均忙期为 e ( b ) ：三( ! 1 ) 证明：因为e ( b ) 5 缈1 2 喜p i 2 丽1 喜塑等三等 5 i 1 j 石- i 其中j io ： 1 + 罗k o k l k i - 1 ，当系统状态状态空间为有限时，上述的求 智p 1 p i 和上限应换为有限正整数。 由此公式，我们应用于等待制排队系统m m n ，因为 入j = 入，j = o ，l ，2 ，i i = jp ，j = l ，2 ， 硕士学位论文 第三章多通道等待排队算法的数学模型 腓c 窆i = 0 等+ 端r 一去 1 。厶 j !n ! ( 1 - p ) 。n p n - i 所以，e ( b ) = y j - j j 毫o学+ 端n l ( 1 训，j ! 一p ) 一 特别对于n = 1 的系统m m 1 ，有e ( b ) ：e ( a ) ：1 _ ， 一九 e ( b + 1 ) = 士 ( 3 3 ) m “- 柚 。 由此我们推导出多通道等待制排队系统的忙期公式，以便计算在选课系统 运行过程中，服务器的承受情况及忙期的推导。 3 2 3 选课系统数量指标的统计推断和系统平稳状态的概率分布 当系统运行一定时间达到平稳状态后，对任一个状态n 来说，单位时间内 进入该状态的平均次数和单位时间内离开该状态的平均次数应相等，即系统在 统计平衡下“流人：流出 。据此，可得任一状态下的平衡方程如下： 0 ：l p l = 九p o 1 ：t o p o + 2 p 2 = “+ l 加l 2 ： p l + 9 3 p 32 协+ 2 k 叫) r 一l ：以一2 p 。一2 + 。p 月= o k l + z 。一l 切。 疗：以一1 p 。一1 + 月+ l p h + i = + 。扫。 由上述平衡方程，可求得： 0 ：p l = 竺p o l 一 1 ：p ：量p 。+ 上0 。p 。一l o p o ) ：量p ，：丛p 。 22,u22 1 2 ：岛：争”o ： p 。) ：互p ：型血风 33,u3,u3a2,ul 。 川：p 。：争m + 陬。一2 - 2 p - 2 ) ：鱼阼。：世风 。 。一i , u 。l 。 刀：p 剃：量p 。+ 上缸。见一2 。- i p - i ) ：生以：盟p 。 j u r + 1p n + 1p r 。ip n “p n p 、? 2 i 硕士学位论文 第三章多通道等待排队算法的数学模型 记：已：互堑丛 n - 1 , 2 ， n j 一1 ” j l 则平稳状态的分布为： 只= c 。只 n = l ，2 ，一 由概率分布的要求：= 1 有：i l l + n = o q j 只1j 于是：昂： l + g n = l ( 3 5 ) ( 3 6 ) ( 3 7 ) 注意：公式( 3 7 ) 只有当级数g 收敛时才有意义，即当g f + 竹i r 刁= 1 一凇 & ) = l e 舛剧= 肚+ 舡) 没有顾客离去的概率为1 一i lt 一旬( t ) 。 ( 3 ) 多于一个顾客到达或离去的概率为o ( a t ) ，可以忽略。因此，在t + t 时刻，系统中有n 个顾客的概率p ( t 十t ) 满足： e o ( t + a t ) = p , , ( t x l 一五出一肛缸) + o ) ，轧堑岔+ 只+ 。o x l 一a a t k 丛口+ 只一。o ) 五砸一弘岔) = 只o 一2 a t 一芦岔) + 只t 址山+ 一。( f l 礼+ o 心) 盟等型= t ) + 比o ) 一以+ 她o ) + 掣 令a t - 0 ，得到方程： 盟等型= 吨o ) + 比o ) 一q + 地o ) + 百o ( a t ) ( 3 _ 8 )& 其中n = l ，2 ，3 ；当n = 0 时可以得到： 掣：一弛o ) + 肥o ) ( 3 - 9 ) t i t x , l 于稳态情形，p n ( t ) 与t 无关，其导数为0 。因此可得差分方程如下： 彼一- + 以+ 1 - q + 地= ” 刀l 一弛+ 朋= 0 只= 昂 仔m 今设p 2 昙“，由于薹- 1 ，故只_ l 一2 - - - = 1 - p l , 从而p 月= 0 p 02 ：_ p 。( 3 - 1 1 ) 只= ( 1 一p ) p ”n = l ，一，2 一 公式( 3 1 1 ) 中p 有其实际意义，称为服务强度。它表示平均到达率入与平均 服务率u 之比；也是一个顾客的平均服务时间1 u 和平均到达间隔1 入之 比。 以公式( 3 1 1 ) 为基础计算系统运行的指标如下： ( 1 ) 在系统中的平均顾客数( 队长的期望值) ： 妒善圮2 南( 3 - 1 2 ) 硕士学位论文第三章多通道等待排队算法的数学模型 ( 2 ) 在队列中等待的平均顾客数( 队列长的期望值) ： 扩薹( 川肛卫, u - 2 ( 3 ) 在系统中顾客逗留时间的期望值： 形：士 ( 4 ) 在队列中顾客等待时间的期望值： 形：二 3 3 2 采用m m s 等待制选课多服务台模型 采用多服务器的等待选课排队模型如下图： - - 0 图3 - 2 多服务器等待选课排队模型图 ( 3 1 3 ) ( 3 - 1 4 ) ( 3 1 5 ) 设顾客单个到达，相继到达的时间间隔服从参数为入的指数分布，系统中 共有s 个服务员，每个服务器的服务时间相互独立，且服从参数为u 的指数分 布。当顾客到达时，若有空闲的服务器则可以马上接受服务，否则便排成一个 队列等待，等待空间为无限。 下面讨论这个排队系统的平稳分布。i ge = p n = 行如= o , l ，2 ) 为系统达到 平稳状态后队长n 的概率分布，注意到对个数为s 的多服务器系统，有： 砌= 五 删 2 和舻 ：= 乞 记成= p s = 三，则当p o 有。 ( 1 ) 学生到达( 生) ：在( t ，t + a t ) i 为系统出现一个新的到达的概率为 f 知址+ 0 ( 出) 2 f 知 0 的常数：没有发生新的到达的概率为l 一以址+ o ( r ) ，出现 多于一个以上的新的到达概率为o ( d 。 ( 2 ) 学生离去( 灭) ：在( t ，t + a t ) f 畸，系统消失一个的概率的以，+ 烈，) ；以 0 圭邮 硕士学位论文第三章多通道等待排队算法的数学模型 的常数，没有消失的概率为消失多于一个以上的概率为o ( a t ) 贝j j 称系统状态 随时间而变化的过程x ( t ) 为一个l 一心a t + d ( 出) 学生选课的生灭过程。 3 4 2 选课生灭过程微分差分方程组的建立 设p n ( 0 为表示选课排队系统在时刻t 的状态x ( t ) = i l 的概率即 p n ( t ) = p x ( t ) = n ) ，n s ，t o 则系统在时刻t + a t 的状态为n 的概率近似于 以下四个概率之和。 ( 1 ) p 系统在时刻t 时为n ，而在t 内没有到达也没有消失) - - - - - p n ( t ) 【1 一以出一以f ) = ( f ) 0 一九址一以a t ) + o ( a t ) ( 2 ) p 系统在t 时为n 1 而在a t 内有一个到达并且没有一个消失 = 只+ l ( f ) 名斛l a t ( 1 一。+ l a t ) = 只一l ( ，) 五斛l a t + o ( a t ) ( 3 ) p f 系统在t 时为n + 1 ，而在a t 内没有到达而有一个消失 = 只+ l ( r ) 。l a t o 一肘l a t ) = 只一l ( f ) 肘l a t + o 陋j ( 4 ) p 系统在t 内发生多于一个的到达或消失 = 0 ( t ) 即应用全概率公式 有只o + f ) = e 0 x 1 一九址一以血) + 只一。( f 玩一。a t + 只+ 。o 址州a t + d 陋) 当n = 0 时，只o + 出) = ? , 0 x i 一肌f ) + 最一o 玩一。a t + d 陋) 类似地 ， 当 s 为有限集时 ， 对 n = k 有 只o + 出) = p o ( t x l 一九f ) + 只( 址。a t + d 阻) 令t o 得，当系统状态s 为有限集时，生灭过程的微分差分方程组为 只( f ) = 以一1 只嘶) 一阮+ 心地( r ) + 以+ l + i ( ，) n l 厶，) = 一厶只( ，) + 1 只( ，) 最( f ) = 以一l 忍一l ( f ) 一u kp k ( f ) 当系统状态s 为可数集时，排队生灭过程微分差分方程组为 0 = _ - 0 一t 一+ 心地+ 以“气琊， 砣1 ( ，) = 一厶异( f ) 一r a _ p o , l - d i ( f ) ( 3 - 2 3 ) 3 4 3 选课中排队流量控制模型 选课系统可靠性的另一个重要特征是流量控制，即当系统接受到的服务请 求超过系统设计容量时，如果即使全部服务器都用上，都不足以承担庞大的学 生选课请求时，需要实行流量限制，在保持选课质量的前提下降低学生排队流， 以减弱系统各设备的负载线性增加趋势，保证系统的平稳运行，这是选课能否 成功完成的另一重要因素。 如何控制最优的流量以优化选课服务器的服务质量，我们需要先寻找一个 排队流量控制的模型。以下我们分析并建立排队流量控制模型。 2 7 硕士学位论文 第三章多通道等待排队算法的数学模型 针对选课过程，服务器s e r v e r 具备一定的服务能力。服务能力表现为最 大并发处理数c 、每个服务的平均服务时长t ( 或服务速率l a = i t ) 、业务处理最 大流量m ( 为保证系统稳定性，在此最大流量下设备负荷不超过满负荷的7 0 ) ， 设学生端为c l i e n t ，这几个参数之间的关系为： 图3 - 4 c il e n t s e r v e r 结构图 只要我们在服务器s e r v e r 端限定最大并发处理数c 及平均服务时长t ，我 们就可以限制业务流量，保证s e r v e r 的平稳运行。对此模型，当业务请求量超 过c 时，s e r v e r 将拒绝服务，此时选课接通率下降。 为提高大选课量下的接通率，可对c l i e n t s e r v e r 模型进行扩展，引入排队 队列，如图3 5 ： 图3 - 5 具备排队队列的c 1i e n t s e r v e r 结构图 这样，当选课请求数超过最大并发处理数c 时，可将选课请求放入排队队 列中进行排队，因排队过程一般不消耗s e r v e r 负荷，可以确保s e r v e r 的平稳运 行。 硕士学位论文第三章多通道等待排队算法的数学模型 排队队列长度有以下几种情况： ( 1 ) 模式一：排队队列长度为0 。模型退化为图3 - 4 。 ( 2 ) 模式二：排队队列为有限长度( 【m m c ： n o o f c f s 模型) 。在该环 境下，当队列满时，s e r v e r 将拒绝新的业务请求，接通率下降。 ( 3 ) 模式三：排队队列为无限长度( 【m m c ：【o o o o f c f s 模型) 。在该 环境下，可使接通率不降低，但当业务请求量持续大于业务服务能力时，s e r v e r 的队列长度将不断增长，内存消耗增加，将引起s e r v e r 不稳定。 排队方式有多种情况，比较常用的是下面两种情况：( 1 ) f c f s ：先进先服 务；( 2 ) l c f s ：后进先服务。 本文中，采用模式二。c l i e n t 的请求服从p o i s s o n 分布，近似认为服务能 力满足负指数分布，则上述通过排队论 m m c ： n 。o f c f s 模型计算出服务 能力、业务请求流量、排队队列与接通率、平均排队时间、平均逗留时间的关 系。则： ( 1 ) 在某种业务请求流量下，为获得需要的接通率，我们可以计算出合适 的队列长度。 ( 2 ) 在大业务量情况下，如果限定逗留时长，计算出一个合适的排队队列 长度，当排队长度超过该值时，业务请求再继续排队就没有意义。( 比如设定超 时退出机制的环境) ( 3 ) 对于关键业务请求，可以通过增大排队队列长度来提高接通率。 关于流量控制的模型可用下面的微分方程组描述： 6ya1 3 【 r 6yq ( t ) 2 击a p 0 - 21 3 ( 1 - p 0 ) yqo 6yq ( t ) + 志q 、 yq0 一byq0 ) 6p ( t 一ra ) 8q ( t ) = n6yq ( t 一r ) 其中，6ya ( t ) = yq ( t ) 一yq0 ， 6p ( t ) = p ( t ) 一p 0 ， 6q ( t ) = q ( t ) 一q 0 ，yq0 = c n ，p 0 = dc ( qn 十bc ) 说明：式中，yq ( t ) 为当前允许排队率，yq0 为期望的允许排队率， p ( t ) 为当前的非拥塞概率，p 0 为临介非拥塞概率，q ( t ) 为服务器中当前的队列 长度，q o 为服务器中期望的队列长度，c 为链路容量，n 为激活的连接数，a 为为选课单元，ta 为自进人拥塞服务器到返回选课请求所经历的时间，yq0 为选课请求与发生拥塞的服务器之间的传输延时。 硕士学位论文第三章多通道等待排队算法的数学模型 3 5 多通道等待排队选课模型的建立 多通道等待排队模型又称多服务台等待制l v l l v l c 排队模型，即n i l v l c , 顾客来到的时间间隔服从参数的负指数分布，服务员为顾客服务时间服从参数 的指数分布，c 个服务台，系统容量为的等待制排队模型。 由于入为：单位时间平均到达的顾客数，即平均到达率，p 为：单位时间 平均服务完的顾客数，即平均服务率，而p = 入u ( 服务强度) ，当p l 时，模 型不稳( 入 l i 时，队列越来越长，入= l a 时达不到统计) ，当p 。 1 时，模型稳 定，有稳定解。 3 5 1 多通道排队稳态的概率分布 m 瓜嗄c 模型系统状态图为 九 九 掘缘 图3 - 6m m c 模型系统状态图 状态转移图是处理稳态b i i v l c 系统的一种工具，设达到服务率分别为入和 u ，则对于状态n ( n = l ，2 ，) ，由于系统满足统计平衡，即流入应等于流出，于 是我们可以列出方程： 1 甩 c 刀c 得到此模型微分差分方程组 ( ，) = 力只- l ( ，) 一以+ n l t 蛾( f ) + g + 1 址只+ l ( ，) 只( ，) = 弛- l ( ，) 一n + 掣地+ 掣只+ l ( ，) t o ( f ) = 地( r ) 一强，) ( 3 2 2 ) 1 i v c 疗c ( 3 - 2 3 ) 3 5 2 列出各状态的代数方程 令p = 入l a ，因为p n 1 系统状态极限概率存在，根据生灭图和建立柯尔 莫可洛夫方程的一般法测，有1 对s 0 有：入p o = l lp 。p 。= ( 入u ) p o = pp o 对s 1 有：入p 。= 2l ap 2p 2 = ( p2 21 ) p 。 力譬 = = 以 心 硕士学位论文第三章多通道等待排队算法的数学模型 对s 2 有： 对s n - 1 有： 入p 2 - - 3l ap 3 入p n l = nl lp n p 3 = ( p3 31 ) p 0 p n = ( pn n ! ) p o 对s n + r - 1 有：入pn + r - l = n upn + rp n = ( p “竹n 7 i c n ! ) p o p o + p l + p 2 + + p n + m = 1 可得出系统的效率指标公式。 3 6 排队选课系统的效率指标的求解 根据p o 求出系统的效率指标：系统损失概率、系统的相对通过能力、系统 的绝对通过能力嗍、系统内排队的等待选课的学生平均数、学生的平均排队等 待时间、占用服务器的平均数、系统内的学生平均数。 以上各项指标如下： ( 1 ) 系统损失概率 在等待系统中，请求服务的顾客迟早会被接受服务，所以，p 掼= 0 ( 2 ) 系统的相对通过能力 ( 3 ) 系统的绝对通过能力 ( 4 ) 系统内排队的等待选课的学生平均数 三队= 1 只+ 1 + 2 只+ 2 + + n 巴+ ，+ = 铸昂+ 筹，等- 筹只南 ( 5 ) 顾客的平均排队时间 。 等_ p n n 磊墨 ( 6 ) 占用服务器的平均数：k ：_ a ：一：p ( 7 ) 系统内顾客平均数：l 系= l 队+ p 经过数学模型的建立，我们将选课中学生排队等待和服务器处理的能力和 效率转化为数学模型进行分析和处理，以下第三章将从系统的效率分析出发， 3 l 硕士学位论文 第三章多通道等待排队算法的数学模型 以研究单通道排队算法和多通道排队算法的效率比较，由此得出采取多通道排 队算法的原因。 硕士学位论文 第四章多通道等待排队算法的效率分析 第四章多通道等待排队算法的效率分析 上章给出了排队算法的数学模型，本章将通过几种排队模型的比较，以找 到效率最佳的排队模型。 4 1 多通道等待排队算法的系统效率指标 从第三章分析，我们得出排队选课系统的效率指标d 1 ： ( 1 ) 系统损失概率：在等待系统中，请求服务的顾客迟早会被接受服务， 所以，p 损= 0 ( 2 ) 系统的相对通过能力：q = i - p 扭= 1 ( 3 ) 系统的绝对通过能力：a = 入q = 入 ( 4 ) 系统内排队的等待选课的学生平均数 l 队= 1xp n + l + 2 p n + 2 + + r p n + r + ：型p o + 2 p n