PLUFS: 一種開銷敏感的周期任務在線多處理器節能實時調度算法

張冬松　王　玨　趙志峰　吳　飛

1(鎮江船艇學院　江蘇鎮江　212001)2　(上海工程技術大學電子電氣工程學院　上海　201620)

?

PLUFS: 一種開銷敏感的周期任務在線多處理器節能實時調度算法

張冬松1王玨1趙志峰1吳飛2

1(鎮江船艇學院江蘇鎮江212001)2(上海工程技術大學電子電氣工程學院上海201620)

(dszhang@nudt.edu.cn)

摘要現有周期任務多處理器節能調度算法雖然在考慮處理器實際開銷情況下可以實現較好的節能效果，但仍不能保證最優可調度性.針對嵌入式實時系統中不可忽視的狀態切換開銷，提出一種開銷敏感的周期任務在線多處理器節能實時調度算法PLUFS.該算法通過TL面流調度模型與處理器實際切換開銷模型相結合，在每個TL面的初始時刻、任務結束執行時刻實現節能調度，在不違反周期任務集最優可調度性的前提下，達到實時約束與能耗節余的合理折中.經過理論證明和模擬實驗，結果表明：PLUFS算法不僅保證了周期任務集的最優可調度性，而且節能效果整體優于現有算法，能耗節余比現有算法提高約10%～20%.

關鍵詞開銷；多處理器系統；節能調度；周期任務；實時系統

隨著多核芯片和片上多處理器系統的不斷推出，多處理器平臺變得更加普遍，已經越來越多地被應用于各類實時系統領域.能耗管理已經成為嵌入式系統和服務器系統中一個重要的系統設計問題，可以用于延長電池使用壽命或降低用電成本.

在嵌入式實時系統中，基于動態電壓頻率調節(DVFS)技術[1]和動態功耗管理(DPM)技術[2]的節能實時調度已經被廣泛研究.節能實時調度就是在滿足實時約束下實現節能.許多研究者都在關注多處理器系統的實時節能調度問題，但很多研究成果都是在劃分法調度的基礎上針對周期或基于幀的任務模型而提出多處理器系統節能實時調度算法[3-4].文獻[3]首次提出一種基于劃分法的實時節能調度方法，指出多核系統中周期任務節能調度是一個NP-hard問題；文獻[4]通過研究多核處理器系統中各種硬件節能技術特點，指出不存在一種算法能夠滿足所有的情況和約束，各種節能調度算法都有其不同的適用條件，還有一些研究成果提出基于全局調度法的DVFS節能調度技術[5-7]；文獻[5]針對同構多處理器系統，使用全局EDF離線節能調度算法解決了周期性實時任務的系統級節能問題，但是僅僅通過離線統一分配任務執行速度來實現節能，沒有實現任務集的最優可調度性；文獻[6]針對周期任務集，基于一種最優全局實時調度算法LLREF[8]，提出多處理器最優離線節能調度方法，這種最優性未考慮轉換開銷；文獻[7]針對基于幀的任務模型，提出一種最優的節能實時調度算法LTF-M，該算法在考慮開銷的實際環境中不是最優的[9].

但是以上這些算法大多集中于各種開銷可以忽視的理想DVFS處理器，沒有考慮實際DVFS處理器具有的頻率更改開銷和狀態切換開銷等物理限制.對于許多硬實時應用來說，是否考慮開銷、考慮哪些開銷對節能實時調度可能產生較大影響，忽視這些細節可能會得到次最優甚至是無效的結果.例如如果狀態切換的能耗開銷大于能耗節余，那么顯然把處理器轉入睡眠狀態很可能不會節能[9].

面對越來越不容忽視的開銷問題，很多研究者已經開始關注具有處理器實際開銷限制的節能實時調度問題.文獻[10]根據工作負載確定活躍處理器的個數，并結合實際處理器具有的狀態切換開銷提出節能實時調度算法;文獻[11]則進一步考慮具有離散速度的系統，針對有向無環圖任務模型，提出啟發式節能實時調度算法;而文獻[9]通過說明關鍵速度的非最優性以及負載均衡的非最優性，針對基于幀的任務模型和周期任務模型，提出了一種考慮狀態切換開銷的節能實時調度算法,該算法顯著地優于原有未考慮開銷情況下的近似算法[12];文獻[13]基于劃分調度方法，提出一種考慮實際處理器狀態切換開銷的在線節能實時調度算法.雖然現有的周期任務多處理器節能調度算法在考慮處理器實際開銷情況下可以實現較好的節能效果，但不能保證最優可調度性.

為此，本文針對具有獨立DVFS和DPM技術的多處理器系統，在考慮處理器狀態切換開銷情況下，提出一種基于切換開銷的周期任務在線節能實時調度算法PLUFS(periodic tasks with largest utilization first based on switching overhead),該算法首先利用流調度模型將所有任務實例的絕對截止期在時間軸上表示為若干個兩兩相連且不重疊的TL(time local)面，然后在每個TL面的初始時刻，采用最大任務利用率優先策略和處理器切換開銷模型來確定每個TL面內所有周期任務的最優執行速度和最優可用處理器個數，接下來確定TL面內所有任務的調度過程；最后在TL面內任務結束執行時刻，通過維護TL面內任務調度序列和處理器狀態切換，在保證周期任務集的最優可調度性下實現節能.

