在C语言中使用银行家算法预防死锁

C语言中使用银行家算法预防死锁

什么是死锁

死锁是指在一个并发系统中,两个或以上的线程互相等待对方的资源而无限制地等待下去,使得进程无法继续运行而陷入一种“死循环”,形成死锁。

银行家算法

银行家算法是一种避免死锁的算法。它通过动态地分配资源,避免进程因竞争资源而发生死锁,并保证分配的资源不会导致系统不安全。

银行家算法的实现需要考虑以下信息:

  • Available:当前可用的资源数目。
  • Max:系统中每种资源的最大需求量。
  • Allocation:系统中每种资源当前已分配的数量。
  • Need:系统中每种资源还需要的数量。

死锁避免的步骤

使用银行家算法避免死锁可以分为以下步骤:

  1. 初始化资源可用数量 Available,系统的所有进程以及它们的资源需求量 Max 和已分配资源数量 Allocation。
  2. 检查系统是否处于安全状态,也就是系统是否有足够的资源满足后续进程的请求。如果是,则接受请求并更新资源分配情况;否则,拒绝请求,等待其他进程释放资源。
  3. 继续进行死锁预防工作。每当分配或释放资源时,都要重新计算实际可用资源和各个进程还需要的资源数量,并尝试将之前因拒绝请求而被阻塞的进程重新考虑分配资源。

示例1:使用银行家算法避免死锁

假设系统中有5个进程,申请资源的顺序为 P1、P2、P3、P4、P5。分别显示它们对三类资源的最大需求量 Max 和已分配资源数量 Allocation 如下表所示。

进程 Allocation Max Need
P1 1 1 0 2 1 1 1 0 1 (Max-Allo)
P2 1 0 1 2 1 2 1 1 1
P3 1 0 0 1 2 0 0 2 0
P4 0 0 1 3 0 0 3 0 2
P5 0 0 1 2 0 1 2 0 0

此时可用资源数量 Available 为 1 2 0。

假设现在进程 P4 申请 1 0 0 资源,判断如下:

  1. 检查系统是否处于安全状态,此时 Available 与 Need 比较结果如下:
进程 Need Available Work Finish
P1 1 0 1 0 2 0 0 0 0 No
P2 1 1 0
P3 0 2 0
P4 3 0 2
P5 2 0 0

则 P2 或 P3 可以被分配资源,我们选择 P2,分配资源后,状态如下:

进程 Allocation Need Available Work Finish
P1 1 0 1 1 0 0 0 1 0 1 0 0 No
P2 1 1 1 1 0 1 1 1 0 0 1 0 Yes
P3 1 0 0 0 2 0 1 2 1 0 0 0 No
P4 0 0 1 3 0 1 1 2 1 0 0 1 No
P5 0 0 1 2 0 0 1 2 2 0 0 0 No
  1. P4 的申请可以被满足,并更新 Allocation 和 Available 信息,状态如下:
进程 Allocation Max Need
P1 1 0 1 2 1 1 1 1 0
P2 1 1 1 2 1 2 1 0 1
P3 1 0 0 1 2 0 0 2 0
P4 0 0 2 3 0 0 3 0 0
P5 0 0 1 2 0 1 2 0 0
1 1 4 10 5 8 5 3 9 (Max-Allo)
  1. 继续进行死锁预防工作,更新各个进程需要的资源数量,状态如下:
进程 Allocation Max Need
P1 1 0 1 2 1 1 1 1 0
P2 1 1 1 2 1 2 1 0 1
P3 1 0 0 1 2 0 0 2 0
P4 0 0 2 3 0 0 3 0 0
P5 0 0 1 2 0 1 2 0 0

示例2:配合源代码使用银行家算法避免死锁

下面是一个基于 C 语言的简单死锁避免示例代码,使用了银行家算法的思想。它让两个线程按不同的顺序执行,增加了产生死锁的概率,验证了死锁验证的正确性。

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

int available[10],max[10][10],allocation[10][10],need[10][10],flag[10],work[10];
int num_process,num_res;

int input_data() {
    int i,j;
    printf("Enter the number of processes: ");
    scanf("%d",&num_process);
    printf("Enter the number of types of resources: ");
    scanf("%d",&num_res);
    for(i=1;i<=num_process;i++){
        printf("Enter the allocation of process %d: ",i);
        for(j=1;j<=num_res;j++){
            scanf("%d",&allocation[i][j]);
        }
        flag[i]=0;
    }
    printf("\n");
    for(i=1;i<=num_process;i++){
        printf("\nEnter the Max Matrix for process %d : ",i);
        for(j=1;j<=num_res;j++){
            scanf("%d",&max[i][j]);
        }
    }
    printf("\n");
    printf("\nEnter the Available Resources : ");
    for(i=1;i<=num_res;i++){
        scanf("%d",&available[i]);
        work[i]=available[i];
    }
    printf("\n");
    return 0;
}

void calculate_need(){
    int i,j;
    for(i=1;i<=num_process;i++){
        for(j=1;j<=num_res;j++){
            need[i][j]=max[i][j]-allocation[i][j];
        }
    }
}

int check_availability(int j){
    int i;
    for(i=1;i<=num_res;i++){
        if (need[j][i]>work[i]){
            return 0;
        }
    }
    return 1;
}

