一種基于任務計算密度優先的改進EDF實時調度算法研究

李 贊，黃燕挺

（電子科技大學中山學院，中山 528400）

0 引言

實時系統是采用實時調度算法處理具有時效限制的多任務處理系統。每個任務必須在規定的時間內處理完。計算機的硬件資源有限，處理能力有限，如果多個實時任務的計算需求超出了處理器能力上限，則發生任務過載情況，造成無法預料的后果。

實時任務分為周期實時任務和非周期實時任務，調度算法又分為搶占式與非搶占式調度算法，經典的調度算法中，EDF（截止時間優先）常被應用于非周期實時任務，LLF（最低松馳度優先）算法應用于周期實時任務，實時調度算法多數以動態計算的優先級來切換任務。經典的的是EDF（最早截止時間優先）和LLF（最低松馳度優先）算法，但是EDF算法存在條件的不完備性，LLF算法存在邏輯設計缺陷，在不添加必要約束條件情況時算法是難以實現的。雖然也有一些算法通過添加某些約束條件來改進EDF和LLF算法，甚至有一些算法嘗試綜合兩種算法來實現實時調度，但是這些實時調度算法并沒有明確算法的一些基本要素，本文首先分析了兩種算法的不足之處，并指出實時調度算法須具有的算法要素，并提出了一個改進的EDF算法用于周期性實時任務的調度。

1 經典EDF算法與LLF調度算法的問題

經典的EDF（截止時間優先）算法常被應用于非搶占式非周期實時任務和搶占式實時任務，LLF（最低松馳度優先）算法被應用于周期實時任務，但是參考文獻對這兩個算法的描述都存在不完備因素，缺少必要的約束條件，并且算法也沒有明確調度算法執行的時機，因此很難轉化為實際算法。

1.1 EDF算法條件的不完備性

EDF（Earliest Deadline First）根據任務的截止時間確定任務的優先級，任務的截止時間越早，其優先級越高。EDF（最早截止時間優先）算法即可用于非搶占式非周期實時任務，也可應用于周期實時任務，是一種搶點式的調度算法，該算法的思想是從就緒任務隊列中選取截止時間早的任務執行。經典EDF算法有缺少兩個條件：第一是調度算法的執行時機，調度程序無法實現每時每刻的運行，第二是如果存在多個截止時刻相同的任務又如何處理，但是這兩個缺失的條件是容易解決的。

1.2 LLF算法存在的設計邏輯問題

最低松馳度優先算法LLF缺失兩個條件：第一何時執行調度算法，第二松馳度相同時的任務如何處理，LLF算法缺乏調用的時機的條件，例如下面的調度由于時機選擇的不同，造成任務的調度產生隨意性。圖1表示兩種采用LLF算法由于調度時機選擇不同造成不同的調度過程。

圖1 實時任務調度選擇時機造成調度差異

即使補全了缺失條件LLF算法也無法實施，這是因為LLF算法存在邏輯問題，接下來分析其算法邏輯的問題。松馳度計算方法為：任務松馳度=任務完成截止時刻點-當前時刻點-任務還剩余的時長。假設前時刻點為，一個實時任務設當任務還剩余執行的時長為，任務松馳度為τ，任務完成截止時刻點為。則：=--，當該任務被系統執行了一個較短的時長Δ，任務沒有結束，則時刻點變為+Δ，而任務剩余的時長為-Δ，新時刻點任務松馳度：1=-（+Δ）-（-Δ），由此可得1=，任務在經過一個較短的執行時長Δ后的松馳度保持不變仍為。所以一個實時任務A執行過程中，松馳度的值保持不變，與執行的時長Δ無關，而等待的任務B的松馳度則減小，兩個任務松馳度直線變化情況如圖2所示。

圖2 LLF算法中實時任務A和B的構馳度變化

圖2中兩個任務的松馳度直線有相交點，該相交點是LLF算法邏輯問題所在。任務A與任務B松馳度值相同時，如果A繼續執行則松馳度值保持不變，B任務松馳度會減小，任務B因為松馳度小于A則算法會搶占正在執行的任務A，很快松馳度顛倒后A又要搶占B，這種任務的反復切換會發在極短的時間間隔，從而產生了選擇抖動，其實是無法進行選擇，這種選擇抖動顯然是邏輯錯誤的，這就是LLF算法思想的缺陷。一旦出現兩個或多個任務松弛度相等的情況，將會出現這幾個任務之間的頻繁任務切換，這種現象又稱為競爭抖動。

LLF算法目的是解決調度問題，如果切換時間片無窮小，則切換次數會變得無窮多，選擇悖論會使得LLF算法無法實現。因此LLF算法必須要添加限制條件才可以實施，例如指定一個間隔時長，在每個間隔時長結束后再執行LLF算法來選取要執行的任務，這是多數改進LLF算法的實現方法。即使指定了LLF算法的間隔時長，還是會存在松馳度值相同的任務，仍然要進一步確定被選定的任務。