本文的主要貢獻如下：

1) 針對常見的周期任務模型，將TL面流調度思想與考慮切換開銷的最優節能策略有機結合起來，提出一種開銷敏感的在線多處理器節能實時調度算法PLUFS，在滿足硬實時約束的條件下獲得了合理的能量節余.

2) 經過系統的理論分析以及大量的模擬實驗，既給出了所提PLUFS算法的最優可調度性證明，又驗證了PLUFS的節能效果整體優于現有算法，接近于理論最優值.

1系統模型與問題定義

1.1處理器模型

本文假設多處理器系統由m個同構處理器構成，m為常數，處理器命名為{cpu1,cpu2,…,cpum}.處理器cpuk以速度(或稱為頻率)s運行時的功耗Pk(s)=α×s3+β[14]，α>0，β≥0.這種功耗模型適用于多種具有DVFS和DPM技術的處理器，例如Intel Xscale處理器[14].顯然，Pk(s)是嚴格凸函數和遞增函數.假設同構多處理器可以在最低處理器速度smin和最高處理器速度smax之間連續調節.

處理器以速度s執行一個時鐘周期的能耗為P(s)s=α×s2+βs.P(s)s是凸函數[15]，使得該函數具有最小值的速度即是關鍵速度s*.這里關鍵速度定義為處理器執行一個時鐘周期所用能耗最小時的速度[7,9].顯然，s*滿足如下性質[9,14]：?s，smin≤s≤smax，P(s*)s*≤P(s)s.

處理器有2種狀態：睡眠狀態和活躍狀態.當處理器處于睡眠狀態時，DPM技術可以關閉處理器時鐘，將處理器電壓降低到非常低的水平，以至于處理器功耗可以忽略不計，近似為0[9].執行任務的處理器則處于活躍狀態.由于睡眠狀態中處理器上下文等信息不被保存，所以返回活躍狀態需要一定的時間和能量開銷[9].不妨定義處理器狀態切換的時間開銷為tsw，處理器狀態切換的能量開銷為Esw，處理器從活躍狀態轉入睡眠狀態的break-even時間為tθ.當處理器的空閑時間大于break-even時間時，將處理器轉入睡眠狀態是節能的.通常假設break-even時間tθ為狀態切換能耗開銷Esw與處理器空閑時功耗Pidle之比，并且大于狀態切換時間開銷tsw[9].這里空閑功耗Pidle為常量，且不小于處理器在最低速度時的功耗P(smin)，即Pidle≥P(smin).此外，處理器的狀態切換時間開銷是毫秒級，而頻率更改時間開銷是微秒級，狀態切換時間開銷遠大于頻率更改時間開銷[9].

1.2任務模型

本文考慮多處理器DVFS系統中周期實時任務集T={τ1,τ2,…,τn}，任務τi用二元組(pi,Ci)表示，其中：pi是周期，Ci是任務τi在最高頻率下的最壞情況執行時間或執行時鐘數.所有周期實時任務具有相同的初始釋放時間.每個周期任務具有無窮序列的任務實例τi j∈{τi1,τi2,…}，又稱為作業.任務τi的每個任務實例都按照相同周期釋放.任務τi的相對截止期等于周期，任務實例τi,k的絕對截止期di,k=k×pi，其釋放時間ri,k=(k-1)×pi.任務τi的利用率為ui=Cipi，任務集的總利用率為ui,τi∈T.任務τi在最高處理器速度下的最壞情況執行時間Ci是預先已知的.假設所有的任務都是獨立的，允許在任意時刻在多處理器之間搶占和遷移.

為保證周期任務集的最優可調度性，任務調度算法借鑒基于TL面的流調度思想[8]，以一個時間片(即TL面)為單位，通過與節能策略相結合，實現實時任務節能調度算法.簡單地說，TL面是一個二維平面，水平軸表示時間，垂直軸表示任務的局部剩余執行時間(local remaining execution time).TL面之間相互連續且互不重疊[8].在TL面內任意時刻t，每個任務τi均有一個局部剩余執行時間li,t≥0.如果在TL面的結束時刻，所有任務的局部剩余執行時間均為0，則稱所有任務是局部可調度的[8].

1.3問題定義

考慮一個獨立周期任務集T在m個同構多處理器上節能調度執行.每個處理器具有相同的功耗函數P(s)=α×s3+β，α,β≥0.每個處理器的執行速度均在smin和smax之間.每個周期任務具有最壞情況執行時間或執行時鐘數和周期，且相對截止期等于周期.處理器從睡眠狀態轉入活躍狀態的切換能耗開銷為Esw，同時時間開銷為tsw≤EswP(smin).本文目標在于考慮處理器切換開銷條件下保證周期任務集的最優可調度性的同時盡可能地降低系統能耗.

