基于动态优先级的测试任务抢占调度算法

丁　超, 唐力伟, 邓士杰

(军械工程学院火炮工程系, 河北 石家庄 050000)



基于动态优先级的测试任务抢占调度算法

丁超, 唐力伟, 邓士杰

(军械工程学院火炮工程系, 河北 石家庄 050000)

基于部队现有装备保障模式,难以满足日趋复杂的测试需求,存在着测试效率偏低、测试周期过长的现象。因此综合考虑任务的时间属性和价值属性,定量分析任务的执行紧迫性、价值密度和资源负载均衡性等因素,提出了应用于任务执行初始时刻的动态优先级分派策略(dynamicpriorityassignment,DPA)和任务执行过程中的抢占调度策略(taskpreemption,TP),即基于动态优先级的测试任务抢占调度算法(testtaskpreemptiveschedulingalgorithmbasedondynamicpriority,TTPSADP),实现了针对现有自动测试系统(automatictestsystem,ATS)价值收益、任务执行成功率和资源负载均衡的综合优化。

自动测试系统; 动态优先级; 任务抢占; 调度算法

0　引　言

在部队日常的装备保障活动中,一旦面临突发保障任务,时间紧迫、任务繁重,基于部队现有装备保障模式难以满足骤增的测试需求[1]。因此,依托现有测试资源,合理排序测试任务,增强任务执行的并行化水平,尽快恢复装备的最佳作战能力,探索针对测试任务的动态调度是部队面临的一项突出难题。

近年来,考虑任务调度的诸多影响因素,如价值属性[2]、可调度性[3]、并行性[4]、柔性资源约束性[5]、最大保障时间[6]等,国内外学者提出了许多调度算法,如基于优先表的禁忌搜索算法[7]、任务优化算法[8]、基于资源推拉的调度算法[9]、多目标函数调度算法[10-12]、基于动态优先级分派的调度算法[1]等。其中部分研究考虑的影响因素比较单一,偏重的应用领域互有差异,限制了算法的应用。

着眼于部队装备保障实际中,分析问题存在的深层次原因,概括为以下两个方面:①测试任务价值属性和时间属性不对称。过于追求时间属性,保障紧迫性高的任务优先执行,提高任务执行的成功率,但可能会导致部分高价值的任务不能尽早执行,降低系统总的价值收益,推迟装备原有作战能力的恢复;过于强调价值收益,可能会使部分低价值的任务因得不到执行机会或被高价值任务抢占而错过截止期,降低任务执行的成功率,使装备无法恢复到最佳作战能力。②测试资源利用不均衡。在系统调用资源的过程中,测试能力强或排序靠前的资源往往会比能力弱或排序靠后的资源得到更多的调用机会,导致部分资源因频繁调用产生不必要的损耗,降低其使用寿命,影响自动测试系统(automatictestsystem,ATS)的测试能力。

本文依据部队装备保障特点,基于任务的价值属性和时间属性,综合考虑影响任务执行的多个关键因素,提出了面向任务执行初始时刻的动态优先级分派策略(dynamicpriorityassignment,DPA),保证任务执行初始时刻的最优调度;提出了面向任务执行过程中的任务抢占调度策略(taskpreemption,TP),保证任务的平稳执行;最后基于以上策略,提出了面临突发保障任务的基于动态优先级的测试任务抢占调度算法(testtaskpreemptiveschedulingalgorithmbasedondynamicpriority,TTPSADP)，并进行了实例验证。

1　测试任务描述

1.1任务数学描述

汇总ATS面临的所有测试任务构成集合Tasks={E1, E2,…, Ei,…, Em};任务Ei包含n(i)个待测点(即测试子任务),构成子任务集合Ei={pi,1, pi,2, …, pi,j, …, pi,n(i)};每个子任务都具有7种属性,如图1所示。

图1　测试任务调度甘特图示例Fig.1　Test task scheduling Gantt chart

