計(jì)算機(jī)操作系統(tǒng)ComputerOperatingSystems第三章

進(jìn)程同步第二章進(jìn)程管理132進(jìn)程同步死鎖管程4經(jīng)典的進(jìn)程同步問題3.1進(jìn)程同步3.1.1程序的并發(fā)執(zhí)行3.1進(jìn)程同步3.1.1程序的并發(fā)執(zhí)行在該例中存在下述前趨關(guān)系：

Ii→Ci，Ii→Ii+1,Ci→Pi,Ci→Ci+1，Pi→Pi+1而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之間，可以并發(fā)執(zhí)行。對于具有下述四條語句的程序段：

S1:a∶=x+2

S2:b∶=y+4

S3:c∶=a+b

S4:d∶=c+b并發(fā)進(jìn)程之間的兩種關(guān)系：相互獨(dú)立：進(jìn)程之間沒有任何關(guān)聯(lián)關(guān)系，僅有CPU競爭關(guān)系；相互關(guān)聯(lián)：進(jìn)程之間存在著某種關(guān)聯(lián)關(guān)系（直接或間接），需要相互通信。3.1進(jìn)程同步【例子】兩個(gè)進(jìn)程，讀－修改－寫count初值為1.進(jìn)程1 進(jìn)程2tmp1=count; tmp2=count;

tmp1++;tmp2=tmp2+2;

count=tmp1;count=tmp2;

請問：如果在這些進(jìn)程執(zhí)行之前，count變量的值為1，那么它最后的結(jié)果是多少？進(jìn)程1 進(jìn)程2tmp1=count;(=1)

interrupt...

tmp2=count;(=1)

tmp2=tmp2+2;(=3)

count=tmp2;(=3)

tmp1++;(=2)

count=tmp1;(=2)情形1情形2進(jìn)程1 進(jìn)程2tmp2=count;(=1)

interrupt...

tmp1=count;(=1)

tmp1++;(=2)

count=tmp1;(=2)

tmp2=tmp2+2;(=3)

count=tmp2;(=3)

情形3進(jìn)程1 進(jìn)程2tmp1=count;(=1)

tmp1++;(=2)

count=tmp1;(=2)

tmp2=count;(=2)

tmp2=tmp2+2;(=4)

count=tmp2;(=4)

3.1進(jìn)程同步3.1.1程序的并發(fā)執(zhí)行間斷性2)失去封閉性3)不可再現(xiàn)性競爭狀態(tài)（racecondition）：

兩個(gè)或多個(gè)進(jìn)程對同一共享數(shù)據(jù)同時(shí)進(jìn)行讀寫操作，而最后的結(jié)果是不可預(yù)測的，它取決于各個(gè)進(jìn)程具體運(yùn)行情況。3.1進(jìn)程同步3.1.1程序的并發(fā)執(zhí)行怎么解決？3.1進(jìn)程同步3.1.2進(jìn)程的互斥

對共享內(nèi)存或共享文件的訪問，可能會(huì)導(dǎo)致競爭狀態(tài)的出現(xiàn)。把需要互斥訪問的共享資源稱為“臨界資源”,把訪問臨界資源的那段程序稱為“臨界區(qū)”.競爭狀態(tài)（racecondition）：兩個(gè)或多個(gè)進(jìn)程對同一共享數(shù)據(jù)同時(shí)進(jìn)行讀寫操作，而最后的結(jié)果是不可預(yù)測的，它取決于各個(gè)進(jìn)程具體運(yùn)行情況。解決之道：在同一時(shí)刻，只允許一個(gè)進(jìn)程訪問該共享數(shù)據(jù)，即如果當(dāng)前已有一個(gè)進(jìn)程正在使用該數(shù)據(jù)，那么其他進(jìn)程暫時(shí)不能訪問。這就是互斥的概念。上述例子有何問題？

兩個(gè)進(jìn)程，在各自臨界區(qū)中需要對某個(gè)共享資源進(jìn)行訪問。非臨界區(qū)；…臨界區(qū)；…非臨界區(qū)；進(jìn)程P1非臨界區(qū)；…臨界區(qū)；…非臨界區(qū)；進(jìn)程P23.1.2進(jìn)程的互斥3.1進(jìn)程同步臨界資源3.1.2進(jìn)程的互斥3.1進(jìn)程同步進(jìn)程互斥是進(jìn)程之間的間接制約關(guān)系。