2PLUFS算法

2.1基本思想

盡管研究者已經提出了不少多處理器節能實時調度算法，但是這些算法大多考慮的是沒有考慮開銷的理想情況.對于越來越不容忽視的處理器開銷問題，雖然已有研究者提出了針對周期任務模型的開銷敏感多處理器節能實時調度算法，但是該算法只能在低負載情況下獲得較好的節能效果，無法保證在高負載情況下任務的可調度性.針對基于幀的實時任務模型，我們之前的研究成果已提出考慮實際切換開銷情況下的多處理器最優節能實時調度算法LUF-SO[16].試想，能否考慮把LUF-SO算法直接應用到周期任務集呢？答案是否定的.原因在于周期任務集中所有任務都具有的相同周期應該是超周期，但在超周期內每個任務具有多個任務實例，這些任務實例的絕對截止期又不相同，所以直接應用LUF-SO算法得到的調度序列無法保證周期任務集的可調度性.

接下來，通過對2種基于TL面的周期任務最優多處理器實時調度LLREF[8]算法和LRE-TL算法[17](這里將周期任務看作是偶發任務的特例)分析可知，如果在每個TL面的初始時刻為每個任務分配與任務利用率成比例的局部剩余執行時間，并且要求在TL面的結束時刻之前所有任務必須完成其局部剩余執行時間，那么每個TL面的結束時刻可以作為TL面所有任務的局部截止期.顯然，每個TL面內具備局部剩余執行時間的所有任務具有相同的局部截止期，這一特性符合基于幀的實時任務模型的要求.因此，本文將LUF-SO中離線節能調節策略與TL面中在線實時調度相結合，提出一種針對周期任務集的開銷敏感在線節能實時調度算法PLUFS.

PLUFS算法采用最大任務利用率優先策略[16]，在考慮處理器實際狀態切換開銷情況下，在每個TL面的初始時刻計算最壞情況下周期任務集的最優可用處理器個數和任務的最優執行速度，從而確定所有任務在每個TL面內的節能實時調度序列.在每個TL面邊界上，PLUFS算法將初始化TL面；在每個TL面內，PLUFS算法處理所有的任務結束執行事件.TL面初始化程序會根據當前TL面的時間長度，為新的TL面重新計算所有的參數，確定任務的調度過程和處理器的執行速度.任務結束執行事件處理程序用于維護TL面內任務調度過程的正確性和處理器狀態切換.一旦初始化或任務結束執行事件處理程序被完成，PLUFS算法將指導每個處理器按照分配的頻率來執行被指派的任務.

2.2主程序描述

PLUFS算法由3個程序構成，主程序描述如算法1所示.PLUFS首先初始化參數，令當前時刻tc和當前TL面的結束時刻tf均為0(見算法1中行①)，然后在每個TL面初始時刻，PLUFS將調用TL面初始化程序(見行③～⑤)，計算每個TL面內周期任務集在考慮切換開銷情況下最優的可用處理器個數和每個任務的執行速度，在線調節所有任務的調度序列，實現TL面中節能實時調度.在每個TL面內任意時刻，一旦某個處理器上發生任務結束執行事件，PLUFS將調用任務結束執行事件處理程序(見行⑥～⑧)，確保TL面內任務調度過程和處理器狀態切換的正確性.一旦初始化或事件被完成，PLUFS會循環等待直到下一個初始化或事件發生(見行②～⑧).

算法1. PLUFS.

①tc←0,tf←0;

② while TRUE do

③ iftc=tfthen

④PLUFS_TL_Initialize();

⑤ endif

⑥ if 處理器cpuk上任務τi在當前時刻tc結束執行 then

⑦Upon_Task_End_Execution(τi,tc,k);

⑧ endif

本文采用與文獻[8]相同的方法來劃分TL面，每個任務實例的絕對截止期就是一個TL面的結束時刻.顯然，對于任意TL面σ和任一任務τi，τi中最多有一個任務實例與TL面σ重疊.因為所有的實時調度策略都是基于一個TL面而產生的，所以只有與當前TL面重疊的任務實例才會被調度.

2.3TL面初始化

算法2.PLUFS_TL_Initialize().

① for 所有在當前時刻tc到達的任務τido

② ifHD.find_key(tc+pi)=NULL then

③HD.insert(tc+pi);

④ endif

⑤ endfor

⑥tf←HD.extract_min();

⑦D←tf-tc;

⑧ 按照任務利用率ui的非遞增順序排列所有任務τi∈T;

⑩ ifU>mor ?τi∈Tsuch thatui>1 then

andi←i+1;

PLUFS算法使用一個HD堆結構來保存當前所有任務的絕對截止期.HD堆結構包含3種方法.其中，如果關鍵字等于k的對象在HD堆中存在，則HD.find_key(k)返回該對象的指針，否則返回為空；HD.insert(I)方法將關鍵字I插入到HD堆中；HD.extract_min()方法從HD堆中刪除具有最小關鍵字的對象.這3種方法的計算復雜度均為O(log(HD堆大小)).

