关于银行家调度算法预防死锁

沉默的菜鸟

今天上机的实习题是实现银行家算法，上次有个老哥写了一个C语言版的银行家算法，我介绍一个C++版本的。（本人菜鸟，代码是自己原创的，未能很好的简化代码，如有错误麻烦指出，谢谢）
一、银行家算法与死锁

  在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
  银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。
  线程死锁是指由于两个或者多个线程互相持有对方所需要的资源，导致这些线程处于等待状态，无法前往执行。当线程进入对象的synchronized代码块时，便占有了资源，直到它退出该代码块或者调用wait方法，才释放资源，在此期间，其他线程将不能进入该代码块。当线程互相持有对方所需要的资源时，会互相等待对方释放资源，如果线程都不主动释放所占有的资源，将产生死锁
二、银行家算法的核心步骤
  核心步骤就是检查序列是否是安全序列，若是安全序列这将调度顺序记录下来，否则返回死锁提示。
   安全序列是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
三、talk is cheap,show your code

[C++] 纯文本查看 复制代码

// BankerAlgorithm.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include "pch.h"
#include <iostream>
#include <array>
#include <queue>
#include <vector>
using namespace std;

struct Client
{
        array<int, 4> own;
        array<int, 4> need;
        Client(array<int,4>a, array<int,4>b) //有参的构造函数
        {
                unsigned int i;
                for (i=0;i<a.size();i++)
                {
                        own[i] = a[i];
                        need[i] = b[i];
                }
        }
        Client() 
        {
                own.fill(0);
                need.fill(0);
        }
};

struct Resource
{
        array<int, 4>my_resource;
        Resource(array<int, 4>a) //带参数的构造函数
        {
                unsigned int i;
                for (i = 0; i < my_resource.size(); i++)
                {
                        my_resource[i] = a[i];
                }
        }
        Resource()//无参数的构造函数
        {
                my_resource.fill(0);
        }
};

bool lower_than(array<int,4> a, array<int, 4>b) 
{
        return (a[0] <= b[0] && a[1] <= b[1] && a[2] <= b[2] && a[3] <= b[3]);
}


bool is_safe(Client *my_client, int nums, Resource remained_resources, queue<int>&dispatch_array)
{
        vector<bool>finish(nums, false);
        bool temp1 = true;
        bool temp2 = false;
        while (true)
        {
                for (int i = 0; i < nums; i++) 
                {
                        if (finish[i])
                        {
                                continue;
                        }
                        if (lower_than(my_client[i].need,remained_resources.my_resource))//剩余的资源大于某一进程需要的资源
                        {
                                finish[i] = true;
                                dispatch_array.push(i);
                                for (unsigned int j = 0; j < my_client[i].own.size(); j++)
                                {
                                        remained_resources.my_resource.at(j) += my_client[i].own.at(j);//回收资源
                                }
                        }
                }
                for (int i = 0; i < nums; i++)
                {
                        temp1 = temp1 && finish[i];//全为true
                        temp2 = temp2 || finish[i];//全为false
                }
                if (temp1)
                {
                        goto label;
                }
                if (!temp2)
                {
                        temp1 = temp2;
                        goto label;
                }
                temp1 = true;
                temp2 = false;
        }
label:        return temp1;
}


//调度函数
void dispatch(Client *my_client,int nums, Resource &all_resources, Resource &allocated_resources, Resource &remained_resources) 
{
        queue<int>dispatch_array;
        if (!is_safe(my_client,nums,remained_resources,dispatch_array))
        {
                cout << "无法完成调度，系统加死锁！！！";
                return;
        }
        cout << "所有资源总表为：";
        for (unsigned int i = 0; i < all_resources.my_resource.size(); i++)
        {
                cout << all_resources.my_resource.at(i)<<" ";
        }
        cout << endl << endl;
        cout << "未调度前已分配的资源总表为：";
        for (unsigned int i = 0; i < allocated_resources.my_resource.size(); i++)
        {
                cout << allocated_resources.my_resource.at(i) << " ";
        }
        cout << endl << endl;
        cout << "未调度前剩余资源总表为：";
        for (unsigned int i = 0; i < remained_resources.my_resource.size(); i++)
        {
                cout << remained_resources.my_resource.at(i) << " ";
        }
        cout << endl << endl;

        for (int i = 0; i < nums; i++)
        {
                cout << "第 " << i + 1 << " 次调度：" << endl;
                cout << "当前各个进程所占资源的表为：" << endl;
                for (int j = 0; j < nums; j++)
                {
                        cout << "进程 " << j<<": ";
                        for (unsigned int k = 0; k < my_client[j].own.size(); k++)
                        {
                                cout << my_client[j].own.at(k)<<" ";
                        }
                        cout << endl;
                }
                int cur_dispatch_num = dispatch_array.front();//当前调度的进程号
                dispatch_array.pop();
                for (unsigned int k = 0; k < my_client[cur_dispatch_num].own.size(); k++)
                {
                        remained_resources.my_resource.at(k) += my_client[cur_dispatch_num].own.at(k);
                        my_client[cur_dispatch_num].own.at(k) = 0;
                }
                cout << "调度完后各个资源剩余的表为：" << endl;
                for (auto a:remained_resources.my_resource)
                {
                        cout << a << " ";
                }
                cout << endl<<endl;
        }
};

void Init(Client *my_client, int nums,Resource &all_resources, Resource &allocated_resources, Resource &remained_resources)
{
        for (int i = 0; i < nums; i++)//从分配给各个客户(进程)的资源数组中统计已分配的资源
        {
                for (unsigned int j = 0; j < my_client[0].own.size(); j++)
                {
                        allocated_resources.my_resource[j] += my_client[i].own.at(j);
                }
        }
        for (unsigned int i = 0; i < all_resources.my_resource.size(); i++)//用总共的资源减去已分配的资源得到剩余的资源
        {
                remained_resources.my_resource.at(i) = all_resources.my_resource.at(i) - allocated_resources.my_resource.at(i);
        }
}



int main()
{

        Client my_client[5] = 
        { 
                {{3,0,1,1},{1,1,0,0}},
                {{0,1,0,0},{0,1,1,2}},
                {{1,1,1,0},{3,1,0,0}},
                {{1,1,0,1},{0,0,1,0}},
                {{0,0,0,0},{2,1,1,0}}
        };
        Resource all_resources, allocated_resources, remained_resources;
        all_resources.my_resource.at(0) = 6;
        all_resources.my_resource.at(1) = 3;
        all_resources.my_resource.at(2) = 4;
        all_resources.my_resource.at(3) = 2;
        Init(my_client,5,all_resources, allocated_resources, remained_resources);
        dispatch(my_client, 5, all_resources, allocated_resources, remained_resources);
}

这张图是原课本的题目和算法思路：

这张图是运行结果：

银河魔装机神

我们也学了

goldli

支持。

代码的过程参数如果大于3，那么建议使用一个对象或结构来封装。

s02lk

下次我们还实现一哈书中别的算法。嘿嘿嘿

1sina

看不懂 还得继续学习

沉默的菜鸟

s02lk 发表于 2019-5-18 19:41
下次我们还实现一哈书中别的算法。嘿嘿嘿

can't agree more,嘿嘿嘿