實時嵌入式異構環(huán)境下多優(yōu)先級混合任務調度動態(tài)策略*

馬 晨, 肖智斌， 張 晶， 范洪博， 車國霖

(昆明理工大學 信息工程與自動化學院,云南 昆明 650500)

?

實時嵌入式異構環(huán)境下多優(yōu)先級混合任務調度動態(tài)策略*

馬 晨, 肖智斌， 張 晶， 范洪博， 車國霖

(昆明理工大學 信息工程與自動化學院,云南 昆明 650500)

針對現(xiàn)有異構環(huán)境下的調度策略，引入迫切密度和剩余價值密度，分析迫切密度和剩余價值密度調節(jié)任務執(zhí)行緊急程度的影響、對優(yōu)先級制定,通過構建單有向無環(huán)圖(DAG)系統(tǒng)模型實現(xiàn)了混合任務的動態(tài)調度。仿真實驗結果表明：該調度策略在系統(tǒng)負載較高的情況下,仍有較優(yōu)的任務執(zhí)行效能和避免顛簸現(xiàn)象。

迫切密度； 剩余價值密度； 有向無環(huán)圖； 動態(tài)調度； 顛簸； 實時性

0 引 言

隨著實時嵌入式工業(yè)控制軟件的不斷發(fā)展，大量異構設備接入到信息物理融合系統(tǒng)](cyber-physical system,CPS)中]，由此形成了一個異構并行分布式處理環(huán)境， 將用戶的任務分解成若干相關子任務進行并行處理，構建實時嵌入式系統(tǒng)任務調度形式相互作用模型]，可以有效地提高系統(tǒng)處理性能，從而并行協(xié)作完成任務。異構并行分布式處理系統(tǒng)與同構系統(tǒng)相比，具有多個不同架構的計算節(jié)點，這些節(jié)點在處理能力、存儲方式、訪問方式等上都存在差異]。如何將實時任務分解后分配到不同節(jié)點上進行調度處理和資源分配]便成為能否充分發(fā)揮并行分布式處理性能的首要問題8〗。

目前，針對異構并行分布式處理環(huán)境多以隨機搜索算法、表調度算法、任務復制法為基礎。遺傳調度算法和基本粒子群調度算法]是常見的隨機搜索算法，但遺傳算法運行時需大量參數(shù)，交叉和變異概率需大量經(jīng)驗數(shù)據(jù)才能確定，且由于遺傳算法自身存在早熟和不收斂，性能顯著降低。

表調度法中，異構動態(tài)優(yōu)先級任務表調度(heteroge-neous dynamic priority task scheduling，HDPTS)算法是異構環(huán)境下任務處理時間具有非單調性的動態(tài)優(yōu)先級任務調度算法，雖實現(xiàn)調度順序動態(tài)改變，但無法保證任務完成的可靠性，尤其是硬實時任務\〗。

任務復制法是對多個接受消息的處理器發(fā)送任務消息副本，將外部通信轉化為內部通信，減少處理器間通信時間，但由于復制大量副本，降低了處理時間。

本文針對異構并行分布式處理環(huán)境中調度算法存在的不足,12〗，根據(jù)子任務間相互依賴關系構造有向無環(huán)圖(directed acyclic graph,DAG)，并引入迫切程度和剩余價值密度概念，提出一種針對異構并行分布式處理環(huán)境下的多優(yōu)先級混合任務動態(tài)調度策略,仿真實驗結果表明:該調度策略在系統(tǒng)負載較高的情況下仍有較優(yōu)的任務執(zhí)行效能和避免顛簸現(xiàn)象。

1 多優(yōu)先級混合任務動態(tài)調度策略

1.1 系統(tǒng)模型

1.1.1 DAG構建

本文將一組相互依賴的子任務用DAG來表示：

定義1G=(T,e),G′=(T′,e′)。其中，G為硬實時子任務的DAG，G′為軟實時子任務的DAG。

定義2Tα={(tαi,i=1,2,3，…，n),α=1,2,3…N}為N個硬實時任務，且每個任務分解為n個有序硬實時子任務的集合。

本文假定單DAG只存在一個開始任務和一個結束任務。

1.1.2 相關定義

