银行家算法程序模拟实现

 代码仓库：JJLi0427/operationsystem (github.com)

1.算法简介

银行家算法是一种用于避免死锁的算法，其主要应用于多进程环境下的资源分配问题。在银行家算法中，每个进程都需要申请一定数量的资源，而系统会根据当前资源的可用性来判断是否能够满足该进程的资源需求，从而决定是否分配资源。

一个典型的银行家算法问题可以描述如下：假设有n个进程和m种不同类型的资源，每个进程需要一定数量的每种资源才能完成任务。系统中有一定数量的每种资源可供分配，但是不同的进程对资源的需求量不同。现在需要设计一个算法，以确保系统能够分配资源并避免死锁

2.解决思路

想解决银行家问题就需要回答以下问题：

1. 每个进程需要的资源量是多少？（建立需求矩阵）

2. 系统中有多少可用的每种资源？（建立可用资源向量）

3. 系统是否能够满足当前进程的资源需求？（安全性判断）

4. 如果系统不能满足当前进程的资源需求，该进程应该如何等待？（计算安全序列）

5. 当系统分配资源后，是否会导致死锁？（不安全退回）

3.模拟实现程序设计思路 

1. 首先，在全局变量中定义进程数量p、资源种类r以及已分配资源矩阵allocate、需求资源矩阵needs和可利用资源向量avail。

2. 通过init函数进行初始化，将已分配资源矩阵、需求资源矩阵和最大需求资源矩阵进行赋值。其中，最大需求资源矩阵的值等于已分配资源矩阵加上需求资源矩阵。

3. 编写output函数，用于输出最大需求资源矩阵、已分配资源矩阵、需求资源矩阵和可利用资源向量的值。

4. 编写compare函数用于比较进程的需求资源和可用资源，判断是否满足分配条件。

5. safe函数用于进行安全性检查，采用银行家算法判断系统是否处于安全状态。具体步骤如下：

   • 初始化finish数组、forwork数组、安全队列list和计数器count。
   • 尝试为每个未完成的进程分配资源，如果该进程的需求资源小于等于可用资源，则将其加入安全队列，并更新可用资源。
   • 如果所有进程都能成功分配资源，则系统处于安全状态，输出安全队列。
   • 如果存在无法分配资源的进程，则系统不安全。

6. bank函数用于处理用户的请求。首先获取用户输入的进程号和请求向量，然后进行以下判断：

   • 请求向量不能大于需求向量。
   • 请求向量不能大于可利用资源向量。
   • 如果满足以上条件，尝试为该进程分配资源，并进行安全性检查。
   • 如果分配成功，则输出"Allocate success"，否则输出"Allocate fail"。

7. 主函数中，先调用init函数进行初始化，并输出初始状态。然后进行一次安全性检查。接着进入循环，每次循环都调用bank函数处理用户的请求，并询问用户是否继续或退出。

4.完整程序

#include
using namespace std;
 
const int p = 5; // 设置进程数量
const int r = 4; // 设置资源种类
int allocate[p][r] = {{0, 1, 0, 0},
                      {2, 0, 0, 1},
                      {3, 0, 2, 1},
                      {2, 1, 1, 0},
                      {0, 0, 2, 0}}; // 已分配资源矩阵
int needs[p][r] = {{7, 4, 3, 3},
                   {1, 2, 2, 2},
                   {6, 0, 0, 0},
                   {0, 1, 1, 1},
                   {4, 3, 1, 1}}; // 需求资源矩阵
int avail[r] = {3, 3, 2, 2}; // 可利用资源向量
 
void init(int maximum[p][r], int allocation[p][r], int need[p][r], int available[r], int request[r]) {
    for(int i = 0; i < p; i++) {
        for(int j = 0; j < r; j++) {
            allocation[i][j] = allocate[i][j];
            need[i][j] = needs[i][j];
            maximum[i][j] = need[i][j]+allocation[i][j]; // maximum = allocation + need
        }
    } // 初始化，从矩阵读取数据
    for(int i = 0; i < r; i++) {
        available[i] = avail[i];
    }
}
 
