實(shí)時(shí)系統(tǒng)中混合任務(wù)集的動(dòng)態(tài)電壓調(diào)節(jié)算法
掃描二維碼
隨時(shí)隨地手機(jī)看文章
嵌入式實(shí)時(shí)操作系統(tǒng)在目前的嵌入式應(yīng)用中用得越來越廣泛,尤其在功能復(fù)雜、系統(tǒng)龐大的應(yīng)用中顯得愈來愈重要。人們要求實(shí)時(shí)嵌入式產(chǎn)品能夠提供更為強(qiáng)勁的計(jì)算能力,以滿足無線通信、多媒體應(yīng)用的要求,然而高性能的代價(jià)就是高能耗,因此延長實(shí)時(shí)嵌入式系統(tǒng)電池使用時(shí)間已經(jīng)成為實(shí)時(shí)嵌入式系統(tǒng)設(shè)計(jì)普遍關(guān)注的問題。在實(shí)時(shí)嵌入式系統(tǒng)中,核心處理器的能耗占據(jù)整個(gè)能耗的相當(dāng)大一部分。動(dòng)態(tài)電壓調(diào)節(jié)被看作是降低處理器能耗的關(guān)鍵技術(shù),其原理是在系統(tǒng)運(yùn)行時(shí)態(tài)通過動(dòng)態(tài)改變處理器的電壓和頻率,降低系統(tǒng)中的無用能耗,從而提高能量的有效利用率[1]。
當(dāng)前,基于任務(wù)的動(dòng)態(tài)電壓調(diào)節(jié)算法主要集中在對(duì)周期性任務(wù)集合的研究,其中只有很少一部分是對(duì)周期性任務(wù)和非周期性任務(wù)的混合任務(wù)集進(jìn)行研究。另外,基于工作負(fù)荷的DVS算法盡管能從系統(tǒng)級(jí)上解決無用能耗問題,但卻很少考慮到系統(tǒng)的實(shí)時(shí)性。
1 動(dòng)態(tài)電壓調(diào)節(jié)算法理論背景
1.1 動(dòng)態(tài)電壓調(diào)節(jié)算法的必要性
由于CMOS電路的能量消耗E與電路電壓V的平方成正比,因此降低電壓是降低線路能耗的最有效的方法之一。DVS算法的基本原理: 系統(tǒng)在運(yùn)行時(shí)間內(nèi)根據(jù)性能的不同要求而相應(yīng)地執(zhí)行降低或者提高電壓和工作頻率的操作,從而降低能耗。
傳統(tǒng)的電源管理技術(shù)只是在空閑時(shí)間內(nèi)降低功耗十分有效,而在運(yùn)行時(shí)間內(nèi)卻無能為力。目前,一些操作系統(tǒng)內(nèi)核對(duì)動(dòng)態(tài)電壓管理(DPM)的支持還是局限于不能調(diào)整核心電壓,主要是通過調(diào)整CPU頻率和支持開關(guān)外圍設(shè)備的供電來實(shí)現(xiàn)。但是近年來,隨著半導(dǎo)體技術(shù)的發(fā)展,在運(yùn)行時(shí)態(tài)動(dòng)態(tài)改變處理器的工作電壓和/或時(shí)鐘頻率已經(jīng)變成了現(xiàn)實(shí)。很多商用嵌入式處理支持動(dòng)態(tài)電壓調(diào)節(jié)DVS這一技術(shù),比如TI公司的OMAP系列處理器、Intel公司的StrongARM處理器、Transmeta公司的Crusoe處理器,還有IBM公司的PowerPC 405LP處理器等。
1.2 實(shí)時(shí)操作系統(tǒng)與任務(wù)調(diào)度
在實(shí)時(shí)系統(tǒng)軟件中,最基本的軟件是實(shí)時(shí)操作系統(tǒng)。它是實(shí)時(shí)系統(tǒng)軟件的基礎(chǔ),所有的實(shí)時(shí)應(yīng)用軟件都是在實(shí)時(shí)操作系統(tǒng)的支撐下運(yùn)行的。與通用操作系統(tǒng)相比,實(shí)時(shí)操作系統(tǒng)有其特有的一些重要特征,包括規(guī)模較小、中斷時(shí)間很短、進(jìn)程切換很快、中斷被屏蔽時(shí)間很短、能管理ms級(jí)或μs級(jí)的多個(gè)定時(shí)器。因此它能適應(yīng)各種實(shí)時(shí)應(yīng)用的需求,從快速的實(shí)時(shí)響應(yīng)到慢速的實(shí)時(shí)響應(yīng),都能應(yīng)付自如。
實(shí)時(shí)系統(tǒng)的實(shí)時(shí)性通過周期(period)和時(shí)限(deadline)來體現(xiàn)。周期是均勻重復(fù)性任務(wù)每兩次調(diào)用開始的時(shí)間間隔。任務(wù)必須在某個(gè)時(shí)刻前完成操作,啟動(dòng)時(shí)刻與該時(shí)刻的時(shí)間間隔被稱為“時(shí)限”。均勻重復(fù)性任務(wù)又稱為“周期性任務(wù)(periodic task)”。周期性任務(wù)在一個(gè)周期內(nèi)的一次調(diào)用可以看作是一個(gè)作業(yè)。通常,周期性任務(wù)的作業(yè)周期和時(shí)限是相等的。
實(shí)時(shí)操作系統(tǒng)的核心就是任務(wù)調(diào)度。它提供給系統(tǒng)一個(gè)決策機(jī)制,決定在某個(gè)瞬間時(shí)刻下,系統(tǒng)作業(yè)池中哪一個(gè)作業(yè)占用處理器?;诰€程的任務(wù)間DVS算法就是以實(shí)時(shí)系統(tǒng)的任務(wù)調(diào)度為主要理論基礎(chǔ)。
1.3 服務(wù)器
然而,現(xiàn)實(shí)的情況是實(shí)時(shí)系統(tǒng)中并非所有的任務(wù)都是非周期性的。對(duì)于兩種任務(wù)的混合調(diào)度情況,在基于優(yōu)先級(jí)的方案中,簡單地使非周期性任務(wù)的優(yōu)先級(jí)低于周期性的任務(wù)[2]。這樣,非周期性任務(wù)作為后臺(tái)活動(dòng)運(yùn)行;而在搶占式系統(tǒng)中,它就不能掠奪周期性任務(wù)的資源。盡管這是一個(gè)安全的方案,但是考慮到非周期性任務(wù)的時(shí)限,如果讓它們只作為后臺(tái)運(yùn)行,往往會(huì)錯(cuò)過它們的時(shí)限。為了改善非周期性任務(wù)的這種狀況,可利用服務(wù)器(server)來解決。在RM策略下,最廣泛研究的是可延期服務(wù)器(Deferred Server,DS)和偶發(fā)服務(wù)器[3](Sporadic Server,SS)。
在DS中,引進(jìn)一個(gè)新的最高優(yōu)先級(jí)任務(wù),這個(gè)任務(wù)也就是服務(wù)器。它有一個(gè)周期Ts和一個(gè)容量(Budget)Es。在運(yùn)行時(shí)態(tài),當(dāng)一個(gè)非周期性任務(wù)達(dá)到時(shí),如果服務(wù)器有可用容量,就立即開始執(zhí)行,直到任務(wù)完成或服務(wù)器容量耗盡;如果服務(wù)器沒有可用容量,那么非周期進(jìn)程會(huì)被掛起(或轉(zhuǎn)換為后臺(tái)優(yōu)先級(jí))。在DS模型中,服務(wù)器容量每Ts個(gè)單位被補(bǔ)充一次。
SS的操作不同于DS在于它的容量補(bǔ)充策略。在SS中,如果一個(gè)任務(wù)在t時(shí)刻到達(dá),并要求使用容量e,那么服務(wù)器在時(shí)間t后的Ts個(gè)時(shí)間單位補(bǔ)充容量e。通常,SS能提供比DS更高的容量,但同時(shí)也增加了實(shí)現(xiàn)的開銷。
2 基于混合任務(wù)集的減慢因子DVS算法
在實(shí)時(shí)系統(tǒng)中可調(diào)度性是保證系統(tǒng)可靠的重要參數(shù),對(duì)任務(wù)集進(jìn)行可調(diào)度性分析是減慢因子算法的必要部分。在進(jìn)行可調(diào)度性分析的過程中,本文把非周期性任務(wù)的服務(wù)器看作固定優(yōu)先級(jí)的周期性任務(wù),將服務(wù)器的周期Ts作為任務(wù)周期和周期性任務(wù)一起分析。假設(shè)在系統(tǒng)S中存在著n個(gè)周期性任務(wù)t1、t2、t3、 K、tn和個(gè)非周期性任務(wù)a1、a2、a3、K、an,所有的非周期性任務(wù)受可延期服務(wù)器DS的調(diào)度。如果系統(tǒng)S運(yùn)行于固定速度處理器上,混合任務(wù)集在單調(diào)速率可搶占的調(diào)度方案下調(diào)度,那么可以用周期性任務(wù)集的單調(diào)速率可搶占調(diào)度方案的響應(yīng)時(shí)間分析方法對(duì)這個(gè)混合任務(wù)集進(jìn)行可調(diào)度分析。
減慢因子即任務(wù)的運(yùn)行頻率和最高頻率之間的比值。在系統(tǒng)運(yùn)行期間,即使所有任務(wù)按照最壞情況執(zhí)行時(shí)間(WCET)運(yùn)行,大多數(shù)情況下處理器的利用率也遠(yuǎn)低于100%,任務(wù)集在某個(gè)任務(wù)時(shí)限前,系統(tǒng)處于空閑調(diào)度循環(huán)中。因此,對(duì)處理器的電壓和工作頻率進(jìn)行減慢因子計(jì)算,使空閑時(shí)間間隔大大縮短甚至消失,這樣就達(dá)到了降低能耗的目的。
在下面的減慢DVS算法中,當(dāng)任何新的周期性任務(wù)或者服務(wù)器進(jìn)入系統(tǒng)并且在調(diào)度器中登記后,將會(huì)執(zhí)行 Compute_Slowdown_Factors過程,進(jìn)行整個(gè)系統(tǒng)的可調(diào)度性分析,并且為每一個(gè)任務(wù)計(jì)算出最低的工作頻率,從而保證所有任務(wù)在其工作頻率下運(yùn)行仍舊是可調(diào)度的,不會(huì)影響整個(gè)系統(tǒng)的實(shí)時(shí)性需求。
下面給出計(jì)算靜態(tài)減慢因子αs算法的偽代碼(其中0<αs≤1):
//Algorithm Compute_Slowdown_Factors
Inputs:
S//將要進(jìn)行減慢因子計(jì)算的任務(wù)集,包括周期性任務(wù)和非周期性任務(wù)的服務(wù)器
Outputs:
Slowdown_Factors[]//任務(wù)集的靜態(tài)減慢因子
{
Sm//計(jì)算出減慢因子后,將要超過時(shí)限的任務(wù)集,初始化為空集
Current_Scaling _Factor=1;
For S中的每一個(gè)任務(wù)i
Slowdown_Factor[i]=1;
While (S不為空集){
F=Scale_WCET(S,Slowdown_Factor[]);//計(jì)算減慢因子F
重新設(shè)置Sm;
Current_Scaling_Facotr *=F;
For S中的每一個(gè)任務(wù)i {
If任務(wù)i!=服務(wù)器
Slowdown_Factor[i]=F;
}
重新設(shè)置集合S,讓集合S中所有任務(wù)的優(yōu)先級(jí)小于Sm中最低優(yōu)先級(jí)任務(wù)的優(yōu)先級(jí);
}
}
上面的程序通過Scale_WCET過程計(jì)算一個(gè)減慢因子,使得給定任務(wù)集中存在的一個(gè)或者多個(gè)任務(wù)的最差響應(yīng)時(shí)間剛好等于它們的時(shí)限(此時(shí)該任務(wù)集剛好可調(diào)度),這樣的任務(wù)稱為“臨界任務(wù)”。Compute_Slowdown_Factors過程首先調(diào)用Scale_WCET過程計(jì)算初始任務(wù)集的同一減慢因子F;然后讓優(yōu)先級(jí)低于臨界任務(wù)的任務(wù)集繼續(xù)調(diào)用Scale_WCET過程計(jì)算出新的減慢因子。這是因?yàn)槿绻^續(xù)讓作用于優(yōu)先級(jí)高于臨界任務(wù)的減慢因子F變小,則必然會(huì)導(dǎo)致至少有一個(gè)臨界任務(wù)超過時(shí)限,破壞了系統(tǒng)的實(shí)時(shí)性;而讓作用優(yōu)先級(jí)低于臨界任務(wù)的減慢因子F變小,則不會(huì)影響整個(gè)任務(wù)集的可調(diào)度性。這個(gè)過程將會(huì)反復(fù)執(zhí)行,直到初始任務(wù)集中的最低優(yōu)先級(jí)任務(wù)變成臨界任務(wù)??傊?,這個(gè)迭代過程為每一個(gè)任務(wù)計(jì)算出減慢因子,同時(shí)保證整個(gè)任務(wù)集是可以調(diào)度的。需要說明的是,對(duì)于服務(wù)器將不會(huì)應(yīng)用靜態(tài)減慢因子,因?yàn)槿绻黾恿朔?wù)器的運(yùn)行時(shí)間,則必然會(huì)造成受服務(wù)器調(diào)度的非周期性任務(wù)的平均響應(yīng)時(shí)間的增加。
3 算法驗(yàn)證和仿真
本算法通過T1 OMAP1612的TCSCDMA無線終端平臺(tái)來驗(yàn)證,對(duì)實(shí)時(shí)嵌入式操作系統(tǒng)Nucleus微內(nèi)核進(jìn)行功能上的擴(kuò)充,主要是實(shí)現(xiàn)了可延期服務(wù)器(DS)和偶發(fā)服務(wù)器(SS)來對(duì)非周期性任務(wù)進(jìn)行調(diào)度。同時(shí),又整合了基于本算法的DVS模塊和CPU功率檢測模塊。
本實(shí)驗(yàn)通過3種情況(沒有采用DVS算法,以及基于混合任務(wù)集的減慢因子DVS算法在DS和SS中的分別應(yīng)用)分別在服務(wù)器利用率為25%、35%、45%的情況下進(jìn)行了時(shí)間為60 s的實(shí)驗(yàn),得出各情況下能耗在不同服務(wù)器利用率下的關(guān)系,如圖1所示。
圖1 各種算法的能耗對(duì)比
圖1結(jié)果表明,采用基于混合任務(wù)集的減慢因子DVS算法與沒有采用DVS算法相比,能耗降低了大概19.3%~32%;同時(shí)也看到,服務(wù)器利用率越高,能耗越接近于沒有采用DVS算法所產(chǎn)生的能耗。這是因?yàn)闉榱吮WC非周期性任務(wù)有很短的響應(yīng)時(shí)間,基于混合任務(wù)集的減慢因子DVS算法在服務(wù)器上運(yùn)行時(shí),總是以最高頻率運(yùn)行,同時(shí)高服務(wù)器利用率意味著服務(wù)器會(huì)占用很大一部分CPU周期。因此,在這樣的環(huán)境下,CPU很大的一部分時(shí)間都運(yùn)行在最高頻率上,導(dǎo)致服務(wù)器利用率越高, 越接近沒有采用DVS算法的情況。
4 結(jié)論
本文提出的針對(duì)靜態(tài)空閑間隔的靜態(tài)減慢因子算法屬于脫機(jī)(offline)的DVS算法。該算法同時(shí)把占系統(tǒng)很大部分的非周期性任務(wù)一起進(jìn)行分析,把非周期性任務(wù)的服務(wù)器當(dāng)作周期性任務(wù)進(jìn)行動(dòng)態(tài)電壓調(diào)節(jié),從而解決了非周期性任務(wù)的功耗問題,具有很大的實(shí)際意義。在保證性能的同時(shí),降低了系統(tǒng)中的無用能耗,提高了能量的有效利用率。隨著研究的深入,還將深入到對(duì)聯(lián)機(jī)(online)情況進(jìn)行動(dòng)態(tài)電壓調(diào)節(jié)。
參考文獻(xiàn)
[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.