車載操作系統(tǒng)的調(diào)度算法分析與改進(jìn)

摘要 當(dāng)前沒(méi)有專門為車栽設(shè)備設(shè)計(jì)的實(shí)時(shí)操作系統(tǒng)，一般都是對(duì)通用嵌入式實(shí)時(shí)操作系統(tǒng)進(jìn)行裁剪來(lái)完成的，需要很大的工作量。本文介紹一種在嵌入式實(shí)時(shí)系統(tǒng)中調(diào)度所面臨的限制以及克服這些限制的調(diào)度技術(shù)；根據(jù)uC/OS-II實(shí)時(shí)嵌入式系統(tǒng)內(nèi)核的特殊性，在原有優(yōu)先級(jí)調(diào)度算法的基礎(chǔ)和某車載設(shè)備設(shè)計(jì)的基礎(chǔ)上，提出一種車栽實(shí)時(shí)操作系統(tǒng)內(nèi)核的改進(jìn)方法，其特點(diǎn)是實(shí)時(shí)性強(qiáng)、穩(wěn)定性高、面向車栽設(shè)備應(yīng)用。
關(guān)鍵詞 實(shí)時(shí)操作系統(tǒng)調(diào)度算法 內(nèi)核 車載設(shè)備

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

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

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

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

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

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

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

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

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

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

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

   

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

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

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

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

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