• 即将更新编译原理,机器学习,JavaScript,HTML/CSS等文章,谢谢关注~
  • 由于算法限制,搜索时注意简化关键字,谢谢支持~
  • 网站不兼容IE5.0及以下,请使用主流浏览器访问.
  • 操作系统银行家算法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-版权所有 转载请注明出处

     

    读者评分
    [评分人数: 2 平均分: 4]

    评论

    OmegaXYZ