云测试平台任务调度方法

任进

（北京工业大学 北京100124）

云测试平台任务调度方法

任进

（北京工业大学 北京100124）

云计算是当前研究的热门领域，现如今，越来越多的应用被架设在了云计算平台中。而在软件开发的流程中，软件测试也是一个重要阶段，所以，将软件测试和云计算结合，对于提高软件测试的效率具有非常重要的意义。目前，云测试平台中的算法尚存在任务调度方式单一的问题。针对此问题，本文提出了一种任务调度模型，该模型采用遗传算法和改进型的min-min算法，对任务进行调度。实验表明，此算法在使用中具有非常好效果。

云计算；软件测试；遗传算法；改进型的min-min算法

现如今，云计算被越来越多的人熟知，但是对于云计算的定义并未达成一致，从广义的角度讲，云计算就是利用公共的计算机硬件资源，通过网络的方式对其进行配置和使用的模式[1]。云计算作为一场IT革命，已经影响到社会生活的方方面面[2]。云计算方面的投资也作为新兴的行业，得到了越来越多的关注，因而也涌现出了大量从事此服务的厂商。

1 云测试平台的意义和重要性

1.1 云计算平台的优势

1）强大的扩展性

云计算平台的显著特点就是所有的计算资源都在云端，这意味着计算资源是可以随时变化的。在需要增加的时候，可以通过增添云端设备的方式增加计算能力。使用起来非常的方便。

2）节约成本

在传统的计算集群中，需要通过添加物理设备的方式增强计算能力，这大大的增加了硬件采购成本，但是使用云平台可以都使用虚拟计算资源，大大节约了成本。

3）方便应用

通过云计算平台的支持的应用，可以很方便的分享给其他人员，因为对于实际的操作者来讲，云计算是一个虚拟的客户端，无论身在何地，处在何时都能够很方便的使用其他人的云应用。

1.2 云测试技术的优势

云测试技术实际上是基于云计算的应用，所以它有云计算的优点，但是云计算平台作为一种全新的测试平台，又有着自己独特的优势。

1）提高设备使用率

在测试阶段中，多设备和多终端的测试是重要内容之一，但是在使用的过程中，往往会遇到测试设备使用率低的问题：一台测试设备往往在使用1次之后，就不会再次被使用了。但是云测试技术克服了这样的问题，通过云分享功能，可以将此设备分享给其他测试人员，提高设备的利用率[3]。

2）提高效率

搭建测试环境在软件的测试环节中往往是非常耗时的一项内容，在云测试平台中有大量通用测试环境模板供测试人员选用，大大提高了测试工作的效率。

3）提高可靠性

测试设备故障也是在软件测试阶段遇到的棘手问题之一，遇到此问题往往会耗费很多宝贵时间。云测试平台具有非常低的故障率，即使出现故障也可以很快跳转到备用机中，这避免了设备故障给测试人员带来的难题。

2 云测试平台的研究现状

云测试平台推出之后，就受到了众多学者和企业的关注，作为一种新的测试模式，云测试技术具有非常重要的市场价值和研究价值。

在学术界，云测试平台是重要的研究方向之一，学者们纷纷的提出了对云测试的见解。有的学者就云测试技术和传统的测试技术进行了比较，提出了两者的联系和区别[4]，有学者通过对云测试的研究，提出云测试应该遵循的一般步骤，为后来者提供了理论支持。还有的学者提出了测试即服务（Testing as a Service，TaaS）的测试理念，这一理念对于软件测试具有强力的推动作用，并指导软件测试不应该各自为战，应将其作为一种服务提供给使用者[5]。

在工业界，云测试平台被越来越多的企业重视，他们纷纷的推出了自己的云测试平台。跨国公司IBM、惠普、微软、VMware先后推出了自己的云测试平台。国内的大型企业，中国银行软件中心还有中石化公司也推出了针对自己独特的业务特点的云测试平台。

3 云测试任务调度研究现状

