0引言

嵌入式實時系統由于自身CPU計算能力較弱和內存容量較低的原因，希望采用復雜度低、系統開銷小的調度算法。目前的實時系統通常采用單優先級驅動的搶占式調度算法，根據任務的某一時間特性參數如任務周期或最后截止期等為各個任務分配系統資源[1][2]。這種搶占式調度策略具有靈活性和動態性等優點。但在，實際應用系統中也有一些由不相交的周期任務子集組成，每個子集是系統的一個主要部分，稱之為子系統。例如，飛行管理系統包含飛行控制，電子設備和導航式三個子系統。這三個子系統的任務如果按照以前的靜態、動態算法實現需要系統開發人員設計很復雜的調度算法，實時控制也相對困難[3][4]。本文按照分層思想在實時操作系統層面上設計調度算法，減輕了解決此類問題系統開發人員的負擔，算法的主要思想是：修改內核的任務控制塊，增加一個子模塊標識來控制分層調度，采用固

定時間輪轉算法調度各子系統模塊，子系統中的任務按照速率單調算法調度，從而實現兩層的調度策略。本文首先定義了分層調度系統的模型，并對分層調度算法的可調度性進行了理論分析；其次，以實時內核μC/OS-Ⅱ為背景，實現了具有分層調度功能的調度器，最后通過實驗驗證分層調度算法的可行性和正確性。

1 分層調度系統模型的定義

定義1 在不考慮釋放抖動的情況下，一個任務集Τ={τ1,τ2,…, τn}中的任務τi 的屬性可以用一個五元組（Mi， ,Pi,Di, Ei）來表示。其中，Mi 表示任務屬于的模塊； 是相位；Pi 表示任務周期，對于非周期任務，取其最小時間間隔作為周期；Di 表示任務完成

的最后期限；Ei 表示任務的最大請求運行時間。

在定義任務屬性時，擴展以前任務描述的四元組到五元組[5]，增加了任務所屬模塊的屬性，這一點是為了給子模塊的索引表提供一個標志，以便實現任務集按子模塊分層調度管理。

定義2 對于任務τi，其各實例從到達時刻至執行完成時刻之間的時間間隔稱為該實例的響應時間,各實例響應時間的最大值稱為任務τi的最大響應時間 Ri，若 Ri≤Di，則稱任務τi可調度。

2 分層調度算法模型的實現

2．1分層模型的可調度性分析

假定：系統中具有n個獨立的，可搶占的任務，并且任務的相對時限等于各自的周期。如果系統的總利用率U滿足下式：