银行家算法避免死锁的研究与实现.doc

银行家算法避免死锁的研究与实现 学 号： 姓 名： 专 业： 目 录 1 死锁 1 1.1 什么是死锁 1 1.2 产生死锁的原因 1 1.2.1 竞争系统资源 1 1.2.2 进程的推进不当 2 1.3 产生死锁的必要条件 2 1.4 解决死锁的基本方法 2 1.4.1 预防死锁 2 1.4.2 避免死锁 3 1.4.3 死锁检测 3 1.4.4 死锁的恢复 ? 4 2 银行家算法 4 2.1 关于银行家算法 4 3 程序实现 7 3.1 程序说明 7 3.2 程序源代码 7 3.3 程序测试 11 1 死锁 1.1 什么是死锁 在多道程序设计环境下，多个进程可能竞争一定数量的资源。一个进程申请资源，如果资源不可用，那么进入等待状态。如果所申请的资源被其他等待进程占有，那么该等待进程有可能无法改变状态，这种情况称为死锁（deadlock）。 设系统有一台打印机(R1)，一台读卡机(R2)，两进程共享这两台设备。用信号量S1表示R1是否可用，初值为1；用信号量S2表示R2是否可用，初值为1； ? ? ? ? ? ? ? ??? ? 这两个进程在并发执行过程中，可能会发生如下的情况。 即P1占用R1，P2占用R2，同时P1和P2又分别申请R2和R1的资源。于是造成了死锁。 1.2 产生死锁的原因 1.2.1 竞争系统资源 如循环图所示： 系统中只有一台打印机R1和一台读卡机R2，可供进程P1和P2共享。R1、R2已经分别分配给P1、P2使用，当P1、P2在不释放资源R1、R2而又同时分别申请R2、R1（如图），形成环路，这样会产生死锁。 1.2.2 进程的推进不当 如前面的例子可知他只是可能发生死锁，也就是说进程的推进不同会导致不同的结果。 1.3 产生死锁的必要条件 互斥条件 进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用。 占有并等待条件 当进程因请求资源而阻塞时，对已获得的资源保持不放。 非抢占条件 进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放。 循环等待条件 在发生死锁时，必然存在一个进程--资源的环形链。 1.4 解决死锁的基本方法 1.4.1 预防死锁 前面我们降到了死锁的必要条件，那么只要一个条件不满足的话，就不会发生死锁了。所以我们可以从必要条件的角度来预防死锁。 a.互斥条件 对于非共享资源，必须有互斥条件。而共享资源是不会涉及死锁。所以通常不能通过否定互斥条件来预防死锁：有些资源本身是非共享的。 b.占有并等待 为了确保该条件不在系统内出现，必须保证：当一个进程申请一个资源时，它不能占有其他资源。 资源一次性分配可以解决这个问题。实现这一分配有两种协议 1. 每个进程在执行前申请并获得所有资源。 2. 允许进程在没有资源时才可申请资源。 两种协议的缺点： 1.资源利用率不高 2.可能发生饥饿（磁带用到一半被抢了） c.非抢占 允许当前进程被其他进程抢过去。 缺点：可能发生饥饿（磁带用到一般被抢了） d.循环等待条件 确保此条件不成立的方法就是对所有资源类型进行完全排序，且要求每个进程按递增顺序来申请资源。 实现方法：资源有序分配法 遵循两种协议： A. 每个进程只按递增顺序申请资源。（第一次可以申请多个，但之后申请编号必须比前面大） B. 进程申请编号比拥有资源编号小时必须先释放大编号资源。 这样进程如果需要磁带机和绘图机，那进程必须先申请磁带机，再申请绘图机。如果再想申请打印机，则必须先释放绘图机。 1.4.2 避免死锁 通过前面介绍想必大家也看到了在预防死锁的过程中会严重系统性能。因此在避免死锁中我们不得不施加较弱的限制，从而获得比较满意的性能。由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算 资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。最具代表性的避免死锁的算法是银行家算法。 一般来说，由于操作系统有并发，共享以及随机性等特点，通过预防和避免的手段达到排除死锁的目的是很困难的。这需要较大的系统开销，而且不能充分利用资源。为此，一种简便的方法是系统为进程分配资源时，不采取任何限制性措施，但是提供了检测和解脱死锁的手段：能发现死锁并从死锁状态中恢复出来。 因此，在实际的操作系统中往往采用死锁的检测与恢复方法来排除死锁。 死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，并能通过外力破坏死锁发生的必要条件，从而使得并发进程从死锁状态中恢复出来。 1.一个用来检查系统状态从而确定是否出现了死锁算法。即死锁检测 2.一个用来从死锁状态中恢复的算法。即恢复算