C语言实现的操作系统银行家算法

简介: C语言实现的操作系统银行家算法

一、银行家算法

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

  在银行中,客户申请贷款的数量是有限的,每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量,在满足所有贷款要求时,客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时,都应尽量满足客户的需要。在这样的描述中,银行家就好比操作系统,资金就是资源,客户就相当于要申请资源的进程。

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

二、方案分析

模拟实现银行家算法对系统资源进行分配,以防止死锁的出现。本课题肯定不可能实现对实际操作系统的资源管理,而是通过对模拟资源数据的处理,检测银行家算法在防止死锁出现的作用。先对用户提出的请求进行合法性检查,即检查请求的是不大于需要的,是否不大于可利用的。若请求合法,则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全,则分配,否则,不分配,恢复原来状态,拒绝申请。

三、开发环境

  • Windows操作系统
  • VS 2017
  • C语言

四、设计思想及实验步骤

4.1 设计思想

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

4.2 银行家算法中的数据结构

可利用资源向量Available。这是一个含有m个元素的数组,其中的每一个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类资源的分配和回收而动态改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。

最大需求矩阵Max。这是一个 的矩阵,它定义了系统中 个进程中的每一个进程对 类资源的最大需求。如果Max[I,j]=K,则进程i需要Rj类资源的最大数目为K。

分配矩阵Allocation。这也是一个 的矩阵,它定义了系统中每一类资源当前已分配给每一个进程的资源数。如果Allocation[i,j]=K,则表示进程i当前已经分得Rj类资源的数目为K。

需求矩阵Need。这也是一个 的矩阵,用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要Rj类资源K个,方能完成任务。

即:

int M ; // 总进程数
int N ; // 资源种类
int ALL_RESOURCE[W];  // 各种资源的数目总和
int Max[W][R];      // 最大需求矩阵,M个进程对N类资源最大资源需求
int Available[R];   // 可利用资源向量,
int Allocation[W][R];// 分配矩阵,各个进程M已经得到N类资源的资源数
int Need[W][R];     // M个进程还需要N类资源的资源量
int Request[R];     // 进程的请求资源个数

以上三个矩阵间存在下述关系:

Need[i,j] = Max[i,j] - allocation[i, j]

4.3 银行家算法bank()

设Request i是进程Pi的请求向量,如果Requesti[j]=K,表示进程Pi需要K个Rj类型的资源。发出请求后,系统按下述步骤进行检查:

  • (1)检查申请量是否不大于需求量。如果Request i[j]<=Need[i,j],便转向步骤(2);否则认为出错,因为他所需要的资源数已经超过它所宣布的最大值。
  • (2)检查申请量是否小于系统中的可利用资源数量。如果Requesti[j]<=Available[i,j],便转向步骤(3);否则认为尚无足够资源,Pi必须等待。
  • (3)若以上两个条件都满足,则系统试探着将资源分配给申请的进程,并修改下面数据结构中的数值:
Available[j]=Available[j]-Request[j];
Allocation[k][j]=Allocation[k][j]+Request[j];
Need[k][j]=Need[k][j]-Request[j];
  • (4)试分配后,系统执行安全性算法,调用safe()函数检查此次资源分配后系统是否处于安全状态。若安全,才正式将资源分配给进程,以完成本次分配,并将安全序列打印出来;否则本次试探分配作废,恢复原来的资源分配状态,让该进程等待。

4.4 安全性算法safe()

(1)设置两个向量

  • 工作向量:
  • Work,它表示系统可提供给进程继续运行所需要的各类资源数目,它含有m个元素,在执行安全性算法开始时,Work: =Available
  • Finish,它表示系统是否有足够资源分配给进程,使之运行完成。开始时先做Finish[i]:=false;当有足够的资源分配给进程时,再令Finish[i]:=true

(2)从进程集合中找到一个满足下述条件的进程

  • Finish[i]:=false;
  • Need[i,j]<=Work[j];若找到,执行步骤(3),否则,执行步骤(4)

(3)当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行

Work[j] = Work[j] + Allocation[i,j];
Finish[i] = true;
go to step 2;

(4)如果所有的进程Finish= true都满足,则表示系统处于安全状态;否则系统处于不安全状态

五、程序的基本结构框图和流程图

5.1 程序结构功能图

5.2 流程图

六、源代码