算法2的具體思想如下：

2) 當ui≥s*時，如果ui>UM，則說明任務τi是重任務(heavy)，需要單獨在一個處理器上執行，它的速度τi.speed為ui，更新參數U和M之后繼續后續任務的判斷(見行)；否則，說明當前未分配速度的所有任務利用率均不大于任務集的平均速度，這些任務?τj∈{τi,τi+1,…,τ|T|}都是輕任務(light)，其速度τj.speed均為UM(見行).

3) 當ui

一旦確定每個TL面的時間長度D和每個任務的局部剩余執行時間li=ui×D，PLUFS算法就可以采用與原有LUF-SO相同的方法，基于任務的最壞情況執行時間確定TL面初始時刻的任務調度序列.但由于每個TL面的時間長度各不相同，使得任務集在每個TL面內具有不同的任務調度序列和執行速度，所以PLUFS屬于在線算法.

定理1. 在每個TL面初始時刻t0，如果PLUFS算法通過算法2來確定周期任務集T在TL面[t0,tf]內的任務調度序列，則該任務調度序列可以保證T中所有任務在當前TL面的結束時刻tf之前完成其局部剩余執行時間.

證畢.

2.4任務結束執行事件

算法3. Upon_Task_End_Execution(τi,tc,k).

① if 在處理器cpuk上沒有任務等待執行 then

② iftf-tc>tθthen

③ 將處理器cpuk轉入睡眠狀態;

④ else

⑤ iftf>tcthen

⑥ 將處理器cpuk轉入空閑狀態;

⑦ endif

⑧ endif

⑨ else

⑩ 處理器cpuk繼續以τi.speed×smax為速度值，按照TL面初始化分配的時間間隔來調度執行后續任務;

定理2. 如果PLUFS算法通過算法3來處理每個TL面內任務結束執行事件，那么對該事件的處理不會影響到TL面初始時刻所確定的任務調度序列.

證明. 由算法3易知，當周期任務τi在某個處理器cpuk上結束執行時，如果處理器cpuk上沒有任務等待執行，那么算法3只是根據此時所產生的靜態松弛時間大小判斷是否將該處理器轉入睡眠狀態或者空閑狀態，并沒有涉及到對其他處理器上任務的處理.而如果處理器cpuk上任務隊列不為空，還有后續任務等待執行，那么算法3不會改變算法2為后續任務分配的開始執行時間與結束執行時間，后續任務在處理器cpuk上的執行序列和執行速度沒有變化.得證.

證畢.

3算法分析

3.1可調度性分析

由于不考慮周期任務集為不可調度的情況，如不做特殊說明，本文均假設周期任務集T滿足U≤m，且?τi∈T，ui≤1.

定理3. 如果周期任務集T使用PLUFS算法調度執行，則T中所有任務在每個TL面內是局部可調度的.

證明. 反證法.所有任務在TL面內具有局部可調度性的定義是指在TL面的結束時刻所有任務的局部剩余執行時間均為0.如果周期任務集T在某個TL面內是局部不可調度的，那么在該TL面的結束時刻一定存在某個任務τi的局部剩余執行時間不為0.已知每個周期任務在PLUFS算法下只能在每個TL面內初始時刻、任務結束執行時刻被調度執行.由定理2可知，任務τi的調度序列是在當前TL面初始時刻被確定，而在每個TL面內任意的任務結束執行時刻，PLUFS算法對任務結束執行事件的處理不會影響到當前TL面初始時刻所確定的任務調度序列.再由假設條件易知，在當前TL面初始時刻所確定的任務調度序列無法保證任務τi在當前TL面結束時刻之前完成其局部剩余執行時間.這與定理1矛盾，命題得證.

證畢.

定理4. PLUFS算法可以保證周期任務集T的最優可調度性.

證明. 因為所有的TL面是連續的，且兩兩獨立，沒有重疊區域，前一個TL面的結束時刻是后一個TL面的開始時刻，所以可以采用歸納法證明.因為周期任務集T滿足U≤m且?τi∈T，ui≤1，所以根據PLUFS算法和定理3可知任務集T在第1個TL面內是可調度的.又因為由定理3可知任務集T在第2個TL面內也是可調度的，根據歸納假設可知PLUFS算法可以保證任意連續多個TL面的局部可調度性，從而可得所有任務均滿足其截止期.命題得證.

證畢.

3.2復雜度分析

設任務集T中任務總數為n，處理器數為m，每個任務狀態數量為w，每個處理器狀態數量為v.

1) 時間復雜度.算法3中行②～⑧的切換處理器狀態以及行⑩的調度后續任務繼續執行，每步的時間復雜度均為常量，因此算法3的時間復雜度為O(1).

PLUFS算法的運行時間依賴于它所調用的程序，如算法1所示.算法1的行①參數初始化的時間復雜度為O(1).根據算法2可知，算法1中最大搶占和遷移次數均為O(m).因此，算法1中行②～⑧之間有一個循環，任務結束執行事件處理程序在每個TL面內被調用次數為O(n+m).

