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

《银行家算法避免死锁的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、银行家算法避免死锁的研究与实现目录1死锁11.1什么是死锁11.2产生死锁的原因11.2.1竞争系统资源11.2.2进程的推进不当21.3产生死锁的必要条件21.4解决死锁的基本方法21.4.1预防死锁21.4.2避免死锁31.4.3死锁检测31.4.4死锁的恢复 42银行家算法42.1关于银行家算法43程序实现73.1程序说明73.2程序源代码73.3程序测试111死锁1.1什么是死锁在多道程序设计环境下，多个进程可能竞争一定数量的资源。一个进程申请资源，如果资源不可用，那么进入等待状态。如果所申请的资源被其他等待进程占有，那么该等待进程有可能无法

2、改变状态，这种情况称为死锁（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而

3、又同时分别申请R2、R1（如图），形成环路，这样会产生死锁。第12页1.2.2进程的推进不当如前面的例子可知他只是可能发生死锁，也就是说进程的推进不同会导致不同的结果。1.3产生死锁的必要条件互斥条件进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用。占有并等待条件当进程因请求资源而阻塞时，对已获得的资源保持不放。非抢占条件进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放。循环等待条件在发生死锁时，必然存在一个进程--资源的环形链。1.4解决死锁的基本方法1.4.1预防死锁前面我们降到了死锁的必要条件，那么只

4、要一个条件不满足的话，就不会发生死锁了。所以我们可以从必要条件的角度来预防死锁。a.互斥条件对于非共享资源，必须有互斥条件。而共享资源是不会涉及死锁。所以通常不能通过否定互斥条件来预防死锁：有些资源本身是非共享的。b.占有并等待为了确保该条件不在系统内出现，必须保证：当一个进程申请一个资源时，它不能占有其他资源。资源一次性分配可以解决这个问题。实现这一分配有两种协议1.每个进程在执行前申请并获得所有资源。2.允许进程在没有资源时才可申请资源。两种协议的缺点：1.资源利用率不高2.可能发生饥饿（磁带用到一半被抢了）c.非抢占允许当前进程被其他进程抢过去

5、。缺点：可能发生饥饿（磁带用到一般被抢了）d.循环等待条件确保此条件不成立的方法就是对所有资源类型进行完全排序，且要求每个进程按递增顺序来申请资源。实现方法：资源有序分配法第12页遵循两种协议：A.每个进程只按递增顺序申请资源。（第一次可以申请多个，但之后申请编号必须比前面大）B.进程申请编号比拥有资源编号小时必须先释放大编号资源。这样进程如果需要磁带机和绘图机，那进程必须先申请磁带机，再申请绘图机。如果再想申请打印机，则必须先释放绘图机。1.4.2避免死锁通过前面介绍想必大家也看到了在预防死锁的过程中会严重系统性能。因此在避免死锁中我们不得不施加较

6、弱的限制，从而获得比较满意的性能。由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。最具代表性的避免死锁的算法是银行家算法。一般来说，由于操作系统有并发，共享以及随机性等特点，通过预防和避免的手段达到排除死锁的目的是很困难的。这需要较大的系统开销，而且不能充分利用资源。为此，一种简便的方法是系统为进程分配资源时，不采取任何限制性措施，但是提供了检测和解脱死锁的手段：能发现死锁并从死锁状态中恢复出来。因此，在实际的操作系统中往往

7、采用死锁的检测与恢复方法来排除死锁。死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，并能通过外力破坏死锁发生的必要条件，从而使得并发进程从死锁状态中恢复出来。1.一个用来检查系统状态从而确定是否出现了死锁算法。即死锁检测2.一个用来从死锁状态中恢复的算法。即恢复算法1.4.3死锁检测首先可以通过画分配图来判断是否发生了死锁。但如何用算法来判断呢？死锁检测算法。算法使用的数据结构是如下这些：       占有矩阵A：n*m阶，其中n表示并发进程的个数，m表示系统的各类资源的个数，这个矩阵记录了每一个进程当前占有

8、各个资源类中资源的个数。    申请矩阵R：n*m阶，其中n表示并发进程的个数，m表示系统的各类资源的个数，