Linux实现银行家算法-FreeNAS中文网

admin 管理员组

文章数量: 887019

1 实验目的

熟练Linux系统编程操作
了解死锁避免的原理。
研究银行家算法的实现方法。

2 实验任务

最有代表性的避绝死锁的算法是迪杰斯特拉（Dijkstra）提出的银行家算法。该名字的由来是，该算法原本为银行系统而设计，以确保银行在发放现金货款时不会发生不能满足所有客户需要的情况。在操作系统（OS）中也可用它来避免死锁。

为实现银行家算法，每个新进程在进人系统时，其都必须申明在运行过程中可能需要每种资源类型的最大单元数目，该数目不应超过系统所拥有的资源总数。当进程清求一组资源时，系统须首先确定是否有足够的资源可分配给该进程。若有，则进一步计算在将这些资源分配给该进程后，系统是否会处于不安全状态。如果不会，则将资源分配给该进程，否则让该进程等待。

该实验要求编程实现银行家算法，具体要求如下：

模拟一个银行家算法：设置数据结构、安全性算法
初始化时让系统拥有一定的资源
用键盘输入的方式申请资源
如果预分配后，系统处于安全状态，则修改系统的资源分配情况
如果预分配后，系统处于不安全状态，则提示不能满足请求

3 思路分析

总体思路：先对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。

3.1 数据结构

为了实现银行家算法，必须在系统中设置 4 个数据结构，它们分別描述：系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配情况以及所有进程还需要多少资源：

可利用资源向量 Available：这是一个含有 m 个元素的数组，其中的每个元素代表一类可利用的资源数目，其初值是系统中所配置的该类全部可用资源的数目，该数目会随对应资源的分配和回收而动态改变。如果 Available[j]=K，则表示系统中现有 j 类资源 k 个。
最大需求矩阵 Max：这是一个 n × m n \times m n×m 的矩阵，它定义了系统中 n 个进程中的每个进程对 m 类资源的最大需求。如果 Max[i,j]=K，则表示进程 i 需要 j 类资源的最大数目为 K。
分配矩阵 Allocation：这是一个 n × m n \times m n×m 的矩阵，它定义了系统中每类资源当前己分配给每一进程的资源数。如果 Allocation[i,j]=K，则表示进程 i 当前已分得 j 类资源的数目为K。
需求矩阵 Need：这是一个 n × m n \times m n×m 的矩阵，用于表示每个进程尚需的各类资源数。如果 Need[i,j]=K，则表示进程 i 还需要 j 类资源 K 个方能完成其任务。

上述 3 个矩阵间存在下列关系：
N e e d [ i , j ] = M a x [ i , j ] − A l l o c a t i o n [ i , j ] Need[i,j]=Max[i,j]-Allocation[i,j] Need[i,j]=Max[i,j]−Allocation[i,j]

3.2 银行家算法

设 Request 是进程 P 的请求向量，如果 Request[j]=K，则表示进程 i 需要 K 个 j 类型的资源。当进程 i 发出资源请求后，系统会按下列步骤进行检查。

如果 Request[i]≤Need[i,j]，则转向步骤 2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
如果 Request[i]≤Available[i,j]，则转向步骤 3；否则表示尚无足够资源，进程 i 必须等待。
系统试探着把资源分配给进程 i，并修改下数据结构中的数值：
A v a i l a b l e [ i , j ] = A v a i l a b l e [ i , j ] − R e q u e s t [ i , j ] Available[i,j] = Available[i,j]-Request[i,j] Available[i,j]=Available[i,j]−Request[i,j]

A l l o c a t i o n [ i , j ] = A l l o c a t i o n [ i , j ] + R e q u e s t [ i , j ] Allocation[i,j] = Allocation[i,j]+Request[i,j] Allocation[i,j]=Allocation[i,j]+Request[i,j]

N e e d [ i , j ] = N e e d [ i , j ] − R e q u e s t [ i , j ] Need[i,j] = Need[i,j]-Request[i,j] Need[i,j]=Need[i,j]−Request[i,j]
系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若是，则正式将资源分配给进程 i，以完成本次分配；否则，将本的试探分配作废，恢复原来的资源分配状态，让进程 i 等待。

3.3 安全性算法

系统所执行的安全性算法可描述如下：

