操作系统 - 死锁

定义

• 死锁是指多个进程因竞争资源而造成的一种相互等待的僵局，若无外力的作用，进程将无法继续进行
• 在多个程序系统中由于多个进程并发执行，改善了资源的利用率提高了系统的处理能力。但也会带来死锁问题

原因

• 系统资源的竞争：系统中拥有的不可剥夺资源不足以满足多个进程运行的需要，使得进程在运行过程中会因竞争资源而陷入僵局。只有对不可剥夺资源的竞争才可能产生死锁，对可剥夺资源的竞争是不会引起死锁
• 进程推进顺序非法：进程在运行中，申请和释放资源的顺序不当，也会导致死锁。信号量使用不当也会造成死锁。进程间彼此相互等待对方发来的消息，结果也会使得进程间无法继续向前推进
• 死锁产生的必要条件：产生死锁必须同时满足以下四条
  1. 互斥条件：进程要求的资源正在进行排他性控制。即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则该请求只能进行等待
  2. 不剥夺条件：进程所获取的资源在未使用完毕之前，不能被其他进程所剥夺。即进程获取的资源只能由该进程进行释放
  3. 请求和保持条件：进程在请求新资源时，该资源被其他进程占有，则此请求堵塞，对已获得资源保持不变
  4. 循环等待条件：存在一种进程资源的循环等待链，链中每一个进程已获得的资源被链中的下一个进程所请求

处理策略

为了使系统不发生死锁，必须设法破坏产生死锁的四个必要条件之一，或者在死锁发生时能够检测出，并有能力将其恢复

• 预防死锁：设置某些条件，破坏产生死锁的四个必要条件，来防止产生死锁
• 避免死锁：在资源的动态分配过程中，使用某种方法防止系统进入不安全状态，从而避免死锁
• 死锁的检测与接触：无需采取任何措施，允许进程在运行过程中产生死锁。通过系统的检测机制及时的检测出死锁，然后采取某种方式接触死锁

预防死锁和避免死锁都属于事先预防策略，但预防死锁的限制条件比较严格，实现起来较为简单，但往往导致系统的效率低，资源利用率低；避免死锁的限制条件相对宽松，资源分配后需要通过算法来判断是否真正的进入不安全状态，实现起来较为复杂

死锁预防

1. 破坏互斥条件：允许系统资源都能共享使用。显然是不现实的，有些资源无法同时访问。例：打印机
2. 破坏不剥夺条件：当一个已保持了某些不剥夺资源的进程，请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。该策略实现比较复杂，释放已获得的资源可能造成前面完成的的工作失效，反复申请和释放资源也会增加系统的开销，降低系统的吞吐量
3. 破坏请求和保持条件：采用预先静态资源分配方法，即进程在运行前申请完它所需的全部资源，在资源未满足之前不进行执行。一旦执行后资源一直归它所有，直至完成。该方式实现简单，但资源被严重浪费，其中有些资源仅在运行初期或运行结束时使用，甚至根本使用不到，而且还会导致“饥饿”现象，当某个资源被长期占用时，将导致等待该资源的进程迟迟不能运行
4. 破坏循环和等待条件：采用顺序资源分配法，首先给系统中的资源编号，规定每个进程必须按编号进行递增的顺序请求资源，同类资源一次申请完。该种策略容易发生释放资源的编号和系统规定顺序不同的情况，造成资源的浪费；此外也会对用户编程造成麻烦

死锁避免

在资源动态分配过程中，防止系统进入不安全状态，以避免死锁。该策略施加的限制条件比较弱，可以获得较好的系统性能 银行家算法 该算法是将系统资源当作银行家管理的资金，进程向系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家指定的规则为进程分配资源

1. 当进程首次申请资源时，要测试该进程对资源的最大需求量
2. 系统满足进程的最大需求量则按当前的申请分配资源，否则推迟分配
3. 当进程执行过程中继续申请资源，则先测试进程已占用资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒接分配，若没超过则在测试系统现存的资源是否满足该进程需要的最大资源数，若满足则按当前的申请量分配资源，否则推迟申请

死锁检测和解除

• 死锁定理：在资源分配图中，找出既不堵塞又不是孤点的进程，即资源分配图不可完全简化
• 死锁解除：一旦检测出死锁，就应该立即采取相应的措施解除死锁
  • 资源剥夺法：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源，而处于资源匮乏状态
  • 撤销进程法：强制撤销部分甚至全部的死锁进程。撤销的原则可以按照进程的优先级和撤销进程的代价的高低进行
  • 进程回退法：让一个或多个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点