實時調度是針對嵌入式系統特點的一種任務調度策略，旨在提高系統性能。RTOS系統在生產生活中廣泛應用，其正確性不僅取決于程序邏輯，還取決于結果產生的時效性。實時系統可分為軟實時和硬實時兩類，后者對響應時間有嚴格要求。實時調度包括單處理器、多處理器和分布式處理器等多種形式，其中動態調度如EDF和LLF能夠實現100%的處理器利用率。
簡介
實時系統在指定響應時間內提供所需服務水平，其正確性不僅涉及程序邏輯正確性，還包括結果產生的時間。硬實時系統要求確保最壞情況下的服務時間，而軟實時系統則是從統計學角度看，任務能夠得到確保的處理時間，但違反截止期限不會導致嚴重錯誤。實時調度可分為靜態調度和動態調度，以及單處理器、集中式多處理器和分布式處理器調度。此外，還有搶占式調度和不可搶占式調度。
分類
RTOS系統按照實時性要求分為軟實時和硬實時兩類。硬實時系統要求無論何種情況下均需滿足響應時間截止期限，如航天領域的宇宙飛船控制系統。軟實時系統則從統計學角度來看待任務處理時間和響應時間，如實時多媒體系統。根據調度表建立和可調度性分析的方式，實時調度還可分為靜態調度和動態調度。靜態調度通常基于RMS算法，而動態調度則以EDF和LLF為主。按系統分類，實時調度可分為單處理器調度、集中式多處理器調度和分布式處理器調度。按任務是否可搶占，可分為搶占式調度和不可搶占式調度。
單處理器實時調度
單處理器實時調度的問題描述為，任務集S中各任務的周期、執行時間和截止日期均為已知，且任務可被搶占。CPU利用率U不超過1是任務集可調度的前提條件。RMS（Rate-Monotonic Scheduling）調度算法是一種靜態固定優先級分配的調度算法，適用于單處理器下的最優靜態調度。RMS算法通過計算系統資源利用率來進行任務可調度性分析，算法簡單有效。然而，RMS算法的處理機利用率較低，在最壞情況下不超過70%，這成為許多實時應用的限制。動態調度算法如EDF和LLF能夠實現100%的處理器利用率。
RMS調度算法
RMS算法的任務模型為周期性任務，優先級與其周期成反比。優先級高的任務具有更高的優先權。可調度性分析可通過計算系統資源利用率來進行。RMS算法已被證明是靜態最優調度算法，但在一般情況下，對于隨機的任務集約有88%的處理器利用率。非周期任務的調度可以通過延遲服務器算法或隨機服務器算法進行，這兩種算法都將非周期任務轉化為周期任務后再進行調度。EDF算法是一種動態調度算法，其優先級根據任務的截止時間動態分配。EDF算法已被證明是動態最優調度，且是充要條件。LLF算法也是動態調度算法，其優先級根據任務的空閑時間動態分配。EDF和LLF算法在每個調度時刻都需要計算任務的截止時間或空閑時間，因此開銷較大，不易實現。
多處理器實時調度
多處理器實時調度可分為靜態調度和動態調度。靜態調度包括基本調度（BS）、可搶占調度（PS）和廣義調度（GS）。PS和GS的最小計算時間相等，且PS在實際中可實現。動態調度的目標是對變化的環境做出快速反應。在l-c空間中，任務可以按EDF和LLF調度算法調度，但由于多處理器下EDF和LLF不是最優算法，因此在動態調度中不存在最優算法。
分布式實時調度
分布式實時調度算法可分為兩類：以RMS為基礎的廣義RMS調度（GRMS）和以風車調度Sr為基礎的DSr調度。GRMS將RMS應用于分布式實時系統，對RMS的概念進行了擴展，并引入了一些新概念。DSr調度算法基于分布式任務集合和網絡節點上的任務執行時間，選擇最小總密度的劃分基作為系統的劃分基礎。
參考資料 >
實時調度概念及其算法詳解.CSDN博客.2024-09-14
實時調度.博客園.2024-09-14
實時調度理論.中國科學技術大學.2024-09-14