用銀行家算法實現系統資源分配

 

銀行家算法是Dijkstra在1965年提出的一種避免死鎖的算法。銀行家算法陳述如下： 1)   當一個進程提出一個資源的請求時，假定分配給它，並調用檢查系統狀態安全性的算法。如果系統是安全的，則對申請者的假分配變為實際的分配。否則，推遲它的請求，讓其阻塞等待。 2)   檢查系統狀態安全性的算法。根據系統剩余的資源情況，銀行家進行檢查，看滿足請求者的要求後，是否仍是系統中的所有進程都能正常完成即能找到一個進程完成序列）。若能，系統是安全的。否則，系統是不安全的。 銀行家算法主要如下： 輸入：資源個數m、進程個數n、最大請求矩陣max、分配矩陣allocation 輸出：進程運行情況和安全狀況提示如果安全，輸出一個可能的進程完成序列） 主要算法： 1)   初始化，輸入各個參數，初始化各變量   2)   判斷系統安全性 程序中安全性算法的描述如下： a.   設置如下兩個工作向量： Work：表示系統可提供給進程繼續運行的各類資源的空閒資源數目，它含有m個元素，執行安全性算法開始時，Work＝Available。 Finish：表示系統是否有足夠的資源分配給進程，使之運行完成。開始時，Finish[i]＝false;當有足夠的資源分配給進程Pi時，令Finish[i]＝true。 b.   從進程集合中找到一個能滿足下列條件的進程： Finish[i]＝ false; Need[i] <= Work; 如果找到了就執行步驟c，否則執行步驟d。 c.   當進程Pi獲得資源後，可執行直到完成，並釋放出分配給它的資源，故應執行 Work = Allocation[i]＋Work; Finish[i]＝true; 然後轉向b。 d.   若所有進程中的Finish[i]都是true，則表示系統處於安全狀態；否則，系統處於不安全狀態。   3)   當系統請求資源時，調用系統狀態安全性算法 系統狀態安全性算法： 當某一進程提出資源申請時，系統須做出判斷，能否將所申請資源分配給該進程。設Request[i]是進程Pi的請求向量，Request[i][j]＝k表示進程Pi請求分配 j類資源有k個。當Pi發出資源請求後，系統按照下述步驟進行檢查： a. 如果Request[i]<= Need[i],則轉向b；否則出錯，因為進程所需要的資源數已超過它所宣布的最大值； b.  如果Request[i]<=Available，則轉向步驟c；否則，表示系統中尚無足夠的資源滿足進程Pi的申請，讓進程Pi等待。 c. 假設系統把申請的資源分配給進程Pi，則對應下面的數據結構進行修改： Available= Available－Request[i];            Allocation[i]= Allocation[i]＋Request[i]; Need[i]= Need[i]－Request[i]; d. 系統執行安全性算法，檢查此次資源分配後，系統是否處於安全狀態。若安全，就將資源分配給Pi，滿足其資源申請要求；否則，讓進程等待，並恢復原來的資源分配狀態。   數據結構： class bank { private:     int m;                //資源數量     int n;                //進程數量     int available[M];     //可利用資源向量     int max[M][N];        //最大需求矩陣     int allocation[M][N]; //分配矩陣     int need[M][N];       //需求矩陣 public:     bool Initilize();     //初始化各變量     bool IsSafe();        //檢查系統是否安全     bool Resoure_allocate();//分配資源     bool IsFinish();      //檢查系統是否運行完畢 };     測試用例： 本測試用例為《操作系統原理教程第二版）》P62頁用例，先給P2分配一個打印機，分配成功，然後分配給P5一台打印機，分配失敗，然後按照P4，P1，P5，P2，P3執行系統。   Available=1,0,2,0）

進程 磁帶機 繪圖機 打印機 光驅 P1 3 0 1 1 P2 0 1 0 0 P3 1 1 1 0 P4 1 1 0 1 P5 0 0 0 0

進程當前的分配矩陣Allocation

進程 磁帶機 繪圖機 打印機 光驅 P1 1 1 0 0 P2 0 1 1 2 P3 3 1 0 0 P4 0 0 1 0 P5 2 1 1 0

進程當前的剩余請求矩陣Need

進程 磁帶機 繪圖機 打印機 光驅 P1 4 1 1 1 P2 0 2 1 2 P3 4 2 1 0 P4 1 1 1 1 P5 2 1 1 0

各個進程的最大請求矩陣Max 測試數據：直接復制到終端中即可） 4 5 4 1 1 1 0 2 1 2 4 2 1 0 1 1 1 1 2 1 1 0 3 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 0 0 0 1 0 2 0 1 2 1 4 2 1 3 2 1 0 0 1 0 1 1 4 0 2 4 1 1 4 2 1 1 1 1 1 3 2 2 0 3 2 1 1 運行結果： 輸入資源數量：4 輸入進程數量：5 輸入最大請求矩陣 5X4 4 1 1 1 0 2 1 2 4 2 1 0 1 1 1 1 2 1 1 0 輸入分配矩陣 5X4 3 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 0 0 0 輸入可利用資源向量 1X4 1 0 2 0 安全序列是 3 0 1 2 4 輸入運行進程號:1 請求資源號：2 請求數量：1 安全序列是 3 0 1 2 4 輸入運行進程號:4 請求資源號：2 請求數量：1 沒有安全序列 系統不安全，等待 輸入運行進程號:3 請求資源號：2 請求數量：1 安全序列是 0 1 2 4 進程3運行完畢 輸入運行進程號:0 請求資源號：0 請求數量：1 安全序列是 0 1 2 4 輸入運行進程號:0 請求資源號：1 請求數量：1 安全序列是 1 2 4 進程0運行完畢 輸入運行進程號:4 請求資源號：0 請求數量：2 安全序列是 1 2 4 輸入運行進程號:4 請求資源號：1 請求數量：1 安全序列是 4 1 2 輸入運行進程號:4 請求資源號：2 請求數量：1 安全序列是 1 2 進程4運行完畢 輸入運行進程號:1 請求資源號：1 請求數量：1 安全序列是 1 2 輸入運行進程號:1 請求資源號：3 請求數量：2 安全序列是 2 進程1運行完畢 輸入運行進程號:2 請求資源號：0 請求數量：3 安全序列是 2 輸入運行進程號:2 請求資源號：1 請求數量：1 安全序列是   進程2運行完畢 所有進程執行完畢

#include <iostream>  
#include <cstdlib>  
#define M 16  
#define N 16  
using namespace std;  
 
class bank  
{  
private:  
    int m;                //資源數量  
    int n;                //進程數量  
    int available[M];     //可利用資源向量  
    int max[M][N];        //最大需求矩陣  
    int allocation[M][N]; //分配矩陣  
    int need[M][N];       //需求矩陣  
public:  
    bool Initilize();     //初始化各變量  
    bool IsSafe();        //檢查系統是否安全  
    bool Resoure_allocate();//分配資源  
    bool IsFinish();      //檢查系統是否運行完畢  
};  
 
int main()  
{  
    bank process;  
 
    if (!process.Initilize())   //初始化  
    {  
        cout<<"輸入錯誤"<<endl;  
    }  
 
    if (!process.IsSafe())      //檢查系統運行初是否安全  
    {  
        return 0;  
    }  
 
    while (true)  
    {  
        process.Resoure_allocate();     //根據各進程需要分配資源  
        if (process.IsFinish())         //檢查系統是否執行完畢  
        {  
            cout<<"所有進程執行完畢"<<endl;  
            break;  
        }  
    }  
    system("PAUSE");  
    return 0;  
}  
 
bool bank::Initilize()  
{  
    int i,j;  
    cout<<"輸入資源數量：";  
    cin>>m;  
    cout<<"輸入進程數量：";  
    cin>>n;  
    cout<<"輸入最大請求矩陣 "<<n<<"X"<<m<<endl;  
    for (i = 0; i < n; i++)  
    {  
        for (j = 0; j < m; j++)  
        {  
            cin>>max[i][j];  
        }  
    }  
    cout<<"輸入分配矩陣 "<<n<<"X"<<m<<endl;  
    for (i = 0; i < n; i++)  
    {  
        for (j = 0; j < m; j++)  
        {  
            cin>>allocation[i][j];  
        }  
    }  
    for (i = 0; i < n; i++)  
    {  
        for (j = 0; j < m; j++)  
        {  
            need[i][j]=max[i][j]-allocation[i][j];  
            if (need[i][j] < 0)  
            {  
                return false;  
            }  
        }  
    }  
    cout<<"輸入可利用資源向量 "<<1<<"X"<<m<<endl;  
    for (i = 0; i < m; i++)  
    {  
        cin>>available[i];  
        if (available[i] < 0)  
        {  
            return false;  
        }  
    }  
    return true;  
}  
 
bool bank::IsSafe()  
{  
    int i,j,k,result[N],work[M],finish[N];  
    for (i = 0; i < m; i++)  
    {  
        work[i]=available[i];  
    }  
    for (i = 0; i < n; i++)                 //標識變量初始化  
    {  
        finish[i]=false;  
    }  
    for (i = 0, k = 0; i < n; i++)  
    {  
        if (!finish[i])  
        {  
            for (j = 0; j < m; j++)  
            {  
                if (need[i][j] > work[j])      //目前無法滿足該進程  
                {  
                    break;  
                }  
            }  
 
            if (j == m)                     //可以滿足該進程  
            {  
                result[k++]=i;  
                for (j = 0; j < m; j++) //將現有可用資源數加上第i進程已經分配了的  
                {  
                    work[j]+=allocation[i][j];  
                }  
                finish[i]=true;  
                i=-1;                       //從頭掃描  
            }  
        }  
    }  
    for (i = 0; i < n; i++)  
    {  
        if (!finish[i])  
        {  
            cout<<"沒有安全序列"<<endl;  
            return false;  
        }  
    }  
    cout<<"安全序列是"<<endl;  
    for (i = 0; i < n; i++)  
    {  
        for ( j = 0; j < m; j++)            //如果進程已經執行完畢,則安全序列中不再輸出  
        {  
            if (need[result[i]][j] != 0)  
            {  
                break;  
            }  
        }  
        if (j == m)  
        {  
            continue;  
        }  
        cout<<result[i]<<" ";  
    }  
    cout<<endl;  
    return true;  
}  
 
bool bank::Resoure_allocate()  
{  
    int i,process_id,source_id,amount;  
    cout<<"輸入運行進程號:";  
    cin>>process_id;  
    cout<<"請求資源號：";  
    cin>>source_id;  
    cout<<"請求數量：";  
    cin>>amount;  
 
    if (amount > need[process_id][source_id])  
    {  
        cout<<"請求不合法，終止運行"<<endl;  
        return false;  
    }  
 
    if (amount > available[source_id])  
    {  
        cout<<"請求無法滿足，等待"<<endl;  
        return false;  
    }  
 
    available[source_id]-=amount;                   //假定分配資源  
    allocation[process_id][source_id]+=amount;  
    need[process_id][source_id]-=amount;  
 
    if (!IsSafe())                                  //檢查系統是否安全  
    {  
        available[source_id]+=amount;  
        allocation[process_id][source_id]-=amount;  
        need[process_id][source_id]+=amount;  
        cout<<"系統不安全，等待"<<endl;  
        return false;  
    }  
 
    for ( i = 0; i < m; i++)                        //查看進程是否執行完畢  
    {  
        if (allocation[process_id][i] != max[process_id][i])  
        {  
            break;  
        }  
    }  
 
    if (i == m)                                     //進程執行完畢  
    {  
        for ( i = 0; i < m; i++)  
        {  
            available[i]+=allocation[process_id][i];  
            allocation[process_id][i]=0;  
            need[process_id][i]=0;  
        }  
        cout<<"進程"<<process_id<<"運行完畢"<<endl;  
    }  
    return true;  
}  
 
bool bank::IsFinish()  
{  
    int i,j,finish[N];  
 
    for ( i = 0; i < n; i++)  
    {  
        finish[i]=false;  
    }  
 
    for ( i = 0; i < n; i++)  
    {  
        for ( j = 0; j < m; j++)  
        {  
            if (need[i][j] != 0)  
            {  
                break;  
            }  
        }  
        if (j == m)  
        {  
            finish[i]=true;  
        }  
    }  
 
    for ( i = 0; i < n; i++)  
    {  
        if (finish[i] == false)  
        {  
            break;  
        }  
    }  
    if (i != n)  
    {  
        return false;  
    }  
    return true;  
}  

 

本文出自 “天才鳥蛋” 博客，請務必保留此出處http://curely.blog.51cto.com/1627940/803342