图1中,Di为任务Ei的绝对截止期;ti,j为子任务pi,j的理论执行时间;bi,j为pi,j的开始执行时刻;di为Ei的最大保障时间,即相对截止期;oi,j为pi,j的预期结束时刻,且oi,j=bi,j+ti,j;wi,j为pi,j的测试价值,若pi,j在Di前完成,即oi,j≤Di,则wi,j=1,否则wi,j=0;fi,j为pi,j的空闲时间,且fi,j=Di-bi,j-ti,j,本文仅考虑等待子任务的空闲时间。

假设子任务执行过程中的当前时刻为T,根据子任务在该时刻的不同状态,将其划分为以下3类:执行子任务,即正处在理论执行时间ti,j里的子任务pi,j;完成子任务,即已经执行完毕,执行成功或失败的pi,j;等待子任务,即未获得执行机会而处于等待状态的pi,j,其中动态价值密度和执行紧迫性会随着等待子任务等待时间的增加而逐渐增大。

针对测试任务的动态调度问题,作出以下4点假设:①子任务在执行过程中不能中断;②子任务之间的切换时间很短,忽略不计;③子任务之间仅在资源占用上存在冲突,不存在其他关系;④单个测试资源在同一时刻只能匹配一个子任务pi,j,单个pi,j在同一时刻也只能匹配一种测试资源。

1.2测试资源匹配

汇总ATS内部所有可用测试资源构成集合resource={r1, r2, …, rk, …, rl};resource中的资源全部为柔性资源(flexibleresource,FR)[13],即单个资源具备多种测试能力,满足多样化测试需求,如图2所示。以数字万用表为例,一套万用表可以实现交/直流电压、电流、电阻测量等多种测试功能。

图2　子任务与资源匹配关系Fig.2　Relationship of sub-task and resource matching

子任务与资源匹配矩阵M(m,n)×l,描述子任务与资源之间的匹配关系

(1)

式中，e(i,j),k表示资源rk对子任务pi,j的匹配结果,如果rk满足pi,j的测试需求,则e(i,j),k=1,否则e(i,j),k=0。

1.3任务调度模型

测试任务的有效执行就是在保证任务执行成功率的基础上,均衡利用测试资源,安排高价值任务优先执行,实现任务执行成功率、资源负载均衡和ATS价值收益的综合优化[14]。相比于日常的装备保障活动,ATS在面临突发保障任务时,要求在短时间内针对众多测试任务进行合理调度,为此需要考虑诸多影响因素:

(1) 动态性。在测试过程中,被测对象和测试环境不断变化,随时可能有新的任务加入,保持现有任务序列依次排序新加入的测试任务,可能会导致部分高价值任务无法尽快执行,降低ATS的价值收益;而打乱现有序列重新排序需要动态考虑多种复杂因素。

(2) 优先性。由于不同任务在测试过程中对恢复装备原有作战能力的影响程度不同,其执行时的优先级也会有差异;考虑到随时可能加入的新任务,依据优先级针对所有任务进行排序,在测试过程中容易引发混乱。

(3) 受限性。突发保障任务往往会在短时间内带来大量测试任务,ATS的内部资源难以同时满足所有测试需求,需要在有限资源的约束下,通过对任务进行排序依次调用所需资源。

测试任务调度模型为

(2)

(3)

(4)

(5)

(6)

(7)

(8)

式(2)表示测试任务执行过程中价值收益的最大化,αi,j,k表示子任务pi,j与资源rk的匹配程度,如果rk满足pi,j的需求,则αi,j,k=1,否则αi,j,k=0;若oi,j≤Di,则βi,j=1,否则βi,j=0。约束式(3)表示任意时刻的执行子任务所匹配的资源数目不能超过系统内部资源总量,其中St为任意时刻t正在执行的子任务集合,ri,j,k为子任务pi,j所需的资源rk。约束式(4)表示单个子任务在执行过程中最多能匹配一种资源。约束式(5)表示后续子任务pi,j只能在前序任务pi′,j′完成后才开始执行。约束式(6)表示任务的理论执行时间必须包含于最大保障时间内。约束式(7)表示任务Ei的绝对截止期是由该任务中最早开始执行的子任务开始时间bi,j和最大保障时间di决定的。约束式(8)表示子任务的预期结束时刻必须早于绝对截止期。

