基于動態(tài)優(yōu)先級的測試任務搶占調(diào)度算法

丁　超, 唐力偉, 鄧士杰

(軍械工程學院火炮工程系, 河北 石家莊 050000)

?

基于動態(tài)優(yōu)先級的測試任務搶占調(diào)度算法

丁超, 唐力偉, 鄧士杰

(軍械工程學院火炮工程系, 河北 石家莊 050000)

基于部隊現(xiàn)有裝備保障模式,難以滿足日趨復雜的測試需求,存在著測試效率偏低、測試周期過長的現(xiàn)象。因此綜合考慮任務的時間屬性和價值屬性,定量分析任務的執(zhí)行緊迫性、價值密度和資源負載均衡性等因素,提出了應用于任務執(zhí)行初始時刻的動態(tài)優(yōu)先級分派策略(dynamicpriorityassignment,DPA)和任務執(zhí)行過程中的搶占調(diào)度策略(taskpreemption,TP),即基于動態(tài)優(yōu)先級的測試任務搶占調(diào)度算法(testtaskpreemptiveschedulingalgorithmbasedondynamicpriority,TTPSADP),實現(xiàn)了針對現(xiàn)有自動測試系統(tǒng)(automatictestsystem,ATS)價值收益、任務執(zhí)行成功率和資源負載均衡的綜合優(yōu)化。

自動測試系統(tǒng); 動態(tài)優(yōu)先級; 任務搶占; 調(diào)度算法

0　引　言

在部隊日常的裝備保障活動中,一旦面臨突發(fā)保障任務,時間緊迫、任務繁重,基于部隊現(xiàn)有裝備保障模式難以滿足驟增的測試需求[1]。因此,依托現(xiàn)有測試資源,合理排序測試任務,增強任務執(zhí)行的并行化水平,盡快恢復裝備的最佳作戰(zhàn)能力,探索針對測試任務的動態(tài)調(diào)度是部隊面臨的一項突出難題。

近年來,考慮任務調(diào)度的諸多影響因素,如價值屬性[2]、可調(diào)度性[3]、并行性[4]、柔性資源約束性[5]、最大保障時間[6]等,國內(nèi)外學者提出了許多調(diào)度算法,如基于優(yōu)先表的禁忌搜索算法[7]、任務優(yōu)化算法[8]、基于資源推拉的調(diào)度算法[9]、多目標函數(shù)調(diào)度算法[10-12]、基于動態(tài)優(yōu)先級分派的調(diào)度算法[1]等。其中部分研究考慮的影響因素比較單一,偏重的應用領(lǐng)域互有差異,限制了算法的應用。

著眼于部隊裝備保障實際中,分析問題存在的深層次原因,概括為以下兩個方面:①測試任務價值屬性和時間屬性不對稱。過于追求時間屬性,保障緊迫性高的任務優(yōu)先執(zhí)行,提高任務執(zhí)行的成功率,但可能會導致部分高價值的任務不能盡早執(zhí)行,降低系統(tǒng)總的價值收益,推遲裝備原有作戰(zhàn)能力的恢復;過于強調(diào)價值收益,可能會使部分低價值的任務因得不到執(zhí)行機會或被高價值任務搶占而錯過截止期,降低任務執(zhí)行的成功率,使裝備無法恢復到最佳作戰(zhàn)能力。②測試資源利用不均衡。在系統(tǒng)調(diào)用資源的過程中,測試能力強或排序靠前的資源往往會比能力弱或排序靠后的資源得到更多的調(diào)用機會,導致部分資源因頻繁調(diào)用產(chǎn)生不必要的損耗,降低其使用壽命,影響自動測試系統(tǒng)(automatictestsystem,ATS)的測試能力。

本文依據(jù)部隊裝備保障特點,基于任務的價值屬性和時間屬性,綜合考慮影響任務執(zhí)行的多個關(guān)鍵因素,提出了面向任務執(zhí)行初始時刻的動態(tài)優(yōu)先級分派策略(dynamicpriorityassignment,DPA),保證任務執(zhí)行初始時刻的最優(yōu)調(diào)度;提出了面向任務執(zhí)行過程中的任務搶占調(diào)度策略(taskpreemption,TP),保證任務的平穩(wěn)執(zhí)行;最后基于以上策略,提出了面臨突發(fā)保障任務的基于動態(tài)優(yōu)先級的測試任務搶占調(diào)度算法(testtaskpreemptiveschedulingalgorithmbasedondynamicpriority,TTPSADP)，并進行了實例驗證。

