實時系統中兩類高能效調度問題

湖南師范大學數學與計算機科學學院 錢光明

?

實時系統中兩類高能效調度問題

湖南師范大學數學與計算機科學學院 錢光明

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

【關鍵詞】單次作業集合；高能效調度；最優調度方案；競爭比

1　引言

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

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

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

2　單次作業集合的高能效調度

2.1未考慮睡眠

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

圖1　單次作業集合示例：作業J1、J2和J3按EDF策略調度

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

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

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

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

2.2考慮睡眠

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

設睡眠時長L剛好補償Etran，并且系統工作在某一固定頻率，那么，是否將處理器空閑狀態轉變為睡眠狀態，主要看睡眠時間是否長于L。如一個簡單直接的算法ALG-D就是：空閑時先不睡眠，只有當空閑時間超過L時才轉入睡眠狀態，此算法的競爭比可達2［2］。還有一些算法可小于2。

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

如果頻率固定，而作業的安排使得處理器出現零零散散的空閑時間，那么，能不能將這些空閑時間盡量集中，使單次睡眠的長度增加，有利于實現合算的睡眠呢？答案是肯定的。關于該問題的最優調度方案，文獻［9］指出如果它是多項式時間復雜度，會有較寬廣的應用。在適當的建模假設下，文獻［10］證明該最優調度方案的時間復雜度是O（n5）。

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

圖2　周期任務集運行時降頻示例

3　周期任務集合的高能效調度

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

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

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

4　結束語

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

參考文獻

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

作者簡介：

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