優先級反轉和死鎖的資源管理模式研究與實現

王溪波， 楊麗娜

(沈陽工業大學信息科學與工程學院，遼寧沈陽110870)

0 引 言

嵌入式實時系統是在 IT網絡技術發展之后的又一發展新方向。嵌入式系統的產生與許多工程性學科類似，他的產生及發展源于軍事航空領域，嵌入式系統已經在各個行業廣泛應用，并且逐漸的改變著這些行業。與傳統的操作系統相比嵌入式實時操作系統有很多的約束，他要求具有安全性、實時性及高可靠性，每個任務必須在其執行限期內完成，并應符合若干規定，例如有效的調度策略，減少中斷處理的時間，優先級反轉問題的解決等等。優先級反轉現象，即高優先級任務被低優先級任務阻塞而無法正常運行。在多任務并發執行、共享資源時，存在死鎖的潛在危險，即指多個任務循環等待它方占有的資源而無限期地僵持下去的局面。需要解決這種現象來消除對系統的不良影響。目前，國內外研究人員提出了大量的設計模式，但 C/OS-Ⅱ并未提供實現方法。本文在分析優先級反轉和死鎖發生的原因的基礎上，修改 C/OS-Ⅱ內核結構并設計相應算法，在 C/OS-Ⅱ中實現了優先級繼承協議抑制優先級反轉，以排序鎖定共享資源管理模式避免死鎖的發生，為 C/OS-Ⅱ支持復雜的、高可靠的實時應用奠定了基礎。理論分析和結果表明，上述方法在抑制無限優先級反轉和避免死鎖具有可行性和有效性。

1 研究現狀

在嵌入式實時操作系統中，以獨占的方式訪問共享資源會出現優先級反轉的現象，為避免這種現象的發生，現在普遍采用的方法有以下兩種：一種是由L.Sha,R.Rajkumar和 J.P.Lehoczky提出的優先級繼承協議[1](priorityinheritanceprotocol，PIP)；另一種是由J.B.Goodenough和L.Sha提出的優先級天花板協議[2](priority ceiling protocol，PCP)。

優先級天花板協議的思想是[3]：當任務申請共享資源時，將該任務的優先級提升到可能訪問這個資源的所有任務中的最高優先級，當任務退出臨界區時，恢復其原有優先級。優先級天花板協議解決了優先級反轉同時也可避免死鎖的發生，但是 C/OS-Ⅱ目前最大只支持64個優先級[4]，也就是支持的任務最大數為64個，而且還有8個系統任務，所以實際上只有56個優先級可以使用，在實現該協議時，每種共享資源占用一個優先級，隨著嵌入式系統設計的日趨復雜，任務的數量受到優先級數量的限制，而且為每一個共享資源分配一個優先級天花板，增加了程序設計的復雜性，使系統的執行效率下降[5]。

優先級繼承協議的思想是：當高優先級的任務在等待低優先級的任務占用的信號量時，把低優先級任務的優先級提升到高優先級任務的優先級，當低優先級的任務退出臨界區時，立刻恢復到原來的優先級[6]。優先級繼承協議的共享資源管理可有內核自動完成，與PCP相比減少了設計者的負擔，并提升了管理執行效率[7-8]，但該協議沒有考慮死鎖問題。優先級繼承樣例模型如圖1所示。

圖1 優先級繼承樣例模型

在此模型中創建了3個任務，Task1、Task2、Task3，優先級分別為10，20，30。Task1在t3時，由于想使用Task3占用的共享資源而阻塞，這時系統提升Task3的優先級至Task1的優先級水平繼續執行。Task 3運行結束時，恢復原來的優先級，在t4時 Task 1申請到了共享資源而運行。由于優先級的提升，在t3到t4時間段內，Task 2不會搶占Task 3的運行。這樣優先級反轉就被限制在一個層次上，不會發生優先級無限反轉現象，抑制了優先級反轉現象的發生。建立3個任務，Task1、Task2、Task3他們的優先級分別為10、10、20，時間延時分別為6s、4s、2s，C/OS-Ⅱ調度運行結果如圖 2 所示。

實驗結果證明，由于Task1與Task2的優先級相同，任務Task2得不到CPU的使用權而無法運行，C/OS-Ⅱ不支持相同任務的優先級調度，因此不支持優先級繼承協議。相同優先級任務的運行結果如圖2所示。

圖2 調度運行結果

在 C/OS-Ⅱ中實現優先級繼承協議的主要思想：在任務控制塊中添加任務標識號TaskID用于標識系統任務以及一個時間片成員TimeSlice。將相同優先級任務鏈成一個雙向循環鏈表，使優先級索引表指向該循環鏈表，系統進行任務調度時判斷當前任務優先級是否為最高，若是則運行直到時間片TimeSlice結束，下一個相同優先級任務繼續執行，反之則查找最高優先級任務。

