解決優(yōu)先級(jí)倒置問題的RTOS優(yōu)先級(jí)調(diào)度策略

1、解決優(yōu)先級(jí)倒置問題的RTOS優(yōu)先級(jí)調(diào)度策略大多數(shù)商用實(shí)時(shí)操作系統(tǒng)(RTOS)均采用基于優(yōu)先級(jí)的搶先調(diào)度器，這些系統(tǒng)為每個(gè)任務(wù)分配唯一的優(yōu)先等 級(jí)。調(diào)度器可以保證在所有等待運(yùn)行的任務(wù)中，真正運(yùn)行的總是具有最高優(yōu)先級(jí)的任務(wù)。為了滿足上述目 標(biāo)，調(diào)度器需要在執(zhí)行中搶先優(yōu)先級(jí)較低的任務(wù)。由于多個(gè)任務(wù)共享資源，調(diào)度器控制范圍以外的事件可以在必要的情況下阻止具有最高優(yōu)先級(jí)的準(zhǔn)備就緒 任務(wù)運(yùn)行。如果出現(xiàn)這種情形，將有可能使任務(wù)錯(cuò)過臨界期限(critical deadline)，從而導(dǎo)致系統(tǒng)崩潰。優(yōu)先 級(jí)倒置就是當(dāng)具有最高優(yōu)先級(jí)的準(zhǔn)備就緒任務(wù)在應(yīng)該運(yùn)行卻無法執(zhí)行時(shí)所采用的一項(xiàng)應(yīng)急措施。資源共享引發(fā)的問題在采用

2、基于優(yōu)先級(jí)的調(diào)度器中，一旦兩個(gè)任務(wù)共享了資源(如存儲(chǔ)緩沖器)，那么其中之一通常具有較高的 優(yōu)先級(jí)。高優(yōu)先級(jí)的任務(wù)期望一旦準(zhǔn)備就緒就能運(yùn)行，但當(dāng)高優(yōu)先級(jí)任務(wù)就緒，而低優(yōu)先級(jí)任務(wù)正在使用 共享資源時(shí)，高優(yōu)先級(jí)任務(wù)必須等待，直到低優(yōu)先級(jí)任務(wù)完成對共享資源的操作。這時(shí)，我們稱高優(yōu)先級(jí) 任務(wù)被掛起。如果高優(yōu)先級(jí)任務(wù)必須滿足臨界期限，那么還必須計(jì)算所有共享資源在最壞條件下的“鎖定 時(shí)間(lockout time)”，并在設(shè)計(jì)中加以考慮。如果累積的鎖定時(shí)間過長，那么資源共享機(jī)制就必須重新設(shè) 計(jì)。任務(wù)需要共享資源進(jìn)行通信和數(shù)據(jù)處理，但這種多線程特性并不適用于實(shí)時(shí)或嵌入式系統(tǒng)。優(yōu)先級(jí)倒置技術(shù)當(dāng)高優(yōu)先級(jí)任務(wù)掛起時(shí)

3、，中優(yōu)先級(jí)的任務(wù)搶先了正在使用共享資源的低優(yōu)先級(jí)任務(wù)，因而真正的問題來自 運(yùn)行階段；如果高優(yōu)先級(jí)任務(wù)已準(zhǔn)備就緒并等待運(yùn)行，但中優(yōu)先級(jí)任務(wù)此刻正在運(yùn)行，這時(shí)就出現(xiàn)了優(yōu)先 級(jí)倒置問題。低優(yōu)先級(jí)任務(wù)L和高優(yōu)先級(jí)任務(wù)H共享了資源，在任務(wù)L占有資源之后不久，任務(wù)H就緒；但這時(shí)任務(wù)H 必須等待任務(wù)L完成對共享資源的操作。在任務(wù)L完成對共享資源的操作之前，任務(wù)M也已就緒并將搶先 任務(wù)L運(yùn)行。在任務(wù)M(也許還包括其他的中優(yōu)先級(jí)任務(wù))運(yùn)行時(shí)，系統(tǒng)中具有最高優(yōu)先級(jí)的任務(wù)H仍然保 持掛起狀態(tài)。許多優(yōu)先級(jí)倒置都不會(huì)給系統(tǒng)帶來危害，最多 只是延遲了馬上應(yīng)該運(yùn)行的任務(wù)。但偶爾也會(huì) 出現(xiàn)系統(tǒng)關(guān)鍵優(yōu)先級(jí)的倒置，例如這種情形就

4、 出現(xiàn)在1997年7月的火星“拓荒者(Mars Pathfinder) ”探測任務(wù)中。“拓荒者”是對火 星表層進(jìn)行高分辨率拍照并將照片發(fā)回地球的 小飛行器?！巴鼗恼摺痹庥龅膯栴}并不出自登陸軟件，而來自登陸命令軟件。大量的任務(wù)通過很大的一塊共享內(nèi)存區(qū)進(jìn)行通信，其中部分是低優(yōu)先級(jí)的天氣數(shù)據(jù)任 務(wù)，另一些則是具有高優(yōu)先級(jí)的信息總線管理任務(wù)。設(shè)計(jì)該軟件的噴氣推進(jìn)實(shí)驗(yàn)室(JPL)的工程人員建立了 信號(hào)量(semaphore)機(jī)制對共享內(nèi)存區(qū)數(shù)據(jù)進(jìn)行存取控制。大部分時(shí)間里，軟件都能無故障地運(yùn)行；但有時(shí)在任務(wù)執(zhí)行中，一個(gè)較為嚴(yán)重的問題足以引發(fā)整個(gè)軟件重 啟。當(dāng)?shù)蛢?yōu)先級(jí)的天氣任務(wù)獲得信號(hào)量并對共享內(nèi)存區(qū)進(jìn)行存