设置两个向量。第一，工作向量 Work：它表示系统可提供给进程继续运行所需的各类资源数目，它含有 m 个元素，在开始执行安全算法时，Work=Availabie。第二，完成向量 Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先令 Finish[i]=FALSE；当有足够的资源可分配给进程时，再令 Finish[i]=TRUE。
从进程集合中寻找一个能满足下述条件的进程：① Finish[i]=FALSE; ② Need[i,j]≤Work[j]。若能找到，则执行步骤 3；否则，执行步骤 4。
当进程 i 获得资源后，可顺利执行直至完成，并释放分配给它的资源，故应执行：
W o r k [ j ] = W o r k [ j ] + A l l o c a t i o n [ i , k ] Work[j]= Work[j]+Allocation[i,k] Work[j]=Work[j]+Allocation[i,k]

F i n i s h [ i ] = T R U E Finish[i]= TRUE Finish[i]=TRUE

g o t o s t e p 2 go \ to \ step \ 2 go to step 2
如果所有进程都满足 Finish[i]=TRUE，则表示系统处于安全状态；否则，系统处于不安全状态。

4 代码实现

4.1 头文件

首先，我们包含实现问题所需的头文件：

#include <stdio.h>
#include <stdlib.h>

4.2 预定义和数据结构

我们定义了预定义了最大进程个数 MAXN，系统最大资源个数 MAXM，以及思路分析中给出的 Available，Max，Allocation，Need 数组，以及实际进程数 N，系统资源数 M：

#define MAXN 100
#define MAXM 100
#define False 0
#define True 1

int N;
int M;
int Avaliable[MAXM];
int Max[MAXN][MAXM];
int Allocation[MAXN][MAXM];
int Need[MAXN][MAXM];

4.3 初始化函数

我们采取从控制台录入的方式读取 Max 和 Allocation 数组的值，并由此计算出 Need 和 Available 的值，具体实现如下：

void Initialize() 
{ 

    int i,j;

    printf("input process number: "); 
    scanf("%d",&N);

    printf("input system resource categories: ");
    scanf("%d",&M);
    for(i=0;i<M;i++)
    { 
        printf("input system resource %d number: ", i); 
        scanf("%d",&Avaliable[i]);
    }

    printf("input MAX matrix (%d * %d):\n",N,M); 
    for(i=0;i<N;i++)
    {
        for(j=0;j<M;j++)
        {
            scanf("%d",&Max[i][j]);
        }
    }

    int total[MAXM]={0};

    printf("input Allocation matrix (%d * %d):\n",N,M); 
    for(i=0;i<N;i++) 
    {
        for(j=0;j<M;j++)
        { 
            scanf("%d",&Allocation[i][j]);
            if(Allocation[i][j]>Max[i][j])
            {
                printf("bad allocation value!\n");
                exit(0);
            }
        }
    }

    for(i=0;i<N;i++)
    {
        for(j=0;j<M;j++)
        { 
            Need[i][j]=Max[i][j]-Allocation[i][j]; 
            Avaliable[j]-=Allocation[i][j];
        }
    }
    printf("\n");
}

4.4 展示数据

以表格的方式展示 Available，Max，Allocation，Need 矩阵的内容，实现代码如下：

void ShowData() 
{ 
    int i,j;
    printf("Describe:\n"); 

    printf("Avaliable: ");
    for (j=0;j<M;j++)
    {
        printf("%d ", Avaliable[j]);
    }
    printf("\n");

    printf("|Proc\t|Max\t|Alloc\t|Need\n"); 
    for(i=0;i<N;i++)
    { 
        printf("|%d\t|",i);

        for(j=0;j<M;j++)
        {
            printf("%d ",Max[i][j]);
        }

        printf("\t|"); 

        for(j=0;j<M;j++)
        {
            printf("%d ",Allocation[i][j]);
        }

        printf("\t|");
         
        for(j=0;j<M;j++)
        {
            printf("%d ",Need[i][j]);
        }

        printf("\n");
    } 
}

4.5 安全性算法

给定系统的某个状态（即：Available，Max，Allocation，Need 矩阵的内容），通过 3.3 的安全性算法检查当前的状态是否为安全状态：若是，则返回 True，同时输出安全序列 Security；若不是，则返回 False；
我们设置了一个函数 Condition() 用于检查工作向量 Work ，是否满足某个进程 i 的 Need 需求。
我们设置了一个函数 Release() 用于模拟进程执行完成后释放资源的情形。

具体实现代码如下：

