操作系統(tǒng)第三章

3.1進(jìn)程間通信3.1.1并發(fā)進(jìn)程的特點3.1.2進(jìn)程間通信33.1.1并發(fā)進(jìn)程的特點資源共享引起的互斥關(guān)系

并發(fā)進(jìn)程互斥使用共享資源

Eg.兩個進(jìn)程均要獨占使用打印機(jī)

間接制約關(guān)系

進(jìn)程-資源-進(jìn)程協(xié)作完成同一個任務(wù)引起的同步關(guān)系

同步點

直接制約關(guān)系

進(jìn)程-進(jìn)程

43.1.2進(jìn)程間通信(1)進(jìn)程之間既相互依賴又相互制約，既相

互合作又相互競爭允許進(jìn)程相互交換數(shù)據(jù)與信息進(jìn)程通信模式

共享內(nèi)存

建立起一塊供協(xié)作進(jìn)程共享的內(nèi)存區(qū) 域，進(jìn)程通過向此共享區(qū)域讀或?qū)懭? 數(shù)據(jù)交換信息

消息傳遞

通過在協(xié)作進(jìn)程間交換消息實現(xiàn)通信

53.1.2進(jìn)程間通信(2)6進(jìn)程間通信模型3.2進(jìn)程同步3.2.1臨界資源與臨界區(qū)..5進(jìn)程互斥進(jìn)程同步信號量經(jīng)典進(jìn)程同步問題3.2.6管程

73.2.1臨界資源與臨界區(qū)(1)83.2.1臨界資源與臨界區(qū)(2)臨界資源

一次僅允許一個進(jìn)程使用的資源臨界區(qū)

每個進(jìn)程訪問臨界資源時必須互斥執(zhí)行

的程序使用臨界資源需遵循的原則

互斥使用：不能同時有兩個進(jìn)程在臨界

區(qū)內(nèi)執(zhí)行

讓權(quán)等待：等待進(jìn)入臨界區(qū)的進(jìn)程應(yīng)釋 放處理機(jī)后阻塞等待

9103.2.1臨界資源與臨界區(qū)(3)

有空讓進(jìn)：臨界資源空閑時，應(yīng)允許一

個請求臨界資源的進(jìn)程進(jìn)入臨界區(qū)

有限等待：不能使進(jìn)入臨界區(qū)的進(jìn)程無 限期地等待在臨界區(qū)之外進(jìn)程Pi的通用結(jié)構(gòu)

do{ entrysection

criticalsection

exitsection remindersection}while(1);3.2.1臨界資源與臨界區(qū)(4)11進(jìn)程A和進(jìn)程B互斥使用臨界區(qū)3.2.2進(jìn)程互斥(1)解決進(jìn)程互斥的硬件方法

關(guān)中斷

進(jìn)程剛進(jìn)入臨界區(qū)后立即禁止所有中 斷；進(jìn)程要離開之前打開所有中斷

原理：CPU只有在發(fā)生時鐘中斷或其

它中斷時才會進(jìn)行進(jìn)程切換實現(xiàn)12關(guān)中斷(disable)criticalsection開中斷(enable)3.2.2進(jìn)程互斥(2)優(yōu)點簡單缺點將禁止中斷的權(quán)力交給用戶進(jìn)程是不明智的在多處理機(jī)系統(tǒng)中，禁止中斷僅對

執(zhí)行本指令的CPU有效，其他CPU

仍將繼續(xù)運(yùn)行，并可訪問共享資源133.2.2進(jìn)程互斥(3)

測試和設(shè)臵指令

是一條不會被中斷的機(jī)器指令

為臨界資源設(shè)臵鎖位變量W

W=0，資源空閑可用

W=1，資源已被占用

初始化時，W的初值為0退出臨界區(qū)時，將W重臵為0實現(xiàn)14k:if(w==1)gotok;elsew=1;忙等待3.2.2進(jìn)程互斥(4)

示例：多個進(jìn)程利用TestSet實現(xiàn)互斥15constintn=3;voidP(inti){ while(1){

intw;TestSet(w);//加鎖CriticalSectionw=0;//開鎖

RemainderSection

}}

