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