int Condition(int Work[MAXM],int i)
{
    int j;
    for(j=0;j<M;j++)
    {
        if(Work[j]<Need[i][j]) return False;
    }
    return True;
}


void Release(int Work[MAXM],int i)
{
    int j;
    for(j=0;j<M;j++)
    {
        Work[j]+=Allocation[i][j];
    }
}


int Safe() 
{ 
    int i,j,k;
    int Security[MAXN];
    int Work[MAXM];   
    int Finish[MAXN];  

    printf("check system status...\n");

    for (i=0;i<N;i++)
    {
        Finish[i]=False;
    }

    for (j=0;j<M;j++) 
    {
        Work[j]=Avaliable[j];
    } 

    for(i=0,k=0;i<N;i++)
    {  
        if(Finish[i]==False)
        {      
            if(Condition(Work,i)==True)
            {
                Release(Work,i);
                Finish[i]=True;
                Security[k++]=i;
                if(k==N) break;
                i=-1;
            }
        }
    }

    for(i=0;i<N;i++)
    { 
        if(Finish[i]==False)
        { 
            printf("system is not safe!\n");
            return False; 
        } 
    } 
    printf("system is safe!\n");
    printf("safe sequence: "); 
    for(i=0;i<N;i++)
    {
        printf("%d",Security[i]); 
        if(i<N-1) printf("->"); 
    } 
    printf("\n"); 
    return True; 
}

4.6 银行家算法

给定进程 i 的请求向量 Request 我们按照 3.2 中的思路编写银行家算法，并在处理完请求后调用 4.4 中 ShowData() 函数展示数据，具体实现如下：

void Bank() 
{ 
    int i,j,k; 
    int Request[MAXM];

    printf("input process id to request resource (0-%d): ",N-1); 
    scanf("%d",&i);
    printf("input Request number (vector): ");
    for(j=0;j<M;j++)
    { 
        scanf("%d",&Request[j]);
    }

    for (j=0;j<M;j++)
    { 
        if(Request[j]>Need[i][j])
        {  
            printf("bad request number (request number beyond Need)\n");
            ShowData();
            return;
        }
        if(Request[j]>Avaliable[j])
        { 
            printf("bad request number (request number beyond Avaliable), process waiting\n");
            ShowData();
            return;
        }
    } 

    printf("try to allocate resources...\n");
    for(j=0;j<M;j++) 
    {
        Avaliable[j]-=Request[j];
        Allocation[i][j]+=Request[j];
        Need[i][j]-=Request[j]; 
    }
    
    if(Safe()==False)
    { 
        for (j=0;j<M;j++) 
        { 
            Avaliable[j]+=Request[j]; 
            Allocation[i][j]-=Request[j]; 
            Need[i][j]+=Request[j];
        } 
        printf("request refused!\n");
    }

    ShowData();
}

4.7 主函数

首先我们调用 Initialize() 函数初始化各个矩阵的值，之后运行安全性算法检查当前状态是否安全；进一步输入进程的请求向量调用 Bank()，检查请求的合法性。直到用户输入 n，程序结束，具体代码如下：

int main()
{
    char ch='y';
    Initialize();
    ShowData();
    Safe();
    while(1)
    {
        if(ch=='y') Bank();
        else if(ch=='n') break;
        else printf("bad choice!\n");
        printf("continue to request resources (y/n)? ");
        getchar();
        ch = getchar();
    }
}

4.8 实验代码

完整实验代码如下：

#include <stdio.h>
#include <stdlib.h>
#define MAXN 100
#define MAXM 100
#define False 0
#define True 1

int N;
int M;
int Avaliable[MAXM];
int Max[MAXN][MAXM];
int Allocation[MAXN][MAXM];
int Need[MAXN][MAXM]; 


void Initialize() 
{ 

    int i,j;

    printf("input process number: "); 
    scanf("%d",&N);

    printf("input system resource categories: ");
    scanf("%d",&M);
    for(i=0;i<M;i++)
    { 
        printf("input system resource %d number: ", i); 
        scanf("%d",&Avaliable[i]);
    }

    printf("input MAX matrix (%d * %d):\n",N,M); 
    for(i=0;i<N;i++)
    {
        for(j=0;j<M;j++)
        {
            scanf("%d",&Max[i][j]);
        }
    }

    int total[MAXM]={0};

    printf("input Allocation matrix (%d * %d):\n",N,M); 
    for(i=0;i<N;i++) 
    {
        for(j=0;j<M;j++)
        { 
            scanf("%d",&Allocation[i][j]);
            if(Allocation[i][j]>Max[i][j])
            {
                printf("bad allocation value!\n");
                exit(0);
            }
        }
    }

    for(i=0;i<N;i++)
    {
        for(j=0;j<M;j++)
        { 
            Need[i][j]=Max[i][j]-Allocation[i][j]; 
            Avaliable[j]-=Allocation[i][j];
        }
    }
    printf("\n");
}


