基于混合任務(wù)的動(dòng)態(tài)電壓調節算法驗證及仿真

　　嵌入式實(shí)時(shí)操作系統在目前的嵌入式應用中用得越來(lái)越廣泛，尤其在功能復雜、系統龐大的應用中顯得愈來(lái)愈重要。人們要求實(shí)時(shí)嵌入式產(chǎn)品能夠提供更為強勁的計算能力，以滿(mǎn)足無(wú)線(xiàn)通信、多媒體應用的要求，然而高性能的代價(jià)就是高能耗，因此延長(cháng)實(shí)時(shí)嵌入式系統電池使用時(shí)間已經(jīng)成為實(shí)時(shí)嵌入式系統設計普遍關(guān)注的問(wèn)題。在實(shí)時(shí)嵌入式系統中，核心處理器的能耗占據整個(gè)能耗的相當大一部分。動(dòng)態(tài)電壓調節被看作是降低處理器能耗的關(guān)鍵技術(shù)，其原理是在系統運行時(shí)態(tài)通過(guò)動(dòng)態(tài)改變處理器的電壓和頻率，降低系統中的無(wú)用能耗，從而提高能量的有效利用率[1]。

　　當前，基于任務(wù)的動(dòng)態(tài)電壓調節算法主要集中在對周期性任務(wù)集合的研究，其中只有很少一部分是對周期性任務(wù)和非周期性任務(wù)的混合任務(wù)集進(jìn)行研究。另外，基于工作負荷的DVS算法盡管能從系統級上解決無(wú)用能耗問(wèn)題，但卻很少考慮到系統的實(shí)時(shí)性。

　　1 動(dòng)態(tài)電壓調節算法理論背景

　　1.1 動(dòng)態(tài)電壓調節算法的必要性

　　由于CMOS電路的能量消耗E與電路電壓V的平方成正比，因此降低電壓是降低線(xiàn)路能耗的最有效的方法之一。DVS算法的基本原理： 系統在運行時(shí)間內根據性能的不同要求而相應地執行降低或者提高電壓和工作頻率的操作，從而降低能耗。

　　傳統的電源管理技術(shù)只是在空閑時(shí)間內降低功耗十分有效，而在運行時(shí)間內卻無(wú)能為力。目前，一些操作系統內核對動(dòng)態(tài)電壓管理(DPM)的支持還是局限于不能調整核心電壓，主要是通過(guò)調整CPU頻率和支持開(kāi)關(guān)外圍設備的供電來(lái)實(shí)現。但是近年來(lái)，隨著(zhù)半導體技術(shù)的發(fā)展，在運行時(shí)態(tài)動(dòng)態(tài)改變處理器的工作電壓和/或時(shí)鐘頻率已經(jīng)變成了現實(shí)。很多商用嵌入式處理支持動(dòng)態(tài)電壓調節DVS這一技術(shù)，比如TI公司的OMAP系列處理器、Intel公司的StrongARM處理器、Transmeta公司的Crusoe處理器，還有IBM公司的PowerPC 405LP處理器等。

　　1.2 實(shí)時(shí)操作系統與任務(wù)調度

　　在實(shí)時(shí)系統軟件中，最基本的軟件是實(shí)時(shí)操作系統。它是實(shí)時(shí)系統軟件的基礎，所有的實(shí)時(shí)應用軟件都是在實(shí)時(shí)操作系統的支撐下運行的。與通用操作系統相比，實(shí)時(shí)操作系統有其特有的一些重要特征，包括規模較小、中斷時(shí)間很短、進(jìn)程切換很快、中斷被屏蔽時(shí)間很短、能管理ms級或μs級的多個(gè)定時(shí)器。因此它能適應各種實(shí)時(shí)應用的需求，從快速的實(shí)時(shí)響應到慢速的實(shí)時(shí)響應，都能應付自如。

