一、实验目的

通过银行家算法设计与实现，可以加深对死锁的理解，掌握死锁的预防、避免、检测和解除的基本原理，重点掌握死锁的避免方法—银行家算法。使学生初步具有研究、设计、编制和调试操作系统模块的能力。

二、实验内容与要求

• 设计银行家算法的核心数据结构、安全性检查算法；
• 画出银行家算法流程图；
• 编程实现算法功能；
• 给出运行结果、测试界面截图、程序清单；
• 工作量要求：完成以上设计要求中的所有算法功能

可以用下面的数据作为测试数据

假定系统中有五个进程｛P0, P1, P2, P3, P4｝和三类资源｛A, B, C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图所示。

先判断系统在T0时刻是否处于安全状态。

请求序列

（1）P1发出请求向量Request1(1，0，2)

（2）P4发出请求向量Request4(3，3，0)

（3）P0发出请求向量Request0(0，2，0)

三、实验报告

1. 算法流程图

2. 数据结构说明

• Max：最大需求矩阵，表示每个进程对每种资源的最大需求。
• Allocation：资源分配矩阵，表示每个进程已经分配的资源数量。
• Need：需求矩阵，表示每个进程剩余需要的资源数量（Need[i][j] = Max[i][j] - Allocation[i][j]）。
• Available：表示每种资源当前的可用数量。
• safeArray：用于存储安全序列，记录系统处于安全状态时进程的执行顺序。

3. 实验流程

1. 初始化数据： 在 main() 函数中，首先初始化了 Max、Allocation、Available 等矩阵和数组，并计算出 Need 矩阵。Need[i][j] 表示进程 i 对资源 j 的剩余需求，Need[i][j] = Max[i][j] - Allocation[i][j]。

2. 安全性检查（isSafe()****）： isSafe() 函数用于判断系统在当前状态下是否安全。该函数的工作流程如下：

   • 创建一个工作向量 Work，初始化为 Available（当前可用资源）。
   • 创建一个 FinishLocal 数组，用于记录进程是否完成。
   • 通过多次循环尝试查找可以完成的进程。对于每个进程，判断其需求是否小于等于当前工作向量中的可用资源。如果是，该进程可以完成，释放其已分配的资源，并将其加入到安全序列中。循环继续直到没有进程能够完成。
   • 如果所有进程都能完成，则返回 true，表示系统处于安全状态；否则，返回 false，表示系统不安全。

3. 资源请求处理（requestResources()）： 当进程请求资源时，requestResources() 函数会执行以下操作：

   • 步骤1：检查进程请求的资源是否小于等于其需求量，如果大于其需求量，直接返回请求失败。
   • 步骤2：检查请求的资源是否小于等于当前系统中可用的资源量。如果可用资源不足，返回请求失败。
   • 步骤3：假设资源可以分配给进程，更新 Available、Allocation 和 Need 矩阵。
   • 步骤4：调用 isSafe() 检查系统是否进入安全状态。如果是安全状态，返回请求成功；否则，恢复资源分配并返回请求失败。

4. 多线程模拟进程请求（processRequest()）：

   • 该函数接收一个线程参数 processIndex，表示请求资源的进程编号。
   • 进程首先输入请求的资源数量，然后调用 requestResources() 函数处理资源请求。
   • 使用 sem_wait() 和 sem_post() 来确保每次只有一个进程能够请求资源，从而避免并发访问共享资源引发的冲突。

5. Main函数及进程模拟：

   • 主函数 main() 允许用户选择是否有进程请求资源。如果有，用户输入进程编号并输入资源请求的数量，程序模拟该进程的资源请求过程。
   • 每次请求都会调用 requestResources() 判断系统是否安全，并打印安全序列或报错信息。

4. 代码实现

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <pthread.h>
#include <semaphore.h>

#define MAX_PROCESSES 5  // 最大进程数
#define MAX_RESOURCES 3  // 资源种类数

// 全局变量定义
int Max[MAX_PROCESSES][MAX_RESOURCES] = {
    {7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 2}, {4, 3, 3}
};

int Allocation[MAX_PROCESSES][MAX_RESOURCES] = {
    {0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}
};

int Need[MAX_PROCESSES][MAX_RESOURCES];
int Available[MAX_RESOURCES] = {3, 3, 2};
int safeArray[MAX_PROCESSES];    // 安全序列 
int n = 5, m = 3;               // 进程数和资源种类数

sem_t sem;  // 信号量，用于进程同步

