1.动态优先级分派策略

在动态优先级分派策略中，考虑等待子任务的动态价值密度和执行紧迫性，得到DPA分派函数；在此基础上考虑资源的负载均衡，设计了DPA分派流程。

（1）动态价值密度（dynamic value density，DVD），不同测试任务具有不同的价值比重，系统在执行过程中的偏重也会有差异，通过量化任务的维修价值wi′，j′和空闲时间fi′，j′实时掌控其DVD的动态变化，见式（5－50）：

（2）执行紧迫性（executive urgency，EU），在测试过程中，不仅要实现系统价值收益的最大化，更要确保任务执行的成功率。针对时间属性的任务调度策略［89］进行改进，综合考虑任务的理论执行时间ti′，j′和空闲时间fi′，j′等影响因素，提出一种新的针对任务执行紧迫性的评价指标，见式（5－51）：

（3）动态优先级分派函数，综合考虑测试任务的动态价值密度和执行紧迫性，提出一种针对测试任务的DPA函数，见式（5－52）：

由式（5－52）得到子任务的最小优先级min－DPAi′，j′（bi′，j′）＝wi′，j′×ti′，j′/［Di′（Di′－ti′，j′）］，即基本优先级（basic priority，BP）。

（4）负载均衡性（load balance，LB），就是将所有资源均衡分配给测试任务，避免出现部分资源过于调用频繁的情况。首先量化系统内部所有资源的测试能力（test ability，TA），即单个资源可以满足几种测试需求，见式（5－53）；然后依据测试能力针对资源进行排序；最后依据匹配原则（match principle，MP）进行资源调度。其中匹配原则就是优先考虑能力弱的资源，在多个资源能力相同的情况下，优先考虑任务更早执行的资源，在两者均相同的情况下，按照编号的先后顺序调用资源。

（5）假设初始时刻，所有子任务都允许执行，动态优先级分派流程如下所示。

步骤1　在初始时刻，依据基本优先级对所有子任务STi′，j′进行排序得到子任务集P3，其中N1＝N（1）＋N（2）＋…＋N（N），依据匹配原则安排BP最高的子任务优先匹配资源。

步骤2　在匹配过程中，实时监控系统内所有匹配后子任务的结束时刻oi′，j′是否错过了截止期Di′，如果oi′，j′＞Di′，则进入步骤3，否则进入步骤4。务抢占阈值的设定方式相同，设定推迟系数Cd（Cd≥1）或者推迟增量ΔT，推迟到的时刻分别是Td＝Cd×T或者Td＝T＋ΔT，如图5－16所示。

步骤3　在排序中依据前移原则（move forward principle，MFP）将错过截止期的子任务前移，对所有发生位置变动的子任务重新进行资源匹配，返回步骤2。

步骤4　子任务与资源匹配完成，生成子任务集P7，开始执行子任务。

假设需要前移的子任务STi2，j2最初为STi1，j1的后序任务，遵守的MFP如下所示。

①一般情况下，STi2，j2每次只能前移一个位置变为STi1，j1的前序子任务。

②当STi2，j2与STi1，j1的所需资源没有交集时，STi2，j2继续前移，一直移动到与其所需资源存在交集的第一个子任务前，变为该子任务的前序子任务。

③当前移过程中出现死循环时，即STi2，j2前移后变为STi1，j1前序任务，STi2，j2满足oi2，j2≤Di2，但oi1，j1＞Di1；基于MFP，此时STi1，j1需要前移到STi2，j2前面，STi1，j1满足oi1，j1≤Di1，但oi2，j2＞Di2；针对该情况，STi2，j2继续前移，跳出死循环。

2.测试任务抢占策略

（1）执行颠簸与避免。在任务的执行过程中，随着时间推移以及新的任务不断加入，多个子任务由于动态优先级交替上升导致任务之间出现频繁抢占的现象，称为任务执行颠簸（task executive bump，TEB）现象［90］。在实际测试过程中，为实现系统价值收益的最大化，任务之间的抢占行为十分必要；而TEB现象是一种过于频繁的任务间抢占行为，会额外消耗大量资源和时间，反而会降低任务执行效率。(www.daowen.com)

为避免可能出现的TEB现象，通过事先设置任务抢占阈值，避免优先级相差不大的子任务相互抢占，减少抢占的次数以及系统内部资源和测试时间的不必要损耗。依托大量实际的测试活动，合理设定阈值。

①阈值系数C（C＞1），设定子任务STi1，j1和STi2，j2的优先级分别为DPAi1，j1和DPAi2，j2，只有当DPAi2，j2＞C×DPAi1，j1时，子任务STi2，j2才允许执行抢占行为。

②阈值增量ΔI（ΔI＞0），只有DPAi2，j2＞DPAi1，j1＋ΔI时，STi2，j2才允许执行抢占行为。

（2）测试任务抢占流程。在任务执行阶段，假设经过了时间T，新的任务加入现有测试序列，由于系统对新加入子任务和等待子任务动态优先级的量化、比较需要一定时间，所以推迟适当时间到时刻Td，保证系统针对所有子任务的重新排序和测试活动的平稳执行。推迟时间的设定方式与任

步骤1　提取时刻Td后的所有等待子任务，与新加入的子任务组成子任务集P5。

步骤2　量化、比较P5中所有子任务的动态优先级，按照由大到小的顺序进行排序并组成子任务集P6。

步骤3～5　转入动态优先级分派流程中的步骤2～4。

3.任务抢占调度流程

综合动态优先级分派策略和测试任务抢占策略，提出了基于动态优先级的测试任务抢占调度算法的具体测试流程和开发思路，分别如图5－18和图5－19所示。首先在初始时刻量化所有子任务的基本优先级，依据动态优先级分派策略实现子任务与资源的匹配；在任务执行阶段突遇新任务，短时间内量化、比较所有等待子任务和新任务的动态优先级，依据测试任务抢占策略重新进行资源匹配。

图5-18　测试任务抢占调度算法流程

图5-19　测试任务抢占调度算法开发思路