作者：劉建偉，焦風川，牛濤

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

1 調度算法分析

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

1．1 RMS調度算法

S算法足在1973年由C．L.Liu和J．Layland提出的。該算法是基于統計任務執行頻率的一種任務調度方法。RMS算法將最高優先級賦予最高執行頻率的任務，以單調的順序對余下的任務分配優先級。分析中，RMS算法作了以下假設：

◇所有任務都是周期性的；

◇任務間不需要同步，沒有共亨資源，沒有任務間數據交換等問題；

◇CPU必須總是執行優先級最高且處于就緒態的任務，即須用可剝奪型內核調度法。

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

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

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

1．2 EDF調度算法

搶占式EDF調度算法是一種動態優先級驅動的調度算法，其中分配給每個任務的優先級根據它們當前對最終截止時問的要求而定。當前請求的截止時間最近的任務具有最高的優先級，而請求截止時間最遠的任務被分配最低優先級。這個算法能夠保證在出現某個任務的截止時問不能滿足之前，不存在處理器的空閑時間。

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

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

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

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

1.3 改進調度算法

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

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

2 應注意的其他問題

（1）微型化

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

（2）強實時性

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

（3）高穩定性

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

（4）可裁剪

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

結語

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

責任編輯：gt