void output(int maximum[p][r], int allocation[p][r], int need[p][r], int available[r]) {
    cout << "Maximum:           " << "Allocation:        " << "Need:              " << "Available: " << endl;
    for(int i = 0; i < p; i++) {
        cout << "Pid=" << i << ": ";
        for(int j = 0; j < r; j++) {
            cout << maximum[i][j] << ' ';
        }
        cout << "    Pid=" << i << ": ";
        for(int j = 0; j < r; j++) {
            cout << allocation[i][j] << ' ';
        }
        cout << "    Pid=" << i << ": ";
        for(int j = 0; j < r; j++) {
            cout << need[i][j] << ' ';
        }
        if(i == 0) {
            cout << "    ";
            for(int k = 0; k < r; k++){
                cout << available[k] << ' ';
            }
        }
        cout << endl;
    }
}
 
bool compare(int need[], int forwork[]) {
    // 比较函数，需要<=可用
    for(int i = 0; i < r; i++) {
        if(need[i] > forwork[i]) {
            return false;
        }
    }
    return true;
}
 
bool safe(int allocation[p][r], int need[p][r], int available[r]) {
    // 安全性检查
    int finish[p]; // finish数组，用来记录进程是可以否执行完成
    int forwork[r]; // 可用资源数组
    int list[p]; // 安全队列
    int count = 0;
    for(int i = 0; i < r; i++)
        forwork[i] = available[i]; // 初始时等于available
 
    for(int x = 0; x < p; x++) {
        for(int i = 0; i < p; i++) {
            if(finish[i] == 1)
                continue; // 跳过已经判断过的进程
            else {
                if(compare(need[i], forwork)) {
                    for(int j = 0; j < r; j++) {
                        forwork[j] += allocation[i][j];
                    }
                    finish[i] = 1;
                    list[count++] = i; // 进程进入安全列中
                    break;
                }
            }
        }
    }
 
    if(count != p) {
        cout << "Will not be safe!" << endl;
        return false;
    }
    cout << "Safe! working list: ";
    for(int i = 0; i < p; i++) {
        cout << list[i];
        if(i != p-1)
            cout << "->";
    }
    cout << endl;
    return true;
}
 
int bank(int maximum[p][r], int allocation[p][r], int need[p][r], int available[r], int request[r]) {
    cout << "Request Process id:" << endl;
    int num = 0;
    cin >> num;
    cout << "Request vector:" << endl;
    for(int i = 0; i < r; i++) {
        cin >> request[i];
    }
    if(!compare(request ,need[num])) {
        // 请求不能大于需求
        cout<<"Error: request > need"<
        return 0;
    }
    else {
        if(!compare(request, available)) {
            // 请求不能大于可用
            cout << "Error: request > available" << endl;
            return 0;
        }
        else {
            for(int j = 0; j < r;j ++) {
                available[j] -= request[j];
                allocation[num][j] += request[j];
                need[num][j] -= request[j];
            }
            if(safe(allocation, need, available)) {
                cout <<"Allocate success"<< endl;
            }
            else {
                cout << "Allocate fail" << endl;
                for(int j = 0; j < r; j++) {
                    need[num][j] += request[j];
                    allocation[num][j] -= request[j];
                    available[j] += request[j];
                } // 分配失败返回原来状态
            }
        }
    }
    output(maximum, allocation, need, available);
    return 0;
}
 
int main() {
    int maximum[p][r], allocation[p][r], need[p][r];
    int available[r], request[r];
    init(maximum, allocation, need, available, request);
    output(maximum, allocation, need, available);
    safe(allocation, need, available);
    char flag = 'c';
    while(flag == 'c' || flag == 'C') {
        bank(maximum, allocation, need, available, request);
        cout << "\nInput q to left / Input c to continue." << endl;
        cin >> flag;
        if(flag == 'q' || flag == 'Q')
            break;
    }
    return 0;
}

5.运行截图

先输入进程id，再输入需要申请的资源向量，继续执行输入c，结束模拟输入q