2) 空間復雜度.如果采用順序表存儲，任務集T所占用的空間為O(n×w)，處理器狀態所占用的空間為O(m×v).因為HD堆中只存放一個關鍵字即任務的絕對截止期，所以HD堆所占用的空間為O(n).

4實驗

本文在Linux 2.6環境下采用C語言編寫了一個離散事件模擬器，針對具有獨立DVFS和DPM的多處理器系統，實現了多種周期任務節能實時調度算法，包括非節能的P-LRE-TL算法[17]、Independent RT-SVFS算法[6]、P-RSLTF算法[9]、PLUFS算法以及Lower-Bound算法[9].其中，P-LRE-TL算法是對LRE-TL算法用于周期任務模型的簡稱，選用它的原因在于其計算復雜度遠小于LLREF算法[8]；Lower-Bound算法是忽視處理器開銷條件下的理論最優算法，而其他算法可看作真實算法.Lower-Bound算法允許將所有任務以關鍵速度執行，它的能耗可以作為考慮開銷條件下實際最優能耗的下界[9].

本文以P-LRE-TL算法的能耗作為標準進行歸一化，比較算法的歸一化能耗(normalized energy consumption, NEC)，然后比較可調度性(feasibility performance, FP)，最后對可調度性與歸一化能耗之比(簡記FPNEC)這個綜合指標進行比較；此外，還比較算法在不同切換能耗開銷情況下的歸一化能耗與不同最小可用速度情況下的歸一化能耗.

4.1參數產生

為更貼近真實任務集，實驗引入下列環境參數：usys，m和n.usys表示系統利用率，m表示處理器個數，n分別表示任務個數，周期任務集的總負載Workloads=usys×m.每個任務利用率ui使用Uunifast算法[18]而產生，這樣不僅有助于分析利用率與任務集中任務個數的關系，還可以產生n個任務利用率在[0,Workloads]的無偏分布.每個任務的周期pi在[1,1000] ms之間均勻分布，可以模擬絕大多數硬實時應用.每個任務τi的最壞情況執行時間Ci=ui×pi.

為了全面評價算法的性能，模擬實驗采用了3種不同的參數設置：1)系統利用率usys從10%開始增加到100%，步長是10%；處理器個數m分別設為4，8和16，任務個數n分別設為10，20和40，且smin=0，Esw=1 mJ；2)切換能耗開銷Esw從0.2 mJ增加到1.5 mJ，步長是0.05 mJ；系統利用率usys分別設為0.1，0.3和0.7，處理器個數m=8，任務個數n=20，smin=0；3)最小可用速度smin從0 GHz增加到0.25 GHz，步長是0.0125 GHz；系統利用率usys分別設為0.1，0.3和0.7，處理器個數m=8，任務個數n=20，Esw=1 mJ.模擬時間為每組任務集的“超周期”，即任務集中所有任務周期的最小公倍數.對于每種參數設置，本文測試100 000組任務集，取平均能耗值以便較真實地反映算法性能.

4.2實驗結果

Fig. 1　Normalized energy consumption changing with workloads.圖1　歸一化能耗

圖1給出了在考慮處理器實際切換開銷的情況下，P-LRE-TL，Independent RT-SVFS，P-RSLTF，PLUFS以及Lower-Bound算法在第1種參數設置下的周期任務集的歸一化能耗.從圖1(a)中可知，當處理器個數為4、任務集中任務個數為10時，不論任務集的總負載如何變化，PLUFS算法的節能效果除了差于理論最優Lower-Bound算法以外，優于其他真實算法，尤其在低負載情況下能耗節余比Independent RT-SVFS算法高約20%，高負載情況下能耗節余比P-RSLTF算法高約10%.

一方面，在系統利用率小于0.3的低負載情況下，PLUFS算法與P-RSLTF算法的能耗節余比較接近，兩者都比Independent RT-SVFS算法具有更多的節能.這是因為Independent RT-SVFS算法靜態地將任務集中所有任務分配到所有的處理器上執行[6]，離線確定每個處理器的狀態切換情況，運行時不再改變節能策略，而低負載情況很可能會產生頻繁的狀態切換，導致切換開銷大于能耗節余，說明它不能較好適應因系統利用率降低而產生的動態負載變化.而PLUFS算法與P-RSLTF算法均考慮到狀態切換開銷問題，允許任務運行在比關鍵速度更低的速度來減少狀態切換次數，可以更好地適應動態負載變化，從而實現更多的節能.

