石效存，張?chǎng)握\(chéng)

(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，陜西 西安 710072)

0 引言

自動(dòng)控制、國(guó)防工業(yè)仿真等領(lǐng)域越來(lái)越多地需要操作系統(tǒng)具有實(shí)時(shí)性，所以實(shí)時(shí)操作系統(tǒng)越來(lái)越受到關(guān)注。除了Linux系統(tǒng)實(shí)時(shí)化，人們?cè)絹?lái)越多地開(kāi)始關(guān)注Windows操作系統(tǒng)的實(shí)時(shí)化。這是因?yàn)閃indows平臺(tái)具有更低的價(jià)格優(yōu)勢(shì)、更豐富的應(yīng)用和更為廣大的用戶群體。除了實(shí)時(shí)化，操作系統(tǒng)經(jīng)常需要一些擴(kuò)展活動(dòng)。本文設(shè)計(jì)了一種Windows驅(qū)動(dòng)加載的自定義臨界區(qū)。在現(xiàn)代的操作系統(tǒng)和應(yīng)用程序中，線程或線程之間的通信往往是不可避免的，有些是因?yàn)楣δ鼙旧淼男枰行﹦t是因?yàn)橘Y源有限而不得不共享。在操作系統(tǒng)擴(kuò)展中不可避免地要涉及線程同步問(wèn)題，而要完全滿足自定義要求就需要定制同步機(jī)制［1-2］。

1 臨界區(qū)機(jī)制

常見(jiàn)的臨界區(qū)是一種較為輕量級(jí)的機(jī)制，在某一時(shí)間內(nèi)只允許一個(gè)線程執(zhí)行某個(gè)給定代碼段。通常在修改全局?jǐn)?shù)據(jù)(如集合類)時(shí)會(huì)使用臨界區(qū)。事件、互斥鎖和信號(hào)量也用于多線程同步，但臨界區(qū)與它們不同，它并不總是執(zhí)行向內(nèi)核模式的控制轉(zhuǎn)換，這一轉(zhuǎn)換成本昂貴。要獲得一個(gè)未占用臨界區(qū)，事實(shí)上只需要對(duì)內(nèi)存做出很少的修改，速度較快。只有在嘗試獲得已占用臨界區(qū)時(shí)，它才會(huì)跳至內(nèi)核模式。這一輕量級(jí)特性的缺點(diǎn)在于臨界區(qū)只能用于對(duì)同一進(jìn)程內(nèi)的線程進(jìn)行同步。另外在有限次等待后進(jìn)入內(nèi)核態(tài)，一直到資源可用為止，這會(huì)使得性能急劇降低［3］。

臨界區(qū)主要是利用有限次的自旋來(lái)進(jìn)行線程同步的。如果一定時(shí)間內(nèi)不能進(jìn)入臨界區(qū)，那么系統(tǒng)會(huì)使得該線程陷入內(nèi)核，進(jìn)行相關(guān)調(diào)度，進(jìn)行任務(wù)切換。在切換時(shí)，調(diào)度會(huì)首先掛起當(dāng)前線程，利用線程結(jié)構(gòu)中的相關(guān)鏈表指針，插入到等待鏈表中，利用調(diào)度算法選出下一個(gè)能夠運(yùn)行的線程，使其運(yùn)行。臨界區(qū)在線程同步時(shí)涉及系統(tǒng)調(diào)度，而由于Windows系統(tǒng)本身的調(diào)度策略以及時(shí)間片問(wèn)題，如果在一直得不到臨界區(qū)的情況下，效率會(huì)變得非常糟糕［4］。Windows臨界區(qū)(CRITICAL_SECTION)結(jié)構(gòu)如下。