　　實(shí)時(shí)系統的實(shí)時(shí)性通過(guò)周期(period)和時(shí)限(deadline)來(lái)體現。周期是均勻重復性任務(wù)每?jì)纱握{用開(kāi)始的時(shí)間間隔。任務(wù)必須在某個(gè)時(shí)刻前完成操作，啟動(dòng)時(shí)刻與該時(shí)刻的時(shí)間間隔被稱(chēng)為“時(shí)限”。均勻重復性任務(wù)又稱(chēng)為“周期性任務(wù)(periodic task)”。周期性任務(wù)在一個(gè)周期內的一次調用可以看作是一個(gè)作業(yè)。通常，周期性任務(wù)的作業(yè)周期和時(shí)限是相等的。

　　實(shí)時(shí)操作系統的核心就是任務(wù)調度。它提供給系統一個(gè)決策機制，決定在某個(gè)瞬間時(shí)刻下，系統作業(yè)池中哪一個(gè)作業(yè)占用處理器?；诰€(xiàn)程的任務(wù)間DVS算法就是以實(shí)時(shí)系統的任務(wù)調度為主要理論基礎。

　　1.3 服務(wù)器

　　然而，現實(shí)的情況是實(shí)時(shí)系統中并非所有的任務(wù)都是非周期性的。對于兩種任務(wù)的混合調度情況，在基于優(yōu)先級的方案中，簡(jiǎn)單地使非周期性任務(wù)的優(yōu)先級低于周期性的任務(wù)[2]。這樣，非周期性任務(wù)作為后臺活動(dòng)運行;而在搶占式系統中，它就不能掠奪周期性任務(wù)的資源。盡管這是一個(gè)安全的方案，但是考慮到非周期性任務(wù)的時(shí)限，如果讓它們只作為后臺運行，往往會(huì )錯過(guò)它們的時(shí)限。為了改善非周期性任務(wù)的這種狀況，可利用服務(wù)器(server)來(lái)解決。在RM策略下，最廣泛研究的是可延期服務(wù)器(Deferred Server，DS)和偶發(fā)服務(wù)器[3](Sporadic Server，SS)。

　　在DS中，引進(jìn)一個(gè)新的最高優(yōu)先級任務(wù)，這個(gè)任務(wù)也就是服務(wù)器。它有一個(gè)周期Ts和一個(gè)容量(Budget)Es。在運行時(shí)態(tài)，當一個(gè)非周期性任務(wù)達到時(shí)，如果服務(wù)器有可用容量，就立即開(kāi)始執行，直到任務(wù)完成或服務(wù)器容量耗盡;如果服務(wù)器沒(méi)有可用容量，那么非周期進(jìn)程會(huì )被掛起(或轉換為后臺優(yōu)先級)。在DS模型中，服務(wù)器容量每Ts個(gè)單位被補充一次。

　　SS的操作不同于DS在于它的容量補充策略。在SS中，如果一個(gè)任務(wù)在t時(shí)刻到達，并要求使用容量e,那么服務(wù)器在時(shí)間t后的Ts個(gè)時(shí)間單位補充容量e。通常，SS能提供比DS更高的容量，但同時(shí)也增加了實(shí)現的開(kāi)銷(xiāo)。

　　2 基于混合任務(wù)集的減慢因子DVS算法

　　在實(shí)時(shí)系統中可調度性是保證系統可靠的重要參數，對任務(wù)集進(jìn)行可調度性分析是減慢因子算法的必要部分。在進(jìn)行可調度性分析的過(guò)程中，本文把非周期性任務(wù)的服務(wù)器看作固定優(yōu)先級的周期性任務(wù)，將服務(wù)器的周期Ts作為任務(wù)周期和周期性任務(wù)一起分析。假設在系統S中存在著(zhù)n個(gè)周期性任務(wù)t1、t2、t3、 K、tn和個(gè)非周期性任務(wù)a1、a2、a3、K、an，所有的非周期性任務(wù)受可延期服務(wù)器DS的調度。如果系統S運行于固定速度處理器上，混合任務(wù)集在單調速率可搶占的調度方案下調度，那么可以用周期性任務(wù)集的單調速率可搶占調度方案的響應時(shí)間分析方法對這個(gè)混合任務(wù)集進(jìn)行可調度分析。

　　減慢因子即任務(wù)的運行頻率和最高頻率之間的比值。在系統運行期間，即使所有任務(wù)按照最壞情況執行時(shí)間(WCET)運行，大多數情況下處理器的利用率也遠低于100%，任務(wù)集在某個(gè)任務(wù)時(shí)限前，系統處于空閑調度循環(huán)中。因此，對處理器的電壓和工作頻率進(jìn)行減慢因子計算，使空閑時(shí)間間隔大大縮短甚至消失，這樣就達到了降低能耗的目的。

　　在下面的減慢DVS算法中，當任何新的周期性任務(wù)或者服務(wù)器進(jìn)入系統并且在調度器中登記后，將會(huì )執行 Compute_Slowdown_Factors過(guò)程，進(jìn)行整個(gè)系統的可調度性分析，并且為每一個(gè)任務(wù)計算出最低的工作頻率，從而保證所有任務(wù)在其工作頻率下運行仍舊是可調度的，不會(huì )影響整個(gè)系統的實(shí)時(shí)性需求。

　　下面給出計算靜態(tài)減慢因子αs算法的偽代碼(其中0<αs≤1)：

　　//Algorithm Compute_Slowdown_Factors

　　Inputs:

　　S//將要進(jìn)行減慢因子計算的任務(wù)集，包括周期性任務(wù)和非周期性任務(wù)的服務(wù)器

　　Outputs:

　　Slowdown_Factors[]//任務(wù)集的靜態(tài)減慢因子

　　{

　　Sm//計算出減慢因子后，將要超過(guò)時(shí)限的任務(wù)集，初始化為空集

　　Current_Scaling _Factor=1;

　　For S中的每一個(gè)任務(wù)i

　　Slowdown_Factor[i]=1;

　　While (S不為空集){

　　F=Scale_WCET(S，Slowdown_Factor[]);//計算減慢因子F

　　重新設置Sm;

　　Current_Scaling_Facotr *=F;

　　For S中的每一個(gè)任務(wù)i {

　　If任務(wù)i!=服務(wù)器

　　Slowdown_Factor[i]=F;

　　}

　　重新設置集合S，讓集合S中所有任務(wù)的優(yōu)先級小于Sm中最低優(yōu)先級任務(wù)的優(yōu)先級;

　　}

　　}

　　上面的程序通過(guò)Scale_WCET過(guò)程計算一個(gè)減慢因子，使得給定任務(wù)集中存在的一個(gè)或者多個(gè)任務(wù)的最差響應時(shí)間剛好等于它們的時(shí)限(此時(shí)該任務(wù)集剛好可調度)，這樣的任務(wù)稱(chēng)為“臨界任務(wù)”。Compute_Slowdown_Factors過(guò)程首先調用Scale_WCET過(guò)程計算初始任務(wù)集的同一減慢因子F;然后讓優(yōu)先級低于臨界任務(wù)的任務(wù)集繼續調用Scale_WCET過(guò)程計算出新的減慢因子。這是因為如果繼續讓作用于優(yōu)先級高于臨界任務(wù)的減慢因子F變小，則必然會(huì )導致至少有一個(gè)臨界任務(wù)超過(guò)時(shí)限，破壞了系統的實(shí)時(shí)性;而讓作用優(yōu)先級低于臨界任務(wù)的減慢因子F變小，則不會(huì )影響整個(gè)任務(wù)集的可調度性。這個(gè)過(guò)程將會(huì )反復執行，直到初始任務(wù)集中的最低優(yōu)先級任務(wù)變成臨界任務(wù)?？傊?，這個(gè)迭代過(guò)程為每一個(gè)任務(wù)計算出減慢因子，同時(shí)保證整個(gè)任務(wù)集是可以調度的。需要說(shuō)明的是，對于服務(wù)器將不會(huì )應用靜態(tài)減慢因子，因為如果增加了服務(wù)器的運行時(shí)間，則必然會(huì )造成受服務(wù)器調度的非周期性任務(wù)的平均響應時(shí)間的增加。

　　3 算法驗證和仿真

　　本算法通過(guò)T1 OMAP1612的TCSCDMA無(wú)線(xiàn)終端平臺來(lái)驗證，對實(shí)時(shí)嵌入式操作系統Nucleus微內核進(jìn)行功能上的擴充，主要是實(shí)現了可延期服務(wù)器(DS)和偶發(fā)服務(wù)器(SS)來(lái)對非周期性任務(wù)進(jìn)行調度。同時(shí)，又整合了基于本算法的DVS模塊和CPU功率檢測模塊。

　　本實(shí)驗通過(guò)3種情況(沒(méi)有采用DVS算法,以及基于混合任務(wù)集的減慢因子DVS算法在DS和SS中的分別應用)分別在服務(wù)器利用率為25%、35%、45%的情況下進(jìn)行了時(shí)間為60 s的實(shí)驗，得出各情況下能耗在不同服務(wù)器利用率下的關(guān)系，如圖1所示。

　　圖1 各種算法的能耗對比

　　圖1結果表明，采用基于混合任務(wù)集的減慢因子DVS算法與沒(méi)有采用DVS算法相比，能耗降低了大概19.3%~32%;同時(shí)也看到，服務(wù)器利用率越高，能耗越接近于沒(méi)有采用DVS算法所產(chǎn)生的能耗。這是因為為了保證非周期性任務(wù)有很短的響應時(shí)間，基于混合任務(wù)集的減慢因子DVS算法在服務(wù)器上運行時(shí)，總是以最高頻率運行，同時(shí)高服務(wù)器利用率意味著(zhù)服務(wù)器會(huì )占用很大一部分CPU周期。因此，在這樣的環(huán)境下，CPU很大的一部分時(shí)間都運行在最高頻率上，導致服務(wù)器利用率越高， 越接近沒(méi)有采用DVS算法的情況。

　　4 結論

　　本文提出的針對靜態(tài)空閑間隔的靜態(tài)減慢因子算法屬于脫機(offline)的DVS算法。該算法同時(shí)把占系統很大部分的非周期性任務(wù)一起進(jìn)行分析，把非周期性任務(wù)的服務(wù)器當作周期性任務(wù)進(jìn)行動(dòng)態(tài)電壓調節，從而解決了非周期性任務(wù)的功耗問(wèn)題，具有很大的實(shí)際意義。在保證性能的同時(shí)，降低了系統中的無(wú)用能耗，提高了能量的有效利用率。隨著(zhù)研究的深入，還將深入到對聯(lián)機(online)情況進(jìn)行動(dòng)態(tài)電壓調節。

　　參考文獻

　　[1] Pering T, Burd T, Brodersen R. Dynamic voltage scaling and the design of a lowpower microprocessor system[C]. Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, 2001:251259.

　　[2] Hakan Aydin, Qi Yang. EnergyResponsiveness Tradeoffs for RealTime Systems with Mixed Workload[C].IEEE RealTime and Embedde Technology and Applications Symposium，7483，2004.

　　[3] Dongkun Shin, Jihong Kim. Dynamic voltage scaling of periodic and aperiodic tasks in prioritydriven systems[C]. Proceedings of the 2004 Conference on Asia South Pacific Design Automation: Electronic Design and Solution Fair 2004, 2004:653658.