w=0;P(1);P(2);P(3);Parendvoidmain(){ Parbegin}3.2.2進(jìn)程互斥(5)解決進(jìn)程互斥的軟件方法

方法1：為兩個進(jìn)程Pi和Pj分別設(shè)臵布爾

變量，即booleanflag[2]，若flag[i]為

true，則表示進(jìn)程Pi正在臨界區(qū)。

ProcessPi：do{while(flag[j]);

flag[i]=true;

CriticalSection flag[i]=false; RemainderSection}while(1);兩個進(jìn)程同時進(jìn)入臨界區(qū)

163.2.2進(jìn)程互斥(6)

方法2：兩個進(jìn)程Pi和Pj共享整型變量

turn，turn指示哪個進(jìn)程應(yīng)進(jìn)入臨界區(qū)

，即turn==i時，允許進(jìn)程Pi進(jìn)入臨界 區(qū)，反之允許進(jìn)程Pj進(jìn)入臨界區(qū)。ProcessPi：do{while(turn!=i); CriticalSection turn=j; RemainderSection}while(1);強(qiáng)制兩個進(jìn)程交替進(jìn)入臨界區(qū)，臨界資源利用率不高

17183.2.2進(jìn)程互斥(7)

方法3：為兩個進(jìn)程Pi和Pj分別設(shè)臵布

爾變量，其初值為flag[i]=flag[j]=false

，若flag[i]==true，則表示進(jìn)程Pi要求 進(jìn)入臨界區(qū)，或是已在臨界區(qū)

ProcessPi：do{flag[i]=true;while(flag[j]);CriticalSectionflag[i]=false;RemainderSection}while(1);兩個進(jìn)程互相阻塞，均不能進(jìn)入臨界區(qū)3.2.2進(jìn)程互斥(8)方法4（Dekker算法）為兩個進(jìn)程Pi和Pj分別設(shè)臵布爾變量，即booleanflag[2]，其初值為flag[i]=flag[j]=false，若flag[i]==true，則表示進(jìn)程Pi要求進(jìn)入臨界區(qū)為兩個進(jìn)程Pi和Pj設(shè)臵共享整型變量turn指示應(yīng)該由哪個進(jìn)程進(jìn)入臨界區(qū)。turn==i時，表示允許進(jìn)程Pi進(jìn)入臨界區(qū)，反之允許進(jìn)程Pj進(jìn)入臨界區(qū)19203.2.2進(jìn)程互斥(9)

ProcessPi：do{flag[i]=true;while(flag[j]) if(turn==j){ flag[i]=false; while(turn==j);

flag[i]=true;

}CriticalSectionturn=j;flag[i]=false;RemainderSection}while(1);3.2.3進(jìn)程同步一組共行進(jìn)程，各自以獨立的、不可預(yù)

知的速度向前推進(jìn)，在前進(jìn)過程中彼此 之間需要相互協(xié)調(diào)步伐，才能正確地完

成同一項任務(wù)示例：計算進(jìn)程與打印進(jìn)程

213.2.4信號量(1)信號量

進(jìn)程同步工具

1965年由Dijkstra（荷蘭）提出 物理意義

表示資源的物理實體結(jié)構(gòu)22typedefstruct{ intvalue; structprocess*L;}semaphore;3.2.4信號量(2)value：表示該類資源的當(dāng)前可用數(shù)量L：等待使用該類資源的阻塞進(jìn)程隊列的隊首指針操作初始化：將value初始化為該類資源的可用數(shù)量原子操作P：申請資源原子操作V：釋放資源信號量value為負(fù)數(shù)時，其絕對值表示在該信號量上等待的進(jìn)程數(shù)目233.2.4信號量(3)//wait(S);down(S)P(S)：

S.value--;if(S.value<0){

addthisprocesstoS.L; block;}V(S)://signal(S);up(S)S.value++;if(S.value<=0){

removeaprocessPfromS.L;

wakeup(P);}

243.2.4信號量(4)25利用信號量實現(xiàn)n個進(jìn)程間的互斥

