[操作系统]银行家算法

C++ 操作系统
操作系统
发布日期:   2021-04-21
文章字数:   2.2k
阅读时长:   9 分
阅读次数:  

题目描述

用程序实现银行家算法，为进程请求资源。

已分配资源数量 资源需求量
A B C A B C
P1 2 1 2 3 4 7
P2 4 0 2 1 3 4
P3 3 0 5 0 0 3
P4 2 0 4 2 2 1
P5 3 1 4 1 1 0

请求序列如下:

a:进程P2请求资源(0,3,4)

b:进程P4请求资源(1,0,1)

c.进程P1请求资源(2,0,1)

d.进程P3请求资源(0,0,2)

程序功能及设计思路

程序功能：

用户输入一个进程请求资源，程序判断能否请求资源，如果分配不会导致死锁则分配资源，否者不能分配，输出告诉用户分配失败。

设计思路：

根据进程请求的资源进行判断，如果请求的资源比资源需求量还大，那么请求是不合理的，直接拒绝。否则预分配资源，预分配后进行安全判断是否会发生死锁（银行家算法），如果不会发生死锁那么就分配成功了，如果会发生死锁就分配失败，把预分配的资源回收。没有进程时结束执行。

程序功能及设计思路

数据结构：

int available[N] = { 2,3,3 }; 
int allocation[M][N] = { {2,1,2},{4,0,2},{3,0,5},{2,0,4},{3,1,4} }; 
int need[M][N] = { {3,4,7},{1,3,4},{0,0,3},{2,2,1},{1,1,0} }; 
int request[N] = { 0,0,0 };

由于资源总数、类型和进程的数量不多，就直接存在了数组中，available为当前系统可用的各种资源量，allocation为各进程当前已分配到的各类资源，need为各进程对资源的剩余需求量，request为当前某进程请求的每种资源量。

算法设计：

//比较两个数组的大小，如果a数组1的每一个元素都大于数组2的对应元素就返回false，否则返回true
bool previousIsBig(int* arr1, int* arr2)
{
    for (int i = 0;i < N;i++)
    {
        if (arr1[i] < arr2[i])
        {//有一个不符合就返回false
            return false;
        }
    }
    //否则返回true
    return true;
}

算法分析：两个数组逐个元素进行比较，只有arr1数组的所有元素大于arr2数组对应位置的所有元素才返回ture，有一个不符合要求就返回false。

//安全状态判别算法
bool safeText()
{
    int i, j;
    bool flag=true;    
    //每个进程运行的状态，初始都为false
    bool finish[M];
    for (i = 0;i < M;i++)
    {
        finish[i] = false;
    }

    //将现有资源转移到work中
    int work[N];
    for (i=0;i < N;i++)
    {
        work[i] = available[i];
    }

    //一直循环查找未完成但是现在能够完成的进程
    while (flag)
    {
        flag = false;
        for (i = 0;i < M;i++)
        {
            if (finish[i] == false && previousIsBig(work, need[i]))
            {//标记为完成且释放掉占用的资源
                finish[i] = true;
                for (j = 0;j < N;j++)
                {//释放资源
                    work[j] += need[i][j];
                }
                flag = true;
            }
        }
    }

    //如果处理完后有一个进程未完成，说明是不安全的
    for (i = 0;i < M;i++)
    {
        if (finish[i] == false) return false;
    }
    //否则就是安全的
    return true;
 }

算法思想：这个算法用于判断是否安全，finish数组用于存储进程的运行状态，初始状态都为未完成false。一直循环查找未完成但是现在能够完成的进程，将这个进程完成并且运行状态标记为true，完成后释放掉所有申请的资源，再继续寻早下一个能完成的资源，直到没有资源可完成。循环结束后对finish的所有元素进行判断，如果为都为true说明所有进程都可以完成，系统是安全的，否则就是有进程无法完成，即系统进入了死锁。

//试探性分配
void distribution(int pi, int* request)
{
    int i = 0;
    for (i;i < N;i++)
    {
        available[i] -= request[i];
        allocation[pi][i] += request[i];
        need[pi][i] -= request[i];
    }
}

算法思想：试探性分配，根据请求的资源，系统可用的各种资源量减少相应的资源数，该进程当前已分配到的各类资源增加，该进程对资源的剩余需求量减少。

//分配失败，取消试探性分配
void cancle(int pi, int* request)
{
    int i = 0;
    for (i;i < N;i++)
    {
        available[i] += request[i];
        allocation[pi][i] -= request[i];
        need[pi][i] += request[i];
    }
}

算法思想：将分配的资源全部回收。

//银行家算法,第一个参数为进程编号，第二个为这个进程各项资源需要的数量
void bank(int pi, int* request)
{
    //先判断需求是否合理
    if (previousIsBig(request, need[pi]))
    {
        //cout << "error" << endl;
        cout << "请求资源数不合理，请求失败!" << endl;
        return;
    }
    //先判断系统是否有足够的盈余资源
    if (!previousIsBig(available, request))
    {
        cout << "系统没有这么多资源，请求失败！" << endl;
        return;
    }
    //试探性分配
    distribution(pi, request);
    //判断是否安全,如果合法就分配
    if (safeText)
    {
        cout << "分配资源成功！" << endl;
        return;
    }

    else
    {//不合法撤回分配
        cancle(pi, request);;
        cout << "分配资源会导致死锁，分配失败！" << endl;
        return;
    }
}

算法思想：先判断请求资源是否合理，即请求的资源数要小于等于资源需求量，再判断系统是否有足够的盈余资源。如果都满足，就先试探性分配，试探性分配后检查系统是否还处于安全状态，如果为安全状态则分配成功，否则分配该资源将导致死锁，拒绝分配并将之前试探性分配的资源回收到系统中。

