Question

请问哪个知道<<操作系统>>中的银行家算法，可以帮我一下吗？

是怎么个道理，我不是很懂．但是要考试的谢谢好心人．呵呵

Answer 1

"安全状态" 为 P[1..n] 之中寻找一排列，使资源 R[1..m] 可以按此排列顺序分配，不会产生不足的问题。若此排列存在，则是目前状态视为安全。在穷举法的情况之下，在所有排列中找出满足者需要 O(n)，银行家演算法则以 O(mn^2) 解决，但前提是每一程序需给定最多要求的资源量 Max[1..n][1..m]，(或者在某些网路上的范例称为 Claim[1..n][1..m])。目前每种资源所剩的数目则为 Available[1..m] 。 由定义可知，Need[i][1..m] = Max[i][1..m] - Allocated[i][1..m]。

银行家演算法分为两部份： "安全演算法" 与 "资源分配演算法"，后者包括了前者，基本概念十分简单：如果 P[i] 目前需要的资源数目 Need[i][1..m] 少於 Available[1..m] ，表示 P[i] 可以顺利完成工作，结束执行; 此时便让 P[i] 结束执行 (Finished[i] = 1)，释出目前占用资源，再另找一新程序 P[i'] 进行同样的测试步骤。如果到最后每个 P[1..n] 都执行完毕，则目前状态安全。如果有些程序尚未结束执行，其 Need[j][1..m] 却多於 Available[1..m] ，表示此程序 j 所需之资源太多，使其无法成为安全状态。

资源分配演算法的概念在於："试试看，如果所需资源被分配之后仍为安全状态，则允许此一资源之分配"。

若不知道 Max[1..n][1..m] ，则无法以 O(mn^2) 完成。