互斥信號量mutex，初值為1

第i個進(jìn)程的執(zhí)行代碼

do{

P(mutex)

<criticalsection>

V(mutex)

<remindersection>

}while(1);3.2.4信號量(5)利用信號量實現(xiàn)進(jìn)程間的同步

示例：利用信號量實現(xiàn)計算進(jìn)程與打印

進(jìn)程之間的同步過程。假定計算進(jìn)程和 打印進(jìn)程共同使用一個單緩沖

信號量

計算進(jìn)程：信號量empty,表示緩沖區(qū) 是否空，初值為1;

打印進(jìn)程：信號量full，表示緩沖區(qū)中

是否有可供打印的計算結(jié)果，初始值為026

3.2.4信號量(6)empty=1;full=0;parbeginbegin//計算進(jìn)程

loop computenextnumber

P(empty)

addthenumbertobuf

V(full)

…… endloopendbegin//打印進(jìn)程

loop

P(full)

printnextnumber

V(empty)

addtheemptytobuf …… endloopendparend

273.2.4信號量(7)信號量分類

公用信號量

互斥信號量，用于解決進(jìn)程之間互斥 進(jìn)入臨界區(qū)

私用信號量

同步信號量，用于解決異步環(huán)境下進(jìn) 程之間的同步

283.2.5經(jīng)典進(jìn)程同步問題(1)生產(chǎn)者—消費(fèi)者問題

是相互合作進(jìn)程關(guān)系的一種抽象

生產(chǎn)者：當(dāng)進(jìn)程釋放一個資源時，可把它 看成是該資源的生產(chǎn)者

消費(fèi)者：當(dāng)進(jìn)程申請使用一個資源時，可 把它看成該資源的消費(fèi)者

計算進(jìn)程：打印數(shù)據(jù)的生產(chǎn)者；空緩沖 的消費(fèi)者

打印進(jìn)程：打印數(shù)據(jù)的消費(fèi)者；空緩沖 的生產(chǎn)者

293.2.5經(jīng)典進(jìn)程同步問題(2)問題描述：

假定有一組生產(chǎn)者(M個）和一組消費(fèi)

者(N個）進(jìn)程，通過一個有界環(huán)形緩 沖區(qū)（k個緩沖塊）發(fā)生聯(lián)系。生產(chǎn) 者將生產(chǎn)的產(chǎn)品放入緩沖區(qū)，消費(fèi)者

從緩沖區(qū)取用產(chǎn)品。

當(dāng)緩沖區(qū)滿時，生產(chǎn)者要等消費(fèi)者取 走產(chǎn)品后才能向緩沖區(qū)放下一個產(chǎn)品

；當(dāng)緩沖區(qū)空時，消費(fèi)者要等生產(chǎn)者

放一個產(chǎn)品入緩沖區(qū)后才能從緩沖區(qū) 取下一個產(chǎn)品。

303.2.5經(jīng)典進(jìn)程同步問題(3)信號量

empty：表示空緩沖

塊的個數(shù)，初值為k full：有數(shù)據(jù)的緩沖

塊個數(shù)，初值為0

mutex：互斥訪問臨 界區(qū)的信號量，初

值為1

313.2.5經(jīng)典進(jìn)程同步問題(4)323.2.5經(jīng)典進(jìn)程同步問題(5)讀者—寫者問題

有一個多進(jìn)程共享的數(shù)據(jù)區(qū)（可以是一

個文件或者主存的一塊空間），有一些 只讀取這個數(shù)據(jù)區(qū)的進(jìn)程（reader)和

一些只往數(shù)據(jù)區(qū)中寫數(shù)據(jù)的進(jìn)程（

writer)：

任意多的讀進(jìn)程可以同時讀數(shù)據(jù)區(qū)

一次只有一個寫進(jìn)程可以寫數(shù)據(jù)區(qū)

若有寫進(jìn)程正在寫，禁止任何進(jìn)程讀

333.2.5經(jīng)典進(jìn)程同步問題(6)信號量

