操作系統(tǒng)實(shí)驗(yàn)二死鎖避免之銀行家算法的模擬

這篇具有很好參考價(jià)值的文章主要介紹了操作系統(tǒng)實(shí)驗(yàn)二死鎖避免之銀行家算法的模擬。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

文章目錄

死鎖

?（1）定義

?（2）死鎖產(chǎn)生的原因

?（3）死鎖產(chǎn)生的必要條件

?（4）死鎖的處理策略

銀行家算法

?（1）核心思想

?（2）數(shù)據(jù)結(jié)構(gòu)

?（3）算法描述

?? (4)? 安全性檢查算法

銀行家算法的模擬

（1）數(shù)據(jù)結(jié)構(gòu)

（2）完整代碼

（3）測(cè)試

死鎖

（1）定義

所謂死鎖，是指多個(gè)進(jìn)程因?yàn)楦?jìng)爭(zhēng)資源而導(dǎo)致的一種互相循環(huán)等待的“僵局”，若無外力作用調(diào)整，這些進(jìn)程都無法向前推進(jìn)運(yùn)行。

如下圖所示，在十字路口，甲車在等著乙車來讓道給自己通行，但乙車司機(jī)脾氣暴躁就是不讓也在等待著甲車讓道給自己通行，互相等待，誰都不讓道，從而造成一種擁堵的僵局現(xiàn)象，這就是生活中常見的死鎖現(xiàn)象。

操作系統(tǒng)實(shí)驗(yàn)二死鎖避免之銀行家算法的模擬

?（2）死鎖產(chǎn)生的原因

系統(tǒng)資源的競(jìng)爭(zhēng)

進(jìn)程推進(jìn)的順序非法

信號(hào)量使用不當(dāng)

（3）死鎖產(chǎn)生的必要條件

操作系統(tǒng)實(shí)驗(yàn)二死鎖避免之銀行家算法的模擬

互斥條件：進(jìn)程要求對(duì)所分配的資源進(jìn)行排他性使用，即在某段時(shí)間內(nèi)某種資源只能被一種進(jìn)程獨(dú)自使用

不可剝奪條件：進(jìn)程在獲得資源后不能被其它進(jìn)程強(qiáng)行奪走，而是由自己主動(dòng)釋放

請(qǐng)求并保持條件：進(jìn)程已經(jīng)保持了一種資源，但又提出了新的資源請(qǐng)求，而該資源已經(jīng)被其它進(jìn)程所占用，此時(shí)請(qǐng)求進(jìn)程被阻塞，但對(duì)自己已經(jīng)獲得的資源保持不放

循環(huán)等待條件：存在一種進(jìn)程資源的循環(huán)等待鏈，鏈中的每個(gè)進(jìn)程所獲得的資源同時(shí)被下一個(gè)資源所請(qǐng)求。如上圖2-15所示

（4）死鎖的處理策略

死鎖預(yù)防：設(shè)置某些限制條件，破壞產(chǎn)生死鎖4個(gè)必要條件中的一個(gè)或幾個(gè)

死鎖避免：在資源的動(dòng)態(tài)分配中，用某種方法防止系統(tǒng)進(jìn)入不安全狀態(tài)

死鎖的檢測(cè)與解除：無需采用任何的限制性措施，允許進(jìn)程發(fā)生死鎖。通過系統(tǒng)的檢測(cè)機(jī)制來檢測(cè)到死鎖，并采取某種措施來解除死鎖

而下面所講的銀行家算法就屬于死鎖避免算法的一種。

銀行家算法

（1）核心思想

????????銀行家算法是最著名的死鎖避免算法，其思想是:把操作系統(tǒng)視為銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資源相當(dāng)于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源。進(jìn)程運(yùn)行之前先聲明對(duì)各種資源的最大需求量，當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程已占用的資源數(shù)與本次申請(qǐng)的資源數(shù)之和是否超過該進(jìn)程聲明的最大需求量。若超過則拒絕分配資源，若未超過則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。

（2）數(shù)據(jù)結(jié)構(gòu)

可用資源向量Available：長(zhǎng)度為n的數(shù)組表示系統(tǒng)中n類資源的當(dāng)前可用數(shù)目。如果Available[j]=k，表示系統(tǒng)中現(xiàn)有Rj類資源為k個(gè)。

