銀行家算法的數(shù)據(jù)結構和安全測試算法

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