張冬松　王　玨　趙志峰　吳　飛

1(鎮(zhèn)江船艇學(xué)院　江蘇鎮(zhèn)江　212001)2　(上海工程技術(shù)大學(xué)電子電氣工程學(xué)院　上海　201620)

?

PLUFS: 一種開(kāi)銷(xiāo)敏感的周期任務(wù)在線(xiàn)多處理器節(jié)能實(shí)時(shí)調(diào)度算法

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

1(鎮(zhèn)江船艇學(xué)院江蘇鎮(zhèn)江212001)2(上海工程技術(shù)大學(xué)電子電氣工程學(xué)院上海201620)

(dszhang@nudt.edu.cn)

摘要現(xiàn)有周期任務(wù)多處理器節(jié)能調(diào)度算法雖然在考慮處理器實(shí)際開(kāi)銷(xiāo)情況下可以實(shí)現(xiàn)較好的節(jié)能效果，但仍不能保證最優(yōu)可調(diào)度性.針對(duì)嵌入式實(shí)時(shí)系統(tǒng)中不可忽視的狀態(tài)切換開(kāi)銷(xiāo)，提出一種開(kāi)銷(xiāo)敏感的周期任務(wù)在線(xiàn)多處理器節(jié)能實(shí)時(shí)調(diào)度算法PLUFS.該算法通過(guò)TL面流調(diào)度模型與處理器實(shí)際切換開(kāi)銷(xiāo)模型相結(jié)合，在每個(gè)TL面的初始時(shí)刻、任務(wù)結(jié)束執(zhí)行時(shí)刻實(shí)現(xiàn)節(jié)能調(diào)度，在不違反周期任務(wù)集最優(yōu)可調(diào)度性的前提下，達(dá)到實(shí)時(shí)約束與能耗節(jié)余的合理折中.經(jīng)過(guò)理論證明和模擬實(shí)驗(yàn)，結(jié)果表明：PLUFS算法不僅保證了周期任務(wù)集的最優(yōu)可調(diào)度性，而且節(jié)能效果整體優(yōu)于現(xiàn)有算法，能耗節(jié)余比現(xiàn)有算法提高約10%～20%.

關(guān)鍵詞開(kāi)銷(xiāo)；多處理器系統(tǒng)；節(jié)能調(diào)度；周期任務(wù)；實(shí)時(shí)系統(tǒng)

隨著多核芯片和片上多處理器系統(tǒng)的不斷推出，多處理器平臺(tái)變得更加普遍，已經(jīng)越來(lái)越多地被應(yīng)用于各類(lèi)實(shí)時(shí)系統(tǒng)領(lǐng)域.能耗管理已經(jīng)成為嵌入式系統(tǒng)和服務(wù)器系統(tǒng)中一個(gè)重要的系統(tǒng)設(shè)計(jì)問(wèn)題，可以用于延長(zhǎng)電池使用壽命或降低用電成本.

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

但是以上這些算法大多集中于各種開(kāi)銷(xiāo)可以忽視的理想DVFS處理器，沒(méi)有考慮實(shí)際DVFS處理器具有的頻率更改開(kāi)銷(xiāo)和狀態(tài)切換開(kāi)銷(xiāo)等物理限制.對(duì)于許多硬實(shí)時(shí)應(yīng)用來(lái)說(shuō)，是否考慮開(kāi)銷(xiāo)、考慮哪些開(kāi)銷(xiāo)對(duì)節(jié)能實(shí)時(shí)調(diào)度可能產(chǎn)生較大影響，忽視這些細(xì)節(jié)可能會(huì)得到次最優(yōu)甚至是無(wú)效的結(jié)果.例如如果狀態(tài)切換的能耗開(kāi)銷(xiāo)大于能耗節(jié)余，那么顯然把處理器轉(zhuǎn)入睡眠狀態(tài)很可能不會(huì)節(jié)能[9].

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

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

