基于任務(wù)同步及節(jié)能的實(shí)時(shí)調(diào)度算法

摘要：實(shí)時(shí)任務(wù)在實(shí)際應(yīng)用中通常需要以獨(dú)占方式訪問共享資源， 但是由于資源的獨(dú)占性導(dǎo)致高優(yōu)先權(quán)任務(wù)運(yùn)行時(shí)往往被低優(yōu)先權(quán)任務(wù)阻塞， 從而產(chǎn)生優(yōu)先權(quán)反轉(zhuǎn)， 難以滿足任務(wù)的實(shí)時(shí)性；同時(shí)當(dāng)前處理器由于較高的能量消耗，導(dǎo)致處理器熱量散發(fā)提高及系統(tǒng)可靠性降低， 已經(jīng)成為目前計(jì)算機(jī)領(lǐng)域較為關(guān)心的問題。提出一種基于任務(wù)同步及節(jié)能的實(shí)時(shí)調(diào)度算法CSSFA，有效地解決了上述難題。CSSFA在滿足任務(wù)實(shí)時(shí)可調(diào)度性及任務(wù)同步的條件下，固定臨界區(qū)的運(yùn)行速度，使更多的空閑時(shí)間用于非臨界區(qū)部分，有效地降低了整體系統(tǒng)的能耗；同時(shí)也能避免高優(yōu)先權(quán)任務(wù)被阻塞、臨界區(qū)繼承高優(yōu)先權(quán)任務(wù)的速度時(shí)所造成的處理器電壓開關(guān)的頻繁切換， 因而能有效地降低實(shí)時(shí)任務(wù)調(diào)度的成本。試驗(yàn)測試表明，CSSFA在調(diào)度性能上明顯優(yōu)于目前所知的有效算法。

關(guān)鍵詞：實(shí)時(shí)調(diào)度；任務(wù)同步；節(jié)能

中圖分類號：TP302文獻(xiàn)標(biāo)志碼：A

文章編號：1001－3695(2008)03－0687－05

0引言

近年來， 處理器性能的提高導(dǎo)致了能量消耗的快速增長。一方面， 這種能量消耗的快速增長降低了基于電池供應(yīng)能量的系統(tǒng)壽命，如手提移動系統(tǒng)等；另一方面， 能量消耗的增長會產(chǎn)生更多熱量并導(dǎo)致系統(tǒng)可靠性下降， 因而需要更好的冷卻技術(shù)。為了降低能量消耗， 一些硬件技術(shù)已被應(yīng)用，如關(guān)閉閑置的電路或者降低沒有被充分應(yīng)用的功能單元的能量級別[1，2]。隨著具有多種供應(yīng)電壓級別的處理器的出現(xiàn)，在處理器層進(jìn)行能量管理已成為現(xiàn)實(shí)。一般采用的方式是利用空閑時(shí)間， 通過動態(tài)電壓調(diào)整(DVS)來降低處理器運(yùn)行速度， 以達(dá)到節(jié)能的目的，但它卻是以延長任務(wù)的實(shí)際運(yùn)行時(shí)間作為代價(jià)[3~5]。

實(shí)時(shí)任務(wù)在實(shí)際應(yīng)用中通常需要以獨(dú)占方式(同步)訪問共享資源(CPU、硬盤、讀寫原子等)。同步原子包括信號燈、加鎖等，而目前一般的實(shí)時(shí)調(diào)度算法忽略了任務(wù)同步。但任務(wù)運(yùn)行時(shí)由于資源的獨(dú)占性導(dǎo)致高優(yōu)先權(quán)任務(wù)往往被低優(yōu)先權(quán)任務(wù)阻塞(blocking)，從而產(chǎn)生優(yōu)先權(quán)反轉(zhuǎn)， 即低優(yōu)先權(quán)任務(wù)先于高優(yōu)先權(quán)任務(wù)執(zhí)行。高優(yōu)先權(quán)任務(wù)的執(zhí)行完成時(shí)間不可避免地由于阻塞而推遲， 因而難以滿足任務(wù)的實(shí)時(shí)性，而周期性實(shí)時(shí)任務(wù)同步的調(diào)度算法是NP難度問題[6]。