2　TTPSADP算法

2.1DPA策略

2.1.1DPA函数

动态价值密度(dynamic value density, DVD)。在装备保障活动中,ATS测试能力的实现依赖于任务的有效执行,但由于不同任务的重要性不同,系统在执行过程中的偏重也会有差异。为此考虑等待子任务的测试价值wi,j和空闲时间fi,j对其重要程度进行量化:

(9)

执行紧迫性(executive urgency, EU)。在针对子任务的调度过程中,不仅要实现ATS价值收益的最大化,更要保证任务执行的成功率。借鉴传统基于时间属性的任务调度策略[15],考虑等待子任务的理论执行时间ti,j与空闲时间fi,j评价任务的执行紧迫性:

(10)

综合考虑任务的DVD和EU,提出针对测试任务的动态优先级分派函数DPA,实现ATS价值收益与任务执行成功率的综合优化:

(11)

由式(9)和式(10)知,子任务pi,j的DVD和EU在任务执行初始时刻最小,分别为wi,j/(Di-ti,j)和ti,j/Di;由式(11)知,pi,j的最小优先级min DPAi,j(bi,j)=wi,j×ti,j/Di(Di-ti,j),即基本优先级(basic priority, BP)仅与其固有属性相关。

2.1.2负载均衡性

在任务与资源匹配过程中,考虑资源的负载均衡性(load balance, LB),就是在保证系统价值收益和任务执行成功率的基础上,依据匹配原则优先将测试能力弱的资源与子任务进行匹配。

匹配原则(match principle, MP)。首先统计资源的测试能力(test ability, TA),即一种测试资源可以满足几种任务需求,如式(12)所示;然后依据TA由小到大对资源进行排序,针对TA相同的资源按照编号由小到大排序。

(12)

2.1.3DPA流程

假设初始时刻,ATS面临的子任务均允许执行,其动态优先级分派流程DPA如下所示:

步骤 1依据BP对系统面临的所有子任务pi,j进行排序得到子任务集P3,优先级最高的pi,j首先与资源进行匹配。

步骤 2在对pi,j匹配的过程中,实时监控每个匹配后子任务的结束时刻是否错过了截止期,即oi,j≤Di;如果出现oi,j>Di的情况,进入步骤3,否则进入步骤4。

步骤 3遵循前移原则(move forward principle, MFP),对oi,j>Di的子任务pi,j前移,对在排序中位置发生变动的子任务重新进行资源匹配,返回步骤2。

假设等待前移的子任务pi,j为pi′,j′的后序任务,需要遵守的MFP原则为:①一般情况下,pi,j在排序中只能前移一个位置,即与pi′,j′互换位置;②当pi′,j′与pi,j所需的资源没有交集时,pi,j继续前移,一直移动到与pi,j所需资源存在交集的第一个子任务前;③当前移过程中出现死循环时,即pi,j前移后变为pi′,j′前序任务,pi,j满足oi,j≤Di,但oi′,j′>Di′;此时pi′,j′需要前移到pi,j前面,pi′,j′满足oi′,j′≤Di′,但oi,j>Di;针对该情况,pi,j继续前移,跳出死循环。

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

2.2TP策略

2.2.1执行颠簸与避免

在测试任务的执行过程中,随着任务执行时间的推移以及新任务的不断加入,可能出现两个或多个子任务由于动态优先级交替上升导致子任务之间反复抢占,即反复变化子任务在排序中的位置,称为任务执行的颠簸现象(task executive bump, TEB)[16]。