本文的主要貢獻(xiàn)如下：

1) 針對(duì)常見(jiàn)的周期任務(wù)模型，將TL面流調(diào)度思想與考慮切換開(kāi)銷(xiāo)的最優(yōu)節(jié)能策略有機(jī)結(jié)合起來(lái)，提出一種開(kāi)銷(xiāo)敏感的在線(xiàn)多處理器節(jié)能實(shí)時(shí)調(diào)度算法PLUFS，在滿(mǎn)足硬實(shí)時(shí)約束的條件下獲得了合理的能量節(jié)余.

2) 經(jīng)過(guò)系統(tǒng)的理論分析以及大量的模擬實(shí)驗(yàn)，既給出了所提PLUFS算法的最優(yōu)可調(diào)度性證明，又驗(yàn)證了PLUFS的節(jié)能效果整體優(yōu)于現(xiàn)有算法，接近于理論最優(yōu)值.

1系統(tǒng)模型與問(wèn)題定義

1.1處理器模型

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

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

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

1.2任務(wù)模型

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

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

1.3問(wèn)題定義

考慮一個(gè)獨(dú)立周期任務(wù)集T在m個(gè)同構(gòu)多處理器上節(jié)能調(diào)度執(zhí)行.每個(gè)處理器具有相同的功耗函數(shù)P(s)=α×s3+β，α,β≥0.每個(gè)處理器的執(zhí)行速度均在smin和smax之間.每個(gè)周期任務(wù)具有最壞情況執(zhí)行時(shí)間或執(zhí)行時(shí)鐘數(shù)和周期，且相對(duì)截止期等于周期.處理器從睡眠狀態(tài)轉(zhuǎn)入活躍狀態(tài)的切換能耗開(kāi)銷(xiāo)為Esw，同時(shí)時(shí)間開(kāi)銷(xiāo)為tsw≤EswP(smin).本文目標(biāo)在于考慮處理器切換開(kāi)銷(xiāo)條件下保證周期任務(wù)集的最優(yōu)可調(diào)度性的同時(shí)盡可能地降低系統(tǒng)能耗.

2PLUFS算法

2.1基本思想

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

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

PLUFS算法采用最大任務(wù)利用率優(yōu)先策略[16]，在考慮處理器實(shí)際狀態(tài)切換開(kāi)銷(xiāo)情況下，在每個(gè)TL面的初始時(shí)刻計(jì)算最壞情況下周期任務(wù)集的最優(yōu)可用處理器個(gè)數(shù)和任務(wù)的最優(yōu)執(zhí)行速度，從而確定所有任務(wù)在每個(gè)TL面內(nèi)的節(jié)能實(shí)時(shí)調(diào)度序列.在每個(gè)TL面邊界上，PLUFS算法將初始化TL面；在每個(gè)TL面內(nèi)，PLUFS算法處理所有的任務(wù)結(jié)束執(zhí)行事件.TL面初始化程序會(huì)根據(jù)當(dāng)前TL面的時(shí)間長(zhǎng)度，為新的TL面重新計(jì)算所有的參數(shù)，確定任務(wù)的調(diào)度過(guò)程和處理器的執(zhí)行速度.任務(wù)結(jié)束執(zhí)行事件處理程序用于維護(hù)TL面內(nèi)任務(wù)調(diào)度過(guò)程的正確性和處理器狀態(tài)切換.一旦初始化或任務(wù)結(jié)束執(zhí)行事件處理程序被完成，PLUFS算法將指導(dǎo)每個(gè)處理器按照分配的頻率來(lái)執(zhí)行被指派的任務(wù).

2.2主程序描述

