死锁

死锁

• 死锁概念
• 死锁起因
• 死锁预防策略

---

死锁的定义

image.png

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

• 每个哲学家都无限期地等待邻座放下筷子
• 而邻座没有吃完之前都不会放下筷子
• 而邻座缺一只筷子永远都无法吃完

死锁起因

• 系统资源有限

  • 资源数目不足，进程对资源的竞争而产生死锁

• 并发进程的推进顺序不当

  • 进程请求资源和释放资源的顺序不当，导致死锁

关于死锁的一些结论

• 参与死锁的进程至少是2个
  • 两个或以上进程才会出现死锁
• 参与死锁的进程至少有2个已经占有资源
• 参与死锁的所有进程都在等待资源
• 参与死锁的进程是当前系统中所有进程的子集
• 死锁会浪费大量系统资源，甚至导致系统崩溃

死锁的必要条件

• 互斥条件
  • 进程互斥使用资源，资源具有独占性
• 不剥夺条件
  • 进程在访问完资源前不能被其他进程强行剥夺
• 部分分配条件
  • 进程边运行边申请资源，临时需要临时分配

  • 区别于：全部分配

    
    image.png

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

• 破坏互斥条件——难
• 破坏不剥夺条件——代价大
• 破坏部分分配条件——预先静态分配
• 破坏环路条件——有序资源分配

避免死锁

• 不事先采取限制去破坏产生死锁的条件，而是在资源分配过程中，用某种方法去评估若分配资源是否会让系统进入死锁状态，若是，则拒绝此次分配资源，从而避免死锁的发送
• 银行家算法
• 只需要较弱的限制条件，可获得较高的资源利用率和系统吞吐量。缺点：实现较难。

检测和恢复死锁

• 允许死锁发生，但可通过检测机制及时检测出死锁状态，并精确确定与死锁有关的进程和资源，然后采取适当措施，将系统中已发生的死锁清除，将进程从死锁状态解脱出来。
• 缺点1：检测方法复杂，实现难度大。
• 缺点2：恢复方法靠人工。撤销一些进程，回收资源再分配。

预先静态分配法
特点：

• 执行可能被延迟：所需资源不能全部满足时
• 应用开销增大：运行前估算资源需求
• 资源利用率低：资源被占而不用

有序资源分配法

• 目的：破坏环路条件，使得环路无法构成
• 策略：
  • 系统中的每个资源分配有唯一的序号
  • 进程每次申请资源时只能申请序号更大的资源
• 资源分配策略
  • 分配资源时检查资源序号是否符合递增规定：
    • 若不符合：则拒绝该申请，并撤销该进程
    • 若符合：且资源可用则予以分配
    • 若符合：且资源不可用则不分配，陷于阻塞