DebugInfo字段包含一個(gè)指針，指向系統(tǒng)分配的伴隨結(jié)構(gòu)，該結(jié)構(gòu)的類型為RTL_CRITICAL_SECTION_DEBUG，主要記錄著等待臨界區(qū)的相關(guān)線程信息。LockCount被初始化為數(shù)值-1;此數(shù)值等于或大于0時(shí)，表示此臨界區(qū)被占用。OwningThread字段包含了擁有此臨界區(qū)的線程ID，與(RecursionCount-1)數(shù)值之間的差值表示有多少個(gè)其他線程在等待獲得該臨界區(qū)。RecursionCount字段包含所有者線程已經(jīng)獲得該臨界區(qū)的次數(shù)。如果該數(shù)值為0，下一個(gè)嘗試獲取該臨界區(qū)的線程將會(huì)成功。LockSemaphore字段實(shí)際上是一個(gè)自復(fù)位事件，而不是一個(gè)信號(hào)。它是一個(gè)內(nèi)核對(duì)象句柄，用于通知操作系統(tǒng):該臨界區(qū)現(xiàn)在空閑。SpinCount僅用于多處理器系統(tǒng)。MSDN文檔對(duì)此字段進(jìn)行如下說(shuō)明:“在多處理器系統(tǒng)中，如果該臨界區(qū)不可用，調(diào)用線程將在對(duì)與該臨界區(qū)相關(guān)的信號(hào)執(zhí)行等待操作之前，旋轉(zhuǎn)dwSpinCount次。如果該臨界區(qū)在旋轉(zhuǎn)操作期間變?yōu)榭捎茫撜{(diào)用線程就避免了等待操作?！毙D(zhuǎn)計(jì)數(shù)可以在多處理器計(jì)算機(jī)上提供更佳性能，其原因在于在一個(gè)循環(huán)中旋轉(zhuǎn)通常要快于進(jìn)入內(nèi)核模式等待狀態(tài)［5］。

2 臨界區(qū)設(shè)計(jì)實(shí)現(xiàn)

2.1 臨界區(qū)與調(diào)度

臨界區(qū)作為線程同步的一種方式，不可避免地需要調(diào)度配合。臨界區(qū)的爭(zhēng)奪，總會(huì)導(dǎo)致線程間的切換。為了提高性能，調(diào)度周期要盡可能地穩(wěn)定，調(diào)度策略應(yīng)盡可能簡(jiǎn)潔。但是多線程的情況下，同步機(jī)制的出現(xiàn)必然會(huì)影響調(diào)度工作。

利用Windows現(xiàn)有的調(diào)度將出現(xiàn)嚴(yán)重的優(yōu)先級(jí)反轉(zhuǎn)問(wèn)題，優(yōu)先級(jí)反轉(zhuǎn)是指這樣的問(wèn)題:在線程調(diào)度時(shí)，一個(gè)低優(yōu)先級(jí)的線程占有一個(gè)共享資源，從而導(dǎo)致高優(yōu)先級(jí)的線程雖然其它運(yùn)行條件都滿足，但因?yàn)榈貌坏皆撡Y源而無(wú)法運(yùn)行。在采用搶占式調(diào)度算法的操作系統(tǒng)中，當(dāng)?shù)蛢?yōu)先級(jí)的線程占有了資源時(shí)，它有可能被中等優(yōu)先級(jí)的其它線程搶占。低優(yōu)先級(jí)線程由于被掛起使得該資源得不到及時(shí)的釋放，從而導(dǎo)致有等待該資源的高優(yōu)先級(jí)線程在更長(zhǎng)時(shí)間內(nèi)無(wú)法運(yùn)行。實(shí)際的效果就是，相當(dāng)于把高優(yōu)先級(jí)的線程降到低優(yōu)先級(jí)。實(shí)時(shí)操作系統(tǒng)顯然需要解決優(yōu)先級(jí)反轉(zhuǎn)這一問(wèn)題［6］。解決優(yōu)先級(jí)反轉(zhuǎn)問(wèn)題的方法有2種:(1)短暫地提高占有臨界區(qū)資源線程的優(yōu)先級(jí)，使得其盡快得到CPU資源運(yùn)行從而釋放臨界區(qū);(2)為臨界區(qū)資源本身設(shè)定優(yōu)先級(jí)，進(jìn)入臨界區(qū)的線程應(yīng)當(dāng)以臨界區(qū)優(yōu)先級(jí)為調(diào)度優(yōu)先級(jí)。離開(kāi)臨界區(qū)時(shí)，應(yīng)該再次回復(fù)本身優(yōu)先級(jí)。

