解決優先級倒置問題的RTOS優先級調度策略

大多數商用即時作業系統(RTOS)均採用基於優先級的搶先調度器，這些系統為每個任務分配唯一的優先等級。調度器可以保證在所有等待執行的任務中，真正執行的總是具有最高優先級的任務。為了滿足上述目標，調度器需要在執行中搶先優先級較低的任務。

由於多個任務共享資源，調度器控制範圍以外的事件可以在必要的情況下阻止具有最高優先級的準備就緒任務執行。如果出現這種情形，將有可能使任務錯過臨界期限(critical deadline)，從而導致系統崩潰。優先級倒置就是當具有最高優先級的準備就緒任務在應該執行卻無法執行時所採用的一項應急措施。

資源共享引發的問題

在採用基於優先級的調度器中，一旦兩個任務共享了資源(如儲存緩衝器)，那麼其中之一通常具有較高的優先級。高優先級的任務期望一旦準備就緒就能執行，但當高優先級任務就緒，而低優先級任務正在使用共享資源時，高優先級任務必須等待，直到低優先級任務完成對共享資源的作業。這時，我們稱高優先級任務被中斷。如果高優先級任務必須滿足臨界期限，那麼還必須計算所有共享資源在最壞條件下的‘鎖定時間(lockout time)’，並在設計中加以考慮。如果累積的鎖定時間過長，那麼資源共享機制就必須重新設計。任務需要共享資源進行通訊和數據處理，但這種多線程特性並不適用於即時或嵌入式系統。

優先級倒置技術

當高優先級任務中斷時，中優先級的任務搶先了正在使用共享資源的低優先級任務，因而真正的問題來自執行階段；如果高優先級任務已準備就緒並等待執行，但中優先級任務此刻正在執行，這時就出現了優先級倒置問題。

圖1顯示了這些危險的事件序列。低優先級任務L和高優先級任務H共享了資源，在任務L佔有資源之後不久，任務H就緒；但這時任務H必須等待任務L完成對共享資源的作業。在任務L完成對共享資源的作業之前，任務M也已就緒並將搶先任務L執行。在任務M(也許還包括其他的中優先級任務)執行時，系統中具有最高優先級的任務H仍然保持中斷狀態。

許多優先級倒置都不會給系統帶來危害，最多只是延遲了馬上應該執行的任務。但偶爾也會出現系統關鍵優先級的倒置，例如這種情形就出現在1997年7月的火星‘拓荒者(Mars Pathfinder)’探測任務中。‘拓荒者’是對火星表層進行高解析度拍照並將照片發回地球的小飛行器。

‘拓荒者’遭遇的問題並不出自登陸軟體，而來自登陸命令軟體。大量的任務通過很大的一塊共享記憶體區進行通訊，其中部份是低優先級的天氣數據任務，另一些則是具有高優先級的資訊匯流排管理任務。設計該軟體的噴氣推進實驗室(JPL)的工程人員建立了信號量(semaphore)機制對共享記憶體區數據進行存取控制。

大部份時間?，軟體都能無故障地執行；但有時在任務執行中，一個較為嚴重的問題足以引發整個軟體重啟。當低優先級的天氣任務獲得信號量並對共享記憶體區進行存取時，就產生一連串導致系統崩潰的事件序列。在這段時間中，高優先級的匯流排管理任務也需要信號量，但不得不等待信號量的釋放(因為天氣任務正在使用該信號量)。此後不久，觸發了一條中斷，導致中優先級的通訊任務就緒。通訊任務無須對共享記憶體區進行存取，但該任務的優先級高於其他正在執行的任務。因此低優先級的天氣任務將被搶先，並開始執行中優先級的通訊任務。中優先級任務需要進行大量的處理，因此將佔用相當長的時間。這期間，低優先級的天氣任務仍然佔據信號量，而高優先級的匯流排管理任務則在等待信號量的釋放。由於高優先級的任務相當重要，因此經常會觸發一個監控定時器。如果未觸發監控定時器，系統將自動重啟。

這樣的問題並不由RTOS的錯誤(如對信號量的錯誤作業)導致，相反，軟體展現了信號量和進程間通訊的一個顯著特徵。實際上，‘拓荒者’的RTOS支援可選的工作區，而JPL的科學家根本就沒有實施這項功能。幸虧科學家們可以遠程作業工作區並完成任務。

兩種優先級倒置方案

優先級倒置研究獲得了兩種解決方案。第一種方案稱為優先級繼承(priority inheritance)，該技術強令低優先級的任務繼承與之共享資源並被中斷的任意高優先級任務的優先等級。一旦高優先級任務開始中斷，即可實施優先級繼承，直到資源釋放。這需要得到作業系統的大力支援。

第二種解決方案稱為優先級頂置(priority ceiling)，該方案為每種資源都分配優先級；調度器將該優先級傳送至任何存取資源的任務，而分配給資源的優先級則為最高優先級用戶的優先級。一旦任務完成對該資源的作業，其優先級恢復正常。

優先級頂置的一大特色就在於任務可以共享資源，並且只需簡單地改變資源的優先級，因此就不再需要信號量。

============================

void TaskA(void)

{

...

SetTaskPriority(RES_X_PRIO);

// Access shared resource X.

SetTaskPriority(TASK_A_PRIO);

...

}

=============================

當任務A的優先級提升時(該任務正對資源X進行存取)，任務A將不會為任何其他資源中斷。當低優先級任務完成對共享資源的作業時，高優先級的用戶將只能成為最高優先級的等待任務。

儘管我們都不全為火星任務編寫過程式，但仍然可以從以往的錯誤中汲取經驗並避免在下一解決方案的實施中重覆相同的錯誤。許多商用的RTOS均支援優先級繼承或優先級倒置，並且只需知道自己需要那種解決方案。

參考文獻

Jones, Mike. "What Really Happened on Mars Rover Pathfinder," Risks-Forum Digest, December 1997.

Sha L., R. Rajkumar, and J.P. Lehoczky. "Priority Inheritance Protocols: An Approach to Real-Time Synchronization," IEEE Transactions on Computers, September 1990, p. 1175.

作者: David Kalinsky

用戶教育總監

OSE Systems公司

Email: david@enea.com

Michael Barr

主編

Embedded Systems Programming

Email: mbarr@cmp.com