死锁预防之银行家算法

admin管理员组

文章数量:1531374

死锁预防之银行家算法

• 死锁
• • 死锁的定义
  • 死锁的产生
  • 死锁的描述
  • 死锁避免算法
• 银行家算法
• • 设计思想
  • 分析
  • 使用数据结构的描述
  • 使用到的函数
  • • 主函数执行的流程
  • 银行家算法的逻辑
• 完整的程序代码
• 运行结果

自己使用的运行环境为linux下，但是在windows下应该也可以，只是使用了简单的矩阵加减运算和基础语法
源码链接：https://github/duchenlong/linux-text/tree/master/lombard
运行方式：./main

死锁

早期的操作系统中，当进程需要申请某一个资源的时候，只有该资源还可以分配，那么就会直接分配给这个进程。

但是在实践中，如果对资源不加限制的分配可能会导致进程间由于竞争资源而相互制约，以至于无法继续运行，进而发生死锁现象。

死锁的定义

进程处于等待状态，并且等待的事件永远不会发生

死锁的产生

1. 当一个线程对同一个互斥量加锁两次，那么他自身就会陷入死锁中

2. 当一个线程在退出的时候，没有释放已占有的互斥量，那么也很容易发生死锁现象

3. 当程序中有多个互斥锁存在的时候，两个或者多个已经上锁的线程之间互相申请对方的互斥锁资源，就会使双方都陷入永久等待的状态，从而产生死锁

死锁的描述

在有向图中，使用圆圈表示进程，使用方框表示互斥量。

那么，申请资源就可以看成一个，从进程到互斥量的一条有向边；

同理，占用资源就可以看做是一个，从互斥量到进程的一条有向边

这样就可以在宏观上，构成一个资源分配图，当资源分配图中出现一个环路的时候，就说明当前系统发生了死锁。

具体的程序实现死锁的现象，可以参考之前写的博文： 互斥锁与死锁(linux多线程)

死锁避免算法

对于之前的分析，当死锁发生的时候，我们的资源分配图中会出现一个环路的现象。

那么我们就可以对于每一个分配资源的过程，都构成一个有向边 ，当每次需要分配资源的时候，先对这个资源分配表进行检测，判断当该锁资源分配给该进程后，是否会发生死锁现象。如果出现了环路，就说明会发生死锁，然后进入相应的逻辑中，进行死锁的避免。

而第二种方法便是著名的银行家算法，他的提出者又是迪杰斯特拉

银行家算法

银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行

设计思想

模拟一个银行贷款的过程，当用户向银行申请贷款信息时，不是用户要多少钱，银行都会交给用户多少钱的。不然随便一个人都去找银行申请天价的贷款，那银行不就快倒闭了。

银行的做法是：你来申请贷款的时候，带上你的身份证和工资卡，然后根据情况给你合理的额度，确保你可以在一定时间中还上来这些钱（分期付款）。

而银行家算法，在银行借贷思想上，做了一个优化，他的精髓之处就在于，进程可以根据自己的需要，然后在不超过自己申请的最大资源的基础上，分阶段动态的向操作系统获取执行的资源

此时银行家会内部计算一下，这次计算的目的就是，确保用户索要的资源符合一开始的预期，要讲武德，不能贪心 ，不能超过了自己申请的资源。

注意：在银行家算法中，进程可以分阶段向系统进行申请资源，但是必须在一定时间内归还资源。借出去的钱，我得确保你在一定时间内可以还给我

那么，单用户的情况已经进行了模拟，他的精髓就在于，可以超额放出贷款。所谓富贵险中求

有这样一个场景：

按照我们自给自足的小农思维，被人借钱的时候，如果我没有那么多钱，那么我是不会借给别人的。

但是银行家却不这样来，我只要确保我余下的钱，可以满足至少一个人的需求，等到这个人满足后把钱还给我，这样我的本钱就多了，再重复这个步骤，确定我可以让每个人都得到钱，那么我就可以把这个钱交给你。（可以仔细思考思考这个过程）

百度百科
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构

分析

在老师给的测试数据中，程序是在系统分配了一些资源后的一个阶段的状态，并不是一开始的状态。

并且，对于运行过程中所参与进来的进程都是事先规定好的，中途加入一个新的进程的功能可以暂时不用实现，哈哈。

实验的目的主要就是，让我们在事中，对银行家算法的分配流程进行一个模拟，可以对银行家算法有一个深刻的印象。

而对于随后某一个进程在运行过程中需要的资源，我们选择通过控制台进行一次输入，指定哪个进程需要申请资源，并且得到该进程具体需要申请每一类资源的数量，然后再调用银行家算法的验证过程，判断是否可以分配。

使用数据结构的描述

使用vector可变列表的原因：在后面的算法中，需对原数据进行操作，可以用vector内部的拷贝函数，降低书写中的一些拷贝的程序

Max二维数组

负责记录每一个进程在执行期间，需要的全部资源数，因为可能存在多种不同的资源，所以使用二维数组来描述。