多線程的同步操作會(huì)使得線程掛起和恢復(fù)操作變得頻繁。這將加重調(diào)度任務(wù)量，影響整體性能。因此需要同步機(jī)制盡可能少地影響調(diào)度隊(duì)列，盡可能讓同步完成在用戶態(tài)，不至于進(jìn)行調(diào)度鏈表操作而影響調(diào)度操作。

2.2 臨界區(qū)結(jié)構(gòu)設(shè)計(jì)

基于上述論述，首先考慮的是依據(jù)Windows本身臨界區(qū)來(lái)設(shè)計(jì)實(shí)時(shí)擴(kuò)展模塊的臨界區(qū)結(jié)構(gòu)。以Windows原有結(jié)構(gòu)為基礎(chǔ)，所設(shè)計(jì)的臨界區(qū)要與調(diào)度器配合解決優(yōu)先級(jí)反轉(zhuǎn)問(wèn)題。選擇臨界區(qū)不設(shè)置優(yōu)先級(jí)，在出現(xiàn)優(yōu)先級(jí)反轉(zhuǎn)時(shí)直接提高占有資源的線程優(yōu)先級(jí)。這樣做的好處是臨界區(qū)本身簡(jiǎn)單化了，用戶區(qū)不用維護(hù)臨界區(qū)本身的優(yōu)先級(jí)，同時(shí)節(jié)省了內(nèi)存。調(diào)度器會(huì)在有優(yōu)先級(jí)反轉(zhuǎn)時(shí)暫時(shí)提高占有臨界區(qū)線程的優(yōu)先級(jí)到最高，保證臨界資源能快速得到釋放。同時(shí)為了保證調(diào)度周期的穩(wěn)定性，盡可能地提高臨界區(qū)執(zhí)行效率，操作應(yīng)該盡可能地在用戶態(tài)執(zhí)行。而Windows本身臨界區(qū)是會(huì)進(jìn)入內(nèi)核態(tài)觸發(fā)事件對(duì)象進(jìn)行同步。從用戶態(tài)切換入內(nèi)核態(tài)是非常消耗時(shí)間的，所以要盡可能地避免這種切換。Windows臨界區(qū)中記錄等待線程信息主要依靠鏈表進(jìn)行，而維護(hù)則需要進(jìn)入內(nèi)核態(tài)。為了提高效率，對(duì)于等待線程記錄的操作需要在用戶態(tài)完成，所以舍棄DebugInfo字段，直接定義一個(gè)合適的線程ID數(shù)組，設(shè)計(jì)臨界區(qū)結(jié)構(gòu)如下:

2.3 臨界區(qū)存儲(chǔ)

為了進(jìn)一步提高效率，可以事先在初始化時(shí)就申請(qǐng)足夠數(shù)量的臨界區(qū)。由于設(shè)置時(shí)用于操作的變量沒(méi)有指針，所以很方便將其映射到用戶態(tài)。用戶態(tài)操作LockCount字段時(shí)需要用到原子操作Interlocked系列Windows提供的API。以上臨界區(qū)設(shè)置，可以避免大部分的操作進(jìn)入內(nèi)核態(tài)，但是在初始化臨界區(qū)時(shí)依然需要進(jìn)入內(nèi)核，將申請(qǐng)的臨界區(qū)掛入內(nèi)核控制鏈表中。

Windows操作系統(tǒng)對(duì)內(nèi)存管理時(shí)，用戶地址和內(nèi)核地址都是虛擬地址［7］，雖然2片地址范圍不存在交集，但是對(duì)它們的訪問(wèn)最終都映射成訪問(wèn)實(shí)際的物理內(nèi)存地址?？梢酝ㄟ^(guò)MDL把用戶空間和內(nèi)核空間的一片內(nèi)存區(qū)域跟一片物理內(nèi)存相關(guān)聯(lián)，如圖1所示。

圖1 映射示意圖

將臨界區(qū)結(jié)構(gòu)提前申請(qǐng)并映射到用戶態(tài)后，臨界區(qū)操作基本可以在用戶態(tài)完成。這可以大大地減少進(jìn)入內(nèi)核的次數(shù)，從而提高其實(shí)時(shí)性能。

