摘要：该文以分布式软件持续质量保证思想为基础，对软件分布式自动化测试平台的任务调度算法进行了讨论分析，发现其存在的问题。通过引入三种效益函数并结合测试任务调度的特点，提出了新的改进算法，文章给出了改进算法的仿真实验以及评价。虽然新算法在性能上有所改进，但是仍存在不足之处，文章最后提出了今后改进的方向，以使调度算法进一步趋于完善。
关键词：软件质量；分布式软件测试；调度算法；效益函数
随着社会的进步与发展，计算机早已渗透到了社会生活的各个方面。人们对于计算机软件质量的要求越来越高，软件技术发展日新月异，高性能的软件正日益运行在由操作系统、数据库系统以及大量复杂硬件组成的网络化平台中，这就使软件工程规模不断扩大，导致了软件测试任务呈几何数增长，从而使本地有限的资源无法在有限的时间内完成如此数量庞大的测试工作。为了解决大规模软件测试中时间与资源有限的问题，美国马里兰大学的Adam Porter教授与范德堡大学的Douglas Schmidt教授为此提出了软件分布式持续质量保障的思想，该思想是以利用网络中的空闲资源来进行全天候的测试，用该思想建立起来的软件分布式自动化测试平台，很好地解决了时间与资源有限性的问题。在测试平台中，测试任务调度算法作为其重要的组成部分，主要研究的是如何为任务与资源之间寻找最佳的匹配策略，管理和调度测试任务的执行，从而使测试资源得以合理利用，测试效率得以提高。该文分析并讨论了基于效益函数的测试调度算法的原理与实现方法。
1、测试任务调度定义
测试平台将测试任务分配给测试资源进行执行的过程中，需要考虑各种因素，任务调度算法就是基于考虑这些因素所实现的一种测试任务最优化划分的方案，因此任务调度算法的优劣性直接影响了软件测试平台完成测试任务的效率。
而平台任务调度算法的实质就是在有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、现有任务调度算法
任务调度算法在分布式系统中的重要性显而易见，但是由于各个系统的任务性质之间的差别以及任务调度本身存在的复杂特点，提出一个普遍适用且高效的调度算法并非易事。下面列出了一些常见的任务调度算法。
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算法的映射规则会使得更多任务映射到某一个或几个资源上，从而使得整个分布式系统中可用资源的负载不平衡。