最大需求矩陣Max：m×n矩陣定義m個(gè)進(jìn)程對(duì)n類資源的最大需求量。如Max[i,j]=k，表示進(jìn)程Pi運(yùn)行期間最多需求Rj資源的數(shù)目為k個(gè)。

已分配資源矩陣Allocation：m×n矩陣定義了每個(gè)進(jìn)程現(xiàn)在已分配到的各類資源的實(shí)際數(shù)目。如果Allocation [i,j]=k，表示進(jìn)程Pi當(dāng)前分到k個(gè)Rj類資源。

?需求矩陣Need：m×n矩陣表示每個(gè)進(jìn)程還需要的各類資源的數(shù)目。如果Need [i, j]=k，表示進(jìn)程Pi尚需k個(gè)Rj類資源才能完成其任務(wù)。很顯然，Need[i,j]=Max[i,j] - Allocation[i,j]，因而，這些數(shù)據(jù)結(jié)構(gòu)的大小和值會(huì)隨著時(shí)間而改變。

?其中，Need=Max-Allocation

?（3）算法描述

設(shè)Requesti表示進(jìn)程Pi的資源申請(qǐng)向量。如Requesti[j]= k，表示進(jìn)程Pi動(dòng)態(tài)申請(qǐng)k個(gè)Rj類資源。當(dāng)進(jìn)程Pi申請(qǐng)資源時(shí)，就執(zhí)行下列動(dòng)作（試探性分配）:

若Requesti[j]＞Need[i,j]，產(chǎn)生出錯(cuò)條件，因?yàn)檫M(jìn)程Pi對(duì)資源的請(qǐng)求量已超過其說明的最大數(shù)量；否則，轉(zhuǎn)到步驟2。

如果Requesti[j]＞Available[j]，則進(jìn)程Pi必須等待，這是因?yàn)橄到y(tǒng)現(xiàn)在沒有可用的資源；否則，轉(zhuǎn)到步驟3。

如果系統(tǒng)可以給進(jìn)程Pi分配所請(qǐng)求的資源，則應(yīng)對(duì)有關(guān)數(shù)據(jù)結(jié)構(gòu)進(jìn)行修改：
??????? Available[j] = Available[j]-Requesti[j];?? (j=1,2,……,n)
??????? Allocation[i,j] = Allocation[i,j] + Requesti[j];?? (i=1,2,……,m)
??????? Need[i,j] = Need[i,j] - Requesti[j];

系統(tǒng)執(zhí)行安全性檢查，查看此時(shí)系統(tǒng)狀態(tài)是否安全。如果安全，就給進(jìn)程Pi 實(shí)際分配資源；否則，即系統(tǒng)是不安全的，則Pi等待，作廢本次試探性分配，并且把資源分配狀態(tài)恢復(fù)成3之前的情況。

(4)安全性檢查算法

????????安全性檢查算法是銀行家算法的核心，在銀行家算法的習(xí)題中，一般會(huì)有某個(gè)進(jìn)程發(fā)出一個(gè)資源請(qǐng)求向量，我們只需要執(zhí)行上面銀行家算法的前三步，就會(huì)得到一個(gè)更新后的Allocation和Need矩陣，再按照上例的安全性算法進(jìn)行判斷，此時(shí)系統(tǒng)是否處于安全狀態(tài)，就能直到系統(tǒng)是否能立即滿足該進(jìn)程提出的資源請(qǐng)求。

一般步驟如下：

設(shè)置兩個(gè)向量：工作向量Work：表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需要的各類資源數(shù)目，長(zhǎng)度為n；進(jìn)程完成標(biāo)志向量Finish：長(zhǎng)度為m，表示各個(gè)進(jìn)程是否能夠得到足夠的資源并運(yùn)行完成。兩個(gè)向量初始化：Work=Available，Finish[i]=false (i=1,2,...m)

從進(jìn)程集合中搜尋滿足下列條件的進(jìn)程（找安全進(jìn)程序列）：Finish[i] ==false且Need[i，j]≤Work[j]。如果找到這樣的進(jìn)程，執(zhí)行3；否則，則轉(zhuǎn)向步驟4。

修改數(shù)據(jù)值:Work[j]=Work[j] + Allocation[i,j]（進(jìn)程Pi釋放所占的全部資源）；Finish[i]=true；返回步驟2

