基于任務同步及節能的實時調度算法

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

關鍵詞：實時調度；任務同步；節能

中圖分類號：TP302文獻標志碼：A

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

0引言

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

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

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

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

1任務調度模型

1．1任務模型

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

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

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

若高優先權任務等待低優先權任務釋放獨占的共享資源，則稱高優先權任務被低優先權任務阻塞(block)。令Bi(由處理器最大執行速度1計算而得)為任務τi被低優先權任務阻塞的最大時間。假設任務運行時， 高優先權任務的非臨界區部分可以搶占低優先權任務的臨界區部分。

1．2能量模型

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

1．3同步協議

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

2CSSFA

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

定理1假設任務τi的臨界區WCET總和為y，非臨界區WCET的總和為x，且x>y。存在一個空閑時間，其長度為z，則空閑時間全部均勻用于臨界區時所產生的能耗大于空閑時間全部均勻用于非臨界區部分時所產生的能耗。

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

由于x>y且x，y，z>0，上面不等式左邊各項都大于0，導致矛盾，故命題成立。

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

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

2．1算法描述

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

首先給出算法描述:

a）任務集中的任務按RM算法進行優先權排序，τ1具有最高優先權， τn具有最低優先權;

b)初始化:q=1;

c)while (q＜=n) do

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

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

f)end for

g)ηm=maxni=q{ηns(τi)}，初始化臨時資源集合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)無重復地添加到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)重新計算任務τn的非臨界區部分的速度。

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

依照本文假設的計算模型，定義任務τi的調度點集合[11]為Si={kTj|j=1，…，i；k=1，…，Ti/Tj」}。

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

(∑1≤r

CSSFA固定任務臨界區部分的運行速度， 因而ηij的計算式如下:

∑1≤r

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

式(2)與(1)的區別在于，每次求得中斷點任務后，有些低優先權任務有可能阻塞非臨界區部分速度已確定的任務， 那么這些低優先權任務的臨界區部分的速度若未定義， 則其速度為中斷點任務臨界區部分的速度(算法j）~l)和p)~r))。因而在式(2)中區分開已定義的臨界區部分及未定義的臨界區部分。USFI算法（式(1)）中同一任務的臨界區及非臨界區部分具有相同的運行速度， 以Bi/ηns(τi)作為低優先權任務對任務τi的最大阻塞時間， 且低優先權任務的執行速度不大于高優先權任務的執行速度[8]。在任務實際運行中， 當任務被阻塞時， 臨界區的運行速度必須繼承被阻塞的高優先權任務的執行速度，以滿足實時可調度性。式(2)則區分開已定義的臨界區部分及未定義的臨界區部分， 在計算中已考慮實際運行時低優先權任務對高優先權任務的最大阻塞時間， 因而滿足任務運行時的實時性要求(見定理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)}。兩種情況下求出的速度應滿足分類條件的要求， 不符合則舍去；若同時滿足則選擇最小值作為非臨界區部分的執行速度。

性質1CSSFA中任一任務的非臨界區部分的速度均不大于有可能阻塞它的臨界區部分的速度。

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

由CSSFA可知，當其執行完畢后， 對于每個任務τi，至少存在某一個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有可能阻塞任務τi。

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

定理2CSSFA能保證所有任務在實際運行中的實時可調度性。

證明CSSFA執行完畢后， 對每個任務τi，式(3)均成立。證明方法類似文獻［12］， 采用反證法。若在運行中任務τi的某一實例在其截止期內無法完成，其絕對截止期為t，則假設t′為小于時間點t且在t′以前沒有優先權大于τi的任務實例到達的最晚時間點。若這樣的時間點t′不存在，則令t′=0。對任務τi的每個調度點Si， j∈Si，令A為在[t′，t′+Si，j]到達且優先權不小于τi的任務實例集合，B為在[t′，t′+Si，j]到達且優先權小于τi的任務實例集合，則根據PCP， 集合B中的任務實例在[t′，t′+Si，j]阻塞τi的時間至多為max{Ccs(zx，y)/ηcs(zx，y)}。其中zx，y有可能阻塞任務τi。集合A中的任務實例在[t′，t′+Si，j]執行時間至多為∑1≤r≤i[Cns(τr)/ηns(τr)+∑Ncs(τr)k=1Ccs(zr，k)/ηcs(zr，k)]「Si，j/Tr。根據假設， 任務τi錯失其截止期， 則對每個Si， j在時間長度為Si， j內有∑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除了在任務運行前計算其靜態的運行速度，在實際運行時針對特殊情況給出了其動態執行速度。

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

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

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

2．2調度成本分析

算法的調度成本包括靜態和動態調度成本兩個方面。靜態調度成本是指計算靜態速度的時間復雜度; 動態調度成本是指任務實例運行時速度調整時的開銷。

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

定義算法的動態調度成本為任務運行時速度調整的次數。對于非臨界區部分， CSSFA與USFI速度調整的次數相同;USFI的頻率繼承導致USFI對每個任務臨界區部分的速度調整次數比CSSFA最多多出（n-1）c次。因而CSSFA的動態調度成本優于USFI算法。

3試驗結果

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

3．1綜合測試結果

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

從圖1可以看出， CSSFA在調度性能上明顯優于USFI。當利用率U較小， 即任務能充分利用空閑時間降低其運行速度時， CSSFA較之USFI的調度性能提高的比例越高。這充分表明CSSFA固定臨界區速度使得非臨界區部分利用更多的空閑時間， 能有效地降低系統能耗。同時， 定理3給出的方法在實際運行中進一步降低了能耗。隨著U的提高， 即可用空閑時間的減少， 兩種算法的調度性能趨于一致。同時由2．2節的分析可知，CSSFA的動態調度成本明顯優于USFI算法， 在實際應用中能進一步提高調度性能。

3．2α對調度性能的影響

圖2給出當U為0.3時，α對調度性能的影響；其他參數隨機選取，橫坐標代表α值。

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

3．3資源數量對調度性能的影響

圖3給出當U為0.3時， 資源數量對調度性能的影響；其他參數隨機選取，橫坐標代表資源數量。由于

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

圖3表明隨著資源數量的增加，CSSFA較之USFI在調度性能提高的比例逐漸下降。原因在于根據PCP，每個任務在實際運行中最多只被低優先權任務阻塞一次， 因而任務被阻塞的概率隨之下降， 而CSSFA中任務臨界區部分執行速度固定且不小于被阻塞的任務非臨界區部分速度， 因而導致能耗提高。從試驗數據發現，當資源的數量及α都相對較大時， CSSFA在調度性能上遜于USFI算法。

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

參考文獻：

［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.

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