任务调度是关于任务处理的一个研究热点，也是计算机中非常重要的研究内容。从之前的传统的单任务调度，多任务调度，到如今的基于网格计算的任务调度，云计算的任务调度，众多的学者一直都在丰富着任务调度的研究范围。针对云计算下的任务调度，众多的学者对其进行了各方面的研究。

在提高任务调度性能方面，众多学者提出了很多有益的算法，其中包括min-min算法，max-min算法，蚁群算法，人工鱼群算法，遗传算法，模拟去火算法等等，这些算法各不相同，但是都能提高任务调度的性能，这些算法在某些特定的场景中，有着优良的调度性能。

服务质量 （QoS）约束同样是当下的研究热点。Chan等人提出以网络带宽作为约束条件，通过加权方式调度任务[8]；以用户的多偏好作为约束，孙大为等人提出了基于免疫克隆的偏好多维QoS云计算调度优化算法[9]；以多工作流为前提，多QoS作为约束，Xu等人提出了工作流的多QoS调度策略[10]。

以经济利益为目标的任务调度研究，已在云计算得到了广泛的应用，更多的企业投入到了这个领域中。如何能够获得更大的经济利益，成为云计算厂家需要面对的问题之一，对此，学者们进行了广泛的研究。RaikumarBuyya等人以厂家的经济利益作为目标函数，调整体系结构和资源分配策略，通过分配器调度资源，以提高经济利益[11]；葛新等人提出以用户的需求作为约束，对要求高的用户分配计算能力强的资源，对于要求一般的用户分配相对计算能力相对低的资源，以此达到提高经济利益的目的[12]。

众多的学者在任务调度方向进行了非常广泛的研究，但针对云测试平台的任务调度，目前仍有较多空白。云测试平台中的任务相对于其他平台有着自己的特点，其独立性强，任务量大，时效性要求高。针对此需要有更有效的算法来完成云测试平台的任务调度工作。

4 云测试平台任务调度模型

4.1 任务调度模型

云测试平台是基于云计算的一种新型的测试技术，是将云计算的丰富研究成果应用于软件的测试环节中。在云测试平台任务调度模型中，任务调度器根据任务调度算法在任务集合中调度任务，然后将任务推送给云测试平台中的虚拟机。虚拟机通过任务执行器中的调度算法执行相应的任务，最后将任务全部执行完毕。上文描述的任务调度模型如下：

4.2 任务调度器

任务调度器的核心是使用遗传算法进行任务的分配。遗传算法自20世纪60年代初提出以来，已经被用在了很多领域。遗传算法是将达尔文的进化思想和孟德尔的遗传定律创造性的用于计算机领域中，创造出了一个全新的进化计算算法。

图1 任务调度模型

1）染色体的映射方案

染色体中基因的长度既是需要分配的任务数量，基因在染色体中的位置代表任务的编号。每个基因中内含的数字代表将要分配给的计算设备编号，使用记号Vi表示。在初始状态会生成一定数量的染色体。

表1 染色体映射方案

例如将10个子任务分配到5个资源上时，产生的一个染色体可能为{1，1，2，3，4，5，2，1，3，2}，此意味着任务在设备上执行。

2）适应度值函数的设计

适应度函数是在遗传算法中非常重要的部分。遗传算法通过适应度算法淘汰不良染色体，经过重复不断的迭代，得到最优解，所以适应度函数的设计非常关键。在此定义的目标函数为

在此函数中E（i，j）代表将j任务分配于i设备之后，完成任务所需要的时间。F（x）表示在m个设备中最后一个任务的完成时间，也就是n个任务全部完成的时间。在遗传算法中适应度函数的值决定染色体淘汰方向，由此可得适应度函数，就是目标函数的倒数，即将会淘汰适应度小的值。

3）染色体杂交

在遗传算法中，通过染色体的杂交获得更多新的染色体，此算法的杂交方案是将随机提取原种群中的两个染色体，选取其中的某个位置进行基因交换。

表2 S1染色体的基因序列

表3 S2染色体的基因序列

杂交步骤：

①随机选取一个值i（1＜=i=10）。

②S1染色体中以i为中心的，长度为染色体总长度五分之一的基因序列中的开头的位置为K，结尾的位置为M。