安全狀態(tài)的判定：如果所有進(jìn)程的Finish[i] ==true都成立（找著安全序列），則系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。

銀行家算法的模擬

（1）數(shù)據(jù)結(jié)構(gòu)

//定義銀行家算法的數(shù)據(jù)結(jié)構(gòu) 
int Available[3]={3,3,2};//系統(tǒng)可用資源 
int Max[5][3]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};//進(jìn)程最大資源需求量 
int Allocation[5][3]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};//系統(tǒng)已經(jīng)給進(jìn)程分配的資源 
int Need[5][3]={{7,4,3},{1,2,2},{6,0,0},{0,1,1},{4,3,1}};//進(jìn)程的資源最大需求量 
int Work[3];//安全性檢查算法中的工作向量 
int Finish[5]={0,0,0,0,0};//進(jìn)程執(zhí)行完成的標(biāo)志 
int SafeArray[5];//安全序列 
int Request[3];//請(qǐng)求資源向量

（2）完整代碼

/*
	模擬銀行家算法，進(jìn)行死鎖的避免 
*/
#include<iostream>
using namespace std;
//定義銀行家算法的數(shù)據(jù)結(jié)構(gòu) 
int Available[3]={3,3,2};//系統(tǒng)可用資源 
int Max[5][3]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};//進(jìn)程最大資源需求量 
int Allocation[5][3]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};//系統(tǒng)已經(jīng)給進(jìn)程分配的資源 
int Need[5][3]={{7,4,3},{1,2,2},{6,0,0},{0,1,1},{4,3,1}};//進(jìn)程的資源最大需求量 
int Work[3];//安全性檢查算法中的工作向量 
int Finish[5]={0,0,0,0,0};//進(jìn)程執(zhí)行完成的標(biāo)志 
int SafeArray[5];//安全序列 
int Request[3];//請(qǐng)求資源向量 

void ShowSafe(int i);
//打印當(dāng)前系統(tǒng)資源的分配情況 
void Show(){
    cout<<"T0時(shí)刻的系統(tǒng)資源分配情況如下："<<endl;
    cout<<"進(jìn)程名\tMax\t\tAllocation\tNeed\t\tAvailable"<<endl;
    for(int i=0;i<5;i++){
        cout<<"P"<<i<<"\t";
        for(int j=0;j<3;j++){
            cout<<Max[i][j]<<" ";
        }
        cout<<"\t\t";
        for(int j=0;j<3;j++){
            cout<<Allocation[i][j]<<" ";
        }
        cout<<"\t\t";
        for(int j=0;j<3;j++){
            cout<<Need[i][j]<<" ";
        }
        cout<<"\t\t";
        if(i==0){
            for(int j=0;j<3;j++){
                cout<<Available[j]<<" ";
            }
        }
        cout<<endl;
    }
}
//安全性檢查中判斷需求矩陣與工作向量關(guān)系 
int NeedLessWork(int i){
    for(int j=0;j<3;j++){
        if(Need[i][j]>Work[j]){
            return 0;
        }
    }
    return 1;
}
//打印安全序列 
void SafeLine(){
    cout<<"當(dāng)前系統(tǒng)處于安全狀態(tài)..."<<endl;
    cout<<"其中一個(gè)安全序列為：" ;
    for(int i=0;i<5;i++){
    	if(i==4)cout<<"P"<<SafeArray[i];
    	else cout<<"P"<<SafeArray[i]<<"-->";
    }
    cout<<endl;
    for(int i=0;i<5;i++){
        Finish[i]=0;
    }
}