由于此類實(shí)時(shí)任務(wù)調(diào)度算法需同時(shí)滿足可調(diào)度性、任務(wù)同步及節(jié)能，該類調(diào)度問題比較復(fù)雜且相關(guān)研究較少。文獻(xiàn)[7]提出了雙速度(dual speed)算法：任務(wù)開始以一固定的低速度L運(yùn)行， 當(dāng)任務(wù)被低優(yōu)先權(quán)任務(wù)阻塞時(shí)， 則該任務(wù)的運(yùn)行速度切換至一個(gè)固定的高速度H；但在任務(wù)運(yùn)行時(shí)， 高優(yōu)先權(quán)任務(wù)的非臨界區(qū)部分不能搶占低優(yōu)先權(quán)任務(wù)的臨界區(qū)部分， 從而使得高優(yōu)先權(quán)任務(wù)被阻塞的時(shí)間延長， 導(dǎo)致任務(wù)完成時(shí)間的延遲。文獻(xiàn)[8]提出頻率繼承的均勻降速算法(USFI)，采用處理器頻率繼承的方法實(shí)現(xiàn)任務(wù)同步及節(jié)能。當(dāng)任務(wù)被阻塞時(shí)，臨界區(qū)的運(yùn)行速度繼承了被阻塞的高優(yōu)先權(quán)任務(wù)的執(zhí)行速度；任務(wù)運(yùn)行時(shí)， 高優(yōu)先權(quán)任務(wù)的非臨界區(qū)部分可以搶占低優(yōu)先權(quán)任務(wù)的臨界區(qū)部分，從而縮短高優(yōu)先權(quán)任務(wù)的執(zhí)行時(shí)間。該算法中同一任務(wù)的非臨界區(qū)部分與臨界區(qū)部分具有相同的執(zhí)行速度。

本文提出的CSSFA由于臨界區(qū)部分的執(zhí)行時(shí)間在實(shí)際應(yīng)用中占任務(wù)總執(zhí)行時(shí)間的比例通常較低[7]，在滿足任務(wù)實(shí)時(shí)可調(diào)度性及任務(wù)同步的條件下，固定臨界區(qū)的運(yùn)行速度，使得更多的空閑時(shí)間用于非臨界區(qū)部分，有效降低了整體系統(tǒng)的能源消耗；允許高優(yōu)先權(quán)任務(wù)的非臨界區(qū)部分搶占低優(yōu)先權(quán)任務(wù)的臨界區(qū)部分，減少高優(yōu)先權(quán)任務(wù)被阻塞的時(shí)間，從而使得任務(wù)在滿足實(shí)時(shí)可調(diào)度性條件下，能以較低的速度運(yùn)行以降低系統(tǒng)的能量消耗；同時(shí)也能避免高優(yōu)先權(quán)任務(wù)被阻塞時(shí)，臨界區(qū)繼承高優(yōu)先權(quán)任務(wù)的速度時(shí)所造成的處理器電壓開關(guān)頻繁切換，有效降低了實(shí)時(shí)任務(wù)調(diào)度的成本。

1任務(wù)調(diào)度模型

1．1任務(wù)模型

本文假設(shè)系統(tǒng)為單處理器系統(tǒng)， 處理器最大執(zhí)行速度為1。系統(tǒng)包含一個(gè)共享資源集合(SR={SRi})， 任務(wù)以獨(dú)占方式訪問資源。通常訪問這些共享資源的同步原子包括信號燈、加鎖等。本文假設(shè)采用信號燈(semaphore)作為同步原子。

實(shí)時(shí)任務(wù)集合Γ={τ1，…，τn}包含n個(gè)周期性任務(wù)，任務(wù)采用RM[9]算法確定任務(wù)的優(yōu)先權(quán)， 即周期小的任務(wù)具有較高的優(yōu)先權(quán)。任務(wù)τi的優(yōu)先權(quán)記為P(τi)， 三元組τi={Ti，Di，Ci}表示任務(wù)τi的周期、相對截止期及最壞情況下的執(zhí)行時(shí)間(WCET)(由處理器最大執(zhí)行速度1計(jì)算而得)。其中Di=Ti。任務(wù)τi的每個(gè)實(shí)例j表示為τi， j，任務(wù)實(shí)例之間按照優(yōu)先權(quán)關(guān)系可以互相搶占。假設(shè)任務(wù)τi的每個(gè)實(shí)例τi， j實(shí)際運(yùn)行時(shí)間為Ci，定義處理器的利用率U=ni=1Ci/Ti。

