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

0引言

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

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

1 分層調(diào)度系統(tǒng)模型的定義

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

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

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

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

2 分層調(diào)度算法模型的實(shí)現(xiàn)

2．1分層模型的可調(diào)度性分析

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