（计算机科学与技术专业论文）拨测管理系统任务自主调度算法的研究与设计.pdf

拨测管理系统任务自主调度算法的研究与设计 摘要 随着移动网络的规模日益扩大，市场竞争愈演愈烈，用户对业务 质量的要求也随之提高。拨打测试系统模拟终端用户的行为，执行拨 测业务，通过分析用户关心的业务性能指标得到业务的使用情况，为 移动网络的终端业务测试提供服务。本文主要研究拨打测试系统的任 务资源调度模型，提出了一种适用于拨测系统环境的任务自主调度算 法。 任务资源调度算法涉及到任务、资源和任务资源调度模型三方 面。其中任务类型、任务与资源的专享关系、任务优先级和任务属性 直接决定了任务q o s 需求；s i d ( s i mi m p o r t e dd e v i c e ，s i m 卡集中 管理设备) 资源和r t d ( r e m o t et e s td e v i c e ，远端拨测设备) 资源属 性决定资源的能力。在任务资源调度模型的框架下，调度系统综合权 衡资源对任务q o s 需求、任务的执行情况和资源利用率，得到最佳 的调度序列。 拨测管理系统任务资源调度模型使用的算法属于m e t a t a s k 型算 法。目前流行的m e t a t a s k 型算法有极小极小算法、极大极小算法和 s u f f e r a g e 算法。极小极小算法和极大极小的算法没有考虑任务q o s 需求和资源利用情况，不适用于拨测管理系统。s u f f e r a g e 算法综合权 衡任务优先级和资源能力来选择任务的执行资源。本文提出的任务自 主调度算法考虑任务优先级和资源利用率、资源对任务q o s 需求的 满足等，全面考虑了所有的决定因素而选出执行资源。 最后，本文提出了一种任务资源调度算法的性能评价指标，采用 任务集完成时间、资源负载均衡程度两个指标衡量算法的性能。通过 伪代码描述算法的执行情况，并用比较图的方式对比任务自主算法和 s u f f e r a g e 算法的性能指标，最终得出两种算法的优缺点和适用场景。 关键字：调度任务自主资源负载q o s t h ei 之e s e a r c ha n dd e s i g no fc a l l i n ga n d t e s t i n gs y s t e m st a s ka u t o n o m y s c h e d u l i n ga l g o r i t h m a b s t r a c t w i t ht h es c a l eo fm o b i l en e t w o r kb e c o m i n gl a r g e ra n dl a r g e r , m a n e t c o m p e t i t i o nb e c o m i n gm o r ea n dm o r ek e e n ，u s e r s s e r v i c ed e m a n d sa r e r i s i n g c a l l i n ga n dt e s t i n gs y s t e mi su s e df o rc u s t o m e rs e r v i c eo nm o b i l e n e t w o r k i ti m i t a t e st h ec u s t o m e r s b e h a v i o ra n dc a r r i e so u tt a s k s ，a n d g e t ss e r v i c e sc o n d i t i o nb ya n a l y z i n gs e r v i c ep e r f o r m a n c ei n d e x t h i s p a p e rm a i n l yr e s e a r c h e sc a l l i n g a n dt e s t i n g s y s t e m s t a s kr e s o u r c e s c h e d u l i n gm o d e l ，a n dg i v e sas e l f - a d a p t i n gs c h e d u l i n ga l g o r i t h mw h i c h i ss u i tf o rt h es y s t e m t h et a s kr e s o u r c es c h e d u l i n ga l g o r i t h mh a sar e l a t i o n s h i pw i t ht a s k s ， r e s o u r c ea n dt a s kr e s o u r c es c h e d u l i n gm o d e l t a s kt y p e ，t h ee x c l u s i v e r e l a t i o n s h i pb e t w e e nt a s ka n dr e s o u r c e ，t a s kp r i o r i t ya n dt a s ka t t r i b u t e d e t e r m i n et h eq o sd e m a n d so ft a s k s t h ec o m p u t i n ga b i l i t yo fr e s o u r c e i sd e p e n d e do ns i da n dr t dr e s o u r c e sa t t r i b u t e s u n d e rt h ef r a m e w o r k o ft a s kr e s o u r c es c h e d u l i n gm o d e l ，t h es y s t e mg e t st h eb e s ts c h e d u l i n g s e q u e n c ec o n s i d e r i n gb o t ht h er e s o u r c ea b i l i t ya n dt h ee x t e n th o wt h e r e s o u r c es a t i s f i e st h eq o sd e m a n d so ft a s k s m e t a t a s ka l g o r i t h m sa r es u i tf o rc a l l i n ga n dt e s t i n gs y s t e m st a s k r e s o u r c es c h e d u l i n gm o d e l t h i sp a p e rm e n t i o n st h r e ep o p u l a ra l g o r i t h m s w h i c ha r em i n - m i n ，m a x - m i na n ds u f f e r a g ea l g o r i t h m n o w a d a y st h e m i n - m i na n dm a x m i na l g o r i t h md o n tc o n s i d e rt h et a s kp r i o f i w , s ot h e y a r en o ts u i t a b l ef o rt h es y s t e mt h ep a p e rm e n t i o n s s u f f e r a g ea l g o r i t h m c o n s i d e r sb o t ht a s kp f i o r i t ya n dt h ea b i l i t yo ft a s k t h i sp a p e rg i v e s t a s k a u t o n o m ya l g o r i t h m ，w h i c hc o n s i d e r st h a tt h er e s o u r c es a t i s f i e st h e q o sd e m a n d so ft a s k sb e s i d e s t a s kp r i o f i t ya n dt h e u s a g er a t i oo f r e s o u r c e ，t os e l e c tr e s o u r c e a tl a s t ，t h i sp a p e rs h o w sap e r f o r m a n c ee v a l u a t i o ni n d e x e so ft a s k r e s o u r c es c h e d u l i n ga l g o r i t h m i tm e a s u r e st h ep e r f o r m a n c eo fa l g o r i t h m b yu s i n gm a k e s p a no ft a s kg r o u pa n dr e s o u r c el o a d t h ep a p e re m u l a t e a l g o r i t h m ，a n dc o m p a r et h ep e r f o r m a n c ei n d e x e so ft a s k - a u t o n o m y a l g o r i t h ma n ds u f f e r a g ea l g o r i t h m i nt h ee n dt h ep a p e rs u m m a r i z e st h i s t w oa l g o r i t h m s a d v a n t a g e sa n dd i s a d v a n t a g e sa sw e l la st h e i ro w n s u i t a b l ec i r c u m s t a n c e s k e y w o r d s ：s c h e d u l i n gt a s k - a u t o n o m y r e s o u r c el o a d q o s 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名至笙i 匕日期： ! ：二2 ：兰! ! 乒 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 本学位论文不属于保密范围，适用本授权书。 本人签名：丝1 5 立 日期： ! = 翌= 互! 翩签弘掣! 啉塑：幽 1 1 研究背景和意义 第1 章前言 随着移动网络规模的扩大、移动通信市场的竞争日益白热化，用户对网络质 量要求的不断提高，保持网络质量领先是企业长足发展的基础。现有的网络质量 测量多是针对系统而言，而没有将用户的服务体验考虑在内。因此造成某些时候 网络的质量很稳定而用户的服务体验却不佳的情况。为了解决这些问题，近年来， 一些移动运营商建立了拨打测试系统，其目的是测试得到终端用户所关心的业务 服务体验指标和解决移动网络中的实时故障。拨打测试系统的建立，使得网络质 量的监测从面向系统层次提升到面向用户感知的层次。一方面，拨打测试系统关 注于用户感受得到的业务指标，从用户的角度来指导移动网络升级和业务功能改 善，极大的提高了用户服务体验。另一方面，拨打测试结合了面向系统的质量测 试和面向用户业务感知的质量测试，全方位多角度的分析测试数据，从而保证了 故障定位和故障解决的实时性和准确性。网络拨测工作的成效已成为影响客户感 知度的重要因素，网络拨测系统因此也成为通信运营商之间竞争网络优势的重要 监测手段。从长远来看，拨打测试系统在战略一致性、维护管理、资源发展、业 务发展、网络安全、技术环境的因素驱动下，将成为一套用户体验反馈机制的有 效实现方式，保证了移动网络的业务性能，业务的人性化程度和业务的功能满足 程度达到用户的要求。 随着一些地方的移动运营商建立自己的移动网络拨打测试系统，出现了多个 拨测系统各自为政的局面，带来一系列问题。因此，建立一套综合拨打测试系统 成为必然。综合拨打测试系统统一管理下级拨测系统，从而提高了数据的共享性， 降低了维护系统复杂度。在综合拨测系统平台上对拨测结果进行统一上报，分析 并存储，降低了各拨打测试系统之间通信的代价，提高了系统处理数据的能力。 建设综合拨打测试系统平台有利于提高拨打测试资源( 拨测设备，测试卡) 的利用 率。通过制定拨打测试系统、拨测设备的接口标准，防止各厂商设备捆绑，促进 拨打测试系统的发展。制定统一的文档输出格式，提高输出的可扩展性。另外， 建设综合拨打测试系统可以方便调度执行联合拨测任务，提高了拨测任务执行的 范围，增加测试过程真实性，丰富了测试结果项。 拨打测试管理系统通过调度资源来执行拨测任务。按照常见的先来先服务原 则，而不考虑任务与资源的关系以及任务资源调度的实时情况，得到的调度序列 在拨测任务的执行和拨测资源的使用上可能都不是最佳的。因此，为了使得任务 和资源都达到最佳状态，必须设计一个合理的任务资源调度算法，得到科学合理 的调度序列，从容保证任务的执行效率和资源的使用效率。 1 2 本文的研究内容 本文主要研究拨打测试系统中任务资源的调度算法。首先，介绍拨测系统的 平台结构和各功能模块。然后阐述了与调度算法相关的任务管理、资源管理和任 务资源调度模型。本文提出了一种基于任务自主调度的算法，综合权衡任务的 q o s 需求、任务执行情况和资源的利用率，选择出最合适的资源执行任务。接 着提出了用于衡量算法优劣的调度算法性能评价指标，通过定义m a k e s p a n ( 任务 集完成时间) 、资源负载均衡度指标，衡量各种算法的任务集执行情况和资源的 使用情况。通过比较各种算法的优缺点，得到它们的适用场景。 本文的主要工作： ( 1 ) 分析各种m e t a - t a s k 型调度算法优缺点 分析m e t a - t a s k 型的三种主流调度算法一极小极小算法、极大极小算法和 s u f f e r a g e 算法，描述极小极小算法和极大极小算法的原理、作用和优缺点。描述 了s u f f e r a g e 算法的原理和优缺点，给出了算法的伪代码。 ( 2 ) 提出一种任务自主调度的算法 分析任务自主调度算法的需求，阐述了研究的问题和调度机制，给出了算法 的输入、输出和目的，设计任务自主调度的思想和算法的步骤，画出了算法的流 程图。 ( 3 ) 定义调度算法性能评价指标和算法的比较 定义调度算法的性能评价指标。分析极小极小算法和极大极小算法不适宜拨 测管理系统的原因。用伪代码实现了s u f f e r a g e 算法和任务自主调度算法，比较 s u f f e r a g e 算法和任务自主调度算法的m a k e s p a n 和资源负载均衡度性能指标，分 析两种算法的适用场景。 1 3 硕士期间工作 在攻读硕士期间，本文作者参与了中国联通i p 承载网网络管理接口功能一 2 致性测试、中国联通c d m a 2 0 0 0 资管与传输接1 2 1 & 网络资源模型、i p t v 运维支 撑系统的研究与系统设计等一系列标准研究工作。具体的研究情况如下： 1 1 编写规范 编写北京网通n g n 业务网络规范标准：作为该标准化工作的主要参与人， 制定了下一代网络的业务能力评审规范，包括g r o u p 能力集规范、i m 能力集规 范、p r e s e n c e 能力集规范、点击拨号业务能力规范、会议业务能力规范、计费能 力接口规范、通话管理业务能力规范。 c d m a 2 0 0 0 网络管理技术要求的制定：作为中国通信标准化协会( c c s a ) 3 g 网络管理研究课题成员，参与国家通信行业标准2 g h zc d m a 2 0 0 0 数字蜂 窝移动通信网网络管理技术要求告诉分组数据( h i 冲d ) ( 第一阶段) 的制 定，担任其中第3 部分：基于c o r b a 技术的网络资源模型设计的设计。 中国联通c d m a 2 0 0 0 资管与传输接口规范设计：作为编写人，使用x m l 语言 编写c d m a 2 0 0 0 的资产接口、传输设备的接口。 2 ) 测试工作 中国联通口承载网网络管理接口功能一致性测试：根据测试规范和功能需 求对各厂商接口功能进行一致性测试，包括连通性测试，配置管理测试，性能管 理测试，告警管理测试，业务管理测试，网流分析数据获取能力测试，并生成测 试文档。 3 ) 论文工作 学术论文：p t v 管理系统的研究与设计。分析口t v 管理系统的需求，规 划t v 管理系统体系结构，分析实现子系统功能的构件技术，设计管理系统的 数据模型，管理功能和终端的管理流程，并完成一篇文稿。 毕业论文：广东移动拨打测试系统任务资源调度算法的设计。分析拨测系统 的任务资源调度模型，设计出一种任务自主的调度算法，提出衡量算法性能的各 项指标，并与其他的调度算法进行比较。 1 4 论文结构 本文共分为六章，论文结构和每章节的内容如下： 1 1 第一章前言 前言描述了本论文的研究背景和重要性，本文的研究内容，研究生阶段的研 究课题内容和论文的结构 2 ) 第二章拨测管理系统 本章介绍了拨测管理系统的产生背景和功能架构。然后阐述了与任务资源调 度模型相关的三个因素任务、资源、调度模型。任务管理方面涉及到任务类 型、任务优先级、任务与资源的专享关系、任务的循环类型和任务属性。拨测管 理系统根据上述任务的q o s 需求来调度。拨测系统在资源管理平台下管理拨测 终端设备( r t d ) 和测试卡( s t o ) 。调度模型阐述了任务资源调度的执行步骤，调度 系统的工作原理，调度模型的功能结构和调度算法。 3 ) 第三章任务自主调度算法 本章先介绍三种m c t a - t a s k 型任务调度算法极小极小算法、极大极小算 法和s u f f e r a g e 算法。然后描述了任务自主调度机制的设计思想，给出了任务自 主调度算法的实现步骤，画出了任务自主调度算法的流程图。 4 ) 第四章任务资源调度算法性能评价 本章定义了调度算法的概念和各种任务资源调度算法性能指标，并用伪代码 实现了任务自主调度算法，并从m a k e s p a n 和资源负载均衡度指标角度比较了任 务自主调度算法和s u f f e r a g e 算法。 5 1 第五章总结 本章是对全文的总结以及对进一步研究工作的展望。 4 第2 章拨打测试系统 2 1 拨打测试系统介绍 传统的人工拨测方式拨测效率较低。人员成本投入较大。自动化的拨测系统 能够把运维人员从繁琐的拨测任务中解放出来。拨测管理系统通过制订拨测任务 计划，下发到拨测终端设备( 或者经已建的拨测系统转发) ，根据测试内容，在 测试完成后从拨测终端设备、拨测相关网络实体或者已建拨测系统收集测试结 果，进行统计分析，实现高速度、大容量、全方位的测试。为通信网络的高效优 质运行提供了保证，同时应对网间通信质量争议，实现不同网络的质量评估。 拨测管理系统体系结构为平台架构系统功能模块建设在底层通用平台之 上。拨测管理系统平台体系结构示意图如图2 1 所示。 匿2 1 接测管理系统平台体系结掏 l 目 ( 1 ) 硬件平台 拨测管理系统平台最底层为硬件平台，其正式环境包括：w e b 服务器、应 用服务器、文件服务器、数据库服务器、数据通信服务器、语音卡服务器等。服 务器需求、域名、环境、机器名由系统建设方与需求方协商定义。 ( 2 ) 软件平台 采用统一的开发工具和操作系统，以提高系统的稳定性和可维性。具体软件 平台需求由系统建设方与需求方协商定义。 ( 3 ) 通用组件 通用组件即将上层应用功能模块的通用功能提取出来，使用组件的方式实 现，并以服务的方式提供相关功能。通用组件包括：应用监控组件，心跳通知组 件，进程守护组件，集中授权组件，单点登录组件，消息通知组件，报表通用组 件，目录同步组件。 ( 4 ) 上层应用 上层应用层的各功能模块实现了拨测管理主要的功能业务逻辑，各模块相互 独立，又支持通过中间件进行实时交互。不仅可以根据不同的目标，灵活选择不 同的模块，构成实际需要的管理功能集；而且可以根据被管理的拨测网络规模， 灵活选择系统硬件平台，以最优方式将软件布署到不同的硬件上。上层应用实现 了拓扑管理、任务管理、结果监控、告警管理、统计报表、资源管理、设备管理、 拨测业务管理和事务管理。 ( 5 ) 统一管理 统一管理包括统一用户身份验证和统一信息呈现。由于上层应用由多个不同 功能模块组成，不同模块可能由不同的开发商承建，为此，在此之上提供统一管 理框架，为用户提供统一的访问接口、呈现视图，保证系统使用的整体性。 ( 6 ) 系统支撑 拨测管理系统是一个基于拨测网络环境下的集中管理软件系统，为保证构成 系统的各管理功能模块之间能够有机配合、正常运行，保证用户能够安全、高效 地使用本系统，协同完成相关的管理目标，实现人机有效结合，要求系统支撑管 理功能实现这一目标。系统管理、安全管理、值班管理和接口管理是系统支撑的 主要功能。 2 2 任务管理 拨测任务的制定涉及到用户的权限，用户角色，任务优先级，任务类型，任 务执行地域，任务与资源的专享关系等相关因素，任务管理模块将管理这些复杂 6 的关联关系。拨测资源与特定用户制定的任务构成专享关系，资源分为专享和共 享。特定情况下，任务根据资源分配原则选择资源。省公司和地市级公司的资源 需要规划，这些问题需要资源管理模块来解决。任务与资源调度模型实现的是任 务从制定完成到下发到资源的流程和整体架构。 2 2 1 任务类型 任务分为临时任务、周期性任务和定时任务。当网络出现故障时，需要专门 制定临时性的任务来检测网络，定位故障点。临时任务映射为单次，短时间有效 的任务。优先级比周期性任务低。 周期性任务主要用于周期性的业务测试，以便实时监控当前网络的运行状况 及服务质量，并为运维和质量监控提供大量的基础数据。通过周期性的测试，可 以判断移动网络的性能状况和变化的趋势。周期性任务映射为长时间，多次的有 效任务，优先级比临时任务高。 定时任务是指在某个特定时间执行的任务。这种任务是用来测试某个时刻的 业务，是预先设置好的。任务优先级介于周期性任务和临时任务之间。 2 2 2 任务与资源的专享关系 专享是一种关系，资源本身无法构成专享关系，当资源是专享性质的，并且 将资源分配给专享该资源的操作员制定的任务时，资源和任务才构成了专享关 系。专享是相对的。用户组a 制定的任务与资源r 是专享关系。从用户组a 的 角度看，资源r 是专享，但从用户组中的用户a i 】和a d 之间的角度看，资源r 是共享的。当在专享资源空闲而共享资源忙碌的情况下，虽然测试任务与共享资 源间没有构成专享关系，在某些任务资源调度策略下，将任务下发到该空闲的共 享资源上去，从而增加了资源的利用率和提高任务的执行水平。 2 2 3 任务优先级 根据任务优先级划分的测试任务分为两类。 1 ) 可抢断资源的任务 可抢断资源的任务优先级是1 级和2 级。优先级1 和2 也叫打断优先级。当打断 优先级的任务没有资源可执行任务时，会打断优先级较低普通优先级任务。 2 ) 不可抢断资源的任务 不可抢断资源的任务优先级是3 级，4 级和5 级。优先级3 ，4 ，5 t g 叫普通优先 级。普通优先级的任务不具备打断当前正在执行任务的权限。 优先级及其描述如表2 1 。 2 2 4 任务循环类型 对于临时性任务，将任务按开始执行时间点的先后顺序排在调度对列中，任 务只执行一次。 对于周期性任务，可以分为按分钟间隔周期执行，按天间隔周期执行，按月 间隔周期执行，周期性任务按开始执行点先后顺序排在调度队列中，同一任务插 入在同一调度队列的不同地方。该任务的下一次执行时间点是本次执行时间点加 上执行的周期时间。 对于定时任务，任务开始执行时间点是可配置的。这种任务每次执行的时间 点并没有规则的分布，而是由用户设置每次的执行时间点。 表2 1 任务优先级描述 优先级 描述 1 最高优先级，可以进行资源的抢断。该权限还可以抢断专享类资源。一 般保留使用。比较紧急的临时任务使用 2 次高优先级，可以进行资源的抢断但不可以抢断专享类资源，该权限 不能抢断专享类资源。临时任务使用 3 较高优先级，属于普通测试任务中的最高优先级，在进行资源分配时最 优先考虑，对于执行频度不是很高，但又比较紧急的任务建议使用此类 优先级。 4 普通优先级，例行测试任务建议采用该类优先级。 5 较低优先级，对测试时间没有严格要求的测试任务可以考虑使用次类优 先级。该优先级也可以保证测试任务能在2 4 小时内完成。 2 2 5 拨测任务属性 在拨测管理系统中，与拨测任务相关的属性有很多。有些拨测任务的属性在 任务开始执行之前已经确定。比如拨测任务的开始执行时间，拨测任务与资源的 专享关系，拨测任务的循环类型等。有些属性在任务的执行过程中动态变化，比 如拨测任务的优先级，会随着被打断次数的增加而升高。有些属性在任务执行完 成后才能确定，比如任务的完成时间。 任务属性如表2 2 所示： 2 3 资源管理 拨测资源包括r t d ( r e m o t et e s td e v i c e ，远程测试设备) 和s i d ( s i mi m p o r t d e v i c e ，s i m 卡集中管理设备) 。每一个r t d q b 装载两个拨测模块，此外还可以外 挂其他拨测手机。例如t e m s 手机，p h s 手机，从而能够同时进行多个业务的测 试。s i d 是装载和集中管理s i m 卡的设备，可自动获取s i m 卡的i m s i 和m s i s d n ， 短信中心号码等信息。 表2 2 任务属性描述表 属性名称说明 类型和取值说明限定 任务编号唯一标识任务的i d 字符串，取值唯一 _ r 用户用户组编号 制定任务的用户或用户字符串，取值唯一 _ r 组的i d 任务优先级值越低，优先级越高取值0 ，1 ，2 ，3 ，4 ，5 一r _ 任务类型标示临时任务、周期任枚举型，取值为：临时任务，_ r 务或者定时任务 周期任务 任务循环类型任务循环执行的策略，枚举型，取值为：一r 适合临时任务和周期任只执行一次，按分钟的间隔周 务 期，按小时的间隔周期，按天 间隔周期，执行时间点可配置 任务开始时刻测试任务的开始时间点浮点型_ r _ 任务执行时间长测试任务的执行时间浮点型_ r _ 度 任务拨打方式拨测的方式枚举型，取值为：c d m 、鹋_ 、_ 。r p h s 任务执行地点任务执行所在地点，固取值为1 ，2 ，3 ，4 ，5_ r 定为几个地点 任务专享任务与某个资源专享， 字符串，取值唯一 _ r 专享值为资源的l d 。0 表示任务不存在专享性 2 3 1sid 的管理 ( 1 ) s i m 卡集中管理设备s i m 卡池( s i d ) s i m 卡池拥有3 2 个s i m 卡槽位，能够支持3 2 张s i m 卡同时远程开机，自动获 得s i m 卡中的i m s i ( 亘际移动用户识别码) ，m s i s d n ( 移动台的i s d n ) ，短信息中 心号码等信息。s i m 卡池集中管理s i m 卡资源，通过与远端拨测设备的接口将s i m 卡分配和调度给拨测设备。s i d 与拨测管理系统间和s i d 与拨测终端间的高保密 性的数据传输实现了测试卡的安全管理。 ( 2 ) 机卡分离技术 拨测管理系统采用机卡分离技术，测试卡实际存放在s i d 设备的测试卡槽 中。将测试卡集中起来，便于集中管理，从而使得s i m 卡的分配和回收更加容易， 进而提高了s i m 卡使用效率。 拨测管理系统支持远程分配测试卡。如果拨测终端直接装载s i m 卡，机与 卡就固定形成一对一的关系。那么在远程拨测设备没有任务执行的时间段里， 9 s i m 卡实际处于锁定状况而不能被使用，而其他的拨测设备则可能过于忙碌，造 成资源的负载不平衡。机卡分离技术则可以避免这种情况，拨测管理系统在远程 分配测试卡，在拨测终端装载的是虚拟的s i m 卡，测试任务完成后，虚拟s i m 卡 收回以供其他的拨测终端使用。拨测终端和s i m 卡的对应关系是多对多，从而提 高了测试卡的复用性和灵活性。 下图是机卡分离技术的应用。如图2 2 所示。 n i一 图2 - 2 机卡分离技术 ( 3 ) s i d 与拨测管理系统的接口 拨测管理系统的各个模块间通信采用长连接方式，长连接是指在一个t c p 连 接上传送多个报文。在t c p 连接保持期间，如果没有数据包发送，需要双方发 送链路检测包以维持连接。一般采用周期性心跳方式。图2 3 描述y s i d 和拨测管 理系统接口的功能：设备登记，心跳通知，槽位扫描。 2 3 2r i d 的管理 ( 1 ) 远端拨测设备r t d r t d 配备两个商用手机模块接口，可以支持g s m c d m 胛h s ，也可扩展为 3 g 模块。并且配备有外部接口，可外挂其他拨测手机。r t d 主板中利用s i m 卡模 l o 拟技术，可模拟s i m 卡要完成的大部分功能，并且根据业务的需要动态远程更新 s i m 卡的信息。 图2 3 拨测管理系统与测试卡管理设备接口流程图 ( 2 ) r t d 与s i d 的接口 r t d 与s i d 的接口用于规范r t d 与s i d 设备的接口操作，实现标准化的 m e s i m 数据交互。该接1 3 的流程分为三个阶段：m e ( m o b i l ee q u i p m e n t ，移动终端) 开机请求s i m ，m e s i m 命令与响应，m e 关机释放s i m 。 ( 3 ) r t d 和拨测管理系统的接口 从图2 4 可以看出该接口的功能包括：设备登记，心跳通知，拨测任务，文 件请求，资源调度。 图2 - 4r t d 和拨测管理系统的接口流程图 2 4 任务资源调度模型 2 4 1 模型执行步骤 1 ) 用户根据需要，制定拨测任务。 2 ) 任务管理器按照任务属性排列拨测任务。任务属性包括任务执行的开始 时间点，任务的优先级等。 3 ) 调度器根据调度算法匹配资源。调度器封装的调度算法可以是一种，也 可以是多种，以适应不同的调度环境。 4 ) 任务管理器将任务传送到指定的资源。 5 ) 执行任务，反馈信息到任务管理器。任务的执行结果上传到指定的服务 器。 1 2 该系统中最关键的就是任务调度的过程，也就是第二和第三步，这是本文的 研究重点。任务管理器和调度器处理任务的模式有两种。一种是单个模式，只要 有任务下发到任务管理器的排队队列，该任务就进入调度器进行调度。第二种模 式是批处理模式，批量处理一定数量的任务。可以是处理一定时间段内的任务， 也可以是任务数量达到一定值后批量处理。 2 4 2 调度系统工作原理 工作原理如图2 6 所示。 图2 5 拨测管理系统任务资源调度模型 2 4 3 任务资源调度模型功能结构 拨打测试系统的任务资源调度子系统结构如上图，主要实现2 4 1 节中所述 的第二、三、四步骤。该系统主要包括两个功能模块。 ( 1 ) 任务管理器 队列管理模块将用户提交的任务进行整理、排队、分配i d 。排队的原则根 据任务的属性，包括任务的执行时刻、任务优先级。如果是批处理模式，则将多 个任务传递到任务调度器的队列缓冲模块。如果是单个模式，则每次将单个的任 务传递到任务调度器的队列缓冲模块。任务映射模块根据任务调度器的结果发送 任务到它匹配的资源上。 ( 2 ) 任务调度器 队列缓存模块接受批量任务。各设备资源周期上报目前设备上运行情况，包 括资源利用率、资源状态、资源所在地理位置、资源的空闲时刻等。资源预测模 块统计上报的各资源性能数据，存储更新各资源设备的性能信息。资源匹配模块 筛选适合执行某任务的资源( 一般是多个资源设备符合条件) ，从资源预测模块 查询这些设备资源的当前情况，根据映射算法选出最合适的执行资源。映射算法 封装在资源匹配模块中，可以是一种，也可以是多种算法以适应不同的资源环境。 2 4 4 调度算法 调度算法是任务资源调度系统的资源匹配算法。常用的调度算法有极大极小 算法( m a x m in ) ，极小极小算法( m in - m in ) ，s u f f r a g e 算法。 1 4 第3 章任务自主的任务资源调度算法 为了使任务资源调度具有如下的特性：既使得任务的执行效率要高，又使得 拨测管理系统能动态的描述资源的实时信息，从而采取合适的措施规避这种动态 性带来的消极影响，并且采用合适的调度算法满足任务执行的q o s 需求和提高整 体资源的性能指标。我们引入任务自主的概念，根据资源当前的负载情况，在资 源上执行任务的数量，并结合资源满足任务的q o s 需求，找到最合适的资源，并 在该资源节点上执行任务。本章首先阐述目前主流的三种m e t a t a s k 型任务调度算 法的基本思想和原理、优点和缺点并分析在拨测管理系统下缺点造成的原因，然 后详细介绍任务自主的任务资源调度算法，算法的基本思想和算法流程图。 3 1m e t a - t a s k 型任务调度算法 拨测管理系统中的测试任务之间没有任何联系，是独立完成的任务，即 m e t a - t a s k 型任务【l 】。目前关于这种类型的调度算法研究的很多。主要有m i n - m i n ， m a x m i n ，s u f f r a g e 。 m i n - m i n 算法是先算出每个任务在所有执行资源上的最小完成时间，然后选 择其中值最小的资源，将任务下发到该资源上。该算法能够在最短时间内完成所 有任务，但是带来的问题是资源的负载不均衡。 m a x m i n 算法与m i n m i n 类似，只是选择值最大的资源下发任务。该算法虽 然能使负载基本均衡，但是完成所有任务的时间会延长。 s u f f r a g e 算法是一种以损失代价为衡量标准的算、法【2 1 。如果该任务不使用这 个资源，会遭受一定损失。选择损失程度最大的资源来下发该任务。 3 1 1 极小极小算法( m i n - m i n ) 极小极小算法是基于最小完成时间的调度算法。该算法需要假设能得到目前 所有资源的性能信息，从而估算出任务集中的每个任务在每个资源上的完成时间 长度。极小极小算法追求的是任务集的m a k e s p a n 最小。基本思想是：首先把所有 任务放在一个任务集中，任务集v = v i ，v 2 v n ) 。然后对任务集中的每个任务，算 出它的最小完成时间点t a c t 。假设m c t ( i ) 是任务i 的在当前环境下的最小完成时间 点，取m i n ( m c t ( i ) ) ，l i n 。将最小的完成时间点对应的任务映射到实现t a c t 的资源 上。将该任务从任务集v 中删除。然后重新估算剩下的任务的m e t ，取最小的任 务下发到与之对应的资源上。依此类推，直到任务集中的所有任务都被删除。 极小极小算法是一种基于m e t 的调度算法，越小的m c t ，任务优先级越高。因 此，这是一个短任务优先的调度算法。优点就是单位时间内处理任务的数量最大 化，从而提高调度系统的任务吞吐率。但是，极小极小算法是基于短任务优先的， 导致长任务被延后调度，造成任务的公平性问题。短任务会集中在几个资源上， 而造成负载不均衡。 从下面的例子可以看出极小极小算法的缺点。假设有一个由6 个任务和2 个处 理机构成的调度问题，6 个任务在处理机l 和2 上的执行时间分别是( 2 ，1 6 ，6 3 ，3 6 ， 4 0 ，1 8 ) 和( 4 ，2 8 ，2 l ，4 ，1 5 ，6 ) 。图3 1 是m i n m i n 算法得到的调度方案，调度长度是 4 6 。而最佳的调度长度是4 0 。 2 5 l o 1 52 0 2 53 0 3 54 04 5 5 0 5 5 6 0 6 5 7 0 图3 - 1r a i n r a i n 算法 从上图看出，处理机1 和2 上的任务分布的并不均匀，而且短任务在长任务之 前优先分配。m i n r a i n 调度算法仅仅考虑了每个任务的最小完成时间，缺乏整体 的规划调度，并没有考虑任务的执行时间和追求所有任务的m a k e s p a n 最小化。除 此之外，r a i n m i n 算法也没有考虑满足任务的q o s 需求。任务的执行时间延迟是每 个任务从规定开始执行时间点到实际开始执行时间点的时间长度，每个任务都有 规定的最大延迟时间，实际延迟时间不能大于最大延迟时间。另外，还要考虑资 源的利用率问题，追求资源的利用效率也是调度算法的目标之一，能够用最小的 资源完成最多的任务将会为拨测管理系统节省很大一部分资源。资源的负载均衡 程度也反映了调度算法的好坏。如果某些资源极度繁忙，而另外的资源空闲，会 造成任务分布不均，从而使得整体的任务执行情况不佳，也降低了拨测资源的性 1 6 能。因此，r a i n r a i n 算法并没有满足任务i 拘q o s 需求以及结合资源的动态特性， 也没有从整体上考虑任务的m a k e s p a n 和资源的使用效率、负载情况。 3 1 2 极大极小算法( m a x - m i n ) 极大极小算法也是基于最小完成时间的调度算法。只不过在选择任务分配资 源时，不是选择最小m c t 的任务，而是选择最大m c t 的任务。极大极小算法是 长任务优先，任务执行时问越长，优先级越高。长任务优先调度使得资源的负载 比较均衡。但是，由于更多的任务没有被分配到合适的资源上去执行，从而导致 了整体执行时间跨度m a k e s p a n l 比m i n m i n 算法更长。 从下面的例子可以看出m a x m i n 算法的缺点。假设有一个由6 个任务和2 个处 理机构成的调度问题，6 个任务在处理机1 和2 上的执行时间分别是( 2 ，1 6 ，6 3 ，3 6 ， 4 0 ，1 8 ) 和( 4 ，2 8 ，2 l ，4 ，1 5 ，6 ) 。如图3 2 所示： 2 51 0 1 52 0 2 5 3 0 3 54 04 5 5 0 5 5 6 0 6 5 7 0 图3 2m a x m i n 算法 从上图可以看出，处理机1 和2 上的任务分配的比较均匀。长任务比短任务优 先分配。但是由于任务1 和4 并没有调度到执行时间最短的任务上，导致了整体的 m a k e s p a n 更长，调度长度是5 2 。m a x - m i n 调度算法与m i n - m i n 算法一样，仅仅考 虑每个任务的最小完成时间，而没有满足任务的q o s 需求和资源的动态特性，没 有追求资源的使用率和资源的负载情况。 3 1 3s u f f e r a g e 调度算法 s u f f e r a g e 调度算法是基于损失度最小的原则，从任务未调度到某资源带来的 损失程度的角度来分析调度策略。在拨打测试系统中，任务分为有截止期的任务 和没有截止期的任务。s u f f e r a g e 算法以任务截止期d e a d l i n e 为导向，但不仅仅考 虑截止期这一个因素，还结合任务的完成时间，任务的优先级等因素，根据加权 1 7 平均值来决定任务调度的顺序。加权值由用户来设定，从而体现用户更关注于哪 个方面。 s u 侬= r a g e 调度算法的思想如下【4 】【5 】：d e a d l i n e ( t i ) 表示任务t i 所对应的 d e a d l i n e s ；l a s t ( t i ，h j ) 表示任务t i 在主机h j 上f 牖晚开始时间；s p a n ( t i ，h j ) 表 示任务t i 在主机坷当前负载下距离相应的最晚开始时间的跨度。该值在调度过程 中能正确反映出任务的紧迫程度。q d w e i g h t 表示任务优先级分组与任务d e a d l i n e 之间的权值；s c w e i g h t 表示任务的d e a d l i n e 约束值与任务的完成时间之间的权 值。 l a s t ( t i ，h j ) = d e a d l i n e ( t i ) e x c ( t i ，h j ) ； s p a n ( t i ，h j ) = l a s t ( t i ，h j ) 一s t a r t ( h j ) = d e a d l i n e ( t i ) c o m p ( t i ，h j ) ； 算法思想伪代码如下： f u n c t i o ns u f f c r a g e s c h c d u l i n g ( m e t a - t a s km ) f o ra l lt a s kt ii nm i f ( d e a d l i n e ( t i ) ) a d dt ii n t od e a d l i n e q u e u e ； e l s ea d dt ii n t on o r m a l q u e u e ； 将任务根据有否d e a d l i n e 约束进行划分 d ot h ep r ig r o u pi n g ； 根据任务优先级分组思想对任务进行划分 f o ra l lt a s kt ii