讀寫互斥信號量db：實現(xiàn)讀寫互斥和

寫寫互斥訪問共享文件，初值為1

計數(shù)器變量rc：記錄同時讀的讀者數(shù)，

初值為0

讀計數(shù)互斥信號量mutex：使讀者互斥 地訪問共享變量rc，初值為1

343.2.5經(jīng)典進(jìn)程同步問題(7)353.2.5經(jīng)典進(jìn)程同步問題(8)哲學(xué)家就餐問題

假設(shè)有5個哲學(xué)家

，花費(fèi)一生的時光 思考和吃飯。在桌 子上放著5把叉子

。一個哲學(xué)家要分

兩次去取其左邊和 右邊的叉子。若得

到兩把叉子，就開

始吃飯；吃完放下 兩把叉子。363.2.5經(jīng)典進(jìn)程同步問題(9)fork:ARRAY[0-4]OFsemaphore;mutex:semaphore;fork[0]:=fork[l]:=fork[2]:=fork[3]:=fork[4]:=l;mutex:=1;parbeginPi:REPEAT/*第i個哲學(xué)家的活動情況*/ ThinkFORwhile;/*思考一會兒，想吃飯*/P(mutex);P(fork[i]);P(fork[(i+l)MOD5]);V(mutex);

/*申請拿叉子*//*釋放申請權(quán)*/

EatFORWHILE;/*吃飯*/

V(fork[i]);

V(fork[(i+l)MOD5]);UNTILfalseparend

373.2.6管程(1)引入管程的原因

各個進(jìn)程自備P(S)和V(S)操作，加重了

用戶負(fù)擔(dān) 大量同步操作分散在各個進(jìn)程中，系統(tǒng)

管理復(fù)雜

易產(chǎn)生死鎖提出

1974年由Hansen和Hoare提出管程的定義

383.2.6管程(2)

一個管程調(diào)用了一個數(shù)據(jù)結(jié)構(gòu)和能為并

發(fā)進(jìn)程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一

組操作，這組操作能同步進(jìn)程和改變管 程中的數(shù)據(jù) 管程是關(guān)于共享資源的數(shù)據(jù)結(jié)構(gòu)及一組 針對該資源的操作過程所構(gòu)成的軟件模塊一次只有一個進(jìn)程能在管程內(nèi)活動。從而提供互斥機(jī)制，保證管程數(shù)據(jù)的一致性

39類3.2.6管程(3)管程的結(jié)構(gòu)

管程名

局部于管程的共享 變量說明

對該數(shù)據(jù)結(jié)構(gòu)進(jìn)行

操作的一組過程 對局部于過程的數(shù)

據(jù)設(shè)臵初始值的語

句403.2.6管程(4)

monitormonitor-name{ sharedvariabledeclarations... ...procedurebodyP1(…){ ...}procedurebodyP2(…){}procedurebodyPn(…){}initializationcode{}}413.2.6管程(5)管程的特點

局部于管程的數(shù)據(jù)結(jié)構(gòu)只能被局部于管

程的過程所訪問，任何管程外部的過程 都不能訪問它 局部于管程的過程只能服務(wù)管程內(nèi)的數(shù) 據(jù)結(jié)構(gòu) 管程每次只允許一個進(jìn)程進(jìn)入管程，從 而實現(xiàn)管程的互斥管程的同步機(jī)制

條件變量c

