湖南師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院 錢光明

?

實時系統(tǒng)中兩類高能效調(diào)度問題

湖南師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院 錢光明

【摘要】實時和嵌入式系統(tǒng)中，節(jié)能和省電備受關(guān)注。這一問題牽涉許多方面，其中系統(tǒng)的調(diào)度方案至關(guān)重要。文章將高能效調(diào)度作了典型分類：單次作業(yè)集合的高能效調(diào)度和周期任務(wù)集合的高能效調(diào)度，總結(jié)和歸納了多年來國際學(xué)者的代表性研究，探討了今后的研究趨勢。

【關(guān)鍵詞】單次作業(yè)集合；高能效調(diào)度；最優(yōu)調(diào)度方案；競爭比

1　引言

從環(huán)保、節(jié)能和經(jīng)濟角度來說，省電是一個長久的話題。Google服務(wù)器維護工程師早就聲稱，如果電費繼續(xù)增加，其所占比例將大大超過硬件開銷［1］。這些年，隨著便攜式通信、遠程測量、無線節(jié)點等技術(shù)的大量應(yīng)用，低功耗越來越被更多的普通人所關(guān)注。

一個嵌入式系統(tǒng)，為了實現(xiàn)其省電和低功耗，經(jīng)?？紤]的是在滿足應(yīng)用需求的前提下，其工作頻率和工作電壓要盡量低，空閑時盡量處于低功耗狀態(tài)（如待機狀態(tài)、斷電狀態(tài)等），也就是要做到高能效（Energy-Efficient）［2］。但是，如何在不同的系統(tǒng)和不同的場合做好這兩個“盡量”，吸引了大量學(xué)者進行研究，至今仍存在不少的開問題。

實時應(yīng)用中，主要的應(yīng)用需求就是任務(wù)需要在一定時間內(nèi)完成。既要低功耗，又要滿足時間指標。容易想象，系統(tǒng)的調(diào)度方案和算法，對實現(xiàn)高能效至關(guān)重要。在眾多的研究文獻中，我們梳理出兩大類問題：①單次作業(yè)集合的高能效調(diào)度；②周期任務(wù)集合的高能效調(diào)度。

2　單次作業(yè)集合的高能效調(diào)度

2.1未考慮睡眠

這里單次作業(yè)集合是指：系統(tǒng)中可能有一個或多個任務(wù)（或稱作業(yè)），但每個任務(wù)只執(zhí)行一次。設(shè)系統(tǒng)中的作業(yè)集合為（J1，J2，…，Jn）。，其釋放時間為ri，截止期為di，執(zhí)行量為wi，作業(yè)模型可表示為（ri，wi，di）。因為高能效調(diào)度一般要考慮改變處理器的頻率，所以Ji的實際執(zhí)行量為wi/f，這里f代表處理器的當前工作頻率。有的文獻中干脆將執(zhí)行量表示為處理器周期數(shù)［3］。

圖1　單次作業(yè)集合示例：作業(yè)J1、J2和J3按EDF策略調(diào)度

圖1所示為單次作業(yè)集合的一個示例，調(diào)度策略為EDF（Earliest Deadline First）［4］。圖中三個作業(yè)分別為，涂黑的部分表示相應(yīng)作業(yè)正在得以執(zhí)行，例如在t=5到t=9期間，J1占據(jù)處理器運行。假定每個作業(yè)在其截止期后就不再有執(zhí)行要求，這就是單次作業(yè)的含義。

實際上，圖1中的調(diào)度情況只是針對處理器的一個特定工作頻率f。當f升高時，每個作業(yè)的運行時間將縮短，當f降低時，運行時間將被拉長。

為了低功耗，實現(xiàn)高能效調(diào)度，一個自然的想法就是：在滿足各作業(yè)截止期的前提下，盡量降低工作頻率f，因為大量的文獻都指出CMOS器件的耗能E是隨著f的升高而快速增加。所以，在計算系統(tǒng)的功率P時，有的研究模型?。?］；有的按進行研究［6］；或干脆寫出，系數(shù)β，γ＞0［7］。

