前言

操作系统系列博客的所有实验源自于课程"操作系统原理与实践检验"，代码是参考老师给的"软件工程专业操作系统实验指导书"文档后的改进版本。操作系统是计算机系统的核心，因此了解操作系统的设计和实现思路是必不可少的。了解操作系统的基本要求是：理解进程的概念，理解死锁，掌握银行家算法；掌握页式储存管理的实现原理以及页面置换法

实验目的

进一步理解利用银行家算法避免死锁的问题
在了解和掌握银行家算法的基础上，编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性
理解和掌握安全序列、安全性算法

实验内容

了解和理解死锁
理解利用银行家算法避免死锁的原理

实验过程

数据结构：

Available：一维数组，系统可用资源列表

Max：二维数组，进程运行完成所需要的资源总数

Need：二维数组，进程到达就绪状态还需要的资源数

Allocation：二维数组，进程已经获得的资源数
安全状态

首先要了解的是：什么是系统的安全状态？

安全状态是指：在当前情况下，系统能够按照某种执行顺序，为每个进程分配足够的资源，使它们能够顺利完成
银行家算法

顾名思义，银行家算法的就是把计算机系统比喻为银行，进程比喻为来贷款的人。要发放贷款最基本的要求是银行金库中还有钱，并且贷款的人有能力还款，这对应了计算机系统中的剩余资源和进程申请资源时不能超过进程需要的最大资源。核心的要求是银行在发放了贷款之后，能通过某种还款顺序保证不出现坏账，对应计算机系统中就是进程能够以某种安全序列完成任务

其中安全检查的步骤如下：
1. 如果Request_i <= Need_i，则继续以下检查，否则显示需求申请超过该进程最大需求值的错误
2. 如果Request <= Available，则继续以下检查，否则显示系统无足够资源，该进程需要继续阻塞等待
3. 系统试着把资源先分配给该进程，并修改相应的数据结构值：
  1
  2
  3
  4
  // i是进程ID的索引，j是资源的索引
  Available[j] -= Request[j];
  Allocation[i][j] += Request[j];
  Need[i][j] -= Request[j];
4. 系统执行安全性算法，检查此次资源分配之后，系统是否处于安全状态。若系统找到了一个安全序列，则本次分配正式结束。若系统找不到安全序列，则本次分配作废，系统恢复到未分配之前的状态
安全性算法

安全性算法就是判断系统能否找到一个安全序列的算法。在本次实验中，我们使用了两个数组变量：
- 工作向量Work：它表示系统可用资源的数目，在安全算法刚开始时，Work = Available
- 标记向量Finish：它表示系统能否有足够的资源分配给进程，使进程运行完成，同时也记录了安全序列
从进程集合中找到一个能满足下述条件的进程，若找到则执行下一步
- Finish[i] = false
- Need[i][j] <= Work[j]
当进程获得资源后，该进程可顺利运行至完成，并释放出分配给该进程的所有资源，此时可回收资源：
1
2
Work[j] += Allocation[i][j];
Finish[i] = true;
重复执行上两个步骤，如果所有进程都完成了，则表示系统处于安全状态，否则系统处于不安全状态

代码汇总

# include <iostream>
# include <cstdio>
# include <cstdlib>
# include <ctime>

// 调试模式
# define DEBUG true
// 系统资源的数量
# define RESOURCES 3
// 系统进程数量
# define PROCESS 5

// 系统可用资源列表
int Available[RESOURCES] = {3, 3, 2};
// 进程运行所需要的总资源
int Max[PROCESS][RESOURCES] = {{7, 5, 3},{3, 2, 2},{9, 0, 2},{2, 2, 2},{4, 3, 3}};
// 进程达到就绪状态还需要的资源
int Need[PROCESS][RESOURCES] = {{7, 4, 3},{1, 2, 2},{6, 0, 0},{0, 1, 1},{4, 3, 1}};
// 已经分配给进程的资源
int Allocation[PROCESS][RESOURCES] = {{0, 1, 0},{2, 0, 0},{3, 0, 2},{2, 1, 1},{0, 0, 2}};