//安全性檢查算法 
void IsSafe(int index){
    for(int i=0;i<5;i++){
        int temp=NeedLessWork(i);
        if(Finish[i]==0&&temp){
            SafeArray[index]=i;
            index++;
            Finish[i]=1;
            ShowSafe(i);
            for(int j=0;j<3;j++){
                Work[j]=Work[j]+Allocation[i][j];
            }
            break;
        }
    }
    int mult=1;
    //如果五個(gè)標(biāo)志都為1即都已經(jīng)完成，則打印安全序列，否則繼續(xù)執(zhí)行安全性檢查算法 
    for(int k=0;k<5;k++){
        mult*=Finish[k];
    }
    if(mult==0){
        IsSafe(index);
    }else{
        SafeLine();
    }
}
void ShowSafe(int i){
    cout<<"P"<<i<<"\t";
    for(int j=0;j<3;j++){
        cout<<Work[j]<<" ";
    }
    cout<<"\t\t";
    for(int j=0;j<3;j++){
        cout<<Need[i][j]<<" ";
    }
    cout<<"\t\t";
    for(int j=0;j<3;j++){
        cout<<Allocation[i][j]<<" ";
    }
    cout<<"\t\t";
    for(int j=0;j<3;j++){
        cout<<Work[j]+Allocation[i][j]<<" ";
    }
    cout<<"\t\t";
    cout<<Finish[i];
    cout<<endl;

}
void SafeCheck(){
    cout<<"試探著將資源分配給它后，系統(tǒng)安全情況分析如下："<<endl;
    cout<<"進(jìn)程\tWork\t\tNeed\t\tAllocation\tWork+Allocation\tFinish"<<endl;
    for(int i=0;i<3;i++){
        Work[i]=Available[i];
    }
    IsSafe(0);
}

int RequestLessNeed(int i){
    for(int j=0;j<3;j++){
        if(Request[j]>Need[i][j]){
            return 0;
        }
    }
    return 1;
}
int RequestLessAvailable(int i){
    for(int j=0;j<3;j++){
        if(Request[j]>Available[j]){
            return 0;
        }
    }
    return 1;
}

//處理進(jìn)程發(fā)出的資源請(qǐng)求 
void RequestResourse(){
    cout<<"請(qǐng)輸入發(fā)出資源請(qǐng)求的進(jìn)程：";
    int n;
	cin>>n;
    cout<<"請(qǐng)依次輸入所請(qǐng)求的資源數(shù)量：";
    for(int i=0;i<3;i++){
        cin>>Request[i];
    }
    if(RequestLessNeed(n)){
    	if(RequestLessAvailable(n)){
    		for(int j=0;j<3;j++){
            Available[j]=Available[j]-Request[j];
            Allocation[n][j]=Allocation[n][j]+Request[j];
            Need[n][j]=Need[n][j]-Request[j];
           }
            SafeCheck();//試探著將資源分配給請(qǐng)求進(jìn)程，并進(jìn)行安全性檢查 
    	}else{
    		cout<<"P"<<n<<"請(qǐng)求的資源向量已超過系統(tǒng)可用資源向量，請(qǐng)求失??！讓其繼續(xù)等待..."<<endl;
    		cout<<"-------------------------------------------------------------------"<<endl; 
            return ;
    	}
    }else{
    	 cout<<"P"<<n<<"請(qǐng)求的資源向量已超過其最大需求向量，請(qǐng)求失?。∽屍淅^續(xù)等待..."<<endl;
    	 cout<<"-------------------------------------------------------------------"<<endl; 
         return ;
    }
}


int main(){
    cout<<"*************************銀行家算法的模擬*************************"<<endl;
    cout<<"    \t\t\t1.顯示當(dāng)前系統(tǒng)資源情況"<<endl;
    cout<<"    \t\t\t2.進(jìn)程發(fā)出請(qǐng)求向量"<<endl;
    cout<<"    \t\t\t3.退出系統(tǒng)"<<endl;
    cout<<"******************************************************************"<<endl; 
    while(true){
        int choose;
        cout<<"請(qǐng)選擇你要執(zhí)行的操作：";
        cin>>choose;
        switch (choose){
            case 1 :
                Show();//展示當(dāng)前系統(tǒng)資源分配情況 
                break;
            case 2:
                RequestResourse();//處理進(jìn)程發(fā)出的資源請(qǐng)求 
                break;
            case 3:
                cout<<"已退出系統(tǒng)！"<<endl;
                return 0;
            default:
                cout<<"輸入錯(cuò)誤，請(qǐng)重新輸入！"<<endl;
                continue;
        }
    }
}

（3）測(cè)試

操作系統(tǒng)實(shí)驗(yàn)二死鎖避免之銀行家算法的模擬

?綜上。

?文章來源地址http://www.zghlxwxcb.cn/news/detail-428831.html

到了這里，關(guān)于操作系統(tǒng)實(shí)驗(yàn)二死鎖避免之銀行家算法的模擬的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！