2 改進的EDF算法設計

2.1 實時調度算法要件

一個可實施的實時調度算法須解決的問題：①執行調度算法的時機。②實現就緒任務的排序。③判斷系統硬件能力是否能夠滿足實時任務對截止時間的要求。參考文獻［1］中LLF算法它選取的時間點依據不足。實時系統中每個任務具有兩個固定的屬性：①就緒時間點。②完成截止時間點。任務的這兩個屬性是固定的。在經典文獻［1］中，單處理機情況下，假定系統中有個周性期的硬實時任務HRT，任務處理時長為C，周期時長表示為P，實時系統中處理能力必須滿足下面的限制條件才是可調度的：

2.2 改進的EDF算法設計原理

非周期實時任務的截止時間無特定規則，例如一個實時任務相較其它任務有特別長的截止時間，則該任務在初始調度時是可以忽略的，因此很難進行量化討論，而系統存在兩個調度算法的執行時機，①新任務到達時刻。②當前任務執行結束，添加這兩個調度時機的EDF算法可適用非周期實時任務調度。對于具有若干周期實時任務的系統，每個任務的需求計算密度T可由其需要的系統處理時長C除以任務允許的響應結束時長P，P=截止時刻-到達時刻，每個實時任務相對于系統的需求計算密度由下式得出：

為了使硬件條件滿足實時任務的需求，所有任務的計算密度要滿足公式（1），所有實時任務的需求計算密度之和須小于1。假設系統存在有個周期實時任務，其總的需求計算密度之和為＜1，只要選取特定長的時間段，將每個周期任務看成是均勻分布的計算需求，所有任務需要的計算總時長小于該時間段長度，如果系統還能滿足每個實時進程的截止時間的條件，系統只要保持滿負荷處理，假設調度粒度無限細小，則每個任務的執行將被無限細分，只要保持調度分配在任務間的比率與其計算密度相同則所有任務都可順利執行，因為總需求計算密度小于1，即小于系統滿負荷能力，因此調度方案必存在。假設有一個新的周期任務X其計算密度為欲加入系統中，如果+＞1，即總需求計算密度大于1，即表示系統的計算能力小于任務總的計算需求，則任務X加入到系統會使系統超載。

由上述討論可知任務的需求計算密度Ti是任務的重要特征，體現任務在實時調度算法中的地位，經典的EDF算法滿足實時任務截止時間的要求條件，本文提出將EDF算法結合計算密度參數，首先對任務的截止時間進行排序，然后求出每個任務的需求計算密度，再依據計算密度值繼續排序，并選取隊首的作業執行。實際的調度算法無法在執行粒度上無限細小，為了減少不必要的任務切換，調度算法執行的時機被明確為兩個：第一是新任務到達時刻，第二是當前任務結束時刻。為方便說明算法的實現，設計下面的任務控制塊：

2.3 改進的任務隊列的構建與任務調度

改進的EDF算法支持周期實時任務的動態增加與刪除，下面分析算法對周期實時任務隊列的管理流程，在新任務到達和當前任務執行結束時運行調度算法，算法首先根據截止時間對任務隊列進行排序，對相同截止時間的任務計算其計算密度并進行減序排列，具有相同的截止時間和相同計算密度的任務則按入隊順序排列，排序完成后取出隊首任務執行。有新增周期任務時只需對任務隊列進行計算密度累加，可判斷系統處理能力是否滿足任務隊列需求，從而決定是否允許新任務的加入，系統處理流程如圖3所示。

圖3 基于計算密度的改進EDF周期實時調度算法流程

通過上圖的調度流程，周期實時處理系統采用改進的EDF算法能夠有效管理就緒任務隊列，可以實現對周期實時任務的調度，運行條件完備，邏輯設計正確，避免了LLF算法產生的競爭抖動現象，具有較高的實施價值。

3 結語

本文分析了實時系統中經典EDF算法的不完備以及LLF算法的邏輯缺陷，明確指出實時任務系統算法的一些要素，并提出了一種改進的EDF實時調度算法，該算法消除了舊EDF算法中不完備的條件，通過引入需求計算密度討論了實時任務調度的理論可行性。算法的創新點有三點：①明確了調度算法執行的時機。②用需求計算密度可動態判斷系統條件是否滿足實時任務需求。③實現了就緒任務隊列的排序方法。最終給出了改進EDF調度算法流程，它能避免LLF算法產生的競爭抖動現象，能有效發揮硬件資源效率，可實施性好，能夠很好地處理周期性實時任務，具有較高的價值。