引言

隨著嵌入式實時操作系統應用的不斷深入，多個實時任務并發執行，再加上任務之間不停地動態切換，這對任務調度算法提出了較高的要求。實時操作系統中各個任務的優先級是不同的，而且經常會遇到超負荷的情況.。在這種超載情況下，使任務集內各任務滿足各自的時限，嵌入式操作系統必須保證在確定的時間內對事件進行處理，因此必須要有一個良好的任務調度算法。周期任務和非周期任務是實時嵌入式系統中的常見任務類型，系統實時任務調度策略主要包括時間驅動調度策略、優先級驅動調度策略。常見的動態優先級調度算法有最早截止期優先調度算法和最小空閑時間優先算法、單調速率調度算法和最大價值優先算法等。

實時系統的任務按產生請求的頻率可分為周期性任務與非周期性任務：周期性任務按照固定的請求間隔持續地產生請求，不同的任務請求間隔不一定相同。 非周期性任務在任意一段時間間隔內可能產生不定數量的請求。按任務優先級分配方式可分為靜態優先級任務和動態優先級任務。

1）固定優先級調度算法

在實時調度算法中，固定優先級調度算法事先根據任務的屬性，如任務的周期、截止期限等為系統中的所有任務靜態分配一個優先級。當任務的截止期限等于周期時，提出了RMS調度算法，它根據任務的執行周期長短的不同來決定優先級，即任務的周期越小優先級越高，任務的周期越大優先級越低。以RMS為代表的固定優先級調度算法，一方面不僅具有運行時間開銷小和易于實現的優點，而且在系統超載情況下，仍然可以保證高優先級的任務得到執行；但另一方面卻是不能充分地利用系統資源。

2）動態優先級調度算法

在實時調度算法中，動態優先級調度算法根據任務資源需求的變化以及任務的屬性，如任務周期、截止期限等動態地決定任務的優先級。當任務的截止期限等于周期時，提出了EDF調度算法，該算法根據就緒隊列中任務的截止期限分配優先級，距離絕對截止期限的最近的任務具有最高的優先級，即任務的絕對截止期限越小優先級越高，任務的絕對截止期限越大優先級越低。以EDF為代表的動態優先級調度算法，一方面可以充分地利用系統的資源；但是另一方面在系統負荷嚴重超載時，系統性能很不穩定，導致大多數任務在截止期限到來之時仍無法滿足。

3）靜態優先調度算法與動態優先調度算法的比較

靜態調度是指系統脫機地進行調度可行性分析后生成一個可調度表，在運行的過程中，調度表中的信息不再發生任何變化。該類調度算法假定系統實時任務的屬性是提前已知的并且在執行過程中很少發生變化，特別適合于對那種確定問題的求解，具有較好的可預測性。

單調速率調度算法(Rate Monotonic Algorithm, RM)

單調速率調度算法是一種被廣泛使用的調度算法, 并且已被證明是一種最佳的靜態優先級算法。單調速率調度（RMS）算法是C.L.Liu和J.W.Layland在1973年引入提出的一種基于周期和多任務的靜態優先級可搶占調度算法。RMS是針對周期任務的優先級調度算法，當任務的截止時間等于其周期時，RMS算法已被證明是靜態最優的調度算法。

當較低優先級的進程正在運行并且較高優先級的進程可以運行時，較高優先級進程將會搶占低優先級。在進入系統時，每個周期性任務會分配一個優先級，它與其周期成反比，即周期越短，優先級越高；周期越長，優先級越低。這種策略背后的理由是：更頻繁地需要 CPU 的任務應分配更高的優先級。此外，單調速率調度假定：對于每次 CPU 執行，周期性進程的處理時間是相同的。也就是說，在每次進程獲取 CPU 時，它的 CPU 執行長度是相同的。

假設有兩個進程 P1 和 P2。P1 和 P2 的周期分別為 50 和 100，即 ρ1 = 50 和 ρ2= 100。P1 和 P2 的處理時間分別為 t1 = 20 和 t2 = 35。每個進程的截止期限要求，它在下一個周期開始之前完成 CPU 執行。
首先，P1 開始，并在時間 20 完成 CPU 執行，從而滿足第一個截止期限。P2 在這點開始運行，并運行直到時間 50。此時，它被 P1 搶占，盡管它的 CPU 執行仍有 5ms 的時間。P1 在時間 70 完成 CPU 執行，在這點調度器恢復 P2。P1 在時間 75 完成 CPU 執行，也滿足第一個截止期限。然后，系統一直空閑直到時間 100，這時，P1 再次被調度。
單調速率調度可認為是最優的，因為如果一組進程不能由此算法調度，它不能由任何其他分配靜態優先級的算法來調度。

最早截止時間優先(Earliest DeadlineFirst, EDF)

最早截止時間優先EDF算法是非常著名的實時調度算法之一。EDF調度算法是單處理器環境下調度性能最優的一種動態調度系統任務的算法。EDF調度算法的優先級是以所調度任務的截止期與當前時刻的差值來確定的差值越小證明任務的截止期越早，與其他差值大的任務相比優先級就越高，越需優先執行避免錯過任務截止期而導致任務夭折。因此，采用EDF調度算法可以保證當前離截止期最近的任務獲得系統資源和控制權，優先進行調度。EDF調度算法最大的優點是大幅度提升處理器的利用率，采用EDF調度算法進行調度時，處理器的利用率可以達到最大值。 但EDF調度算法在進行任務調度時系統開銷較大，且任務調度過程中無法對系統負載情況進行量化判斷，無法應對系統高負載情況下的任務調度問題。EDF算法在調度過程中存在任務錯失截止期的情況，進而影響其他等待調度任務的正常調度，致后續多個任務錯失截止期而夭折。在系統超負載的情況下調度算法會導致系統任務調度的成功率大幅度降低，影響嵌入式系統的實時調度性能。

在每一個新的就緒狀態，調度器都是從那些已就緒但還沒有完全處理完畢的任務中選擇最早截止時間的任務，并將執行該任務所需的資源分配給它。在有新任務到來時，調度器必須立即計算EDF，排出新的定序，即正在運行的任務被剝奪，并且按照新任務的截止時間決定是否調度該新任務。如果新任務的最后期限早于被中斷的當前任務，就立即處理新任務。按照EDF算法，被中斷任務的處理將在稍后繼續進行。該算法的思想是從兩個任務中選擇截至時間最早的任務，把它暫作為當前處理任務，再判斷該任務是否在當前周期內，若不在當前周期內，就讓另一任務暫作當前處理任務，若該任務也不在當前周期內，就讓CPU空跑到最靠近的下一個截至時間的開始，若有任務在該周期內，就判斷該任務的剩余時間是否小于當前截至時間與當前時間的差,若小于，則讓該任務運行到結束。否則，就讓該任務運行到該周期的截止時間，就立即搶回處理器，再判斷緊接著的最早截至時間，并把處理器給它,做法同上，如此反復執行。

最小空閑時間優先算法(Least Slack First，LSF)

最小空閑時間優先LSF算法結合任務執行的緩急程度來給任務分配優先級。任務所剩的空閑時間越少，就越需要盡快執行。最小空閑時間優先調度算法改進了EDF算法的性能，算法中任務優先級由任務空閑時間片數值來決定， 即任務截止時間與剩余執行時間之差，空閑時間片數值越小，任務優先執行的級別越高，LSF調度算法通過緊急任務優先執行策略一定程度上解決了EDF算法存在的問題，但調度算法存在任務調度頻繁搶占問題，增加了系統的開銷同時也降低了實時系統的性能。