423.2.6管程(6)同步原語wait(c)：執(zhí)行wait(c)的進(jìn)程將自己阻塞在條件變量c的相應(yīng)等待隊列中。在阻塞前，釋放管程的互斥使用權(quán)；同步原語signal(c)：執(zhí)行signal(c)的進(jìn)程檢查條件變量c的相應(yīng)等待隊列。如果隊列為空，則執(zhí)行此操作的進(jìn)程繼續(xù)；否則，喚醒c隊列中的第一個等待者，讓被喚醒者進(jìn)入該管程。433.2.6管程(7)利用管程實現(xiàn)臨界資源的互斥使用monitormutexshow{

boolbusy;//臨界資源狀態(tài)

conditionnonbusy;//條件變量

definerequest,release;//進(jìn)程可調(diào)用過程

usewait,signal;//同步操作

Procedurerequest{//申請資源

ifbusythenwait(nonbusy); busy=true; } Procedurerelease{//釋放資源

busy=false;

signal(nonbusy);

}

{busy=false;}//初始：資源空閑}443.2.6管程(8)利用管程解決生產(chǎn)者—消費(fèi)者問題453.3消息傳遞通信(1)共享內(nèi)存通信（進(jìn)程低級通信）

優(yōu)點

速度快

缺點

傳送信息量小且效率低，每次通信只

能傳遞一個單位的信息量

P、V操作使用不當(dāng)時，易導(dǎo)致死鎖消息傳遞通信（進(jìn)程高級通信）

用戶直接利用OS提供的通信命令，高 效地傳遞大量數(shù)據(jù)

463.3消息傳遞通信(2)消息傳遞通信

消息結(jié)構(gòu)

消息緩沖

直接/間接通信

同步/異步通信直接通信

消息發(fā)送原語send(接收者，被發(fā)送信息始址，信息長度)

47structmessage_buffer{

sender:消息發(fā)送者

receiver:消息接收者size:消息長度text:消息正文next:指向下一消息 緩沖區(qū)指針};

主要工作請求分配一個消

息緩沖區(qū)；將消息正文傳送

到該緩沖區(qū)中，

并填入有關(guān)發(fā)送

參數(shù)；將該消息緩沖區(qū)

掛到接收進(jìn)程消

息鏈上send(receiver,a){ getbuf(a.size,i); i.sender=a.sender; i.size=a.size; i.text=a.text; i.next=0; getid(PCBset,receiver,j);P(j.mutex);Insert(j.mq,i);V(j.mutex);V(j.sm);}483.3消息傳遞通信(3)3.3消息傳遞通信(4)

接收消息原語

receive（發(fā)送者，信息始址，接收區(qū)

始址,信息長度)49

主要工作檢查消息鏈上 是否有消息；有則將消息接 收到接收區(qū)；無則阻塞等待消息的到來receive(b){

j=getid; P(j.sm); P(j.mutex); Remove(j.mq,i);

V(j.mutex);

b.sender=i.sender; b.size=i.size;b.text=i.text;}發(fā)送進(jìn)程P1send(p2,A,x)

發(fā)送區(qū)發(fā)送3.3消息傳遞通信(5)

接收進(jìn)程PCB信息隊列的頭指針…第一個消息緩沖區(qū)

...第N個消息緩沖區(qū)

50接收進(jìn)程P2接收receive(p1,A1,

B,x1)

接收區(qū)3.3消息傳遞通信(6)

消息隊列通常放在進(jìn)程控制塊中

PCB的結(jié)構(gòu)

structPCB{ …mq；//消息隊列隊首指針mutex；//消息隊列互斥信號量sm；//消息隊列同步信號量

…}

513.3消息傳遞通信(7)間接通信（信箱通信）

間接通信方式

發(fā)送原語

send(A,message)

接收原語

receive(A,message)

信箱屬性

共享 專用523.3消息傳遞通信(8)消息同步

發(fā)送進(jìn)程與接收進(jìn)程狀態(tài)

阻塞 非阻塞

消息同步方式

非阻塞發(fā)送，非阻塞接收 非阻塞發(fā)送，阻塞接收 阻塞發(fā)送，阻塞接收阻塞發(fā)送，非阻塞接收533.3消息傳遞通信(9)通信鏈路54

消息緩沖區(qū)發(fā)送進(jìn)程發(fā)送信息接收進(jìn)程接收信息消息發(fā)送發(fā)送信息接收進(jìn)程接收回答接收信息緩沖區(qū)發(fā)送回答進(jìn)程進(jìn)程之間的雙向通信進(jìn)程之間的單向通信3.4客戶-服務(wù)器系統(tǒng)通信(1)Socket通信RPC(RemoteProcedureCall)RMI(RemoteMethodInvocation)消息隊列553.4客戶-服務(wù)器系統(tǒng)通信(2)56Socket通信3.4客戶-服務(wù)器系統(tǒng)通信(3)57RPC通信3.4客戶-服務(wù)器系統(tǒng)通信(4)58消息隊列3.5死鎖3.5.1基本概念.3鴕鳥算法死鎖預(yù)防3.5.4死鎖避免3.5.5死鎖檢測3.5.6死鎖恢復(fù)

