当前位置：首页 > 工具资源 > 正文内容

银行家算法：避免死锁的资源分配算法[cpp]

admin2周前 (05-25)工具资源15

在多进程操作场景中，资源的妥善分配与管控对于系统平稳运行极为关键。但若资源分配不当，可能会引发死锁现象，即进程将无法继续执行而陷入永久的阻塞状态。为此，银行家算法应运而生，旨在防止死锁的发生。本文将阐述银行家算法的基本原理，并附上一个简单的C++实现案例。

死锁与资源分配问题

在操作系统内部，众多进程为了争夺有限的资源，诸如内存、文件、打印机等，展开激烈竞争。一旦某个进程获取了部分资源却陷入等待其他进程释放资源的境地，就可能触发死锁现象。所谓死锁，即系统中的进程因所需资源被其他进程所占用而无法继续执行银行家算法资源分配，而这些占用资源的进程同样在等待释放资源。在这种状况下银行家算法资源分配，系统将无法再进行资源分配，进而导致进程无法顺利完成。

银行家算法原理

银行家算法属于资源分配领域银行家算法：避免死锁的资源分配算法[cpp]，其核心目的是防止系统陷入死锁。该算法通过执行安全性检验来评估在特定资源分配方案下银行家算法资源分配，系统能否保持在一个安全的状态。这一算法的构建基于以下几个核心要素：

银行家算法实现

以下是一个以C++为基础的银行家算法示例，该示例接收可利用资源向量、最大需求矩阵以及已分配矩阵作为输入数据，进而对系统是否达到安全状态进行评估。

#include 
const int MAX_PROCESSES = 5;
const int MAX_RESOURCES = 3;
bool isSafeState(int available[], int max_demand[][MAX_RESOURCES], int[id_102752104][][MAX_RESOURCES], int safe_sequence[]) {
    int num_processes = MAX_PROCESSES;
    int num_resources = MAX_RESOURCES;
    int need[MAX_PROCESSES][MAX_RESOURCES];
    bool finish[MAX_PROCESSES] = {false};
    int work[MAX_RESOURCES];
    // Calculate the need matrix
    for (int i = 0; i < num_processes; i++) {
        for (int j = 0; j < num_resources; j++) {
            need[i][j] = max_demand[i][j] - allocated[i][j];
        }
    }
    // Initialize work array
    for (int j = 0; j < num_resources; j++) {
        work[j] = available[j];
    }
    寻找一个可执行的流程。
    int count = 0;
    while (count < num_processes) {
        bool found = false;
        for (int i = 0; i < num_processes; i++) {
            if (!finish[i]) {
                bool canExecute = true;
                for (int j = 0; j < num_resources; j++) {
                    if (need[i][j] > work[j]) {
                        canExecute = false;
                        break;
                    }
                }
                if (canExecute) {
                    为该进程分配所需资源
                    for (int j = 0; j < num_resources; j++) {
                        work[j] += allocated[i][j];
                    }
                    将此流程标记为已完成状态。
                    finish[i] = true;
                    found = true;
                    count++;
                    将此流程纳入安全序列之中。
                    safe_sequence[count - 1] = i;
                    break;
                }
            }
        }
        if (!found) {
            break;
        }
    }
    确认所有进程是否均已结束
    return count == num_processes;
}
int main() {
    int available_resources[] = {3, 3, 2};
    int maximum_demand[][MAX_RESOURCES] = {{7, 5, 3},
                                           {3, 2, 2},
                                           {9, 0, 2},
                                           {2, 2, 2},
                                           {4, 3, 3}};
    int allocated_resources[][MAX_RESOURCES] = {{0, 1, 0},
                                                {2, 0, 0},
                                                {3, 0, 2},
                                                {2, 1, 1},
                                                {0, 0, 2}};
    int safe_sequence[MAX_PROCESSES];
    bool isSafe = isSafeState(available_resources, maximum_demand, allocated_resources, safe_sequence);
    if (isSafe) {
        std::cout << "System is in a safe state." << std::endl;
        std::cout << "Safe sequence: ";
        for (int i = 0; i < MAX_PROCESSES; i++) {
            std::cout << "P" << safe_sequence[i] << " ";
        }
        std::cout << std::endl;
    } else {
        std::cout << 系统目前处于不稳定状态。 << std::endl;
    }
    return 0;
}

示例和演示

为了深入掌握银行家算法的运作机制银行家算法：避免死锁的资源分配算法[cpp]，我们不妨借助一个实例来展示其运作步骤。

存在五个进程（标记为P0至P4）以及三种独特的资源（分别命名为R0至R2）。目前，可供使用的资源数量分别为3、3和2。此外，最大需求矩阵与已分配矩阵的具体情况如下：

最大需求矩阵：

已分配矩阵：

我们将运用这些示例数据对银行家算法进行操作，同时留意并评估系统的安全状况。