若任務(wù)獲得某一共享資源的使用權(quán)， 則稱該任務(wù)進(jìn)入其臨界區(qū)(critical section)。任務(wù)τi的第j個(gè)臨界區(qū)記為zi，j，其WCET記為Ccs(zi， j)，zi， j訪問的共享資源記為s(zi， j)。其中s(zi， j)∈SR。假設(shè)任務(wù)的臨界區(qū)可以適當(dāng)嵌套(proper nesting)， 即對任務(wù)τi的任一對zi， j及zi，k有:zi，jzi，k，或zi， jzi，k，或zi， j∩zi，k=1。若任務(wù)τi的臨界區(qū)數(shù)量為Ncs(τi)， 非臨界區(qū)部分的WCET總和為Cns(τi)，則Ci=Cns(τi)+Ncs(τi)j=1Ccs(zi，j)。

若高優(yōu)先權(quán)任務(wù)等待低優(yōu)先權(quán)任務(wù)釋放獨(dú)占的共享資源，則稱高優(yōu)先權(quán)任務(wù)被低優(yōu)先權(quán)任務(wù)阻塞(block)。令Bi(由處理器最大執(zhí)行速度1計(jì)算而得)為任務(wù)τi被低優(yōu)先權(quán)任務(wù)阻塞的最大時(shí)間。假設(shè)任務(wù)運(yùn)行時(shí)， 高優(yōu)先權(quán)任務(wù)的非臨界區(qū)部分可以搶占低優(yōu)先權(quán)任務(wù)的臨界區(qū)部分。

1．2能量模型

基于CMOS技術(shù)的處理器， 能量的消耗由動態(tài)能量揮發(fā)Pd決定， Pd=Cef×V2dd×PS。其中：Cef為有效的開關(guān)電容量；Vdd是供應(yīng)電壓；PS是處理器時(shí)鐘頻率即處理器速度。處理器速度一般與供應(yīng)電壓呈線性關(guān)系: PS=k×(Vdd-Vt)2/Vdd［1］。其中：k為常數(shù)；Vt為電壓閾值。因此Pd與PS為立方關(guān)系: Pd≈Cef×PS3/k2。一個(gè)任務(wù)的執(zhí)行時(shí)間為time=CN/PS。其中CN為任務(wù)所有指令周期的數(shù)量。該任務(wù)的能量消耗EC為Pd×time≈CN×Cef×PS2/k2， 即能量消耗正比于處理器執(zhí)行速度的平方。由于最大處理器速度在本文中假設(shè)為1，對任一任務(wù)τi有EC≈Ci×Cef×PS2/k2。本文令EC=Ci×Cef×PS2/k2。假設(shè)可以通過在一定電壓的情況下設(shè)置處理器最大速度， 使得電壓與處理器的速度能夠同時(shí)被調(diào)節(jié)。由于本文采用RM算法確定任務(wù)的優(yōu)先權(quán)， 而RM算法中利用率U的最小上界為n(21/n-1)，當(dāng)處理器利用率較低時(shí)，可以利用空閑時(shí)間降低處理器的運(yùn)行速度， 達(dá)到節(jié)能的目的。

1．3同步協(xié)議

本文采用文獻(xiàn)［10］的同步協(xié)議PCP，該協(xié)議適用于靜態(tài)優(yōu)先權(quán)的實(shí)時(shí)任務(wù)調(diào)度算法， 如RM等。任務(wù)運(yùn)行時(shí)， 高優(yōu)先權(quán)任務(wù)的非臨界區(qū)部分可以搶占低優(yōu)先權(quán)任務(wù)的臨界區(qū)部分。若高優(yōu)先權(quán)任務(wù)被低優(yōu)先權(quán)任務(wù)阻塞， 則該低優(yōu)先權(quán)任務(wù)繼承被阻塞的高優(yōu)先權(quán)任務(wù)的優(yōu)先權(quán)；當(dāng)?shù)蛢?yōu)先權(quán)任務(wù)退出臨界區(qū)時(shí)，則恢復(fù)其本來的優(yōu)先權(quán)。定義任一資源SRi優(yōu)先權(quán)的頂為PC(SRi)=maxi{P(τi)}，若s(zi， j)=SRi， 即訪問該資源的所有任務(wù)優(yōu)先權(quán)的最高值。若高優(yōu)先權(quán)任務(wù)τi搶占其他低優(yōu)先權(quán)的臨界區(qū)zm，n， 然后準(zhǔn)備進(jìn)入自己的未被獨(dú)占的臨界區(qū)時(shí)， 如果τi的優(yōu)先權(quán)高于PC（S（Zm，n）），則準(zhǔn)許進(jìn)入; 否則被掛起。PCP保證每個(gè)任務(wù)在實(shí)際運(yùn)行中最多只被低優(yōu)先權(quán)任務(wù)阻塞一次， 且避免了資源的死鎖。

