車(chē)載操作系統的調度算法分析與改進(jìn)

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

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

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

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

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

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

任務(wù)的最長(cháng)響應時(shí)間Tr是可測的，須滿(mǎn)足Tr小于截止時(shí)間，任務(wù)才能被調度。對于Tr可用下式表達：

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

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

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

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

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

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

(3)高穩定性
車(chē)載設備一旦開(kāi)始運行就不需要人過(guò)多地干預。在此條件下，負責系統管理的車(chē)載操作系統要具有較高的穩定性。

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

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