在不同的工作時間段，合理分配不同的最低工作頻率，就可能既滿足時間指標又能耗最低。YDS（以作者姓氏首字母命名）算法便符合此要求，它是一個適應(yīng)于圖1所示場合的最優(yōu)調(diào)度方案［2］［5］［6］。這是一個離線（offline）調(diào)度方案，只有多項式時間復(fù)雜度。但是，在線（online）調(diào)度就沒這么幸運，因為任務(wù)的參數(shù)（如執(zhí)行時間wi）有時是難以預(yù)知的。設(shè)計出一個在線調(diào)度方案，往往需要評估它與最優(yōu)調(diào)度方案有多大的差別。例如，如果采用最優(yōu)調(diào)度方案時系統(tǒng)的能量消耗為Eopt，在線調(diào)度方案消耗的能量為，那么，k值可達多少？這就是所謂的競爭比（competitive ratio）［2］。抽象地，與競爭比相關(guān)的問題遠遠不只是在考慮計算機的調(diào)度方案時碰到，物聯(lián)網(wǎng)、交通領(lǐng)域、經(jīng)濟調(diào)控等諸多領(lǐng)域都與之關(guān)聯(lián)，文獻［8］被眾多不同專業(yè)的研究人員所引用。

2.2考慮睡眠

為了節(jié)能，當處理器空閑時，可將其設(shè)置在睡眠狀態(tài)（sleep state），或干脆到停機狀態(tài)（Power-Down）。例如，圖1中，在t=9 到t=12期間，三個作業(yè)都已運行完畢，處理器空閑，自然想到此間停機最好。但是，無論從喚醒（wake-up）到睡眠，還是從睡眠到喚醒，變化過程都是需要消耗能量的，設(shè)其為Etran。如果睡眠時間不夠長，其節(jié)省的能量可能還不夠補償Etran。

設(shè)睡眠時長L剛好補償Etran，并且系統(tǒng)工作在某一固定頻率，那么，是否將處理器空閑狀態(tài)轉(zhuǎn)變?yōu)樗郀顟B(tài)，主要看睡眠時間是否長于L。如一個簡單直接的算法ALG-D就是：空閑時先不睡眠，只有當空閑時間超過L時才轉(zhuǎn)入睡眠狀態(tài)，此算法的競爭比可達2［2］。還有一些算法可小于2。

如果頻率可變，又要考慮睡眠狀態(tài)，可歸為SS-PD（Speed Scaling with Power-Down）問題［9］。SS-PD問題的離線最優(yōu)調(diào)度算法已被證明是NP難度［7］，盡管存在近似算法的研究［6］。

如果頻率固定，而作業(yè)的安排使得處理器出現(xiàn)零零散散的空閑時間，那么，能不能將這些空閑時間盡量集中，使單次睡眠的長度增加，有利于實現(xiàn)合算的睡眠呢？答案是肯定的。關(guān)于該問題的最優(yōu)調(diào)度方案，文獻［9］指出如果它是多項式時間復(fù)雜度，會有較寬廣的應(yīng)用。在適當?shù)慕＜僭O(shè)下，文獻［10］證明該最優(yōu)調(diào)度方案的時間復(fù)雜度是O（n5）。

需要注意的是：實際系統(tǒng)中工作頻率并不是越低越好，因為可能存在一部分與頻率無關(guān)的能量損耗。文獻［6］提出了一個臨界頻率fcrit（critical speed）的概念。系統(tǒng)工作頻率等于fcrit時，能量損耗最低。關(guān)聯(lián)fcrit時，調(diào)度方案將更加復(fù)雜化。在t=4到t=6期間，系統(tǒng)工作頻率從f=1降到f=0.5來運行。

圖2　周期任務(wù)集運行時降頻示例

3　周期任務(wù)集合的高能效調(diào)度

許多實時系統(tǒng)中任務(wù)是周期性的。對于一個周期任務(wù)來說，每一周期可看作一個單次作業(yè)；對系統(tǒng)中的所有周期任務(wù)，可以找出它們周期的最小公倍數(shù)周期TLCM，然后在TLCM內(nèi)應(yīng)用單次作業(yè)集合的分析方法。但無論如何這都使問題更負責(zé)。