另一方面，在系統利用率大于0.3的高負載情況下，P-RSLTF算法與Independent RT-SVFS算法的能耗節余比較接近，隨著總負載的增加，兩者的能耗節余不斷減少.雖然PLUFS算法獲得的能耗節余也不斷減少，但是更接近于Lower-Bound算法的能耗節余.這是因為P-RSLTF算法基于劃分方法來調度周期任務集而只能實現降低部分任務的執行速度，Independent RT-SVFS算法屬于靜態節能調度方法，隨著總負載的增加，所有的處理器都會運行以滿足任務集可調度性的要求，此時這2種算法無法實現任務集在更多處理器上減少狀態切換次數，不適應高負載情況下動態負載變化.但是PLUFS算法可以在保證周期任務集最優可調度性的同時，根據處理器開銷模型和每個TL面的時間長度確定在每個TL面中所有任務的節能實時調度序列，能夠利用完全動態的任務實例級遷移來減少狀態切換次數，確保在高負載情況下也能取得較好的節能效果.

另外，當處理器核數m=8，任務個數n=20(如圖1(b)所示)和處理器核數m=16，任務個數n=40(如圖1(c)所示)時，可以得到與圖1(a)相類似的結論，這反映出在不同處理器核數條件下，除了Lower-Bound算法以外，PLUFS算法的節能效果整體優于其他真實算法，其能耗節余隨著總負載的增加而緩慢減少.

同時，在圖1(a)～(c)中還可以注意到，在系統利用率最高時的高負載情況下，P-RSLTF算法的歸一化能耗值不存在，例如在處理器核數和任務集總負載均為4，在處理器核數m=8而任務集總負載為8，以及處理器核數m=16而任務集總負載為16.這是因為P-RSLTF算法基于最大任務優先策略實現超周期內周期任務的劃分調度，只考慮在可調度任務集下的平均能耗值，而在高負載情況下無法實現任務集的可調度性，故而平均能耗值不存在，如圖2所示：

Fig. 2　Feasibility performance changing with workloads.圖2　隨負載變化的可調度性分析

基于與圖1相同的實驗參數設置，圖2給出了算法的可調度性.從圖2(a)中可知，PLUFS和Independent RT-SVFS算法均能保證最優可調度性，P-RSLTF算法的可調度性卻隨著總負載的增加而不斷降低，直至近似為0.這是因為PLUFS和Independent RT-SVFS算法均是基于TL面的流調度思想來實現最優實時任務調度，而P-RSLTF算法本質上還是多處理器劃分任務調度方法，不具有最優可調度性[9].另外，從圖2(a)～(c)中可以看出，PLUFS算法在不同實驗參數下，均可以在實現節能的同時保證周期任務集的可調度性.

Fig. 3　Feasibility performance normalized energy consumption.圖3　可調度性與歸一化能耗之比(FPNEC)

為了全面衡量各個節能實時調度算法的性能，基于與圖2相同的實驗參數設置，圖3給出了可調度性與歸一化能耗之比.從圖3(a)中可知，不論任務集的總負載如何變化，PLUFS算法的FPNEC值最接近Lower-Bound算法，但大于其他真實算法，并且隨著總負載的增加，該FPNEC值從5.8左右緩慢減小到1左右.這是因為PLUFS算法不僅保證了最優可調度性，而且能耗節余較多.Independent RT-SVFS算法的FPNEC值則隨著總負載的增加，先增后減，在系統利用率大于0.3之后逐漸趨近于非節能P-LRE-TL算法的FPNEC值，這恰好反映了Independent RT-SVFS算法的靜態節能實時調度特性.而P-RSLTF算法的FPNEC值在系統利用率小于0.3時接近PLUFS算法，但在系統利用率大于0.3時，其FPNEC值逐漸減小直至為0.這是因為P-RSLTF算法在高負載情況下可調度性不斷降低，且能耗節余不斷減少.另外，從圖3(b),(c)中可以得到與圖3(a)相一致的結論，這反映在不同實驗參數條件下，除了Lower-Bound算法以外，PLUFS算法的FPNEC值大于其他真實算法.

圖4給出了在考慮處理器不同切換能耗開銷情況下，P-LRE-TL，Independent RT-SVFS，P-RSLTF，PLUFS以及Lower-Bound算法在第2種參數設置下的周期任務集的歸一化能耗.從圖4(a)中可知，當處理器個數m=8、任務集中任務個數n=20、最小可用速度為0和總負載為0.8時，不論處理器的切換能耗開銷如何變化，PLUFS算法的節能效果除了差于理論最優Lower-Bound算法以外，優于其他真實算法.這是因為Independent RT-SVFS算法屬于靜態節能調度方法，本身并沒有考慮切換能耗開銷，不受切換能耗開銷變化的影響.P-RSLTF算法基于任務利用率來計算不同任務劃分方法中所有任務的執行速度，使得任務調度序列中存在大量小塊的空閑時間，而PLUFS算法也是基于任務利用率計算每個TL面內所有任務的執行速度，同樣會產生大量小塊的空閑時間，這些空閑時間的存在使得無法更多地減少狀態切換次數，因此僅僅減少切換能耗開銷不會對2種算法節能效果產生較大的影響.Lower-Bound算法本身沒有考慮處理器切換開銷情況，顯然不受切換能耗開銷變化的影響.

Fig. 4　Normalized energy consumption under different energy switching overheads.圖4　不同切換能耗開銷情況下歸一化能耗

