基于最早截止期優(yōu)先算法的過(guò)渡過(guò)程研究

錢光明

(湖南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,長(zhǎng)沙410081)

基于最早截止期優(yōu)先算法的過(guò)渡過(guò)程研究

錢光明

(湖南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,長(zhǎng)沙410081)

在以最早截止期優(yōu)先算法調(diào)度的實(shí)時(shí)系統(tǒng)中,如果出現(xiàn)新任務(wù)插入和/或現(xiàn)行任務(wù)加速要求,而系統(tǒng)所剩帶寬又不足時(shí),必須進(jìn)行帶寬轉(zhuǎn)讓,系統(tǒng)運(yùn)行模式將被迫發(fā)生改變。針對(duì)該問(wèn)題,研究新任務(wù)插入和/或現(xiàn)行任務(wù)加速的動(dòng)態(tài)過(guò)程,分析帶寬轉(zhuǎn)讓對(duì)系統(tǒng)可調(diào)度性的影響。應(yīng)用處理器需求準(zhǔn)則,證明截止期丟失只可能出現(xiàn)在某一時(shí)間點(diǎn)之前。通過(guò)該結(jié)論可以合理定義過(guò)渡過(guò)程的長(zhǎng)度,從而展示一個(gè)清晰的三階段模型。最后給出相關(guān)仿真實(shí)例。

帶寬轉(zhuǎn)讓;任務(wù)插入;模式改變;過(guò)渡過(guò)程;截止期;處理器需求準(zhǔn)則;最早截止期優(yōu)先算法

1 概述

模式改變存在于諸多實(shí)際應(yīng)用中。例如,當(dāng)一臺(tái)電腦開機(jī)而長(zhǎng)時(shí)間無(wú)人操作時(shí),自動(dòng)進(jìn)入屏幕保護(hù)就是一種模式改變;一部手機(jī)正在用于電子游戲過(guò)程中,突然有電話到來(lái),游戲暫停而進(jìn)入通話模式,也是一種模式改變。

目前,眾多的嵌入式芯片更是專門設(shè)計(jì)了多種模式供設(shè)計(jì)者選擇,如運(yùn)行模式、空閑模式、省電模式等。多模式的引入,往往是為了系統(tǒng)的有限資源得到盡可能合理而充分的利用。

一般地,當(dāng)系統(tǒng)的某些內(nèi)部狀態(tài)發(fā)生有效改變,或是探測(cè)到某些外部事件時(shí),便會(huì)引起模式改變[1]。

為滿意地完成一個(gè)模式改變,有許多問(wèn)題需要研究[1-2]。例如,采用何種策略進(jìn)行。可調(diào)度性如何[3]。過(guò)渡過(guò)程的長(zhǎng)度如何定義和計(jì)算,過(guò)渡過(guò)程對(duì)系統(tǒng)有何影響等[4-5]。顯然,對(duì)這些問(wèn)題的回答,與具體系統(tǒng)結(jié)構(gòu)、具體調(diào)度算法以及應(yīng)用場(chǎng)合等諸多因素有關(guān)。

本文研究的是這樣一種模式改變:一個(gè)以最早截止期優(yōu)先(Earliest Deadline First,EDF)算法調(diào)度的周期性實(shí)時(shí)系統(tǒng)中,當(dāng)有新任務(wù)要求插入和/或現(xiàn)行任務(wù)要求加速,而系統(tǒng)所剩帶寬又不足時(shí),必須要進(jìn)行帶寬轉(zhuǎn)讓,系統(tǒng)運(yùn)行模式將被迫發(fā)生改變。此處的系統(tǒng)所剩帶寬,指的是1(即100%)減去所有現(xiàn)行任務(wù)的使用率(帶寬)之和。

這樣的任務(wù)插入和加速問(wèn)題,可聯(lián)想到某些實(shí)際應(yīng)用場(chǎng)合。如機(jī)器人目標(biāo)逼近測(cè)量時(shí),目標(biāo)越近,負(fù)責(zé)測(cè)量的任務(wù)周期應(yīng)該越短,使用率增加(加速)。又如一個(gè)網(wǎng)絡(luò)通道中,如果帶寬基本被現(xiàn)有用戶用完,而新用戶又要進(jìn)來(lái)時(shí),只好壓縮舊用戶的帶寬以容納新用戶的插入。

