基于效益函数的软件分布式自动化测试调度算法研究

摘要：该文以分布式软件持续质量保证思想为基础，对软件分布式自动化测试平台的任务调度算法进行了讨论分析，发现其存在的问题。通过引入三种效益函数并结合测试任务调度的特点，提出了新的改进算法，文章给出了改进算法的仿真实验以及评价。虽然新算法在性能上有所改进，但是仍存在不足之处，文章最后提出了今后改进的方向，以使调度算法进一步趋于完善。

关键词：软件质量；分布式软件测试；调度算法；效益函数

中图分类号：TP311文献标识码：A文章编号：1009-3044(2012)11-2502-04

A Study of Scheduling Algorithm for Distributed Automatic Software Testing Based on Utility Functions

XU Mei-yang, HONG Mei, QUE Shu, LI Hai-nu

(Computer Science College of Sichuan University, Chengdu 610065, China)

Abstract: This paper is based on distributed continuous software quality assurance. After discussing and analyzing the task scheduling algo? rithm for distributed automatic software testing platform, we find some problems. Considering three utility functions and the characteristics of testing task scheduling, a new improved algorithm is proposed. This paper gives simulation results and evaluation of improved algorithm. Although the new algorithm has improved the performance, there are still inadequacies. The last part of the paper concludes with a direc? tion for future improvements to make the scheduling algorithm becoming perfect.

Key words: software quality; distributed software testing;scheduling algorithm;utility function

随着社会的进步与发展,计算机早已渗透到了社会生活的各个方面。人们对于计算机软件质量的要求越来越高，软件技术发展日新月异，高性能的软件正日益运行在由操作系统、数据库系统以及大量复杂硬件组成的网络化平台中，这就使软件工程规模不断扩大，导致了软件测试任务呈几何数增长，从而使本地有限的资源无法在有限的时间内完成如此数量庞大的测试工作。为了解决大规模软件测试中时间与资源有限的问题，美国马里兰大学的Adam Porter教授与范德堡大学的Douglas Schmidt教授为此提出了软件分布式持续质量保障的思想[1]，该思想是以利用网络中的空闲资源来进行全天候的测试，用该思想建立起来的软件分布式自动化测试平台，很好地解决了时间与资源有限性的问题[2]。在测试平台中，测试任务调度算法作为其重要的组成部分，主要研究的是如何为任务与资源之间寻找最佳的匹配策略，管理和调度测试任务的执行，从而使测试资源得以合理利用，测试效率得以提高。该文分析并讨论了基于效益函数的测试调度算法的原理与实现方法。

1测试任务调度定义

测试平台将测试任务分配给测试资源进行执行的过程中，需要考虑各种因素[3]，任务调度算法就是基于考虑这些因素所实现的一种测试任务最优化划分的方案，因此任务调度算法的优劣性直接影响了软件测试平成测试任务的效率。

而平台任务调度算法的实质就是在有m个测试任务等待执行，有n个测试资源是可用的情况下，将m个测试任务以合理的顺序分配给n个测试资源端进行执行。现对任务调度算法中涉及到的定义说明如下：

1）测试工程（Test Project，TP）由测试人员所提交的一个关于测试对象的抽象描述，包括所有测试任务、测试脚本以及测试任务对测试资源的需求等。

2）测试任务（Test Task，TT）测试任务是经由任务划分模块划分完成后所形成的独立可分发调度的任务执行单元，是任务调度的基本单位。

3）测试用例（Test Case，TC）测试用例是为某个特殊目标而编制的一组测试输入、执行条件以及预期结果，以便测试某个程序路径或核实是否满足某个特定需求，体现了测试的方案、方法、技术和策略。内容包括测试目标、测试环境、输入数据、测试步骤、预期结果、测试脚本等。

4）测试脚本（Testing Script，TS）测试脚本是自动执行测试过程（或部分测试过程）的计算机可读指令。测试脚本可以被创建（记录）或使用测试自动化工具自动生成，或用某种高级语言编程来完成。

5）测试资源（Test Resources，TR）测试资源是由分布在不同地域的异构网络资源所组成的，是测试任务的执行端。测试资源是测试任务赖以执行的保证，平台拥有的测试资源的种类和数量越多，测试任务才能够更快更好的得到执行。

2现有任务调度算法

任务调度算法在分布式系统中的重要性显而易见，但是由于各个系统的任务性质之间的差别以及任务调度本身存在的复杂特点，提出一个普遍适用且高效的调度算法并非易事。下面列出了一些常见的任务调度算法[4]。

1）OLB（Opportunistic Load Balancing）随机负载平衡算法

该算法的主要思想是并不考虑待分配任务的执行时间的长短以及其对资源的需求，而直接把待分配任务随机地分配给任一个可用资源。该算法具有思想简单、调度效率高、一定程度上保证了负载平衡等优点，由于未考虑到待分配任务的需求以及任务的其他因素，当一个任务被分配给并不能满足其执行条件的资源时，该任务就无法得到顺利执行，从而导致测试任务的失败。

2）MCT（Minimum Completion Time）最早完成时间算法