實驗結果表明，經改進后在 C/OS-Ⅱ中支持相同優先級任務的調度，改進內核后調度運行結果如圖3所示。

圖3 改進內核后調度運行結果

下面介紹優先級繼承協議在 C/OS-Ⅱ中的實現。

建立3個任務Task1、Task2、Task3，并且優先級分別設置為10、20、30，Task1優先級最高，建立一個互斥信號量S。其中任務Task1，Task3申請使用信號量S，Task2不申請此信號量。該實驗模型的功能是在屏幕上顯示一行字符串。其中 Task2先運行，然后Task3獲得CPU的使用權并占有共享資源，此時Task1也想申請該信號量，通過該實驗驗證優先級繼承協議在 C/OS-Ⅱ中使用的可行性。

實驗結果表明，改進內核后的優先級置頂協議可以在 C/OS-Ⅱ中使用，并且抑制了優先級反轉現象。當Task1申請使用Task3占用的信號量時，立刻將Task3的優先級提升到與Task1相同，使Task3盡快的運行，當Task3釋放了信號量后，Task1開始運行，可以抑制優先級反轉，當執行完后，Task3自動恢復到原來的優先級。改進內核后的優先級繼承協議抑制了優先級反轉現象如圖4和圖5所示。

圖4 改進內核后的優先級繼承協議抑制了優先級反轉現象

在 C/OS-Ⅱ中采用基于時間片輪轉調度算法優先級繼承協議實現能夠抑制優先級反轉現象，但沒考慮死鎖問題，不能夠避免死鎖。

圖5 優先級繼承協議抑制優先級反轉時序

3 死鎖產生的原因

死鎖也稱抱死(deadlock或deadlyembrace)，指兩個任務無限期的互相等待對方控制著的資源[10-11]。死鎖的產生原因有兩個[12]：①有限資源的競爭；②進程的推進順序。有兩個任務Task1和Task2，其共享兩個資源R1和R2。Task1的優先級高于Task2的優先級，Task1試圖先鎖定R2然后再鎖定R1，然后再以相反的次序釋放R1和R2；Task2試圖先鎖定R1然后鎖定R2，然后也以相反的次序釋放它們。在A點Task2獲得CPU的使用權開始運行，在B點Task2占用了共享資源R1，在C點，由于Task1的優先級高于Task2的優先級，Task1搶占了Task2獲得了CPU的使用權并開始運行，在D點Task1占用了共享資源R2此時系統可以正常運行，但到了E點，Task1又需要占用共享資源R1，而R1已經被Task2占用，所以Task1被阻塞，等待Task2釋放R1后繼續運行，Task2開始運行，而Task2需要占用共享資源R2，而R2被Task1占用，在這個時候，Task1和Task2都在等待一個不可能到來的條件，因此發生了死鎖。死鎖產生示意圖如圖6所示。

圖6 死鎖的產生

4 避免死鎖的主要思想

處理死鎖的有3種基本方法：死鎖的預防、死鎖的避免、死鎖的檢測與恢復[13]。本文重采用死鎖的避免來處理死鎖現象。

對優先級繼承協議進行改進的主要思想是使其在支持C/OS-Ⅱ實時操作系統的基礎上，避免死鎖的發生，提高系統的實時性和穩定性。采用排序鎖定共享資源的方法，使共享資源按照由低到高的次序被訪問，使循環的現象不再發生，從而避免死鎖。

共享資源R1和R2，資源號SourceIDR1Task2>Task3，Task3首先獲得了cpu的使用權并且開始運行，在t1時刻task1占用了共享資源R1；在t2時刻，Task1申請使用共享資源R2，由于SourceID R1

圖7 避免死鎖

本文在優先級繼承協議的基礎上在內核中增加了共享資源控制塊 OS_SourceTCB及共享資源控制塊鏈表 OSSource-TCBTbl[]。

4.1 共享資源的數據結構

*OSSourceTCBNext，*OSSourceTCBprev為指向共享資源的指針。共享資源的內容主要包括：指向共享資源堆棧的指針OSSourceTCBStdPtr；共享資源的標識，一個共享對應一個唯一的SourceID，用于指定被訪問的順序；OSTCBPrio任務的優先級，與任務一一對應；當任務占有某個共享資源時，其對應的OSSourceTCBStat被置為1，當共享資源被釋放時OSSource-TCBStat置為 0。

4.2 共享資源控制塊鏈表

在資源管理上，增加了兩條鏈表：一條是空的共享資源控制塊鏈表，(其中所有共享資源還沒有被任務占用)，令一條是共享資源控制塊鏈表(其中所有共享資源已被任務占用)。具體做法為：系統在調用OSInit()對 C/OS-Ⅱ進行初始化的時候，就先在RAM中建立一個OSSourceTCBTbl[]，然后把各個元素鏈成一個表，從而形成一個空的共享資源控制塊鏈表。初始化時創建的一個空共享資源控制塊鏈表如圖8所示。