2CSSFA

由于在實(shí)際應(yīng)用中臨界區(qū)部分的WCET占任務(wù)總的WCET的比例較低，可以適當(dāng)提高臨界區(qū)部分的實(shí)際執(zhí)行速度， 騰出更多的空閑時(shí)間用于非臨界區(qū)部分， 以降低系統(tǒng)能耗。盡管定理1及推論1只考慮了較為簡單的情況， 但是可以看出，降低非臨界區(qū)部分的執(zhí)行速度更有可能降低整個(gè)系統(tǒng)能耗。

定理1假設(shè)任務(wù)τi的臨界區(qū)WCET總和為y，非臨界區(qū)WCET的總和為x，且x>y。存在一個(gè)空閑時(shí)間，其長度為z，則空閑時(shí)間全部均勻用于臨界區(qū)時(shí)所產(chǎn)生的能耗大于空閑時(shí)間全部均勻用于非臨界區(qū)部分時(shí)所產(chǎn)生的能耗。

證明空閑時(shí)間全部均勻用于臨界區(qū)及非臨界區(qū)部分時(shí)能耗分別為xCef/k2+yCef[y/(y+z)]2/k2及yCef/k

由于x>y且x，y，z>0，上面不等式左邊各項(xiàng)都大于0，導(dǎo)致矛盾，故命題成立。

推論1假設(shè)任務(wù)τi的臨界區(qū)zi， j的WCET為y，zi，j阻塞任務(wù)τk，τk被阻塞的WCET為x， 且x>y。存在一個(gè)空閑時(shí)間， 其長度為z，則空閑時(shí)間全部用于臨界區(qū)zi， j時(shí)所產(chǎn)生的能耗大于空閑時(shí)間全部均勻用于τk被阻塞部分時(shí)所產(chǎn)生的能耗。

證明證明過程與定理1一致。

2．1算法描述

CSSFA在滿足可調(diào)度性及同步協(xié)議的基礎(chǔ)上， 固定任務(wù)臨界區(qū)部分的運(yùn)行速度， 使得非臨界區(qū)部分獲得更多的空閑時(shí)間， 以降低系統(tǒng)能耗。同時(shí)， 在任務(wù)實(shí)際運(yùn)行中， 臨界區(qū)無須繼承被阻塞任務(wù)的運(yùn)行速度， 避免了處理器電壓開關(guān)的頻繁切換， 以降低調(diào)度成本。在CSSFA中， 任一任務(wù)τi的非臨界區(qū)部分的速度ηns(τi)相同， 而任一臨界區(qū)部分zi， j的速度ηcs(zi，j)不盡相同， 但是都不小于zi，j有可能阻塞的任務(wù)的非臨界區(qū)部分的速度(見性質(zhì)1)。

首先給出算法描述:

a）任務(wù)集中的任務(wù)按RM算法進(jìn)行優(yōu)先權(quán)排序，τ1具有最高優(yōu)先權(quán)， τn具有最低優(yōu)先權(quán);

b)初始化:q=1;

c)while (q＜=n) do

d)for (i=q;i＜=n;i++) do

e)計(jì)算τi非臨界區(qū)部分的速度ηns(τi);

f)end for

g)ηm=maxni=q{ηns(τi)}，初始化臨時(shí)資源集合TSR為空;

h)for (i=q; i＜=m;i++) do

i)ηns(τi)=ηm；

j)if (ηcs(zi，j)未定義(1≤j≤Ncs(τi)))

k)ηcs(zi，j)=ηm;

l)else

將s(zi，j)無重復(fù)地添加到TSR中；

m）end if

n）end for

o）for (j=m+1; j＜=n;j++)

p)if(s(zj， k)∈TSR and zj， k未定義)or (s(zj， k)∈TSR and zj，k已定義and ηcs(zj，k)＜ηm)

q)ηcs(zj，k)=ηm

r)end if

s)end for

t)q=m+1;

u)end while

v)重新計(jì)算任務(wù)τn的非臨界區(qū)部分的速度。

CSSFA中d)~s)的每次循環(huán)中， 定義τm為中斷點(diǎn)任務(wù)。其中τm的非臨界區(qū)部分的速度為ηm(算法g）)。CSSFA d)~s)中稱臨界區(qū)zi， j(i≥q)的速度未定義(notdefined(zi， j))， 當(dāng)且僅當(dāng)不存在某一s(zx， y)=s(zi， j)(其中x＜q)，即任務(wù)臨界區(qū)zi，j不阻塞所有優(yōu)先權(quán)高于τi的任務(wù); 否則稱zi， j的速度已定義(defined(zi， j))。

