死鎖避免之模擬銀行家算法的編程實(shí)現(xiàn)

劉暢，文家俊，賈海鵬，徐艷

（四川大學(xué)錦城學(xué)院計(jì)算機(jī)與軟件學(xué)院，四川成都，611731）

1 研究背景與意義

在進(jìn)程運(yùn)行中，經(jīng)常出現(xiàn)多方進(jìn)程都需要同一資源時(shí)，各方都希望其它進(jìn)程能釋放出所需要的資源，從而所有進(jìn)程都無(wú)法獲得所需要的資源而沒(méi)有繼續(xù)運(yùn)行，也導(dǎo)致都無(wú)法釋放出其占有的資源，且會(huì)一直在該狀態(tài)，最后形成死鎖。而形成它的四個(gè)條件有互斥，不可搶占，占有和等待，環(huán)路等待等條件[1]。Dijkstra的銀行家算法原本是為了銀行的系統(tǒng)設(shè)計(jì)的，是為了保證銀行能順利的發(fā)放貸款，在操作系統(tǒng)中也可以解決系統(tǒng)資源問(wèn)題，使多進(jìn)程進(jìn)入安全狀態(tài)，能夠有效的避免死鎖和合理的分配資源給多個(gè)進(jìn)程[2]，從而避免了死鎖。

2 死鎖的產(chǎn)生與避免思路

2.1 死鎖的定義

死鎖，其實(shí)便是一組多個(gè)進(jìn)程在運(yùn)行過(guò)程中因爭(zhēng)奪臨界資源而導(dǎo)致的一種僵局。因此可以給死鎖做出如下的定義：如果一組進(jìn)程中的每一個(gè)進(jìn)程都在等待僅由該組進(jìn)程中的其它進(jìn)程才能引發(fā)的事件，那么該組進(jìn)程是死鎖的（Deadlock）。[3]

2.2 處理死鎖的方法

（1）預(yù)防死鎖，事先采取某種限制措施，破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或多個(gè)來(lái)預(yù)防死鎖。（2）避免死鎖，在資源動(dòng)態(tài)分配過(guò)程中，防止系統(tǒng)進(jìn)入不安全狀態(tài)，來(lái)避免發(fā)生死鎖。（3）檢測(cè)死鎖，允許進(jìn)程在運(yùn)行時(shí)產(chǎn)生死鎖，但在產(chǎn)生死鎖后可及時(shí)通過(guò)檢測(cè)機(jī)構(gòu)檢測(cè)出死鎖，并采用適當(dāng)措施，從而解決死鎖。4.解除死鎖，當(dāng)檢測(cè)到進(jìn)程中已經(jīng)有死鎖后，采用相應(yīng)措施，解除進(jìn)程的死鎖。

2.3 銀行家算法

避免死鎖有鴕鳥(niǎo)算法，有序資源分配法，銀行家算法。其中最著名的便是Dijkstra的銀行家算法。是由艾茲格·迪杰斯特拉在1965年為T.H.E系統(tǒng)設(shè)計(jì)的一種避免死鎖產(chǎn)生的算法。它以銀行借貸系統(tǒng)的分配策略為基礎(chǔ)，判斷并保證系統(tǒng)的安全運(yùn)行。

3 問(wèn)題分析與編程實(shí)現(xiàn)

3.1 安全性算法流程

（1）先對(duì)內(nèi)容進(jìn)行初始化，然后輸入進(jìn)程號(hào)和資源數(shù)。

（2）request請(qǐng)求矩陣與Avaliable資源，Need需求矩陣判斷，如果請(qǐng)求矩陣小于它們則進(jìn)行，否則Error報(bào)錯(cuò)。

（3）判斷需求矩陣是否為0，當(dāng)為0時(shí)，使q[n]=1,a=a-1,Avalab+=max.否則直接進(jìn)入search查詢，得出是否為安全狀態(tài)，若是不安全狀態(tài)則略過(guò)重復(fù)步驟1。

3.2 算法程序的實(shí)現(xiàn)

銀行家算法目前的已知條件是：系統(tǒng)的總資源，已分配的資源，最大的需求資源，仍需要的資源。以下是用C語(yǔ)言為主體編寫的程序。

Work用于存儲(chǔ)當(dāng)前可用資源。按順序判斷每個(gè)沒(méi)有結(jié)束的進(jìn)程是否能完成，count用來(lái)統(tǒng)計(jì)可以完成的進(jìn)程數(shù)，a代表進(jìn)程數(shù)，如果count和a相等，說(shuō)明系統(tǒng)是安全的。只循環(huán)一次是不夠的，最多需要循環(huán)a次，所以當(dāng)循環(huán)要結(jié)束時(shí)令i=-1重新開(kāi)始循環(huán)直到循環(huán)a次還有未完成的進(jìn)程說(shuō)明系統(tǒng)是不安全的。

