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

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

1 研究背景與意義

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

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

2.1 死鎖的定義

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

2.2 處理死鎖的方法

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

2.3 銀行家算法

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

3 問題分析與編程實現(xiàn)

3.1 安全性算法流程

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

（2）request請求矩陣與Avaliable資源，Need需求矩陣判斷，如果請求矩陣小于它們則進行，否則Error報錯。

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

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

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

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

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

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

3.3 運行結(jié)果

對演視樣例編譯，其中輸入的第一個參數(shù)為該資源中的第幾個進程，第二個參數(shù)，第三個參數(shù)等為目前的資源數(shù)量，由圖1得需求矩陣，同時得到當前可利用資源數(shù)量{2，3，3}。輸入選擇當前小于可利用資源數(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，運行P1即{1，3，4，7}以此類推，驗證求得如下運行結(jié)果如下，序列P5->P1->P2->P3->P4符合要求：

4 應(yīng)用分析

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

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

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

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

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

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

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