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

進(jìn)程同步機(jī)制及應(yīng)用

利用硬件方法解決進(jìn)程互斥問(wèn)題

利用軟件方法解決進(jìn)程互斥問(wèn)題

利用鎖機(jī)制解決進(jìn)程互斥問(wèn)題

利用信號(hào)量機(jī)制解決進(jìn)程同步與互斥問(wèn)題進(jìn)程同步機(jī)制及應(yīng)用

禁止中斷

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

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

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

booleanold;

old=*lock;*lock=TRUE;

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

;//donothing臨界區(qū)

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

3.4進(jìn)程同步3.4.2進(jìn)程同步機(jī)制及應(yīng)用1.利用硬件方法解決進(jìn)程互斥問(wèn)題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ū);}違背了讓權(quán)等待原則利用swap指令實(shí)現(xiàn)互斥：交換兩個(gè)字的內(nèi)容

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

臨界區(qū)turn=1;

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

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

算法2：兩個(gè)進(jìn)程P0,P1共享某臨界資源：設(shè)立一個(gè)標(biāo)志數(shù)組flag[2]：描述進(jìn)程是否已在臨界區(qū)，初值均為0(FALSE)，表示進(jìn)程都不在臨界區(qū)。違背了忙則等待、讓權(quán)等待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進(jìn)程同步3.4.2進(jìn)程同步機(jī)制及應(yīng)用2.利用軟件方法實(shí)現(xiàn)互斥這個(gè)算法是否遵循了同步機(jī)制的4條準(zhǔn)則？如果沒(méi)有，違背了哪些準(zhǔn)則？3.4.2進(jìn)程同步機(jī)制及應(yīng)用2.利用軟件算法實(shí)現(xiàn)互斥：

算法3：Peterson算法，兩個(gè)進(jìn)程P0,P1共享某臨界資源

設(shè)立一個(gè)標(biāo)志數(shù)組flag[2]：描述進(jìn)程是否希望進(jìn)入臨界區(qū)，初值均為0(FALSE)，表示進(jìn)程都不希望進(jìn)入臨界區(qū)。intturn=0,表示首先輪到P0進(jìn)入臨界區(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進(jìn)程同步違背了讓權(quán)等待原則這個(gè)算法是否遵循了同步機(jī)制的4條準(zhǔn)則？如果沒(méi)有，違背了哪些準(zhǔn)則？如何實(shí)現(xiàn)n個(gè)進(jìn)程間的互斥呢？3.4.2進(jìn)程同步機(jī)制及應(yīng)用2.利用軟件算法實(shí)現(xiàn)互斥：

算法4：面包店算法

由美國(guó)數(shù)學(xué)家LeslieLamport提出

面包店排隊(duì)原則：按所取號(hào)碼由小到大原則排隊(duì)；

號(hào)碼相同時(shí)，按顧客名字的字典順序排隊(duì)。

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

while(true){

choosing[i]=True;//pi正在取號(hào)

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

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)));//首先是取得小號(hào)者優(yōu)先；當(dāng)多個(gè)進(jìn)程取到同號(hào)時(shí)，保證編號(hào)小的進(jìn)程優(yōu)先進(jìn)入臨界區(qū)

}

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

剩余區(qū)}}

算法4：面包店算法3.4.2進(jìn)程同步機(jī)制及應(yīng)用

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

算法5：兩個(gè)進(jìn)程P0,P1共享某臨界資源：設(shè)立一個(gè)標(biāo)志數(shù)組flag[2]：描述進(jìn)程是否希望進(jìn)入臨界區(qū)，初值均為0(FALSE)，表示進(jìn)程都不希望進(jìn)入臨界區(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進(jìn)程同步這個(gè)算法是否遵循了同步機(jī)制的4條準(zhǔn)則？如果沒(méi)有，違背了哪些準(zhǔn)則？違背了空閑讓進(jìn)、有限等待、讓權(quán)等待什么是原語(yǔ)？3.4.2進(jìn)程同步機(jī)制及應(yīng)用3.利用鎖機(jī)制實(shí)現(xiàn)互斥什么是鎖

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

lock()

{test：if(w為1)gototest；

elsew=1；}∕*上鎖*∕

開(kāi)鎖原語(yǔ)

unlock()

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

臨界區(qū)

unlock(w)

剩余區(qū)}違背了讓權(quán)等待原則3.4.2進(jìn)程同步機(jī)制及應(yīng)用3.利用鎖機(jī)制實(shí)現(xiàn)互斥3.4進(jìn)程同步3.4.2進(jìn)程同步機(jī)制及應(yīng)用4.信號(hào)量機(jī)制

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

整形信號(hào)量機(jī)制：

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

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

記錄型信號(hào)量

3.4進(jìn)程同步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)中是否有其他進(jìn)程因?yàn)樯暾?qǐng)不到信號(hào)量S所代表的臨界資源而在阻塞等待呢？3.4.2進(jìn)程同步機(jī)制及應(yīng)用4.信號(hào)量機(jī)制

信號(hào)量集機(jī)制：一次可申請(qǐng)多類資源；每類資源可申請(qǐng)多個(gè)3.4進(jìn)程同步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{

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

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

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

4.信號(hào)量機(jī)制

利用信號(hào)量機(jī)制實(shí)現(xiàn)互斥：為臨界資源設(shè)置一個(gè)互斥信號(hào)量mutex，初值為1：

semaphore

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

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

pb());}