當(dāng)一個(gè)進(jìn)程進(jìn)入臨界區(qū)使用臨界資源時(shí)，另一個(gè)進(jìn)程必須等待。只有當(dāng)使用臨界資源的進(jìn)程退出臨界區(qū)后，這個(gè)進(jìn)程才會(huì)解除阻塞狀態(tài)。進(jìn)程互斥的產(chǎn)生原因進(jìn)程宏觀上并發(fā)執(zhí)行，依靠時(shí)鐘中斷來實(shí)現(xiàn)微觀上輪流執(zhí)行；訪問共享資源。3.1.2進(jìn)程的互斥3.1.2進(jìn)程的互斥3.1進(jìn)程同步可把一個(gè)訪問臨界資源的循環(huán)進(jìn)程描述如下：repeat

criticalsection;

remaindersection;

untilfalse;entrysectionexitsection任何兩個(gè)進(jìn)程都不能同時(shí)進(jìn)入臨界區(qū)；不能事先假定CPU的個(gè)數(shù)和運(yùn)行速度；當(dāng)一個(gè)進(jìn)程運(yùn)行在它的臨界區(qū)外面時(shí)，

不能妨礙其他的進(jìn)程進(jìn)入臨界區(qū)；任何一個(gè)進(jìn)程進(jìn)入臨界區(qū)的要求應(yīng)該在

有限時(shí)間內(nèi)得到滿足。3.1.2進(jìn)程的互斥3.1.2進(jìn)程的互斥3.1進(jìn)程同步應(yīng)遵循的規(guī)則空閑讓進(jìn)。(2)忙則等待。(3)有限等待。(4)讓權(quán)等待。

P、V原語包含有進(jìn)程的阻塞和喚醒機(jī)制，因此

在進(jìn)程等待進(jìn)入臨界區(qū)時(shí)不會(huì)浪費(fèi)CPU時(shí)間；Wait(P)原語：申請一個(gè)空閑資源(把信號(hào)量減1)，若成功，則退出；若失敗，則該進(jìn)程被阻塞；Signal(V)原語：釋放一個(gè)被占用的資源(把信號(hào)量加1)，若發(fā)現(xiàn)有被阻塞的進(jìn)程，則選擇一個(gè)喚醒之。Value=2Value=1Value=0Value=1Value=0Value=23.1.3信號(hào)量3.1.3整數(shù)型信號(hào)量Wait(S):whileS≤0dono-op

S

∶=S-1;

Signal(S):S∶=S+1;

信號(hào)量S是一個(gè)整數(shù)，代表可用資源數(shù)。Wait(P)原語：申請一個(gè)資源,Signal(V)原語：釋放一個(gè)資源。

用信號(hào)量實(shí)現(xiàn)互斥semaphoreS=1；ParbeginProcess1:BeginRepeateWait（S)；Criticalsection；Signal（S）；Untilfalse；End

Process2:BeginRepeate

Wait（S)；Criticalsection；

Signal（S）；Untilfalse；EndParend.利用信號(hào)量來實(shí)現(xiàn)進(jìn)程互斥intcount; //共享變量（臨界資源）semaphoremutex；//互斥信號(hào)量，初始化為??非臨界區(qū)Wait(mutex);臨界區(qū)Signal(mutex);非臨界區(qū)P1非臨界區(qū)Wait(mutex);臨界區(qū)Signal(mutex);非臨界區(qū)P2非臨界區(qū)Wait(mutex);臨界區(qū)Signal(mutex);非臨界區(qū)P33.1進(jìn)程同步進(jìn)程間的同步是指多個(gè)進(jìn)程中發(fā)生的事件存在某種時(shí)序關(guān)系，因此在各個(gè)進(jìn)程之間必須協(xié)同合作，相互配合，使各個(gè)進(jìn)程按一定的速度執(zhí)行，以共同完成某一項(xiàng)任務(wù)。同步：合作。 互斥：競爭。如何實(shí)現(xiàn)A先執(zhí)行，然后B執(zhí)行？A；V(S);進(jìn)程P1P(S);

