實(shí)時(shí)嵌入式異構(gòu)環(huán)境下多優(yōu)先級(jí)混合任務(wù)調(diào)度動(dòng)態(tài)策略*

馬 晨, 肖智斌， 張 晶， 范洪博， 車國(guó)霖

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

?

實(shí)時(shí)嵌入式異構(gòu)環(huán)境下多優(yōu)先級(jí)混合任務(wù)調(diào)度動(dòng)態(tài)策略*

馬 晨, 肖智斌， 張 晶， 范洪博， 車國(guó)霖

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

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

迫切密度； 剩余價(jià)值密度； 有向無環(huán)圖； 動(dòng)態(tài)調(diào)度； 顛簸； 實(shí)時(shí)性

0 引 言

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

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

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

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

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

1 多優(yōu)先級(jí)混合任務(wù)動(dòng)態(tài)調(diào)度策略

1.1 系統(tǒng)模型

1.1.1 DAG構(gòu)建

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

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

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

本文假定單DAG只存在一個(gè)開始任務(wù)和一個(gè)結(jié)束任務(wù)。

1.1.2 相關(guān)定義

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

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

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í)行速率，該值可通過將子任務(wù)在相應(yīng)處理資源下反復(fù)試驗(yàn)并經(jīng)過統(tǒng)計(jì)計(jì)算得來。

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

(4)

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

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

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

(6)

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

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

(7)

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

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

(8)

式中Vαi為tαi的價(jià)值；ρVαi為tαi的價(jià)值密度。

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

(9)

式中Vα為Tα的總價(jià)值。

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

1.2.1 迫切密度

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

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

(10)

根據(jù)式(7)得

(11)

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

1.2.2 剩余價(jià)值密度

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

定理2 價(jià)值密度等于子任務(wù)價(jià)值與預(yù)估執(zhí)行時(shí)間之商，即單位預(yù)估執(zhí)行時(shí)間內(nèi)的價(jià)值。

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

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

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

(12)

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

剩余價(jià)值密度為

(13)

定理3 當(dāng)0≤γ≤ωaiφ時(shí)，對(duì)式(11)增加一個(gè)加速參數(shù)τ，τ>1且取定值，子任務(wù)的預(yù)估立即價(jià)值隨γ遞增。

證明：構(gòu)造函數(shù)

(14)

并對(duì)式(13)求一階導(dǎo)數(shù)， 即

(15)

1.3 動(dòng)態(tài)搶占調(diào)度策略

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

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

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

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

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

(16)

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

1.3.1 軟實(shí)時(shí)任務(wù)

1.3.2 硬實(shí)時(shí)任務(wù)

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

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

2 實(shí)驗(yàn)仿真

2.1 仿真環(huán)境

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

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

2.2 仿真性能指標(biāo)

實(shí)驗(yàn)中，采用的仿真性能指標(biāo)為：任務(wù)累計(jì)價(jià)值和搶占次數(shù)。

2.3 仿真比較

2.3.1 基礎(chǔ)性能分析

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

表1 實(shí)驗(yàn)所用參數(shù)

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

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

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

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

實(shí)驗(yàn)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對(duì)調(diào)度策略基礎(chǔ)性能的影響。實(shí)驗(yàn)結(jié)果如圖3所示。

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

2.3.2 算法對(duì)比分析

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

圖4 算法對(duì)比仿真實(shí)驗(yàn)結(jié)果Fig 4 Simulation experiment results of algorithms comparison

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

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

3 結(jié)束語

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

[1] 劉純堯.信息物理融合系統(tǒng)的調(diào)度算法研究[D].上海：華東師范大學(xué),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] 朱怡安，黃姝娟，段俊花，等.新的混合關(guān)鍵任務(wù)調(diào)度算法的研究[J].電子科技大學(xué)學(xué)報(bào),2014(2):268-271，286.

[5] 辛 宇，楊 靜，謝志強(qiáng).面向分布式環(huán)境的信號(hào)驅(qū)動(dòng)任務(wù)調(diào)度算法[J].通信學(xué)報(bào),2015(7):60-70.

[6] 孫 健，張興軍，董小社.異構(gòu)平臺(tái)實(shí)時(shí)任務(wù)的可用性提升容錯(cuò)調(diào)度算法[J].計(jì)算機(jī)研究與發(fā)展,2015(12):2669-2683.

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

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

[9] 劉純堯，張立臣.信息物理融合系統(tǒng)的動(dòng)態(tài)多優(yōu)先級(jí)調(diào)度[J].計(jì)算機(jī)科學(xué),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)絡(luò)節(jié)點(diǎn)調(diào)度算法研究[D].長(zhǎng)沙： 湖南大學(xué),2015.

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

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

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

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

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

[17] 駱 堅(jiān)，席 望，謝 鯤.基于異構(gòu)比特速率的無線傳感器網(wǎng)絡(luò)擁塞控制技術(shù)[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調(diào)度算法優(yōu)化[J].計(jì)算機(jī)工程,2015(12):96-100.

[20] 胡顯俊，陳建新，周生強(qiáng)，等.IEEE 802．15．4實(shí)時(shí)通信調(diào)度算法研究[J].計(jì)算機(jī)科學(xué),2015(B11):222-226,241.

[21] 田新越，李翔宇.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)任務(wù)調(diào)度與功耗管理算法研究[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

云南省應(yīng)用基礎(chǔ)研究計(jì)劃重點(diǎn)項(xiàng)目(2014FA029)

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

TP 18

A

1000—9787(2016)10—0012—05

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