錢光明

(湖南師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院,長沙410081)

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

錢光明

(湖南師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院,長沙410081)

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

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

1 概述

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

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

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

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

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

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

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

2 相關(guān)研究

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

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

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

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

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

定義 任務(wù)壓縮

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

3 過渡過程

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

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

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

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

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

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

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

再引入符號Δ:

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

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

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

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

因此:

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

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

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

因此:

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

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

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

4 仿真示例

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

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

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

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

5 結(jié)束語

關(guān)于任務(wù)壓縮和插入的模式改變,盡管舊模式和新模式下均滿足所有任務(wù)使用率之和不大于1,但仍然有可能出現(xiàn)截止期丟失。本文證明了這種丟失只可能出現(xiàn)在過渡過程[tr,t0+)中,這將成為今后繼續(xù)研究的一個重要基礎(chǔ)。但本文討論的是壓縮單個任務(wù)τi,因此,同時壓縮多個任務(wù)時能得到何種結(jié)論是需要進一步研究的課題。此外,即使是單任務(wù)壓縮,如何確定最早的時間點,使新任務(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] 錢光明,姜 輝,陳湘華.實時任務(wù)調(diào)度算法最早可行時刻的求取模式[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

長沙市科技局基金資助項目(K11ZD014-13)。

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

2013-09-03

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