EDF是一個(gè)經(jīng)典調(diào)度算法[6-7]。文獻(xiàn)[6]證明了只要所有任務(wù)使用率之和不大于1,系統(tǒng)就是可調(diào)度的,即不會(huì)出現(xiàn)截止期丟失的情況。但當(dāng)插入和加速引起模式改變時(shí),這一可調(diào)度性準(zhǔn)則是否合適仍然是個(gè)問(wèn)題。因此,本文將通過(guò)分析和證明指出,只要新模式時(shí)所有任務(wù)使用率之和不大于1,截止期丟失就只可能出現(xiàn)在某一時(shí)間點(diǎn)之前,而系統(tǒng)在新模式下一定是可調(diào)度的。同時(shí)合理地將過(guò)渡過(guò)程的長(zhǎng)度定義為tr到該時(shí)間點(diǎn)之間。

2 相關(guān)研究

當(dāng)系統(tǒng)從一種模式過(guò)渡到另一種模式時(shí),可以用圖1來(lái)簡(jiǎn)單表示。其中,tr表示模式改變的要求時(shí)刻。在該時(shí)刻之前系統(tǒng)運(yùn)行于舊模式,或稱現(xiàn)行模式。tr之后系統(tǒng)進(jìn)入過(guò)渡過(guò)程,然后工作于新模式。

圖1 模式改變對(duì)應(yīng)的3個(gè)階段

實(shí)時(shí)系統(tǒng)雖然有數(shù)十年的研究歷史,但任務(wù)插入和加速這一模式改變問(wèn)題,一直有相當(dāng)?shù)难芯侩y度。如文獻(xiàn)[4]發(fā)現(xiàn)一個(gè)有趣現(xiàn)象:動(dòng)態(tài)加入一個(gè)新任務(wù)時(shí),如果不很小心,會(huì)出現(xiàn)截止期丟失的情況。但當(dāng)時(shí)并未深入研究。

關(guān)于EDF算法的任務(wù)插入和/或加速問(wèn)題,文獻(xiàn)[8]給出了一個(gè)彈性調(diào)度模型。當(dāng)系統(tǒng)剩余帶寬不足時(shí),對(duì)現(xiàn)行任務(wù)進(jìn)行壓縮,以應(yīng)對(duì)插入和/或加速。該模型中求出了一個(gè)時(shí)間點(diǎn),指出只要不早于該點(diǎn),插入和/或加速就不會(huì)引起截止期丟失。文獻(xiàn)[9]證明了這樣的時(shí)間點(diǎn)還可以更早些,并且加速問(wèn)題可以等效為插入問(wèn)題來(lái)研究(故下面只以插入來(lái)描述模型即可)。因此,什么是最早的、不引起截止期丟失的時(shí)間點(diǎn)(文獻(xiàn)[8]稱為最早可行時(shí)刻),并非本文的研究?jī)?nèi)容。文獻(xiàn)[8-10]均未指出截止期丟失可能出現(xiàn)的區(qū)間,均未明確過(guò)渡過(guò)程到底該算到何時(shí)為止,這正是本文要研究解決的問(wèn)題。

首先通過(guò)以下定義列出關(guān)于任務(wù)壓縮的模型[9]。

定義 任務(wù)壓縮

圖2 任務(wù)壓縮示意圖

3 過(guò)渡過(guò)程

由上可知,tr前夕,現(xiàn)行任務(wù)集為(τi,Γ)。要研究過(guò)渡過(guò)程以及系統(tǒng)的可調(diào)度性,一般選擇從現(xiàn)行任務(wù)集的運(yùn)行起點(diǎn)tLCM0開始[9]。且注意有式(1)表達(dá)的時(shí)間次序。

此外,相關(guān)定理的證明中要用到處理器需求準(zhǔn)則[11-12]:當(dāng)且僅當(dāng)任務(wù)集中所有任務(wù)的處理器需求之和小于等于1時(shí),任務(wù)集是基于EDF可調(diào)度的。

