車載調(diào)度算法的改進(jìn)設(shè)計及應(yīng)用分析

作者：劉建偉;焦風(fēng)川;牛濤;申建德;王蕾

1 引 言

隨著現(xiàn)場總線技術(shù)、嵌入式微控制技術(shù)的發(fā)展，現(xiàn)代列車的過程控制已從集中型的直接數(shù)字控制系統(tǒng)發(fā)展成為基于網(wǎng)絡(luò)的分布式控制系統(tǒng)。高速列車以保汪旅客乘車安全與舒適為基礎(chǔ)，必須對車輛的制動、防滑、車門、供電及空調(diào)等設(shè)備分別進(jìn)行控制、檢測和診斷；各設(shè)備分別由相應(yīng)的車載微機(jī)進(jìn)行控制，構(gòu)成各個子系統(tǒng)；子系統(tǒng)之間通過現(xiàn)場總線互聯(lián)，形成全列車的網(wǎng)絡(luò)控制系統(tǒng)。實際情況下，車載微機(jī)需要對多點的壓力、溫度以及許多其他的狀態(tài)參量進(jìn)行采集與監(jiān)測．單一編程較為復(fù)雜，應(yīng)選用嵌入式實時操作系統(tǒng)來完成這些任務(wù)。任務(wù)中有些需要按時間片進(jìn)行調(diào)度，分時完成各個任務(wù)；而現(xiàn)有的源碼開放的嵌入式實時操作系統(tǒng)一般都是搶占式多任務(wù)內(nèi)核，因此需要對現(xiàn)有實時操作系統(tǒng)的任務(wù)調(diào)度機(jī)制進(jìn)行改造，從而滿足車載操作系統(tǒng)的實際需求。

2 調(diào)度算法分析

調(diào)度算法是指在有限的處理單元上對具有某些已知特征的任務(wù)集執(zhí)行順序的設(shè)計。在嵌入式實時系統(tǒng)中，任務(wù)的執(zhí)行要面對兩種限制：時間限制和資源限制。實時任務(wù)要求系統(tǒng)有良好的響應(yīng)時間以滿足截止時間，在嵌入式系統(tǒng)中只有有限的RAM和CPU等資源，所以調(diào)度的好壞在很大程度上決定了系統(tǒng)的性能。

2．1 RMS調(diào)度算法

RMS算法足在1973年由C．L.Liu和J．Layland提出的。該算法是基于統(tǒng)計任務(wù)執(zhí)行頻率的一種任務(wù)調(diào)度方法。RMS算法將最高優(yōu)先級賦予最高執(zhí)行頻率的任務(wù)，以單調(diào)的順序?qū)τ嘞碌娜蝿?wù)分配優(yōu)先級。分析中，RMS算法作了以下假設(shè)：

所有任務(wù)都是周期性的；

任務(wù)間不需要同步，沒有共亨資源，沒有任務(wù)間數(shù)據(jù)交換等問題；

CPU必須總是執(zhí)行優(yōu)先級最高且處于就緒態(tài)的任務(wù)，即須用可剝奪型內(nèi)核調(diào)度法。

由于采用搶占式的凋度方式，高優(yōu)先級的任務(wù)就緒后立即搶占正在運(yùn)行的較低優(yōu)先級的任務(wù)。設(shè)系統(tǒng)中有n項不同的任務(wù)，由于RMS算法要求調(diào)度的獨立的周期性任務(wù)總能滿足其截止時間，即要求系統(tǒng)中的所有任務(wù)必須滿足硬實時條件，于是有下列不等式成立：

式中：Uk為任務(wù)k最長執(zhí)行時間，Tk是任務(wù)k的執(zhí)行周期，Vk／Tk即任務(wù)k所需的CPU時間利用率。當(dāng)系統(tǒng)中的任務(wù)數(shù)n趨于無窮大時，S（n）的值為Ln2，即0．693。于是，若要使所有的任務(wù)都滿足硬實時要求，則有：

亦即所有有時間限制的任務(wù)的總CPU時間利用率應(yīng)低于70％。其實，系統(tǒng)設(shè)計中，使CPU的時間利用率達(dá)到100％并不好。如果那樣，程序就沒有修改的余地了，也無法增加新的功能。實際情況下，CPU的時間利用率應(yīng)在60％～70％以下。RMS算法的優(yōu)點是靈活性強(qiáng)、開銷小、可調(diào)度件測試簡單。但在某些情況下．執(zhí)行頻率最高的任務(wù)并非最重要的任務(wù)。

2．2 EDF調(diào)度算法

搶占式EDF調(diào)度算法是一種動態(tài)優(yōu)先級驅(qū)動的調(diào)度算法，其中分配給每個任務(wù)的優(yōu)先級根據(jù)它們當(dāng)前對最終截止時問的要求而定。當(dāng)前請求的截止時間最近的任務(wù)具有最高的優(yōu)先級，而請求截止時間最遠(yuǎn)的任務(wù)被分配最低優(yōu)先級。這個算法能夠保證在出現(xiàn)某個任務(wù)的截止時問不能滿足之前，不存在處理器的空閑時間。

C．L．Liu和J．Layland證明了對于一個具有n個任務(wù)的集合，截止時間驅(qū)動的調(diào)度算法的可行條件為：

任務(wù)的最長響應(yīng)時間Tr是可測的，須滿足Tr小于截止時間，任務(wù)才能被調(diào)度。對于Tr可用下式表達(dá)：