MCT是以任意顺序分配作业到具有最早完成时间的节点上，而不考虑该节点上的计算资源是否对此作业具有最小执行时间，适合于要求快速响应的任务。该算法有可能因为被分配的任务占用资源时间过长而导致任务完成的代价过大，也就是比较浪费计算资源。

3）Min-Min（Minimum - Minimum computing time）算法和Max-Min (Maximum–Minimum completion time)算法

Min-Min算法首先将需要调度的作业组成一个作业集合，然后计算任务集内每个任务的最短完成时间。调度过程中，从作业集中选取最具有最短执行时间任务调度到使之最快完成的主机上执行，然后从任务集合中删除该任务，重复以上操作直到任务集为空。Max-Min算法同Min-Min算法非常类似，二者都需要计算每个任务在任何可用资源上的最早完成时间，不同的是Max-Min算法选择将最早完成时间最大的任务映射到对应的资源上。Min-Min算法和Max-Min算法的映射规则会使得更多任务映射到某一个或几个资源上，从而使得整个分布式系统中可用资源的负载不平衡。

3基于效益函数的测试调度算法

上节介绍的任务调度算法，并不能够完全解决任务调度所碰到的问题。最突出的就是现有的任务调度算法所处理的任务对象以及资源对象都是基于小数量的，而对于数量大的任务，现有算法并不能够较好的完成工作。如果将现有的任务调度算法直接应用到测试平台中，虽然能够完成测试任务的分配，但是由于其低下的效率，最终将导致测试平台中存在着大量的测试任务等待执行而造成测试任务的拥堵，而在测试任务执行端也会有大量的空闲资源未能够加以利用，从而使得测试任务的进度过慢。

因此，针对本平台中的任务调度的特点，需要有针对性地设计一种新的任务调度算法来解决上述问题。

3.1引入三种效益函数[5]

通过对上节介绍的任务调度算法进行研究，发现在min-min算法的基础上引入效益函数，可有效地对任务调度过程进行调节，使测试任务执行的效率得到较大提高。为此，引入了三种类型的效益函数：

3.1.1硬性级效益函数

time_utilityhard(m,n)=ì

(1)

此效益函数的含义是：

如果测试任务Tm无法在测试任务所规定的截止时间之前完成，那么将不会获得任何效益，如果能够成功完成，则其效益值为1。

其中，TCm,n指的是测试任务Tm在测试客户端资源Rn上的期待完成时间，TDm指的是测试任务Tm截止执行的时间。

3.1.2软性级效益函数

time_utilitysoft(m,n)=ì

(2)

此效益函数的含义是：

如果测试任务Tm无法在测试任务所规定的截止时间之前完成，使得执行时间超过了规定时间，那么其获得的效益值是按照一定的方式进行计算之后而获得的，并不是为0；而在测试任务能够成功的在其规定时间之内完成时，则其效益值为1。

其中函数中的TCm,n指的是测试任务Tm在测试客户端资源Rn上的期待完成时间，TDm指的是测试任务Tm的截止执行时间。λc是一个常数，满足λc>0。

3.1.3尽力级效益函数

time_utilitybest_effort(m,n)=e-λb*TCm,n

(3)

此效益函数的含义是：

如果测试任务Tm需要在一个很长的时间内才能够完成，那么测试任务会给资源带来一定的效益，但是并不会很多，但是假设测试任务能够在一个很短的时间内就可以完成，那么资源就会得到更大的效益。

其中的TCm,n指的是测试任务Tm在测试客户端资源Rn上的期待完成时间，λb是一个常数，满足条件λb>λc（λc是软性级效益函数中的常数）。

3.2改进的调度算法描述

在Min-Min算法的基础上，通过效益函数的引进，可以解决调度效率低下的问题。引进效益函数后的改进调度算法描述如下：

1）把待测任务集合中的任务分为三种[6]，以供调度算法进行调度：C1是具有硬性级的调度测试任务的集合，C2是具有软性级的调度测试任务的集合，C3是具有尽力级的调度测试任务的集合。

2）在对测试任务进行调度的时候，首先会调度C1中的测试任务，然后再调度C2中的测试任务，最后调度C3中的测试任务。

3）判断客户资源是否能够满足测试任务的测试需求，如果所有的客户资源均无法满足测试任务的需求，则放弃此测试任务的执行；如果存在资源能够满足测试任务的需求，则执行下一步；

4）由上节中所引入的三个效益函数来计算测试任务在所分配的客户资源上进行测试所能够获得的效益值，然后执行下一步；

5）如果同时存在很多资源能够满足待测试任务的执行条件，那么比较一下由哪一个资源进行测试能够得到最大的经济效益，然后选择将测试任务分配给能够得到最大效益的测试任务执行客户端，然后将该序列记录下来[7]；

6）对于效益值相同的序列对，则比较该两项测试任务执行时间的大小，然后选择将测试任务分配给执行时间小的测试资源进行执行；

7）反复执行步骤3-6，直到所有的测试任务均完成。

改进后的算法流程如图1所示。

4基于效益函数的测试调度算法实验验证和结果分析

