優(yōu)先級(jí)反轉(zhuǎn)和死鎖的資源管理模式研究與實(shí)現(xiàn)

王溪波， 楊麗娜

(沈陽(yáng)工業(yè)大學(xué)信息科學(xué)與工程學(xué)院，遼寧沈陽(yáng)110870)

0 引 言

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

1 研究現(xiàn)狀

在嵌入式實(shí)時(shí)操作系統(tǒng)中，以獨(dú)占的方式訪問(wèn)共享資源會(huì)出現(xiàn)優(yōu)先級(jí)反轉(zhuǎn)的現(xiàn)象，為避免這種現(xiàn)象的發(fā)生，現(xiàn)在普遍采用的方法有以下兩種：一種是由L.Sha,R.Rajkumar和 J.P.Lehoczky提出的優(yōu)先級(jí)繼承協(xié)議[1](priorityinheritanceprotocol，PIP)；另一種是由J.B.Goodenough和L.Sha提出的優(yōu)先級(jí)天花板協(xié)議[2](priority ceiling protocol，PCP)。

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

優(yōu)先級(jí)繼承協(xié)議的思想是：當(dāng)高優(yōu)先級(jí)的任務(wù)在等待低優(yōu)先級(jí)的任務(wù)占用的信號(hào)量時(shí)，把低優(yōu)先級(jí)任務(wù)的優(yōu)先級(jí)提升到高優(yōu)先級(jí)任務(wù)的優(yōu)先級(jí)，當(dāng)?shù)蛢?yōu)先級(jí)的任務(wù)退出臨界區(qū)時(shí)，立刻恢復(fù)到原來(lái)的優(yōu)先級(jí)[6]。優(yōu)先級(jí)繼承協(xié)議的共享資源管理可有內(nèi)核自動(dòng)完成，與PCP相比減少了設(shè)計(jì)者的負(fù)擔(dān)，并提升了管理執(zhí)行效率[7-8]，但該協(xié)議沒(méi)有考慮死鎖問(wèn)題。優(yōu)先級(jí)繼承樣例模型如圖1所示。

圖1 優(yōu)先級(jí)繼承樣例模型

在此模型中創(chuàng)建了3個(gè)任務(wù)，Task1、Task2、Task3，優(yōu)先級(jí)分別為10，20，30。Task1在t3時(shí)，由于想使用Task3占用的共享資源而阻塞，這時(shí)系統(tǒng)提升Task3的優(yōu)先級(jí)至Task1的優(yōu)先級(jí)水平繼續(xù)執(zhí)行。Task 3運(yùn)行結(jié)束時(shí)，恢復(fù)原來(lái)的優(yōu)先級(jí)，在t4時(shí) Task 1申請(qǐng)到了共享資源而運(yùn)行。由于優(yōu)先級(jí)的提升，在t3到t4時(shí)間段內(nèi)，Task 2不會(huì)搶占Task 3的運(yùn)行。這樣優(yōu)先級(jí)反轉(zhuǎn)就被限制在一個(gè)層次上，不會(huì)發(fā)生優(yōu)先級(jí)無(wú)限反轉(zhuǎn)現(xiàn)象，抑制了優(yōu)先級(jí)反轉(zhuǎn)現(xiàn)象的發(fā)生。建立3個(gè)任務(wù)，Task1、Task2、Task3他們的優(yōu)先級(jí)分別為10、10、20，時(shí)間延時(shí)分別為6s、4s、2s，C/OS-Ⅱ調(diào)度運(yùn)行結(jié)果如圖 2 所示。

實(shí)驗(yàn)結(jié)果證明，由于Task1與Task2的優(yōu)先級(jí)相同，任務(wù)Task2得不到CPU的使用權(quán)而無(wú)法運(yùn)行，C/OS-Ⅱ不支持相同任務(wù)的優(yōu)先級(jí)調(diào)度，因此不支持優(yōu)先級(jí)繼承協(xié)議。相同優(yōu)先級(jí)任務(wù)的運(yùn)行結(jié)果如圖2所示。

圖2 調(diào)度運(yùn)行結(jié)果

