動態(tài)優(yōu)先級調度算法的特點及實現(xiàn)

《動態(tài)優(yōu)先級調度算法的特點及實現(xiàn)》由會員上傳分享，免費在線閱讀，更多相關內容在工程資料-天天文庫。

1、WORD格式可編輯動態(tài)優(yōu)先級調度算法的特點和實現(xiàn)摘要：本文從實時操作系統(tǒng)的調度功能入手，簡單介紹了實時調度算法的分類和種類，并主要討論動態(tài)優(yōu)先級調度算法的特點和實現(xiàn)。接下來本文介紹了兩類動態(tài)優(yōu)先級調度算法：截止時間優(yōu)先調度算法和最短空閑時間優(yōu)先調度算法的定義及實現(xiàn)方式。然后將靜態(tài)調度與動態(tài)調度進行比較，突出動態(tài)優(yōu)先級調度的特點，同時指出其可能導致的優(yōu)先級反轉、死鎖等不良后果。然后具體介紹了優(yōu)先級反轉的定義以及解決該問題的兩種方案：采用優(yōu)先級繼承協(xié)議與采用優(yōu)先級天花板協(xié)議。關鍵詞：嵌入式系統(tǒng)動態(tài)優(yōu)先級調度算法優(yōu)先級反轉在嵌入式的實時操作系統(tǒng)中，調度是一個非常重要的功能，用

2、來確定多任務環(huán)境下任務執(zhí)行的順序和在獲得CPU資源后能夠執(zhí)行的時間長度。操作系統(tǒng)通過一個調度程序（Scheduler）來實現(xiàn)調度功能。調度程序以函數的形式存在，用來實現(xiàn)操作系統(tǒng)的調度算法。調度程序本身并不是一個任務，而是一個函數調用，可在內核的各個部分進行調用。調度程序是影響系統(tǒng)性能（如吞吐率、延遲時間等）的重要部分。在設計調度程序是、時，通常要綜合考慮如下因素：●CPU的使用率（CUPutilization）；●輸入/輸出設備的吞吐率；●響應時間（responsivetime）；●公平性；●截止時間。這些因素之間具有一定的沖突性。比如可通過讓更多的任務處于就緒狀態(tài)來提

3、高CPU的使用率，但這顯然會降低系統(tǒng)的響應時間。因此，調度程序的設計需要優(yōu)先考慮最重要的需求，然后在各種因素之間進行折中處理?？梢园岩粋€調度算法（SchedulingAlgorithms）描述為是在一個特定時刻用來確定將要運行的任務的一組規(guī)則。從1973年Liu和Layland開始關于實時調度算法的研究工作以來（1973年，Liu和Layland發(fā)表了一篇名為“SchedulingAlgorithmsforMultiprogramminginaHardReal-TimeEnvironment”的論文），相繼出現(xiàn)了許多調度算法和方法。對于大量的實時調度方法而言，存在著以下

4、幾類主要的劃分方法：●離線（off-line）和在線（on-line）調度；●搶占（preemptive）和非搶占（non-preemptive）調度；●靜態(tài)（static）和動態(tài)（dynamic）調度；專業(yè)知識分享WORD格式可編輯●最佳（optimal）和試探性（heuristic）調度。以下主要討論動態(tài)優(yōu)先級調度算法的特點和實現(xiàn)。一、動態(tài)優(yōu)先級調度算法的定義優(yōu)先級驅動策略指按照任務的優(yōu)先級的高低確定任務的執(zhí)行順序。根據任務優(yōu)先級的確定時機，調度算法分為靜態(tài)調度和動態(tài)調度兩類。在靜態(tài)調度算法中，所有任務的優(yōu)先級在設計時就確定下來了，且在運行過程中不會發(fā)生變化（如RM

5、S）。在動態(tài)調度算法中，任務的優(yōu)先級則在運行過程中確定，并可能不斷地發(fā)生變化（如EDF）。靜態(tài)調度算法適用于能夠完全把握系統(tǒng)中所有任務及其時間約束（如截止時間、運行時間、優(yōu)先順序和運行過程中的到達時間）特性的情況。靜態(tài)調度比較簡單，但是缺乏靈活性，不利于系統(tǒng)擴展；動態(tài)調度有足夠的靈活性來處理變化的系統(tǒng)情況，但是需要消耗更多的系統(tǒng)資源。在動態(tài)調度中，任務的優(yōu)先級可根據需要進行改變，也可能隨著時間按照一定的策略自動發(fā)生變化。二、動態(tài)優(yōu)先級調度算法的分類1、截止時間優(yōu)先調度算法RMS調度算法（Rate-MonotonicSchedulingalgorithm，比率單調調度算法

6、）的CPU使用率比較低，在任務比較多的情況下，可調度上限為68%。Liu和Layland又提出了一種采用動態(tài)調度的、具有更高CPU使用率的調度算法——截止時間優(yōu)先調度算法EDF（EarliestDeadlineFirst）。在EDF中，任務的優(yōu)先級根據任務的截止時間來確定。任務的絕對截止時間越近，任務的優(yōu)先級越高；任務的絕對截止時間越遠，任務的優(yōu)先級越低。當有新的任務處于就緒狀態(tài)時，任務的優(yōu)先級就有可能需要進行調整。同RMS一樣，Liu和Layland對EDF算法的分析也是在一系列假設的基礎上進行的。在Liu和Layland的分析中，EDF不要求任務為周期任務，其他假設

7、條件與RMS相同。例如在系統(tǒng)中有3個進程需要執(zhí)行，分別為P1、P2、P3，其執(zhí)行需花費的時間各為1、2、1l，而執(zhí)行周期為3、5、4，在時間單位4時，因為P1的執(zhí)行時限為6，P2的執(zhí)行時限為10，P3的執(zhí)行時限為8，所以P1的優(yōu)先級最高，進程切換到P1：在時間單位6時，因為P1的執(zhí)行時限為9，P2的執(zhí)行時限為10，P3的執(zhí)行時限為12，所以P1的優(yōu)先級最高，進程又再次切換到P1，而非P2：在時間單位7時，因為P1的執(zhí)行時限為12，P2的執(zhí)行時限為10，P3的執(zhí)行時限為12，所以P2的優(yōu)先級最高，進程切換到P2。后續(xù)流程以此類推。專業(yè)知識分