神經網絡模型的壓縮與量化技術
時間：2025-08-25 來源：華清遠見
一、概述
嵌入式系統中的任務調度算法是實時操作系統（RTOS）的核心功能之一，負責決定何時執行哪個任務，以確保系統資源的高效利用和實時性需求的滿足。而現如今常用的實時調度算法有三種：單調速率調度（RMS），最早截止時間優先（EDF），最低松弛時間優先（LLF）。這也是本篇文章要詳細講一講的東西，當然這里提一嘴與其對應的目前常用的非實時調度算法，有以下幾種：最低松弛時間優先（LLF），短作業優先（SJF），時間片輪轉（RR），優先級調度。
當然也要詳細講一講不同的調度算法的選擇，我們開發人員會因為系統的實時性需求、任務特性（如周期性和非周期性）、資源限制等因素，選擇合適的調度算法。
二、詳解
1. 單調速率調度（RMS）1)是什么
單調速率調度（RMS）是1973年Liu和Layland提出來的，它是一種經典的靜態優先級實時任務調度算法，通過將任務的優先級與周期建立單調遞減關系，確保高優先級任務能夠及時完成。就目前看來單調速率調度已經成為在單處理器環境下最優的靜態優先級調度算法，目前，廣泛應用于航空航天、工業控制、醫療設備等對實時性要求極高的領域。
2)模型
RMS調度算法基于嚴格的周期性任務模型，每個任務定義為三元組(Ti, Ci, Di)，其中：
Ti：任務的周期，表示任務請求的間隔時間
Ci：任務的執行時間，指處理器在無中斷情況下執行該任務所需的時間
Di：任務的截止時間，通常等于周期Ti，即任務必須在下一個周期開始前完成
這些任務必須滿足以下基本約束條件：0 ≤ Ci ≤ Ti ≤ Di，確保任務執行時間不超過周期，并且有明確的截止時間要求。
3)調度思想
RMS的核心思想是任務的優先級與周期成反比，周期越短，優先級越高。這種單調遞減的優先級分配策略保證了系統中執行頻率最高的任務能夠獲得最高的執行權限，從而滿足其嚴格的實時性要求。
具體而言，調度器遵循以下原則：
1.當高優先級任務到達時，可以搶占正在執行的低優先級任務
2.任務一旦開始執行，必須連續執行直到完成或被更高優先級任務搶占
3.任務在周期起點被激活，周期性地重復執行
4)分配機制
RMS采用靜態優先級分配，即在系統啟動或任務創建時確定優先級，之后不再改變。優先級分配規則如下：
將所有任務按周期長短排序：T1 < T2 < T3 < ... < Tn
為周期最短的任務T1分配最高優先級
依次為周期較長的任務分配較低優先級
這種優先級分配機制確保了在任何時刻，處理器總是執行當前可用的最高優先級任務，從而在資源受限的情況下最大化系統實時性。
5)調度過程
RMS調度過程可以分為以下幾個關鍵步驟：
任務激活：在每個周期的起點，任務被激活并加入就緒隊列。
優先級比較：調度器檢查就緒隊列中的所有任務，選擇優先級最高的任務執行。
任務執行：選定的高優先級任務開始執行，執行時間固定。
搶占機制：如果有更高優先級的任務到達，可以搶占當前正在執行的任務。
任務完成：任務執行完畢后，調度器繼續選擇下一個最高優先級的任務執行。
這種可搶占的靜態優先級調度機制確保了高優先級任務能夠及時獲得處理器資源，滿足其嚴格的實時性要求。
6)優缺點
優點：
可預測性強：靜態優先級分配使得調度行為可預測，便于系統設計和驗證。
實現簡單：無需動態調整優先級，降低算法復雜度和運行時開銷。
理論支持充分：通過Liu & Layland定理提供嚴格的可調度性分析方法。
確定性高：在滿足可調度性條件時，能夠保證所有任務在截止時間內完成。
抗干擾能力強：高優先級任務能夠及時響應中斷，避免關鍵任務被延遲。
缺點：
利用率上限低：當任務數n→∞，利用率上限趨近于69.3%，導致處理器資源利用率受限。
饑餓問題：低優先級任務可能因頻繁被高優先級任務搶占而長時間無法執行。
僅適用于周期性任務：無法直接處理非周期性或動態變化的任務。
對任務參數敏感：任務參數(周期、執行時間)的微小變化可能導致整個任務集的可調度性分析失效。
缺乏靈活性：靜態優先級在任務執行過程中不可調整，難以適應動態變化的系統需求。
2.最早截止時間優先（EDF）
1) 是什么
最早截止時間優先調度算法（Earliest Deadline First, EDF）是一種基于動態優先級的實時任務調度策略，其核心思想是根據任務的截止時間進行優先級排序，確保截止時間最早的高優先級任務能夠優先獲得處理器資源。與傳統的靜態優先級調度算法（如速率單調調度RMS）不同，EDF能夠靈活適應任務截止時間的變化，為實時系統提供更高效的資源利用和更可靠的截止時間保證。本文將從算法原理、實現機制、優缺點分析及實際應用案例等方面，系統闡述EDF調度算法的完整技術框架。
2) 核心思想
最早截止時間優先調度算法的核心思想是：在調度時，優先選擇截止時間最早的任務進行執行。這種動態優先級分配機制使得調度器能夠根據任務的緊迫程度實時調整執行順序，特別適合處理截止時間變化或任務到達時間不固定的實時系統。
EDF算法的數學基礎是任務的松弛度（Slack）計算，即松弛度=截止時間-當前時間-剩余執行時間。算法總是選擇松弛度最小（即截止時間最近）的任務執行，從而最大限度地減少任務錯過截止時間的風險。
3) 任務模型
EDF算法適用于以下類型的任務模型：
周期性任務：具有固定周期和執行時間的任務，如傳感器數據采集、控制系統等。
非周期性任務：到達時間不確定、執行時間可變的任務，如事件觸發的報警處理。
混合任務集：同時包含周期性和非周期性任務的系統，EDF能夠統一處理。
每個任務在EDF系統中通常被描述為四元組(Ti, Ai, Ci, Di)，其中：
Ti：任務的到達時間或周期（對于周期性任務）
Ai：任務的激活時間
Ci：任務的執行時間
Di：任務的截止時間
對于周期性任務，通常Di = Ai + Ti，即任務必須在下一個周期開始前完成。
4) 調度原則
EDF算法遵循以下調度原則：
動態優先級分配：任務的優先級由其截止時間決定，截止時間越早，優先級越高。
搶占式調度：當新任務的截止時間早于當前正在執行任務的截止時間時，可立即搶占處理器資源。
任務就緒隊列管理：系統維護一個就緒隊列，隊列按任務截止時間從早到晚排序。
時間敏感性：調度決策基于實時計算，確保系統能夠及時響應任務截止時間的變化。
與靜態優先級調度算法（如RMS）相比，EDF的最大優勢在于其能夠適應任務截止時間的動態變化，而無需在任務創建時確定固定優先級。
5) 實現的機制
① 就緒隊列管理
EDF算法的關鍵實現機制是高效的就緒隊列管理。就緒隊列按照任務截止時間的早晚進行排序，確保調度器能夠快速選擇具有最早截止時間的任務。
就緒隊列通常采用以下數據結構實現：
優先隊列（堆結構）：使用最小堆（Min-Heap）存儲任務，堆頂始終是截止時間最早的任務。
時間輪（Time-W輪）：適用于具有固定周期的任務，通過輪轉機制快速定位下一個到期任務。
鏈表結構：對于任務數量較少的系統，可使用簡單鏈表按截止時間排序。
就緒隊列的操作包括：
任務插入：當新任務到達或周期性任務激活時，將其插入隊列并按截止時間排序。
任務刪除：當任務完成執行或被阻塞時，從隊列中移除。
隊列更新：在時鐘中斷或任務狀態變化時，更新隊列中的任務排序。
② 搶占條件與上下文切換
在搶占式EDF實現中，調度器需要確定何時觸發搶占：
任務到達搶占：當新任務到達時，如果其截止時間早于當前正在執行任務的截止時間，則立即搶占。
時鐘中斷搶占：在固定時間間隔（如時鐘嘀嗒）觸發調度檢查，重新評估任務優先級。
任務完成搶占：當前任務完成后，調度器立即選擇隊列中下一個最早截止時間的任務執行。
搶占過程中，系統需要執行上下文切換操作，保存當前任務的寄存器狀態（PCB）、程序計數器和棧指針等信息，并加載新任務的上下文。上下文切換的開銷是EDF算法的一個重要考量因素，尤其在高頻率搶占場景中。
③ 動態優先級調整
EDF算法的核心在于動態調整任務優先級，這主要體現在以下幾個方面：
任務到達時的調整：新任務到達后，立即計算其截止時間并插入就緒隊列的適當位置。
任務執行過程中的調整：周期性任務在每個周期開始時生成新實例，賦予新的截止時間。
時間推進引起的調整：隨著系統時間的推進，各任務的松弛度（截止時間-當前時間）不斷變化，需要定期重新計算優先級。
動態優先級調整的實現方式包括：
顯式排序：在每個調度決策點重新排序整個隊列。
增量更新：僅在任務狀態變化時更新隊列中的相關位置。
預計算截止時間：對于周期性任務，可預先計算未來多個周期的截止時間，減少實時計算開銷。
④ 非搶占式EDF實現
在非搶占式EDF實現中，任務一旦獲得處理器資源，必須執行完畢或主動放棄才能釋放資源。這種實現方式適用于以下場景：
低搶占開銷環境：如資源受限的嵌入式系統，減少上下文切換的開銷。
非周期性任務調度：如醫療設備中的緊急報警處理，需要確保任務執行完整性。
硬件支持不足：當處理器不支持快速搶占時，采用非搶占式實現。
非搶占式EDF的調度過程：
1.當前任務執行完畢或主動釋放處理器。
2.調度器檢查就緒隊列，選擇截止時間最早的任務執行。
3.任務開始執行，直到完成或主動阻塞。
非搶占式EDF的缺點是可能導致長任務阻塞短截止時間任務，從而增加任務錯過截止時間的風險。
6) 優缺點
優點：
高資源利用率：理論上可以達到100%的處理器利用率，特別適合資源受限的嵌入式系統。
靈活性：能夠處理周期性和非周期性任務的混合調度場景。
動態適應性：根據任務截止時間動態調整優先級，適應任務到達時間的變化。
最優調度保證：在單處理器環境下，EDF被證明是最優的動態調度算法。
缺點：
調度開銷大：動態優先級計算和頻繁的上下文切換增加了系統開銷。
過載風險：當系統總利用率超過1時，EDF無法保證所有任務都能在截止時間內完成。
實現復雜度高：需要維護復雜的就緒隊列結構，并實時計算任務截止時間。
確定性不足：動態調度可能導致系統行為難以預測，增加驗證難度。
1. 最低松弛時間優先（LLF）
1) 是什么
最低松弛度優先調度算法（Least Slack Time First，簡稱LSTF，也稱為Lowest Laxity First，LLF）是一種在實時系統中廣泛應用的動態優先級調度算法，通過精確計算任務的松弛度來確定執行順序，確保系統能夠高效處理周期性實時任務。本文將全面解析LSTF算法的核心原理、實現機制、特點優勢及實際應用場景，為理解這一算法提供系統性認知。
2) 松弛度是什么
松弛度（Slack Time）是LSTF算法的核心指標，表示任務從當前時間起，到必須完成之前所剩余的可用時間。松弛度越小，任務越緊急，優先級越高。
3) 未執行任務的松弛度怎么算
對于尚未開始執行的新任務，松弛度計算公式為：
Slack Time = Deadline - Current Time - Service Time
其中：
Deadline：任務的截止時間
Current Time：當前系統時間
Service Time：任務的總執行時間
示例：若有一個任務A，周期為20ms，執行時間為10ms，截止時間為30ms。當系統時間在10ms時，該任務的松弛度為：
Slack(A) = 30ms - 10ms - 10ms = 10ms
4) 已部分執行任務的松弛度計算
對于已經開始執行但尚未完成的任務，松弛度計算公式為：
Slack Time = Deadline - Current Time - Remaining Execution Time
其中：
Remaining Execution Time = Service Time - 已執行時間
示例：若任務B執行時間為25ms，已運行5ms，截止時間為50ms。當系統時間在15ms時，該任務的松弛度為：
Slack(B) = 50ms - 15ms - (25ms - 5ms) = 25ms - 20ms = 5ms
5) 調度規則
LSTF算法的核心調度規則是：始終選擇當前松弛度最小的任務作為下一個執行的任務。這種動態優先級分配機制確保了系統能夠根據任務的緊急程度實時調整執行順序。
LSTF算法的調度過程可以分為以下幾個步驟：
任務到達：周期性任務在每個周期的開始時間生成新實例
松弛度計算：計算所有就緒任務的松弛度
優先級排序：根據松弛度對任務進行排序，松弛度最小的任務優先級最高
任務選擇：選擇優先級最高的任務（即松弛度最小的任務）執行
執行監控：持續監控當前執行任務和就緒隊列中的任務
任務切換：當新任務到達或當前任務的松弛度變化時，立即切換到松弛度最小的任務
任務完成：任務完成后，更新系統狀態，準備下一輪調度
6) 調度機制
LSTF算法通常采用可搶占式調度，這意味著：
1.當一個任務的松弛度減為0時，它必須立即搶占CPU，以保證按時完成
2.當有更高優先級（即更低松弛度）的任務到達時，當前任務會被暫停，讓出CPU
3.任務切換時，系統需要保存當前任務的執行狀態，以便后續恢復
4.這種搶占機制確保了系統能夠及時響應緊急任務，但也會帶來一定的調度開銷。
若碰到相同松弛度時的處理辦法：
當多個任務具有相同的松弛度且為最小時，LSTF算法采用以下次級規則進行調度：
最近最久未調度（LRU）原則：
優先調度最近一次被調度時間最久的任務
任務到達順序：按照任務到達的先后順序進行調度
優先級編號：為每個任務預設優先級編號，作為最終判定依據
法核心特點（優點）
動態優先級：任務優先級隨松弛度實時變化，而非固定不變
周期性任務優化：直接利用任務周期性和截止期限信息，平衡任務間的調度
可搶占式調度：允許任務被搶占，確保緊急任務優先執行
資源高效利用：通過動態調整任務執行順序，減少CPU空閑時間
最小響應時間：優先執行剩余處理時間最短、截止時間最近的任務，有效縮短任務響應時間
預防系統過載：通過優先調度松弛度小的任務，有助于在系統過載時優先保證關鍵任務的截止期限
負載均衡：能夠在各個任務之間實現相對均衡的負載分配，提高系統整體性能
8) 算法的局限（缺點）
計算復雜度高：需頻繁計算所有就緒任務的松弛度，對系統計算能力有一定要求
調度開銷大：頻繁的任務切換可能導致調度開銷增加，特別是在任務粒度較細的場景
參數敏感：算法效果高度依賴任務參數的準確性，包括周期、執行時間和截止期限
不適用于非周期任務：主要針對周期性任務設計，對非周期任務的處理不如EDF算法靈活
總結
綜上通過合理選擇調度算法并結合優化策略，嵌入式系統可在資源受限條件下實現高實時性與可靠性。實際應用中需根據任務特性（周期性、截止時間、優先級）綜合評估，必要時可采用混合調度方案。
感謝大家看我絮絮叨叨，希望可以對你有所幫助。
