實時系統優先級反轉研究

摘要：在實時多任務操作系統中，由于外部事件需要有快速的反應能力，選擇一種合適的任務調度算法非常重要。如果多個任務訪問共享資源時，可能會導致優先級的反轉問題。對此給出了目前經常采用的兩種解決此問題的方法。分析了它們可能存在的不足，重點分析了優先級繼承，并對它作了進一步改進。通過測試證明，該方法行之有效。

關鍵詞： 實時系統； 調度算法； 信號量； 優先級反轉； 優先級繼承

中圖分類號：TP316.2文獻標志碼：A

文章編號：1001－3695(2008)06－1728－03

實時系統與其他系統之間的最大不同之處就是要滿足處理與時間的關系。在實時計算中，系統的正確性不僅僅依賴于計算結果的正確性而且還依賴于計算結果產生的時間。對于實時系統來說，最重要的要求就是實時系統必須有滿足在一個事先定好的時間限制中對外部或內部的事件進行響應和處理的能力。因此，一種合適的任務調度算法對于實時多任務系統的這種要求就顯得非常重要。典型的調度算法有優先級搶占調度、時間片輪轉調度等[1～3]。多任務系統將信號量機制作為一種普通的方式來控制共享資源。當一個任務需要使用一個共享資源時，它必須先申請得到這個信號量；一旦它得到了此信號量，那就只有等它使用完了該資源，信號量才會被釋放。在這個過程中即使有優先權更高的任務進入了就緒態，因為無法得到信號量，也不能使用該資源，這也將會導致優先級的反轉[4] 。針對這個問題，目前比較有效的解決方法是采用優先級置頂協議和優先級繼承協議。

1優先級反轉及解決方法

1．1優先級反轉問題分析

對于可搶占的實時內核，一般高優先級的任務應該能夠從初始化開始就搶占較低優先級的任務立即執行。優先級反轉是指一個任務等待比它優先級低的任務釋放資源而被阻塞，如果這時有中等優先級的就緒任務，阻塞會進一步惡化，甚至超過了任務的最后期限。這種情況通常產生在兩個任務同時要訪問共享資源時，直接導致了不確定的優先級反轉時間和系統可調度性的降低，從而嚴重危害了系統的實時性能[6]。

圖1為優先級反轉的示意圖。在t1、t2、t3三個任務中，它們的優先級順序是t1>t2>t3，t3通過得到分配的信號量已經獲得一些資源。當t1搶占t3，并且為滿足得到相同信號量的資源時，t1就會被阻塞。如果要確保t1不會被長時間阻塞，由于資源是不能被搶占的，通常要等t3的資源用完后t1才能得到信號量。然而，低優先級任務搶占較高優

先級任務（如t2）時，較高優先級任務能夠放棄資源而使t3禁止，這也使低優先級任務容易受損。這種情況可以斷定：可以無限期地阻塞t1。假如在實際系統中，t1任務是顯示報警信息，那么這種被長時間阻塞的情況無疑是致命的。

上述現象中，優先級高的任務要等優先級低的任務運行完之后才能被調度。如果優先級低的任務執行的是很費時的操作，顯然優先級高的任務被調度的時機就不能得到保證，整個實時調度的性能就很差了。

1．2優先級反轉的解決方法

目前解決優先級反轉問題主要有兩種方案：

a)優先級置頂協議。把系統中每一個臨界資源與一個優先級上限相聯系，當一個任務進入臨界區時，系統把這個優先級上限傳遞給這個任務，使得該任務的優先級最高，以完成任務。這樣每一個資源都會擁有一個叫priority ceiling的事先設計好的保留優先級。當高優先級的任務要求訪問該資源時，如果這個資源已經被低優先級的任務占有，那么程序當中就把該低優先級任務臨時提高到priority ceiling來，將低優先級的任務先完成。當這個任務退出臨界區后系統立即將其優先級恢復正常，從而保證系統不會出現優先級反轉。

b)優先級繼承協議。當一個任務阻塞一個或多個高優先級任務時，該任務便忽略自己的原始優先級分配而以它阻塞的所有任務的最高優先級執行臨界區，使得該任務能盡快釋放出優先級較高的任務所需要的資源。在退出臨界區后，該任務再恢復原來的優先級。

2優先級反轉解決方法的技術改進

2．1分析目前方法存在的不足

