银行家算法 C++描述

银行家算法 C++描述

银行家算法

操作系统——银行家算法

实现代码

main.cpp

#include "BankerAlgorithm.h"

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<vector<int> > max(n, vector<int>(m));
    vector<vector<int> > allocation(n, vector<int>(m));
    vector<int> available(m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            scanf("%d", &max[i][j]);
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            scanf("%d", &allocation[i][j]);
        }
    }
    for (int i = 0; i < m; ++i) {
        scanf("%d", &available[i]);
    }
    BankerAlgorithm bankerAlgorithm(max, allocation, available);
    int process;
    while (~scanf("%d", &process) && process >= 0) {
        vector<int> request(m);
        for (int i = 0; i < request.size(); ++i) {
            scanf("%d", &request[i]);
        }
        bankerAlgorithm.request(process, request);
    }

    return 0;
}

BankerAlgorithm.h

#include <bits/stdc++.h>
using namespace std;
#ifndef BANKERALGORITHM_BANKERALGORITHM_H
#define BANKERALGORITHM_BANKERALGORITHM_H


class BankerAlgorithm {
private:
    vector<vector<int> > max;
    vector<vector<int> > allocation;
    vector<vector<int> > need;
    vector<int> available;
    vector<bool> finished;
    vector<int> safeSequence;
    vector<int> allocate(vector<int> systemResources, vector<int> neededResources);
    vector<int> release(vector<int> systemResources, vector<int> releaseResources);
    bool finish(vector<int>& needResources);
    bool allFinish();
    bool isAvailable(vector<int>& requestResources);
    bool safeStatusCheck();
public:
    BankerAlgorithm(vector<vector<int> > max, vector<vector<int> > allocation, vector<int> available);
    void request(int process, vector<int> requestResources);
};


#endif //BANKERALGORITHM_BANKERALGORITHM_H

BankerAlgorithm.cpp

#include "BankerAlgorithm.h"

vector<int> BankerAlgorithm::allocate(vector<int> systemResources, vector<int> neededResources) {
    for (int i = 0; i < systemResources.size(); ++i) {
        systemResources[i] -= neededResources[i];
    }
    return systemResources;
}

vector<int> BankerAlgorithm::release(vector<int> systemResources, vector<int> releaseResources) {
    for (int i = 0; i < systemResources.size(); ++i) {
        systemResources[i] += releaseResources[i];
    }
    return systemResources;
}

BankerAlgorithm::BankerAlgorithm(vector<vector<int> > max, vector<vector<int> > allocation, vector<int> available) {
    this->max = max;
    this->allocation = allocation;
    this->need.resize(max.size());
    this->finished.resize(max[0].size());
    this->available.resize(available.size());

    for (int i = 0; i < max.size(); ++i) {
        this->need[i] = allocate(max[i], allocation[i]);
    }

    for (int i = 0; i < finished.size(); ++i) {
        finished[i] = false;
    }

    for (int i = 0; i < finished.size(); ++i) {
        this->available[i] = available[i];
    }

}

bool BankerAlgorithm::isAvailable(vector<int>& requestResources) {
    for (int i = 0; i < available.size(); ++i) {
        if (available[i] < requestResources[i]) {
            return false;
        }
    }
    return true;
}

void BankerAlgorithm::request(int process, vector<int> requestResources) {
    if (!isAvailable(requestResources)) {
        printf("Available resource is not enough, rejected allocation request!\n");
        return;
    }
    available = allocate(available, requestResources);
    allocation[process] = release(allocation[process], requestResources);
    need[process] = allocate(need[process], requestResources);
    if (safeStatusCheck()) {
        printf("Allocation succeed!\n");
    } else {
        printf("Entering unsafe status, rejected allocation request!\n");
    }
}

bool BankerAlgorithm::safeStatusCheck() {
    int count = 0;
    for (int i = 0; i < need.size(); ++i) {
        count += isAvailable(need[i]) ? 0 : 1;
    }
    if (count == available.size()) {
        return false;
    }
    bool safe = false;
    for (int i = 0; i < need.size() && !safe; ++i) {
        if (isAvailable(need[i]) && !finished[i]) {
            available = release(available, allocation[i]);
            finished[i] = true;
            safeSequence.push_back(i);
            if (allFinish()) {
                safe = true;
                printf("Safe Sequence: \n");
                for (int j = 0; j < safeSequence.size(); ++j) {
                    printf("P%d ", safeSequence[j]);
                }
                printf("\n");
            } else {
                safe = safeStatusCheck();
            }

            safeSequence.pop_back();
            finished[i] = false;
            available = allocate(available, allocation[i]);
        }
    }
    return safe;
}

bool BankerAlgorithm::finish(vector<int>& needResources) {
    for (int i = 0; i < needResources.size(); ++i) {
        if (needResources[i] == 0) {
            return false;
        }
    }
    return true;
}

bool BankerAlgorithm::allFinish() {
    for (int i = 0; i < finished.size(); ++i) {
        if (!finished[i]) {
            return false;
        }
    }
    return true;
}

测试数据

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

测试结果

Safe Sequence:
P0 P2 P1 P3
Allocation succeed!

最后

• 由于博主水平有限，不免有疏漏之处，欢迎读者随时批评指正，以免造成不必要的误解！