基于EDF的實時任務帶寬轉讓研究綜述

錢光明 鄧朝豐

摘要：實時任務帶寬轉讓問題在網絡通信和機器人目標逼近等許多場合具有應用背景。當新任務插入或老任務加速時，可能需要某些現行任務轉讓帶寬。該文從三個方面對這個問題進行綜述。一是如何進行壓縮任務的選擇，以便盡快而安全地實現這種轉讓;二是如何求出最早的安全轉讓時刻;三是有關算法的收斂問題。這三個方面都是基于最早截止期優先算法來展開研究的。

關鍵詞：帶寬轉讓;安全轉讓時刻;實時任務;選擇性壓縮;最早截止期優先

中圖分類號：TP393 ? ? ? ?文獻標識碼：A

文章編號：1009-3044（2021）31-0060-02

1 引言

本文的任務“帶寬”指的是任務的“使用率”。對于周期性任務[τi（Ci，Ti）]而言，其使用率[Ui=Ci/Ti]，[Ti]是任務周期，[Ci]是每周期所需執行時間（執行量），[i]屬于非負整數集。一個實時系統的全部帶寬看作1，即100%。如果所有任務的周期和執行量都恒定不變，那么，只要它們的帶寬之和不超過1，就是EDF（Earliest Deadline First）可調度的[1]。但是，在進行帶寬轉讓時，即某些老任務（現行任務）出讓帶寬，以應對新任務的插入或其它老任務的加速要求時，即使所有任務帶寬之和不大于1，也可能出現不可調度的情況（超截止期）[2]。所謂帶寬轉讓，就是壓縮某個或某些現行任務（延長其執行周期），使其讓出部分帶寬用于新的帶寬需求，例如，將[τi（Ci，Ti）]的周期延長為[T'i]，其使用率會降低為[U'i=Ci/T'i]，從而讓出的帶寬為

[Ui-U'i=Ci/Ti-Ci/T'i.] ? ? ? ? ? ? ? ? ? ? ? ? （1）

（1）式的帶寬可以全部用于新任務插入或老任務加速。文獻[3]已經證明老任務加速可以等效為新任務插入來處理。實現這種帶寬轉讓時，如何避免出現超截止期，研究由此展開。不會導致截止期丟失的新任務插入稱為平滑插入，相應的插入時刻稱為平滑插入時刻[δ][3]，最早平滑插入時刻表示為[δearliest][4]。

2 轉讓任務的選擇

一個實時系統中，往往有多個任務正在運行。當選擇不同的現行任務進行壓縮時，導致的截止期丟失情況可能會不一樣[5-7]。圖1，假定EDF調度的任務集中，共有兩個現行任務：[τ0（4，8）]和[τ1（4，8）]，它們的帶寬均為1/2，帶寬之和為1，即系統已滿負荷運行。如果在[tr=4]時，有較緊急的新任務[τnew（1，4）]要求插入，帶寬[Unew=1/4]，此時，就不得不進行帶寬轉讓。假設選擇壓縮[τ0]，即延長其周期為16，轉讓1/4的帶寬給[τnew]，并且在[t=4]時立即釋放[τnew]的話，顯然會造成在[t=8]處新任務的截止期丟失。

但是，如果選擇壓縮[τ1]而保持[τ0]不變，即將[τ1]的周期延長為16，則新任務在[t=4]時的插入不會導致任何截止期丟失，如圖2所示。因此，圖2中的[t=4]是一個平衡插入時刻。

帶寬轉讓時，截止期丟失與否，與選擇的壓縮任務有關，這便是文獻[5]提出的選擇性壓縮思想。文獻[6]和[7]進一步對這一思想進行深入研究，提出了一個最晚截止期優先的帶寬轉讓算法：在[tr]所處的周期中，在可壓縮任務集內，先壓縮當前作業截止期最晚的任務。這樣做往往可以取得非常滿意的效果。因為截止期最晚的任務往往是剩余執行量和剩余帶寬較大的任務[6]，可以立即出讓較大比例的帶寬。

3 最早安全轉讓時刻的求取

最早安全轉讓時刻（新任務平滑插入時刻） [δearliest]的求取，一直是一個令人感興趣的挑戰性問題[8-9]。對于任務周期等于截止期的研究模型，只壓縮任務[τi（Ci，Ti）]時，文獻[2]提出公式（2）用于平滑插入時刻的計算：

[δi=Ti—ci（tr）/Ui.] ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（2）

（2）式中[ci（tr）]是任務[τi]開始壓縮時，當前周期的剩余執行量。該式表明：[τi]的出讓帶寬從[δi]開始，一定可以完全被新任務使用而不會引起截止期丟失。通過進一步深入研究，文獻[3]提出了公式（3）：

[δi=Ti—ci（tr）/（Ui—U'i）.] ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（3）

很明顯，公式（3）算出的[δi]要等于或早于公式（2）的值。例如，圖1中，假定在[tr=3]時開始壓縮[τ0（4，8）]，其周期延長為16，剩余執行量為[c0（tr）=1]，那么，由（2）式和（3）式算得的[δi]分別為6和4。如果將壓縮起點設定為[tr=4]，則剩余執行量為[c0（tr）=0]，由（2）式和（3）式算得的[δi]均為8。

無論是公式（2）和公式（3），算出的[δi]都不能保證是最早平滑插入時刻[δearliest]。后續文獻為計算[δearliest]做出了努力。文獻[10]研究的模型設定為任務對：即老任務[τi（Ci，Ti）]出讓帶寬給一個新任務[τj（Cj，Tj）]，而任何時間段為其它任務留下的帶寬都等于它們的使用率之和。該模型的最早平滑插入時刻計算式為

[δjest=t0+Ti—（n+1）Tj+（n+1）Cj-ci（tr）Ui.] ? ? ?（4）

公式（4）中，[t0]代表任務[τi]現行作業周期的起點時刻，[n]的計算則要分情況討論，與新任務在[Ti]前的處理器需求以及[ci（tr）]有關[10]。以圖1為例，設[tr=4]，則[n=ci（tr）/Cj=01=0]，代入（4）式得

[δjest=0+8—（0+1）4+（0+1）×1-012=6.]

與（2）式和（3）式算得的結果比對可知：（4）式得出的[δjest=6]要更早。

但是，（4）式對應的模型沒有考慮任務對以外的其它任務的搶占情況，換言之，其它任務并不一定要求所有時間段都需要等于其使用率之和的帶寬。只有全面考慮這一因素后，才能得出真正的[δearliest]。文獻[4]作了較全面考慮，提出了一個ESITforSNT （Earliest Smooth Insertion Time for Single New Task）算法，用于計算單個新任務插入時真正的[δearliest]。ESITforSNT算法也要分兩種情況計算[δearliest]，對于圖1設[tr=4]的話，有

[δearliest=tr+T1—（tr+T1—trTjTj）+Δ（tr，T1）+Δ（tr，T1）—CjCj（Tj—Cj）]

[=4+8—（4+8—44×4）+1+1—11（4—1）=5.] ? ? ? ? ? ? （5）

（5）式得出的[δearliest=5]是真正的最早平滑插入時刻，要比（4）式的[δjest=6]更早。式中的[Δ（tr，T1）]代表從[t=tr]到[t=T1]間的[Δ]檢查值[4]。更詳細的描述可參考文獻[4]。

4 算法的收斂問題

如果不考慮時間復雜度的因素，求取[δearliest]最樸素的方法是離線法[11]：先設[δearliest=tr]進行測試，如果插入新任務后系統不出現超截止期，則真正的[δearliest]就是[tr]，測試停止;否則設[δearliest=δearliest+tstep]再進行下一輪測試。這樣的測試可能要經過很多輪。文獻[11]中步長[tstep]取值為1。

這樣的測試方法的復雜度，主要與兩個因素有關：一是[tstep]的取值;二是每次測試時，要檢查的最大截止期點，即到底要檢查到什么時間點才算結束，也就是算法的收斂條件。

文獻[12]證明了一個準則：如果測試時某點截止期丟失，到下一輪的[tstep]取值至少不小于此時的[Δ]檢查值（可能大于1）。對于降低算法復雜度，這個準則顯然具有重要貢獻。

文獻[11]給出了算法的三個收斂條件：即試探到公倍點、試探到截止期對齊和試探到較小的剩余使用率。進一步，后續文獻證明了截止期丟失只可能出現在時間段[[d'min，d'max）]中[12-14]。[d'min]和[d'max]分別代表[tr]所處當前周期中，所有受壓任務的最早和最晚截止期點。這樣，每次測試時，只要從[d'min]試探到[d'max]即可。對于快速求取[δearliest]，這個結論具有重要意義。

5 結束語

關于實時任務帶寬轉讓問題，雖然依上所述取得了不錯的成果，但仍然有待深入研究。今后的研究思路主要有以下幾點：（1）需要壓縮多個任務進行帶寬轉讓時，有必要尋找更好的選擇策略以實現快速轉讓。（2）關于[δearliest]的求取，ESITforSNT算法只是針對單個新任務。多個新任務壓縮時，如何快速求取[δearliest]，仍然需要探索。（3）算法的收斂條件也需要繼續深入研究。例如，如果[d'max]數值太大，且在[[d'min，d'max）]間截止期點過多，也會延長獲得[δearliest]的測試時間。（4）如果作業的截止期點不是任務周期的結束點，或是干脆有的任務不是周期性的，那么，模型的建立和[δearliest]的求取將會更加復雜。

參考文獻：

[1] Liu C L，Layland J W.Scheduling algorithms for multiprogramming in a hard-real-time environment[J].Journal of the ACM，1973，20（1）：46-61.

[2] Buttazzo G C，Lipari G，Caccamo M，et al.Elastic scheduling for flexible workload management[J].IEEE Transactions on Computers，2002，51（3）：289-302.

[3] Qian G M.An earlier time for inserting and/or accelerating tasks[J].Real-Time Systems，2009，41（3）：181-194.

[4] Qian G M.The earliest smooth release time for a new task based on EDF algorithm[J].IEEE Access，2020，8：220595-220605.

[5] 錢光明，陳湘華，姜輝.實時任務的選擇性壓縮[J].湖南文理學院學報（自然科學版），2011，23（1）：67-70，80.

[6] 錢光明，楊揚.最晚截止期優先帶寬轉讓算法[J].計算機工程，2013，39（9）：137-141.

[7] 楊揚.基于EDF的帶寬轉讓算法研究[D].長沙：湖南師范大學，2014.

[8] Pillai P， Shin K G. Real-Time Dynamic Voltage Scaling for Low-Power[C].In Proc. 18th ACM Symposium， Operating Systems Principles， Banff， Canada， Aug.， 2001： 89-102.

[9] Casini D，Biondi A，Buttazzo G.Handling transients of dynamic real-time workload under EDF scheduling[J].IEEE Transactions on Computers，2019，68（6）：820-835.

[10] 錢光明，周垠宇.基于最早截止期優先算法的任務對帶寬轉讓研究[J].計算機工程，2016，42（4）：65-69.

[11] 錢光明，姜輝，陳湘華.實時任務調度算法最早可行時刻的求取模式[J].計算機工程，2012，38（4）：284-286.

[12] QIAN Guangming， SU Shen. Method to Evaluate Earliest Release Time of New Real-time Tasks[J]. Computer Engineering，2018， 44（12）： 62-67.

[13] 錢光明.基于最早截止期優先算法的過渡過程研究[J].計算機工程，2014，40（9）：55-58.

[14] 錢光明，梁麗穩.實時多任務帶寬轉讓的過渡過程研究[J].計算機工程，2017，43（12）：292-295，302.

【通聯編輯：代影】

收稿日期：2021-03-20

基金項目：長沙市科技局資助項目（ZD1802001）

作者簡介：錢光明，男，教授，主要研究方向為嵌入式和實時系統;鄧朝豐，男，在讀研究生。