定義8 R={Rφ,φ=1,2,3，…，l}。其中，R為物聯(lián)網(wǎng)所有處理資源的集合，l為處理資源個數(shù)，tiφ,p表示第i個子任務分配到Rφ上處于第p個位置。

因此，包含有若干相互依賴的子任務的集合可以定義如下

Tα={sTα,tαi,dLαi,DLα,δαi,ωαiφ,

ESTαiφ,p,EFTαiφ,p,LFTαiξ,p,Vαi,

VDαi,Vα,α=1,2,3,…,N}

(1)

(2)

(3)

式中 Vαi×φ(1≤α≤N,1≤i≤n,1≤φ≤l)為Tα中的tαi在Rφ上的執(zhí)行速率，該值可通過將子任務在相應處理資源下反復試驗并經(jīng)過統(tǒng)計計算得來。

結合式(3)和δαi，即可算出單個子任務在不同處理資源下的預估執(zhí)行時間

(4)

根據(jù)公式(4)可知，在Rφ下無中斷執(zhí)行所需ωαiφ與δαi成正比，與vαiφ成反比。

式中ESTαiφ,p為tαi在Rφ上的最早開始時刻；ωαkλ為tαi的父任務tαk在Rλ上的預估執(zhí)行時間；lagαiφ為tαk在Rλ上的等待或延時；cTαk,αi為父任務tαk與子任務tαi之間通信所花費的時間；EFTiφ,p-1為tαiφ,p在的Rφ上前一個位置上tαiφ,p-1的最早開始時刻。由于本調度方法采用搶占式策略，因此,當tαi被迫讓出處理資源時，實際執(zhí)行時間將延長，tαi的最早開始時間將推遲

EFTαiφ,p=ESTαiφ,p+minωαiφ

(6)

式中EFTαiφ,p為tαi在Rφ上的最早完成時刻

LFTαiφ,p=PESTαiφ,p+maxωαiφ,且LFTαiφ,p

(7)

式中LFTαiξ,p為tαi在Rφ上的最遲完成時刻。

ρVαi=Vαt/ωαiφ

(8)

式中Vαi為tαi的價值；ρVαi為tαi的價值密度。

價值密度ρVαi，即單位預估執(zhí)行時間上的價值，與ωαiφ成反比，與Vαi成正比。

(9)

式中Vα為Tα的總價值。

1.2 多優(yōu)先級分析

1.2.1 迫切密度

在本文以硬實時任務為例，引入迫切密度概念，保證任務能夠在最遲完成時刻前完成，不影響子任務和后續(xù)任務執(zhí)行。

證明：假設tαi在Rφ上的等待或延時時間為lagαiφ，預估執(zhí)行時間為ωaiφ,設其在Rφ上最早開始時刻任務的執(zhí)行迫切密度為ρEαi，且對迫切密度追加一個權重系數(shù)q，則

(10)

根據(jù)式(7)得

(11)

根據(jù)式(11)知，當比值大于1，子任務即使被分配到最快的處理資源上也可能無法在截止期內執(zhí)行完成。

1.2.2 剩余價值密度

價值是實時任務系統(tǒng)中的內在屬性，本文以硬實時任務為例，引入迫切密度概念，保證緊急任務有限執(zhí)行。

定理2 價值密度等于子任務價值與預估執(zhí)行時間之商，即單位預估執(zhí)行時間內的價值。

證明：根據(jù)式(8)可知，價值密度為

ρVαi=Vαi/ωαiφ

若子任務已經(jīng)執(zhí)行的單位時間為γ，則子任務的預估動態(tài)價值(estimate dynamic value,EDV)為

(12)

式中γ為任務已執(zhí)行單位時間逐漸遞增且小于ωαiφ。

剩余價值密度為

(13)

定理3 當0≤γ≤ωaiφ時，對式(11)增加一個加速參數(shù)τ，τ>1且取定值，子任務的預估立即價值隨γ遞增。

證明：構造函數(shù)

(14)

并對式(13)求一階導數(shù)， 即

(15)

1.3 動態(tài)搶占調度策略

異構并行分布式處理環(huán)境下調度一般包含兩個問題：1)如何合理分配具有相互依賴性質的子任務到多處理資源上。2)分配在單處理資源上多個子任務順序的排序，即任務調度\〗。