#include<stdio.h>
// 预处理
#define FALSE 0
#define TRUE 1
#define W 10
#define R 10
int safe_queue[10];
static int cnt = 0;
int M;  // 进程数
int N;  // 资源种类数
int all_resource[W];  // 各种资源数目
int max[W][R];      // 最大需求矩阵,M个进程对N类资源最大资源需求
int available[R];   // 可利用资源数
int allocation[W][R]; // 已分配矩阵,各个进程M得到N类资源的资源数
int need[W][R];     // M个进程还需要N类资源的数目
int request[R];     // 进程请求的资源个数
void display();     // 项目信息
void show();      // 显示当前各进程的分配和需求信息
void fenpei(int k);   // 分配资源
void huishou(int k);  // 上一个进程结束释放所得资源后,系统重新获得的可利用资源huishou
bool safe();      // 安全性算法
void bank();      // 银行家算法
int main()
{
  int i = 0, j = 0, p;
  display();
  printf("------------------------------------------------\n\n");
  // 信息输入
  printf("请输入进程数:");
  scanf("%d", &M);
  printf("请输入资源种类:");
  scanf("%d", &N);
  printf("请输入%d个各类资源总数:", N);
  for (i = 0; i < N; i++)
  {
    scanf("%d", &all_resource[i]);
  }
  printf("请输入%d个各进程所需要的各类资源的最大数量(M*N矩阵输入):\n", M*N);
  for (i = 0; i < M; i++) {
    for (j = 0; j < N; j++) {
      do {
        scanf("%d", &max[i][j]);
        if (max[i][j] > all_resource[j])
          printf("占有资源超过了声明的该资源总数,请重新输入\n");
      } while (max[i][j] > all_resource[j]);
    }
  }
  printf("请输入%d个各进程已经分配的各类资源的数量:\n", M*N);  //各进程已经分配的各类资源的数量
  for (i = 0; i < M; i++) {
    for (j = 0; j < N; j++) {
      do {
        scanf("%d", &allocation[i][j]);
        if (allocation[i][j] > max[i][j])
          printf("已分配的资源超过了声明的最大资源,请重新输入\n");
      } while (allocation[i][j] > max[i][j]);
    }
  }
  // 需要资源的数目=最大-已分配
  for (i = 0; i < M; i++)
    for (j = 0; j < N; j++)
      need[i][j] = max[i][j] - allocation[i][j];
  // 可利用资源数=总的-所有进程用的
  for (j = 0; j < N; j++) {
    p = all_resource[j];
    for (i = 0; i < M; i++) {
      p = p - allocation[i][j]; // 减去已经被占据的资源
      available[j] = p;
      if (available[j] < 0)
        available[j] = 0;
    }
  }
  show();   // 显示当前各进程的分配和需求信息
  bank();   // 调用银行家算法进行计算
  return 0;
}
// 打印项目信息
void display()
{
  printf("\n\n\n      ------------------------------------------\n");
  printf("      |                                         | \n");
  printf("      |        题目:银行家算法实现             | \n");
  printf("      |                                         | \n");
  printf("      -------------------------------------------\n");
}
// 显示当前各进程的分配和需求信息
void show()
{
  int i, j;
  printf("\n-----------------------------------------------------------------\n");
  printf("各种资源的总数量:\n"); //各种资源的总数量
  for (j = 0; j < N; j++)
  {
    printf(" %d", all_resource[j]);
  }
  printf("\n-----------------------------------------------------------------\n");
  printf("目前各种资源可利用的数量为:\n");//各种资源的总数量减去已分配后剩余的资源量  
  for (j = 0; j < N; j++)
  {
    printf(" %d", available[j]);
  }
  printf("\n-----------------------------------------------------------------\n");
  printf("各进程还需要的资源数量:\n"); //各进程还需要的资源数量
  for (i = 0; i < N; i++)
  {
    printf("    资源%d", i);
  }
  printf("\n");
  for (i = 0; i < M; i++) {
    printf("进程%d    ", i);
    for (j = 0; j < N; j++)
      printf("%d        ", need[i][j]);
    printf("\n");
  }
  printf("\n");
  printf("-----------------------------------------------------------------\n");
  printf("各进程已经得到的资源量: \n");//打印各进程已经得到的资源量 
  for (i = 0; i < N; i++)
  {
    printf("        资源%d", i);
  }
  printf("\n");
  for (i = 0; i < M; i++)
  {
    printf("进程%d    ", i);
    for (j = 0; j < N; j++)
    {
      printf("%d         ", allocation[i][j]);
    }
    printf("\n");
  }
  printf("\n");
}
// 分配资源
void fenpei(int k)
{
  int j;
  // 系统试探着把资源分配给进程Pi,并修改下面的数据结构fenpei
  for (j = 0; j < N; j++) 
  {
    available[j] = available[j] - request[j];
    allocation[k][j] = allocation[k][j] + request[j];
    need[k][j] = need[k][j] - request[j];
  }
}
// 上一个进程结束释放所得资源后,系统重新获得的可利用资源
void huishou(int k)
{
  int j;
  for (j = 0; j < N; j++) 
  {
    available[j] = available[j] + request[j];
    allocation[k][j] = allocation[k][j] - request[j];
    need[k][j] = need[k][j] + request[j];
  }
}
/*
安全性算法,设置两个向量Work和Finish.
  Work:表示系统可提供给进程继续运行所需的各类资源数目;
  Finish:表示系统是否有足够的资源分配给进程。
*/
bool safe()
{
  int Work[R], Finish[W];     // 设置两个向量Work和Finish.
  int i, j, m;
  for (j = 0; j < N; j++)
    Work[j] = available[j];   // 在执行安全算法之前,初始化
  for (i = 0; i < M; i++)
    Finish[i] = FALSE;      // 系统初始化,将各进程的初始完成状态设置为FALSE
  for (i = 0; i < M; i++)   // M进程
  {
    for (j = 0; j < N; j++) // j类资源
    {
      for (m = 0; m < M; m++) // 对M线程都对应查M次
      {
        // 如果m进程还未完成 且 所需小于系统可用的,那么试分配资源
        if (Finish[m] == FALSE && need[m][j] <= Work[j])
        {
          Work[j] = Work[j] + allocation[m][j]; // 该进程完成后,系统可用的变为原来的加上该进程已分配的
          Finish[m] = TRUE;           // 当有足够的资源分配给进程时,设置为TRUE
          safe_queue[cnt] = m;          // 记录安全进程序列
          cnt++;
        }
      }
    }
  }
  // 判断系统安全性
  for (i = 0; i < M; i++)
  {
    if (Finish[i] == FALSE)
    {
      printf("\n经安全性算法检查,此时系统处于不安全状态! 本次分配不成功!!!\n\n");
      return 1;
    }
    else
    {
      printf("\n经安全性算法检查,此时系统安全,分配成功。\n");
      printf("此时系统的安全序列是:\n");
      for (i = 1; i < cnt; i++) {
        printf("%d  ", safe_queue[i]);  // 打印安全序列
      }
      printf("\n");
      return 0;
    }
  }
  return 1;
}
// 银行家算法进行计算
void bank()
{
  int i = 0, j = 0;
  char flag = 'Y';
  while (flag == 'Y' || flag == 'y') {
    i = -1;
    while (i < 0 || i >= M) {
      printf("-----------------------------------------------------------------\n");
      printf("请输入申请资源的进程号:\n"); //进程Pi发出请求
      scanf("%d", &i);
      if (i < 0 || i >= M)
        printf("对不起,输入的进程号不存在,请重新输入!\n");
    }
    printf(" 请输入进程%d申请各类资源的数量:\n", i);
    for (j = 0; j < N; j++) {
      printf("资源%d: ", j);
      scanf("%d", &request[j]);
      // 若请求的资源数大于进程还需要i类资源的资源量j
      if (request[j] > need[i][j]) 
      {
        printf("进程%d申请的资源数大于进程%d还需要%d类资源的数量!\n", i, i, j);
        printf("若继续执行系统将处于不安全状态!\n");
        flag = 'N';
        break;
      }
      else 
      {
        // 若请求的资源数大于可用资源数
        if (request[j] > available[j])
        {
          printf(" 进程%d申请的资源数大于系统可用%d类资源的数量!\n", i, j);
          printf(" 若继续执行系统将处于不安全状态!\n");
          flag = 'N';
          break;
        }
      }
    }
    if (flag == 'Y' || flag == 'y') 
    {
      fenpei(i);  // 调用fenpei(i)函数,改变资源数
      safe_queue[cnt] = i;
      cnt++;
      // 若系统安全
      if (safe()) 
      {
        huishou(i); // 调用huishou(i)函数,恢复资源数
        show();   // 输出资源分配情况
      }
      else      // 若系统不安全,输出资源分配情况
        show();
    }
    else      //执行flag=N||flag=n
      printf("\n");
    printf(" 是否继续银行家算法演示?按'Y'或'y'继续,按'N'或'n'退出演示: \n");
    getchar();
    flag = getchar();
  }
}


