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

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