admin 管理员组

文章数量: 1184232

文章目录

  • 银行家算法
    • 用途
    • 数据结构
    • 算法描述
    • 例题说明

银行家算法

用途

银行家算法用于避免死锁，是最著名的死锁避免算法

竞争资源和进程推进顺序不恰当会导致死锁

所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，都将无法再向前推进

  • 产生死锁的必要条件：
    ①互斥：进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用
    ②请求和保持：当进程因请求资源而阻塞时，对已获得的资源保持不放
    ③不剥夺：进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放
    ④环路等待：在发生死锁时，必然存在一个进程–资源的环形链

数据结构

  • (1) 可利用资源向量 Available
    这是一个含有 m 个元素的数组，其中每一个元素（Available[i]）代表第i类可利用的资源数目，其初始值是系统中所配置的该类资源的数目，其数值随该类资源的分配和回收而动态改变
    【Available[j] 表示系统中有的j类资源数量】
  • (2) 最大需求矩阵Max
    这是一个n x m的矩阵，定义了系统中每个进程对m类资源的总需求
    【Max[i][j] 表示第i个进程对j类资源的总需求数】
  • (3) 分配矩阵 Allocation
    这也是一个n x m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数
    【 Allocation[i][j]表示进程i当前己获得的第j类的资源数目
  • (4) 需求矩阵Need
    这也是一个n×m的矩阵，用以表示每一个进程还需要的各类资源数
    【Need[i][j]表示进程i还需要第j类的资源数量】

上述n x m矩阵间存在下述关系:
　　　　　　　　　Need[i][j] = Max[i][j] - allocation[i][j]

算法描述

资源分配算法

安全性算法（即上图资源分配算法中的安全检查部分）

例题说明


① T0时刻是否安全？

②T0时刻以后，若进程P2发出资源请求Request2(1,0,1)，系统能否将资源分配给它？

③在进程P2申请资源后，若P1发出资源请求Request1(1,0,1)，系统能否将资源分配给它？
④在进程P1申请资源后，若P3发出资源请求Request3(0,0,1)，系统能否将资源分配给它？

本文标签： 死锁 银行家 题型 算法 操作系统

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