圖2所示的方法稱為ccEDF（cycle-conserving EDF），直截了當，但其節(jié)能性能并非最好［11］。文獻［11］中提出了一個look-ahead EDF，從將來的某一截止期往當前時刻反推，其節(jié)能性能強于ccEDF，算法實現(xiàn)雖然不像ccEDF簡單，也不很復(fù)雜，是一個值得推薦的online算法，該文被同行引用早已超過千次。文獻［12］在保存ccEDF簡潔性的同時，提出了一個EccEDF算法，該算法能精確計算未使用的帶寬，以改善節(jié)能。

實際系統(tǒng)中，往往工作頻率并非連續(xù)可變的，只能取一些離散值。因此，當算法選定的頻率fopt不存在時，只好選擇其附近的一個可用頻率，這樣一來，節(jié)能又要打折扣。文獻［3］提出了一個PWM （pulse-width modulation）方案，在最靠近fopt的左邊和右邊各取一個可用頻率fl-opt和fr-opt，fl-opt＜fopt＜fr-opt，通過調(diào)節(jié)系統(tǒng)在fl-opt和fr-opt下的工作時間，達到最小化能量消耗的目的。

4　結(jié)束語

除了以上典型代表外，學(xué)者們還有不少其它研究模型。比如，離線非最優(yōu)調(diào)度方案［6］。又如單次作業(yè)集合的運行時調(diào)度方案［2］［5］。不過，系統(tǒng)運行前，如果所有任務(wù)的所有參數(shù)都是已知的、不變的，自然就想到要考察最低能耗的最優(yōu)調(diào)度方案，上面提到既變頻又考慮睡眠時這一問題為NP難度，因此，今后應(yīng)該會出現(xiàn)一些性能較好的非最優(yōu)調(diào)度方案。而系統(tǒng)運行中，方案應(yīng)該盡量簡單而快速，所以，在現(xiàn)有基礎(chǔ)上，有理由期盼找到更簡單的、能耗更低的、或是適應(yīng)于某些特定場合的運行時調(diào)度方案。

參考文獻

［1］Barroso L A.The price of performance［J］.Queue，2005，3（7）：48-53. ［2］Albers S.Energy-efficient algorithms［J］.Communications of the ACM，2010，53（5）：86-96.

［3］Bini E，Buttazzo G，Lipari G.Minimizing CPU energy in realtime systems with discrete speed management［J］.ACM Transactions on Embedded Computing Systems（TECS），2009，8（4）：31.1-31.23.

［4］Liu C L，Layland J W.Scheduling algorithms for multiprogramming in a hard-real-time environment［J］.Journal of the ACM（JACM），1973，20（1）：46-61.

［5］Yao F，Demers A，Shenker S.A scheduling model for reduced CPU energy［C］.//Foundations of Computer Science，1995.Proceedings.，36th Annual Symposium on.IEEE，1995：374-382.

［6］Irani S，Shukla S，Gupta R.Algorithms for power savings［J］.ACM Transactions on Algorithms（TALG），2007，3（4）：41.1-41.23.

［7］Albers S，Antoniadis A.Race to idle：new algorithms for speed scaling with a sleep state［J］.ACM Transactions on Algorithms（TALG），2014，10（2）：9.1-9.31.

［8］Borodin A，El-Yaniv R.Online computation and competitive analysis［M］.cambridge university press，2005.

［9］Irani S，Pruhs K R.Algorithmic problems in power management［J］. ACM Sigact News，2005，36（2）：63-76.

［10］Baptiste P，Chrobak M，Dürr C.Polynomial-time algorithms for minimum energy scheduling［J］.ACM Transactions on Algorithms（TALG），2012，8（3）：26.1-26.29.

［11］Pillai P，Shin K G.Real-time dynamic voltage scaling for lowpower embedded operating systems［C］.//ACM SIGOPS Operating Systems Review.ACM，2001，35（5）：89-102.

［12］Min-Seok L E E，Cheol-Hoon L E E.Enhanced Cycle-Conserving Dynamic Voltage Scaling for Low-Power Real-Time Operating Systems［J］. IEICE TRANSACTIONS on Information and Systems，2014，97（3）：480-487.

作者簡介：

錢光明，男，教授，主要研究方向為嵌入式和實時系統(tǒng)。