测试子任务之间的相互抢占会优化子任务的执行序列,提高测试效率,但需要消耗系统内部资源;而任务执行颠簸是一种过于频繁的任务间抢占,会额外消耗系统大量资源和时间,反而会降低测试效率。为避免可能出现的TEB现象,设置任务抢占阈值,避免优先级相差不大的子任务之间相互抢占,减少ATS资源的不必要损耗。子任务抢占阈值的设定主要有以下两种方式:①设定阈值系数C(C≥1),针对前序子任务pi′,j′和后序子任务pi,j,其优先级分别为DPAi′,j′和DPAi,j,只有当DPAi,j>C×DPAi′,j′时,子任务pi,j才允许抢占;②设定阈值增量ΔI(ΔI>0),只有DPAi,j>DPAi′,j′+ΔI时,子任务pi,j才允许抢占。

不论是阈值系数C还是阈值增量ΔI,其设定的准确性都需要通过大量的实际测试来验证。

2.2.2TP流程

假设子任务与资源匹配完成后,任务进入执行阶段。经过时间T,新的测试任务加入现有保障活动中,由于ATS对新加入的任务和等待子任务动态优先级的计算、比较需要一定时间,所以推迟适当时间到时刻Td,保证系统重新排序新加入的任务和等待子任务,实现任务的平稳执行。推迟时间Td的设定相似于任务抢占阈值的设定,设定推迟系数Cd(Cd≥1)或者推迟增量ΔT,推迟时间分别是Td=Cd×T或者Td=T+ΔT,如图1所示。测试任务抢占调度流程TP如下所示:

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

步骤 2计算、比较P5中所有子任务的动态优先级,按照优先级由大到小的顺序进行排序组成一个新的子任务集P6,优先级最高的子任务首先与资源进行匹配;

步骤 3～步骤5转入DPA策略中的步骤2～步骤4。

2.3算法流程

基于DPA策略和TP策略,实现了ATS针对装备保障活动的平稳执行,保证测试任务的最优调度。综合两类策略的具体流程,提出了TTPSADP流程，如图3所示。其中,灰色方框表示DPA策略,白色方框表示TP策略。

图3　TTPSADP算法流程Fig.3　TTPSADP algorithm flow

3　实例验证

基于文献[6]中针对装备的测试实例,相关数据如表1所示,验证TTPSADP算法的可行性。假设任务执行的初始时刻,只有任务E1和E2加入,经过时间T=6后,E3加入测试任务序列。

表1　测试任务实例相关数据

3.1DPA策略

步骤 1计算初始阶段测试任务E1和E2中所有子任务的基本优先级BP,如表2所示;以子任务p1,1为例,计算其基本优先级:

0.50×6/[30×(30-6)]=0.004 2

(13)

经过比较后排序,得到子任务集P3={p2,1, p1,2, p1,1, p2,4, p2,2, p2,3, p1,3, p1,4},对P3中子任务进行资源匹配,如表2所示。

步骤 2实时监控匹配过程中的子任务pi,j,全部满足oi,j≤Di,进入步骤3。

步骤 3任务与资源匹配完成,生成子任务集P7={p2,1, p1,2, p1,1, p2,4, p2,2, p2,3, p1,3, p1,4},开始执行任务,如图4所示。

表2　测试任务计算数据

图4　初始阶段测试任务调度甘特图Fig.4　Testing task scheduling Gantt chart in the initial phase

3.2TP策略

步骤 1设定推迟增量ΔT=2,则Td=T+ΔT=8;提取时刻Td后的等待子任务,与新加入的E3组成子任务集P5={p1,4,p1,3,p2,3,p3,1,p3,2,p3,3,p3,4}。

步骤 2计算P5中所有子任务的动态优先级DPA,如表2所示;以子任务p1,3为例,计算其动态优先级:

(0.90×16)/[(40-20)×(40-20-16)]=0.180 0

(14)

