死鎖避免之模擬銀行家算法的編程實現

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

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

1 研究背景與意義

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

2 死鎖的產生與避免思路

2.1 死鎖的定義

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

2.2 處理死鎖的方法

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

2.3 銀行家算法

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

3 問題分析與編程實現

3.1 安全性算法流程

（1）先對內容進行初始化，然后輸入進程號和資源數。

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

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

3.2 算法程序的實現

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

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

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

用Security函數判斷是否安全，安全則輸出結果，不安全則輸出并退回資源。

3.3 運行結果

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

4 應用分析

4.1 于銀行貸款中的應用

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

4.2 于網絡爬蟲中的應用

網絡爬蟲資源分配不足會導致發生死鎖，發生死鎖的爬蟲進程無法繼續運行，必須通過釋放爬蟲資源重新抓取網頁信息，因此造成爬蟲算法效率低下。

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

4.3 于旅游業中的應用

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