依照本文假設(shè)的計(jì)算模型，定義任務(wù)τi的調(diào)度點(diǎn)集合[11]為Si={kTj|j=1，…，i；k=1，…，Ti/Tj」}。

在CSSFA中e）計(jì)算τi非臨界區(qū)部分的速度ηns(τi)時(shí)， 首先對每個(gè)Si， j∈Si計(jì)算ηi， j。USFI[8]算法中同一任務(wù)的臨界區(qū)部分與非臨界區(qū)部分的速度均相同。在滿足實(shí)時(shí)性條件下， 給出的ηij計(jì)算公式如下:

(∑1≤r

CSSFA固定任務(wù)臨界區(qū)部分的運(yùn)行速度， 因而ηij的計(jì)算式如下:

∑1≤r

其中:zx，y有可能阻塞任務(wù)τi；zp，a未定義；zp，b已定義；τi非臨界區(qū)部分的速度ηns(τi)=minj(ηi，j)。

式(2)與(1)的區(qū)別在于，每次求得中斷點(diǎn)任務(wù)后，有些低優(yōu)先權(quán)任務(wù)有可能阻塞非臨界區(qū)部分速度已確定的任務(wù)， 那么這些低優(yōu)先權(quán)任務(wù)的臨界區(qū)部分的速度若未定義， 則其速度為中斷點(diǎn)任務(wù)臨界區(qū)部分的速度(算法j）~l)和p)~r))。因而在式(2)中區(qū)分開已定義的臨界區(qū)部分及未定義的臨界區(qū)部分。USFI算法（式(1)）中同一任務(wù)的臨界區(qū)及非臨界區(qū)部分具有相同的運(yùn)行速度， 以Bi/ηns(τi)作為低優(yōu)先權(quán)任務(wù)對任務(wù)τi的最大阻塞時(shí)間， 且低優(yōu)先權(quán)任務(wù)的執(zhí)行速度不大于高優(yōu)先權(quán)任務(wù)的執(zhí)行速度[8]。在任務(wù)實(shí)際運(yùn)行中， 當(dāng)任務(wù)被阻塞時(shí)， 臨界區(qū)的運(yùn)行速度必須繼承被阻塞的高優(yōu)先權(quán)任務(wù)的執(zhí)行速度，以滿足實(shí)時(shí)可調(diào)度性。式(2)則區(qū)分開已定義的臨界區(qū)部分及未定義的臨界區(qū)部分， 在計(jì)算中已考慮實(shí)際運(yùn)行時(shí)低優(yōu)先權(quán)任務(wù)對高優(yōu)先權(quán)任務(wù)的最大阻塞時(shí)間， 因而滿足任務(wù)運(yùn)行時(shí)的實(shí)時(shí)性要求(見定理2)。

式(2)的求解分兩種情況討論，即maxnotdefined(zx，y){Ccs(zx，y)/ηi，j}≥maxdefined(zx，y){Ccs(zx，y)/ηcs(zx，y)}或maxnotdefined(zx，y){Ccs(zx，y)/ηi，j}≤maxdefined(zx，y){Ccs(zx，y)/ηcs(zx，y)}。兩種情況下求出的速度應(yīng)滿足分類條件的要求， 不符合則舍去；若同時(shí)滿足則選擇最小值作為非臨界區(qū)部分的執(zhí)行速度。

性質(zhì)1CSSFA中任一任務(wù)的非臨界區(qū)部分的速度均不大于有可能阻塞它的臨界區(qū)部分的速度。

證明CSSFA每次求出一個(gè)中斷點(diǎn)任務(wù)后， 算法h）~s)對目前有可能阻塞τq，…，τm的臨界區(qū)部分的速度進(jìn)行了處理。若臨界區(qū)的速度未定義， 則將其定義為中斷點(diǎn)任務(wù)的非臨界區(qū)部分的速度; 若臨界區(qū)的速度已定義而其速度小于當(dāng)前中斷點(diǎn)任務(wù)的非臨界區(qū)部分的速度時(shí)， 則調(diào)整其速度使之等于當(dāng)前中斷點(diǎn)任務(wù)的非臨界區(qū)部分的速度， 故命題成立。