pa(){…wait(mutex)；csa

；signal(mutex)；

…}

pb(){…wait(mutex)；csb

；signal(mutex)；

…}

利用信號(hào)量機(jī)制實(shí)現(xiàn)互斥：

例1：兩個(gè)進(jìn)程共享一臺(tái)打印機(jī)

semaphoremutex;main(){mutex=1；

parbegin(pa(),

pb();)}

pa(){…wait(mutex)；csa

；signal(mutex)；…

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

…

}

4.信號(hào)量機(jī)制mutex=0mutex=-1Pb等待mutex=0喚醒Pbmutex=1打印機(jī)空閑3.4.2進(jìn)程同步機(jī)制及應(yīng)用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個(gè)售票處同時(shí)運(yùn)行下面程序段進(jìn)行售票parbeginprogrampi{…R=x[k];/*現(xiàn)有票數(shù)*/

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

x[k]=R;

輸出一張機(jī)票；

}

else{顯示“票已售完”；

}}4.信號(hào)量機(jī)制

利用信號(hào)量機(jī)制實(shí)現(xiàn)互斥

semaphoremutex={1,NULL};這個(gè)問(wèn)題怎么解決呢？

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

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

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

}

else{

顯示“票已售完”；

}}

利用信號(hào)量機(jī)制實(shí)現(xiàn)互斥例2：民航售票系統(tǒng)，n個(gè)售票處同時(shí)運(yùn)行下面程序段進(jìn)行售票

算法1：這樣實(shí)現(xiàn)可能會(huì)出現(xiàn)什么問(wèn)題？

semaphoremutex={1,NULL};

parbeginprogrampi{………wait(mutex)；

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

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

}

else{signal(mutex)；

顯示“票已售完”；

}}例2：民航售票系統(tǒng)，n個(gè)售票處同時(shí)運(yùn)行下面程序段進(jìn)行售票

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

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

進(jìn)超市內(nèi)選購(gòu)商品；wait（mutex2）；

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

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

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

利用信號(hào)量機(jī)制實(shí)現(xiàn)互斥實(shí)現(xiàn)進(jìn)程間相互合作的前驅(qū)后繼關(guān)系

思路描述：為一個(gè)同步關(guān)系設(shè)置一個(gè)同步信號(hào)量S，其初值為0：semaphore

S=0

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

3.4進(jìn)程同步3.4.2進(jìn)程同步機(jī)制及應(yīng)用

4.信號(hào)量機(jī)制

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

semaphoreS；

main(){

S=0；

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

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

}

pb(){

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

}

3.4進(jìn)程同步3.4.2進(jìn)程同步機(jī)制及應(yīng)用

4.信號(hào)量機(jī)制

利用信號(hào)量機(jī)制實(shí)現(xiàn)同步例1：

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

S2=0；

Parbegin(I(),

C(),P());

}I(){

完成輸入；signal(S1)；}

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

}

P()

{wait(S2)；完成打??；

}

3.4.2進(jìn)程同步機(jī)制及應(yīng)用4.信號(hào)量機(jī)制

利用信號(hào)量機(jī)制實(shí)現(xiàn)同步wait(S){S->value--;if(S->value<0)thensleep(S->L);}Signal(S){S->value++;if(S->value≤0)thenwakeup(S->L);}重點(diǎn)分析S2節(jié)點(diǎn)與S6節(jié)點(diǎn)的算法，為什么是這樣寫(xiě)的？例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進(jìn)程同步機(jī)制及應(yīng)用4.信號(hào)量機(jī)制

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

program司機(jī){啟動(dòng)車輛;正常行車；

到站停車；}program售票員{關(guān)閉車門(mén);售票

打開(kāi)車門(mén);}

分析：同步關(guān)系：（1）售票員關(guān)閉車門(mén)→司機(jī)啟動(dòng)車輛（2）司機(jī)到站停車→售票員打開(kāi)車門(mén)

信號(hào)量設(shè)置：semaphoredrive_sem={0,NULL};semaphoreconductor_sem={0,NULL};這個(gè)問(wèn)題中有哪些前驅(qū)后繼關(guān)系？3.4.2進(jìn)程同步機(jī)制及應(yīng)用4.信號(hào)量機(jī)制

利用信號(hào)量機(jī)制實(shí)現(xiàn)同步例3算法實(shí)現(xiàn)：

利用信號(hào)量機(jī)制實(shí)現(xiàn)同步semaphoredrive_sem={0,NULL};關(guān)閉車門(mén)→啟動(dòng)車輛semaphoreconductor_sem={0,NULL};到站停車→打開(kāi)車門(mén)program司機(jī){while(1){

wait(drive_sem)；等待關(guān)門(mén)

啟動(dòng)車輛;

正常行車；到站停車;

signal(conductor_sem)；

喚醒開(kāi)門(mén)}}

program售票員{while(1){關(guān)閉車門(mén);signal(drive_sem)；喚醒司機(jī)開(kāi)車售票；

wait(conductor_sem)；

等待停車打開(kāi)車門(mén);}}（1）確定進(jìn)程：包括進(jìn)程的數(shù)量