依据计算结果对子任务排序得到子任务集P6={p3,2,p3,1,p2,3,p3,3,p3,4,p1,3,p1,4}。

步骤 3实时监控匹配过程中子任务pi,j,发现p1,4的o1,4>D1。

步骤 4基于MFP原则前移子任务p1,4,更新子任务集P6={p3,2,p3,1,p1,4,p2,3,p3,3,p3,4,p1,3},新序列中的子任务全部满足oi,j≤Di,对P6中子任务进行资源匹配,如表2所示。

步骤 5任务与资源匹配完成,更新子任务集P7={p2,1,p1,2,p1,1,p2,4,p2,2,p3,2,p3,1,p1,4,p2,3,p3,3,p3,4,p1,3},其中p1,1已经完成,p2,1,p1,2,p2,4,p2,2正在执行;执行后续任务,如图5所示。

图5　执行阶段测试任务抢占甘特图Fig.5　Testing task preemption Gantt chart in the execution phase

4　结　论

综合考虑测试任务的DVD、EU和资源LB等影响因素,提出了TTPSADP:在任务执行的初始阶段依托DPA实现了任务的最优排序,在任务抢占阶段依托TP实现了任务间执行顺序的合理抢占,在保证任务执行成功率的基础上,实现了ATS价值收益和内部资源均衡利用的综合优化。

[1] Xia J L, Chen H, Yang B. A real-time tasks scheduling algorithm based on dynamic priority[J].ChineseJournalofCompu-ters, 2012, 35(12): 2685-2695. (夏家莉, 陈辉, 杨兵. 一种动态优先级实时任务调度算法[J].计算机学报, 2012, 35(12): 2685-2695.)

[2] Burus A, Prasad D, Bondavalli A, et al. The meaning and role of value in scheduling flexible real-time system[J].JournalofSystemsArchitecture, 2000, 46(4): 305-325.

[3] Balbastre P, Ripoll I, Crespo A. Minimum deadline calculation for periodic real-time tasks in dynamic priority systems[J].IEEETrans.onComputers, 2008, 57(1): 96-109.

[4] Liang X, Li X S, Yu J S. Research on the task schedule algorithm based on the GA[J].JournalofElectronicMeasurementandInstrument,2009,23(2):19-24.(梁旭,李行善,于劲松.基于遗传算法的并行测试调度算法研究[J].电子测量与仪器学报,2009,23(2): 19-24.)

[5] Huang M M,Luo R G． Study on flexible-resource-constrained product development project scheduling[J].JournalofIndustrialEngineering/EngineeringManagement, 2010, 24(4): 143-148. (黄敏镁, 罗荣桂. 柔性资源约束下的产品开发项目优化调度研究[J]. 管理工程学报, 2010, 24(4): 143-148.)

[6] Wan M, Zhang F M, Fan X G. Two novel algorithm for equipment maintenance task scheduling in wartime[J].SystemsEngineeringandElectronics,2012,34(1):107-110.(万明,张凤鸣,樊晓光.战时装备维修任务调度的两种新算法[J].系统工程与电子技术,2012,34(1):107-110.)

[7] Bellenguez-Morineau O. Methods to solve multi-skill project scheduling problem[J].AQuarterlyJournalofOperationResearch, 2008, 6(1): 85-88.

[8] Wang Z Y, Yan X Q, Zhu Y, et al. An optimal method on dynamic maintenance task scheduling with subject taken into account[J].ActaArmamentarii,2009,30(2):252-256.(王正元,严小琴,朱昱,等.一种考虑专业的动态维修任务调度的优化方法[J].兵工学报,2009,30(2):252-256.)

[9] Xu C J, Li A P, Liu X M. Multi-project scheduling algorithm based on resource push-pull technology[J].ComputerIntegratedManufacturingSystems, 2010, 16(6): 1246-1254. (徐赐军, 李爱平, 刘雪梅. 基于资源推拉技术的多项目调度算法[J]. 计算机集成制造系统, 2010, 16(6): 1246-1254.)