PLUFS算法由3個(gè)程序構(gòu)成，主程序描述如算法1所示.PLUFS首先初始化參數(shù)，令當(dāng)前時(shí)刻tc和當(dāng)前TL面的結(jié)束時(shí)刻tf均為0(見(jiàn)算法1中行①)，然后在每個(gè)TL面初始時(shí)刻，PLUFS將調(diào)用TL面初始化程序(見(jiàn)行③～⑤)，計(jì)算每個(gè)TL面內(nèi)周期任務(wù)集在考慮切換開(kāi)銷(xiāo)情況下最優(yōu)的可用處理器個(gè)數(shù)和每個(gè)任務(wù)的執(zhí)行速度，在線(xiàn)調(diào)節(jié)所有任務(wù)的調(diào)度序列，實(shí)現(xiàn)TL面中節(jié)能實(shí)時(shí)調(diào)度.在每個(gè)TL面內(nèi)任意時(shí)刻，一旦某個(gè)處理器上發(fā)生任務(wù)結(jié)束執(zhí)行事件，PLUFS將調(diào)用任務(wù)結(jié)束執(zhí)行事件處理程序(見(jiàn)行⑥～⑧)，確保TL面內(nèi)任務(wù)調(diào)度過(guò)程和處理器狀態(tài)切換的正確性.一旦初始化或事件被完成，PLUFS會(huì)循環(huán)等待直到下一個(gè)初始化或事件發(fā)生(見(jiàn)行②～⑧).

算法1. PLUFS.

①tc←0,tf←0;

② while TRUE do

③ iftc=tfthen

④PLUFS_TL_Initialize();

⑤ endif

⑥ if 處理器cpuk上任務(wù)τi在當(dāng)前時(shí)刻tc結(jié)束執(zhí)行 then

⑦Upon_Task_End_Execution(τi,tc,k);

⑧ endif

本文采用與文獻(xiàn)[8]相同的方法來(lái)劃分TL面，每個(gè)任務(wù)實(shí)例的絕對(duì)截止期就是一個(gè)TL面的結(jié)束時(shí)刻.顯然，對(duì)于任意TL面σ和任一任務(wù)τi，τi中最多有一個(gè)任務(wù)實(shí)例與TL面σ重疊.因?yàn)樗械膶?shí)時(shí)調(diào)度策略都是基于一個(gè)TL面而產(chǎn)生的，所以只有與當(dāng)前TL面重疊的任務(wù)實(shí)例才會(huì)被調(diào)度.

2.3TL面初始化

算法2.PLUFS_TL_Initialize().

① for 所有在當(dāng)前時(shí)刻tc到達(dá)的任務(wù)τido

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

③HD.insert(tc+pi);

④ endif

⑤ endfor

⑥tf←HD.extract_min();

⑦D←tf-tc;

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

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

andi←i+1;

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

算法2的具體思想如下：

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

3) 當(dāng)ui

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

定理1. 在每個(gè)TL面初始時(shí)刻t0，如果PLUFS算法通過(guò)算法2來(lái)確定周期任務(wù)集T在TL面[t0,tf]內(nèi)的任務(wù)調(diào)度序列，則該任務(wù)調(diào)度序列可以保證T中所有任務(wù)在當(dāng)前TL面的結(jié)束時(shí)刻tf之前完成其局部剩余執(zhí)行時(shí)間.

證畢.

2.4任務(wù)結(jié)束執(zhí)行事件

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

① if 在處理器cpuk上沒(méi)有任務(wù)等待執(zhí)行 then

② iftf-tc>tθthen

③ 將處理器cpuk轉(zhuǎn)入睡眠狀態(tài);

④ else

⑤ iftf>tcthen

⑥ 將處理器cpuk轉(zhuǎn)入空閑狀態(tài);

⑦ endif

⑧ endif

⑨ else

⑩ 處理器cpuk繼續(xù)以τi.speed×smax為速度值，按照TL面初始化分配的時(shí)間間隔來(lái)調(diào)度執(zhí)行后續(xù)任務(wù);

