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

?

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

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

【摘要】實(shí)時(shí)和嵌入式系統(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)濟(jì)角度來說，省電是一個(gè)長久的話題。Google服務(wù)器維護(hù)工程師早就聲稱，如果電費(fèi)繼續(xù)增加，其所占比例將大大超過硬件開銷［1］。這些年，隨著便攜式通信、遠(yuǎn)程測量、無線節(jié)點(diǎn)等技術(shù)的大量應(yīng)用，低功耗越來越被更多的普通人所關(guān)注。

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

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

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

2.1未考慮睡眠

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

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

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

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

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

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

2.2考慮睡眠

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

設(shè)睡眠時(shí)長L剛好補(bǔ)償Etran，并且系統(tǒng)工作在某一固定頻率，那么，是否將處理器空閑狀態(tài)轉(zhuǎn)變?yōu)樗郀顟B(tài)，主要看睡眠時(shí)間是否長于L。如一個(gè)簡單直接的算法ALG-D就是：空閑時(shí)先不睡眠，只有當(dāng)空閑時(shí)間超過L時(shí)才轉(zhuǎn)入睡眠狀態(tài)，此算法的競爭比可達(dá)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)零零散散的空閑時(shí)間，那么，能不能將這些空閑時(shí)間盡量集中，使單次睡眠的長度增加，有利于實(shí)現(xiàn)合算的睡眠呢？答案是肯定的。關(guān)于該問題的最優(yōu)調(diào)度方案，文獻(xiàn)［9］指出如果它是多項(xiàng)式時(shí)間復(fù)雜度，會有較寬廣的應(yīng)用。在適當(dāng)?shù)慕＜僭O(shè)下，文獻(xiàn)［10］證明該最優(yōu)調(diào)度方案的時(shí)間復(fù)雜度是O（n5）。

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

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

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

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

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

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

4　結(jié)束語

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

參考文獻(xiàn)

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

作者簡介：

錢光明，男，教授，主要研究方向?yàn)榍度胧胶蛯?shí)時(shí)系統(tǒng)。