之前寫過一篇關于死鎖和銀行家算法的詳細描述的博客https://www.cnblogs.com/wkfvawl/p/11598647.html

寫這篇博客的目的，主要是詳細講解一下銀行家算法以及代碼的實現

Dijkstra在1965年提出的銀行家算法是著名的死鎖避免算法，這個用于一個銀行家給多個顧客貸款的算法可以直接用于操作系統給進程分配資源，這時只要把銀行家換成操作系統，把顧客換成進程，把資金換成資源，把銀行家決定是否放貸時所用的判斷過程（即判斷顧客是否有信譽和償還能力）換成操作系統決定是否分配資源時所用的判斷過程（即判斷進程是否能及時歸還資源）即可。為了描述銀行家算法，下面先介紹一下系統的安全狀態的概念。

一、安全序列

注意：

（1）系統在某一時刻的安全狀態可能不唯一，但這不影響對系統安全性的判斷。
（2）安全狀態是非死鎖狀態，而不安全狀態并不一定是死鎖狀態。即系統處于安全狀態一定可以避免死鎖，而系統處于不安全狀態則僅僅可能進入死鎖狀態。

二、銀行家算法

銀行家算法的實質就是要設法保證系統動態分配資源后不進入不安全狀態，以避免可能產生的死鎖。即沒當進程提出資源請求且系統的資源能夠滿足該請求時，系統將判斷滿足此次資源請求后系統狀態是否安全，如果判斷結果為安全，則給該進程分配資源，否則不分配資源，申請資源的進程將阻塞。

銀行家算法的執行有個前提條件，即要求進程預先提出自己的最大資源請求，并假設系統擁有固定的資源總量。下面介紹銀行家算法所用的主要的數據結構。

三、具體實例

假定操作系統中的4個進程P1、P2、P3、P4和3類資源R1、R2、R3(資源數量分別為9、3、6)，在t0時刻的資源分配情況如表2-1：

四、測試代碼

#include<iostream>
using namespace std;
// p 進程數，r資源種類
int p ;
int r ;
int maxs[10][10]; //最大需求矩陣
int allocation[10][10]; //分配矩陣
int need[10][10];   //需求矩陣
int available[10]; //可用資源向量
int request[10];   //請求向量當前進程對各類資源的申請量,算法的入口參數
//輸入函數
void infInput()
{
    int i,j;
    cout<<"請輸入最大需求矩陣max
";
    for(i=0; i<p; i++)
    {
        for(j=0; j<r; j++)
        {
            cin>>maxs[i][j];
        }
    }
    cout<<"請輸入分配矩陣allocation
";
    for(i=0; i<p; i++)
    {
        for(j=0; j<r; j++)
        {
            cin>>allocation[i][j];
        }
    }
    cout<<"請輸入需求矩陣need
";
    for(i=0; i<p; i++)
    {
        for(j=0; j<r; j++)
        {
            cin>>need[i][j];
        }
    }
    cout<<"請輸入可用資源向量available
";
    for(i=0; i<r; i++)
    {
        cin>>available[i];
    }
}

//比較函數
//比較進程為m中的元素全大于n中的元素返回1，否則返回0
int compare(int m[],int n[])
{
    int i;
    for(i=0; i<r; i++)
    {
        if(m[i]<n[i])
        {
            return 0;
        }
    }
    return 1;
}


//安全性檢驗函數，檢測是否存在安全序列
int stest()
{
    int i,j,k,l,flag=0;
    int finish[p];
    int work[r];
    for(i=0; i<p; i++)
    {
        finish[i]=0;
        //vis為1即表示available滿足第i進程的資源需要
    }
    for(i=0; i<r; i++)
    {
        work[i]=available[i];
    }
    cout<<"分配序列：
";
    cout<<"            allocation            need              avilable"<<endl;
    for(k=0; k<p; k++)
    {
        for(i=0; i<p; i++)
        {
            if(finish[i]==1)
            {
                continue;
            }
            else
            {
                if(compare(work,need[i]))//available>=need
                {
                    finish[i]=1;
                    cout<<'
'<<"進程"<<i+1<<'	';
                    flag=1;
                    for (j =0; j<r; j++)
                    {
                        printf("  %2d ", allocation[i][j]);
                    }
                    cout<<"     ";
                    for (j = 0; j < r; j++)
                    {
                        printf("  %2d ", need[i][j]);
                    }
                    cout<<"     ";
                    for (j = 0; j <r; j++)
                    {
                        printf("  %2d ", work[j] +allocation[i][j]);
                    }
                    for(l=0; l<r; l++)
                    {
                        work[l]=work[l]+allocation[i][l];
                        //進程完成，釋放資源
                    }
                    break;
                }
            }
            if(flag==1)
            {
                break;
            }
        }
    }
    cout<<'
';
    for(l=0; l<p; l++)
    {
        if(finish[l]==0)
        {
            return 0;//不存在安全序列
        }
    }
    return 1;//存在安全序列
}

//申請進程后的安全性檢驗函數

void rtest(int n)
{
    int j;
    //n=n-1;
    if(compare(available,request)&&compare(need[n-1],request))//available>=request 并且 need >=request
    {
        for(j=0; j<r; j++)
        {
            allocation[n-1][j]=allocation[n-1][j]+request[j];
            need[n-1][j]=need[n-1][j]-request[j];
            available[j]=available[j]-request[j];
        }
        if(stest())
        {
            cout<<"允許"<<n<<"進程申請資源！
";
        }
        else
        {
            cout<<"不允許"<<n<<"進程申請資源！
";
            for(j=0; j<r; j++)
            {
                allocation[n-1][j]=allocation[n-1][j]-request[j];
                need[n-1][j]=need[n-1][j]+request[j];
                available[j]=available[j]+request[j];
            }
        }
    }
    else
    {
        cout<<"申請資源量越界！
";
    }
}

int main()
{
    int i,n;       //n-第n個資源申請
    cout<<"請輸入進程數：";
    cin>>p;
    cout<<"請輸入資源種類數：";
    cin>>r;
    //默認狀態4、3
    infInput();//輸入函數
    if(stest()==1)
    {
        cout<<"存在安全序列，初始狀態安全。
";
    }
    else
    {
        cout<<"不存在安全序列，初始狀態不安全。
";
    }
    cout<<"請輸入發出請求向量request的進程編號：";
    cin>>n;
    cout<<"請輸入請求向量request
";
    for(i=0; i<r; i++)
    {
        cin>>request[i];
    }
    rtest(n);
    return 0;
}
/*
4
3
3 2 2
6 1 3
3 1 4
4 2 2
1 0 0
5 1 1
2 1 1
0 0 2
2 2 2
1 0 2
1 0 3
4 2 0
1 1 2
*/

總結

以上是生活随笔為你收集整理的操作系统——银行家算法（Banker's Algorithm）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。