實時系統(tǒng)中混合任務(wù)集的動態(tài)電壓調(diào)節(jié)算法

摘要 在實時嵌入式系統(tǒng)中，核心處理器的能耗占據(jù)整個能耗的相當(dāng)大一部分。動態(tài)電壓調(diào)節(jié)被看作是降低處理器能耗的關(guān)鍵技術(shù)，介紹實時系統(tǒng)和動態(tài)電壓調(diào)節(jié)的基本概念，并在CMOS器件功耗理論和實時系統(tǒng)下任務(wù)調(diào)度理論的基礎(chǔ)上，提出基于混合任務(wù)集的減慢因子DVS算法。
關(guān)鍵詞 動態(tài)電壓調(diào)節(jié) 實時操作系統(tǒng)低功耗任務(wù)調(diào)度

    嵌入式實時操作系統(tǒng)在日前的嵌入式應(yīng)用中用得越來越廣泛，尤其在功能復(fù)雜、系統(tǒng)龐大的應(yīng)用中顯得愈來愈重要。人們要求實時嵌入式產(chǎn)品能夠提供更為強勁的計算能力，以滿足無線通信、多媒體應(yīng)用的要求，然而高性能的代價就是高能耗，因此延長實時嵌入式系統(tǒng)電池使用時間已經(jīng)成為實時嵌入式系統(tǒng)設(shè)汁普遍關(guān)注的問題。在實時嵌入式系統(tǒng)中，核心處理器的能耗占據(jù)整個能耗的相當(dāng)大一部分。動態(tài)電壓調(diào)節(jié)被看作是降低處理器能耗的關(guān)鍵技術(shù)，其原理是在系統(tǒng)運行時態(tài)通過動態(tài)改變處理器的電壓和頻率，降低系統(tǒng)中的無用能耗，從而提高能量的有效利用率。
    當(dāng)前，基于任務(wù)的動態(tài)電壓調(diào)節(jié)算法主要集中在對周期性任務(wù)集合的研究，其中只有很少一部分是對周期性任務(wù)和非周期性任務(wù)的混合任務(wù)集進(jìn)行研究。另外，基于工作負(fù)荷的DVS算法盡管能從系統(tǒng)級上解決無用能耗問題，但卻很少考慮到系統(tǒng)的實時性。

1 動態(tài)電壓調(diào)節(jié)算法理論背景
1.1 動態(tài)電壓調(diào)節(jié)算法的必要性
    由于CMOS電路的能量消耗E與電路電壓V的平方成正比，因此降低電壓是降低線路能耗的最有效的方法之一。DVS算法的基本原理：系統(tǒng)在運行時間內(nèi)根據(jù)性能的不同要求而相應(yīng)地執(zhí)行降低或者提高電壓和工作頻率的操作，從而降低能耗。
    傳統(tǒng)的電源管理技術(shù)只是在空閑時間內(nèi)降低功耗十分有效，而在運行時間內(nèi)卻無能為力。月前，一些操作系統(tǒng)內(nèi)核對動態(tài)電壓管理(DPM)的支持還是局限于不能調(diào)整核心電壓，主要是通過調(diào)整CPU頻率和支持開關(guān)外圍設(shè)備的供電來實現(xiàn)。但是近年來，隨著半導(dǎo)體技術(shù)的發(fā)展，在運行時態(tài)動態(tài)改變處理器的工作電壓和／或時鐘頻率已經(jīng)變成了現(xiàn)實。很多商用嵌入式處理支持動態(tài)電壓調(diào)節(jié)DVS這一技術(shù)，比如TI公司的OMAP系列處理器、Intel公司的StrongARM處理器、Transmeta公司的Crusoe處理器，還有IBM公司的PowerPC 405LP處理器等。
1．2 實時操作系統(tǒng)與任務(wù)調(diào)度
    在實時系統(tǒng)軟件中，最基本的軟件是實時操作系統(tǒng)。它是實時系統(tǒng)軟件的基礎(chǔ)，所有的實時應(yīng)用軟件都是在實時操作系統(tǒng)的支撐下運行的。與通用操作系統(tǒng)相比，實時操作系統(tǒng)有其特有的一些重要特征，包括規(guī)模較小、中斷時間很短、進(jìn)程切換很快、中斷被屏蔽時間很短、能管理ms級或μs級的多個定時器。因此它能適應(yīng)各種實時應(yīng)用的需求，從快速的實時響應(yīng)到慢速的實時響應(yīng)，都能應(yīng)付自如。
    實時系統(tǒng)的實時性通過周期(period)和時限(dead-line)來體現(xiàn)。周期是均勻重復(fù)性任務(wù)每兩次調(diào)用開始的時間間隔。任務(wù)必須在某個時刻前完成操作，啟動時刻與該時刻的時間間隔被稱為“時限”。均勻重復(fù)性任務(wù)又稱為“周期性任務(wù)(periodic task)”。周期性任務(wù)在一個周期內(nèi)的一次調(diào)用可以看作是一個作業(yè)。通常，周期性任務(wù)的作業(yè)周期和時限是相等的。
    實時操作系統(tǒng)的核心就是任務(wù)調(diào)度。它提供給系統(tǒng)一個決策機(jī)制，決定在某個瞬間時刻下，系統(tǒng)作業(yè)池中哪一個作業(yè)占用處理器。基于線程的任務(wù)問DVS算法就是以實時系統(tǒng)的任務(wù)調(diào)度為主要理論基礎(chǔ)。