1　測試任務描述

1.1任務數(shù)學描述

匯總ATS面臨的所有測試任務構(gòu)成集合Tasks={E1, E2,…, Ei,…, Em};任務Ei包含n(i)個待測點(即測試子任務),構(gòu)成子任務集合Ei={pi,1, pi,2, …, pi,j, …, pi,n(i)};每個子任務都具有7種屬性,如圖1所示。

圖1　測試任務調(diào)度甘特圖示例Fig.1　Test task scheduling Gantt chart

圖1中,Di為任務Ei的絕對截止期;ti,j為子任務pi,j的理論執(zhí)行時間;bi,j為pi,j的開始執(zhí)行時刻;di為Ei的最大保障時間,即相對截止期;oi,j為pi,j的預期結(jié)束時刻,且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,本文僅考慮等待子任務的空閑時間。

假設(shè)子任務執(zhí)行過程中的當前時刻為T,根據(jù)子任務在該時刻的不同狀態(tài),將其劃分為以下3類:執(zhí)行子任務,即正處在理論執(zhí)行時間ti,j里的子任務pi,j;完成子任務,即已經(jīng)執(zhí)行完畢,執(zhí)行成功或失敗的pi,j;等待子任務,即未獲得執(zhí)行機會而處于等待狀態(tài)的pi,j,其中動態(tài)價值密度和執(zhí)行緊迫性會隨著等待子任務等待時間的增加而逐漸增大。

針對測試任務的動態(tài)調(diào)度問題,作出以下4點假設(shè):①子任務在執(zhí)行過程中不能中斷;②子任務之間的切換時間很短,忽略不計;③子任務之間僅在資源占用上存在沖突,不存在其他關(guān)系;④單個測試資源在同一時刻只能匹配一個子任務pi,j,單個pi,j在同一時刻也只能匹配一種測試資源。

1.2測試資源匹配

匯總ATS內(nèi)部所有可用測試資源構(gòu)成集合resource={r1, r2, …, rk, …, rl};resource中的資源全部為柔性資源(flexibleresource,FR)[13],即單個資源具備多種測試能力,滿足多樣化測試需求,如圖2所示。以數(shù)字萬用表為例,一套萬用表可以實現(xiàn)交/直流電壓、電流、電阻測量等多種測試功能。

圖2　子任務與資源匹配關(guān)系Fig.2　Relationship of sub-task and resource matching

子任務與資源匹配矩陣M(m,n)×l,描述子任務與資源之間的匹配關(guān)系

(1)

式中，e(i,j),k表示資源rk對子任務pi,j的匹配結(jié)果,如果rk滿足pi,j的測試需求,則e(i,j),k=1,否則e(i,j),k=0。

1.3任務調(diào)度模型

測試任務的有效執(zhí)行就是在保證任務執(zhí)行成功率的基礎(chǔ)上,均衡利用測試資源,安排高價值任務優(yōu)先執(zhí)行,實現(xiàn)任務執(zhí)行成功率、資源負載均衡和ATS價值收益的綜合優(yōu)化[14]。相比于日常的裝備保障活動,ATS在面臨突發(fā)保障任務時,要求在短時間內(nèi)針對眾多測試任務進行合理調(diào)度,為此需要考慮諸多影響因素:

(1) 動態(tài)性。在測試過程中,被測對象和測試環(huán)境不斷變化,隨時可能有新的任務加入,保持現(xiàn)有任務序列依次排序新加入的測試任務,可能會導致部分高價值任務無法盡快執(zhí)行,降低ATS的價值收益;而打亂現(xiàn)有序列重新排序需要動態(tài)考慮多種復雜因素。

(2) 優(yōu)先性。由于不同任務在測試過程中對恢復裝備原有作戰(zhàn)能力的影響程度不同,其執(zhí)行時的優(yōu)先級也會有差異;考慮到隨時可能加入的新任務,依據(jù)優(yōu)先級針對所有任務進行排序,在測試過程中容易引發(fā)混亂。

(3) 受限性。突發(fā)保障任務往往會在短時間內(nèi)帶來大量測試任務,ATS的內(nèi)部資源難以同時滿足所有測試需求,需要在有限資源的約束下,通過對任務進行排序依次調(diào)用所需資源。