由CSSFA可知，當(dāng)其執(zhí)行完畢后， 對于每個(gè)任務(wù)τi，至少存在某一個(gè)Si， j∈Si， 使得

∑1≤r≤i[Cns(τr)/ηns(τr)+∑Ncs(τr)k=1Ccs(zr，k)/ηcs(zr，k)]「Si，j/Tr+

max{Ccs(zx，y)/ηcs(zx，y)}≤Si，j (3)

其中zx，y有可能阻塞任務(wù)τi。

由于已定義的臨界區(qū)速度在算法中可能會被修改(算法p）和q）)，在v)步按式(3)重新計(jì)算任務(wù)τn非臨界區(qū)部分的速度。τn非臨界區(qū)部分的速度調(diào)整之后， 其他任務(wù)τi(1≤i

定理2CSSFA能保證所有任務(wù)在實(shí)際運(yùn)行中的實(shí)時(shí)可調(diào)度性。

證明CSSFA執(zhí)行完畢后， 對每個(gè)任務(wù)τi，式(3)均成立。證明方法類似文獻(xiàn)［12］， 采用反證法。若在運(yùn)行中任務(wù)τi的某一實(shí)例在其截止期內(nèi)無法完成，其絕對截止期為t，則假設(shè)t′為小于時(shí)間點(diǎn)t且在t′以前沒有優(yōu)先權(quán)大于τi的任務(wù)實(shí)例到達(dá)的最晚時(shí)間點(diǎn)。若這樣的時(shí)間點(diǎn)t′不存在，則令t′=0。對任務(wù)τi的每個(gè)調(diào)度點(diǎn)Si， j∈Si，令A(yù)為在[t′，t′+Si，j]到達(dá)且優(yōu)先權(quán)不小于τi的任務(wù)實(shí)例集合，B為在[t′，t′+Si，j]到達(dá)且優(yōu)先權(quán)小于τi的任務(wù)實(shí)例集合，則根據(jù)PCP， 集合B中的任務(wù)實(shí)例在[t′，t′+Si，j]阻塞τi的時(shí)間至多為max{Ccs(zx，y)/ηcs(zx，y)}。其中zx，y有可能阻塞任務(wù)τi。集合A中的任務(wù)實(shí)例在[t′，t′+Si，j]執(zhí)行時(shí)間至多為∑1≤r≤i[Cns(τr)/ηns(τr)+∑Ncs(τr)k=1Ccs(zr，k)/ηcs(zr，k)]「Si，j/Tr。根據(jù)假設(shè)， 任務(wù)τi錯(cuò)失其截止期， 則對每個(gè)Si， j在時(shí)間長度為Si， j內(nèi)有∑1≤r≤i[Cns(τr)/ηns(τr)+∑Ncs(τr)k=1Ccs(zr，k)/ηcs(zr，k)]「Si，j/Tr+max{Ccs(zx，y)/ηcs(zx，y)}>Si，j，與式(3)矛盾， 故命題成立。

CSSFA除了在任務(wù)運(yùn)行前計(jì)算其靜態(tài)的運(yùn)行速度，在實(shí)際運(yùn)行時(shí)針對特殊情況給出了其動態(tài)執(zhí)行速度。

定義任務(wù)τi在時(shí)間t時(shí)的剩余執(zhí)行時(shí)間為R(τi，t)， 即尚未完成的臨界區(qū)及非臨界區(qū)部分的剩余執(zhí)行時(shí)間(按照它們的靜態(tài)速度計(jì)算而得)。

定理3假設(shè)在時(shí)間t時(shí)只有任務(wù)τi的實(shí)例在運(yùn)行， 其他任務(wù)的實(shí)例均已完成。若所有任務(wù)的下一實(shí)例最早到達(dá)時(shí)間為P且R(τi，t)+t＜P， 則任務(wù)τi實(shí)例未完成部分(包括臨界區(qū))的速度可調(diào)整為R(τi，t)/（P-t）。

證明由于除τi的實(shí)例外所有任務(wù)的已到達(dá)實(shí)例在時(shí)間t時(shí)均已完成且R(τi，t)+t＜P，表明在其他任務(wù)實(shí)例到達(dá)前， 任務(wù)τi的實(shí)例按靜態(tài)速度完成時(shí)依然存在空閑時(shí)間，而這些空閑時(shí)間可以用于τi的實(shí)例以更小的速度運(yùn)行。當(dāng)速度調(diào)整為R(τi，t)/（P-t）， 任務(wù)τi的實(shí)例在所有任務(wù)的下一實(shí)例最早到達(dá)時(shí)間之前可以完成， 因而不會搶占或阻塞其他任務(wù)的實(shí)例，滿足實(shí)時(shí)可調(diào)性的條件。

2．2調(diào)度成本分析

算法的調(diào)度成本包括靜態(tài)和動態(tài)調(diào)度成本兩個(gè)方面。靜態(tài)調(diào)度成本是指計(jì)算靜態(tài)速度的時(shí)間復(fù)雜度; 動態(tài)調(diào)度成本是指任務(wù)實(shí)例運(yùn)行時(shí)速度調(diào)整時(shí)的開銷。

假設(shè)每個(gè)任務(wù)調(diào)度點(diǎn)的最大數(shù)目為m，每個(gè)任務(wù)臨界區(qū)的最大數(shù)目為c，則USFI算法的靜態(tài)時(shí)間復(fù)雜度為O(mn2);CSSFA中d）~f)的時(shí)間復(fù)雜度為O(mn)，h)~t)的時(shí)間復(fù)雜度為O(cn)， 則CSSFA的靜態(tài)時(shí)間復(fù)雜度為O((m+c)n2)。兩種算法具有相近的時(shí)間復(fù)雜度。