// 系统初始化
void init()
{
    if (DEBUG)
    {
        printf("Debug模式，银行家账本使用书中的例子\n");
        return;
    }
    else
    {
        printf("非Debug模式，银行家账本随机生成\n");
        // 随机产生资源和使用情况
        srand(time(NULL));
        for (int i = 0; i < PROCESS; i++)
        {
            for (int j = 0; j < RESOURCES; j++)
            {
                Available[j] = rand() % 5 + 15;
                Max[i][j] = rand() % 7 + 1;
                Allocation[i][j] = rand() % 3 + 1;
                Need[i][j] = Max[i][j] - Allocation[i][j];
            }
        }
    }
}

// 查看当前账本
void ps()
{
    printf("\n====================银行家账本===================\n");
    printf("\nAvailable: ");
    for (int i = 0; i < RESOURCES; i++)
    {
        printf("%3d ", Available[i]);
    }
    printf("\nProcess | Allocation | Need\n");
    // Process
    for (int i = 0; i < PROCESS; i++)
    {
        printf("%5d |", i);
        // Allocation
        for (int j = 0; j < RESOURCES; j++)
        {
            printf("%3d", Allocation[i][j]);
        }
        printf(" | ");
        // Need
        for (int k = 0; k < RESOURCES; k++)
        {
            printf("%3d", Need[i][k]);
        }
        printf("\n");
    }
    printf("=================================================\n\n");
}

/**
 * 银行家算法
 * pid：当前要运行的进程
 * no：当前运行的进程顺序
 * work：当前系统可用资源
 * finish：记录进程完成状态和顺序
 **/
bool bank(int pid, int no, int work[], int finish[])
{
    printf("新一轮运行尝试，尝试的pid: %d，no: %d\n", pid, no);
    // 判断当前系统资源能否满足当前进程运行
    for (int i = 0; i < RESOURCES; i++)
    {
        // 不满足运行条件，终止本次尝试，向上回溯
        if (work[i] < Need[pid][i])
        {
            printf("当前pid: %d, 可用的资源: %d, 需要的资源: %d。不满足运行条件！\n", pid, work[i], Need[pid][i]);
            return false;
        }
    }
    // 当前资源满足了当前进程运行
    // 标记当前进程已完成
    finish[pid] = no;
    // 释放资源
    for (int i = 0; i < RESOURCES; i++)
    {
        work[i] += Allocation[pid][i];
    }
    printf("当前进程成功运行完成: %d, 是第 %d 个完成的进程。寻找下一个可运行的进程......\n", pid, no);
    // 判断系统是否运行完成
    if (no >= PROCESS)
    {
        printf("分配完毕，系统安全！安全序列：");
        for (int i = 1; i <= PROCESS; i++)
        {
            for (int j = 0; j < PROCESS; j++)
            {
                if (finish[j] == i)
                {
                    printf("%d -> ", j);
                }
            }
        }
        printf("finish\n");
        return true;
    }
    // 寻找下一个未完成的进程
    for (int i = 0; i < PROCESS; i++)
    {
        if (!finish[i])
        {
            bool flag = bank(i, no + 1, work, finish);
            if (flag)
                return true;
        }
    }
    // 没有下一个可以运行的进程了，系统进入不安全状态，往上回溯
    for (int i = 0; i < RESOURCES; i++)
    {
        work[i] -= Allocation[pid][i];
    }
    finish[pid] = 0;
    printf("没有下一个可以运行的进程了，系统进入不安全状态，往上回溯。当前进程pid:%d,no:%d\n", pid, no);
    return false;
}

/**
 * 申请使用资源
 * pid：申请资源的进程ID
 * req_list：申请的资源列表
 **/