B；進(jìn)程P2配對先后S初始值為0….A(先)；….進(jìn)程P1信號(hào)量S初始值為？？….B(后)；….進(jìn)程P2while(計(jì)算未完成){

得到一個(gè)計(jì)算結(jié)果;

將數(shù)據(jù)送到緩沖區(qū)；}Computewhile(打印未完成){

從緩沖區(qū)中取一數(shù)據(jù)；

打印該數(shù)據(jù)；}Print3.1.4進(jìn)程同步兩合作進(jìn)程共享一個(gè)緩沖區(qū)，工作流程如圖：計(jì)算下一數(shù)據(jù)從buf

取數(shù)據(jù)數(shù)據(jù)送buf打印圖：兩進(jìn)程共享單緩沖區(qū)工作流程ABAB3.1.4進(jìn)程同步

計(jì)算進(jìn)程A計(jì)算數(shù)據(jù)并將結(jié)果放入緩沖區(qū)buf中去，打印進(jìn)程則從緩沖區(qū)buf中取出數(shù)據(jù)來打印，如圖3.12。圖3.12：計(jì)算進(jìn)程和打印進(jìn)程使用單緩沖區(qū)情況

緩沖區(qū)打印進(jìn)程計(jì)算進(jìn)程BA計(jì)算下一個(gè)數(shù)據(jù)Wait(SA)數(shù)據(jù)送入緩沖區(qū)Signal(SB)Wait(SB)Signal(SA)從緩沖區(qū)取出數(shù)據(jù)打印該數(shù)據(jù)SA=1SB=0圖3.13：單緩沖區(qū)打印數(shù)據(jù)

因資源個(gè)數(shù)為1，所以在進(jìn)程同步的同時(shí)也已實(shí)現(xiàn)互斥，故不設(shè)互斥信號(hào)量，于是合作進(jìn)程A,B間的同步可描述如圖3.13：

如果將緩沖區(qū)空時(shí)看作一種資源SA,而將緩沖區(qū)滿時(shí)看作另一種資源SB．則對A進(jìn)程需要SA，釋放SB．而對B進(jìn)程需要SB，釋放SA．3.1.5記錄型信號(hào)量Wait(S):whileS≤0dono-op

S∶=S-1;

Signal(S):S∶=S+1;

整數(shù)型信號(hào)量的P、V操作，含有循序執(zhí)行空操作浪費(fèi)CPU資源。信號(hào)量結(jié)構(gòu)體類型的定義typedefstruct

{intvalue; //

計(jì)數(shù)變量

ListL//listofprocess；

}semaphore;3.1.5記錄型信號(hào)量Wait原語：申請一個(gè)資源semaphoreS;ProcedureWait（S）beginS.value=S.value-1;If(S.value<0)thenblock(S.L);endSignal原語：釋放一個(gè)資源semaphoreS;ProcedureSignal（S）beginS.value=S.value+1;If(S.value<=0)thenwakeup(S.L);end入口sem=sem-1S<0?調(diào)用阻塞進(jìn)程入等待隊(duì)列轉(zhuǎn)進(jìn)程調(diào)度是返回（a）P原語操作功能入口sem=sem+1S≤0?是喚醒等待隊(duì)列中的一個(gè)進(jìn)程返回或轉(zhuǎn)進(jìn)程調(diào)度否返回（b）V原語操作功能圖3-5P、V操作的流程圖3.1.5記錄型信號(hào)量否semaphoreSR1=1，SR2=1；ParbeginP1:BeginRepeateWait（SR1）；……..aWait（SR2）；……..bP1進(jìn)程的臨界區(qū)；Signal（SR2）；Signal（SR1）；Untilfalse；EndP2:BeginRepeateWait（SR2）；…….cWait（SR1）；…….dP2進(jìn)程的臨界區(qū)；Signal（SR1）；Signal（SR2）；Untilfalse；EndParend.3.1.6集合型信號(hào)量

semaphoreS1,S2,…,Sn;ProcedureSwait（S1,d1,S2,d2,…,Sn,dn）beginIfS1>=d1andS2>=d2and…andSn>=dnThenFori=1tonDoSi=Si-di;NextiElseblock(L);把進(jìn)程送入系統(tǒng)的因等待資源而阻塞的