int wait_or_exit(){
    int i,j,found,flag;
    for(i=1;i<=num_process;i++){
        if(flag[i]==0 && check_availability(i)){
            flag[i]=1;
            for(j=1;j<=num_res;j++){
                work[j]=work[j]+allocation[i][j];
            }
            break;
        }
    }
    if(i>num_process){
        return 0;
    }
    else{
        return 1;
    }
}

void detect_deadlock(){
    int i,j,found,flag;
    calculate_need();
    int process_allocated = 0;
    while(process_allocated<num_process){
        found = 0;
        for(i=1;i<=num_process;i++){
            if(flag[i]==0 && check_availability(i)){
                flag[i]=1;
                found = 1;
                printf("\nProcess %d is allocated resources ",i);
                for(j=1;j<=num_res;j++){
                    work[j]=work[j]+allocation[i][j];
                }
                process_allocated++;
            }
        }
        if(found==0){
            printf("\nSystem is not in safe state\n");
            return;
        }
    }
    printf("\nSystem is in safe state\n");
}

int main(){
    input_data();
    detect_deadlock();
    return 0;
}

这个代码输入了最大需求量、当前已分配数量和可用资源数量。它先计算出需要的资源数量,然后检查系统是否处于安全状态。如果不是,就需要等待其他资源释放。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:在C语言中使用银行家算法预防死锁 - Python技术站

(0)
上一篇 2023年5月9日
下一篇 2023年5月9日

相关文章

  • C++如何判断一个数是不是素数

    当然,作为一个网站的作者,我很乐意为你提供详细的攻略。 在C++中判断一个数是否是素数,通常有两种方法:暴力枚举和筛法。 暴力枚举 暴力枚举是一种较为简单的方法,即对于一个数n,将n分别除以2,3,4,…,n-1,判断它是否能除尽这些数。若一旦出现n%i==0,则说明n不是素数。 暴力枚举的代码实现如下: bool isPrime(int n) { if…

    C 2023年5月23日
    00
  • C语言实现输入两个数字将其按从小到大输出的方法

    以下是C语言实现输入两个数字将其按从小到大输出的方法的攻略: 步骤一:设置两个变量,输入两个数字 例如: #include <stdio.h> int main() { int a, b; printf("请输入两个整数: "); scanf("%d %d", &a, &b); return…

    C 2023年5月23日
    00
  • Dev C++ 安装及使用方法(图文教程)

    下面是Dev C++安装及使用方法的完整攻略,主要分为以下几个步骤: 步骤一:下载安装包 访问Dev C++官网(https://www.bloodshed.net/devcpp.html),点击最新版本的下载链接,下载适合自己电脑的安装包。 步骤二:安装Dev C++ 使用管理员权限打开下载的安装包,按照安装向导提示完成安装。 步骤三:使用Dev C++ …

    C 2023年5月23日
    00
  • Python模块介绍与使用详细讲解

    Python模块介绍与使用详细讲解 在Python中,一个模块就是一个包含Python定义和声明的文件。模块通常包括各种函数、变量和类的定义,使用模块能够使你的代码更加模块化,易于维护。 模块的导入 在Python中,使用关键字import声明已经存在的模块,可以让你在程序中使用一个特定的模块。有三种不同的方式可以从模块中导入内容: 1. 直接导入模块 使用…

    C 2023年5月22日
    00
  • C语言三个函数的模拟实现详解

    C语言三个函数的模拟实现详解 一、题目背景 C语言是一种重要的编程语言,其语法严谨,灵活性高,被广泛应用于软件开发、嵌入式系统等领域。在学习C语言的过程中,掌握其常用函数的原理及实现方式是非常有必要的。本篇攻略主要讲解了C语言中三个常用函数的模拟实现方法。 二、题目概述 在C语言中,有三个常用函数,分别是strlen函数、strcpy函数和strcat函数。…

    C 2023年5月23日
    00
  • C语言实现的猜拳游戏代码分享

    C语言实现的猜拳游戏代码分享 1. 概述 本文将介绍C语言实现的猜拳游戏的代码分享,该游戏采用了简单的命令行交互界面,玩家与计算机进行猜拳游戏。 2. 猜拳游戏规则 猜拳游戏的规则非常简单,玩家和计算机各出一招,谁胜利就由出招的手势确定。具体规则如下: 石头胜剪刀 剪刀胜布 布胜石头 3. 代码实现 下面是C语言实现的猜拳游戏的代码: #include &l…

    C 2023年5月24日
    00
  • C++实现宿舍管理查询系统

    C++实现宿舍管理查询系统攻略 1. 系统介绍 C++实现宿舍管理查询系统是一款基于控制台界面的宿舍管理查询应用。该系统主要用于方便宿舍管理员进行学生入住管理和住宿情况查询。系统功能包括:学生信息录入、住宿信息录入、学生信息查询、住宿信息查询、学生信息删除等。 2. 开发环境 操作系统:Windows 10 编程语言:C++ 集成开发环境:Visual St…

    C 2023年5月23日
    00
  • C 语言基础教程(我的C之旅开始了)[十]

    下面是“C 语言基础教程(我的C之旅开始了)[十]”的完整攻略,主要包含以下几个部分: 标题 文章的标题应该简明、准确地反映文章的主题。在本篇文章中,标题为“C 语言基础教程(我的C之旅开始了)[十]”,可知该文章是系统讲解 C 语言基础知识的系列文章的第十篇。 章节 要做到篇章设计清晰,特别是对于长篇文章来说,应该对其进行章节划分。在本篇文章中,可以根据文…

    C 2023年5月23日
    00
合作推广
合作推广
分享本页
返回顶部