③将K之前的基因序和M之后的基因序全部复制到新染色体S′中。

④在S2中从头到尾搜索，在S′中插入S2中独有的基因，即S′中没有S2中有的基因，如果插入之后S’中基因序仍然没有补齐，则在空位填充S′中出现最少的基因。

由此产生了全新的染色体S1′。

按照杂交步骤演示如下：

A随机选择的数字为4。

B经过2-3步得到如下S1′：

表4 S1′染色体的基因序列

C经过4步得到的结果如下：

表5 S1′染色体的基因序列

S1′染色体的基因序列：

表6 S1′染色体的基因序列

4）变异操作

对S1，S2，S′求其适应度函数值，求适应度最小的染色体执行基因变异。变异的方案为随机选中染色体的一个基因，将其变为染色体中设备号出现最少的。变异后的S1′记为S′′，将此基因加入原始种群中。

经过变异之后的染色体S′′：

表7 S′′染色体的基因序列

5）再生成操作

重新利用适应度算法求在种群中所有染色体的适应度值，淘汰低适应度染色体，在此过程中需要保持种群数量的稳定。当算法遇到终止条件的任何一种时，算法即停止。算法的终止条件：

①算法迭代100次，染色体无变化。

②算法迭代次数超过15 00次。

③经过迭代，染色体收敛为同一染色体

在达到终止条件后，输出适应度值最高的染色体。

4.3 任务执行器

任务调度器将任务推送到云平台计算资源之后，VM任务执行器将通过一种改进的min-min算法执行对应的任务。

4.3.1 基本的min-min算法

min-min算法在任务调度方面有着实现简单，响应速度快等特点。

min-min算法的基本步骤如下：

1）将所有的任务填入任务执行表中

2）比较每个任务的执行时间，将执行时间最短的任务先执行。

3）任务执行完毕后，将此任务从任务执行表中删除

4）重复进行2-3步，直到任务表为空为止。

4.3.2 云计算环境下改进min-min算法

虽然min-min的优点非常的明显，但是它也存在着不足，比如长任务会处于长时间等待状态，为了解决此问题，提出了一种带权值的改进型的minmin调度算法。

基本步骤如下：

1）将所有任务记入任务列表中，并且记录他们的预计执行时间，记为ExceptTime（i）

2）通过公式计算每个任务的权值

Q（i）=TimeExcept（i）/WaitTime（i）

其中TimeExcept（i）代表第i个任务的预计执行时间，WaitTime（i）代表此任务的等待时间。将其更新到权值表中。

3）通过基本min-min算法调度在第2步得到的带权值的任务。将权值最小的任务执行。

4）将执行完毕的任务从任务表和权值表中删除。

5）更新权值表和任务列表，

6）重复2-5步，直到任务表为空。

到此算法结束。

5 实验与结果分析

5.1 实验环境与数据

为了获得更好的实验结果，硬件环境采用一台8核i7处理器，采用16 G内存，在其上虚拟出8台主机，其中一台主机拥有一个核心，2 G内存和30 G硬盘空间。软件的回归测试和验收测试是在软件测试中非常关键的测试阶段，本文将针对这两个阶段进行测试。被测软件分别是校邮箱服务平台和校OA服务平台。测试主要任务也分为WEB测试和后台API测试。其中WEB前端全部使用Selenium编写，后台API的测试用例全部使用Java语言编写。

测试用例分布如下：

表8 测试用例分布

5.2 实验结果与分析

实验中采用两种调度方式，一种是传统任务调度方式，即先来先服务进行调度，另一种即是本文提出的任务调度方案，分别对其结果进行了统计和分析。

实验结果如表9、10所示：

表9 邮件服务平台测试花费时间统计结果/min

表10 OA服务平台测试花费时间统计结果/min

