計算機操作系統(tǒng)（第二版）課件：進程同步機制及應用

進程同步機制及應用

利用硬件方法解決進程互斥問題

利用軟件方法解決進程互斥問題

利用鎖機制解決進程互斥問題

利用信號量機制解決進程同步與互斥問題進程同步機制及應用

禁止中斷

3.4進程同步3.4.2進程同步機制及應用1.利用硬件方法解決進程互斥問題禁止中斷臨界區(qū)開放中斷剩余區(qū)缺點：可能增加系統(tǒng)風險只能用于單處理機系統(tǒng)CPU在兩個進程之間切換必須在中斷處理協(xié)助下才能實現(xiàn)為什么多處理機系統(tǒng)中這個方法不能實現(xiàn)互斥？openEuler中斷控制arch_local_irq_disable()arch_local_irq_enable()arch/arm64/include/asm/irqflags.h

利用TSL指令實現(xiàn)互斥

檢測并上鎖指令3.4進程同步3.4.2進程同步機制及應用1.利用硬件方法解決進程互斥問題booleanTSL(boolean*lock){

booleanold;

old=*lock;*lock=TRUE;

returnold;}booleanlock=FALSE；Pi：{while(TSL(&lock))

;//donothing臨界區(qū)

lock=FALSE;剩余區(qū);}違背了讓權等待原則利用swap指令實現(xiàn)互斥：交換兩個字的內(nèi)容

3.4進程同步3.4.2進程同步機制及應用1.利用硬件方法解決進程互斥問題voidSwap(boolean*a,boolean*b){

booleantemp;

temp=*a;*a=*b;*b=temp;}booleanlock=FALSE；Pi：{booleankey=TRUE;

while(key==TRUE)

Swap(&lock,&key)；臨界區(qū)

lock=FALSE;剩余區(qū);}違背了讓權等待原則利用swap指令實現(xiàn)互斥：交換兩個字的內(nèi)容

3.4進程同步3.4.2進程同步機制及應用1.利用硬件方法解決進程互斥問題3.4進程同步3.4.2進程同步機制及應用2.利用軟件方法實現(xiàn)互斥算法1：兩個進程P0,P1共享某臨界資源：需要保證互斥設立一個公用整型變量turn，描述允許進入臨界區(qū)的進程標識，假設初始化turn=0，表示首先輪到P0訪問臨界資源P0的代碼：while(turn!=0);

臨界區(qū)turn=1;

剩余區(qū)P1的代碼：while(turn!=1);

臨界區(qū)turn=0;剩余區(qū)違背了空閑讓進、讓權等待

算法2：兩個進程P0,P1共享某臨界資源：設立一個標志數(shù)組flag[2]：描述進程是否已在臨界區(qū)，初值均為0(FALSE)，表示進程都不在臨界區(qū)。違背了忙則等待、讓權等待P0:while(flag[1]);flag[0]=1;

臨界區(qū)

flag[0]=0;

剩余區(qū)P1:while(flag[0]);flag[1]=1;

臨界區(qū)

flag[1]=0;

剩余區(qū)3.4進程同步3.4.2進程同步機制及應用2.利用軟件方法實現(xiàn)互斥這個算法是否遵循了同步機制的4條準則？如果沒有，違背了哪些準則？3.4.2進程同步機制及應用2.利用軟件算法實現(xiàn)互斥：

算法3：Peterson算法，兩個進程P0,P1共享某臨界資源

設立一個標志數(shù)組flag[2]：描述進程是否希望進入臨界區(qū)，初值均為0(FALSE)，表示進程都不希望進入臨界區(qū)。intturn=0,表示首先輪到P0進入臨界區(qū)。P0:

flag[0]=1;turn=1;while(flag[1]&&turn==1);臨界區(qū)

flag[0]=0;

剩余區(qū)P1:flag[1]=1;turn=0;while(flag[0]&&turn==0);臨界區(qū)

flag[1]=0;

剩余區(qū)3.4進程同步違背了讓權等待原則這個算法是否遵循了同步機制的4條準則？如果沒有，違背了哪些準則？如何實現(xiàn)n個進程間的互斥呢？3.4.2進程同步機制及應用2.利用軟件算法實現(xiàn)互斥：

算法4：面包店算法

由美國數(shù)學家LeslieLamport提出