當總負載為2.4(如圖4(b)所示)和總負載為5.6(如圖4(c)所示)時，可以得到與圖4(a)相類似的結論，這反映出在不同總負載情況下，不論切換能耗開銷如何變化，除了Lower-Bound算法以外，PLUFS算法的節能效果整體優于其他真實算法，其能耗節余隨著總負載的增加而緩慢減少.

Fig. 5　Normalized energy consumption under different minimum available speeds.圖5　不同最小可用速度情況下歸一化能耗

圖5給出了在考慮處理器不同最小可用速度情況下，P-LRE-TL，Independent RT-SVFS，P-RSLTF，PLUFS以及Lower-Bound算法在第3種參數設置下周期任務集的歸一化能耗.從圖5(a)中可知，當處理器個數m=8、任務集中任務個數n=20、切換能耗開銷為1.0 mJ和總負載為0.8時，不論處理器的最小可用速度如何變化，PLUFS算法的節能效果除了差于理論最優Lower-Bound算法以外，優于其他真實算法.這是因為處理器的最小可用速度主要用于計算處理器空閑功耗和進入睡眠狀態的break-even時間，隨著最小可用速度的減小，處理器空閑功耗會減少，而break-even時間會增大.Independent RT-SVFS算法屬于靜態節能調度方法，運行時處理器的電壓和頻率不能改變，所以隨著最小可用速度的減小，空閑功耗會減少，導致能耗節余會有所增加.Lower-Bound算法不僅沒有考慮處理器切換開銷情況，還不允許任務以低于關鍵速度來執行，而實驗中最小可用速度的最大取值仍小于關鍵速度，所以該算法不受最小可用速度變化的影響.P-RSLTF算法和PLUFS算法都是基于任務利用率來計算所有任務的執行速度，在任務調度序列中都存在大量小塊的空閑時間，空閑功耗的減少和break-even時間的增大會使得處理器傾向于空閑狀態，但這樣又會增加可用處理器個數，同樣會增加能耗，因此最小可用速度的變化對2種算法節能效果的影響有限.

當總負載為2.4(如圖5(b)所示)和總負載為5.6(如圖5(c)所示)時，可以得到與圖5(a)相類似的結論，這反映出在不同總負載情況下，不論最小可用速度如何變化，除了Lower-Bound算法以外，PLUFS算法的節能效果整體優于其他真實算法，其能耗節余隨著總負載的增加而緩慢減少.

5結束語

本文針對具有獨立DVFS的多處理器系統，在考慮處理器狀態切換開銷情況下，提出一種基于周期任務模型的在線節能實時調度算法PLUFS.1)該算法利用TL面流調度模型將周期任務調度分解為每個TL面內任務調度問題；2)在每個TL面的初始時刻，采用最大任務利用率優先策略來確定具有最低能耗值的活躍處理器個數，再根據狀態切換時間和能量開銷來確定任務調度序列；3)在TL面內任務結束執行時刻，通過維護TL面內任務調度序列和處理器狀態切換，在保證周期任務集的最優可調度性下實現節能.系統的理論分析證明了PLUFS算法的最優可調度性.大量的模擬實驗結果表明PLUFS算法不僅可以保證周期任務集的最優可調度性，而且整體優于現有算法，尤其在低負載情況下能耗節余比Independent RT-SVFS算法高約20%，高負載情況下能耗節余比P-RSLTF算法高約10%.

參考文獻

[1]Rele S, Pande S, Onder S, et a1. Optimizing static power dissipation by functional units in superscalar processors[G]LNCS 2304: Proc of the 11th Int Conf on Compiler Construction. Berlin: Springer, 2002: 261-275

[2]Chandrakasan A, Sheng S, Brodersen R. Low-power CMOS digital design[J]. IEEE Journal of Solid-State Circuit, 1992, 27(4): 473-484

[3]Yang C, Chen Jianjia, Luo T. An approximation algorithm for energy-efficient scheduling on a chip multiprocessor[C]Proc of Design, Automation and Test in Europe. Piscataway, NJ: IEEE, 2005: 468-473

[4]Rotem E, Mendelson A, Ginosar R, et al. Multiple clock and voltage domains for chip multiprocessors[C]Proc of the 42nd Annual IEEEACM Int Symp on Microarchitecture. New York: ACM, 2009: 459-468

[5]Anderson J, Baruah S. Energy-efficient synthesis of periodic task systems upon identical multiprocessor platforms[C]Proc of the 24th Int Conf Distributed Computing Systems. Piscataway, NJ: IEEE, 2004: 428-435

[6]Funaoka K, Kato S, Yamasaki N. Energy-efficient optimal real-time scheduling on multiprocessors[C]Proc of the 11th IEEE Symp on Object Oriented Real-Time Distributed Computing. Piscataway, NJ: IEEE, 2008: 23-30

[7]Chen Jianjia. Energy-efficient scheduling for real-time tasks in uniprocessor and homogeneous multiprocessor systems[D]. Taibei, Taiwan: National Taiwan University, 2006