在發生優先級反轉的時候，利用優先級置頂協議的缺點是（回到圖1優先級反轉示意圖）：如果在任務t3申請信號量的時候，發現信號量已經被t1所占用，那么將執行優先級置頂協議，將任務t1臨時提升到priority ceiling的優先級。假設目前存在一個任務t4，而t4的優先級高于t3，但是又比priority cei－ling要低，那么在t1的優先級提升到priority cei－ling后， t4已經就緒要求執行了。而這時由于t4的優先級比priority ceiling要低，t4不能執行，必須等待t1執行完畢以后才能從就緒狀態轉入到運行狀態來執行。而實際情況是t4比其他三個任務的優先級都要高，按照搶先式設計，任務t4必須優先執行，而這個時候t1卻比t4優先執行。如果t4是一個非常重要的任務，那么系統的實時性能就不可靠了。因此，在系統設計時，程序設計者必須為每一個資源都設計一個惟一的合適的priority ceiling。這會大大增加程序設計者的負擔。程序設計者必須靜態地將每個任務以及每個資源都仔細地進行考慮，然后選擇適合的priority ceiling來對優先級加以保護。如果設計得不好，系統有可能存在隱患，而對于實時反應要求高的系統，往往是致命的地方。優先級置頂協議的好處是在大多數情況較好時，它不需要作環境切換，這樣就可以大大提高系統的效率。

如果采用優先級繼承方法則不需要另外給任務添加prio－rity ceiling。優先級繼承保證了擁有資源的任務運行，而高優先級的任務則要被這個資源阻塞。因此就要提高擁有資源任務的優先級，一旦這個任務的優先級被提高，直到該任務擁有的所有互斥信號量被釋放，這個任務的優先級始終都會保持在一個被提高的狀態。因此，繼承任務就會被任意一個優先級處在中間的任務所保護。

優先級繼承方法的使用可以減輕程序設計者的負擔，不需要為每一個資源設計一個優先級來確定怎樣設置priority cei－ling而煩惱，可以大大方便實時系統設計者。但是，由于實時系統的優先級是惟一的，每一個任務只能有一個優先級，而且是惟一一個優先級，這是由實時系統任務調度方式來決定的，它在任務就緒表中選擇優先級最高的任務執行，且只能選擇一個任務。因此，優先級繼承方法需要改寫內核os_task_info數據結構等，并且要將其改寫為支持時間片輪轉算法，這就與實時系統的設計初衷不一樣了，而且其修改要將實時系統變成兩個任務可以擁有同一個優先級的方式，會改變整個設計思路。這個方法也有缺點。

2．2優先級繼承方法的改進

優先級繼承法可以大大減輕程序設計者的負擔，這對于軟件設計方向來說是一個趨勢。實時操作系統的設計必須減輕軟件設計者的負擔，盡量將精力轉移到程序邏輯上面來，而不是更多地注重編程技巧和編程方法。因此，可以將優先級繼承方法進行改進，做到既不改變實時系統的任務調度方式，又可以很好地防止優先級反轉。

優先級反轉的原因很多是因為申請信號量而產生的優先級反轉。可以考慮通過對信號量的申請來實現優先級的交換，以此對優先級的繼承作進一步改進。圖2為優先級繼承示意圖。優先級繼承解決優先級反轉問題，是通過提高t3的優先級來實現的，而在t1時間內，t1的優先級被信號量阻塞。下面通過優先級繼承示意圖（圖2）來看如何實現優先級交換的。

圖1優先級反轉圖2優先級繼承

當在位置（3）時，t1想要搶占t3是因為要申請信號量。而這時可以檢測到該信號量已經被t3占用。那么這時可以將t3和t1的優先級進行交換。由于t1和t3本來就是惟一的優先級，交換以后并不影響實時系統優先級惟一的規定，并且可以看到，在位置（3）（4）當中，如果這兩者之間有一個新任務：任務t4就緒，t4比這三個優先級還要高，這時任務t4依然可以搶占掉t3，按照原有的邏輯將高優先級任務完成。到了位置（4）時，t3釋放信號量，這時就將t3和t1的優先級再交換過來，這樣t1就可以繼續運行了。

