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

0引言

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

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

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

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

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

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

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

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

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

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