对银行家算法避免死锁的研究论文

死锁：是指两个以上的进程都因要求对方已经占有的资源，导致无法运行下去的现象，死锁是系统的一种出错状态，不仅浪费大量的系统资源，甚至会导致整个系统的崩溃，所以死锁是尽量预防和避免的。 产生死锁的四个条件： 死锁的处理 银行家算法是死锁避免的重要算法。 银行家算法：资源==钱；收回资源==收回贷款；收不回资源==不会放贷； 例题：假设系统中有三类互斥资源R1，R2，R3。可用资源分别是9,8,5.在T0时刻系统有P1，P2，P3，P4，P5五个进程，这些进程最大的需求和已分配的资源如下所示，如果按_执行，那么系统的状态是安全的。 解：第一步：根据可用资源，可以求得剩余资源。 R1=9-(1+2+2+1+1)=2 R2=8-(2+1+1+2+1)=1 R3=5-(1+1+0+0+3)=0 第二步：根据剩余资源求得还需要的资源数。 公式：还需资源（Need）=最大需求（Max）-已分配资源（Allocation）。 第三部，根据剩余资源数，求出安全序列。 根据剩余资源可得，p2可以执行（条件：每个值都必须≦剩余资源） 由此可见安全序列为P2-->p4-->p5-->p1-->p3。 其实安全序列不是唯一的，这是为什么呢？ 大家可以看出来，现有资源要大于需要资源的情况下是有多种选择的，因此安全序列不唯一。

给你个网址你自己看看吧！

死锁是指两个或两个以上的进程因竞争资源而造成的一种互相等待的现象，若无外力作用，这些进程都将无法向前推进。

饥饿：由于长期得不到想要的资源而导致进程无法向前推进的现象。如在进程调度算法中的短进程优先算法中，若有源源不断的短进程到来，则长进程一直得不到处理机，从而发生了长进程饥饿。   死循环：某进程执行的过程中一直跳不出某种循环的现象。死循环可能是因为程序bug或者程序员有意为之。

(1) 互斥条件。 只有对必须互斥使用的资源争抢（如打印机设备）才能导致死锁。   (2) 不剥夺条件。 进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。如果进程可以抢夺其他进程持有自己需要的资源的话，也就不会产生死锁了，需要资源直接抢就行了。   (3) 请求和保持条件。 进程已经保持了至少一个资源，但是又提出了新的资源需求，而该资源又被其他进程占有，此时请求进程被阻塞，但是又对自己持有的资源保持不放。也是很简单的道理，如果一个进程请求的资源被阻塞，就释放了自己持有的资源，其他进程就可以获取它释放的资源，也就不会发生相互等待而导致死锁了。   (4) 循环等待条件。 存在一种进程资源的循环等待链，链中的每一个进程已经获得的资源同时被下一个进程所请求。

(1) 对系统资源的争抢。各进程对不可剥夺资源的竞争可能会引起死锁。   (2) 进程推进顺序非法。如果请求资源的顺序不当也会导致死锁，如上面的图，双方请求的资源被对方占有而导致死锁。   (3) 信号量的使用不当。并发执行进程时，如果信号量使用的顺序不当也会到导致死锁。   总之，对不可剥夺的资源的不合理分配，可能导致死锁。

(1) 预防死锁。 破坏死锁产生的四个必要条件中的一个或几个。   (2) 避免死锁。 用某种方法防止系统进入安全状态，从而避免死锁（银行家算法）。   (3) 死锁的检测和解除。 允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后才去某种措施解除死锁。

如果把只能互斥使用的资源改造成允许共享使用，则系统不会进入死锁状态。如 SPOOLing技术 。操作系统可以采用SPOOLing技术吧独占设备在逻辑上改造成共享设备。 它由专门负责 I/O 的常驻内存进程以及输入、输出井组成。 比如，用SPOOLing技术将打印机改造为共享设备...

缺点：并不是所有的资源都可以改造成共享使用的资源。并且为了系统安全，有时候还需要保护这种互斥性。

方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时重新申请。   方案二：申请的资源被其他进程占用时，借助操作系统的协助，剥夺进程资源，至于剥夺哪个进程资源可以根据优先级考虑。   缺点：实现复杂。暂时请求不到某个资源，之前获取的资源就需要释放，以后重新申请，如果一直这样可能会导致饥饿。

可以采用 静态分配方法 ，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足之前，不让它运行。一旦运行，这些资源在运行期间一直归它所有，该进程就不会再请求别的任何资源。   缺点：如果有些资源只需要用很短的时间，因此如果进程运行时间长，在运行期间都会保持持有所有资源，就会造成资源浪费， 资源利用率低。 此外，该策略可能导致某些进程饥饿。如下，如果C类进程需要资源1和资源2，如果有大量的A或B类进程，就会导致C类进程一直不能一次获取全部需要的资源，导致饥饿。

