QUESTION:銀行家算法總結及實現(xiàn)?

目錄

QUESTION:銀行家算法總結及實現(xiàn)?

ANSWER:

一：銀行家算法介紹

1.1什么是銀行家算法

1.2背景

1.3數(shù)據(jù)結構

1.4算法分析

二：安全狀態(tài)和不安全狀態(tài)

2.1概念

2.2安全性檢查

三：算法實現(xiàn)

3.1流程圖

3.2代碼實現(xiàn)

---

ANSWER:

一：銀行家算法介紹

1.1什么是銀行家算法

銀行家算法（Banker's Algorithm）是一種關于操作系統(tǒng)分配資源時避免死鎖（Deadlock）產(chǎn)生的安全性檢測算法，它類似于銀行中貸款的分配策略，由艾茲格·迪杰斯特拉在1965年為T.H.E系統(tǒng)設計的一種避免死鎖產(chǎn)生的算法。

1.2背景

在銀行中，客戶為了完成某個項目需要向銀行進行貸款申請，客戶已經(jīng)擁有部分資金，客戶給出最大資金需求，銀行進行對客戶的貸款申請檢查，如果客戶完全滿足申請條件，并且客戶申請的資金小于銀行擁有的資金總額，則完成對客戶的貸款。在這一過程中，銀行就像操作系統(tǒng)，客戶就像進程，資金就像要申請的資源。

1.3數(shù)據(jù)結構

1.資源種類數(shù)R：

是一個定量，R=n代表有n種資源。

2.進程數(shù)P：

也是一個定量，P=n代表有n個進程。

3.可利用的資源數(shù)向量Available：

是一個一維向量，Available[n]=k,代表n類資源可利用資源數(shù)為k。

4.最大需求矩陣Max:

是一個二維矩陣，Max[n][m]=k,代表第n個進程需要m類的最大數(shù)目為k。

5.已經(jīng)分配的資源數(shù)目矩陣Allocation:

是一個二維矩陣，Allocation[n][m]=k,代表n個進程已經(jīng)分配m類資源的數(shù)目為k。

6.需求矩陣Need:

是一個二維向量，Need[n][m]=k，代表進程n還需要m類資源的數(shù)目為k。

Need[n][m]=Max[n][m]-Allocation[n][m]。

1.4算法分析

為保證資金的安全，銀行家規(guī)定：

(1) 當一個顧客對資金的最大需求量不超過銀行家現(xiàn)有的資金時就可接納該顧客；

(2) 顧客可以分期貸款，但貸款的總數(shù)不能超過最大需求量；

(3) 當銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時，對顧客的貸款可推遲支付，但總能使顧客在有限的時間里得到貸款；

(4) 當顧客得到所需的全部資金后，一定能在有限的時間里歸還所有的資金.

操作系統(tǒng)按照銀行家制定的規(guī)則為進程分配資源，當進程首次申請資源時，要測試該進程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當前的申請量分配資源，否則就推遲分配。當進程在執(zhí)行中繼續(xù)申請資源時，先測試該進程本次申請的資源數(shù)是否超過了該資源所剩余的總量。若超過則拒絕分配資源，若能滿足則按當前的申請量分配資源，否則也要推遲分配。

Allocation　　　Max　　　AvailableＡＢＣＤ　　 ＡＢＣＤ　　ＡＢＣＤP1 ００１４　　 ０６５６　　１５２０　P2　 １４３２　　 １９４２　P3　 １３５４　 　１３５６P4 　１０００　　 １７５０

我們會看到一個資源分配表，要判斷是否為安全狀態(tài)，首先先找出它的Need，Need即Max(最多需要多少資源)減去Allocation(原本已經(jīng)分配出去的資源)，計算結果如下：

NEEDＡＢＣＤ０６４２　０５１００００２０７５０

然后加一個全都為false的字段：

FINISHfalsefalsefalsefalse

接下來找出Need比Available小的(千萬不能把它當成4位數(shù) 他是4個不同的數(shù))：

NEED　　 AvailableＡＢＣＤ　　ＡＢＣＤ０６４２　　１５２００５１０<-０００２０７５０

P2的需求小于能用的，所以分配給他再回收：

NEED　　 AvailableＡＢＣＤ　　ＡＢＣＤ０６４２　　１５２０００００　＋１４３２０００２－－－－－－－０７５０　　２９５２

此時P2 FINISH的false要改成true(己完成)：

FINISHfalsetruefalsefalse

接下來繼續(xù)往下找，發(fā)現(xiàn)P3的需求為0002，小于能用的2952，所以資源配置給他再回收：

　NEED　　 AvailableＡＢＣＤ　　Ａ　Ｂ　Ｃ　Ｄ０６４２　　２　９　５　２００００　＋１　３　５　４００００－－－－－－－－－－０７５０　　３　12　10　6

依此類推，做完P4→P1，當全部的FINISH都變成true時，就是安全狀態(tài)。

二：安全狀態(tài)和不安全狀態(tài)

2.1概念

如果所有過程有可能完成執(zhí)行（終止），則一個狀態(tài)（如上述范例）被認為是安全的。由于系統(tǒng)無法知道什么時候一個過程將終止，或者之后它需要多少資源，系統(tǒng)假定所有進程將最終試圖獲取其聲明的最大資源并在不久之后終止。在大多數(shù)情況下，這是一個合理的假設，因為系統(tǒng)不是特別關注每個進程運行了多久（至少不是從避免死鎖的角度）。此外，如果一個進程終止前沒有獲取其它能獲取的最多的資源，它只是讓系統(tǒng)更容易處理。

基于這一假設，該算法通過嘗試尋找允許每個進程獲得的最大資源并結束（把資源返還給系統(tǒng)）的進程請求的一個理想集合，來決定一個狀態(tài)是否是安全的。不存在這個集合的狀態(tài)都是不安全的。

安全序列是指一個進程序列{P1，…，Pn}是安全的，即對于每一個進程Pi(1≤i≤n），它以后尚需要的資源量不超過系統(tǒng)當前剩余資源量與所有進程Pj (j < i )當前占有資源量之和。

如果存在一個由系統(tǒng)中所有進程構成的安全序列P1，…，Pn，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒有死鎖發(fā)生。

不存在一個安全序列。不安全狀態(tài)不一定導致死鎖。

2.2安全性檢查

1)設置兩個工作向量Work=AVAILABLE;FINISH

(2)從進程集合中找到一個滿足下述條件的進程，

FINISH==false;

NEED<=Work;

如找到，執(zhí)行（3)；否則，執(zhí)行（4)

(3)設進程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。

Work=Work+ALLOCATION;

Finish=true;

GOTO 2

(4)如所有的進程Finish= true，則表示安全；否則系統(tǒng)不安全。

?

三：算法實現(xiàn)

3.1流程圖

3.2代碼實現(xiàn)

?

?

?

?

總結

以上是生活随笔為你收集整理的银行家算法总结及实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。