基于最早截止期優先算法的過渡過程研究

錢光明

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

基于最早截止期優先算法的過渡過程研究

錢光明

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

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

帶寬轉讓;任務插入;模式改變;過渡過程;截止期;處理器需求準則;最早截止期優先算法

1 概述

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

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

一般地,當系統的某些內部狀態發生有效改變,或是探測到某些外部事件時,便會引起模式改變[1]。

為滿意地完成一個模式改變,有許多問題需要研究[1-2]。例如,采用何種策略進行。可調度性如何[3]。過渡過程的長度如何定義和計算,過渡過程對系統有何影響等[4-5]。顯然,對這些問題的回答,與具體系統結構、具體調度算法以及應用場合等諸多因素有關。

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

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

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

2 相關研究

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

圖1 模式改變對應的3個階段

實時系統雖然有數十年的研究歷史,但任務插入和加速這一模式改變問題,一直有相當的研究難度。如文獻[4]發現一個有趣現象:動態加入一個新任務時,如果不很小心,會出現截止期丟失的情況。但當時并未深入研究。

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

首先通過以下定義列出關于任務壓縮的模型[9]。

定義 任務壓縮

圖2 任務壓縮示意圖

3 過渡過程

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

此外,相關定理的證明中要用到處理器需求準則[11-12]:當且僅當任務集中所有任務的處理器需求之和小于等于1時,任務集是基于EDF可調度的。

一個任務在一個時間段內的處理器需求,等于該時間段內該任務必須要完成的執行量。

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

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

未受壓的現行任務處理器需求之和為:

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

再引入符號Δ:

那么,依據上述處理器需求準則[11-12],當且僅當Δ≥0時,系統是可調度。下面的證明將用到這一結論。

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

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

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

因此:

所以,系統在該時間段可調度,即不會出現截止期丟失情況。證畢。

由定理1可知,在時間點t0+Ti之前,系統總是可調度的。

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

因此:

顯然,Δ≥0表明該時間段內系統總是可調度的。證畢。

由定理2可知,當時間大于或等于t0+Ti′時,系統總是可調度的。

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

4 仿真示例

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

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

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

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

5 結束語

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

[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] 錢光明,姜 輝,陳湘華.實時任務調度算法最早可行時刻的求取模式[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-),男,教授,主研方向:實時系統,嵌入式應用。

2013-09-03

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