測試任務調(diào)度模型為

(2)

(3)

(4)

(5)

(6)

(7)

(8)

式(2)表示測試任務執(zhí)行過程中價值收益的最大化,α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)表示任意時刻的執(zhí)行子任務所匹配的資源數(shù)目不能超過系統(tǒng)內(nèi)部資源總量,其中St為任意時刻t正在執(zhí)行的子任務集合,ri,j,k為子任務pi,j所需的資源rk。約束式(4)表示單個子任務在執(zhí)行過程中最多能匹配一種資源。約束式(5)表示后續(xù)子任務pi,j只能在前序任務pi′,j′完成后才開始執(zhí)行。約束式(6)表示任務的理論執(zhí)行時間必須包含于最大保障時間內(nèi)。約束式(7)表示任務Ei的絕對截止期是由該任務中最早開始執(zhí)行的子任務開始時間bi,j和最大保障時間di決定的。約束式(8)表示子任務的預期結(jié)束時刻必須早于絕對截止期。

2　TTPSADP算法

2.1DPA策略

2.1.1DPA函數(shù)

動態(tài)價值密度(dynamic value density, DVD)。在裝備保障活動中,ATS測試能力的實現(xiàn)依賴于任務的有效執(zhí)行,但由于不同任務的重要性不同,系統(tǒng)在執(zhí)行過程中的偏重也會有差異。為此考慮等待子任務的測試價值wi,j和空閑時間fi,j對其重要程度進行量化:

(9)

執(zhí)行緊迫性(executive urgency, EU)。在針對子任務的調(diào)度過程中,不僅要實現(xiàn)ATS價值收益的最大化,更要保證任務執(zhí)行的成功率。借鑒傳統(tǒng)基于時間屬性的任務調(diào)度策略[15],考慮等待子任務的理論執(zhí)行時間ti,j與空閑時間fi,j評價任務的執(zhí)行緊迫性:

(10)

綜合考慮任務的DVD和EU,提出針對測試任務的動態(tài)優(yōu)先級分派函數(shù)DPA,實現(xiàn)ATS價值收益與任務執(zhí)行成功率的綜合優(yōu)化:

(11)

由式(9)和式(10)知,子任務pi,j的DVD和EU在任務執(zhí)行初始時刻最小,分別為wi,j/(Di-ti,j)和ti,j/Di;由式(11)知,pi,j的最小優(yōu)先級min DPAi,j(bi,j)=wi,j×ti,j/Di(Di-ti,j),即基本優(yōu)先級(basic priority, BP)僅與其固有屬性相關(guān)。

2.1.2負載均衡性

在任務與資源匹配過程中,考慮資源的負載均衡性(load balance, LB),就是在保證系統(tǒng)價值收益和任務執(zhí)行成功率的基礎(chǔ)上,依據(jù)匹配原則優(yōu)先將測試能力弱的資源與子任務進行匹配。

匹配原則(match principle, MP)。首先統(tǒng)計資源的測試能力(test ability, TA),即一種測試資源可以滿足幾種任務需求,如式(12)所示;然后依據(jù)TA由小到大對資源進行排序,針對TA相同的資源按照編號由小到大排序。

(12)

2.1.3DPA流程

假設(shè)初始時刻,ATS面臨的子任務均允許執(zhí)行,其動態(tài)優(yōu)先級分派流程DPA如下所示:

步驟 1依據(jù)BP對系統(tǒng)面臨的所有子任務pi,j進行排序得到子任務集P3,優(yōu)先級最高的pi,j首先與資源進行匹配。

步驟 2在對pi,j匹配的過程中,實時監(jiān)控每個匹配后子任務的結(jié)束時刻是否錯過了截止期,即oi,j≤Di;如果出現(xiàn)oi,j>Di的情況,進入步驟3,否則進入步驟4。

步驟 3遵循前移原則(move forward principle, MFP),對oi,j>Di的子任務pi,j前移,對在排序中位置發(fā)生變動的子任務重新進行資源匹配,返回步驟2。