實時任務包含硬、軟實時任務，軟實時任務允許發(fā)生超時錯誤，且超時對系統(tǒng)影響較?。挥矊崟r任務對時限要求較剛性，要求指定任務在規(guī)定時間內必須完成，一旦超時不僅對系統(tǒng)造成極其嚴重的影響\〗，諸如對實時任務有嚴格要求的產(chǎn)品一旦出現(xiàn)這種情況會造成無法想象的嚴重后果\〗。本文的動態(tài)調度策略為保證硬實時任務順利完成，允許硬實時任務搶占軟實時任務處理資源，在保證硬實時任務的執(zhí)行可靠性下最大限度\〗的完成軟實時任務。

在可搶占的動態(tài)實時任務調度中，任務的執(zhí)行順序會隨著參數(shù)的改變而動態(tài)變化，當后續(xù)任務的優(yōu)先級超過當前執(zhí)行任務的優(yōu)先級時便會發(fā)生搶占現(xiàn)象。隨著后續(xù)任務占用處理資源，其他任務又重新開始進行優(yōu)先級排序，若有多個任務的優(yōu)先級交替上升從而反復搶占處理器，則稱為“顛簸”現(xiàn)象，進行多次上下文切換，造成系統(tǒng)資源大量浪費。為了避免此類事件發(fā)生，合理的搶占策略是關鍵。本文的基本策略是：硬實時子任務可搶占軟實時子任務，硬實時子任務之間可互相搶占。

依據(jù)前一節(jié)中所論述的ρEαi和ρRVαi，提出一種多優(yōu)先級混合任務動態(tài)調度策略。本文所提出的調度策略以實現(xiàn)任務執(zhí)行迫切程度和動態(tài)價值累積最優(yōu)為目標。構造動態(tài)優(yōu)先級函數(shù)：DPαi=m×ρEαi+n×ρRVαi，其中0≤m≤1,0≤n≤1為權重系數(shù)，且m+n=1。

由式(11)和式(13)可知

(16)

假設硬實時子任務tai被分配到處理資源cφ上，保證它能順利執(zhí)行完成的基本條件是maxωaiξ-lagaiφ>minωaiφ，隨著等待時間lagaiφ的不斷增加，其優(yōu)先級也不斷增加，若超過當前任務的優(yōu)先級則會發(fā)生搶占，此時按照當前執(zhí)行任務種類的不同有兩種處理策略。

1.3.1 軟實時任務

1.3.2 硬實時任務

設taj已執(zhí)行時間為tajed,則剩余執(zhí)行時間為ωaj-tajed。為了消除“顛簸”現(xiàn)象，此處分為兩種情況：

2)被搶占過。為防止taj被頻繁搶占導致執(zhí)行效率不高，此時tai不進行搶占，若maxωaiφ-lagaiφ-ωajφ-tajed>minωaiφ，tai繼續(xù)等待。若maxωaiφ-lagaiφ-ωajφ-tajed

2 實驗仿真

2.1 仿真環(huán)境

仿真環(huán)境均為CPU為Intel(R) Core(TM) i5—4210H CPU @ 2.90 GHz 2.90 GHz，內存為8 G，64位操作系統(tǒng)的臺式機上進行，實驗平臺采用Matlab實驗仿真平臺。試驗中所涉及的時間參數(shù)都以EXCEL隨機函數(shù)RAND的形式產(chǎn)生。

實驗對本文提出的動態(tài)搶占調度策略進行基礎性能分析，然后與傳統(tǒng)的最小空閑時間優(yōu)先(least slack first，LSF)調度算法，最早截止時間優(yōu)先(earliest deadline first，EDF)調度算法進行對比。

2.2 仿真性能指標

實驗中，采用的仿真性能指標為：任務累計價值和搶占次數(shù)。

2.3 仿真比較

2.3.1 基礎性能分析

在該實驗中，依據(jù)隨機數(shù)產(chǎn)生取實驗中所用參數(shù)如表1所示。

表1 實驗所用參數(shù)

實驗1 固定參數(shù)m=0.5,n=0.5,τ=2 ，變量參數(shù)q=0.2,0.4,0.6,0.8，分析q對調度策略基礎性能的影響，實驗結果如圖1所示。