593.5.1基本概念(1)死鎖概念

多個進(jìn)程在運(yùn)行過程中因爭奪資源而造

成的一種僵局，當(dāng)進(jìn)程處于這種僵持狀 態(tài)時，若無外力作用，所有進(jìn)程都將無 法向前推進(jìn)產(chǎn)生死鎖的原因

競爭資源（資源數(shù)量不足）

資源類型

可搶占資源：主存、CPU

不可搶占資源：慢速設(shè)備/共享變量

603.5.1基本概念(2)R1R2P1P2S2P1S3P3S1P2I/O設(shè)備共享時的死鎖進(jìn)程之間通信時的死鎖

613.5.1基本概念(3)

進(jìn)程推進(jìn)順序非法

請求和釋放資源的順序不當(dāng)62

P2Rel(R1) P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)D(1)(2)(3)(4)3.5.1基本概念(4)死鎖產(chǎn)生的必要條件

同時具備下列四個條件

互斥條件

每個資源是不可共享的，它或者已經(jīng)

分配給一個進(jìn)程，或者空閑

保持和等待條件

進(jìn)程因請求資源而被阻塞等待時，對

已經(jīng)分配給它的資源保持不放

不可剝奪條件 循環(huán)等待條件

633.5.1基本概念(5)死鎖產(chǎn)生的必要條件

同時具備下列四個條件

互斥條件 保持和等待條件 不可剝奪條件

進(jìn)程所獲得的資源在未使用完之前，不 能被其它進(jìn)程強(qiáng)行剝奪，只能由獲得資 源的進(jìn)程自己釋放

循環(huán)等待條件

存在進(jìn)程循環(huán)鏈，鏈中有兩(多)個進(jìn)程 在等待鏈中下一個成員保持的資源643.5.1基本概念(6)資源分配圖

由節(jié)點V和邊E構(gòu)成；

節(jié)點V分為兩類：

進(jìn)程節(jié)點：P={P1,P2,…,Pn},用圓圈

表示，構(gòu)成了系統(tǒng)中的進(jìn)程集合；

資源節(jié)點：R={R1,R2,…,Rm},用方 塊表示，表示系統(tǒng)中的各種資源；

邊E分為兩類：

請求邊–有向邊P1→Rj

分配邊–有向邊Rj→Pi

65Pi擁有資源Rj的一個實例663.5.1基本概念(7)

示例

進(jìn)程

具有4個實例的資源

Pi請求資源Rj的一個實例

PiPi

RjRj3.5.1基本概念(8)67資源分配圖示例3.5.1基本概念(9)68資源分配圖示例3.5.1基本概念(10)69帶有死鎖的資源分配圖3.5.1基本概念(11)70有環(huán)路但未死鎖的資源分配圖3.5.1基本概念(12)結(jié)論資源分配圖中無環(huán)路無死鎖資源分配圖中有環(huán)路每類資源只有一個實例則死鎖；每類資源有多個實例，可能死鎖；解決死鎖的方法忽略死鎖問題，假定系統(tǒng)永不死鎖保證系統(tǒng)永遠(yuǎn)不進(jìn)入死鎖狀態(tài)死鎖預(yù)防死鎖避免713.5.1基本概念(13)允許系統(tǒng)進(jìn)入死鎖狀態(tài)，并可從死鎖狀態(tài)中恢復(fù)

死鎖檢測 死鎖恢復(fù)723.5.2鴕鳥算法假定死鎖從不發(fā)生原因

死鎖在計算機(jī)中很少出現(xiàn)

預(yù)防死鎖的代價太高UNIX和Windows采用此方法

733.5.3死鎖預(yù)防(1)破壞死鎖產(chǎn)生的必要條件破壞互斥條件