列表	意义
数组的行号	当前正在申请的进程编号
数组的列号	当前需要申请的该类资源数量
Max[i][j]	进程i需要申请j类资源，Max[i][j]个

Allocation二维数组

负责记录每个进程在执行的过程中，已经分配的每种资源数。

列表	意义
数组的行号	当前正在申请的进程编号
数组的列号	当前已经得到的该类资源数量
Allocation [i][j]	进程i已经得到j类资源，Allocation [i][j]个

Need 二维数组

负责记录每个进程之后的执行过程中，还需要的每种资源数

列表	意义
数组的行号	当前正在申请的进程编号
数组的列号	之后还需要该类资源的数量
Need [i][j]	进程i还需要得到j类资源，Need [i][j]个

Available 一维数组

就是我当前的操作系统中，还拥有的每种资源的数量。我们只有一个可以分配资源的系统。

列表	意义
数组的列号	系统还剩余的该类资源的数量
Available [i]	系统还有i类资源，Available [i]个

SafrOrder一维数组

保存一个可以安全执行的序列

Request 一维数组
idx 变量

我们模拟进程在调度的过程中，某一个阶段需要得到的资源的数量，然后存在当前数组中。

和idx配合使用，表示给idx进程分配的每种资源数量

ID 一维数组

可有可无

单纯的实验要求，每个进程有一个自己的名称，就像P0，P1…

ProVis一维数组
NoAllocCnt 变量

可有可无，自己后期为了方便加上的

列表	描述
ProVis[i]	i进程是否已经完全分配 ；true -> 分配完全，false -> 还在执行的过程中
NoAllocCnt	当前还在执行过程中的进程数

使用到的函数

主函数执行的流程

需要注意的一个函数逻辑，那就是银行家算法的逻辑了

银行家算法的逻辑

// 得到第一个可以释放的进程号，没有返回-1
int GetFirst(vector<int>& t, vector<bool>& vis);

// 确定资源可以分配时，进行资源分配的工作
void check();

// 执行银行家算法            
bool banker();

具体验证该资源是否分配，就需要再进一步细分一下

完整的程序代码

main.cpp 主函数部分

#include "head.hpp"

char buf;

int main() {
    system("clear");
    init();
    if(!banker()) return 0;
    
    display();  // 显示当前资源
    while (isExit() == false) {
        bool ret = input();    // 输入
        
        if(ret)
            banker();   // 执行银行家算法

        display();  // 显示当前资源
        cout << "按任意键继续 ~~~~~~~~~~~" << endl;
        fflush(stdout);
        getchar();
    }

    return 0;
}

head.hpp 头文件

#ifndef __HEAD_HPP__
#define __HEAD_HPP__ 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

#define MAXNUM      20      // 最大行号
#define RESOURCECNT 3       // 系统资源数
#define PROCESSCNT  5       // 系统进程数

extern vector<string> ID;                  //  每个进程的名称
extern vector<int> Available;              //  系统可分配资源
extern vector<vector<int> > Max;           //  每个进程对每种资源的需求
extern vector<vector<int> > Allocation;    //  每个进程已经分配的每种资源
extern vector<vector<int> > Need;          //  进程还需要资源
extern vector<int> SafeOrder;              //  安全执行的顺序
extern vector<int> Request;                //  进程请求资源量
extern int idx;                            //  请求的进程编号
extern int NoAllocCnt;                     //  当前没有分配完全的进程数
extern vector<bool> ProVis;                //  当前进程是否已经完全分配


void init();                                // 初始化
void display();                             // 显示系统资源，未结束的进程占用资源情况
bool banker();                              // 执行银行家算法
bool input();                               // 输入分配指定进程的资源
bool isExit();                              // 所有进程是否都得到了资源
#endif 

head.cpp 头文件中函数的实现

#include "head.hpp"

vector<bool> ProVis;                //  当前进程是否已经完全分配
vector<string> ID;                  //  每个进程的名称
vector<vector<int> > Max;           //  每个进程对每种资源的需求
vector<vector<int> > Allocation;    //  每个进程已经分配的每种资源
vector<vector<int> > Need;          //  进程还需要资源
vector<int> Request;                //  进程请求资源量
vector<int> SafeOrder;              //  安全执行的顺序
vector<int> Available;              //  系统可分配资源
int idx;                            //  请求的进程编号
int NoAllocCnt;                     //  当前没有分配完全的进程数

