死锁避免 银行家算法_银行家算法例题详解_银行家算法解题过程(2)

非可剥夺资源死锁

死锁发生：双方都等待对方去生成资源，如次序：P1 P2

总的来说，死锁和不可剥夺资源有关。我们讨论的重点放在不可剥夺资源。

使用一资源事件的顺序如下：申请资源，使用资源，释放资源。

另一种原因是由于进程推进顺序不合适引发的死锁。资源少也未必一定产生死锁。就如同两个人过独木桥，如果两个人都要先过，在独木桥上僵持不肯后退，必然会因竞争资源产生死锁；但是，如果两个人上桥前先看一看有无对方的人在桥上，当无对方的人在桥上时自己才上桥，那么问题就解决了。死锁避免 银行家算法所以，如果程序设计得不合理，造成进程推进的顺序不当，也会出现死锁。

下面简述一下产生死锁的必要条件：

如果在计算机系统中同时具备下面四个必要条件时，那么会发生死锁。换句话说，只要下面四个条件中有一个不具备，系统就不会出现死锁。

1．互斥条件：即某个资源在一段时间内只能由一个进程占有，不能同时被两个或两个以上的进程占有。

2．不可抢占条件：进程所获得的资源在未使用完毕之前，资源申请者不能强行地从资源占有者手中夺取资源，而只能由该资源的占有者进程自行释放。

3．占有且申请条件：进程至少已经占有一个资源，但又申请新的资源；由于该资源已被另外进程占有，此时该进程阻塞；但是，它在等待新资源之时，仍继续占用已占有的资源。

4．循环等待条件：存在一个进程等待序列{P1,P2,…,Pn},其中P1等待P2所占有的某一资源，P2等待P3所占有的某一资源，……，而Pn等待P1所占有的某一资源，形成一个进程循环等待环。死锁避免 银行家算法

死锁的有向图表示

面我们提到的这四个条件在死锁时会同时发生。也就是说，只要有一个必要条件不满足，则死锁就可以排除。

处理死锁的基本方法可归结为以下3种：

关于死锁的预防、检测与恢复，不是本文讨论的话题，感兴趣的读者可翻阅相关资料查找到这些信息。在这里，我们着重谈一谈死锁的避免。

我们说死锁预防是排除死锁的静态策略，它使产生死锁的四个必要条件不能同时具备，从而对进程申请资源的活动加以限制，以保证死锁不会发生；而死锁的避免是排除死锁的动态策略，它不限制进程有关申请资源的命令，而是对进程所发出的每一个申请资源的命令加以动态地检查，并根据检查结果决定是否进行资源分配。就是说，在资源分配过程中若预测有发生死锁的可能性，则加以避免。这种方法的关键是确定资源分配的安全性。那么，是否存在一种算法，总能做出正确的选择从而避免死锁呢？答案是肯定的，但条件是必须事先获得一些特定的信息。

Dijkstra 于1965年提出了一个经典的避免死锁的算法----银行家算法（banker’s algorithm）。

其模型基于一个小城镇的银行家，他向一群客户分别承诺了一定金额的贷款，而他知道不可能所有客户同时都需要最大的贷款额。在这里，我们可将客户比作进程，银行家比作操作系统。银行家算法就是对每一个客户的请求进行检查，检查如果满足它是否会引起不安全状态。假如是，那么不满足该请求；否，那么便满足。

怎样得知一个状态是否安全呢？

所谓系统是安全的，是指系统中的所有进程能够按照某一种次序分配资源，并且依次地运行完毕，这种进程序列

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-47006-2.html