多線程的應(yīng)用系統(tǒng)避免死鎖

多線程的應(yīng)用系統(tǒng)避免死鎖

應(yīng)用軟件在一個(gè)多級(jí)的應(yīng)用系統(tǒng)環(huán)境中運(yùn)行，同步訪問共享資源是系統(tǒng)安全性的基本要求。其中對(duì)單個(gè)資源進(jìn)行多讀單寫和對(duì)多個(gè)資源進(jìn)行排序鎖定是較常見的同步訪問控制方式,已經(jīng)有了很成熟的算法。但軟件運(yùn)行時(shí)也經(jīng)常需要對(duì)多個(gè)資源進(jìn)行多讀單寫的同步訪問控制,利用當(dāng)前已有的算法已無法解決,需要將讀者-寫者算法和排序鎖定模式結(jié)合,提供一種既能允許對(duì)多個(gè)資源分別多讀單寫,又能避免同時(shí)訪問一個(gè)以上資源時(shí)出現(xiàn)死鎖狀態(tài)的算法。1提出問題1.11.1.1讀者-作家的算法讀者-寫者算法是一類經(jīng)典的同步訪問控制算法,它提供了對(duì)單個(gè)資源進(jìn)行同時(shí)讀或者單獨(dú)寫的訪問控制方式,并保證無寫者死等待。1.1.2免死鎖的發(fā)生排序鎖定模式是為了解決多個(gè)線程共享多個(gè)資源時(shí)如何避免發(fā)生死鎖的問題。它通過破壞死鎖發(fā)生的環(huán)路等待條件(條件4)來避免死鎖的發(fā)生。應(yīng)用該模式時(shí),首先應(yīng)該對(duì)每個(gè)共享資源設(shè)定全局唯一的優(yōu)先級(jí),每個(gè)客戶線程只允許按照指定的順序?qū)Y源進(jìn)行鎖定:一個(gè)線程只能鎖定比它所持有的所有資源優(yōu)先級(jí)低的新資源,如果所持有資源中有比當(dāng)前1申請(qǐng)資源的優(yōu)先級(jí)低的資源時(shí),則對(duì)新資源加鎖的申請(qǐng)不會(huì)立即被實(shí)施,排序鎖定模式將會(huì)拋出一個(gè)加鎖順序異常,由客戶線程捕獲該異常,并對(duì)之進(jìn)行處理。1.2熟的算法的求解針對(duì)軟件經(jīng)常性并發(fā)多讀單寫操作多個(gè)資源而容易造成死鎖問題,目前還沒有一個(gè)成熟的算法可以解決。而讀者-寫者算法解決了對(duì)單個(gè)資源的多讀單寫的同步訪問控制問題,排序鎖定模式提出了一種對(duì)多個(gè)資源進(jìn)行同步訪問并避免發(fā)生死鎖的安全方式,所以將這兩個(gè)方法結(jié)合起來應(yīng)該是解決對(duì)多資源進(jìn)行多讀單寫訪問控制的良好途徑。2資源管理算法排序鎖定模式包括三個(gè)部分(1)管理資源列表,處理從客戶線程發(fā)出的資源訪問申請(qǐng),將其轉(zhuǎn)化為對(duì)具體資源的加鎖請(qǐng)求,并且發(fā)現(xiàn)加鎖順序異常,觸發(fā)處理過程。(2)處理加鎖請(qǐng)求,對(duì)具體資源進(jìn)行多讀單寫方式的加鎖操作。(3)處理申請(qǐng)過程中發(fā)生的異常情況,即處理加鎖順序異常。資源管理算法應(yīng)該將客戶線程的資源申請(qǐng)對(duì)應(yīng)到資源的實(shí)際加鎖和解鎖操作,所以對(duì)于資源的每一種加鎖和解鎖方式,資源管理算法都應(yīng)該有對(duì)應(yīng)的處理請(qǐng)求的接口。為了完成對(duì)單個(gè)資源的多讀單寫訪問方式的控制,我們應(yīng)該將多讀單寫算法以多讀單寫鎖的方式實(shí)現(xiàn),包括讀加鎖、寫加鎖、讀解鎖和寫解鎖四個(gè)調(diào)用方法。相應(yīng)的,資源管理算法也應(yīng)該有四種對(duì)應(yīng)的處理請(qǐng)求方法。算法的結(jié)構(gòu)視圖如下圖1所示:算法中的ResourceClientPolicy表示資源客戶線程,ResourceList表示資源管理器,對(duì)于一個(gè)客戶線程只有一個(gè)資源管理器實(shí)例,ResourcePolicy是資源的多讀單寫鎖,提供對(duì)資源的多讀單寫方式的同步控制,ResourcePolicyImpl是一個(gè)具體的資源類,實(shí)現(xiàn)資源的具體業(yè)務(wù)邏輯,并繼承ResourcePolicy獲得資源鎖。下面我們?cè)敿?xì)介紹資源管理算法中的三個(gè)重要組成部分:多讀單寫鎖,資源管理器和加鎖異常處理算法。2.1記錄特征應(yīng)是受鎖的同步訪問控制多讀單寫鎖算法中加鎖和解鎖的操作可以封裝到單獨(dú)的方法當(dāng)中,實(shí)際使用中具體的資源類只需自定義對(duì)該資源特有的讀寫操作過程,并且繼承該鎖以獲得對(duì)自身的同步訪問控制的方法。算法中應(yīng)該維護(hù)一個(gè)全局的整數(shù)變量,記錄當(dāng)前對(duì)該資源進(jìn)行讀操作的線程數(shù)量,每調(diào)用一次讀加鎖方法時(shí)該變量自增,調(diào)用讀解鎖操作時(shí)自減,在寫鎖加鎖時(shí)作為判斷條件:只有當(dāng)讀者的數(shù)量為0的時(shí)候,寫者線程才能占用該資源,并向其中寫入信息。下面給出多讀單寫鎖算法四個(gè)鎖操作方法的算法描述:2.2加鎖資源的存儲(chǔ)資源管理器首先需要記錄應(yīng)用程序中當(dāng)前資源總數(shù)和它所管理的所有資源的優(yōu)先級(jí);同時(shí),因?yàn)閷?duì)加鎖順序異常的處理過程也在資源管理算法內(nèi)部執(zhí)行,該過程要求資源管理算法必須知道資源的位置,才能對(duì)其進(jìn)行相應(yīng)的鎖操作,所以資源管理器還應(yīng)該記錄每個(gè)資源的地址。在運(yùn)行過程當(dāng)中,對(duì)這些信息的遍歷操作比較頻繁,故而采用適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)存儲(chǔ)這些信息,將會(huì)提高查詢具體資源的效率,從而提高整個(gè)算法的執(zhí)行效率?？紤]到每種資源的優(yōu)先級(jí)是全局唯一的,不可能有兩種資源有相同的優(yōu)先級(jí),因此我們可以采用以資源的優(yōu)先級(jí)作為鍵值的有序數(shù)組(以下稱之為資源數(shù)組)存儲(chǔ)以上信息,數(shù)組的長(zhǎng)度為當(dāng)前資源總數(shù),資源優(yōu)先級(jí)越高,其資源ID越小,在數(shù)組中位置越靠前。當(dāng)有客戶線程向資源管理器發(fā)出資源占用請(qǐng)求時(shí),它必須向相應(yīng)的加鎖申請(qǐng)?zhí)幚矸椒▊鬟f兩個(gè)參數(shù),一個(gè)是該資源的優(yōu)先級(jí),另一個(gè)是該資源指針。加鎖方法首先判斷對(duì)該資源的加鎖請(qǐng)求是否滿足排序鎖定規(guī)則:如果滿足則對(duì)資源進(jìn)行對(duì)應(yīng)的加鎖操作,并將該資源優(yōu)先級(jí)和指針保存到資源數(shù)組中其對(duì)應(yīng)的位置;如果請(qǐng)求不滿足規(guī)則,則轉(zhuǎn)異常處理程序。如果請(qǐng)求解鎖則只需給出該資源的優(yōu)先級(jí),解鎖方法遍歷資源數(shù)組,獲得該資源的指針,對(duì)于寫鎖,首先對(duì)資源做解除寫鎖操作,并直接將資源指針釋放,表示不再占有該資源;對(duì)于讀鎖,在解鎖之后還要判斷該資源的當(dāng)前讀者是否為0,是則釋放該資源指針,否則不作任何操作。2.3異常處理算法當(dāng)發(fā)現(xiàn)加鎖順序違規(guī)時(shí),通常的做法是:解鎖所持有資源當(dāng)中所有比當(dāng)前申請(qǐng)資源優(yōu)先級(jí)低的資源,然后按照優(yōu)先級(jí)由高到低的順序從當(dāng)前申請(qǐng)資源開始重新鎖定這些資源。對(duì)于讀操作和寫操作,該算法的邏輯并沒有太大區(qū)別,因此可以將異常處理過程設(shè)計(jì)成對(duì)讀寫操作公用的算法,為了判斷用戶對(duì)所持有資源正在進(jìn)行的是那種操作,以便作出相應(yīng)的解鎖操作,我們用一個(gè)有序數(shù)組保留了每個(gè)所持有資源當(dāng)前的讀者數(shù)量,當(dāng)讀者數(shù)量大于0時(shí),說明當(dāng)前客戶對(duì)該資源正在進(jìn)行讀操作,應(yīng)該解除讀鎖,當(dāng)讀者數(shù)量為0時(shí),說明當(dāng)前對(duì)該資源應(yīng)該正在進(jìn)行寫操作,應(yīng)該解除寫鎖。當(dāng)異常處理過程被調(diào)用時(shí),首先遍歷資源優(yōu)先級(jí)數(shù)組,獲得當(dāng)前優(yōu)先級(jí)最低資源的指針,然后判斷其讀者數(shù)量是否為0,根據(jù)比較結(jié)果作相對(duì)應(yīng)的解鎖操作,循環(huán)該過程,直到所有優(yōu)先級(jí)低于當(dāng)前請(qǐng)求資源的資源都已經(jīng)被釋放,然后對(duì)當(dāng)前請(qǐng)求資源進(jìn)行加鎖,最后按照順序?qū)?yōu)先級(jí)低于當(dāng)前請(qǐng)求資源的資源按照排序順序恢復(fù)加鎖,在恢復(fù)加鎖時(shí)也應(yīng)該通過資源的讀者數(shù)量決定應(yīng)該進(jìn)行哪種加鎖操作。下面給出異常處理算法描述:以上定義了UnlockHighorderResource()方法,該方法負(fù)責(zé)對(duì)所持有的低優(yōu)先級(jí)資源進(jìn)行順序解鎖,該方法中g(shù)etMaxID()方法負(fù)責(zé)獲得資源管理器列表當(dāng)中當(dāng)前最低優(yōu)先級(jí)資源(資源ID最大),getResource()方法根據(jù)資源ID返回該資源的指針,此后可以通過GetReadCount()方法返回當(dāng)前該資源的讀者數(shù)量,以判斷應(yīng)當(dāng)對(duì)該資源解除讀鎖還是寫鎖,并調(diào)用相應(yīng)的解鎖方法,同時(shí)還應(yīng)該將這個(gè)數(shù)量記錄下來以備恢復(fù)加鎖時(shí)判斷應(yīng)該是加讀鎖還是寫鎖。以上定義了RestoreHighorderResource()方法,實(shí)現(xiàn)對(duì)所持有的低優(yōu)先級(jí)資源進(jìn)行順序恢復(fù)加鎖的過程。上述兩個(gè)方法共同提供了異常處理算法當(dāng)中的公有操作,使用時(shí)由處理加鎖請(qǐng)求的方法調(diào)用UnlockHighorderResource()方法對(duì)低優(yōu)先級(jí)資源進(jìn)行解鎖,然后對(duì)當(dāng)前申請(qǐng)資源進(jìn)行加鎖(由于加鎖請(qǐng)求方法分為讀加鎖請(qǐng)求和寫加鎖請(qǐng)求兩個(gè),因此它當(dāng)然知道應(yīng)該對(duì)當(dāng)前請(qǐng)求資源加哪種鎖),之后再調(diào)用RestoreHighorderResource()方法恢復(fù)對(duì)UnlockHighorderResource()方法釋放的資源加鎖。3基于平臺(tái)的禁止時(shí)間效率算法中用一個(gè)ResourcePolicy類來實(shí)現(xiàn)多讀單寫鎖,資源類繼承ResourcePolicy以獲得它定義的StartRead(),EndRead(),StartWrite(),EndWrite()四個(gè)多讀單寫的訪問控制方法。ResourceList類實(shí)現(xiàn)了資源管理器,其中我們將資源ID和資源指針的信息用vector類型來存儲(chǔ),對(duì)比于使用數(shù)組的方式,使用vector固然會(huì)犧牲一定的空間效率,但是對(duì)于遍歷操作它比數(shù)組的效率要高,因此當(dāng)資源較多的情況下,算法的時(shí)間效率將會(huì)獲得顯著的提高。Semaphore類定義了信號(hào)量類的接口,是一個(gè)純虛類,只有兩個(gè)純虛函數(shù)lock()和unlock()的定義,其子類SemaphoreMFCImpl類使用MFC的semaphore類提供信號(hào)量操作的windows平臺(tái)下的實(shí)現(xiàn)方式,從而屏蔽了與平臺(tái)相關(guān)的具體實(shí)現(xiàn)信息。ResourcePolicy是通過調(diào)用它的lock和unlock操作來實(shí)現(xiàn)其StartRead