一個(gè)任務(wù)在一個(gè)時(shí)間段內(nèi)的處理器需求,等于該時(shí)間段內(nèi)該任務(wù)必須要完成的執(zhí)行量。

從tLCM0到任意時(shí)間點(diǎn)t,新任務(wù)的處理器需求之和表示為:

其中,J代表新任務(wù)組成的子集;Unew為該子集中各任務(wù)使用率之和;Uj為其中某一任務(wù)的使用率;rj為其釋放時(shí)刻;rJ為它們中最早發(fā)布的那個(gè)任務(wù)的釋放時(shí)刻,rJ≥tr。最壞情況是所有新任務(wù)同時(shí)在rJ=tr時(shí)刻釋放。

未受壓的現(xiàn)行任務(wù)處理器需求之和為:

綜上,如果受壓任務(wù)τi的處理器需求為Di(tLCM0,t),則系統(tǒng)所有任務(wù)處理器需求之和為:

再引入符號(hào)Δ:

那么,依據(jù)上述處理器需求準(zhǔn)則[11-12],當(dāng)且僅當(dāng)Δ≥0時(shí),系統(tǒng)是可調(diào)度。下面的證明將用到這一結(jié)論。

定理1 基于EDF可調(diào)度的周期性實(shí)時(shí)任務(wù)集中,tLCM0為任務(wù)集運(yùn)行的起點(diǎn)時(shí)刻。從tr開始?jí)嚎s任務(wù)τi(Ci,Ti)以出讓帶寬給新任務(wù)。在[tLCM0,t0+Ti)期間,一定不會(huì)出現(xiàn)任何任務(wù)超截止期的情況。

證明:?t∈[tr,t0+Ti),τi在[tLCM0,t]間的處理器需求:

那么,依據(jù)式(2)和式(3),有:

因此:

所以,系統(tǒng)在該時(shí)間段可調(diào)度,即不會(huì)出現(xiàn)截止期丟失情況。證畢。

由定理1可知,在時(shí)間點(diǎn)t0+Ti之前,系統(tǒng)總是可調(diào)度的。

基于式(2)和式(3),有:

因此:

顯然,Δ≥0表明該時(shí)間段內(nèi)系統(tǒng)總是可調(diào)度的。證畢。

由定理2可知,當(dāng)時(shí)間大于或等于t0+Ti′時(shí),系統(tǒng)總是可調(diào)度的。

證明:由定理1和定理2可直接得出此推論。

4 仿真示例

雖然經(jīng)過(guò)了上述證明,仍然有必要進(jìn)行示例驗(yàn)證。在EDF實(shí)驗(yàn)平臺(tái)上的大量仿真表明上述定理是準(zhǔn)確無(wú)疑的。圖3為示例之一。

圖3 任務(wù)壓縮和插入的模式改變示例

t0+Ti=8,t0+=16。依據(jù)上述定理和推論,該例中的過(guò)渡過(guò)程應(yīng)是[4,16)這一時(shí)間段,截止期丟失只可能出現(xiàn)在這一期間。如圖3所示,τj(1,4)的第一個(gè)作業(yè)截止期未能得以滿足,本該完成的一個(gè)單位長(zhǎng)執(zhí)行量被延誤到第2個(gè)周期的t=8和t=9之間才完成。

新模式從t0+=16開始,從該點(diǎn)及以后的時(shí)間內(nèi),所有作業(yè)截止期都能滿足。本例中有意選擇τi, τk和τj,使它們?cè)谠擖c(diǎn)均開始一個(gè)新的作業(yè),以便可以明顯看出后面是可調(diào)度的。實(shí)際上,即使不如此,上面的定理也保證了新模式下一定不會(huì)再出現(xiàn)截止期丟失。

5 結(jié)束語(yǔ)