void request(int pid, int req_list[])
{
    // pid校验
    if (pid >= PROCESS)
    {
        printf("进程ID非法！\n");
        return;
    }
    // req_list校验
    for (int i = 0; i < RESOURCES; i++)
    {
        if (req_list[i] > Need[pid][i])
        {
            printf("请求了过多的资源，分配终止！\n");
            return;
        }
        if (req_list[i] > Available[i])
        {
            printf("系统可用资源不足，无法分配！\n");
            return;
        }
    }
    // 使用银行家算法判断系统是否安全
    int work[RESOURCES], finish[PROCESS];
    for (int i = 0; i < PROCESS; i++)
    {
        finish[i] = 0;
    }
    // 试探性分配，然后检查是否安全
    for (int i = 0; i < RESOURCES; i++)
    {
        Available[i] -= req_list[i];
        Allocation[pid][i] += req_list[i];
        Need[pid][i] -= req_list[i];
        work[i] = Available[i];
    }
    // 检查是否安全
    bool safe = false;
    for (int i = 0; i < PROCESS; i++)
    {
        if (bank(i, 1, work, finish))
        {
            safe = true;
            break;
        }
    }
    // 如果系统安全，则本次分配完成
    if (safe)
    {
        printf("本次分配完成！\n");
        ps();
    }
    else
    {
        // 分配不安全，本次分配作废
        for (int i = 0; i < RESOURCES; i++)
        {
            Available[i] += req_list[i];
            Allocation[pid][i] -= req_list[i];
            Need[pid][i] += req_list[i];
        }
        printf("没有安全的分配方案，请求资源失败！\n");
        return;
    }
}

void terminal()
{
    char cmdstr[32];
    int cmd, req_id, req_list[3];
    while (1)
    {
        printf("cmd: ");
        scanf("%s", cmdstr);

        if (!strcmp(cmdstr, "exit"))
        {
            return;
        }

        if (!strcmp(cmdstr, "help"))
        {
            printf("\n=================================================\n");
            printf("请求资源: request\n");
            printf("查看当前银行家账本: ps\n");
            printf("获取帮助: help\n");
            printf("退出: exit\n");
            printf("=================================================\n\n");
            continue;
        }

        if (!strcmp(cmdstr, "ps"))
        {
            ps();
            continue;
        }

        if (!strcmp(cmdstr, "request"))
        {
            printf("要申请资源的进程ID: ");
            scanf("%d", &req_id);
            printf("要申请的资源的数量: ");
            scanf("%d %d %d", &req_list[0], &req_list[1], &req_list[2]);
            request(req_id, req_list);
            continue;
        }

        printf("cmd: 未知的命令！\n");
    }
}

int main(int argc, char const *argv[])
{
    init();
    ps();
    terminal();
    return 0;
}

实验测试

编译运行程序，这里就不放截图了
1
2
g++ bank.cpp -o bank
./bank
使用help命令查看帮助信息
使用ps命令查看当前账本
使用request申请资源，查看系统运行过程

总结

本次实验我们实现了银行家算法，了解了系统为了防止死锁发生所做的工作。在现代的商业系统中，可能有许多的进程，要防止死锁的代价是非常高的，所以这些系统都采取了消极的措施，就是不管死锁的发生，也不去处理，在真正出现问题的时候，重启还是一个比较快的方法。但在一些高可靠性的系统中，可能系统的进程数量比较少，而且因为业务的要求，系统必须采取措施来防止死锁的发生，这时候银行家算法就有用武之地了

课后思考

在编程中遇到了哪些问题？你是如何解决的？

一开始想要以非递归的方法实现安全性检测，但是发现代码十分混乱而且比较难理解，改用递归的方法之后就好很多了。有了思路之后，实现算法的速度还是挺快的
在安全性算法中，为什么不用变量Available，而又定义一个临时变量Work？

因为在递归调用安全性检测的算法过程中，一直需要对系统可用资源进行调整，直接用Available变量会导致算法在找到安全序列之后还要向上回溯，恢复Available的值，因此定义一个临时变量Work更为方便