第3章死锁问题(856KB).ppt

* * * * * * * * * * * * * * * * * * * * * * * * Safe, Unsafe , Deadlock State * 3.3.2 银行家算法 1965年由Dijkstra提出的一种避免死锁的调度算法，它模拟了一个银行家在发放信用贷款时的处理方式。 在小镇上，有一位银行家和一些需要贷款服务的客户。银行家根据每一位客户的背景情况，为之设定了相应的最高贷款限额。现在的问题是银行家必须设计出一种算法，以保证借贷过程的顺利进行，也就是说，当某个客户提出了一个贷款申请时，该算法必须判断，如果批准了这个申请，是否会导致一种不安全的状态，如果是的话，就拒绝该申请；如果否的话，就批准该申请。 1. 单一资源类型的情形 * 一个例子 四个客户A、B、C、D，每个客户都有一个最高贷款限额，初始时，银行家手里只保留10K美元。 A 0 6 B 0 5 C 0 4 D 0 7 已贷 限额 银行家：10K 安全状态 7 4 D 4 2 C 5 1 B 6 1 A 已贷 限额 银行家： 2K 安全状态 7 4 D 4 2 C 5 2 B 6 1 A 已贷 限额 银行家： 1K 不安全状态 * 银行家算法 S1 某个客户提出贷款请求； S2 假设批准该请求，将得到系统状态T； S3 判断状态T是否安全， 如果安全，则批准该请求，转S1； 如果不安全，则不批准该请求，延期到 以后处理，转S1； 判断一个状态T是否安全 S1 银行家检查一下，看他手里的资源能否满足 某个客户的请求（剩余的最大限额）； S2 如果可以，则该客户的贷款请求已经满足， 因此他偿还了所有贷款。转S1； S3 如果到最后，所有的贷款都能偿还，则状态 T就是安全的，否则就是不安全的。 * 2. 多种资源类型的情形 银行家算法：与单一资源类型的情形相同。 判断一个状态T是否安全 数据结构：总的资源向量E、空闲资源向量A、当前分配矩阵C、请求矩阵R： S1 在请求矩阵R当中，寻找某一行Ri，它的每一个 分量均小于或等于A当中的相应元素；如果不存 在这样的行，则表示找不到一个进程可以运行结 束，系统将可能陷入死锁； S2 如果Ri存在，则假设进程Pi将请求它需要的所有 资源，并得到了满足。然后运行结束，并释放它 的所有资源（加入到A当中）； S3 重复上述两个步骤，直到所有的进程都能运行结 束，这就说明最初的状态T是安全的；或者是死 锁发生，这就说明T是不安全的。 * 一个例子 P1 3 0 1 1 P2 0 1 0 0 P3 1 1 1 0 P4 1 1 0 1 P5 0 0 0 0 当前分配矩阵 C P1 1 1 0 0 P2 0 1 1 2 P3 3 1 0 0 P4 0 0 1 0 P5 2 1 1 0 请求矩阵 R 总的资源向量 E ＝（ ） 空闲资源向量 A ＝（ ） 6 3 4 2 1 0 2 0 进程 磁带机 绘图仪 打印机 光驱 进程 磁带机 绘图仪 打印机 光驱 假设进程P2现在请求一个打印机… 1 1 0 0 0 0 0 – – – – 2 1 1 1 1 0 0 0 0 0 – – – – 5 1 2 2 * 这么说，利用银行家算法，在死锁避免 问题上，我们真能够做到釜底抽薪？ 3.3.3 死锁避免小结 NO! 从理论上说，银行家算法是精彩的，但从实际上来说，它是无用的。 请求矩阵R如何得到？ 进程的个数不是固定的，而是动态变化的； 资源的个数也不是固定的（磁带机突然坏了）。 * 3.4 死锁的预防 既然死锁的避免无法实现（它需要知道 将来的资源请求信息），那么在实际的 系统当中，如何来防止死锁的出现呢？ 破坏死锁产生的四个必要条件之一！ * 允许多个进程同时使用一个资源。例如，采用 假脱机打印方式，可以使多个进程同时生成输 出数据，然后由一个后台打印进程来真正使用 打印机。由于该打印进程不占用任何其他的资 源，因此可以消除因争夺打印机资源而引发的 死锁问题。但这种方法不具有普遍性。 1. 破坏互斥条件 * 2. 破坏请求和保持条件 不允许进程在占用资源的同时又去申请新的资源。 要求各个进程在开始运行之前，先一次性请求所有的资源。只有当这些资源都空闲时，系统才会分配给它，然后它可以开始运行。 进程事先并不知道自己将需要哪些资源，需要多少资源（否则，银行家算法就能用）； 这种方法难以保证资源的使用效率； 要求进程在请求一个新资源时，先暂时释放它已