void ShowData() 
{ 
    int i,j;
    printf("Describe:\n"); 

    printf("Avaliable: ");
    for (j=0;j<M;j++)
    {
        printf("%d ", Avaliable[j]);
    }
    printf("\n");

    printf("|Proc\t|Max\t|Alloc\t|Need\n"); 
    for(i=0;i<N;i++)
    { 
        printf("|%d\t|",i);

        for(j=0;j<M;j++)
        {
            printf("%d ",Max[i][j]);
        }

        printf("\t|"); 

        for(j=0;j<M;j++)
        {
            printf("%d ",Allocation[i][j]);
        }

        printf("\t|");
         
        for(j=0;j<M;j++)
        {
            printf("%d ",Need[i][j]);
        }

        printf("\n");
    } 
}


int Condition(int Work[MAXM],int i)
{
    int j;
    for(j=0;j<M;j++)
    {
        if(Work[j]<Need[i][j]) return False;
    }
    return True;
}


void Release(int Work[MAXM],int i)
{
    int j;
    for(j=0;j<M;j++)
    {
        Work[j]+=Allocation[i][j];
    }
}


int Safe() 
{ 
    int i,j,k;
    int Security[MAXN];
    int Work[MAXM];   
    int Finish[MAXN];  

    printf("check system status...\n");

    for (i=0;i<N;i++)
    {
        Finish[i]=False;
    }

    for (j=0;j<M;j++) 
    {
        Work[j]=Avaliable[j];
    } 

    for(i=0,k=0;i<N;i++)
    {  
        if(Finish[i]==False)
        {      
            if(Condition(Work,i)==True)
            {
                Release(Work,i);
                Finish[i]=True;
                Security[k++]=i;
                if(k==N) break;
                i=-1;
            }
        }
    }

    for(i=0;i<N;i++)
    { 
        if(Finish[i]==False)
        { 
            printf("system is not safe!\n");
            return False; 
        } 
    } 
    printf("system is safe!\n");
    printf("safe sequence: "); 
    for(i=0;i<N;i++)
    {
        printf("%d",Security[i]); 
        if(i<N-1) printf("->"); 
    } 
    printf("\n"); 
    return True; 
} 


void Bank() 
{ 
    int i,j,k; 
    int Request[MAXM];

    printf("input process id to request resource (0-%d): ",N-1); 
    scanf("%d",&i);
    printf("input Request number (vector): ");
    for(j=0;j<M;j++)
    { 
        scanf("%d",&Request[j]);
    }

    for (j=0;j<M;j++)
    { 
        if(Request[j]>Need[i][j])
        {  
            printf("bad request number (request number beyond Need)\n");
            ShowData();
            return;
        }
        if(Request[j]>Avaliable[j])
        { 
            printf("bad request number (request number beyond Avaliable), process waiting\n");
            ShowData();
            return;
        }
    } 

    printf("try to allocate resources...\n");
    for(j=0;j<M;j++) 
    {
        Avaliable[j]-=Request[j];
        Allocation[i][j]+=Request[j];
        Need[i][j]-=Request[j]; 
    }
    
    if(Safe()==False)
    { 
        for (j=0;j<M;j++) 
        { 
            Avaliable[j]+=Request[j]; 
            Allocation[i][j]-=Request[j]; 
            Need[i][j]+=Request[j];
        } 
        printf("request refused!\n");
    }

    ShowData();
}


int main()
{
    char ch='y';
    Initialize();
    ShowData();
    Safe();
    while(1)
    {
        if(ch=='y') Bank();
        else if(ch=='n') break;
        else printf("bad choice!\n");
        printf("continue to request resources (y/n)? ");
        getchar();
        ch = getchar();
    }
}

5 实验结果

我们通过gcc编译器编译源程序bank.c，生成目标文件bank