4.3 避免死鎖的算法描述

在文獻[14]的基礎上解決死鎖問題，對共享資源加鎖的基本策略是為每個共享資源分配一個唯一的SourceID每個任務對資源的訪問要按照SourceID遞增的順序進行訪問，當有任務申請真用某資源時，從OS_SourceTbl[]中查找任務已使用過的資源的最大的SourceID與申請的SourceID’進行比較，如果已經用過的最大的SourceID小于SourceID’則該資源可以被占用。如果任務第一次申請使用資源，則允許使用該資源。如果當任務申請的資源被其他資源占用時，該資源處于阻塞狀態，但是死鎖不會發生[15]。因為至少有一個任務將不得不阻塞等待一個資源的釋放，而該資源的SourceID比占用資源的任務的最大SourceID要小。

用排序鎖定共享資源的方法避免死鎖發生，代碼如下：

5 實驗及結果分析

實驗的硬件環境為：T6400CPU、512MB內存、250GB硬盤的PC機，軟件環境為：移植 C/OS-Ⅱ實時操作系統到PC機上，使用Borland C++4.5和tasm5.0編譯器完成程序的測試。

本文根據優先級反轉及死鎖的基本理論在 C/OS-Ⅱ操作系統上設計了一個抑制優先級反轉同時避免死鎖的實驗模型。在這個實驗模型中，C/OS-Ⅱ操作系統創建了3個任務，Task1、Task2和Task3，它們的優先級Task1>Task2>Task3。兩個共享資源分別為R1和R2，資源號SourceIDR1Task3，在采用了改進的優先級繼承協議的基礎上，將Task3的優先級提升到Task1的水平，抑制了先級反轉現象，使得低優先級任務Task3繼續運行，然后Task3釋放了共享資源R1。

從避免死鎖現象的運行結果中看到，該模型中的共享資源是按照遞增的順序被訪問的，有效避免了死鎖的發生。避免死鎖現象的運行結果如圖9所示。

圖9 避免死鎖現象的運行結果

6 結束語

圖8 空資源控制塊鏈表

本文將優先級繼承協議和基于排序鎖定共享資源的方法相結合，并通過擴展 C/OS-Ⅱ的內核，使優先級反轉和死鎖問題的資源管理模式應用到 C/OS-Ⅱ實時操作系統中，不僅可以抑制 C/OS-Ⅱ操作系統的優先級反轉同時還可以避免死鎖的發生，增強了系統的實時性與穩定性。通過實驗驗證該方法切實有效。但是，新增的一些數據結構增加了系統的開銷，此外還存在資源等待的現象，下一步工作還需解決資源浪費的現象，減少系統開銷。

[1]周緒川.一種解決 C/OS中優先級反轉問題的方案[J].微計算機信息,2007,23(5-2):58-60.

[2]李光成,褚偉.基于 C/OS-II嵌入式實時系統的優先級倒置分析[J].計算機技術與發展,2007,17(7):98-101.

[3]王濤.實時系統調度若干關鍵技術的研究[D].哈爾濱:哈爾濱工程大學,2006:59-68.

[4]張軍,曹岳輝.改進的優先級繼承協議在 C/OS中的實現[J].自動化技術與應用,2009,28(3):126-128.

[5]徐亮,徐中偉.C/OS-II實時系統任務調度優化[J].計算機工程,2007,33(19):57-59.

[6]王繼剛,顧國昌.一種改進的優先級繼承協議及其算法研究[J].計算機工程,2007,33(8):41-44.

[7]毛德梅,汪明珠.C/OS-II中任務優先級反轉問題研究[J].安徽理工大學學報(自然科學版),2007,27(3):39-41.

[8]周本海,王溪波,喬建忠,等.基于多參數的 C/OS-Ⅱ任務優先級和調度方法[J].計算機工程,2007,33(21):28-30.

[9]胡國珍,范生凱.嵌入式RTOS優先級天花板協議研究[J].計算機工程與設計,2009,30(8):1893-1895.

[10]Labrosse J J.MicroC/OS-Ⅱ嵌入式實時操作系統[M].邵貝貝,譯.2版.北京:北京航空航天大學出版社,2007:55-56.

[11]千承輝.基于嵌入式實時系統的汽車檢測線測控系統研究[D].長春:吉林大學,2008:20-25.

[12]申雪琴.計算機操作系統中死鎖問題研究[J].計算機與數字工程,2008,36(7):203-204.

[13]劉林,劉正熙.基于排序的避免死鎖的方法[J].微計算機信息,2009,25(5-3):141-142.

[14]周本海.實時系統中實時調度算法及其資源管理的研究[D].沈陽:沈陽工業大學,2007:30-41.

[15]麥中凡,陶偉.實時設計模式[M].北京:北京航空航天大學出版社,2004:282-283.