[8]Cho H, Ravindran B, Jensen ED, An optimal real-time scheduling algorithm for multiprocessors[C]Proc of the 27th IEEE Real-Time System Symp. Piscataway, NJ: IEEE, 2006: 101-110

[9]Chen Jianjia, Thiele L, Energy-efficient scheduling on homogeneous multiprocessor platforms[C]Proc of ACM Symp on Applied Computing. New York: ACM, 2010: 542-549

[10]Xu R, Zhu D, Melhem R, et al. Energy-efficient policies for embedded clusters.[C]Proc of ACM SIGPLANSIGBED Conf on Languages, Compilers, and Tools for Embedded Systems. New York: ACM, 2005: 1-10

[11]Langen P J D, Juurlink B H H. Leakage-aware multiprocessor scheduling for low power[C]Proc of Parallel and Distributed Processing Symp. Piscataway, NJ: IEEE, 2006: 80-87

[12]Horn WA. Some simple scheduling algorithms[J]. Naval Research Logistics Quarterly, 1974, 21(1): 177-185

[13]Huang H, Xia F, Wang J, et al. Leakage-aware reallocation for periodic real-time tasks on multicore processors[C]Proc of the 5th Int Conf on Frontier of Computer Science and Technology. Piscataway, NJ: IEEE, 2010: 85-91

[14]Zhu D. Reliability-aware dynamic energy management in dependable embedded real-time systems[C]Proc of the 12th IEEE Real-Time and Embedded Technology and Applications Symp. Piscataway, NJ: IEEE, 2006: 397-407

[15]Irani S, Shukla S, Gupta R. Algorithms for power savings[C]Proc of the 14th Annual ACM-SIAM Symp on Discrete Algorithms. New York: ACM, 2003: 37-46

[16]Zhang Dongsong, Wu Fei, Chen Fangyuan, et al. An overhead-aware optimal energy-efficient real-time scheduling algorithm on multiprocessors[J]. Chinese Journal of Computers, 2012, 35(6):1297-1312 (in Chinese)(張冬松, 吳飛, 陳芳園, 等. 開銷敏感的多處理器最優節能實時調度算法[J]. 計算機學報, 2012, 35(6): 1297-1312)

[17]Funk S, Nadadur V. LRE-TL: An optimal multiprocessor algorithm for sporadic task sets[C]Proc of Conf on Real-Time and Network Systems (RTNS). Paris: INRIA HAL, 2009: 159-168[18]Bini E, Buttazzo G C. Measuring the performance of schedulability tests[J]. Journal of Real-Time Systems, 2005, 30(12): 129-154

Zhang Dongsong, born in 1980. PhD and Lecturer. His main research interests include real-time theory and green computing.

Wang Jue, born in 1987. Master and teaching assistant. His main research interests include database application and real-time scheduling.

Zhao Zhifeng, born in 1970. PhD and associate professor. His main research interests include bigdata application and real-time scheduling.

Wu Fei, born in 1968. PhD and professor. Senior member of China Computer Federation. His main research interests include green computing, parallel computing and information intelligent process.

收稿日期：2016-03-11；修回日期：2016-05-16

基金項目：國家自然科學基金項目(61402527,61272097)

中圖法分類號TP316.4

PLUFS: An Overhead-Aware Online Energy-Efficient Scheduling Algorithm for Periodic Real-Time Tasks in Multiprocessor Systems

Zhang Dongsong1, Wang Jue1, Zhao Zhifeng1, and Wu Fei2

1(ZhenjiangWatercraftCollege,Zhenjiang,Jiangsu212001)2(CollegeofElectronicandElectricalEngineering,ShanghaiUniversityofEngineeringScience,Shanghai201620)

AbstractAlthough some existing multiprocessor energy-efficient approaches for periodic real-time tasks can achieve more energy savings with taking practical overhead of processor into consideration, they cannot guarantee the optimal feasibility of periodic tasks. For the non-ignorable overhead of switching the processor state in embedded real-time systems, this paper proposes an overhead-aware online energy-efficient real-time scheduling algorithm in multiprocessor systems, the periodic tasks with largest utilization first based on switching overhead (PLUFS). PLUFS utilizes the fluid scheduling concept of time local (TL) remaining execution plane and the switching overhead of the processor states to implement energy-efficient scheduling for real-time tasks in multiprocessors at the initial time of each TL plane as well as at the end execution time of a periodic task in each TL plane. Consequently, PLUFS can obtain a reasonable tradeoff between the real-time constraint and the energy-saving while realizing the optimal feasibility of periodic tasks. Mathematical proof and extensive simulation results demonstrate that PLUFS guarantees the optimal feasibility of periodic tasks, and on average saves more energy than existing algorithms, and improves the saved energy of some existing algorithms by about 10% to 20% at the same time.

Key wordsoverhead; multiprocessor systems; energy-efficient scheduling; periodic task; real-time system

This work was supported by the National Natural Science Foundation of China (61402527,61272097).