饥饿与死锁

• 死锁
• • 死锁的原理
  • 死锁的条件
  • 死锁的处理
• 死锁预防
• 死锁避免
• • 进程启动拒绝
  • 资源分配拒绝(`银行家算法`)
• 死锁检测
• • 死锁恢复
• 哲学家就餐

死锁

死锁的原理

1. 死锁是指多个进程因竞争资源而造成相互等待的现象
2. 死锁问题没有有效的通用解决方案

• 可重用资源：

• 定义： 一次仅供一个进程安全使用且不因使用而耗尽的资源

1. 处理器、I/O通道、内存、外存、数据库、信号量‘

• 考虑相互竞争的两个进程都要独占访问磁盘文件D和磁盘设备T的情形，此时，多道程序设计系统交替地执行两个进程时就会发生死锁： p 0 p 1 q 0 q 1 p 2 q 2 p_0p_1q_0q_1p_2q_2 p0​p1​q0​q1​p2​q2​

• 可消耗资源：

• 定义： 可被创建(生产)和销毁(消耗)的资源

1. 中断、信号、消息、I/O缓冲区

• 资源分配图：
  

死锁的条件

• 必要条件：

1. 互斥条件： 一个进程访问共享资源时，其他进程无法再访问该资源，直到正在访问的进程结束了对该共享资源的访问
2. 请求和保持条件:进程在获得一定的资源后，又对其他共享资源发出请求，而该资源被其他进程占有，请求进程被阻塞，并且该进程不释放自己已经占有的资源
3. 不可剥夺条件:进程已经获得的资源，除非完成对共享资源的访问后自己释放，否则不可被剥夺
4. 循环等待条件： 存在一个闭合的进程链，每个进程至少占有此链中下一个进程所需的一个资源

1. 系统中存在循环等待的进程集合，不一定会发生死锁

死锁的处理

1. 死锁的预防： 采用某种策略来消除条件1~4中的某个条件的出现
2. 死锁的避免： 基于资源分配的当前状态做动态选择
3. 死锁的检测： 检测死锁(满足条件1~4)的存在并从死锁中恢复

死锁预防

1. 设计一种系统来排除发生死锁的可能性
2. 死锁的预防方法会造成系统资源的低效使用和进程的低效执行
3. 分类：
   （1）直接死锁预防：防止三个必要条件中的任何一个条件的发生
   （2）间接死锁预防：防止循环等待的发生

1. 互斥条件不可能禁止，如果需要对资源进行互斥访问，那么操作系统就必须支持互斥
2. 为了预防占有和请求条件可要求进程一次性请求所有需要的资源，并阻塞这个进程直到所有请求都同时满足
   （1）进程可能会被长时间阻塞
   （2）为某一进程分配的资源可能未被使用，但其他进程也无法使用该资源
   （3）无法预测进程在执行过程中所需的全部资源
3. 预防不可剥夺条件的方法：
   （1）占有某些资源的一个进程进一步申请资源时若被拒绝，该进程主动放弃其最初占有的资源，必要时可再次申请这些资源和其他资源
   （2） 一个进程请求当前被另一个进程占有的一个资源时，操作系统可以抢占另一个进程，要求它释放资源
   （3）后一种方案只有在任意两个进程的优先级都不同的条件下才能预防死锁
4. 循环等待条件可以通过定义资源类型的线性顺序来预防，即若一个进程已分配了$R$类型的资源，则其接下来请求的资源只能是那些排在$R$类型之后的资源
   （1）类似占有和请求条件，循环等待的预防方法可能是低效的，它会使进程执行速度变慢

1. 死锁预防的方法都会导致低效的资源使用和低效的进程执行

死锁避免

1. 死锁的避免允许互斥条件、保持和请求条件以及不可剥夺条件，但通过明智的选择，可确保永远不会到达死锁点
2. 和死锁预防相比，死锁避免可允许更多的并发
3. 是否允许当前的资源分配请求是通过判断该请求是否可能导致死锁来决定的，因此死锁避免需要知道未来进程资源请求的情况

• 基本方法：

1. 若一个进程的请求会导致死锁，则不启动该进程
2. 若一个进程增加的资源请求会导致死锁，则不允许这一资源分配

进程启动拒绝

1. 考虑一个有 n n

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！