資源特性 將獨享設(shè)備改造為共享設(shè)備破壞保持和請求條件

進(jìn)程在開始運(yùn)行前必須獲得所需的全部 資源。若系統(tǒng)不能滿足，則該進(jìn)程等待

優(yōu)點

簡單，易于實現(xiàn)，安全

743.5.3死鎖預(yù)防(2)

缺點

資源利用率低 饑餓問題破壞非剝奪條件

當(dāng)一個已經(jīng)占有了一些資源的進(jìn)程提出新 的資源申請而不能立即得到滿足時，必須 釋放已經(jīng)占有的全部資源，待以后需要時 再重新申請

缺點

保護(hù)進(jìn)程放棄資源時的現(xiàn)場及之后的恢 復(fù)現(xiàn)場，系統(tǒng)要付出很高的代價

753.5.3死鎖預(yù)防(3)

增加了進(jìn)程周轉(zhuǎn)時間破壞循環(huán)等待條件將系統(tǒng)全部資源按類進(jìn)行全局編號排序，進(jìn)程對資源的請求必須按照資源的遞增或遞減順序序號申請缺點找到能滿足所有進(jìn)程要求的資源編號限制新類型設(shè)備的增加763.5.4死鎖避免(1)死鎖預(yù)防

靜態(tài)分配資源死鎖避免

動態(tài)分配資源

允許進(jìn)程動態(tài)地申請資源，一次申請一

部分資源。系統(tǒng)在進(jìn)行資源分配之前， 先計算資源分配的安全性。若此次分配

不會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，便將資

源分配給進(jìn)程；否則，進(jìn)程等待

773.5.4死鎖避免(2)系統(tǒng)處于安全狀態(tài)無死鎖系統(tǒng)處于不安全狀態(tài)可能死鎖避免死鎖保證系統(tǒng)永不進(jìn)入不安全狀態(tài)783.5.4死鎖避免(3)安全狀態(tài)

系統(tǒng)能按照某種進(jìn)程順序(P1,P2,…,Pn)

來為每個進(jìn)程Pi分配其所需資源，直至 滿足每個進(jìn)程對資源的最大需求，使每

個進(jìn)程都可順利地完成安全序列

(P1,P2,…,Pn)不安全狀態(tài)

不存在一個安全序列

793.5.4死鎖避免(4)(a)(b)(c)(d)(e)安全狀態(tài)——安全序列(B,C,A)

803.5.4死鎖避免(5)不安全狀態(tài)

81(a)(b)(c)(d)3.5.4死鎖避免(6)銀行家算法

1965年由Dijkstra提出

數(shù)據(jù)結(jié)構(gòu)

n表示進(jìn)程數(shù)目，m表示資源類型

可用資源向量Available：含有m個元

素的數(shù)組，每個元素代表一類可利用 的資源的數(shù)目，初始值為系統(tǒng)中所配

臵的該類資源的全部可用數(shù)目。如果

Available[j]=k，則表示系統(tǒng)中現(xiàn)有Rj

類資源k個。

823.5.4死鎖避免(7)最大需求矩陣Max：n×m的矩陣，定義了系統(tǒng)中n個進(jìn)程中的每一個進(jìn)程對m類資源的最大需求。如果Max[i,j]=k，則表示進(jìn)程Pi需要Rj類資源的最大數(shù)目為k。分配矩陣Allocation：n×m的矩陣，定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)目。如果Allocation[i,j]=k，則表示進(jìn)程Pi當(dāng)前已分配到Rj類資源的數(shù)目為k。833.5.4死鎖避免(8)需求矩陣Need：n×m的矩陣，表示每一個進(jìn)程還需要的各類資源的數(shù)目。如果Need[i,j]=k,則表示進(jìn)程Pi還需要Rj類資源k個，才能完成其任務(wù)。各個矩陣之間的關(guān)系：Need[i,j]=Max[i,j]–Allocation[i,j]算法設(shè)Requesti是進(jìn)程Pi的請求向量，如果Requesti[j]=k，表示進(jìn)程Pi需要k個Rj類的資源843.5.4死鎖避免(9)