定理2. 如果PLUFS算法通過(guò)算法3來(lái)處理每個(gè)TL面內(nèi)任務(wù)結(jié)束執(zhí)行事件，那么對(duì)該事件的處理不會(huì)影響到TL面初始時(shí)刻所確定的任務(wù)調(diào)度序列.

證明. 由算法3易知，當(dāng)周期任務(wù)τi在某個(gè)處理器cpuk上結(jié)束執(zhí)行時(shí)，如果處理器cpuk上沒(méi)有任務(wù)等待執(zhí)行，那么算法3只是根據(jù)此時(shí)所產(chǎn)生的靜態(tài)松弛時(shí)間大小判斷是否將該處理器轉(zhuǎn)入睡眠狀態(tài)或者空閑狀態(tài)，并沒(méi)有涉及到對(duì)其他處理器上任務(wù)的處理.而如果處理器cpuk上任務(wù)隊(duì)列不為空，還有后續(xù)任務(wù)等待執(zhí)行，那么算法3不會(huì)改變算法2為后續(xù)任務(wù)分配的開(kāi)始執(zhí)行時(shí)間與結(jié)束執(zhí)行時(shí)間，后續(xù)任務(wù)在處理器cpuk上的執(zhí)行序列和執(zhí)行速度沒(méi)有變化.得證.

證畢.

3算法分析

3.1可調(diào)度性分析

由于不考慮周期任務(wù)集為不可調(diào)度的情況，如不做特殊說(shuō)明，本文均假設(shè)周期任務(wù)集T滿(mǎn)足U≤m，且?τi∈T，ui≤1.

定理3. 如果周期任務(wù)集T使用PLUFS算法調(diào)度執(zhí)行，則T中所有任務(wù)在每個(gè)TL面內(nèi)是局部可調(diào)度的.

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

證畢.

定理4. PLUFS算法可以保證周期任務(wù)集T的最優(yōu)可調(diào)度性.

證明. 因?yàn)樗械腡L面是連續(xù)的，且兩兩獨(dú)立，沒(méi)有重疊區(qū)域，前一個(gè)TL面的結(jié)束時(shí)刻是后一個(gè)TL面的開(kāi)始時(shí)刻，所以可以采用歸納法證明.因?yàn)橹芷谌蝿?wù)集T滿(mǎn)足U≤m且?τi∈T，ui≤1，所以根據(jù)PLUFS算法和定理3可知任務(wù)集T在第1個(gè)TL面內(nèi)是可調(diào)度的.又因?yàn)橛啥ɡ?可知任務(wù)集T在第2個(gè)TL面內(nèi)也是可調(diào)度的，根據(jù)歸納假設(shè)可知PLUFS算法可以保證任意連續(xù)多個(gè)TL面的局部可調(diào)度性，從而可得所有任務(wù)均滿(mǎn)足其截止期.命題得證.

證畢.

3.2復(fù)雜度分析

設(shè)任務(wù)集T中任務(wù)總數(shù)為n，處理器數(shù)為m，每個(gè)任務(wù)狀態(tài)數(shù)量為w，每個(gè)處理器狀態(tài)數(shù)量為v.

1) 時(shí)間復(fù)雜度.算法3中行②～⑧的切換處理器狀態(tài)以及行⑩的調(diào)度后續(xù)任務(wù)繼續(xù)執(zhí)行，每步的時(shí)間復(fù)雜度均為常量，因此算法3的時(shí)間復(fù)雜度為O(1).

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

2) 空間復(fù)雜度.如果采用順序表存儲(chǔ)，任務(wù)集T所占用的空間為O(n×w)，處理器狀態(tài)所占用的空間為O(m×v).因?yàn)镠D堆中只存放一個(gè)關(guān)鍵字即任務(wù)的絕對(duì)截止期，所以HD堆所占用的空間為O(n).

4實(shí)驗(yàn)