通过对实验数据的分析，可以看到，文中提出的云平台下的任务调度算法大大的提高了任务调度效率，其中在回归测试阶段云平台任务调度比传统任务调度在花费时间方面减少了52%、48%，在验收阶段减少了22%、36%；当测试用例全部是WEB前端时，花费时间减少了48%、50%，而测试用例全部是API后台时，花费时间减少了56%、52.5%。从实验数据分析可以看到，测试用例越多，本算法的优势越明显，符合预期。由于文中提出的算法在初始阶段需要花费大量的时间，所以任务少时本算法优势不明显。通过观察可以发现在 API后台测试的效果优于WEB前端测试，经过分析发现，WEB前端测试依赖浏览器等第三方软件，由此带来了不必要的时间耗费，而API后台测试，则完全独立，不会有此问题。

6 结 论

文中基于遗传算法和改进min-min算法提出一种云测试平台的任务调度模型，从前文的分析中，可以清晰的看到此任务模型可以提高云平台的任务调度效率。但是在研究的过程中也发现一些问题，即算法的启动时间相对较长等问题，今后将继续关注对此问题，并对其进行解决。

[1]Saurabh KumarGarg，SteveVersteeg，Rajkumar Buyya，et al.A framework for ranking of cloud computing services[J].Future generations computer systems，2013，29（4）:1012-1023.

[2]Murugesan，San.Cloud Computing:The new normal [J].Computer，2013，46（1）:77-79.

[3]白虹桥.基于云计算的软件测试技术探索与研究[J].信息技术与信息化，2015（3）：65-66.

[4]雷万保.云计算环境下的软件测试研究[J].信息化研究，2013（1）:1-3.

[5]Lian Y，Wei-Tek T，Xiangji C，et al.Testing as a serviceovercloud:FifthIEEEInternationalSymposiumonServiceOrientedSystemEngineering（SOSE），Nanjing，2010[C].2010.

[6]林奇.基于云计算的测试管理予台[J].科技传播, 2013（17）:227-228.

[7]黄璐.基于遗传算法的云计算任务调度算法研究[D].厦门：厦门大学，2014.

[8]Chauhan S S'Joshi R C.A heuristic for QoS based independent task scheduling in gridenvironment[C]// Industrial and Information Systems(ICIIS),2010 International Conferenceon.IEEE,2010:102-106.

[9]孙大为,常桂然,李凤云，等.一种基于免疫克隆的偏好多维QoS云资源调度优化算法[J].电子学报，2011（8）：1824-1831.

[10]Xu M，Cui L，Wang H,et al.A multiple QoS constrained scheduling strategy of multipleworkflows for cloud computing[C]//Parallel and Distributed Processing with Applications,2009 IEEE International Symposium on.IEEE,2009:629-634.

[11]Buyya R,Yeo C S，Venugopal S,et al.Cloud computing and emerging IT platforms:Vision,hype, and reality for delivering computing as the 5th utility[J].Future Generation computersystems，2009，25（6）:599-616.

[12]葛新，陈华平，杜冰，等.基于云计算集群扩展中的调度策略研究 [J].计算机应用研究，2011，28（3）:995-997.

[13]李乔，柯栋梁，王小林.云测试研究现状综述[J].计算机应用研究，2012，29（12）：4403.

[14]Masayuki Hirayama,Osamu Mizuno,TohruKikuno.Analysis of software test item Generation-Comparison between High Skilled and Low Skilled Engineers[J].计算机科学技术学报：英文版，2005，20（2）:250-257.

[15]李建锋,彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用，2011（1）：184-186.

The module of task schedule in cloud testing platform

REN Jin
（Beijing University of Technology，Beijing 100124，China）

The study of Cloud Computing is one of the most popular study aspects.More and more appliances are deployed in Cloud.It is of great significance for the increase of Software Test efficiency that we deploy the applicationsof Software Testing， which are very momentous during software development，in Cloud.But the method of Task Schedule is very simple in Testing cloud.In order to solve the problem，we explored one module that use genetic algorithm and improved min-min algorithm to arrange tasks.Experimental results show that the module truly improves the efficiency of Software Test.

cloud computing；software testing；genetic algorithm；improve min-min

TN0

：A

：1674－6236（2017）03-0056-05

2016-01-18稿件编号：201601139

任 进（1988—），男，山西吕梁人，硕士。研究方向：云计算，软件测试。