源代码

stdfax.h

#ifndef STDAFX_H_INCLUDE
#define STDAFX_H_INCLUDE

#include <iostream>

#define M 5                   //进程数量
#define N 3                   //资源种类
using namespace std;
#endif // !STDAFX_H_INCLUDE

bank.h

#ifndef BANK_H_INCLUDE
#define BANK_H_INCLUDE
#include "stdafx.h"


int available[N] = { 2,3,3 };                                        //当前系统可用的各种资源量
int allocation[M][N] = { {2,1,2},{4,0,2},{3,0,5},{2,0,4},{3,1,4} };    //各进程当前已分配到的各类资源
int need[M][N] = { {3,4,7},{1,3,4},{0,0,3},{2,2,1},{1,1,0} };        //各进程对资源的剩余需求量
int request[N] = { 0,0,0 };                                            //当前某进程请求的每种资源量，默认都为0

//比较两个数组的大小，如果a数组1的每一个元素都大于数组2的对应元素就返回false，否则返回true
bool previousIsBig(int* arr1, int* arr2)
{
    for (int i = 0;i < N;i++)
    {
        if (arr1[i] < arr2[i])
        {//有一个不符合就返回false
            return false;
        }
    }
    //否则返回true
    return true;
}

//只有三个元素的数组相加
int* addArr(int* arr1, int* arr2)
{
    int result[3];
    for (int i = 0;i < 3;i++)
    {
        result[i] = arr1[i] + arr2[i];
    }
    return result;
}

//安全状态判别算法
bool safeText()
{
    int i, j;
    bool flag=true;    
    //每个进程运行的状态，初始都为false
    bool finish[M];
    for (i = 0;i < M;i++)
    {
        finish[i] = false;
    }

    //将现有资源转移到work中
    int work[N];
    for (i=0;i < N;i++)
    {
        work[i] = available[i];
    }

    //一直循环查找未完成但是现在能够完成的进程
    while (flag)
    {
        flag = false;
        for (i = 0;i < M;i++)
        {
            if (finish[i] == false && previousIsBig(work, need[i]))
            {//标记为完成且释放掉占用的资源
                finish[i] = true;
                for (j = 0;j < N;j++)
                {//释放资源
                    work[j] += need[i][j];
                }
                flag = true;
            }
        }
    }

    //如果处理完后有一个进程未完成，说明是不安全的
    for (i = 0;i < M;i++)
    {
        if (finish[i] == false) return false;
    }

    //否则就是安全的
    return true;
 }

//试探性分配
void distribution(int pi, int* request)
{
    int i = 0;
    for (i;i < N;i++)
    {
        available[i] -= request[i];
        allocation[pi][i] += request[i];
        need[pi][i] -= request[i];
    }
}

//分配失败，取消试探性分配
void cancle(int pi, int* request)
{
    int i = 0;
    for (i;i < N;i++)
    {
        available[i] += request[i];
        allocation[pi][i] -= request[i];
        need[pi][i] += request[i];
    }
}


//银行家算法,第一个参数为进程编号，第二个为这个进程各项资源需要的数量
void bank(int pi, int* request)
{
    //先判断需求是否合理
    if (previousIsBig(request, need[pi]))
    {
        cout << "请求资源数不合理，请求失败!" << endl;
        return;
    }
    //先判断系统是否有足够的盈余资源
    if (!previousIsBig(available, request))
    {
        cout << "系统没有这么多资源，请求失败！" << endl;
        return;
    }
    //试探性分配
    distribution(pi, request);
    //判断是否安全,如果合法就分配
    if (safeText)
    {
        cout << "分配资源成功！" << endl;
        return;
    }

    else
    {//不合法撤回分配
        cancle(pi, request);;
        cout << "分配资源会导致死锁，分配失败！" << endl;
        return;
    }
}
#endif // !BANK_H_INCLUDE

main.cpp

#include "bank.h"

int main()
{
    //p2请求资源（0，3，4）
    int re[3] = { 0, 3,4 };
    cout << "p2请求资源:";
    bank(1, re);    

    //p4请求资源（1，0，1）
    re[0] = 1, re[1] = 0, re[2] = 1;
    cout << "p4请求资源:";
    bank(3, re);

    //p1请求资源（2，0，1）
    re[0] = 2, re[1] = 0, re[2] = 1;
    cout << "p1请求资源:";
    bank(0, re);

    //p3请求资源（0，0，2）
    re[0] = 0, re[1] = 0, re[2] = 2;
    cout << "p3请求资源:";
    bank(2, re);
    return 0;
}
文章作者: 陈细利
文章链接: https://firewolf321.github.io/2021/04/21/cao-zuo-xi-tong-yin-xing-jia-suan-fa/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 陈细利 !
C++ 操作系统
赏
评论
 上一篇
[操作系统]动态分区式存贮区管理 [操作系统]动态分区式存贮区管理
题目描述设计一个动态分区式存贮区管理程序，要求支持不同的放置策略。包括首次、最佳、最坏。 说明： (1) 分区描述器rd如下: flag size next 要求空闲区队列按链表组织。 主存大小假设为maxsize（单位为节=
2021-04-25 操作系统
C++ 操作系统
下一篇 
[操作系统]多级队列调度算法 [操作系统]多级队列调度算法
题目描述多级队列调度算法，设RQ分别为R1和RQ2，RQ1采用轮转法，时间片q=7。 RQ1>RQ2，RQ2采用短进程优先调度算法。 测试数据如下：RQ1：P1-P5，RQ2：P6-P10 进程 P1 P2 P3 P4 P5 P
2021-04-15 操作系统
C++ 操作系统
  目录