在 C/OS-Ⅱ中實(shí)現(xiàn)優(yōu)先級(jí)繼承協(xié)議的主要思想：在任務(wù)控制塊中添加任務(wù)標(biāo)識(shí)號(hào)TaskID用于標(biāo)識(shí)系統(tǒng)任務(wù)以及一個(gè)時(shí)間片成員TimeSlice。將相同優(yōu)先級(jí)任務(wù)鏈成一個(gè)雙向循環(huán)鏈表，使優(yōu)先級(jí)索引表指向該循環(huán)鏈表，系統(tǒng)進(jìn)行任務(wù)調(diào)度時(shí)判斷當(dāng)前任務(wù)優(yōu)先級(jí)是否為最高，若是則運(yùn)行直到時(shí)間片TimeSlice結(jié)束，下一個(gè)相同優(yōu)先級(jí)任務(wù)繼續(xù)執(zhí)行，反之則查找最高優(yōu)先級(jí)任務(wù)。

實(shí)驗(yàn)結(jié)果表明，經(jīng)改進(jìn)后在 C/OS-Ⅱ中支持相同優(yōu)先級(jí)任務(wù)的調(diào)度，改進(jìn)內(nèi)核后調(diào)度運(yùn)行結(jié)果如圖3所示。

圖3 改進(jìn)內(nèi)核后調(diào)度運(yùn)行結(jié)果

下面介紹優(yōu)先級(jí)繼承協(xié)議在 C/OS-Ⅱ中的實(shí)現(xiàn)。

建立3個(gè)任務(wù)Task1、Task2、Task3，并且優(yōu)先級(jí)分別設(shè)置為10、20、30，Task1優(yōu)先級(jí)最高，建立一個(gè)互斥信號(hào)量S。其中任務(wù)Task1，Task3申請(qǐng)使用信號(hào)量S，Task2不申請(qǐng)此信號(hào)量。該實(shí)驗(yàn)?zāi)Ｐ偷墓δ苁窃谄聊簧巷@示一行字符串。其中 Task2先運(yùn)行，然后Task3獲得CPU的使用權(quán)并占有共享資源，此時(shí)Task1也想申請(qǐng)?jiān)撔盘?hào)量，通過(guò)該實(shí)驗(yàn)驗(yàn)證優(yōu)先級(jí)繼承協(xié)議在 C/OS-Ⅱ中使用的可行性。

實(shí)驗(yàn)結(jié)果表明，改進(jìn)內(nèi)核后的優(yōu)先級(jí)置頂協(xié)議可以在 C/OS-Ⅱ中使用，并且抑制了優(yōu)先級(jí)反轉(zhuǎn)現(xiàn)象。當(dāng)Task1申請(qǐng)使用Task3占用的信號(hào)量時(shí)，立刻將Task3的優(yōu)先級(jí)提升到與Task1相同，使Task3盡快的運(yùn)行，當(dāng)Task3釋放了信號(hào)量后，Task1開(kāi)始運(yùn)行，可以抑制優(yōu)先級(jí)反轉(zhuǎn)，當(dāng)執(zhí)行完后，Task3自動(dòng)恢復(fù)到原來(lái)的優(yōu)先級(jí)。改進(jìn)內(nèi)核后的優(yōu)先級(jí)繼承協(xié)議抑制了優(yōu)先級(jí)反轉(zhuǎn)現(xiàn)象如圖4和圖5所示。

圖4 改進(jìn)內(nèi)核后的優(yōu)先級(jí)繼承協(xié)議抑制了優(yōu)先級(jí)反轉(zhuǎn)現(xiàn)象

在 C/OS-Ⅱ中采用基于時(shí)間片輪轉(zhuǎn)調(diào)度算法優(yōu)先級(jí)繼承協(xié)議實(shí)現(xiàn)能夠抑制優(yōu)先級(jí)反轉(zhuǎn)現(xiàn)象，但沒(méi)考慮死鎖問(wèn)題，不能夠避免死鎖。

圖5 優(yōu)先級(jí)繼承協(xié)議抑制優(yōu)先級(jí)反轉(zhuǎn)時(shí)序

3 死鎖產(chǎn)生的原因

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

圖6 死鎖的產(chǎn)生

4 避免死鎖的主要思想

處理死鎖的有3種基本方法：死鎖的預(yù)防、死鎖的避免、死鎖的檢測(cè)與恢復(fù)[13]。本文重采用死鎖的避免來(lái)處理死鎖現(xiàn)象。

對(duì)優(yōu)先級(jí)繼承協(xié)議進(jìn)行改進(jìn)的主要思想是使其在支持C/OS-Ⅱ?qū)崟r(shí)操作系統(tǒng)的基礎(chǔ)上，避免死鎖的發(fā)生，提高系統(tǒng)的實(shí)時(shí)性和穩(wěn)定性。采用排序鎖定共享資源的方法，使共享資源按照由低到高的次序被訪問(wèn)，使循環(huán)的現(xiàn)象不再發(fā)生，從而避免死鎖。

