实验报告_银行家算法

操作系统

实验内容

给定若干进程的资源占用情况,判断当前是否处于安全状态, 审核某个进程的请求是否可以被批准.
要求: 自行设计实验方案, 程序的输入和输出.

解决方案

对于每个进程$P_i$的请求向量, 系统首先判断是否有足够的资源分配给$P_i$, 如果没有, 先让$P_i$等待, 并判断下个进程$P_{i+1}$. 如果有足够的资源, 则正式把资源分配给该进程, 结束后, 系统回收这个进程占用的资源. 如此往复, 直到所有进程的请求都满足为止.
如果出现所有进程的请求都无法满足的情况, 则系统处于不安全状态, 向用户报错Error.

测试样例说明

第一行为资源种类数$N$.
第二行一共$N$个数, 代表系统每个资源持有数.
第三行为任务个数$D$.
之后$D$行, 每行有$2N$个数字, 前$N$个数代表任务占有资源数, 后N个代表任务请求资源数.

运行结果

对于测试样例

3
3 3 2
5
0 1 0 7 4 3
2 0 0 1 2 2
3 0 2 6 0 0
2 1 1 0 1 1
0 0 2 4 3 1

运行结果为

Duty 2 is finished.
Current avaliable source:5 3 2 
Duty 4 is finished.
Current avaliable source:7 4 3 
Duty 1 is finished.
Current avaliable source:7 5 3 
Duty 3 is finished.
Current avaliable source:10 5 5 
All duty is finished. Congratulations!

对于测试样例

4
5 5 5 5
3
1 5 5 3 4 6 6 4
1 0 0 1 0 0 0 1
2 3 2 4 4 6 6 5

运行结果为

Duty 2 is finished.
Current avaliable source:6 5 5 5 
Error: no enough source.

源码展示

#include <iostream>
#include <cstring>
using namespace std;
#define N 105
int main(){
    int Source; //资源种类数
    int Available[N];//可利用资源向量
    int Duty;   //进程数
    int Allocation[N][N];  //分配矩阵
    int Need[N][N]; //需求矩阵
    freopen("data.txt", "r", stdin);
    cin >> Source;
    for(int i = 1; i <= Source; i++) cin >> Available[i];
    cin >> Duty;
    for(int i = 1; i <= Duty; i++){
        for(int j = 1; j <= Source; j++){
            cin >> Allocation[i][j];
        }
        for(int j = 1; j <= Source; j++){
            cin >> Need[i][j];
        }
    }
    int cur = Duty+1;
    bool Finished[Duty];
    memset(Finished, 0, sizeof(Finished));
    while(cur--){
        if(cur == 0) {
            puts("All duty is finished. Congratulations!");
            break;
        }
        int flag = 0; //flag : if there is a satisfied duty.
        for(int i = 1; i <= Duty; i++){
            if(Finished[i]) continue;
            int flag_2 = 0; //flag_2 : if current duty is satisfied.
            for(int j = 1; j <= Source; j++){
                if(Need[i][j] > Available[j]) flag_2 = 1;
            }
            if(flag_2 == 0){
                flag = 1; //Successfully find a duty.
                Finished[i] = 1;
                for(int j = 1; j <= Duty; j++){
                    Available[j] += Allocation[i][j];
                }
                cout<<"Duty "<<i<<" is finished."<<endl;
                cout<<"Current avaliable source:";
                for(int j = 1; j <= Source; j++){
                    cout<<Available[j]<<" ";
                }
                cout<<endl;
                break;
            }
        }
        if(flag == 0) {
            puts("Error: no enough source.");
            getchar();
            exit(0);
        }
    }
}