車載操作系統(tǒng)的調度算法分析與改進

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

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

1．1 RMS調度算法
RMS算法足在1973年由C．L.Liu和J．Layland提出的。該算法是基于統(tǒng)計任務執(zhí)行頻率的一種任務調度方法。RMS算法將最高優(yōu)先級賦予最高執(zhí)行頻率的任務，以單調的順序對余下的任務分配優(yōu)先級。分析中，RMS算法作了以下假設：
◇所有任務都是周期性的；
◇任務間不需要同步，沒有共亨資源，沒有任務間數(shù)據(jù)交換等問題；
◇CPU必須總是執(zhí)行優(yōu)先級最高且處于就緒態(tài)的任務，即須用可剝奪型內核調度法。
由于采用搶占式的凋度方式，高優(yōu)先級的任務就緒后立即搶占正在運行的較低優(yōu)先級的任務。設系統(tǒng)中有n項不同的任務，由于RMS算法要求調度的獨立的周期性任務總能滿足其截止時間，即要求系統(tǒng)中的所有任務必須滿足硬實時條件，于是有下列不等式成立：

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

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

1．2 EDF調度算法
搶占式EDF調度算法是一種動態(tài)優(yōu)先級驅動的調度算法，其中分配給每個任務的優(yōu)先級根據(jù)它們當前對最終截止時問的要求而定。當前請求的截止時間最近的任務具有最高的優(yōu)先級，而請求截止時間最遠的任務被分配最低優(yōu)先級。這個算法能夠保證在出現(xiàn)某個任務的截止時問不能滿足之前，不存在處理器的空閑時間。
C．L．Liu和J．Layland證明了對于一個具有n個任務的集合，截止時間驅動的調度算法的可行條件為：

任務的最長響應時間Tr是可測的，須滿足Tr小于截止時間，任務才能被調度。對于Tr可用下式表達：

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

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

1.3 改進調度算法
在嵌入式實時系統(tǒng)中資源非常有限，所以開銷要盡可能減??；而RMS和EDF調度算法的問題就在于它們的開銷――運行開銷和調度開銷。本文以uC／OS-II為例，結合Linux的調度算法，對uC／OS-II內核的任務調度算法進行改進．使其成為搶占式與時間片輪轉調度相結合的調度算法，而系統(tǒng)的開銷并無多大改變。

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

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

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

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

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

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