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

算法简介

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

算法目的

为了了解系统的资源分配情况,假定系统的任何一种资源在任意时刻只能被一个进程使用,任何进程已经占用的资源只能由进程自己释放,而不能由其他进程抢占,当进程申请的资源不能满足时,必须等待。因此只要资源分配算法能保证进程的资源请求,且不出现循环等待,则系统不会出现死锁。

算法原理

在避免死锁的方法中,所施加的限制条件较弱,有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态,只要能使系统始终都处于安全状态,便可以避免发生死锁。

银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。

设进程cusneed提出请求REQUEST [i],则银行家算法按如下规则进行判断。

  • (1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i],则转(2);否则,出错。
  • (2)如果REQUEST [cusneed] [i]<= AVAILABLE[i],则转(3);否则,等待。
  • (3)系统试探分配资源,修改相关数据:

AVAILABLE[i]-=REQUEST[cusneed][i];

ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];

NEED[cusneed][i]-=REQUEST[cusneed][i];

  • (4)系统执行安全性检查,如安全,则分配成立;否则试探险性分配作废,系统恢复原状,进程等待。

安全性检查算法

  • (1)设置两个工作向量Work=AVAILABLE;FINISH
  • (2)从进程集合中找到一个满足下述条件的进程,

FINISH==false;

NEED<=Work;

如找到,执行(3);否则,执行(4)

  • (3)设进程获得资源,可顺利执行,直至完成,从而释放资源。

Work=Work+ALLOCATION;

Finish=true;

GOTO 2

算法流程图

算法C语言实现版本1

实现效果

安全性检查

分配资源与安全性检查

网站所有原创代码采用Apache 2.0授权 
网站文章采用知识共享许可协议BY-NC-SA4.0授权

© 2018 • OmegaXYZ-版权所有 转载请注明出处

 

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注