操作系统原理复习 第五章 资源分配与调度

死锁

死锁定义1

• 两个或多个进程无限期地等待永远不会发生的条件的一种系统状态。
• 结果：每个进程都永远阻塞

死锁定义2

• 在两个或多个进程中，每个进程都已持有某种资源，但又继续申请其它进程已持有的某种资源。
• 每个进程都拥有其运行所需的部分资源，但又不足够运行，从而每个进程都不能向前推进，陷于阻塞状态。这种状态称死锁。

死锁的起因

• 系统资源有限：资源数目不足以满足所有进程的需要，引起进程对资源的竞争而产生死锁
• 并发进程的推进顺序不当：进程在运行过程中，请求和释放资源的顺序不当，导致进程产生死锁

死锁的必要条件

• 互斥条件：资源具有独占性，进程互斥使用资源
• 不剥夺条件：进程在释放资源前（即访问完）不能被其他进程剥夺
• 部分分配条件：进程所需资源逐步分配，需要时申请和分配
  • 占有一些资源，同时申请新资源
• 环路条件：多个进程构成环路：环中每个进程已占用的资源被前一进程申请，而自己所需新资源又被环中后一进程所占用

解决死锁的策略

预防死锁、避免死锁、检测死锁、恢复死锁

预防死锁

通过设置某些限制条件，破坏死锁四个必要条件中的一个或多个，来防止死锁。

• 破坏互斥条件……………（难）
• 破坏不剥夺条件…………（代价大）
• 破坏部分分配条件………（预先静态分配）
• 破坏环路条件……………（有序资源分配）
  • 较易实现， (早期)广泛使用。
  • 缺点：由于限制太严格，导致资源利用率和吞吐量降低。

避免死锁

在资源的分配过程中，用某种方法分析该次分配是否可能导致死锁？若会则不分配；若不会就分配

• 实现较难

检测和恢复死锁

允许死锁发生，但可通过检测机制及时检测出死锁状态，并精确确定与死锁有关的进程和资源，然后采取适当措施，将系统中已发生的死锁清除，将进程从死锁状态解脱出来。

• 检测方法复杂
• 恢复方法：撤消或挂起一些进程，以回收一些资源
• 实现难度大

预先静态分配法

目的：破坏部分分配条件

进程运行前将所需全部资源一次性分配给它

• 特点：进程仅当其所需全部资源可用时才开始运行

1. 应用设计和执行开销增大：进程运行前估算资源需求
2. 执行可能被延迟：进程所需资源不能全部满足时
3. 资源利用率低：资源被占而不用

• 改进：资源分配的单位由进程改为程序步

有序资源分配法

目的：破坏环路条件，使得环路无法构成

• 进程每次申请资源时只能申请序号更大的资源：如果进程已占有资源的序号最大为M，则下次只能申请序号大于M的资源，而不能再申请序号小于或等于M的资源。

• 分配资源时检查资源序号是否符合递增规定

  • 若不符合则拒绝该申请，并撤销该进程。
  • 若符合且资源可用则予以分配
  • 若符合但资源不可用则不分配，陷于阻塞。