死锁的预防

一、解决死锁的方法

总体上有四种：

1、鸵鸟算法：不考虑此问题，不理睬死锁问题

2、不让死锁问题发生
又分为两种：
（1）死锁预防
静态策略：设计合适的资源分配算法，来保证死锁的发生
（2）死锁避免
动态策略：以不让死锁发生为目标，跟踪并评估资源分配过程，根据评估结果决策是否分配

3、让死锁发生
（1）死锁检测与解除

二、死锁预防

1、在设计系统时，通过确定资源分配算法，排除发生死锁的可能性
2、具体做法是：防止产生死锁的四个必要条件中的任何一个发生，即破坏产生死锁的四个必要条件之一。

第一个:破坏“互斥使用/资源独占”条件
1、资源转换技术：把独占资源变为共享资源

2、SPOOLing技术的引用
解决不允许任何进程直接占有打印机的问题
设计一个“守护进程/线程”负责管理打印机，进程需要打印时，将请求发给该daemon，由它完成打印任务

第二个：破坏“占有且等待”条件

进程在申请新的资源的同时保持对原有资源的占有。即一个进程请求资源得不到满足而阻塞自己时，并不释放自己已经分配得到的资源

1、实现方案1：要求每个进程在运行前必须一次性申请它所需要的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配
问题：资源利用率低；会出现饥饿现象

2、实现方案2：在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，从等待变成就绪后再重新申请
问题：可能它再次申请的那些资源已经不是之前的那个状态了，另外，申请新的资源也得不到了，那么也会导致饥饿现象。

第三个：破坏“不可抢占”条件

1、实现方案：
当一个进程申请的资源被其他进程占用时，可以通过操作系统抢占这一资源（两个进程优先级不同）
2、局限性：只适用于状态易于保存和恢复的资源（内存、CUP）

第四个：破坏“循环等待”条件

1、通过定义资源类型的线性顺序实现

2、实现方案：资源有序分配法

把系统中所有的资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配

3、要考虑的问题：哪个资源的编号在前面，那些资源的编号在后面，通常的，可以按照资源使用的频繁性，常使用的资源就放在前面，不常使用的资源放在后面。

4、例子：解决哲学家就餐问题

三、为什么资源有序分配法不会产生死锁？

假如说有资源1到10，以及有若干个进程需要使用这些资源，比如P1进程需要1、3、9这三个资源，P2进程需要1、2、5这三个资源。在任何一个时刻，在进程的集合当中总能够找到一个进程，这个进程得到的资源编号是最大的那个，也就是说，它得到了一些资源，那么在这些资源当中，因为是按顺序申请的，所以它拿到的目前为止得到资源编号最大的那个资源是在这个进程手里的，所以在这个进程集合里可以找到这样的进程，它拿到当前资源分配编号最大的那一个，那么从这一个进程出发，后续的资源编号都会比它现在占有的资源编号大，而后续的这些资源都没有分配出去，所以让这个进程继续申请，它后面的那些资源实际上都是能满足的，按照之前的假设，如果资源都满足了，那么久可以把资源使用完就还给系统，这样的话这个进程就执行完成了，那么这个集合就从n个进程变成了n-1个进程，然后再从n-1进程中寻找当前占有这个资源编号最大的进程，然后把后续的资源分配给这个进程，同样完成后又还给系统，集合从n-1变成了n-2，不断的消减，最后所有的进程都能完成

最后用一个小例子在总结下：
小河中铺了一串垫脚石用于过河，当垫脚石每次只允许一个人通过，并且两人在河中相遇且都不退让时发生了死锁。破坏死锁4个必要条件实现过河问题的方法如下：

（1）破坏互斥条件。将互斥资源改造成共享资源，即加宽垫脚石可以同时站立两个人，即允许两人共享一块垫脚石

（2）破坏请求和保持（部分分配）条件。在过河前，每个人必须申请使用河中的所有垫脚石（一次性分配所有资源）。

（3）破坏不可抢占（不剥夺）条件。当两个人在河中相遇的时候强行要求过河的另一方撤回，即抢占另一方使用的垫脚石资源

（4）破坏循环等待条件。为避免河中两人都要求对方的垫脚石而陷入循环等待，可铺设两串垫脚石供双放过河