操作系統(tǒng)教程第十周

本文格式為Word版，下載可任意編輯——操作系統(tǒng)教程第十周3.6死鎖

教學(xué)內(nèi)容：

3.6.4死鎖的避免(△□)3.6.5死鎖的檢測和解除

教學(xué)時(shí)數(shù)：

2學(xué)時(shí)

教學(xué)進(jìn)程：

3.6.4死鎖的避免

銀行家算法

銀行家擁有一筆周轉(zhuǎn)資金,客戶要求分期貸款，假使客戶能夠得到各期貸款，就一定能夠歸還貸款，否則就一定不能歸還貸款,銀行家應(yīng)提防的貸款，防止出現(xiàn)壞帳。

用銀行家算法避免死鎖

操作系統(tǒng)（銀行家）

操作系統(tǒng)管理的資源(周轉(zhuǎn)資金)進(jìn)程（要求貸款的客戶）

單種資源的銀行家算法

進(jìn)程PQR系統(tǒng)擁有某資源10個(gè)已有資源數(shù)422還需資源數(shù)427對(duì)每個(gè)請(qǐng)求進(jìn)行檢查，是否會(huì)導(dǎo)致?lián)鷳n全狀態(tài)。若是，則不滿足該請(qǐng)求；否則便滿足。檢查狀態(tài)是否安全的方法是看他是否有足夠的資源滿足一個(gè)距最大需求最近的客戶，如此反復(fù)下去。假使所有投資最終都被收回，則該狀態(tài)是安全的，最初的請(qǐng)求可以批準(zhǔn).

4個(gè)客戶每個(gè)都有一個(gè)貸款額度

一個(gè)狀態(tài)被稱為是安全的

條件是存在一個(gè)狀態(tài)序列能夠使所有的客戶均得到其所有的貸款。

上圖所示狀態(tài)是安全的，以使Marvin運(yùn)行終止，釋放所有的4個(gè)單位資金。這樣下去便可滿足Suzanne或Barbara的請(qǐng)求。

擔(dān)憂全的狀態(tài)

考慮給Barbara另一個(gè)她申請(qǐng)的資源，則得到的狀態(tài)是擔(dān)憂全的。

假使突然所有的客戶都申請(qǐng)，希望得到最大貸款額，而銀行家無法滿足其中任何一個(gè)的要求，則發(fā)生死鎖。

多種資源的銀行家算法

總的資源E、已分派資源P、剩余資源A

查找右邊矩陣是否有一行，其未被滿足的設(shè)備數(shù)均小于或等于向量A。假使找不到，系統(tǒng)將死鎖，任何進(jìn)程都無法運(yùn)行終止

若找到這樣一行，可以假設(shè)它獲得所需的資源并運(yùn)行終止，將該進(jìn)程標(biāo)記為終止，并將資源加到向量A上重復(fù)以上兩步，直到所有進(jìn)程都標(biāo)記為終止，則狀態(tài)是安全的，否則將發(fā)生死鎖

資源軌跡圖

兩階段上鎖算法

第一階段，進(jìn)程試圖將其所需全部記錄加鎖，一次鎖一個(gè)記錄若成功，則數(shù)據(jù)進(jìn)行更新并解鎖

若有些記錄已被上鎖，則它將已上鎖的記錄解鎖并重新開始執(zhí)行

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

考慮一個(gè)系統(tǒng)有n個(gè)進(jìn)程和m種不同類型的資源,現(xiàn)定義包含以下向量和矩陣的數(shù)據(jù)結(jié)構(gòu)：?系統(tǒng)每類資源總數(shù)--該m個(gè)元素的向量為系統(tǒng)中每類資源的數(shù)量Resource=(R1,R2,?,Rm)

?每類資源未分派數(shù)量--該m個(gè)元素的向量為系統(tǒng)中每類資源尚可供分派的數(shù)量Avilable=(V1,V2,?,Vm)

最大需求矩陣--每個(gè)進(jìn)程對(duì)每類資源的最大需求量,Cij表示進(jìn)程Pi需Rj類資源最大數(shù)

?C11?C?21Claim????????Cn1C12C22??Cn2????A12A22??An2????????C1m?C2m???????Cnm??????A1n?A2n???????Anm??分派矩陣—表示進(jìn)程當(dāng)前已分得的資源數(shù),Aij表示進(jìn)程Pi已分到Rj類資源的個(gè)數(shù)

?A11?A?21Allocation????????An1

銀行家算法中

以下關(guān)系式確保成立

?Ri=Vi+∑Aki對(duì)i=1,..,m,k=1,..,n;表示所有資源要么已被分派、要么尚可分派?Cki≤Rj對(duì)i=1,..,m,k=1,..,n;表示進(jìn)程申請(qǐng)資源數(shù)不能超過系統(tǒng)擁有的資源總數(shù)

?Aki≤Cki對(duì)i=1,..,m,k=1,..,n;表示進(jìn)程申請(qǐng)任何類資源數(shù)不能超過聲明的最大資源需求數(shù)

