基于μC/OS-Ⅱ的實(shí)時(shí)分層調度算法研究

0引言

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

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

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

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

的最后期限；Ei 表示任務(wù)的最大請求運行時(shí)間。

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

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

2 分層調度算法模型的實(shí)現

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

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