1．3 服務(wù)器
    然而，現(xiàn)實的情況是實時系統(tǒng)中并非所有的任務(wù)都是非周期性的。對于兩種任務(wù)的混合調(diào)度情況，在基于優(yōu)先級的方案中，簡單地使非周期性任務(wù)的優(yōu)先級低于周期性的任務(wù)。這樣，非周期性任務(wù)作為后臺活動運行；而在搶占式系統(tǒng)中，它就不能掠奪周期性任務(wù)的資源。盡管這是一個安全的方案，但是考慮到非周期性任務(wù)的時限，如果讓它們只作為后臺運行，往往會錯過它們的時限。為了改善非周期性任務(wù)的這種狀況，可利用服務(wù)器(server)來解決。在RM策略下，最廣泛研究的是可延期服務(wù)器(De-ferred Servcr，DS)和偶發(fā)服務(wù)器(Sporadic Server，SS)。
    在DS中，引進(jìn)一個新的最高優(yōu)先級任務(wù)，這個任務(wù)也就是服務(wù)器。它有一個周期Ts和一個容量(Budget)Es。在運行時態(tài)，當(dāng)一個非周期性任務(wù)達(dá)到時，如果服務(wù)器有可用容量，就立即開始執(zhí)行，直到任務(wù)完成或服務(wù)器容量耗盡；如果服務(wù)器沒有可用容量，那么非周期進(jìn)程會被掛起(或轉(zhuǎn)換為后臺優(yōu)先級)。在DS模型中，服務(wù)器容量每Ts個單位被補充一次。
    SS的操作不同于DS在于它的容量補充策略。在SS中，如果一個任務(wù)在t時刻到達(dá)，并要求使用容量e，那么服務(wù)器在時間t后的Ts個時間單位補充容量e。通常，SS能提供比DS更高的容量，但同時也增加了實現(xiàn)的開銷。

2 基于混合任務(wù)集的減慢因子DVS算法
    在實時系統(tǒng)中可調(diào)度性是保證系統(tǒng)可靠的重要參數(shù)，對任務(wù)集進(jìn)行可調(diào)度性分析是減慢因子算法的必要部分。在進(jìn)行可調(diào)度性分析的過程中，本文把非周期性任務(wù)的服務(wù)器看作固定優(yōu)先級的周期性任務(wù)，將服務(wù)器的周期Ts作為任務(wù)周期和周期性任務(wù)一起分析。假設(shè)在系統(tǒng)S中存在著n個周期性任務(wù)t1、t2、t3、K、tn和個非周期性任務(wù)a1、a2、a3、K、an，所有的非周期性任務(wù)受可延期服務(wù)器DS的調(diào)度。如果系統(tǒng)S運行于固定速度處理器上，混合任務(wù)集在單調(diào)速率可搶占的調(diào)度方案下調(diào)度，那么可以用周期性任務(wù)集的單調(diào)速率可搶占調(diào)度方案的響應(yīng)時間分析方法對這個混合任務(wù)集進(jìn)行可調(diào)度分析。
    減慢因子即任務(wù)的運行頻率和最高頻率之間的比值。在系統(tǒng)運行期間，即使所有任務(wù)按照最壞情況執(zhí)行時間(WCET)運行，大多數(shù)情況下處理器的利用率也遠(yuǎn)低于l0O％，任務(wù)集在某個任務(wù)時限前，系統(tǒng)處于空閑調(diào)度循環(huán)中。因此，對處理器的電壓和工作頻率進(jìn)行減慢因子計算，使空閑時間間隔大大縮短甚至消失，這樣就達(dá)到了降低能耗的目的。
    在下面的減慢DVS算法中，當(dāng)任何新的周期性任務(wù)或者服務(wù)器進(jìn)入系統(tǒng)并且在調(diào)度器中登記后，將會執(zhí)行Compute_Slowdown_Factors過程，進(jìn)行整個系統(tǒng)的可調(diào)度性分析，并且為每一個任務(wù)計算出最低的工作頻率，從而保證所有任務(wù)在其工作頻率下運行仍舊是可調(diào)度的，不會影響整個系統(tǒng)的實時性需求。
    下面給出計算靜態(tài)減慢因子as算法的偽代碼(其中0<αs≤1)

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

3 算法驗證和仿真
    本算法通過Tl OMAPl612的TC-SCDMA無線終端平臺來驗證，對實時嵌入式操作系統(tǒng)Nucleus微內(nèi)核進(jìn)行功能上的擴(kuò)充，主要是實現(xiàn)了可延期服務(wù)器(DS)和偶發(fā)服務(wù)器(SS)來對非周期性任務(wù)進(jìn)行調(diào)度。同時，又整合了基于本算法的DVS模塊和CPU功率檢測模塊。
    本實驗通過3種情況(沒有采用DVS算法，以及基于混合任務(wù)集的減慢因子VVS算法在DS和SS中的分別應(yīng)用)分別在服務(wù)器利用率為25％、35％、45％的情況下進(jìn)行了時間為60 s的實驗，得出各情況下能耗在不同服務(wù)器利用率下的關(guān)系，如圖1所示。

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

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