可采用 顺序资源分配法。 首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源一次申请完。   原理：一个进程只要已占有我号的资源时，才有资格申请更大号编号的资源。按照这样的规则，已持有大编号的资源就不会逆向回来申请我号的资源，从而就不会产生循环等待的现象。   缺点：   (1) 实现复杂。   (2) 不方便增加新的设备，因为要重新分配所有编号。   (3) 进程实际使用资源的顺序可能和资源编号递增顺序不一致，会导致资源浪费。例如打印机设备编号2，输出设备编号为1，那么一个进程请求打印机设备前，必须先请求输出设备，而输出设备在请求打印机设备这一段时间内根本没有发挥作用，其他进程也不能访问，造成资源浪费。

假如你是一个成功的银行家，手里有100个小目标资金....现在有三家公司A、B、C分别向从你贷款

然而，有个规则，如果借给企业的钱达不到企业提出的最大需求，那么钱可能就一去不复返了.....   刚开始，三家公司分别从你这里借了20、10、30亿.......

此时，手里还要40亿，此时B表示还要借20亿，那么你需要考虑可以借吗？   如果给B借了20亿.....此时手里还要有20亿。

之后看手里剩下的钱能不能周转过来，现在可以将剩下的20亿借给C，C就达到了最大需求，之后C还钱50亿，然后借给A，A达到最大需求，最后A还70亿，最后A........还好借给B20亿后，可以通过 C->A->B 这个顺序周转，所以这20亿可以借。   现在看另一种情况，回到最初状态，现在手里还有40亿

对于上面的第一种借给B20亿是安全的，因为会存在C->A->B这样的周转路径（安全序列），不会血本无归。    安全序列：如果系统按照这种序列分配资源，则每个进程都能顺利完成。 只要能找出一个安全序列，系统就是 安全的 。一个系统的 安全序列可能有多个 。   如果分配了资源之后，系统中找不到任何一个安全序列，系统进入了 不安全状态 ，这就意味着之后可能所有的进程都无法顺序执行下去。当然，如果有进程提前归还了一些资源（如对上面的第二中情况，如果B提前还10亿，那么就可以周转了....），那系统也可能 重新回到安全状态 ，不过在分配资源之前总是考虑最坏情况 。   如果系统处于 安全状态 ，就 一定不会发生死锁 。如果系统进入了不安全状态未必一定发生死锁，但是发生了死锁一定是在不安全状态。

银行家算法 核心思想： 在进程提出资源请求时，先预先判断此次分配是否会导致系统进入不安全状态，如果进入不安全状态，就暂时不答应这次请求，让该进程先阻塞。   银行家算法步骤：

如果系统中既不采取预防死锁的措施，也不采取避免死锁的措施，系统就很可能发生死锁。在这种情况下，系统应当提供两个算法：   (1) 死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁。   (2) 死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来。

系统死锁可利用 资源分配图 来描述。

上图可以看到，R1类资源的资源数已经全部分配完了，R2类资源还有一个资源。P1进程向R2类资源请求一个资源，P2进程向R1类资源请求一个资源。   如果系统中剩余可用的资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利的执行下去。如果这个进程执行结束了把资源归还给系统，就可能使某些正在等待的资源的进程重新被激活，并顺利的执行下去。相应的，这些被激活的进程执行完后又会归还一些资源，这样可能又会激活另外一些阻塞的进程...

按照上面的过程分析，最终 能消除所有边 ，就称这个图是 可完全简化的 。此时一定 没有发生死锁 （相当于找到一个安全序列）。如果最终 不能消除所有边 ，那么此时就是 发生死锁了。    最终还连着边的进程就是处于死锁状态的进程。   检测死锁的算法：

死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁。   下图是一个系统死锁的图：

即使P3释放了资源，P1和P2进程都不满足继续运行的条件，所以此时P1和P2就是死锁进程。

解除死锁的方法有：   (1) 资源剥夺法。 挂起（暂时放在外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他进程，但是应防止被挂起长时间导致饥饿。   (2) 撤销进程法。 强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这中方法实现简单，但是也是有代价的，如果有些已经运行了很长时间了，离成功只有一步之遥了，此时撤销导致功亏一篑，还需要从头再来....   (3) 进程回退法。 让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。

那么对哪些进程动手呢？可以考虑优先对以下的进程处理：   (1) 优先级低的进程。   (2) 执行时间段的进程。   (3) 距离运行结束剩余时间长的进程。   (4) 使用资源多的进程。   (5) 批处理式而不是交互式的进程。