本文在Linux 2.6環(huán)境下采用C語(yǔ)言編寫(xiě)了一個(gè)離散事件模擬器，針對(duì)具有獨(dú)立DVFS和DPM的多處理器系統(tǒng)，實(shí)現(xiàn)了多種周期任務(wù)節(jié)能實(shí)時(shí)調(diào)度算法，包括非節(jié)能的P-LRE-TL算法[17]、Independent RT-SVFS算法[6]、P-RSLTF算法[9]、PLUFS算法以及Lower-Bound算法[9].其中，P-LRE-TL算法是對(duì)LRE-TL算法用于周期任務(wù)模型的簡(jiǎn)稱(chēng)，選用它的原因在于其計(jì)算復(fù)雜度遠(yuǎn)小于LLREF算法[8]；Lower-Bound算法是忽視處理器開(kāi)銷(xiāo)條件下的理論最優(yōu)算法，而其他算法可看作真實(shí)算法.Lower-Bound算法允許將所有任務(wù)以關(guān)鍵速度執(zhí)行，它的能耗可以作為考慮開(kāi)銷(xiāo)條件下實(shí)際最優(yōu)能耗的下界[9].

本文以P-LRE-TL算法的能耗作為標(biāo)準(zhǔn)進(jìn)行歸一化，比較算法的歸一化能耗(normalized energy consumption, NEC)，然后比較可調(diào)度性(feasibility performance, FP)，最后對(duì)可調(diào)度性與歸一化能耗之比(簡(jiǎn)記FPNEC)這個(gè)綜合指標(biāo)進(jìn)行比較；此外，還比較算法在不同切換能耗開(kāi)銷(xiāo)情況下的歸一化能耗與不同最小可用速度情況下的歸一化能耗.

4.1參數(shù)產(chǎn)生

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

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

4.2實(shí)驗(yàn)結(jié)果

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

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

一方面，在系統(tǒng)利用率小于0.3的低負(fù)載情況下，PLUFS算法與P-RSLTF算法的能耗節(jié)余比較接近，兩者都比Independent RT-SVFS算法具有更多的節(jié)能.這是因?yàn)镮ndependent RT-SVFS算法靜態(tài)地將任務(wù)集中所有任務(wù)分配到所有的處理器上執(zhí)行[6]，離線(xiàn)確定每個(gè)處理器的狀態(tài)切換情況，運(yùn)行時(shí)不再改變節(jié)能策略，而低負(fù)載情況很可能會(huì)產(chǎn)生頻繁的狀態(tài)切換，導(dǎo)致切換開(kāi)銷(xiāo)大于能耗節(jié)余，說(shuō)明它不能較好適應(yīng)因系統(tǒng)利用率降低而產(chǎn)生的動(dòng)態(tài)負(fù)載變化.而PLUFS算法與P-RSLTF算法均考慮到狀態(tài)切換開(kāi)銷(xiāo)問(wèn)題，允許任務(wù)運(yùn)行在比關(guān)鍵速度更低的速度來(lái)減少狀態(tài)切換次數(shù)，可以更好地適應(yīng)動(dòng)態(tài)負(fù)載變化，從而實(shí)現(xiàn)更多的節(jié)能.