// 初始化
void init() {
    ID          = {"P0","P1","P2","P3","P4"};
    Available   = {3,3,2};
    Max         = {{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
    Allocation  = {{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};
    Need        = {{7,4,3},{1,2,2},{6,0,0},{0,1,1},{4,3,1}};

    idx = -1;
    NoAllocCnt = PROCESSCNT;
    ProVis.resize(PROCESSCNT,false);
    Request.reserve(RESOURCECNT);
    //SafeOrder.resize(PROCESSCNT,-1);
    for(int i = 0; i < PROCESSCNT; i++) SafeOrder.push_back(i);
}


// 显示系统资源，未结束的进程占用资源情况                            
void display() {
    printf("\n\n\n-----------------------------------------\n");
    printf("当前系统可用资源: \n");
    for(int i = 0; i < RESOURCECNT; i++) printf("\t%c",'A' + i);
    printf("\n");
    for(int i = 0; i < RESOURCECNT; i++) printf("\t%d",Available[i]);
    printf("\n\n");

    printf("正在执行进程的资源分配情况： \n");
    printf("ID \tMAX \t Allocation \t Need \n");
    for(int i = 0; i < NoAllocCnt; i++) {
        int p = SafeOrder[i];
        cout << ID[p] << "\t";
        for(int j = 0; j < RESOURCECNT; j++) cout << Max[p][j] << " ";
        cout << " \t    ";

        for(int j = 0; j < RESOURCECNT; j++) cout << Allocation[p][j] << " ";
        cout << " \t";

        for(int j = 0; j < RESOURCECNT; j++) cout << Need[p][j] << " ";
        cout << "\n";
    }
    
    cout << "\n 安全分配的序列： ";
    for(int i = 0; i < NoAllocCnt; i++){
        cout << SafeOrder[i];
        if(i != NoAllocCnt - 1) cout << " -> ";
    }
    cout << "\n\n";
}

// 得到第一个可以释放的进程号，没有返回-1
int GetFirst(vector<int>& t, vector<bool>& vis) {
    
    for(int i = 0; i < PROCESSCNT; i++) {
        if(vis[i]) continue;
        int j = 0;
        for(; j < RESOURCECNT; j++) {
            if(Need[i][j] > t[j]) break;
        }
        if(j == RESOURCECNT) return i;
    }

    return -1;
}

void check() {
    if(idx == -1) return ; 
    bool flag = true;
    for(int i = 0; i < RESOURCECNT; i++) {
        Allocation[idx][i] += Request[i];
        Need[idx][i] -= Request[i];
        Available[i] -= Request[i];
        if(Need[idx][i] != 0) flag = false;
    }
    
    // 可以释放
    if(flag) {
        ProVis[idx] = true;
        for(int i = 0; i < NoAllocCnt; i++)
            if(SafeOrder[i] == idx){
                NoAllocCnt --;
                SafeOrder.erase(SafeOrder.begin() + i);
                ProVis[idx] = true;
                for(int j = 0; j < RESOURCECNT; j++)
                    Available[j] += Max[idx][j];
                break;
            }

    }
}

// 执行银行家算法            
bool banker() {
    vector<int> t = Available;          // 当前系统资源的副本
    vector<bool> vis = ProVis;          // 当前可分配资源的副本
    vector<int> newOrder = SafeOrder;   // 安全序列的副本
    vector<int> tIdx;                   // 请求分配进程的Need的副本

    if(idx != -1) {
        tIdx = Need[idx];
        // 减去请求分配的资源
        for(int i = 0; i < RESOURCECNT; i++) {
            t[i] -= Request[i];
            Need[idx][i] -= Request[i];
        }
    }

    for(int i = 0; i < NoAllocCnt; i++) {
        int index = GetFirst(t,vis);
        // cout << index << " ";
        if(index == -1) {
            if(idx != -1) Need[idx] = tIdx;
            cout << "\n 当前资源无法分配 ~~~~~~~~~ " << endl;
            return false; // 存在无法分配资源的进程
        }
        
        for(int j = 0; j < RESOURCECNT; j++) {
            t[j] += Allocation[index][j];           // 当前进程结束后，可以还给操作系统的资源数
            if(index == idx) t[j] += Request[j];    // 是请求分配的资源
        }
        newOrder[i] = index;
        vis[index] = true;
    }
    
    SafeOrder = newOrder;
    if(idx != -1) Need[idx] = tIdx;
    // 可以成功分配，检查idx是否可以释放
    check();
    
    idx = -1;
    return true;
}

// 输入分配资源
bool input() {
    printf("\n\n=========================================\n\n");
    printf("请输入需要分配资源的进程号，例如 P0 : 0  -> ");
    fflush(stdout);
    cin >> idx;
    // cout <<" ------" <<  idx << endl;
    if(idx < 0 || idx >= PROCESSCNT || ProVis[idx]) {
        cout << " 输入进程号不合法 ~~~~~~" << endl;
        return false;
    }
    
    bool flag = true;
    for(int i = 0; i < RESOURCECNT; i++) {
        printf(" 分配给 [%d] 号进程 [%c] 资源的数量为 -> ",idx,(char)('A' + i));
        cin >> Request[i];
        if(Request[i] > Need[idx][i] || Available[i] < Request[i]) flag = false;
        cout << endl;
    }
    if(!flag) cout << " 当前资源分配不合理(和需求不相符，或者超过最大资源)，不能分配 ~~~~~~~~" << endl;
    return flag;
}

// 所有进程是否都得到了资源                    
bool isExit() {
    return NoAllocCnt == 0;
}                            

运行结果

开始界面，需要的资源已经在程序中输入

资源分配

资源分配不合理

本文标签： 死锁银行家算法