[10] Ben A M, Sassi M, Gossa M. Simultaneous scheduling of production and maintenance tasks in the job shop[J].InternationalJournalofProductionResearch, 2011, 49(13): 3891-3918.

[11] Safari E, Sadjadi S J. A hybrid method for flow shops scheduling with condition-based maintenance constraint and machines breakdown[J].ExpertSystemswithApplication, 2011, 38(3): 2020-2029.

[12] Hsu C J, Yang S J, Yang D L. Due-date assignment and optimal maintenance activity scheduling problem with linear deteriorating jobs[J].JournalofMarineScienceandTechnology, 2011, 19(1): 97-100.

[13] Lü X Z, Chen L, Yin J, et al. Maintenance task scheduling model considering rest time and its solving algorithm[J].ActaArmamentarii,2014,35(12):2116-2123.(吕学志,陈乐,尹健,等.考虑休息的维修任务调度模型及其求解算法[J].兵工学报,2014,35(12):2116-2123.)

[14] Wang X, Yan J L. Evaluation function-based dynamic collaboration task scheduling algorithm[J].JournalofHuazhongUniversityofScienceandTechnology(NaturalScienceEdition), 2011, 39(10): 46-49. (王璇, 颜景龙. 基于评价函数的动态协同任务调度算法[J]. 华中科技大学学报(自然科学版), 2011, 39(10): 46-49.)

[15] Zhu Y, Song J S, Wang Z Y. Scheduling model of the battle equipment maintenance task based on the most support time[J].SystemsEngineeringandElectronics, 2007, 29(11): 1900-1903. (朱昱, 宋建社, 王正元. 一种基于最大保障时间的战时装备维修任务调度[J]. 系统工程与电子技术, 2007, 29(11): 1900-1903.)

[16] Jin H, Wang H A, Wang Q, et al. An improved least-slack-first scheduling algorithm[J].JournalofSoftware, 2004, 15(8): 1116-1123. (金宏, 王宏安, 王强, 等. 改进的最小空闲时间优先调度算法[J]. 软件学报, 2004, 15(8): 1116-1123.)

Testtaskpreemptiveschedulingalgorithmbasedondynamicpriority

DINGChao,TANGLi-wei,DENGShi-jie

(Department of Artillery Engineering, College of Ordinance Engineering, Shijiazhuang 050000, China)

Thereisaphenomenonoflowtestefficiencyandlongcycleundertheexistingequipmenttestmodelinthearmy,whichishardtosatisfytheincreasinglycomplextestrequirements.Consideringthetimeandvalueattributesandqualitativeanalysisofthetaskexecutionurgency,valuedensityandresourceloadbalancing,thetacticsofdynamicpriorityassignment(DPA)andtaskpreemption(TP),whichisusedinthebeginningoftaskexecution,arestudiedtoachievethecomprehensiveoptimizationofthevaluegains,taskexecutionsuccessrateandresourceloadbalancingoftheautomatictestsystem(ATS),namelythetesttaskpreemptiveschedulingalgorithmbasedondynamicpriority(TTPSADP).

automatictestsystem(ATS);dynamicpriority(DP);taskpreemption(TP);schedulingalgorithm

2015-11-04；

2016-01-11；网络优先出版日期：2016-05-12。

TP316

ADOI:10.3969/j.issn.1001-506X.2016.09.16

丁超(1990-),男,博士研究生,主要研究方向为自动测试系统设计与应用。

E-mail:duncan1119@163.com

唐力伟(1961-),男,教授,博士,主要研究方向为自动测试系统、机械测试及性能检测与故障诊断。

E-mail:tom5157@163.com

邓士杰(1982-),男,讲师,博士,主要研究方向为故障诊断及自动测试系统。

E-mail:13700317750@163.com

网络优先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160512.0908.004.html