操作系統(tǒng)銀行家算法

操作系統(tǒng)銀行家算法簡(jiǎn)介銀行家算法，也稱(chēng)為資源分配算法，是一種用于操作系統(tǒng)的安全性算法。該算法用于避免進(jìn)程在運(yùn)行過(guò)程中的死鎖狀態(tài)，確保資源的安全分配和釋放。它基于與銀行家類(lèi)似的原則，即只有在滿足所有進(jìn)程對(duì)資源的最大需求時(shí)，系統(tǒng)才會(huì)分配資源，否則將等待，從而避免了死鎖的發(fā)生。算法原理銀行家算法需要維護(hù)以下信息：可利用資源向量（Avlable）：表示系統(tǒng)當(dāng)前可分配給進(jìn)程的資源數(shù)量。最大需求矩陣（Max）：表示每個(gè)進(jìn)程對(duì)每種資源的最大需求量。已分配矩陣（Allocation）：表示每個(gè)進(jìn)程當(dāng)前已分配的資源數(shù)量。需求矩陣（Need）：表示每個(gè)進(jìn)程對(duì)每種資源還需要的數(shù)量。算法邏輯如下：初始化時(shí)，將可利用資源向量初始化為可分配資源的數(shù)量減去已分配給進(jìn)程的資源數(shù)量。檢查當(dāng)前系統(tǒng)的資源分配情況是否滿足每個(gè)進(jìn)程對(duì)資源的最大需求，如果滿足則進(jìn)入下一步，否則等待。選擇一個(gè)沒(méi)有死鎖的進(jìn)程，并檢查該進(jìn)程的最大需求是否小于等于系統(tǒng)當(dāng)前可利用的資源數(shù)量，如果是則進(jìn)入下一步，否則等待。假設(shè)分配資源給該進(jìn)程，執(zhí)行安全性檢查：分配資源給進(jìn)程，并在已分配矩陣和需要矩陣中更新相應(yīng)的數(shù)值。計(jì)算當(dāng)前系統(tǒng)可利用資源向量和需求矩陣的差值。檢查是否存在一個(gè)安全序列，如果存在則繼續(xù)進(jìn)行下一步，否則回滾分配的資源。終止進(jìn)程并回收其分配的資源。更新可利用資源向量和已分配矩陣。示例假設(shè)系統(tǒng)有3個(gè)進(jìn)程（P1、P2、P3）和4種資源（R1、R2、R3、R4），系統(tǒng)當(dāng)前的資源分配情況和進(jìn)程所需資源如下：可利用資源向量（Avlable）:3322最大需求矩陣（Max）:進(jìn)程R1R2R3R4P17534P23220P39022已分配矩陣（Allocation）:進(jìn)程R1R2R3R4P10100P22000P33022需求矩陣（Need）:進(jìn)程R1R2R3R4P17434P21220P36000系統(tǒng)根據(jù)銀行家算法的原理進(jìn)行分配和檢查的過(guò)程如下：第一次分配進(jìn)程P3請(qǐng)求資源：Request=(2000)檢查系統(tǒng)資源是否滿足該進(jìn)程對(duì)資源的需求：Need[P3]<=Avlable?

(6000)<=(3322)系統(tǒng)資源滿足進(jìn)程的需求，進(jìn)行第一次分配：Avlable=Avlable-Request

(3322)-(2000)=(1322)

Allocation[P3]=Allocation[P3]+Request

(3022)+(2000)=(5022)

Need[P3]=Need[P3]-Request

(6000)-(2000)=(4000)第二次分配進(jìn)程P3請(qǐng)求資源：Request=(1022)檢查系統(tǒng)資源是否滿足該進(jìn)程對(duì)資源的需求：Need[P3]<=Avlable?

(4000)<=(1322)系統(tǒng)資源滿足進(jìn)程的需求，進(jìn)行第二次分配：Avlable=Avlable-Request

(1322)-(1022)=(0300)

Allocation[P3]=Allocation[P3]+Request

(5022)+(1022)=(6044)

Need[P3]=Need[P3]-Request

(4000)-(1022)=(30-2-2)安全性檢查安全性檢查需要檢測(cè)系統(tǒng)是否存在一個(gè)安全序列，即進(jìn)程可以按照順序運(yùn)行直到完成，避免產(chǎn)生死鎖。計(jì)算安全序列的過(guò)程如下：定義安全序列（SafeSequence）Work=Avlable

Finish=[false,false,false]

whileexistsPsuchthatFinish[P]==falseandNeed[P]<=Work:

Work=Work+Allocation[P]

Finish[P]=true根據(jù)上述算法計(jì)算得到安全序列為[P3,P1,P2]。即系統(tǒng)可以按照該順序運(yùn)行直到完成，避免產(chǎn)生死鎖。回收資源系統(tǒng)完成進(jìn)程P3后，需要釋放其占用的資源并進(jìn)行相應(yīng)的更新：Avlable=Avlable+Allocation[P3]

(0300)+(6044)=(6344)

Allocation[P3]=(0000)

Need[P3]=(0000)終止進(jìn)程根據(jù)需要，如果所有進(jìn)程都已終止，則可停止系統(tǒng)。否則，返回第三步，選擇下一個(gè)沒(méi)有死鎖的進(jìn)程并檢查其需求量。結(jié)論銀行家算法是一種用于操作系統(tǒng)的資源分