另一方面，在系統(tǒng)利用率大于0.3的高負(fù)載情況下，P-RSLTF算法與Independent RT-SVFS算法的能耗節(jié)余比較接近，隨著總負(fù)載的增加，兩者的能耗節(jié)余不斷減少.雖然PLUFS算法獲得的能耗節(jié)余也不斷減少，但是更接近于Lower-Bound算法的能耗節(jié)余.這是因?yàn)镻-RSLTF算法基于劃分方法來(lái)調(diào)度周期任務(wù)集而只能實(shí)現(xiàn)降低部分任務(wù)的執(zhí)行速度，Independent RT-SVFS算法屬于靜態(tài)節(jié)能調(diào)度方法，隨著總負(fù)載的增加，所有的處理器都會(huì)運(yùn)行以滿(mǎn)足任務(wù)集可調(diào)度性的要求，此時(shí)這2種算法無(wú)法實(shí)現(xiàn)任務(wù)集在更多處理器上減少狀態(tài)切換次數(shù)，不適應(yīng)高負(fù)載情況下動(dòng)態(tài)負(fù)載變化.但是PLUFS算法可以在保證周期任務(wù)集最優(yōu)可調(diào)度性的同時(shí)，根據(jù)處理器開(kāi)銷(xiāo)模型和每個(gè)TL面的時(shí)間長(zhǎng)度確定在每個(gè)TL面中所有任務(wù)的節(jié)能實(shí)時(shí)調(diào)度序列，能夠利用完全動(dòng)態(tài)的任務(wù)實(shí)例級(jí)遷移來(lái)減少狀態(tài)切換次數(shù)，確保在高負(fù)載情況下也能取得較好的節(jié)能效果.

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

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

Fig. 2　Feasibility performance changing with workloads.圖2　隨負(fù)載變化的可調(diào)度性分析

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

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

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

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

Fig. 4　Normalized energy consumption under different energy switching overheads.圖4　不同切換能耗開(kāi)銷(xiāo)情況下歸一化能耗

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

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

圖5給出了在考慮處理器不同最小可用速度情況下，P-LRE-TL，Independent RT-SVFS，P-RSLTF，PLUFS以及Lower-Bound算法在第3種參數(shù)設(shè)置下周期任務(wù)集的歸一化能耗.從圖5(a)中可知，當(dāng)處理器個(gè)數(shù)m=8、任務(wù)集中任務(wù)個(gè)數(shù)n=20、切換能耗開(kāi)銷(xiāo)為1.0 mJ和總負(fù)載為0.8時(shí)，不論處理器的最小可用速度如何變化，PLUFS算法的節(jié)能效果除了差于理論最優(yōu)Lower-Bound算法以外，優(yōu)于其他真實(shí)算法.這是因?yàn)樘幚砥鞯淖钚】捎盟俣戎饕糜谟?jì)算處理器空閑功耗和進(jìn)入睡眠狀態(tài)的break-even時(shí)間，隨著最小可用速度的減小，處理器空閑功耗會(huì)減少，而break-even時(shí)間會(huì)增大.Independent RT-SVFS算法屬于靜態(tài)節(jié)能調(diào)度方法，運(yùn)行時(shí)處理器的電壓和頻率不能改變，所以隨著最小可用速度的減小，空閑功耗會(huì)減少，導(dǎo)致能耗節(jié)余會(huì)有所增加.Lower-Bound算法不僅沒(méi)有考慮處理器切換開(kāi)銷(xiāo)情況，還不允許任務(wù)以低于關(guān)鍵速度來(lái)執(zhí)行，而實(shí)驗(yàn)中最小可用速度的最大取值仍小于關(guān)鍵速度，所以該算法不受最小可用速度變化的影響.P-RSLTF算法和PLUFS算法都是基于任務(wù)利用率來(lái)計(jì)算所有任務(wù)的執(zhí)行速度，在任務(wù)調(diào)度序列中都存在大量小塊的空閑時(shí)間，空閑功耗的減少和break-even時(shí)間的增大會(huì)使得處理器傾向于空閑狀態(tài)，但這樣又會(huì)增加可用處理器個(gè)數(shù)，同樣會(huì)增加能耗，因此最小可用速度的變化對(duì)2種算法節(jié)能效果的影響有限.

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

5結(jié)束語(yǔ)

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

參考文獻(xiàn)

[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)(張冬松, 吳飛, 陳芳園, 等. 開(kāi)銷(xiāo)敏感的多處理器最優(yōu)節(jié)能實(shí)時(shí)調(diào)度算法[J]. 計(jì)算機(jī)學(xué)報(bào), 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

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(61402527,61272097)

中圖法分類(lèi)號(hào)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).