1.如果Requesti[j]≤Need[i,j]，轉(zhuǎn)向第

2步；否則出錯；

2.如果Requesti[j]≤Available[j]，轉(zhuǎn) 向第3步；否則表示尚無足夠資源，

Pi須等待；

3.假定將資源分配給進(jìn)程Pi，修改下 列數(shù)據(jù)結(jié)構(gòu)：

Available[j]=Available[j]-Requesti[j]

Allocation[i,j]=Allocation[i,j]+Requesti[j]Need[i,j]=Need[i,j]-Requesti[j]853.5.4死鎖避免(10)4.系統(tǒng)執(zhí)行安全性算法，檢查此次分配后，系統(tǒng)是否處于安全狀態(tài)。安全資源分配給進(jìn)程Pi不安全Pi等待，本次試探分配取消，恢復(fù)原來的資源分配狀態(tài)安全性算法1.設(shè)臵工作向量Work，表示系統(tǒng)可提 供給進(jìn)程繼續(xù)運(yùn)行所需要的各類資源

數(shù)目，它含有m個元素，初始值為

Work=Available；863.5.4死鎖避免(11)2.設(shè)臵向量Finish，表示系統(tǒng)是否有足

夠的資源分配給進(jìn)程使之運(yùn)行完成，

它含有n個元素，初始值為

Finish[i]=false；3.從進(jìn)程集合中查找能滿足下列條件的進(jìn)程Finish[i]=falseNeed[i,j]Work[j]若存在該進(jìn)程，則轉(zhuǎn)4；否則，執(zhí)行5；873.5.4死鎖避免(12)4.進(jìn)程Pi獲得資源后可順利執(zhí)行至完成，并釋放分配給它的資源，即執(zhí)行

Work[j]=Work[j]+Allocation[i,j]

Finish[i]=true執(zhí)行第3步；5.若所有進(jìn)程均滿足Finish[i]==true，則 系統(tǒng)處于安全狀態(tài)；否則為不安全狀態(tài)示例：假定有5個進(jìn)程{P0,P1,P2,P3,P4}，3類資源{A,B,C}，各類資源的數(shù)目分別為10，5，7。88MaxAllocationNeedAvailableABCABCABCABCP

0753010743332P

1322200122P

2902302600P

3222211011P

44330024313.5.4死鎖避免(13)T0時刻的資源分配情況如下：89WorkAllocationNeedWork+AllocationFinishABCABCABCABCP

1332200122532trueP

3532211011743trueP

4743002431745trueP

27453026001047trueP

010470107431057true3.5.4死鎖避免(14)存在安全序列<P1,P3,P4,P2,P0>，系統(tǒng)處于安全狀態(tài)

90MaxAllocationNeedAvailableABCABCABCABCP

0753010743230P

1322302020P

2902302600P

3222211011P

44330024313.5.4死鎖避免(15)P1請求資源(1,0,2)

Request1(1,0,2)Need1(1,2,2)true Request1(1,0,2)Available1(3,3,2)true91WorkAllocationNeedWork+AllocationFinishABCABCABCABCP

1230302020532trueP

3532211011743trueP

4743002431745trueP

0745010743755trueP

27553026001057true3.5.4死鎖避免(16)執(zhí)行安全性算法可知，存在安全序列<P1,P3,P4,P0,P2>，系統(tǒng)處于安全狀態(tài)，可將資源分配給P1923.5.4死鎖避免(17)P4請求資源(3,3,0)

Request4(3,3,0)Need4(4,3,1)true Request4(3,3,0)Available4(2,3,0)false

P4等待P0請求資源(0,2,0)

Request0(0,2,0)Need0(7,4,3)true Request0(0,2,0)Available0(2,3,0)true

執(zhí)行安全性算法可知，系統(tǒng)進(jìn)入不安全 狀態(tài)，不能夠?qū)①Y源分配給P0

93MaxAllocationNeedAvailableABCABCABCABCP

0753030723210P

1322302020P

2