2.4 臨界區(qū)操作

臨界區(qū)操作主要包括:初始化、進(jìn)入、退出、刪除。臨界區(qū)操作應(yīng)該都是原子性的。所以臨界區(qū)內(nèi)部操作均需InterLocked系列函數(shù)支持。該系列函數(shù)式Windows針對(duì)無(wú)符號(hào)整數(shù)提供了一系列原子操作。臨界區(qū)基本接口設(shè)計(jì)如下:

首先初始化應(yīng)該在進(jìn)程一開(kāi)始就進(jìn)行。初始化時(shí)，需要進(jìn)入內(nèi)核態(tài)，從預(yù)先申請(qǐng)的臨界區(qū)上取下一個(gè)節(jié)點(diǎn)，以head_list字段掛接在內(nèi)核中臨界區(qū)管理鏈表上。設(shè)置LockCount字段為-1，表示可用。進(jìn)入和退出時(shí)需要配合調(diào)度器進(jìn)行線程狀態(tài)的維護(hù)，以便準(zhǔn)確調(diào)度。進(jìn)入時(shí)，若臨界區(qū)可用，則以InterLocked-Increment函數(shù)使 LockCount加 1，改變 OwingThread字段為當(dāng)前線程。若不可用，依然使得LockCount加1，然后將線程id加入WaitingThread字段，同時(shí)置線程狀態(tài)為WAIT。退出操作中需要在釋放臨界區(qū)時(shí)，查看WaitingThread字段，找出其中優(yōu)先級(jí)最高者。更改最高優(yōu)先級(jí)線程狀態(tài)為READY，使其可以參加下一輪調(diào)度。刪除操作一般在進(jìn)程結(jié)束時(shí)進(jìn)行，進(jìn)入內(nèi)核態(tài)，從臨界區(qū)管理鏈表上取下此節(jié)點(diǎn)即可。

以上是臨界區(qū)本身操作。在進(jìn)入和退出臨界區(qū)時(shí)，主要的操作是將臨界區(qū)和相關(guān)線程關(guān)聯(lián)起來(lái)，同時(shí)根據(jù)臨界區(qū)狀態(tài)設(shè)置等待線程的狀態(tài)為WAIT或者READY。在下一個(gè)時(shí)鐘中斷時(shí)，進(jìn)入調(diào)度。調(diào)度器會(huì)根據(jù)鏈表中線程控制表(TCB)的狀態(tài)進(jìn)行鏈表調(diào)整［8］，將WAIT狀態(tài)的節(jié)點(diǎn)全部掛入等待隊(duì)列。若有獲取臨界區(qū)狀態(tài)為READY的線程，則從WAIT鏈表轉(zhuǎn)移進(jìn)入READY鏈表。最后從READY鏈表中選擇優(yōu)先級(jí)最高的線程運(yùn)行，設(shè)置狀態(tài)RUN。其基本流程如圖2所示。

圖2 臨界區(qū)及調(diào)度執(zhí)行流程

3 試驗(yàn)結(jié)果及分析

在完成上述臨界區(qū)設(shè)計(jì)的基礎(chǔ)上，編碼實(shí)現(xiàn)了自定義臨界區(qū)原型。設(shè)計(jì)實(shí)驗(yàn)對(duì)其進(jìn)行功能性測(cè)試。實(shí)驗(yàn)設(shè)計(jì)如下:創(chuàng)建3個(gè)線程，分別對(duì)共享資源(全局變量A)進(jìn)行加法運(yùn)算1000次，每次加法之后讓線程放棄CPU，最后輸出結(jié)果。在不使用臨界區(qū)時(shí)，最終結(jié)果會(huì)出現(xiàn)不確定性，不一定等于3000。使用臨界區(qū)時(shí)，結(jié)果總是準(zhǔn)確的。2種情況測(cè)試各100次，結(jié)果如表1所示。

表1 測(cè)試結(jié)果

測(cè)試結(jié)果表明，在線程進(jìn)行全局變量加法時(shí)，如果有釋放CPU的行為很容易導(dǎo)致結(jié)果錯(cuò)誤，而使用臨界區(qū)可以有效地解決全局變量不一致問(wèn)題。以上測(cè)試結(jié)果說(shuō)明自定義的臨界區(qū)是有效的，它能夠保護(hù)共享資源，完成多線程的同步問(wèn)題。

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