關(guān)于任務(wù)壓縮和插入的模式改變,盡管舊模式和新模式下均滿足所有任務(wù)使用率之和不大于1,但仍然有可能出現(xiàn)截止期丟失。本文證明了這種丟失只可能出現(xiàn)在過(guò)渡過(guò)程[tr,t0+)中,這將成為今后繼續(xù)研究的一個(gè)重要基礎(chǔ)。但本文討論的是壓縮單個(gè)任務(wù)τi,因此,同時(shí)壓縮多個(gè)任務(wù)時(shí)能得到何種結(jié)論是需要進(jìn)一步研究的課題。此外,即使是單任務(wù)壓縮,如何確定最早的時(shí)間點(diǎn),使新任務(wù)的插入不至于引起截止期丟失,也仍然需要深入研究。

[1] Real J,Crespo A.Mode Change Protocols for Real-Time Systems:A Survey and a New Proposal[J].Real-Time Systems,2004,26(2):161-197.

[2] Sha L,Rajkumar R,Lehoczky J,et al.Mode Change Protocols for Priority-Driven Preemptive Scheduling[J]. Real-Time Systems,1989,1(3):243-264.

[3] Pedro P,BurnsA.Scheduabilty AnalysisforMode Change[C]//Proc.of the 10th EUROMICRO Workshop on Real-Time Systems Symposium.Berlin,Germany: [s.n.],1998:172-179.

[4] PillaiP,Shin K G.Real-Time Dynamic Voltage Scaling for Low-Power[C]//Proc.of the 18th ACM Symposium on Operating Systems Principles.Banff,Canada:[s.n.], 2001:89-102.

[5] Qian Guangming,ChenXianghua,YaoGang.Two Methods to Release a New Real-time Task[J].Indian Journal of Computer Science and Engineering,2012,3 (1):75-81.

[6] Liu C L,Laylan J W.Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment[J]. Journal of the ACM,1973,20(1):40-61.

[7] Baruah S.Partitioned EDF Scheduling:A Closer Look [J].Real-Time Systems,2013,49(6):715-729.

[8] Buttazzo G C,LipariG,CaccamoM,etal.Elastic Scheduling for Flexible Workload Management[J].IEEE Transactions on Computers,2002,51(3):289-302.

[9] Qian Guangming.An Earlier Time for Inserting and/or Accelerating Tasks[J].Real-Time Systems,2009,41(3): 181-194.

[10] 錢光明,姜 輝,陳湘華.實(shí)時(shí)任務(wù)調(diào)度算法最早可行時(shí)刻的求取模式[J].計(jì)算機(jī)工程,2012,38(4): 284-286.

[11] Barauh S K,Howell R R,Rosier L E.Algorithms and Complexity Concerning the Preemptive Scheduling of Periodic Real-Time Tasks on One Processor[J].Real-Time Systems,1990,2(4):301-324.

[12] Jeffay K,Stone D L.Accounting for Interrupt Handling Costs in Dynamic Priority Task Systems[C]//Proc.of the 14th IEEE Real-Time Systems Symposium.Raleigh-Durham,USA:[s.n.],1993:212-221.

編輯 金胡考

Research on Transition Process Based on Earliest Deadline First Algorithm

QIAN Guang-ming
(College of Mathematics and Computer Science,Hunan Normal University,Changsha 410081,China)

In a real-time system scheduled with the Earliest Deadline First(EDF)algorithm,if the request of new tasks'insertion and/or current tasks'acceleration occurs and the remaining bandwidth of the system is not enough for this request,then part of the bandwidth has to be freed and the system will change its running mode.Aiming at this problem,this paper discusses the influences on the schedulability by the mode change based on the analysis on the dynamic processes of the insertion of a new task and/or the acceleration of a current task.With the processor demand criterion,it proves that deadline missing is possible only before a time point.Hence the length of the transition can be reasonably defined,and it results a clean research model of three stages.Illustrative examples are also given.

bandwidth transfer;tasks insertion;mode change;transition process;deadline;processor demand criterion; Earliest Deadline First(EDF)algorithm

1000-3428(2014)09-0055-04

A

TP316.2

10.3969/j.issn.1000-3428.2014.09.012

長(zhǎng)沙市科技局基金資助項(xiàng)目(K11ZD014-13)。

錢光明(1963-),男,教授,主研方向:實(shí)時(shí)系統(tǒng),嵌入式應(yīng)用。

2013-09-03

2013-10-27E-mail:qqyy@hunnu.edu.cn