圖1 變量參數(shù)q對調度策略基礎性能的影響Fig 1 Influence of parameter q on basic performance of scheduling policy

實驗2 固定參數(shù)m=0.5,n=0.5,q=0.5，變量參數(shù)τ=3,4,5,6,7，分析τ對調度策略基礎性能的影響，實驗結果如圖2所示。

圖2 變量參數(shù)τ對調度策略基礎性能的影響Fig 2 Influence of parameter τ on performance of scheduling policy

實驗3 固定參數(shù)τ=2,q=0.5，變量參數(shù)m=0.2,0.4,0.6,0.8,n=0.8,0.6,0.4,0.2，分析m,n對調度策略基礎性能的影響。實驗結果如圖3所示。

圖3 變量參數(shù)m,n對調度策略基礎性能的影響Fig 3 Influence of parameter m,n on performance of scheduling policy

2.3.2 算法對比分析

算法對比分析將本調度策略與LSF,EDF～19〗進行對比，仿真實驗在不同系統(tǒng)負載下，選取對比的三種調度算法，在仿真實驗過程中所用參數(shù)依舊以隨機數(shù)方式產(chǎn)生，在不考慮干擾因素情況下，仿真結果如圖4。對影響仿真實驗結果的干擾因素，將在以后的工作中進行研究分析。

圖4 算法對比仿真實驗結果Fig 4 Simulation experiment results of algorithms comparison

如圖4(a),(b)所示:1)累計價值：當系統(tǒng)負載在1～3時，本調度策略劣于LSF，略優(yōu)于EDF；當系統(tǒng)負載在3～7時，三種調度算法沒有明顯優(yōu)劣程度；當系統(tǒng)負載愈來愈大時，本調度策略對比其他兩種調度算法有明顯優(yōu)勢。2)搶占次數(shù)：當系統(tǒng)負載在1～3時，本調度策明顯優(yōu)于LSF和EDF；當系統(tǒng)負載在3～7時，三種調度算法沒有明顯優(yōu)劣程度；當系統(tǒng)負載愈來愈大時，本調度策略對比其他兩種調度算法有明顯優(yōu)勢。

綜上所述，本調度策略在系統(tǒng)負載不斷增大過程中，無論是累計價值，或搶占次數(shù)都明顯優(yōu)于其他兩種算法。

3 結束語

本文通過比較傳統(tǒng)的調度算法,21〗，分析了當前異構環(huán)境下調度算法存在的不足，根據(jù)分解后的硬實時和軟實時任務的子任務之間的相互依賴關系構造有向無環(huán)圖，建立單DAG異構系統(tǒng)模型，并明確模型內相關定義，通過引入ρEαi和ρRVαi概念，并對其做詳細定義與相關證明，基于多優(yōu)先級任務構造迫切密度和剩余價值密度優(yōu)先級隊列，提出了一種異構環(huán)境下多優(yōu)先級混合任務動態(tài)調度策略，即保證了多優(yōu)先級任務調度的實時性，使得混合任務得到高效處理，同時也避免了調度策略在搶占過程中的顛簸現(xiàn)象。最后利用不考慮干擾因素情況下的仿真實驗，通過與相關傳統(tǒng)算法進行比較，得出本調度策略在異構環(huán)境下，不僅提高了CPS實時嵌入式異構環(huán)境下調度策略的執(zhí)行效能\〗，同時能夠在高系統(tǒng)負載下較優(yōu)地對混合任務進行調度，進而保證實時嵌入式工業(yè)控制系統(tǒng)交互行為的存在性和唯一性，更準確地表達系統(tǒng)資源分配與實時任務調度的確定性。

[1] 劉純堯.信息物理融合系統(tǒng)的調度算法研究[D].上海：華東師范大學,2015.

[2] Bastoni A,Brandedburg B B,Anderson J H.An empirical compa-rison of global,partitioned,and clustered multiprocessor EDF schedulers]∥Proceedings of the 31st IEEE Real-Time System Symposium,San Diego,USA,2010:14-24.