Windows操作系統(tǒng)有著廣泛的應(yīng)用，在很多情況下需要擴(kuò)展，這時(shí)同步機(jī)制自定義實(shí)現(xiàn)或改進(jìn)將是必不可少的。本文通過(guò)分析提出了一種自定義臨界區(qū)的設(shè)計(jì)。應(yīng)用內(nèi)存映射，使得進(jìn)入和退出臨界區(qū)操作均在用戶態(tài)進(jìn)行。相比于需要進(jìn)入內(nèi)核態(tài)操作，這將使得臨界區(qū)的操作更為快速。臨界區(qū)只是同步機(jī)制中最簡(jiǎn)單的一種，而其它同步機(jī)制也是很有必要的。另外，實(shí)時(shí)化過(guò)程中同步機(jī)制與擴(kuò)展模塊的調(diào)度本身的配合很重要。這是一個(gè)很值得考慮的問(wèn)題。Windows本身擴(kuò)展改造是一個(gè)復(fù)雜而系統(tǒng)的問(wèn)題，所以在設(shè)計(jì)時(shí)需要根據(jù)相應(yīng)場(chǎng)景進(jìn)行全面考量。

［1］杜旭東，蔣澤軍，王麗芳，等.基于資源重分配的Windows實(shí)時(shí)性改造［J］.微電子學(xué)與計(jì)算機(jī)，2012，29(5):95-98，103.

［2］蔣善峰，王麗芳，蔣澤軍.Windows時(shí)鐘機(jī)制的實(shí)時(shí)擴(kuò)展研究［J］.微電子學(xué)與計(jì)算機(jī)，2013，30(8):116-119，123.

［3］呂浩勇，余啟港，董元和.Windows多線程同步技術(shù)研究［J］.計(jì)算機(jī)與現(xiàn)代化，2006(10):86-89.

［4］［美］Jeffrey Richter，［法］Christophe Nasarre.Windows核心編程［M］.北京:清華大學(xué)出版社，2010.

［5］鐘劍，蔣澤軍，王麗芳，等.實(shí)時(shí)信號(hào)量機(jī)制的研究［J］.現(xiàn)代電子技術(shù)，2012，35(2):40-42，50.

［6］馬魁濤，蔡穎，郭寶峰.Win32進(jìn)程間信息共享的實(shí)現(xiàn)方法研究［J］.計(jì)算機(jī)應(yīng)用與軟件，2007，24(12):119-120，157.

［7］毛德操.Windows內(nèi)核情景分析［M］.北京:電子工業(yè)出版社，2009.

［8］潘漢，莫蘇蘇.基于Local APIC的Windows 2000實(shí)時(shí)化改造［J］.電子元器件應(yīng)用，2009，11(10):79-82.

［9］章秦.Win32多線程同步技術(shù)淺析［J］.電子設(shè)計(jì)工程，2011，19(21):56-58，61.

［10］郭靜寰，孟祥迪，熊木地.多線程同步機(jī)制在應(yīng)用程序與驅(qū)動(dòng)程序通信中的應(yīng)用［J］.微計(jì)算機(jī)信息，2005，21(18):129-131.

［11］孫建杰，陳佳品.臨界區(qū)讀寫鎖的實(shí)現(xiàn)［J］.計(jì)算機(jī)與現(xiàn)代化，2011(9):215-219.

［12］周炎濤，李立明.現(xiàn)代操作系統(tǒng)中的多線程技術(shù)及其應(yīng)用［J］.計(jì)算機(jī)與現(xiàn)代化，2002(7):7-11.

［13］Graunke G，Thakkar S.Synchronization algorithms for sharedmemory multiprocessors［J］.IEEE Computer，1990，23(6):60-69.

［14］王欣明，金蓓弘，張昕.用不對(duì)稱的P/V操作設(shè)計(jì)并發(fā)算法［J］.計(jì)算機(jī)工程與應(yīng)用，2005，41(12):65-69.