P1所分配的资源：两项、零项、两项
Resource needs for P1: 1 2 2 
现有资源状况：三个、三个、两个。
分配后可用的资源：5，3，2。
P3项目分配的资源：两个单位，一个单位，一个单位。
Resource needs for P3: 0 1 1 
当前可用的资源数量分别为：五、三、二。
分配后可用资源：7，4，3。
P0项目所分配的资源：零，一，零。
Resource needs for P0: 7 4 3 
现有资源数量：七个、四个、三个。
分配后可用的资源数量分别为：七、五、三。
P2所分配的资源为：三个零，两个零，两个零二。
Resource needs for P2: 6 0 0 
当前可用的资源数量分别为：七、五、三。
分配后可用的资源：10，5，5。
P4项目所分配的资源为：零、零、二。
Resource needs for P4: 4 3 1 
现有资源状况：数量分别为10、5、5。
分配后的可用资源：10，5，7。
System is in a safe state.
Safe sequence: P1 P3 P0 P2 P4

随机生成数据

#include 
#include 
#include 
const int num_processes = 5;
const int num_resources = 3;
bool isSafeState(int available[], int max_demand[][num_resources], int allocated[][num_resources], int safe_sequence[]) {
    int need[num_processes][num_resources];
    int work[num_resources];
    bool finish[num_processes] = { false };
    // Calculate the need matrix
    for (int i = 0; i < num_processes; i++) {
        for (int j = 0; j < num_resources; j++) {
            need[i][j] = max_demand[i][j] - allocated[i][j];
        }
    }
    // Initialize work array
    for (int j = 0; j < num_resources; j++) {
        work[j] = available[j];
    }
    // Find a process that can be executed
    int count = 0;
    while (count < num_processes) {
        bool found = false;
        for (int i = 0; i < num_processes; i++) {
            if (!finish[i]) {
                bool canExecute = true;
                for (int j = 0; j < num_resources; j++) {
                    if (need[i][j] > work[j]) {
                        canExecute = false;
                        break;
                    }
                }
                if (canExecute) {
                    // Allocate resources to the process
                    for (int j = 0; j < num_resources; j++) {
                        work[j] += allocated[i][j];
                    }
                    finish[i] = true;
                    found = true;
                    count++;
                    safe_sequence[count - 1] = i;
                    break;
                }
            }
        }
        if (!found) {
            break;
        }
    }
    // Check if all processes are finished
    return count == num_processes;
}
int main() {
    // Initialize random seed
    std::srand(static_cast<unsigned int>(std::time(0)));
    int available_resources[num_resources];
    int maximum_demand[num_processes][num_resources];
    int allocated_resources[num_processes][num_resources];
    为现有资源生成随机数值。
    for (int j = 0; j < num_resources; j++) {
        available_resources[j] = std::rand() % 10 + 1;
    }
    生成随机数值以确定最大需求量及分配的资源额度。
    for (int i = 0; i < num_processes; i++) {
        for (int j = 0; j < num_resources; j++) {
            maximum_demand[i][j] = std::rand() % available_resources[j] + 1;
            allocated_resources[i][j] = std::rand() % (maximum_demand[i][j] + 1);
        }
    }
    输出随机生成的数值
    std::cout << "Number of processes: " << num_processes << std::endl;
    std::cout << "Number of resources: " << num_resources << std::endl;
    std::cout << "Available resources: ";
    for (int j = 0; j < num_resources; j++) {
        std::cout << available_resources[j] << " ";
    }
    std::cout << std::endl;
    std::cout << "Maximum demand matrix:" << std::endl;
    for (int i = 0; i < num_processes; i++) {
        for (int j = 0; j < num_resources; j++) {
            std::cout << maximum_demand[i][j] << " ";
        }
        std::cout << std::endl;
    }
    std::cout << "Allocated resources matrix:" << std::endl;
    for (int i = 0; i < num_processes; i++) {
        for (int j = 0; j < num_resources; j++) {
            std::cout << allocated_resources[i][j] << " ";
        }
        std::cout << std::endl;
    }
    int safe_sequence[num_processes];
    确认系统是否处于安全状态，进行检测。
    bool is_safe = isSafeState(available_resources, maximum_demand, allocated_resources, safe_sequence);
    若存在安全序列，请将其打印出来。
    if (is_safe) {
        std::cout << 系统目前处于稳定状态。安全序列为：;
        for (int i = 0; i < num_processes; i++) {
            std::cout << safe_sequence[i] << " ";
        }
        std::cout << std::endl;
    } else {
        std::cout << 系统目前处于不稳定状态。 << std::endl;
    }
    return 0;
}

测试结果：1

Number of processes: 5
Number of resources: 3
Available resources: 7 8 6 
Maximum demand matrix:
7 1 2 
4 2 3 
1 4 1 
4 1 5 
6 6 2 
Allocated resources matrix:
2 0 0 
4 1 2 
1 2 1 
0 1 1 
4 2 2 
系统目前处于安全状态，其安全序列依次为：零、一、二、三、四。

测试结果：2

Number of processes: 5
Number of resources: 3
Available resources: 3 4 3 
Maximum demand matrix:
4 4 5 
3 4 4 
3 4 5 
5 6 4 
3 6 5 
Allocated resources matrix:
3 1 0 
0 3 2 
3 2 0 
0 2 1 
1 0 3 
系统目前处于安全状态，其安全序列依次为：一、零、二、三、四。

测试结果：3

Number of processes: 5
Number of resources: 3
Available resources: 3 4 3 
Maximum demand matrix:
9 8 8 
10 11 9 
9 9 9 
10 10 9 
8 9 8 
Allocated resources matrix:
4 0 1 
7 2 4 
8 4 2 
7 10 2 
4 9 1 
系统目前处于不稳定状态。

加入微信交流群：************ ，请猛戳这里→点击入群