我们从控制台输入命令$ ./bank运行程序，录入矩阵的初始值：

程序自动运行安全性算法，得到结果如下：

系统检查为安全，安全序列为 1->3->0->2->4。

之后我们录入一组数据模拟 1 号进程的请求，得到结果：

系统仍为安全的，安全序列为 1->3->0->2->4，并且已经为 1 号进程分配了相应的资源。

我们再录入一组数据模拟 4 号进程请求资源，得到结果：

由于 4 号进程的请求资源超过了系统的可利用资源，故进程需要等待。

我们再录入一组数据模拟 0 号进程请求资源，得到结果：

由于给 0 号进程分配资源后系统状态不安全，故系统拒绝了请求。

最后我们输入 n 退出了程序，程序测试通过。

本文标签：银行家算法 Linux

版权声明：本文标题：Linux实现银行家算法内容由网友自发贡献，该文观点仅代表作者本人，转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1727377020h1110976.html，本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。

技术交流 – FreeNAS中文网

Linux实现银行家算法

1 实验目的

2 实验任务

3 思路分析

3.1 数据结构

3.2 银行家算法

3.3 安全性算法

4 代码实现

4.1 头文件

4.2 预定义和数据结构

4.3 初始化函数

4.4 展示数据

4.5 安全性算法

4.6 银行家算法

4.7 主函数

4.8 实验代码

5 实验结果

更多相关文章

windows 10 安装 linux子系统

linux puppy 设置中文_Linux常见发行版本优缺点对比

如何把linux上的文件拷贝到windows下--SecureCRT篇

[ Linux 命令基础 4 ] Linux 命令详解-文本处理命令

linux使用cifs方式mount（挂载）Windows7共享文件

Linux系统ISO镜像文件下载地址

linux制作U盘启动盘无法使用,完美:使用syslinux制作U盘启动盘

【Linux】Linux的常用命令、Vi和Vim编辑器

Linux和Windows配置ssh免密码登录

windows下oracle重启,linux &amp; windows下重启oracle

Windows系统下Linux子系统cuda、pytorch及tensorrt环境搭建与VScode连接

下载VirtualBox，创建虚拟机，安装Linux系统(Ubuntu版)

Windows Subsystem for Linux (WSL, Ubuntu) 最新安装教程（2024.11 更新）

Windows 7能够战胜Linux吗？

（亲测）制作linux启动U盘

通过 WSL在Windows下愉快的玩耍Linux

windows和linux共用efi分区,技术|使用 UEFI 双启动 Windows 和 Linux

win7下卸载linux系统（不用windows光盘）

windows上传文件到Linux（centos7）上

Windows下生成ssh密钥，并用ssh免密访问Linux服务器

发表评论

推荐文章

改HUME的SHELLCODE模版程序

Windows：cpu路+核+线程+主频+缓存、Windows桌面图标变白、电脑系统、机械键盘、Typora空白过大

Redis安装教程（Windows版）

ThinkPad随机Windows 7恢复光盘恢复系统的方法

Windows 7突然断电默认进入修复模式解决方法

热门文章

ThinkPad T480升级改造实战：从屏幕到硬盘的全面升级指南

夜神模拟器：新建android模拟器并安装apk文件

layui数据表格实现点击数据行变色效果，从而保存浏览历史

英文句子逆序

Windows Server 2022 简体中文版、英文版下载 (updated Jun 2022)

电脑变WIFI:建立虚拟共享WIFI热点可查看WIFI密码windows中使用bat批处理命令提示符cmd创建教程含工具

Windows和linux谁更流畅,Linux、Windows，谁速度更快

配置windows下域名解析及修改hosts文件不起作用的问题

微星主板黑苹果_组装电脑哪个主板好？如何选择电脑主板？2020年电脑主板推荐及分析。...

FreeCAD是什么、如何下载（windows+0.18.4版本）和安装以及中文设置

最新文章

Raid技术

LSI_阵列卡操作手册

破解Centos7_root用户密码

Redhat重置Root用户密码方法

远程批量修改linux服务器密码的脚本

最新Windows 11教育版下载：专为教育设计的系统！

Win7系统下搭建NFS服务器

零基础使用UltraISO制作并安装纯净Win10系统指南

苹果电脑windows系统换苹果系统

Win11系统崩溃错误修复指南：三种实用方法详解

windows下oracle重启,linux & windows下重启oracle