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

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