相关文章
|
1月前
|
算法 调度 UED
探索操作系统的心脏:调度算法的奥秘与影响
【10月更文挑战第9天】 本文深入探讨了操作系统中至关重要的组件——调度算法,它如同人体的心脏,维持着系统资源的有序流动和任务的高效执行。我们将揭开调度算法的神秘面纱,从基本概念到实际应用,全面剖析其在操作系统中的核心地位,以及如何通过优化调度算法来提升系统性能。
|
9天前
|
搜索推荐 C语言
【排序算法】快速排序升级版--三路快排详解 + 实现(c语言)
本文介绍了快速排序的升级版——三路快排。传统快速排序在处理大量相同元素时效率较低,而三路快排通过将数组分为三部分(小于、等于、大于基准值)来优化这一问题。文章详细讲解了三路快排的实现步骤,并提供了完整的代码示例。
32 4
|
20天前
|
存储 算法 数据管理
C语言算法复杂度
【10月更文挑战第20天】
C语言算法复杂度
|
10天前
|
搜索推荐 算法 C语言
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
51 8
|
10天前
|
搜索推荐 算法 C语言
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
39 7
|
20天前
|
算法 大数据 Linux
深入理解操作系统之进程调度算法
【10月更文挑战第24天】本文旨在通过浅显易懂的语言,带领读者深入了解操作系统中的进程调度算法。我们将从进程的基本概念出发,逐步解析进程调度的目的、重要性以及常见的几种调度算法。文章将通过比喻和实例,使复杂的技术内容变得生动有趣,帮助读者建立对操作系统进程调度机制的清晰认识。最后,我们还将探讨这些调度算法在现代操作系统中的应用和发展趋势。
|
1月前
|
算法 调度 UED
深入理解操作系统的进程调度算法
【10月更文挑战第7天】在操作系统的心脏——内核中,进程调度算法扮演着至关重要的角色。它不仅影响系统的性能和用户体验,还直接关系到资源的合理分配。本文将通过浅显易懂的语言和生动的比喻,带你一探进程调度的秘密花园,从最简单的先来先服务到复杂的多级反馈队列,我们将一起见证算法如何在微观世界里编织宏观世界的和谐乐章。
|
1月前
|
边缘计算 算法 调度
探究操作系统的心脏:调度算法的进化与影响
【10月更文挑战第2天】 本文深入探讨了操作系统中核心组件——调度算法的历史演变、关键技术突破及其对现代计算的影响。通过详细回顾从单任务到多任务、实时系统及分布式计算环境下调度算法的发展,文章揭示了这些算法如何塑造我们的数字世界,并对未来的趋势进行了展望。不同于传统的摘要,本文特别聚焦于技术细节与实际应用的结合点,为读者提供一幅清晰的技术演进蓝图。
46 4
|
1月前
|
算法 调度 UED
探索操作系统的心脏:进程调度算法
【9月更文挑战第32天】在数字世界的每一次心跳中,都隐藏着一个不为人知的英雄——进程调度算法。它默默地在后台运作,确保我们的命令得到快速响应,应用程序平稳运行。本文将带你走进操作系统的核心,一探进程调度的奥秘,并通过代码示例揭示其背后的智慧。准备好跟随我一起深入这趟技术之旅了吗?让我们开始吧!
|
2月前
|
算法 调度
操作系统的心脏:深入解析进程调度算法
本文旨在深入探讨现代操作系统中的核心功能之一——进程调度。进程调度算法是操作系统用于分配CPU时间片给各个进程的机制,以确保系统资源的高效利用和公平分配。本文将详细介绍几种主要的进程调度算法,包括先来先服务(FCFS)、短作业优先(SJF)、时间片轮转(RR)以及优先级调度(PS)。我们将分析每种算法的基本原理、优缺点及其适用场景。同时,本文还将讨论多级反馈队列(MFQ)调度算法,并探讨这些算法在实际应用中的表现及未来发展趋势。通过深入解析这些内容,希望能够为读者提供对操作系统进程调度机制的全面理解。