面包店排隊原則：按所取號碼由小到大原則排隊；

號碼相同時，按顧客名字的字典順序排隊。

每個進程設置一個唯一的編號Pi（i=0‥n-1）booleanchoosing[n]：表示進程是否正在取號，初值為Falseintnumber[n]：記錄每個進程取到的號碼，初值為03.4進程同步voidPi()（i=0‥n-1）{

while(true){

choosing[i]=True;//pi正在取號

number[i]=1+max(Number[1],...,Number[N]);//Pi取到的號碼

choosing[i]=False;

for(j=0;j＜N;++j){

while(choosing[j]!=0);

while((number[j]!==0)&&

((number[j]＜number[i])||((number[j]==number[i])&&(j＜i)));//首先是取得小號者優(yōu)先；當多個進程取到同號時，保證編號小的進程優(yōu)先進入臨界區(qū)

}

臨界區(qū)number[i]=0;

剩余區(qū)}}

算法4：面包店算法3.4.2進程同步機制及應用

2.利用軟件方法實現(xiàn)互斥

算法5：兩個進程P0,P1共享某臨界資源：設立一個標志數(shù)組flag[2]：描述進程是否希望進入臨界區(qū)，初值均為0(FALSE)，表示進程都不希望進入臨界區(qū)P0:flag[0]=1;while(flag[1]);臨界區(qū)

flag[0]=0;

剩余區(qū)P1:flag[1]=1;while(flag[0]);臨界區(qū)

flag[1]=0;

剩余區(qū)3.4進程同步這個算法是否遵循了同步機制的4條準則？如果沒有，違背了哪些準則？違背了空閑讓進、有限等待、讓權等待什么是原語？3.4.2進程同步機制及應用3.利用鎖機制實現(xiàn)互斥什么是鎖

用變量w代表某種資源的狀態(tài)，w稱為“鎖”。加鎖原語和開鎖原語3.4進程同步加鎖原語

lock()

{test：if(w為1)gototest；

elsew=1；}∕*上鎖*∕

開鎖原語

unlock()

{w=0；}∕*開鎖*∕使用方法intw=0;Pi(){while(True){lock(w);

臨界區(qū)

unlock(w)

剩余區(qū)}違背了讓權等待原則3.4.2進程同步機制及應用3.利用鎖機制實現(xiàn)互斥3.4進程同步3.4.2進程同步機制及應用4.信號量機制

整形信號量機制：3.4進程同步荷蘭計算機科學家Dijkstra提出的。你還在哪里學習過Dijkstra的理論或觀點呢？你還了解Dijkstra的哪些事跡呢？圖靈獎計算機科學教育杰出貢獻獎ACMPODC最具影響力論文獎結(jié)構(gòu)程序之父3.4.2進程同步機制及應用4.信號量機制

整形信號量機制：

初始化操作：非負整數(shù)P原語操作：down()或wait()V原語操作：up()或signal()3.4進程同步wait(S){while(S≤0);//donothingS--;//S值減1}signal(S){S++;//S值加1}違背了“讓權等待”準則是否遵循了4個準則？3.4.2進程同步機制及應用4.信號量機制

記錄型信號量機制：3.4進程同步typedefstruct{intvalue;/*信號量的值*/PCB*L;/*進程等待隊列隊首指針*/}semaphore;value:初始化為一個非負整數(shù)值，表示空閑資源總數(shù)－－若為非負值表示當前的空閑資源數(shù)，若為負值其絕對值表示當前等待臨界資源的進程個數(shù)。L：初值為空3.4.2進程同步機制及應用4.信號量機制：

記錄型信號量

3.4進程同步wait(S){S->value--;if(S->value<0)thensleep(S->L);}

signal(S){S->value++;if(S->value≤0)thenwakeup(S->L);}semaphore*S;如果現(xiàn)在value的值小于0，那么在執(zhí)行減1操作前，value的最大值只可能是多少？如果用value的值表示可用資源數(shù)量，那么現(xiàn)在系統(tǒng)中是否還有空閑資源供分配呢？如果現(xiàn)在value的值小于等于0，那么在執(zhí)行加1操作前，value的最大值只可能是多少？那么現(xiàn)在系統(tǒng)中是否有其他進程因為申請不到信號量S所代表的臨界資源而在阻塞等待呢？3.4.2進程同步機制及應用4.信號量機制

信號量集機制：一次可申請多類資源；每類資源可申請多個3.4進程同步Swait(S1,t1,d1,S2,t2,d2,…,Sn,tn,dn){if(S1>=t1&&…&&Sn>=tn){for(i=1;i<=n;i++){Si=Si–di;}}else{

將當前進程阻塞到第一個Si<ti的信號量Si的阻塞隊列中；}}使用時，有一個隱含條件：ti≥di3.4進程同步Ssignal(S1,d1,S2,d2,…,Sn,dn){for(i=1;i<=n;i++){Si=Si+di;

喚醒所有因S1～Sn而阻塞的進程，插入就緒隊列；}}Swait(S，d，d)：表示每次申請d個資源Swait(S，1，1)：表示記錄型信號量Swait(S，1，0)：可作為一個可控開關Swait(S1,1,1,S2,1,1,…,Sn,1,1)：表示AND型信號量這個可以用在什么場合下呢？能實現(xiàn)什么功能呢？3.4.2進程同步機制及應用4.信號量機制

信號量集機制：一次可申請多類資源；每類資源可申請多個對信號量X執(zhí)行P操作時，若（）則進程進入等待狀態(tài)X-1＜0X-1≤0X-1＞0X-1≥0ABCD提交單選題10分若信號量S的初值為2，當前值為-2，則表示有（）等待進程。0234ABCD提交單選題10分3.4.2進程同步機制及應用

4.信號量機制

利用信號量機制實現(xiàn)互斥：為臨界資源設置一個互斥信號量mutex，初值為1：

semaphore

mutex=1在每個進程中將臨界區(qū)代碼置于wait(mutex)和signal(mutex)原語之間：wait（mutex）臨界區(qū)signal（mutex）剩余區(qū)3.4進程同步必須成對出現(xiàn)4.信號量機制

利用信號量機制實現(xiàn)進程互斥算法描述：3.4.2進程同步機制及應用semaphoremutex；voidmain(){mutex=1；∕*互斥信號量*∕parbegin(pa(),

pb());}

pa(){…wait(mutex)；csa

；signal(mutex)；

…}

pb(){…wait(mutex)；csb

；signal(mutex)；

…}

利用信號量機制實現(xiàn)互斥：

例1：兩個進程共享一臺打印機

semaphoremutex;main(){mutex=1；

parbegin(pa(),

pb();)}

pa(){…wait(mutex)；csa

；signal(mutex)；…

}pb(){…wait(mutex)；csb；signal(mutex)；

…

}

4.信號量機制mutex=0mutex=-1Pb等待mutex=0喚醒Pbmutex=1打印機空閑3.4.2進程同步機制及應用wait(S){S->value--;if(S->value<0)thensleep(S->L);}Signal(S){S->value++;if(S->value≤0)thenwakeup(S->L);}例2：民航售票系統(tǒng)，n個售票處同時運行下面程序段進行售票parbeginprogrampi{…R=x[k];/*現(xiàn)有票數(shù)*/

if(R>=1){R--;

x[k]=R;

輸出一張機票；

}

else{顯示“票已售完”；

}}4.信號量機制

利用信號量機制實現(xiàn)互斥

semaphoremutex={1,NULL};這個問題怎么解決呢？

semaphoremutex={1,NULL};parbeginprogrampi{…wait(mutex)；

R=x[k];/*現(xiàn)有票數(shù)*/

if(R>=1){R--;x[k]=R;signal(mutex)；輸出一張機票；

}

else{

顯示“票已售完”；

}}

利用信號量機制實現(xiàn)互斥例2：民航售票系統(tǒng)，n個售票處同時運行下面程序段進行售票

算法1：這樣實現(xiàn)可能會出現(xiàn)什么問題？

semaphoremutex={1,NULL};

parbeginprogrampi{………wait(mutex)；

R=x[k];/*現(xiàn)有票數(shù)*/

if(R>=1){R--;x[k]=R;signal(mutex)；輸出一張機票；

}

else{signal(mutex)；

顯示“票已售完”；

}}例2：民航售票系統(tǒng)，n個售票處同時運行下面程序段進行售票

算法2：利用信號量機制實現(xiàn)互斥小組討論：某超級市場，可容納多人同時購物。入口處有200個籃子，每個購物者可拿一只籃子入內(nèi)購物，無籃子時不能進入超市購物。出口處結(jié)帳，并歸還籃子（出、入口禁止多人同時通過）。出入口不在同一處。試用信號量機制實現(xiàn)購物者的同步算法。4.信號量機制簡答思路：①所用信號量設置如下：1）資源信號量basket，初值為2002）互斥信號量mutex1，初值為1，用以保證同時只能有一個購物者進程進入入口拿起籃子3）互斥信號量mutex2，初值為1，用以保證同時只能有一個購物者進程進入出口結(jié)賬歸還籃子

利用信號量機制實現(xiàn)互斥Pi(){wait(basket);wait（mutex1）；從入口處進超市，并取一只籃子signal（mutex1）；

進超市內(nèi)選購商品；wait（mutex2）；

到出口結(jié)帳，并歸還籃子；signal（mutex2）；

signal(basket);從出口離開超市；

}小組討論分析思路semaphorebasket，mutex1，mutex2voidmain(){mutex1=mutex2=1，basket=200parbegin(pi());}

利用信號量機制實現(xiàn)互斥實現(xiàn)進程間相互合作的前驅(qū)后繼關系

思路描述：為一個同步關系設置一個同步信號量S，其初值為0：semaphore

S=0

——表示消息或令牌前驅(qū)進程完成操作后執(zhí)行signal(S)：表示發(fā)送消息或令牌后繼進程開始操作前執(zhí)行wait(S)：表示所等待消息獲令牌到達

3.4進程同步3.4.2進程同步機制及應用

4.信號量機制

利用信號量機制實現(xiàn)同步算法描述：Pa→Pb

semaphoreS；

main(){

S=0；

parbegin(pa(),pb())；}pa(){

完成前驅(qū)工作；signal(S)；

}

pb(){

wait(S)；執(zhí)行后繼工作

}

3.4進程同步3.4.2進程同步機制及應用

4.信號量機制

利用信號量機制實現(xiàn)同步例1：

I→C→PsemaphoreS1；semaphoreS2;main(){S1=0；

S2=0；

Parbegin(I(),

C(),P());

}I(){

完成輸入；signal(S1)；}

C(){wait(S1)；完成計算；signal(S2)；

}

P()

{wait(S2)；完成打?。?/p>

}

3.4.2進程同步機制及應用4.信號量機制

利用信號量機制實現(xiàn)同步wait(S){S->value--;if(S->value<0)thensleep(S->L);}Signal(S){S->value++;if(S->value≤0)thenwakeup(S->L);}重點分析S2節(jié)點與S6節(jié)點的算法，為什么是這樣寫的？例2：前驅(qū)圖a,b,c,d,e,f,g:semaphore=0,0,0,0,0,0,0Parbegin(s1,s2,s3,s4,s5,s6);s1:{s1;signal(a);signal(b);}s2:{wait(a);s2;signal(c);signal(d);}s3:{wait(b);s3;signal(e);}

s4:{wait(c);s4;signal(f);}s5:{wait(d);s5;signal(g);}s6:{wait(e);wait(f);wait(g);s6;}

3.4.2進程同步機制及應用4.信號量機制

利用信號量機制實現(xiàn)同步abcdefgS1S2S3S4S5S6例3：一輛公共汽車上，司機和售票員進程的同步

program司機{啟動車輛;正常行車；

到站停車；}program售票員{關閉車門;售票

打開車門;}

分析：同步關系：（1）售票員關閉車門→司機啟動車輛（2）司機到站停車→售票員打開車門

信號量設置：semaphoredrive_sem={0,NULL};semaphoreconductor_sem={0,NULL};這個問題中有哪些前驅(qū)后繼關系？3.4.2進程同步機制及應用4.信號量機制

利用信號量機制實現(xiàn)同步例3算法實現(xiàn)：

利用信號量機制實現(xiàn)同步semaphoredrive_sem={0,NULL};關閉車門→啟動車輛semaphoreconductor_sem={0,NULL};到站停車→打開車門program司機{while(1){

wait(drive_sem)；等待關門

啟動車輛;

正常行車；到站停車;

signal(conductor_sem)；

喚醒開門}}

program售票員{while(1){關閉車門;signal(drive_sem)；喚醒司機開車售票；

wait(conductor_sem)；

等待停車打開車門;}}（1）確定進程：包括進程的數(shù)量