銀行家算法的數據結構和安全測試算法一、銀行家算法的產生和背景在實際應用中，一個進程可能要訪問并且獨占多個資源，而操作系統又在實際應用中允許多個進程并發執行并共享系統資源，此時就可能出現系統進程永遠被阻塞的現象，導致系統進程一直處于等待狀態，為了避免出現上述死鎖的現象，銀行家算法的調度方式就可以解決這一問題。該算法的出現當時是基于一個小鎮的銀行家模型，其當時的算法描述為：假設一個銀行家擁有的資金數目為刀，并且可以被N個用戶享用，為確保銀行家算法的順利實施，銀行家對客戶提出三點要求：第一，每個客戶必須事先說明自己所需求的最大資金量；第二，每個客戶每次提出部分資金量的申請和獲得分配情況；第三，如果銀行滿足了客戶對資金的最大需求量，然后，客戶在資金運作完成后，應在有限時間內全部歸還銀行。只要滿足上面三點的要求，銀行將可以保證在有限的時間內讓客戶或得資金，我們現在把客戶看作是系統里面的進程，資金看做是系統資源數目，銀行看做是系統，我們就可以得出了銀行家算法，來實現避免產生死鎖的一種調度算法。二、銀行家算法的基本思想銀行家算法又可以稱之為“資源分配拒絕法”，其核心基本思想是：首先把系統中的所有進程放入進程集合里面。在系統安全狀態下，系統開始接收一個進程的資源請求，然后把資源試探性的分配給該進程。下面，系統開始使用剩下的可用資源和每個進程集合中的其他進程還需要的資源數目進行比較，在進程集合里面找到剩余資源數目可用滿足最大需求資源數目量的進程，從而保證了該進程可用順利運行完畢并且歸還全部資源數目，此時，從進程集合里面取出該進程，從而使得系統剩余的資源數目增多，然后重復執行上面操作步驟，類似數據結構中的遞歸算法思想應用。最后，對系統進程集合進行檢查，如果發現進程集合為空則表明此次申請是可行的，系統處于安全狀態，可真正實施本次的資源分配；如果發現進程集合中還有進程不能執行完畢，則表明此時系統處于不安全狀態，系統對本次資源分配暫不實施，讓該進程處于等待狀態，系統開始接受下一進程資源數目請求。三、銀行家算法的數據結構由于一個系統會有多個進程和多種不同類型的資源數目，現在我們假設一個系統進程數有N和資源的類型有M個，對此時系統的數據結構的定義可表示為包含以下的向量和矩陣：⑴系統中每類資源的總數目：使用m個元素的向量表示系統中每類資源的數目：Resource=(R1,R2,R3,…Rm)⑵系統中每類資源未分配數目：使用m個元素的向量表示系統中每類資源還可供分配的數目：⑶進程最大需求矩陣：每個進程對每類資源數目的最大需求量，Cij表示進程Pi需求Rj類資源最大數，為預防產生死鎖，實現死鎖避免，這個信息必須要事先獲?。簽榱藢崿F銀行算法解決死鎖的問題現在需要對上面的數據做如下的操作，并且需要保證下列關系式的成立：Ri=Vi+刀Aki，其中i屬于（1,2,3,…，m）,k屬于（1,2,3,…，n）；是用來統計所有的資源的分配情況，即表示當前資源要么已分配,要么尚可分配。Cki=C（n+1）i+刀Cki其中i屬于（1,2,3,…，m）,k屬于（1,2,3,…，n）；系統若要啟動一個新進程，其中對資源Ri的最大資源需求數，也即是說應該滿足當前系統中所有進程對資源Ri的最大資源需求說,加上啟動的新進程的最大資源需求數目,只有在最大資源需求數目不超過系統所擁有的最大數目時,系統才啟動該進程。⑤Cki-Aki ⑵P1請求資源現在我們假設進程P1要申請A資源的數目為1個和B類資源數目為2個,下面進行判斷此時申請能否立即準許,按照銀行家算法進行檢查：Request1（1,0,2）Available（2,3,0）此時尚可使用資源不能滿足進程