進(jìn)程隊(duì)列Endifend3.1.6集合型信號(hào)量

ProcedureSsignal（S1,d1,S2,d2,…,Sn,dn）beginFori=1tonDoSi=Si+di;NextiIf(L不空)ThenWakeup（l

L）;喚醒L中滿足條件的一個(gè)進(jìn)程EndifendsemaphoreSa=1，Sb=1；ParbeginP1:BeginRepeateSwait（Sa,1,Sb,1）；

P1進(jìn)程的臨界區(qū)；Ssignal（Sa,1,Sb,1）；Untilfalse；EndP2:BeginRepeateSwait（Sa,1,Sb,1）；

P2進(jìn)程的臨界區(qū)；Ssignal（Sa,1,Sb,1）；Untilfalse；EndParend.39例題1

設(shè)系統(tǒng)中有兩個(gè)進(jìn)程P1、P2，P1進(jìn)程負(fù)責(zé)計(jì)算數(shù)據(jù)，將結(jié)果放入緩沖區(qū)Buf，P2進(jìn)程從緩沖區(qū)Buf中取數(shù)據(jù)輸出。試寫出兩個(gè)進(jìn)程的同步算法。40例題1

semaphorebe=1，bf=0；ParbeginP1:BeginRepeate

計(jì)算數(shù)據(jù)Data；Wait（be）；Data=>Buf；Signal（bf）；Untilfalse；EndP2:BeginRepeateWait（bf）；

取Data；Signal(be)；Untilfalse；EndParend.41例題2

42例題2