一種死鎖避免策略

系統(tǒng)中若要啟動(dòng)一個(gè)新進(jìn)程工作,其對(duì)資源Ri的需求僅當(dāng)滿足以下不等式：Ri≥C(n+1)I+∑Cki對(duì)i=1,..,m,k=1,..,n;

即應(yīng)滿足當(dāng)前系統(tǒng)中所有進(jìn)程對(duì)資源Ri的最大資源需求數(shù)加上啟動(dòng)的新進(jìn)程的最大資源需求數(shù)不超過系統(tǒng)擁有的最大數(shù)。

系統(tǒng)安全性定義

在時(shí)刻T0系統(tǒng)是安全的,僅當(dāng)存在一個(gè)進(jìn)程序列P1,..,Pn,對(duì)進(jìn)程Pk(k=1,..,n)滿足公式Cki-Aki≤Availablei+∑Aji,j=1,..,k;k=1,..,n;i=1,..,m

該序列稱安全序列,公式左邊表示進(jìn)程Pk尚缺少的各類資源;Availablei是T0時(shí)刻系統(tǒng)尚可

用于分派且為Pk所想要的那類資源數(shù);∑Aji表示排在進(jìn)程Pk之前的所有進(jìn)程占用的Pk所需要的資源的總數(shù)。

實(shí)例說明系統(tǒng)所處的安全或擔(dān)憂全狀態(tài)

假使系統(tǒng)中共有五個(gè)進(jìn)程和A、B、C三類資源;A類資源共有10個(gè),B類資源共有5個(gè),C類資源共有7個(gè)。

在時(shí)刻T0,系統(tǒng)目前資源分派狀況如下：

processAllocationClaimAvailableABCABCABCP0010753332P1200322P2302902P3211222P4002433

每個(gè)進(jìn)程目前還需資源為Cki-AkiprocessCki-Aki

ABCP0743P1122P2600P3011P4431

進(jìn)程P1申請(qǐng)資源request1=(1,0,2),檢查request1≤Available、比較(1,0,2)≤(3,3,2),結(jié)果滿足條件,試分派,得到新狀態(tài)：

processAllocationClaimAvailableABCABCABCP0010743230P1302020P2302600P3211011P400243

判定新狀態(tài)是否安全?可執(zhí)行安全性測試算法，找到一個(gè)進(jìn)程序列{P1,P3,P4,P0,P2}能滿足安全性條件,可正式把資源分派給進(jìn)程P1;

系統(tǒng)若處在下面狀態(tài)中,進(jìn)程P4請(qǐng)求資源(3,3,0),由于可用資源不足,申請(qǐng)被系統(tǒng)拒絕;此時(shí),系統(tǒng)能滿足進(jìn)程P0的資源請(qǐng)求(0,2,0);但可看出系統(tǒng)已處于擔(dān)憂全狀態(tài)了。

銀行家算法的基本思想

系統(tǒng)中的所有進(jìn)程進(jìn)入進(jìn)程集合,在安全狀態(tài)下系統(tǒng)收到進(jìn)程的資源請(qǐng)求后,先把資源試探性分派給它。

系統(tǒng)用剩下的可用資源和進(jìn)程集合中其他進(jìn)程還要的資源數(shù)作比較，在進(jìn)程集合中找到剩余資源能滿足最大需求量的進(jìn)程,從而,保證這個(gè)進(jìn)程運(yùn)行完畢并歸還全部資源。

把這個(gè)進(jìn)程從集合中去掉,系統(tǒng)的剩余資源更多了,反復(fù)執(zhí)行上述步驟。

最終,檢查進(jìn)程集合,若為空說明本次申請(qǐng)可行,系統(tǒng)處于安全狀態(tài),可實(shí)施本次分派;否則,有進(jìn)程執(zhí)行不完，系統(tǒng)處于擔(dān)憂全狀態(tài),本次資源分派暫不實(shí)施,讓申請(qǐng)進(jìn)程等待。

銀行家算法的程序及簡短說明

typestate=record/*全局?jǐn)?shù)據(jù)結(jié)構(gòu)*/resource,available:array[0?m-1]ofinteger;claim,allocated:array[0?n-1,0?m-1]ofinteger;end/*資源分派算法*/

ifalloc[i,*]+request[*]>claim[i,*]then/*申請(qǐng)量超過最大需求量*/else

ifrequest[*]>available[*]thenelse/*模擬分派*/end;

ifsafe(newstate)thenelse

endend

functionsafe(state:s):boolean;/*banker’salgorithm*/varcurrentavail:array{0?m-1}ofinteger;rest:setofprocess;begin

currentavail:=available;rest:={allprocess};possible:=true;whilepossibledo

findaPkinrestsuchthat

claim[k,*]-alloc[k,*]≤currentavail;

iffoundthencurrentavail:=currentavail+allocation[k,*];rest:=rest-[Pk];else

possible:=false;endend;

safe:=(rest=null)e