輸入每種資源的需求數(shù)量，判斷輸入是否合理并分配資源。如果分配不合理，則退回資源。z1=1時(shí)表示輸入的數(shù)據(jù)不合規(guī)范分配出錯(cuò)，z1=0則分配正常。如果需求資源=0，說(shuō)明進(jìn)程執(zhí)行結(jié)束，退回資源。

用Security函數(shù)判斷是否安全，安全則輸出結(jié)果，不安全則輸出并退回資源。

3.3 運(yùn)行結(jié)果

對(duì)演視樣例編譯，其中輸入的第一個(gè)參數(shù)為該資源中的第幾個(gè)進(jìn)程，第二個(gè)參數(shù)，第三個(gè)參數(shù)等為目前的資源數(shù)量，由圖1得需求矩陣，同時(shí)得到當(dāng)前可利用資源數(shù)量{2，3，3}。輸入選擇當(dāng)前小于可利用資源數(shù)的序列，在輸入{1，3，4，7}，{2，1，3，4}，{3，0，0，6}，{4，2，2，1}，{5，1，1，0}中有P5即{5，1，1，0}，然后釋放P5，運(yùn)行P1即{1，3，4，7}以此類推，驗(yàn)證求得如下運(yùn)行結(jié)果如下，序列P5->P1->P2->P3->P4符合要求：

4 應(yīng)用分析

4.1 于銀行貸款中的應(yīng)用

貸款是銀行或其他金融機(jī)構(gòu)按一定利率和必須歸還等條件出借貨幣資金的一種信用活動(dòng)形式。由于一定數(shù)量的貨幣需要在多個(gè)客戶之間借貸周轉(zhuǎn)，銀行家算法可以有效防止銀行資金無(wú)法周轉(zhuǎn)從而倒閉，對(duì)每一筆貸款都要考察是否能按期歸還。在銀行貸款中，銀行的流動(dòng)貨幣是有限的，客戶想申請(qǐng)貸款時(shí)，第一次必須要聲明自己所需的貨幣量，客戶也需要按時(shí)還款。在銀行貸款中，這個(gè)規(guī)則就是操作系統(tǒng)，銀行的流動(dòng)貨幣就是系統(tǒng)中的資源，而客戶就是需要資源申請(qǐng)資源的進(jìn)程。

4.2 于網(wǎng)絡(luò)爬蟲(chóng)中的應(yīng)用

網(wǎng)絡(luò)爬蟲(chóng)資源分配不足會(huì)導(dǎo)致發(fā)生死鎖，發(fā)生死鎖的爬蟲(chóng)進(jìn)程無(wú)法繼續(xù)運(yùn)行，必須通過(guò)釋放爬蟲(chóng)資源重新抓取網(wǎng)頁(yè)信息，因此造成爬蟲(chóng)算法效率低下。

死鎖是多用戶操作系統(tǒng)正常運(yùn)行的一個(gè)重要問(wèn)題，系統(tǒng)資源不足會(huì)導(dǎo)致爬蟲(chóng)算法進(jìn)入不安全狀態(tài)，進(jìn)而引發(fā)死鎖等問(wèn)題。引入被廣泛用于操作系統(tǒng)的銀行家算法，調(diào)度多個(gè)網(wǎng)絡(luò)爬蟲(chóng)進(jìn)程并發(fā)運(yùn)行，并且為每個(gè)進(jìn)程合理分配系統(tǒng)資源，當(dāng)進(jìn)程無(wú)法獲取系統(tǒng)資源時(shí)，則等待其他進(jìn)程分配完成后釋放系統(tǒng)資源，從而完成資源分配，有效降低死鎖率。而死鎖率的降低就等于提高了爬蟲(chóng)算法的效率，合理分配了資源。

4.3 于旅游業(yè)中的應(yīng)用

游客分流管理作為游客管理中的一方面，對(duì)景區(qū)游客分配、景點(diǎn)科學(xué)設(shè)置都有著重要作用。由于景區(qū)對(duì)游客和各類資源分配不合理，所以景區(qū)也同樣存在擁堵的問(wèn)題。本質(zhì)上看，兩者都是因?yàn)楣芾碚邲](méi)有采用合理方法對(duì)目標(biāo)對(duì)象進(jìn)行合理配置造成的[4]。這個(gè)問(wèn)題的本質(zhì)就是資源的分配和管理。在這個(gè)問(wèn)題中，游客可以看作進(jìn)程申請(qǐng)資源，景區(qū)各個(gè)景點(diǎn)可以看作系統(tǒng)資源，銀行家算法就應(yīng)用到了問(wèn)題中，通過(guò)固定的算法對(duì)景區(qū)進(jìn)行管理，就會(huì)解決景區(qū)中的“死鎖”問(wèn)題。