semaphorea=0，b=0，c=0，d=0，e=0，f=0，g=0；ParbeginBeginS1；Signal（a）；Signal（b）；EndBeginWait(a）；S2；Signal（c）；Signal（d）；EndBeginWait(b）；S3；Signal（e）；EndBeginWait(c）；S4；Signal（f）；EndBeginWait(d）；S5；Signal（g）；EndBeginWait(e）；Wait(f）；Wait(g）；S6；EndParend.3.2經(jīng)典的進(jìn)程同步問題3.2.1生產(chǎn)者消費(fèi)者問題

兩個(gè)進(jìn)程（生產(chǎn)者和消費(fèi)者）共享一個(gè)公有的、固定大小的緩沖區(qū)，生產(chǎn)者不斷地制造產(chǎn)品，并把它放入緩沖區(qū)，而消費(fèi)者不斷地把產(chǎn)品取出來，并且使用它。要求這兩個(gè)進(jìn)程相互協(xié)調(diào)，正確地完成各自的工作。12345678生產(chǎn)者生產(chǎn)—消費(fèi)者問題消費(fèi)方向生產(chǎn)方向消費(fèi)者3.2經(jīng)典的進(jìn)程同步問題3.2.1生產(chǎn)者消費(fèi)者問題

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

問題分析對于生產(chǎn)者進(jìn)程：制造一個(gè)產(chǎn)品，當(dāng)要送入緩沖區(qū)

時(shí)，要檢查緩沖區(qū)是否有空位，若是，才可將產(chǎn)品

送入緩沖區(qū)，并在必要時(shí)通知消費(fèi)者；否則等待；對于消費(fèi)者進(jìn)程：當(dāng)它去取產(chǎn)品時(shí)，先要檢查緩沖

區(qū)中是否有產(chǎn)品可取，若有，則取走一個(gè)，并在必

要時(shí)通知生產(chǎn)者；否則等待。這種相互等待，并互通信息就是典型的進(jìn)程同步。同時(shí)，緩沖區(qū)是個(gè)臨界資源，因此，各個(gè)進(jìn)程在

使用緩沖區(qū)的時(shí)候，還有一個(gè)互斥的問題。3.2.1生產(chǎn)者消費(fèi)者問題

semaphoreempty=n,full=0;itembuffer［0,…,n-1］;integerin=0,out=0;parbeginproceducer:beginrepeatitem=produce_item();wait(empty);buffer(in)=item;in=(in+1)modn;signal(full);untilfalse;endconsumer:beginrepeatwait(full);item=buffer(out);out=(out+1)modn;signal(empty);consumertheitem;untilfalse;endparend49生產(chǎn)者-消費(fèi)者問題semaphoreempty=n,full=0;itembuffer［0,…,n-1］;integerin=0,out=0;parbeginproceducer:beginrepeatitem=produce_item();wait(empty);buffer(in)=item;in=(in+1)modn;signal(full);untilfalse;endsemaphoremutex=1;

signal(mutex);

wait(mutex);50生產(chǎn)者-消費(fèi)者問題consumer:beginrepeatwait(full);item=buffer(out);out=(out+1)modn;signal(empty);consumertheitem;untilfalse;endparend

wait(mutex);

signal(mutex);3.2.2讀者寫者問題

3.2.2讀者寫者問題

（1）

任意多個(gè)讀進(jìn)程可以同時(shí)讀這個(gè)文件；

（2）

一次只有一個(gè)寫進(jìn)程可以往文件中寫；

（3）

如果一個(gè)寫進(jìn)程正在進(jìn)行操作，禁止任何讀進(jìn)程度文件。3.2.2讀者寫者問題

寫者進(jìn)程讀者進(jìn)程寫者進(jìn)程互斥互斥讀者進(jìn)程互斥不互斥54semaphorewrt=1;integerreadcount=0;parbegin

parend

Writer:begin

repeatwait(wrt);

performwriteoperation;

signal(wrt);untilfalse;endReader:begin

repeatifreadcount=0thenwait(wrt);readcount++;

performreadoperation;Readcount--;ifreadcount=0thensignal(wrt);untilfalse;end55讀者-寫者問題Reader:beginrepeat

ifreadcount=0thenwait(wrt);readcount++;

performreadoperation;

Readcount--;ifreadcount=0then

signal(wrt);untilfalse;end

wait(mutex);

signal(mutex);

wait(mutex);

signal(mutex);semaphoremutex=1;3.2.3哲學(xué)家問題

semaphorechopstick［0…4］；beginfor（i=0to4）chopstick［i］=1；nextiendparbeginrepeat think;wait(chopstick［i］); wait(chopstick［(i+1)mod5］); eat;signal(chopstick［i］); signal(chopstick［(i+1)mod5］);untilfalse;parend

可采取以下幾種解決方法：

(1)至多只允許有四位哲學(xué)家同時(shí)去拿左邊的筷子，最終能保證至少有一位哲學(xué)家能夠進(jìn)餐，并在用畢時(shí)能釋放出他用過的兩只筷子，從而使更多的哲學(xué)家能夠進(jìn)餐。

(2)僅當(dāng)哲學(xué)家的左、右兩只筷子均可用時(shí)，才允許他拿起筷子進(jìn)餐。

(3)規(guī)定奇數(shù)號(hào)哲學(xué)家先拿他左邊的筷子，然后再去拿右邊的筷子；而偶數(shù)號(hào)哲學(xué)家則相反。按此規(guī)定，將是1、2號(hào)哲學(xué)家競爭1號(hào)筷子；3、4號(hào)哲學(xué)家競爭3號(hào)筷子。即五位哲學(xué)家都先競爭奇數(shù)號(hào)筷子，獲得后，再去競爭偶數(shù)號(hào)筷子，最后總會(huì)有一位哲學(xué)家能獲得兩只筷子而進(jìn)餐。3.2.3哲學(xué)家問題

semaphorechopstick［0…4］；beginfor（i=0to4）chopstick［i］=1；nextiendparbeginrepeat

think;Swait(chopstick［i］，1，chopstick［(i+1)mod5］，1);

eat;Ssignal(chopstick［i］，1，chopstick［(i+1)mod5］，1);untilfalse;parend3.3死鎖3.3.1死鎖的基本概念

先看例題

假設(shè)系統(tǒng)中有進(jìn)程P1、進(jìn)程P2，有資源R1、資源R2，進(jìn)程P1、P2都需要使用資源R1、資源R2。進(jìn)程P1、P2的同步算法semaphoreSR1=1，SR2=1；ParbeginP1:BeginRepeateWait（SR1）；……..aWait（SR2）；……..bP1進(jìn)程的臨界區(qū)；Signal（SR2）；Signal（SR1）；Untilfalse；EndP2:BeginRepeateWait（SR2）；…….cWait（SR1）；…….dP2進(jìn)程的臨界區(qū)；Signal（SR1）；Signal（SR2）；Untilfalse；EndParend.【例】過橋問題交通規(guī)則：車輛靠右行駛！3.3死鎖3.3.1死鎖的基本概念

3.3死鎖3.3.1死鎖的基本概念

死鎖是指兩個(gè)或兩個(gè)以上的進(jìn)程在執(zhí)行過程中，因爭奪資源而造成的一種互相等待的現(xiàn)象，若無外力推動(dòng)，它們都將無法推進(jìn)下去，此時(shí)稱系統(tǒng)處于死鎖狀態(tài)或者說系統(tǒng)產(chǎn)生了死鎖。3.3死鎖3.3.2死鎖的產(chǎn)生的原因

1）資源不夠，資源的數(shù)量不是足夠多，不能同時(shí)滿足所有進(jìn)程提出的資源申請，這就造成了資源的競爭，而且資源的使用不允許剝奪。2）進(jìn)程的推進(jìn)不當(dāng)，進(jìn)程的推進(jìn)次序影響系統(tǒng)對資源的使用。比如，上述的P1、P2進(jìn)程，如果讓P1進(jìn)程申請R1資源，再申請R2資源，然后P2申請R2，可能這時(shí)P2暫時(shí)因得不到資源而阻塞，但P1進(jìn)程需要的資源都已滿足，P1進(jìn)程會(huì)使用資源結(jié)束，釋放資源并喚醒P2進(jìn)程。這樣的推進(jìn)方式就不會(huì)死鎖了。進(jìn)程推進(jìn)次序

663.1.2資源（resources）

資源可以分為兩大類：可搶占的（preemptable）

和不可搶占的（nonpreemptable）。

可搶占的資源：當(dāng)一個(gè)進(jìn)程正在使用這種類型

的資源時(shí)，可以把它拿走而不會(huì)對該進(jìn)程造成

任何不良的影響。例如：CPU、內(nèi)存。不可搶占的資源：當(dāng)一個(gè)進(jìn)程正在使用這種類

型的資源時(shí)，如果強(qiáng)行把它拿走，將會(huì)導(dǎo)致該

進(jìn)程運(yùn)行失敗。例如：光盤刻錄機(jī)。死鎖主要由不可搶占資源引起。3.3死鎖3.3.3產(chǎn)生死鎖的必要條件

互斥條件：在任何時(shí)刻，每一個(gè)資源最多只能被

一個(gè)進(jìn)程所使用；請求和保持條件：進(jìn)程在占用若干個(gè)資源的同時(shí)

又可以請求新的資源；不可搶占條件：進(jìn)程已經(jīng)占用的資源，不會(huì)被強(qiáng)

制性拿走，而必須由該進(jìn)程主動(dòng)釋放；環(huán)路等待條件：存在一條由兩個(gè)或多個(gè)進(jìn)程所組

成的環(huán)路鏈，其中每一個(gè)進(jìn)程都在等待環(huán)路鏈中

下一個(gè)進(jìn)程所占用的資源。3.3死鎖3.3.4銀行家算法

怎樣能避免死鎖呢？？3.3.4銀行家算法安全狀態(tài)所謂安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序(P1,P2,…，Pn)(稱〈P1,P2,…,Pn〉序列為安全序列)，來為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對資源的最大需求，使每個(gè)進(jìn)程都可順利地完成。如果系統(tǒng)能找到這樣一個(gè)安全序列，則稱系統(tǒng)處于安全狀態(tài)。如果系統(tǒng)無法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。3.3.4銀行家算法示例：

系統(tǒng)中有三個(gè)進(jìn)程P1、P2和P3，共有12臺(tái)磁帶機(jī)。進(jìn)程P1總共要求10臺(tái)磁帶機(jī)，P2和P3分別要求4臺(tái)和9臺(tái)。假設(shè)在T0時(shí)刻，進(jìn)程P1、P2和P3已分別獲得5臺(tái)、2臺(tái)和2臺(tái)磁帶機(jī)，尚有3臺(tái)空閑未分配?，F(xiàn)在的狀態(tài)是安全狀態(tài)嗎？進(jìn)程最大需求已分配可用P1P2P31049522371銀行家算法

一個(gè)銀行家，手里有100萬元的資金，他看中三個(gè)投資項(xiàng)目，這三個(gè)投資項(xiàng)目所需資金分別是60萬、30萬、70萬。這三個(gè)項(xiàng)目的總投資160萬元，三個(gè)項(xiàng)目的啟動(dòng)資金分別是20萬、20萬、30萬。項(xiàng)目號(hào)需求總資金已獲得資金還需要資金銀行家剩余資金12360307020203040104030當(dāng)前的資金投入是安全的72銀行家算法

在當(dāng)前狀態(tài)下如果項(xiàng)目1提出申請資金20萬，銀行家是否批準(zhǔn)呢？項(xiàng)目號(hào)需求總資金已獲得資金還需要資金銀行家剩余資金12360307020203040104030當(dāng)前的資金投入也是安全的，可以批準(zhǔn)40201073銀行家算法

這時(shí)項(xiàng)目3提出5萬元的資金要求，銀行家是否同意呢？項(xiàng)目號(hào)需求總資金已獲得資金還需要資金銀行家剩余資金12360307040203020104010資金狀態(tài)變成不安全狀態(tài)，不予批準(zhǔn)??！353553.3.4銀行家算法

銀行家的做法就是判斷系統(tǒng)的安全性，動(dòng)態(tài)地決定資源的分配。

銀行家算法是一種代表性的避免死鎖的算法。它允許進(jìn)程動(dòng)態(tài)地申請資源，系統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計(jì)算此次分配資源的安全性，若分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則分配，否則不分配。75銀行家算法1.銀行家算法中的數(shù)據(jù)結(jié)構(gòu)

(1)可利用資源向量Available。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果Available［j］=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。

(2)最大需求矩陣Max。這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對m類資源的最大需求。如果Max［i,j］=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。

(3)分配矩陣Allocation。這也是一個(gè)n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation［i,j］=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。

(4)需求矩陣Need。這也是一個(gè)n×m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Need［i,j］=K，則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)。Need［i,j］=Max［i,j］-Allocation［i,j］

2.銀行家算法

設(shè)Requesti是進(jìn)程Pi的請求向量，如果Requesti［j］=K，表示進(jìn)程Pi需要K個(gè)Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：

(1)如果Requesti［j］≤Need［i,j］，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。

(2)如果Requesti［j］≤Available［j］，便轉(zhuǎn)向步驟(3)；否則，表示尚無足夠資源，Pi須等待。

(3)系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：

Available［j］∶=Available［j］-Requesti［j］;Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;Need［i,j］∶=Need［i,j］-Requesti［j］;

(4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。

假定系統(tǒng)中有五個(gè)進(jìn)程｛P0,P1,P2,P3,P4｝和三類資源｛A,B,C｝，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖所示。銀行家算法舉例資源情況進(jìn)程MaxAllocationNeedAvailableABCABCABCABCP0852110742233P1322200122

P2802301501

P3223211012

P4433002431

系統(tǒng)中存在一個(gè)安全序列（P1，P3，P4，P2，P0），所以它是安全的銀行家算法舉例系統(tǒng)中存在一個(gè)安全序列（P1，P3，P4，P2，P0），所以它是安全的資源情況進(jìn)程WorkNeedAllocationWork+Allocation

FinishABCABCABCABCP1233122200433trueP3433012211644trueP4644431002646trueP2646501301947trueP09477231101057true

P1發(fā)出請求向量Request1(1，0，2)銀行家算法舉例資源情況進(jìn)程MaxAllocationNeedAvailableABCABCABCABCP0852110742233P1322200122

P2802301501

P3223211012

P4433002431

302020131銀行家算法舉例系統(tǒng)中還存在安全序列（P1，P3，P4，P2，P0），所以它是安全的資源情況進(jìn)程WorkNeedAllocationWork+Allocation

FinishABCABCABCABCP1233122200433trueP3433012211644trueP4644431002646trueP2646501301947trueP09477231101057true

P4發(fā)出請求向量Request4(1，2，0)銀行家算法舉例資源情況進(jìn)程MaxAllocationNeedAvailableABCABCABCABCP0852110742131P1322302020

P2802301501

P3223211012

P4433002431

122311011系統(tǒng)中不存在存在安全序列，是不安全的，不予分配??！3.安全性算法(1)設(shè)置兩個(gè)向量：①工作向量Work:它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算法開始時(shí)，Work∶=Available;②Finish:它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finish［i］∶=false;當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令Finish［i］∶=true。

(2)從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：

①Finish［i］=false;②Need［i,j］≤Work［j］；

若找到，執(zhí)行步驟(3)，否則，執(zhí)行步驟(4)。

(3)當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，

并釋放出分配給它的資源，故應(yīng)執(zhí)行：

Work［j］:=Work［i］+Allocation［i,j］;Finish［i］:=true;

gotostep2;(4)如果所有進(jìn)程的Finish［i］=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。86死鎖的檢測與解除1.資源分配圖(ResourceAllocationGraph)1)一組進(jìn)程結(jié)點(diǎn)P={p1,p2,…,pn}和一組資源結(jié)點(diǎn)R={r1,r2,…,rn}，N是節(jié)點(diǎn)的集合，N=PUR。即：N={p1,p2,…,pn}U{r1,r2,…,rn}。2)E是有向邊的集合，e∈E，e連接著P中的一個(gè)結(jié)點(diǎn)和R中的一個(gè)結(jié)點(diǎn)，e={pi,rj}是資源請求邊，由進(jìn)程pi指向資源rj，表示進(jìn)程pi請求一個(gè)單位的rj資源。e={rj,pi}是資源分配邊，由資源rj指向進(jìn)程pi,它表示把一個(gè)單位的資源rj分配給進(jìn)程pi。

87進(jìn)程：資源（方框內(nèi)的圓點(diǎn)表示資源個(gè)數(shù)）：進(jìn)程P正占用R類型的一個(gè)資源：

進(jìn)程P請求R類型的資源未果，被阻塞：P??PRR????88死鎖的檢測與解除P1P2R1R289死鎖的檢測與解除2.資源分配圖化簡P1P2R1R290資源分配圖示例死鎖一種類型的資源有多個(gè)91有無死鎖？死鎖無死鎖92死鎖的檢測與解除3.死鎖定理

如果資源分配圖是可完全化簡的，則系統(tǒng)是安全的，如果資源分配圖是不可化簡的，則系統(tǒng)處于不安全狀態(tài)，會(huì)發(fā)生死鎖。93死鎖的檢測

(1)可用資源向量Available，表示了m類資源中每一類資源的可用數(shù)目。

(2)把不占用資源的進(jìn)程(向量Allocation∶=0)記入L表中，即Li∪L。

(3)從進(jìn)程集合中找到一個(gè)Requesti≤Work的進(jìn)程，做如下處理：①將其資源分配圖簡化，釋放出資源，增加工作向量Work∶=Work+Allocationi。②將它記入L表中。

(4)若不能把所有進(jìn)程都記入L表中，便表明系統(tǒng)狀態(tài)S的資源分配圖是不可完全簡化的。該系統(tǒng)狀態(tài)將發(fā)生死鎖。94死鎖的檢測Work:=Available;L:={Li|Allocationi=0∩Requesti=0}forallLi∈LdobeginforallRequesti≤WorkdobeginWork:=Work+Allocationi;Li∪L;endenddeadlock:=?(L={p1,p2,…,pn});95死鎖解除

1）剝奪法恢復(fù)

將某些資源從其它進(jìn)程強(qiáng)占過來分配給另一些進(jìn)程。要求強(qiáng)占不影響原進(jìn)程恢復(fù)后的執(zhí)行。與資源的屬性有關(guān)，難實(shí)現(xiàn)。2）撤銷進(jìn)程

這是常用的解除死鎖的方法，從系統(tǒng)中撤消某些進(jìn)程，釋放資源以解除死鎖。要求保證系統(tǒng)的數(shù)據(jù)等的一致性，難于判斷。3）回退法恢復(fù)

系統(tǒng)執(zhí)行過程中設(shè)置若干斷點(diǎn)，并保存現(xiàn)場。采用回滾方式釋放資源以解除死鎖。要求保護(hù)的現(xiàn)場不能頻繁覆蓋。963.4

管程1.管程的定義

管程由三部分組成：

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

②對該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程；

③對局