该文的改进调度算法是在Min-Min算法的基础上改进得来的，为了验证改进调度算法的有效性，需要对算法进行性能评估，将改进算法与Min-Min算法的性能进行对比实验。

4.1实验环境介绍

本实验采用的是由澳大利亚墨尔本大学所开发的算法实验模拟器GridSim来完成对算法在各种情况下的性能模拟实验。Grid? Sim模拟器可以进行网格调度算法的模拟，用户通过使用模拟器所提供的method来完成模拟文件的编写，从而完成整个调度算法的实验模拟过程。

GridSim的模拟特性[8]：

1）从网络应用的模拟角度：在GridSim中使用的是虚拟程序，它通过理论计算来对应用的时间花销进行分析，从而能够更好的完成大量实验的模拟工作。

2）从网络中间件的模拟角度：在资源管理方面，GridSim为了更好的对资源的异构性进行模拟，提出了资源的“空间共享”以及“时间共享”的概念。在GridSim中，其信息服务与任务调度都是属于集中式的。

3）从网络资源的模拟角度：GridSim可以模拟计算能力和网络带宽。

4）从使用特性的角度：由于GridSim是基于SimJava来实现的，所以它使用的是纯Java语言。GridSim支持可视化并提供API，需要用户编程来实现网络环境的模拟工作。

4.2模拟实验步骤

1）创建网格资源点；

PE1=new PE(id，capability)；//创建资源对象。

PEList peList=new PEList( )；//创建资源列表对象

peList.add( PE1); //将资源加入列表

Machine machinel=newMachine(id，pelist)；//创建资源列表

2）创建资源与任务；

GridResource gridRes =new GridResource (name，baud rate，seed, resConfig，peakLoad，offPeakLoad，holidayLoad，Weekends，Holi? days)；//创建网格资源对象，参数分别表示资源名称、带宽、seed、资源特性、负载等信息。

Gridlet gridletl=new Gridlet(id，length，configuration，dependent)；//创建Gridlet对象，id表示任务号，length表示任务的计算量，con? figuration表示任务的配置要求，dependent表示任务的依赖属性。

3）编写任务调度算法，开始进行算法模拟实验；

class min-min extends GridSim //继承GfidSim类

{public void body()//在body()编写新算法

}

GridSim.startGridSimulation()；

4）模拟结束，输出任务完成情况。

private static void printGridletList(GridletList list)；

4.3模拟实验结果分析

在本次实验中，为了与传统min-min算法进行比较，GridSim随机构造了m个任务和n个资源，其中任务共分为三大类：硬性级时效性任务、软性级时效性任务以及尽力级时效性任务。在每次运行程序的时候，可以通过命令行参数来设置任务数目，以及任务中所需要的配置参数。设置任务数为500，资源数为250，该情况下任务调度情况的模拟实验结果如图2所示：

图2测试任务调度的时间对比

从图中可以看出，两种算法均能够完成调度任务，但是由于在改进算法中考虑了任务的执行效益，相比于传统min-min算法，改进调度算法能够更好的完成任务的调度，表现出了相对于min-min算法更好的性能。

5结束语

该文通过引入效益函数，使传统的任务调度算法性能上得到了一定的改进，但是基于异构网络的新特性，该改进算法仍有不足之处，还有许多问题需要解决。这些问题主要包含以下几个方面：

1）有关分布式持续质量保证方面的研究还有待深化，基于此思想的分布式自动化测试调度算法还有待完善，比如测试任务的划分以及测试任务的结果的分析与收集等。

2）由于异构网络的复杂性，对于执行失败的任务，有必要分析其原因，如何收集信息并正确的定位出错原因也有待研究。

3）对于大任务量的实时状态以及任务结果如何做到快速查询也是亟待解决的问题之一。

4）由GridSim模拟器试验可以看出，虽然本hg文中的改进算法有效的提高了任务的调度效率，但是由于数据的不均衡性，使得性能并没有达到预想的效果，且算法的动态性适应也不足，因此对于任务调度算法仍需进一步研究。

（下转第2520页）

参考文献：

[1] Memon,A.Porter,C.Yilmaz,A.Nagarajan,D.C.Schmidt,andB.Natarajan.Skoll:Distributed Continuous Quality Assurance[C]//Proceedings of the 26th IEEE/ACM,International Conference on Software Engineering, (Edinburgh, Scotland), IEEE/ACM,2004.

[2]石柱.软件质量管理[M].北京:航空工业出版社,2003.

[3]闫会强,许静.分布式软件测试系统的设计与实现[J].南开大学学报:自然科学版,2003,36(4):50.

[4]李国微,王洪亚.分布式实时数据库并发控制[J].小型微型计算机系统,2003,24(6):1021-1024.

[5]王志平,熊光泽.实时调度算法研究[J].电子科技大学学报, 2000,29(2) :205- 208.

[6]曲绍云.分布式异构系统中任务调度问题的研究[D].青岛:青岛大学,2005.

[7]王岁花.一种新型快速排序算法的设计与实现[J].河南师范大学学报,2002(2).

[8]孟宪福.分布式环境下任务调度模型研究[J].大连理工大学学报, 2006(6).