作業系統課程設計之模擬通過銀行家演算法避免死鎖

模擬通過銀行家演算法避免死鎖

一、銀行家演算法產生的背景及目的

1：在多道程式系統中，雖然節奏、雖然借助於多個程序的併發執行來改善系統的利用率，提高系統的吞吐量，但可能發生一種危險—死鎖。，死鎖就是多個程序在執行過程中因爭奪資源而造成的一種僵局，當程序處於這種

僵局狀態時，如無外力作用，他們將無法再向前進行，如再把訊號量作為同步工具時，多個wait和signal操作順序不當，會產生程序死鎖。

然而產生死鎖的必要條件有互斥條件，請求和保持條件，不剝奪條件和環路等待條件。在預防死鎖的幾種方法中，都施加了較強的限制條件，在避免死鎖的方法中，所施加的條件較弱，有可能獲得令人滿意的系統效能。在該方法中把系統的狀態分為安全狀態和不安全狀態，只要能使系統都處於安全狀態，便可避免死鎖。

2：實驗目的：讓學生獨立的使用程式語言編寫和除錯乙個系統分配資源的簡單模擬程式，了解死鎖產生的原因及條件。

採用銀行家演算法及時避免死鎖的產生，進一步理解課堂上老師講的相關知識點。銀行家演算法是從當前狀態出發，逐個按安全序列檢查各客戶中誰能完成其工作，然後假定其完成工作且歸還全部貸款，再進而檢查下乙個能完成工作的客戶。如果所有客戶都能完成工作，則找到乙個安全序列，銀行家才是安全的。

二：銀行家演算法中的資料結構

1：可利用資源向量**ailable。這是乙個含有m個元素的陣列，其中的每個元素代表一類可利用的資源數目，其初始值是系統中所配置的該類全部可用資源的數目，其數值隨該類資源的分配和**而動態的改變。

如果**ailable[j]=k，z

則表示系統中現有rj類資源k 個。

2：最大需求矩陣max。這是乙個n*m的矩陣，它定義了系統中n個程序中的每乙個程序對m類資源的最大需求。如果max[i,j]=k，表示第i個程序需要第rj類資源的最大數目k個.

3: 分配矩陣allocation,也是n*m的矩陣，若allocation[i,j]=k,表示第i

個程序已分配rj類資源的數目為k個。

4：需求矩陣need。也是乙個n*m的矩陣，need[i,j]=k,表示第i個程序還需rj類資源k個。

三、銀行家演算法及安全性演算法

1：銀行家演算法

設request[i]是程序pi的請求向量，若request[i][j]=k;表示程序需要j類資源k個。當pi發出資源請求時，系統按下屬步驟進行檢查；

(1) 如果request[i][j]<=need[i][j];便轉向步驟（2），否則認為出錯，因為它所需要的資源數已超過他所宣布的最大值。

(2) 如果request[i][j]<=**ailable[i][j],便轉向步驟（3），否則認為尚無足夠資源，程序需等待。

(3) 系統試探著把資源分配給程序，並修改下面資料結構的資料

**ailable[i][j]=**ailable[i][j]-request[i][j];

allocation[i][j]=allocation[i][j]+request[i][j];

need[i][j]=need[i][j]-request[i][j];

(4) 系統執行安全性演算法，檢查此次資源分配後系統是否處於安全狀態。若安全，才正式將資源分配給程序pi，已完成此次分配。否則，將本次的試探分配作廢，回覆原來的資源分配狀態，將程序pi等待。

2：安全性演算法

（1）設定兩個向量；

1：工作向量work，表示系統可提供給程序執行所需的各類資源數目，它含有m個元素，初始時work=**ailable

2：finish ,表示系統是否有足夠的資源分配給程序，使之執行完成。開始時先做finish[i]=true

（2）從程序中找到乙個能滿需下屬條件的程序

1；finish[i]=false；

2：need[i][j]<=work[j];若找到執行步驟（3），否則執行步驟（4）

（3）當程序pi順利獲得資源後，直至完成，並釋放分配給它的資源，執行：

work[j]=work[j]+allocation[i][j];

finish[i]=true;

go to step (2);

(5) 如果所有的程序finish[i]都滿足，則表示系統處於安全狀態，否則，處於不安全狀態。

四、模組設計與分析及整體功能概述

模組設計與分析：

整個銀行家演算法分為初始化函式init（），安全性演算法函式 safe（），銀行家演算法函式bank（）三部分。初始化函式生成開始時刻系統中的程序和資源情況，安全性演算法判斷當某程序申請資源時，系統能否處於安全狀態。在本實驗中，若系統處於安全狀態，便生成乙個安全程序序列（安全序列可能有多個）。

銀行家演算法函式bank（）負責整體的檢查與異常判斷。

整體功能概述：

死鎖會引起系統陷入僵局，作業系統必須防止此現象的發生。本實驗通過乙個動態分配資源的模擬程式，更清楚的理解死鎖產生的原因和條件。dijkstra的銀行家演算法是最有代表性的避免死鎖的方法。

執行程式時使用者設定系統中程序和可利用資源的種類數目。輸入各程序的可利用資源**ailable，最大需求max，已分配資源allocation ，需求資源need，之後各系統發出資源請求request，利用實驗中的安全性演算法判斷能否產生乙個安全性佇列，若能，則給該程序分配成功，否則，不予分配。

五、流程圖設計

六、源**及除錯分析

#include<>

#define maxm 50定義最大程序數

#define maxn 100定義最大資源數

int max[maxm][maxn最大需求矩陣

int allocation[maxm][maxn]; //已分配矩陣

int **ailable[maxn可用資源陣列

int need[maxm][maxn需求矩陣

int request[maxm][maxn請求矩陣

int finish[maxm儲存完成資源分配的程序

int sequence[maxm模擬的資源分配序列

int work[maxn系統是否有足夠的資源分配給程序

int m,nm個程序,n個資源

#define false 0

#define true 1

void input(); //資料輸入函式

int safealg(); //安全性演算法函式

void banker(); //銀行家演算法函式

void main()

初始化演算法

void input()

}cout<<"各程序當前獲得資源(allocation),按照"< for(i=0;i

}cout<<"系統可用資源(**ailable):"< for(j=0;j

cout<<"當前時刻的程序分配情況如圖：\n";

cout<<"程序號-"<<"max----"<<"allocation---"<<"need--"<<"**ailable---\n";//顯示各程序的資源情況

for(i=0;i

}銀行家演算法，為程序分配資源

void banker()

{ int i,j;

int choice;

while(1)

{cout<

作業系統課程設計之模擬通過銀行家演算法避免死鎖

作業系統課程設計指導

作業系統課程設計報告

作業系統課程設計報告

作業系統課程設計之模擬通過銀行家演算法避免死鎖

作業系統課程設計指導

作業系統課程設計報告

作業系統課程設計報告

相關推薦