式中；Trun_i為任務(wù)i的執(zhí)行時間；Tlok_i為任務(wù)i的閉鎖時間；Tspd_i為任務(wù)i的調(diào)度開銷時間；Trdy_j為任務(wù)j再次就緒的時間；max{Tr/Trdy_j}·Trun_j為低優(yōu)先級任務(wù)i被高優(yōu)先級任務(wù)j剝奪后，高優(yōu)先級任務(wù)占用的總時間。

搶占式EDF調(diào)度算法最大的優(yōu)勢在于，當(dāng)系統(tǒng)的負(fù)載相對較低時非常有效，對于任何給定的任務(wù)集，只要處理器的利用率不超過100%，就能夠保證它的可調(diào)度性。EDF的劣勢在于不能解決過載問題，當(dāng)系統(tǒng)負(fù)載較重時，可能引起大量任務(wù)錯過截止時間，導(dǎo)致CPU的時間大量花費在調(diào)度上，這時系統(tǒng)的性能很低。

2.3 改進(jìn)調(diào)度算法

在嵌入式實時系統(tǒng)中資源非常有限，所以開銷要盡可能減?。欢鳵MS和EDF調(diào)度算法的問題就在于它們的開銷——運(yùn)行開銷和調(diào)度開銷。本文以uC／OS-II為例，結(jié)合Linux的調(diào)度算法，對uC／OS-II內(nèi)核的任務(wù)調(diào)度算法進(jìn)行改進(jìn)．使其成為搶占式與時間片輪轉(zhuǎn)調(diào)度相結(jié)合的調(diào)度算法，而系統(tǒng)的開銷并無多大改變。

以車載系統(tǒng)中常用的數(shù)據(jù)采集任務(wù)為例，可將uC/OS-II就緒表中的8個進(jìn)程設(shè)為數(shù)據(jù)采集專用的進(jìn)程。對于這8個進(jìn)程，采用時間片輪轉(zhuǎn)的任務(wù)調(diào)度算法，在TCB控制塊中增加一項變量counter作為任務(wù)調(diào)度的權(quán)值。如果就緒隊列中有優(yōu)先級比這8個進(jìn)程高的任務(wù)，則無條件讓出CPU使用權(quán)，系統(tǒng)執(zhí)行任務(wù)切換程序。如果當(dāng)前就緒隊列中優(yōu)先級最高的進(jìn)程屬于數(shù)據(jù)采集專用的8個進(jìn)程之一，則順序遍歷所有就緒的數(shù)據(jù)采集專用進(jìn)程，計算其時間片counter的值，取出時間片最大的進(jìn)程運(yùn)行。若遇到時間片大小相同的進(jìn)程，則取出優(yōu)先級高的進(jìn)程運(yùn)行。改進(jìn)后的任務(wù)調(diào)度算法如下：

3 應(yīng)注意的其他問題

（1）微型化

車載設(shè)備所能提供的資源有限，所以車載操作系統(tǒng)必須做到小巧以滿足系統(tǒng)硬件的限制。微內(nèi)核是一種機(jī)制與策略分離的開放式設(shè)計思路，已經(jīng)逐步取代了原來的單核概念，成為操作系統(tǒng)結(jié)構(gòu)設(shè)計的主流。微內(nèi)核思想帶來的模塊性及可配置性，適合于嵌入式應(yīng)用環(huán)境的需求。

（2）強(qiáng)實時性

車載操作系統(tǒng)工作在實時性要求很高的環(huán)境中，這就要求其必須將實時性作為一個重要的方面來考慮。在實時系統(tǒng)中，基于任務(wù)結(jié)束期限的調(diào)度是最理想化的調(diào)度算法，但是難以實現(xiàn)。現(xiàn)在實時性的保證主要依靠基于優(yōu)先級的搶占式調(diào)度。在車載應(yīng)用環(huán)境中，不同任務(wù)、不同優(yōu)先級的可搶先調(diào)度基本能夠滿足實時性的要求，但局限性很大；如果根據(jù)實際情況對原有的調(diào)度策略進(jìn)行改進(jìn)，則會給系統(tǒng)的開發(fā)帶來了很大的方便。

（3）高穩(wěn)定性

車載設(shè)備一旦開始運(yùn)行就不需要人過多地干預(yù)。在此條件下，負(fù)責(zé)系統(tǒng)管理的車載操作系統(tǒng)要具有較高的穩(wěn)定性。

（4）可裁剪

由于車載設(shè)備應(yīng)用目的不同，所以車載操作系統(tǒng)必須能夠根據(jù)應(yīng)用的要求進(jìn)行裁剪，去掉多余的部分，或者簡化相應(yīng)的模塊。

4 結(jié)語

車載操作系統(tǒng)內(nèi)核調(diào)度策略是針對車載系統(tǒng)應(yīng)用環(huán)境而設(shè)計的，滿足其任務(wù)搶占調(diào)度與時間片輪轉(zhuǎn)調(diào)度相結(jié)合的設(shè)計要求，同時該操作系統(tǒng)又具有微型化、實時性強(qiáng)、可裁剪等特點。目前，該系統(tǒng)已進(jìn)入詳細(xì)改造設(shè)計階段，下一步將對該操作系統(tǒng)進(jìn)一步實行移植測試，使其更好地滿足車載設(shè)備的要求。

責(zé)任編輯：gt