[3] Jensen E D,Locke C D,Toduda H,A time-driven scheduling model for real-time operating systems]∥Proceedings of the IEEE Real-Time Systems Symposium,San Diego,CA,USA,1985:112-122.

[4] 朱怡安，黃姝娟，段俊花，等.新的混合關鍵任務調度算法的研究[J].電子科技大學學報,2014(2):268-271，286.

[5] 辛 宇，楊 靜，謝志強.面向分布式環(huán)境的信號驅動任務調度算法[J].通信學報,2015(7):60-70.

[6] 孫 健，張興軍，董小社.異構平臺實時任務的可用性提升容錯調度算法[J].計算機研究與發(fā)展,2015(12):2669-2683.

[7] 孫力娟，魏 靜，郭 劍，等.面向異構無線傳感器網(wǎng)絡的節(jié)點調度算法[J].電子學報,2014 (10):1907-1912.

[8] 彭 浩，韓江洪，陸 陽，等.多處理器硬實時系統(tǒng)的搶占閾值調度研究[J].計算機研究與發(fā)展,2015(5):1177-1186.

[9] 劉純堯，張立臣.信息物理融合系統(tǒng)的動態(tài)多優(yōu)先級調度[J].計算機科學,2015(1):28-32.[10] Qi X,Zhu D K,Aydin H.Cluster scheduling for real-time systems:Utilization bounds and run-time overhead[J].Journal of Real-Time Systems,2011,47(3):253-284.

[11] 曾增日.無線傳感網(wǎng)絡節(jié)點調度算法研究[D].長沙： 湖南大學,2015.

[12] 羅惠星.基于批量作業(yè)調度的算法研究[D].上海：上海師范大學,2015.

[13] 張銀香.協(xié)作通信技術中的調度算法研究[D].北京：北京郵電大學,2015.

[14] 任健康.信息物理系統(tǒng)高效數(shù)據(jù)傳輸和調度機制研究[D].大連：大連理工大學,2015.

[15] 張憶文，郭銳鋒.實時系統(tǒng)混合任務低功耗調度算法[J].吉林大學學報:工學版,2015(1):261-266.

[16] 王希杰.基于物聯(lián)網(wǎng)技術的生態(tài)環(huán)境監(jiān)測應用研究[J].傳感器與微系統(tǒng),2011,30(7)：149-152.

[17] 駱 堅，席 望，謝 鯤.基于異構比特速率的無線傳感器網(wǎng)絡擁塞控制技術[J].傳感器與微系統(tǒng),2015,34(11):23-26.

[18] Baruah S.Partitioned EDF scheduling:A closer look[J].Journal of Real-Time Systems,2013,49(6):715-729.

[19] 桑 磊，陸 陽，俞 磊.基于貪心策略的EDF調度算法優(yōu)化[J].計算機工程,2015(12):96-100.

[20] 胡顯俊，陳建新，周生強，等.IEEE 802．15．4實時通信調度算法研究[J].計算機科學,2015(B11):222-226,241.

[21] 田新越，李翔宇.無線傳感器網(wǎng)絡節(jié)點任務調度與功耗管理算法研究[J].傳感器與微系統(tǒng),2016,35(2):9-12.

Dynamic scheduling strategy for multi priority hybrid tasks in heterogeneous environment of real-time embedded systems*

MA Chen, XIAO Zhi-bin, ZHANG Jing, FAN Hong-bo, CHE Guo-lin

(Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China)

Introduce concept of urgency density and surplus value density,analyze influence of urgency density and surplus value density on priority setting,adjusted the task execution degree of emergency based on weight coefficient and acceleration factor,and dynamic scheduling of hybrid task is achieved based on constructing single directed acyclic graph(DAG) system model.Simulation results show that the proposed scheduling strategy can achieve better task execution efficiency and avoid thrashing even at higher load level.

urgency density; surplus value density:directed acyclic graph(DAG); dynamic scheduling; thrash; real-time

2016—06—06

云南省應用基礎研究計劃重點項目(2014FA029)

10.13873/J.1000—9787(2016)10—0012—05

TP 18

A

1000—9787(2016)10—0012—05

馬 晨(1989-)，男，遼寧沈陽人，碩士研究生，主要研究方向為實時與嵌入式軟件、信息物理融合系統(tǒng)。