共享資源R1和R2，資源號(hào)SourceIDR1Task2>Task3，Task3首先獲得了cpu的使用權(quán)并且開(kāi)始運(yùn)行，在t1時(shí)刻task1占用了共享資源R1；在t2時(shí)刻，Task1申請(qǐng)使用共享資源R2，由于SourceID R1

圖7 避免死鎖

本文在優(yōu)先級(jí)繼承協(xié)議的基礎(chǔ)上在內(nèi)核中增加了共享資源控制塊 OS_SourceTCB及共享資源控制塊鏈表 OSSource-TCBTbl[]。

4.1 共享資源的數(shù)據(jù)結(jié)構(gòu)

*OSSourceTCBNext，*OSSourceTCBprev為指向共享資源的指針。共享資源的內(nèi)容主要包括：指向共享資源堆棧的指針OSSourceTCBStdPtr；共享資源的標(biāo)識(shí)，一個(gè)共享對(duì)應(yīng)一個(gè)唯一的SourceID，用于指定被訪問(wèn)的順序；OSTCBPrio任務(wù)的優(yōu)先級(jí)，與任務(wù)一一對(duì)應(yīng)；當(dāng)任務(wù)占有某個(gè)共享資源時(shí)，其對(duì)應(yīng)的OSSourceTCBStat被置為1，當(dāng)共享資源被釋放時(shí)OSSource-TCBStat置為 0。

4.2 共享資源控制塊鏈表

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

4.3 避免死鎖的算法描述

在文獻(xiàn)[14]的基礎(chǔ)上解決死鎖問(wèn)題，對(duì)共享資源加鎖的基本策略是為每個(gè)共享資源分配一個(gè)唯一的SourceID每個(gè)任務(wù)對(duì)資源的訪問(wèn)要按照SourceID遞增的順序進(jìn)行訪問(wèn)，當(dāng)有任務(wù)申請(qǐng)真用某資源時(shí)，從OS_SourceTbl[]中查找任務(wù)已使用過(guò)的資源的最大的SourceID與申請(qǐng)的SourceID’進(jìn)行比較，如果已經(jīng)用過(guò)的最大的SourceID小于SourceID’則該資源可以被占用。如果任務(wù)第一次申請(qǐng)使用資源，則允許使用該資源。如果當(dāng)任務(wù)申請(qǐng)的資源被其他資源占用時(shí)，該資源處于阻塞狀態(tài)，但是死鎖不會(huì)發(fā)生[15]。因?yàn)橹辽儆幸粋€(gè)任務(wù)將不得不阻塞等待一個(gè)資源的釋放，而該資源的SourceID比占用資源的任務(wù)的最大SourceID要小。

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

5 實(shí)驗(yàn)及結(jié)果分析

實(shí)驗(yàn)的硬件環(huán)境為：T6400CPU、512MB內(nèi)存、250GB硬盤(pán)的PC機(jī)，軟件環(huán)境為：移植 C/OS-Ⅱ?qū)崟r(shí)操作系統(tǒng)到PC機(jī)上，使用Borland C++4.5和tasm5.0編譯器完成程序的測(cè)試。

本文根據(jù)優(yōu)先級(jí)反轉(zhuǎn)及死鎖的基本理論在 C/OS-Ⅱ操作系統(tǒng)上設(shè)計(jì)了一個(gè)抑制優(yōu)先級(jí)反轉(zhuǎn)同時(shí)避免死鎖的實(shí)驗(yàn)?zāi)Ｐ?。在這個(gè)實(shí)驗(yàn)?zāi)Ｐ椭?，C/OS-Ⅱ操作系統(tǒng)創(chuàng)建了3個(gè)任務(wù)，Task1、Task2和Task3，它們的優(yōu)先級(jí)Task1>Task2>Task3。兩個(gè)共享資源分別為R1和R2，資源號(hào)SourceIDR1Task3，在采用了改進(jìn)的優(yōu)先級(jí)繼承協(xié)議的基礎(chǔ)上，將Task3的優(yōu)先級(jí)提升到Task1的水平，抑制了先級(jí)反轉(zhuǎn)現(xiàn)象，使得低優(yōu)先級(jí)任務(wù)Task3繼續(xù)運(yùn)行，然后Task3釋放了共享資源R1。