5、取時(shí)，就產(chǎn)生一連串導(dǎo)致系統(tǒng)崩潰的事件序 列。在這段時(shí)間中，高優(yōu)先級(jí)的總線管理任務(wù)也需要信號(hào)量，但不得不等待信號(hào)量的釋放（因?yàn)樘鞖馊蝿?wù)正 在使用該信號(hào)量）。此后不久，觸發(fā)了一條中斷，導(dǎo)致中優(yōu)先級(jí)的通信任務(wù)就緒。通信任務(wù)無須對共享內(nèi)存 區(qū)進(jìn)行存取，但該任務(wù)的優(yōu)先級(jí)高于其他正在運(yùn)行的任務(wù)。因此低優(yōu)先級(jí)的天氣任務(wù)將被搶先，并開始運(yùn) 行中優(yōu)先級(jí)的通信任務(wù)。中優(yōu)先級(jí)任務(wù)需要進(jìn)行大量的處理，因此將占用相當(dāng)長的時(shí)間。這期間，低優(yōu)先 級(jí)的天氣任務(wù)仍然占據(jù)信號(hào)量，而高優(yōu)先級(jí)的總線管理任務(wù)則在等待信號(hào)量的釋放。由于高優(yōu)先級(jí)的任務(wù) 相當(dāng)重要，因此經(jīng)常會(huì)觸發(fā)一個(gè)監(jiān)控定時(shí)器。如果未觸發(fā)監(jiān)控定時(shí)器，系統(tǒng)將自動(dòng)重啟。這樣的問

6、題并不由RTOS的錯(cuò)誤（如對信號(hào)量的錯(cuò)誤操作）導(dǎo)致，相反，軟件展現(xiàn)了信號(hào)量和進(jìn)程間通信的 一個(gè)顯著特征。實(shí)際上，“拓荒者”的RTOS支持可選的工作區(qū)，而JPL的科學(xué)家根本就沒有實(shí)施這項(xiàng)功 能。幸虧科學(xué)家們可以遠(yuǎn)程操作工作區(qū)并完成任務(wù)。兩種優(yōu)先級(jí)倒置方案優(yōu)先級(jí)倒置研究獲得了兩種解決方案。第一種方案稱為優(yōu)先級(jí)繼承（priority inheritance），該技術(shù)強(qiáng)令低優(yōu) 先級(jí)的任務(wù)繼承與之共享資源并被掛起的任意高優(yōu)先級(jí)任務(wù)的優(yōu)先等級(jí)。一旦高優(yōu)先級(jí)任務(wù)開始掛起，即 可實(shí)施優(yōu)先級(jí)繼承，直到資源釋放。這需要得到操作系統(tǒng)的大力支持。第二種解決方案稱為優(yōu)先級(jí)頂置（priority ceiling），該方案

7、為每種資源都分配優(yōu)先級(jí)；調(diào)度器將該優(yōu)先級(jí)傳 送至任何存取資源的任務(wù)，而分配給資源的優(yōu)先級(jí)則為最高優(yōu)先級(jí)用戶的優(yōu)先級(jí)。一旦任務(wù)完成對該資源 的操作，其優(yōu)先級(jí)恢復(fù)正常。優(yōu)先級(jí)頂置的一大特色就在于任務(wù)可以共享資源，并且只需簡單地改變資源的優(yōu)先級(jí)，因此就不再需要信 號(hào)量。void TaskA(void) ( SetTaskPriority(RES_X_PRIO); / Access shared resource X. SetTaskPriority(TASK_A_PRIO); 當(dāng)任務(wù)A的優(yōu)先級(jí)提升時(shí)（該任務(wù)正對資源X進(jìn)行存取），任務(wù)A將不會(huì)為任何其他資源掛起。當(dāng)?shù)蛢?yōu)先級(jí) 任務(wù)完成對共享資源的操作時(shí)，

8、高優(yōu)先級(jí)的用戶將只能成為最高優(yōu)先級(jí)的等待任務(wù)。盡管我們都不全為火星任務(wù)編寫過程序，但仍然可以從以往的錯(cuò)誤中汲取經(jīng)驗(yàn)并避免在下一解決方案的實(shí) 施中重復(fù)相同的錯(cuò)誤。許多商用的RTOS均支持優(yōu)先級(jí)繼承或優(yōu)先級(jí)倒置，并且只需知道自己需要那種解 決方案。參考文獻(xiàn)Jones, Mike. What Really Happened on Mars Rover Pathfinder, Risks-Forum Digest, December 1997.Sha L.，R. Rajkumar, and JP Lehoczky. Priority Inheritance Protocols: An Approach to Real-Time Synchronization, IEEE Transactions on Computers, September 1990, p. 1175.作者：David Kalinsky用