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

錢光明 鄧朝豐

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

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

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

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

1 引言

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

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

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

2 轉讓任務的選擇

一個實時系統(tǒng)中，往往有多個任務正在運行。當選擇不同的現(xiàn)行任務進行壓縮時，導致的截止期丟失情況可能會不一樣[5-7]。圖1，假定EDF調度的任務集中，共有兩個現(xiàn)行任務：[τ0（4，8）]和[τ1（4，8）]，它們的帶寬均為1/2，帶寬之和為1，即系統(tǒng)已滿負荷運行。如果在[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]進一步對這一思想進行深入研究，提出了一個最晚截止期優(yōu)先的帶寬轉讓算法：在[tr]所處的周期中，在可壓縮任務集內(nèi)，先壓縮當前作業(yè)截止期最晚的任務。這樣做往往可以取得非常滿意的效果。因為截止期最晚的任務往往是剩余執(zhí)行量和剩余帶寬較大的任務[6]，可以立即出讓較大比例的帶寬。

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

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

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

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

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

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

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

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

公式（4）中，[t0]代表任務[τi]現(xiàn)行作業(yè)周期的起點時刻，[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]進行測試，如果插入新任務后系統(tǒng)不出現(xiàn)超截止期，則真正的[δearliest]就是[tr]，測試停止;否則設[δearliest=δearliest+tstep]再進行下一輪測試。這樣的測試可能要經(jīng)過很多輪。文獻[11]中步長[tstep]取值為1。

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

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

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

5 結束語

關于實時任務帶寬轉讓問題，雖然依上所述取得了不錯的成果，但仍然有待深入研究。今后的研究思路主要有以下幾點：（1）需要壓縮多個任務進行帶寬轉讓時，有必要尋找更好的選擇策略以實現(xiàn)快速轉讓。（2）關于[δearliest]的求取，ESITforSNT算法只是針對單個新任務。多個新任務壓縮時，如何快速求取[δearliest]，仍然需要探索。（3）算法的收斂條件也需要繼續(xù)深入研究。例如，如果[d'max]數(shù)值太大，且在[[d'min，d'max）]間截止期點過多，也會延長獲得[δearliest]的測試時間。（4）如果作業(yè)的截止期點不是任務周期的結束點，或是干脆有的任務不是周期性的，那么，模型的建立和[δ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] 錢光明，楊揚.最晚截止期優(yōu)先帶寬轉讓算法[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] 錢光明，周垠宇.基于最早截止期優(yōu)先算法的任務對帶寬轉讓研究[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] 錢光明.基于最早截止期優(yōu)先算法的過渡過程研究[J].計算機工程，2014，40（9）：55-58.

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

【通聯(lián)編輯：代影】

收稿日期：2021-03-20

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

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