從避免死鎖現(xiàn)象的運(yùn)行結(jié)果中看到，該模型中的共享資源是按照遞增的順序被訪問(wèn)的，有效避免了死鎖的發(fā)生。避免死鎖現(xiàn)象的運(yùn)行結(jié)果如圖9所示。

圖9 避免死鎖現(xiàn)象的運(yùn)行結(jié)果

6 結(jié)束語(yǔ)

圖8 空資源控制塊鏈表

本文將優(yōu)先級(jí)繼承協(xié)議和基于排序鎖定共享資源的方法相結(jié)合，并通過(guò)擴(kuò)展 C/OS-Ⅱ的內(nèi)核，使優(yōu)先級(jí)反轉(zhuǎn)和死鎖問(wèn)題的資源管理模式應(yīng)用到 C/OS-Ⅱ?qū)崟r(shí)操作系統(tǒng)中，不僅可以抑制 C/OS-Ⅱ操作系統(tǒng)的優(yōu)先級(jí)反轉(zhuǎn)同時(shí)還可以避免死鎖的發(fā)生，增強(qiáng)了系統(tǒng)的實(shí)時(shí)性與穩(wěn)定性。通過(guò)實(shí)驗(yàn)驗(yàn)證該方法切實(shí)有效。但是，新增的一些數(shù)據(jù)結(jié)構(gòu)增加了系統(tǒng)的開(kāi)銷(xiāo)，此外還存在資源等待的現(xiàn)象，下一步工作還需解決資源浪費(fèi)的現(xiàn)象，減少系統(tǒng)開(kāi)銷(xiāo)。

[1]周緒川.一種解決 C/OS中優(yōu)先級(jí)反轉(zhuǎn)問(wèn)題的方案[J].微計(jì)算機(jī)信息,2007,23(5-2):58-60.

[2]李光成,褚偉.基于 C/OS-II嵌入式實(shí)時(shí)系統(tǒng)的優(yōu)先級(jí)倒置分析[J].計(jì)算機(jī)技術(shù)與發(fā)展,2007,17(7):98-101.

[3]王濤.實(shí)時(shí)系統(tǒng)調(diào)度若干關(guān)鍵技術(shù)的研究[D].哈爾濱:哈爾濱工程大學(xué),2006:59-68.

[4]張軍,曹岳輝.改進(jìn)的優(yōu)先級(jí)繼承協(xié)議在 C/OS中的實(shí)現(xiàn)[J].自動(dòng)化技術(shù)與應(yīng)用,2009,28(3):126-128.

[5]徐亮,徐中偉.C/OS-II實(shí)時(shí)系統(tǒng)任務(wù)調(diào)度優(yōu)化[J].計(jì)算機(jī)工程,2007,33(19):57-59.

[6]王繼剛,顧國(guó)昌.一種改進(jìn)的優(yōu)先級(jí)繼承協(xié)議及其算法研究[J].計(jì)算機(jī)工程,2007,33(8):41-44.

[7]毛德梅,汪明珠.C/OS-II中任務(wù)優(yōu)先級(jí)反轉(zhuǎn)問(wèn)題研究[J].安徽理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2007,27(3):39-41.

[8]周本海,王溪波,喬建忠,等.基于多參數(shù)的 C/OS-Ⅱ任務(wù)優(yōu)先級(jí)和調(diào)度方法[J].計(jì)算機(jī)工程,2007,33(21):28-30.

[9]胡國(guó)珍,范生凱.嵌入式RTOS優(yōu)先級(jí)天花板協(xié)議研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(8):1893-1895.

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

[11]千承輝.基于嵌入式實(shí)時(shí)系統(tǒng)的汽車(chē)檢測(cè)線測(cè)控系統(tǒng)研究[D].長(zhǎng)春:吉林大學(xué),2008:20-25.

[12]申雪琴.計(jì)算機(jī)操作系統(tǒng)中死鎖問(wèn)題研究[J].計(jì)算機(jī)與數(shù)字工程,2008,36(7):203-204.

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

[14]周本海.實(shí)時(shí)系統(tǒng)中實(shí)時(shí)調(diào)度算法及其資源管理的研究[D].沈陽(yáng):沈陽(yáng)工業(yè)大學(xué),2007:30-41.

[15]麥中凡,陶偉.實(shí)時(shí)設(shè)計(jì)模式[M].北京:北京航空航天大學(xué)出版社,2004:282-283.