// 安全性检查函数
bool isSafe()
{
    int Work[MAX_RESOURCES];
    int i, j;
    
    // 初始化工作向量为当前可用资源
    for (i = 0; i < m; i++) 
        Work[i] = Available[i];    
    
    // 进行试探分配时进程完成的标志 
    bool FinishLocal[MAX_PROCESSES] = {false};
    
    int safeCount = 0;  // 安全序列中的进程数量 
    
    while (true)
    {
        // 检查每次循环是否能找到一个可以顺利完成的进程
        bool found = false;        
        for (i = 0; i < n; i++)
        {
            if (!FinishLocal[i])
            {
                // 判断进程i是否可以顺利完成
                bool canFinish = true;
                for (j = 0; j < m; j++)
                {
                    // 如果进程i需要的资源大于可用资源
                    if (Need[i][j] > Work[j])    
                    {
                        canFinish = false;
                        break;
                    }
                }
                
                // 进程可以完成，释放分配给该进程的资源
                if (canFinish)
                {
                    for (j = 0; j < m; j++) 
                        Work[j] += Allocation[i][j]; 
                    
                    FinishLocal[i] = true;
                    // 将能够顺利完成的进程加入安全序列
                    safeArray[safeCount++] = i;    
                    found = true;
                    break; 
                } 
            }
        }
        
        // 如果没有进程可以完成，跳出循环
        if (!found) break; 
    }
    
    // 检查是否所有进程都完成
    for (i = 0; i < n; i++)
        if (!FinishLocal[i]) 
            return false;
    
    return true; 
}

// 请求和分配资源函数
bool requestResources(int processId, int Request[MAX_RESOURCES])
{
    int i;
    // 确认请求小于等于Need
    for (i = 0; i < m; i++)
    {
        if (Request[i] > Need[processId][i])
        {
            printf("请求错误！进程 %d 请求超出它的需求！\n", processId);
            return false; 
        }
    }
    
    // 确认请求小于等于Available
    for (i = 0; i < m; i++)
    {
        if (Request[i] > Available[i])
        {
            printf("没有足够的资源，请等待！\n");
            return false;
        }
    }
    
    // 假设资源分配给进程
    for (i = 0; i < m; i++)
    {
        Available[i] -= Request[i];
        Allocation[processId][i] += Request[i];
        Need[processId][i] -= Request[i]; 
    }
    
    // 检查系统是否安全
    if (isSafe())
    {
        printf("系统处于安全状态\n");
        
        // 输出安全序列
        printf("当前安全序列：");
        for (i = 0; i < n; i++) 
            printf("P%d   ", safeArray[i]);
        printf("\n");
        
        return true; 
    }
    else  // 恢复资源分配
    {
        for (i = 0; i < m; i++)
        {
            Available[i] += Request[i];
            Allocation[processId][i] -= Request[i];
            Need[processId][i] += Request[i]; 
        }
        printf("该请求会导致系统处于不安全状态！\n");
        return false; 
    }
}

// 模拟进程请求资源函数
void* processRequest(void* arg)
{
    int processId = *(int*)arg;
    int Request[MAX_RESOURCES];
    
    int i;
    printf("请输入进程 %d 请求的资源数量：", processId);
    for (i = 0; i < m; i++) 
        scanf("%d", &Request[i]);
    
    sem_wait(&sem);  // 获取信号量
    
    if(requestResources(processId, Request))
        printf("进程 %d 成功获得资源！\n", processId);
    else 
        printf("进程 %d 请求资源失败！\n", processId); 
    
    sem_post(&sem);  // 释放信号量
    return NULL;
}

int main()
{
    int i, j;
    
    // 计算Need矩阵
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
            Need[i][j] = Max[i][j] - Allocation[i][j];
            
    // 显示初始资源分配情况
    printf("最大需求矩阵Max：\n");
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++) 
            printf("\t%d", Max[i][j]);
        printf("\n");
    }
    
    printf("\n分配矩阵Allocation：\n");
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++) 
            printf("\t%d", Allocation[i][j]);
        printf("\n");
    }
    
    printf("\n进程剩余需求矩阵Need：\n");
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++) 
            printf("\t%d", Need[i][j]);
        printf("\n");
    }
    
    // 初始化信号量
    sem_init(&sem, 0, 1);
    
    // 主循环，处理用户请求
    while(true)
    {
        char s[5];
        printf("\n是否有进程请求资源？yes or no：");
        scanf("%s", s);
        
        if (strcmp(s, "no") == 0) 
            break;
        
        int processId;
        printf("请输入请求资源的进程号（0~4）：");
        scanf("%d", &processId);
        
        if (processId < 0 || processId >= MAX_PROCESSES)
        {
            printf("进程号无效，请重新输入！\n");
            continue;
        }
        
        // 创建线程处理资源请求
        pthread_t thread;
        pthread_create(&thread, NULL, processRequest, &processId);
        pthread_join(thread, NULL);
    }
    
    // 销毁信号量
    sem_destroy(&sem);
    return 0;
}

5. 运行效果