實時系統中的信號量由兩部分組成：一個是信號量計數值，它是一個16位的無符號整數（0~65 535）；另一個由等待該信號量的任務組成的等待任務表。用戶要在OS_CFGH中將OS_SEM_EN開關量常數設置成1，這樣實時系統才能支持信號量。實時系統提供了五個對信號量進行操作的函數，分別是OSSemCreate()、OSSemPend()、 OSSenPost()、 OSSemAccept() 和OSSemQuery()。在使用一個信號量之前，首先要建立該信號量，即調用OSSemCreate()；OSSemPend()是用來等待一個信號量；OSSenPost()是發送一個信號量。OSSemAccept()是無等待地請求一個信號量。當一個任務請求一個信號量時，如果該信號量暫時無效，也可以讓該任務簡單地返回，而不是進入睡眠等待狀態。這種情況下的操作是由OSSemAccept()函數完成的。OSSemQuery()是查詢一個信號量的當前狀態，在應用程序中，用戶隨時可以調用函數OSSemQuery()來查詢一個信號量的當前狀態。程序只需要在創建信號量、釋放信號量和等待信號量當中作修改，為每創建的信號量添加三個變量Cur_Priority、Is_Convert和Con_Priority。Cur_Priority看目前占用信號量資源任務的優先級是多少；Is_Convert是用來標記是否進行了優先級交換；Con_Priority是用來保存被交換的優先級。在創建信號量的時候，對這三個變量先進行初始化。

當申請信號量時，先看是不是有任務已經占有該信號量。如果沒有占有，則占有該信號量，并且將Cur_Priority設置為本任務的優先級。如果已經有其他任務占用這個信號量，看該信號量的Cur_Priority是否比本任務的優先級要高。如果高則不作其他變動，但是如果Cur_Priority比自身要低的話，則進行優先級反轉。首先將Is_Convert置為true；然后將Cur_Priority保存到Con_Priority當中去；再將兩個任務的優先級進行交換。

當釋放信號量時，先檢查Is_Convert是否為true。如果 Is_Convert為真，則表示發生過優先級交換。那么將本任務優先級轉換為Con_Priority的值，而Con_Priority優先級所對應的任務優先級也要變換成本任務優先級，這樣就將優先級交換回來了；然后再調度優先級高的任務運行。如果Is_Convert為假，那么就不做其他操作。這樣就實現了優先級的交換。圖3為優先級繼承改進算法流程圖。

圖3優先級繼承改進算法流程

這種方法是對優先級繼承方法的改進。首先是不需要修改系統的運行方式，不需要將實時操作系統改做支持時間片輪轉調度，也不需要修改內核的TCB的結構，并且編程方式更加簡單，只需要修改信號量管理分布即可。

3優先級繼承改進算法的測試結果

建立三個任務，分別為TH、TM、TL，即高優先級任務、中等優先級任務和低優先級任務。高優先級任務主要負責打印成對數字“1，2”；中等優先級任務負責打印成對數字“3，4”；低優先級任務則負責打印成對數字“5，6”。其中：高優先級任務和低優先級任務當中申請同一信號量，并且在申請信號量后，用一個空循環段來延遲時間。其測試結果如圖4所示。當沒有采用優先級繼承改進算法時，三個任務打印出來的數字可以表示其中優先級反轉發生的情況，即中等優先級任務搶占了低優先級任務執行，使得高優先級任務執行的時間大大延遲。采用了優先級繼承改進算法后，高優先級任務執行的時間只延遲了低優先級任務處理信號量的過程。

圖4優先級繼承改進算法測試結果

從圖4可以看出，采用了優先級繼承改進算法以后，可以大大減少優先級反轉的時間，使得任務執行正常，從而保證高優先級的任務可以按時完成，很好地避免了優先級的反轉。

4結束語

實時多任務操作系統相對于其他操作系統而言，外部事件需要有更快的反應能力。選擇一種合適的任務調度算法非常重要。如果多個任務訪問共享資源可能會導致優先級反轉。基于這個問題，本文分析了目前采用的兩種解決此問題的方法，即優先級置頂和優先級繼承，分析了它們可能存在的不足，并對優先級繼承作了進一步改進。通過測試證明，此方法可以很好地解決優先級的反轉問題。

參考文獻：

[1]SEO Y， PARK J， HONG S. Supporting preemptive user－level threads for embedded real－time systems，SNU－EE－TR－98－1[R].[S.l.]:SNU EE，1998.

[2]DIERKS H. Synthesizing controllers from real－time specifications[J]. IEEE Trans on Computer－Aided Design of Integrated Circuits and Systems， 1999，18(1):33－43.

[3]MIGGE J. Real－time scheduling: a trajectory based model[D].[S.l.]:University of Nice， 1999.

[4]DHAMDHERE D M. Systems programming and operating systems[M]. Beijing: Tsinghua University Press，2001:99－101.

[5]BACH M J. The desgin of the UNIX operating system[M].[S.l.]:Prentice Hall Inc，1990:79－84.

[6]LABROSSE J J.嵌入式實時操作系統μC/OS－Ⅱ[M].邵貝貝，等譯. 2版.北京:北京航空航天大學出版社，2003:150－154.

[7] 鄭宗漢.實時系統軟件基礎[M].北京：清華大學出版社，2003:56－71.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文