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

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

教學內(nèi)容：

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

教學時數(shù)：

2學時

教學進程：

3.6.4死鎖的避免

銀行家算法

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

用銀行家算法避免死鎖

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

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

單種資源的銀行家算法

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

4個客戶每個都有一個貸款額度

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

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

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

擔憂全的狀態(tài)

考慮給Barbara另一個她申請的資源，則得到的狀態(tài)是擔憂全的。

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

多種資源的銀行家算法

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

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

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

資源軌跡圖

兩階段上鎖算法

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

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

銀行家算法的數(shù)據(jù)結構

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

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

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

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

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

銀行家算法中

以下關系式確保成立

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

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

一種死鎖避免策略

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

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

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

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

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

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

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

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

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

processAllocationClaimAvailableABCABCABCP0010753332P1200322P2302902P3211222P4002433

每個進程目前還需資源為Cki-AkiprocessCki-Aki

ABCP0743P1122P2600P3011P4431

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

processAllocationClaimAvailableABCABCABCP0010743230P1302020P2302600P3211011P400243

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

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

銀行家算法的基本思想

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

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

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

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

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

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

ifalloc[i,*]+request[*]>claim[i,*]then/*申請量超過最大需求量*/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