假設(shè)等待前移的子任務pi,j為pi′,j′的后序任務,需要遵守的MFP原則為:①一般情況下,pi,j在排序中只能前移一個位置,即與pi′,j′互換位置;②當pi′,j′與pi,j所需的資源沒有交集時,pi,j繼續(xù)前移,一直移動到與pi,j所需資源存在交集的第一個子任務前;③當前移過程中出現(xiàn)死循環(huán)時,即pi,j前移后變?yōu)閜i′,j′前序任務,pi,j滿足oi,j≤Di,但oi′,j′>Di′;此時pi′,j′需要前移到pi,j前面,pi′,j′滿足oi′,j′≤Di′,但oi,j>Di;針對該情況,pi,j繼續(xù)前移,跳出死循環(huán)。

步驟 4任務與資源匹配完成,生成子任務集P7,開始執(zhí)行任務。

2.2TP策略

2.2.1執(zhí)行顛簸與避免

在測試任務的執(zhí)行過程中,隨著任務執(zhí)行時間的推移以及新任務的不斷加入,可能出現(xiàn)兩個或多個子任務由于動態(tài)優(yōu)先級交替上升導致子任務之間反復搶占,即反復變化子任務在排序中的位置,稱為任務執(zhí)行的顛簸現(xiàn)象(task executive bump, TEB)[16]。

測試子任務之間的相互搶占會優(yōu)化子任務的執(zhí)行序列,提高測試效率,但需要消耗系統(tǒng)內(nèi)部資源;而任務執(zhí)行顛簸是一種過于頻繁的任務間搶占,會額外消耗系統(tǒng)大量資源和時間,反而會降低測試效率。為避免可能出現(xiàn)的TEB現(xiàn)象,設(shè)置任務搶占閾值,避免優(yōu)先級相差不大的子任務之間相互搶占,減少ATS資源的不必要損耗。子任務搶占閾值的設(shè)定主要有以下兩種方式:①設(shè)定閾值系數(shù)C(C≥1),針對前序子任務pi′,j′和后序子任務pi,j,其優(yōu)先級分別為DPAi′,j′和DPAi,j,只有當DPAi,j>C×DPAi′,j′時,子任務pi,j才允許搶占;②設(shè)定閾值增量ΔI(ΔI>0),只有DPAi,j>DPAi′,j′+ΔI時,子任務pi,j才允許搶占。

不論是閾值系數(shù)C還是閾值增量ΔI,其設(shè)定的準確性都需要通過大量的實際測試來驗證。

2.2.2TP流程

假設(shè)子任務與資源匹配完成后,任務進入執(zhí)行階段。經(jīng)過時間T,新的測試任務加入現(xiàn)有保障活動中,由于ATS對新加入的任務和等待子任務動態(tài)優(yōu)先級的計算、比較需要一定時間,所以推遲適當時間到時刻Td,保證系統(tǒng)重新排序新加入的任務和等待子任務,實現(xiàn)任務的平穩(wěn)執(zhí)行。推遲時間Td的設(shè)定相似于任務搶占閾值的設(shè)定,設(shè)定推遲系數(shù)Cd(Cd≥1)或者推遲增量ΔT,推遲時間分別是Td=Cd×T或者Td=T+ΔT,如圖1所示。測試任務搶占調(diào)度流程TP如下所示:

步驟 1提取時刻Td后的所有等待子任務,將其與新加入的任務組成新的子任務集P5;

步驟 2計算、比較P5中所有子任務的動態(tài)優(yōu)先級,按照優(yōu)先級由大到小的順序進行排序組成一個新的子任務集P6,優(yōu)先級最高的子任務首先與資源進行匹配;

步驟 3～步驟5轉(zhuǎn)入DPA策略中的步驟2～步驟4。

2.3算法流程

基于DPA策略和TP策略,實現(xiàn)了ATS針對裝備保障活動的平穩(wěn)執(zhí)行,保證測試任務的最優(yōu)調(diào)度。綜合兩類策略的具體流程,提出了TTPSADP流程，如圖3所示。其中,灰色方框表示DPA策略,白色方框表示TP策略。

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

3　實例驗證

基于文獻[6]中針對裝備的測試實例,相關(guān)數(shù)據(jù)如表1所示,驗證TTPSADP算法的可行性。假設(shè)任務執(zhí)行的初始時刻,只有任務E1和E2加入,經(jīng)過時間T=6后,E3加入測試任務序列。

表1　測試任務實例相關(guān)數(shù)據(jù)

3.1DPA策略