定義算法的動態(tài)調(diào)度成本為任務(wù)運(yùn)行時(shí)速度調(diào)整的次數(shù)。對于非臨界區(qū)部分， CSSFA與USFI速度調(diào)整的次數(shù)相同;USFI的頻率繼承導(dǎo)致USFI對每個(gè)任務(wù)臨界區(qū)部分的速度調(diào)整次數(shù)比CSSFA最多多出（n-1）c次。因而CSSFA的動態(tài)調(diào)度成本優(yōu)于USFI算法。

3試驗(yàn)結(jié)果

本章測試CSSFA和USFI算法的調(diào)度性能，性能指標(biāo)為能耗。測試采用模擬仿真，設(shè)任務(wù)集合有10~15個(gè)周期性任務(wù)。為使測試更加全面，考慮了不同任務(wù)粒度， 任務(wù)周期分別為[90，200]，[200，2 000]，[2 000，5 000]。對于這三個(gè)區(qū)間，任務(wù)的WCET分別為[10，20]， [10，100]， [10，500]。共享資源的數(shù)量為[0，4]， 任務(wù)臨界區(qū)的數(shù)量為[0，4]，臨界區(qū)部分在任務(wù)中的位置隨機(jī)選取。任一任務(wù)τi的臨界區(qū)WCET為[0.2αCi/Ncs(τi)，1.8αCi/Ncs(τi)]。其中α為臨界區(qū)執(zhí)行時(shí)間與Ci比例，其值為3%~30%，步長為3%。利用率U為0.1~0.7。測試中的隨機(jī)數(shù)均采用均勻分布。每次模擬測試中， 任務(wù)集合運(yùn)行時(shí)間為200 000。該模擬程序采用GNU C，并在Linux OS 2.4.18， 512 MB RAM， 2.0 GHz AMD CPU的單機(jī)上模擬測試。

3．1綜合測試結(jié)果

圖1顯示CSSFA比USFI性能提高的百分比，橫坐標(biāo)代表利用率U。本次測試中除利用率外， 其他參數(shù)均隨機(jī)選取。

從圖1可以看出， CSSFA在調(diào)度性能上明顯優(yōu)于USFI。當(dāng)利用率U較小， 即任務(wù)能充分利用空閑時(shí)間降低其運(yùn)行速度時(shí)， CSSFA較之USFI的調(diào)度性能提高的比例越高。這充分表明CSSFA固定臨界區(qū)速度使得非臨界區(qū)部分利用更多的空閑時(shí)間， 能有效地降低系統(tǒng)能耗。同時(shí)， 定理3給出的方法在實(shí)際運(yùn)行中進(jìn)一步降低了能耗。隨著U的提高， 即可用空閑時(shí)間的減少， 兩種算法的調(diào)度性能趨于一致。同時(shí)由2．2節(jié)的分析可知，CSSFA的動態(tài)調(diào)度成本明顯優(yōu)于USFI算法， 在實(shí)際應(yīng)用中能進(jìn)一步提高調(diào)度性能。

3．2α對調(diào)度性能的影響

圖2給出當(dāng)U為0.3時(shí)，α對調(diào)度性能的影響；其他參數(shù)隨機(jī)選取，橫坐標(biāo)代表α值。