步驟 1計算初始階段測試任務E1和E2中所有子任務的基本優(yōu)先級BP,如表2所示;以子任務p1,1為例,計算其基本優(yōu)先級:

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

(13)

經(jīng)過比較后排序,得到子任務集P3={p2,1, p1,2, p1,1, p2,4, p2,2, p2,3, p1,3, p1,4},對P3中子任務進行資源匹配,如表2所示。

步驟 2實時監(jiān)控匹配過程中的子任務pi,j,全部滿足oi,j≤Di,進入步驟3。

步驟 3任務與資源匹配完成,生成子任務集P7={p2,1, p1,2, p1,1, p2,4, p2,2, p2,3, p1,3, p1,4},開始執(zhí)行任務,如圖4所示。

表2　測試任務計算數(shù)據(jù)

圖4　初始階段測試任務調(diào)度甘特圖Fig.4　Testing task scheduling Gantt chart in the initial phase

3.2TP策略

步驟 1設(shè)定推遲增量Δ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中所有子任務的動態(tài)優(yōu)先級DPA,如表2所示;以子任務p1,3為例,計算其動態(tài)優(yōu)先級:

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

(14)

依據(jù)計算結(jié)果對子任務排序得到子任務集P6={p3,2,p3,1,p2,3,p3,3,p3,4,p1,3,p1,4}。

步驟 3實時監(jiān)控匹配過程中子任務pi,j,發(fā)現(xiàn)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已經(jīng)完成,p2,1,p1,2,p2,4,p2,2正在執(zhí)行;執(zhí)行后續(xù)任務,如圖5所示。

圖5　執(zhí)行階段測試任務搶占甘特圖Fig.5　Testing task preemption Gantt chart in the execution phase

4　結(jié)　論

綜合考慮測試任務的DVD、EU和資源LB等影響因素,提出了TTPSADP:在任務執(zhí)行的初始階段依托DPA實現(xiàn)了任務的最優(yōu)排序,在任務搶占階段依托TP實現(xiàn)了任務間執(zhí)行順序的合理搶占,在保證任務執(zhí)行成功率的基礎(chǔ)上,實現(xiàn)了ATS價值收益和內(nèi)部資源均衡利用的綜合優(yōu)化。

[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. (夏家莉, 陳輝, 楊兵. 一種動態(tài)優(yōu)先級實時任務調(diào)度算法[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.(梁旭,李行善,于勁松.基于遺傳算法的并行測試調(diào)度算法研究[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. (黃敏鎂, 羅榮桂. 柔性資源約束下的產(chǎn)品開發(fā)項目優(yōu)化調(diào)度研究[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.(萬明,張鳳鳴,樊曉光.戰(zhàn)時裝備維修任務調(diào)度的兩種新算法[J].系統(tǒng)工程與電子技術(shù),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.(王正元,嚴小琴,朱昱,等.一種考慮專業(yè)的動態(tài)維修任務調(diào)度的優(yōu)化方法[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. (徐賜軍, 李愛平, 劉雪梅. 基于資源推拉技術(shù)的多項目調(diào)度算法[J]. 計算機集成制造系統(tǒng), 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.(呂學志,陳樂,尹健,等.考慮休息的維修任務調(diào)度模型及其求解算法[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. (王璇, 顏景龍. 基于評價函數(shù)的動態(tài)協(xié)同任務調(diào)度算法[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. (朱昱, 宋建社, 王正元. 一種基于最大保障時間的戰(zhàn)時裝備維修任務調(diào)度[J]. 系統(tǒng)工程與電子技術(shù), 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. (金宏, 王宏安, 王強, 等. 改進的最小空閑時間優(yōu)先調(diào)度算法[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；網(wǎng)絡(luò)優(yōu)先出版日期：2016-05-12。

TP316

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

丁超(1990-),男,博士研究生,主要研究方向為自動測試系統(tǒng)設(shè)計與應用。

E-mail:duncan1119@163.com

唐力偉(1961-),男,教授,博士,主要研究方向為自動測試系統(tǒng)、機械測試及性能檢測與故障診斷。

E-mail:tom5157@163.com

鄧士杰(1982-),男,講師,博士,主要研究方向為故障診斷及自動測試系統(tǒng)。

E-mail:13700317750@163.com

網(wǎng)絡(luò)優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160512.0908.004.html