從圖2可以看出， 隨著α的提高， 即臨界區(qū)執(zhí)行時(shí)間比例的提高，CSSFA較之USFI在調(diào)度性能上提高的比例越大，表明固定臨界區(qū)速度使得非臨界區(qū)部分利用更多的空閑時(shí)間， 能有效地降低系統(tǒng)能耗。但是，α提高到一定的程度，CSSFA較之USFI在調(diào)度性能上提高的比例反而呈下降趨勢。其原因在于臨界區(qū)執(zhí)行比例到達(dá)一定程度時(shí)，意味著被其阻塞的任務(wù)的剩余執(zhí)行時(shí)間大于臨界區(qū)執(zhí)行時(shí)間的概率隨之下降。由推論1可知， 能耗下降的比例也隨之下降。

3．3資源數(shù)量對調(diào)度性能的影響

圖3給出當(dāng)U為0.3時(shí)， 資源數(shù)量對調(diào)度性能的影響；其他參數(shù)隨機(jī)選取，橫坐標(biāo)代表資源數(shù)量。由于

資源數(shù)量為0(即無須任務(wù)同步)時(shí)兩種算法的調(diào)度性能一樣，僅考慮資源數(shù)量大于0的情況。

圖3表明隨著資源數(shù)量的增加，CSSFA較之USFI在調(diào)度性能提高的比例逐漸下降。原因在于根據(jù)PCP，每個(gè)任務(wù)在實(shí)際運(yùn)行中最多只被低優(yōu)先權(quán)任務(wù)阻塞一次， 因而任務(wù)被阻塞的概率隨之下降， 而CSSFA中任務(wù)臨界區(qū)部分執(zhí)行速度固定且不小于被阻塞的任務(wù)非臨界區(qū)部分速度， 因而導(dǎo)致能耗提高。從試驗(yàn)數(shù)據(jù)發(fā)現(xiàn)，當(dāng)資源的數(shù)量及α都相對較大時(shí)， CSSFA在調(diào)度性能上遜于USFI算法。

致謝:感謝美國University of Delaware高光榮教授對本文提出的寶貴建議。

參考文獻(xiàn)：

［1］BURD T D， BRODERSEN R W.Energy efficient CMOS microprocessor design[C]//Proc of Hawaii Int’l Conf on System Science.1995:288－297.

[2]CHANDRAKASAN A，SHENG S， BRODERSEN R. Lowpower CMOS digital design[J].IEEE J SolidState Circuit，1992，27(4): 473－484.

[3]ZHU Dakai，MELHEM R，CHILDERS B R.Scheduling with dynamic voltage/speed adjustment using slack reclamation in multiprocessor realtime systems[J].IEEE Trans on Parallel and Distributed Systems，2003，14(7):686－699.

[4]YAN Le，LUO Jiong，JHA N K.Joint dynamic voltage scaling and adaptive body biasing for heterogeneous distributed realtime embedded systems[J].IEEE Trans on Computer Aided Design of Integrated Circuits and Systems，2005，24(7):10301041.

[5]CHABINI N，WOLF W.Unification of scheduling，binding， and retiming to reduce power consumption under timings and resource constraints[J].IEEE Trans on Very Large Scale Integration Systems，2005，13(10): 11131126.

[6]STANKOVIC J A， SPURIM S，NATALE M D.Implications of classical scheduling results for realtime systems[J].IEEE Trans on Computers，1994，28(6):16－25.

[7]ZHANG Fang， CHANSON S T.Blockingaware processor voltage scheduling for realtime systems[J].ACM Trans on Embedded Computing Systems，2004，3(2):307－335.

[8]JEJURIKA R，GUPTA R.Energy aware task scheduling with task synchronization for embedded realtime systems[J].IEEE Trans on Computer Aided Design of Integrated Circuits and Systems，2006，25(6):10241037.

[9]LIU C L，LAYLAND J W.Scheduling algorithms for multiprogramming in a hard realtime environment[J].Journal of the ACM， 1973，20(1):46－61.

[10]SHA Lu， RAJKUMAR R，LEHOCZKY J.Priority inheritance protocols:an approach to realtime synchronization[J].IEEE Trans on Computers，1990，39(9):11751185.

[11]LEHOCZKY J，SHA Lu， DING Ye.The rate monotonic scheduling algorithm:exact characterization and average case behavior[C]//Proc of IEEE Realtime Systems Symposium.1989.

[12]BAKER T P. Stackbased scheduling of realtime processes[J].Journal of Realtime Systems，1991，3(1): 6799.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”