《計算機操作系統(tǒng) 》課件-3.4進程同步

3.4進程同步本節(jié)主要內(nèi)容：進程同步的基本概念進程同步機制及應用經(jīng)典進程同步問題管程機制Linux同步機制解析3.4進程同步3.4.1進程同步的基本概念

并發(fā)進程間的制約關系

進程同步與互斥的概念

臨界資源、臨界區(qū)的概念

同步機制應遵循的原則3.4進程同步3.4.1進程同步的基本概念1.并發(fā)進程間的間接制約關系與進程互斥：

間接制約關系：相互競爭資源

臨界資源

一次僅允許一個進程使用的資源稱為臨界資源。硬件：如輸入機、打印機、磁帶機等軟件：如公用變量、數(shù)據(jù)、表格、隊列等

例1：兩個進程共享一個變量x，設x的初值為10P1和P2兩個進程都對共享變量x執(zhí)行加1的操作：p1：r1:=x；r1:=r1+1；x:=r1

；p2：r2:=x；r2:=r2+1；x:=r2

；33

兩種可能的執(zhí)行次序：x=10A次序：

p1：r1:=x；r1:=r1+1；x:=r1；

p2：r2:=x；r2:=r2+1；x:=r2

；執(zhí)行結(jié)果：

x=11B次序：

p1：r1:=x；r1:=r1+1；x:=r1

；

p2：r2:=x；r2:=r2+1；x:=r2

；執(zhí)行結(jié)果：

x=121、并發(fā)進程間的間接制約關系與進程互斥

臨界資源共享變量的修改沖突

例2：民航售票系統(tǒng)，n個售票處

/*ProcessPi,i=1,2,...,n*/…../*按訂票要求找到數(shù)據(jù)庫中的共享數(shù)據(jù)x[k]*//*x[k]存放某月某日某次航班的現(xiàn)有票數(shù)*/R=x[k];/*現(xiàn)有票數(shù)*/

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

x[k]=R;

輸出一張機票；

}else

顯示“票已售完”；互斥：對某個臨界資源，一個進程正在使用它，另外一個想用它的進程就必須等待，而不能同時使用；

x

:=x+1;

進程P1進程P2

x

:=x+1;

3.4.1進程同步的概念1.并發(fā)進程間的間接制約關系與進程互斥

臨界區(qū)：進程中訪問臨界資源的一段代碼。

臨界區(qū)的互斥訪問過程：

x

:=x+1;

csa{進程P1進程P2

x

:=x+1;

csb{entrysection進入?yún)^(qū)exitsection退出區(qū)

criticalsection(臨界區(qū)）

remaindersection（剩余區(qū)）進程代碼3.4.1進程同步的基本概念1、并發(fā)進程間的間接制約關系與進程互斥：3.4進程同步3.4.1進程同步的基本概念1.并發(fā)進程間的間接制約關系與進程互斥：同步機制應遵循的原則空閑讓進：其他進程均不處于臨界區(qū)；忙則等待：已有進程處于其臨界區(qū)；

有限等待：等待進入臨界區(qū)的進程不能"死等"；

讓權等待：不能進入臨界區(qū)的進程，應釋放CPU（如轉(zhuǎn)換到阻塞狀態(tài)）3.4.1進程同步的基本概念2.并發(fā)進程間的直接制約關系與進程同步：相互協(xié)作，保證先后順序例1：病人就診：醫(yī)生看病活動：初步診斷開出化驗單；

依據(jù)化驗結(jié)果繼續(xù)診?。换瀱T化驗活動：進行化驗；

開出化驗結(jié)果；3.4進程同步例2：共享緩沖區(qū)的計算進程與打印進程的相互協(xié)作

計算進程cp和打印進程op公用一個單緩沖

單緩沖opcpABCDABCD3.4進程同步3.4.1進程同步的基本概念2.并發(fā)進程間的直接制約關系與進程同步：相互協(xié)作進程同步概念：并發(fā)進程在一些關鍵點上可能需要互相等待或互通消息，這種相互制約的等待或互通消息稱為進程同步。

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

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

禁止中斷，TSL指令，swap指令

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

不正確的算法，Peterson算法，面包店算法

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

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

整形信號量、記錄型信號量、信號量集機制

禁止中斷

3.4進程同步3.4.2進程同步機制及應用1.利用硬件方法解決進程互斥問題禁止中斷臨界區(qū)開放中斷剩余區(qū)缺點：可能增加系統(tǒng)風險只能用于單處理機系統(tǒng)

利用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ū);}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)互斥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進程同步如何實現(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)先進入臨界區(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進程同步分組討論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進程同步機制及應用4.信號量機制

整形信號量機制：

初始化操作：非負整數(shù)P原語操作：down()或wait()V原語操作：up()或signal()3.4進程同步wait(S){while(S≤0);//donothingS--;//S值減1}signal(S){S++;//S值加1}違背了“讓權等待”準則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;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的阻塞隊列中；}}3.4.2進程同步機制及應用4.信號量機制

信號量集機制：一次可申請多類資源；每類資源可申請多個3.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型信號量二.進程同步機制及應用

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：

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

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

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

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

從出口離開超市；

}②算法描述：

利用信號量機制實現(xiàn)互斥semaphoremutex1，mutex2；；∕*互斥信號量*∕voidmain(){mutex1=mutex2=1parbegin(pi());}

實現(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);}例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};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ù)量、進程的工作內(nèi)容。（2）確定進程同步互斥關系：根據(jù)進程間是競爭臨界資源還是相互合作處理上的前后關系，來確定進程間是互斥還是同步。（3）確定信號量：根據(jù)進程間的同步互斥關系確定信號量個數(shù)、含義、初始值，各進程需要對信號量進行的wait()/signal()操作。（4）用類程序語言描述算法。3.4進程同步3.4.2進程同步機制及應用

4.信號量機制

利用信號量機制解決進程同步與互斥問題的步驟：課堂分組討論：計算進程cp和打印進程op公用一個單緩沖（一次只能放一個數(shù)據(jù)），cp不斷的計算并將結(jié)果放入單緩沖中，op則不斷從單緩沖中取出結(jié)果并打印。為了完成正確的計算與打印，試用信號量機制實現(xiàn)這兩個進程的同步。

單緩沖區(qū)bufopcp3.4進程同步3.4.2進程同步機制及應用

4.信號量機制55程序main(){intsa=0；∕*表示buf中有無信息*∕

intsb=1；∕*表示buf中有無空位置*∕

parbegin(cp(),iop())；}cp()op(){

{while(計算未完成)

while(打印工作未完成){

{

得到一個計算結(jié)果；

wait(sa)；wait(sb)；

從緩沖區(qū)中取一數(shù)；將數(shù)送到緩沖區(qū)中；

signal(sb)；signal(sa)；從打印機上輸出；

}

}}

}

單緩沖區(qū)bufiopcp生產(chǎn)者-消費者問題哲學家進餐問題讀者-寫者問題理發(fā)師問題3.4進程同步3.4.3經(jīng)典進程同步問題1.生產(chǎn)者－消費者問題(theproducer-consumerproblem)問題描述：若干進程通過有限的共享緩沖區(qū)交換數(shù)據(jù)。其中，"生產(chǎn)者"進程不斷寫入，而"消費者"進程不斷讀出；共享緩沖區(qū)共有K個；任何時刻只能有一個進程可對共享緩沖區(qū)進行操作。0123…4K-13.4進程同步inout3.4.3經(jīng)典進程同步問題1.生產(chǎn)者－消費者問題分析：確定進程：進程數(shù)量及工作內(nèi)容；確定進程間的關系：

互斥：多個進程間互斥使用同一個緩沖池；

同步：當緩沖池空時，消費者必須阻塞等待；當緩沖池滿時，生產(chǎn)者必須阻塞等待。設置信號量：Mutex：用于訪問緩沖池時的互斥，初值是1Full：“滿緩沖”數(shù)目，初值為0；Empty：“空緩沖"數(shù)目，初值為K。full+empty=K3.4.3經(jīng)典進程同步問題＃defineK100

＃defineMAXLEN80typedefstruct{intnum;chararray[MAXLEN];}Message;semaphoremutex;semaphoreempty;

semaphorefull;Messagebuffers[K];

intin,out;

1.生產(chǎn)者－消費者問題算法描述：三.經(jīng)典進程同步問題

voidmain(){mutex={1,NULL};empty={K,NULL};

full={0,NULL};

Messagebuffers[K];in=0;out=0;

parbegin(produceri,consumerj)}

生產(chǎn)者－消費者問題programproduceri{Messagep_puf;while(1){produceamessageinp_buf;

wait(empty)；

wait(mutex)；buffers[in]=p_bufin=(in+1)%K;

signal(mutex)；

signal(full)；}}3.4.3經(jīng)典進程同步問題1.生產(chǎn)者－消費者問題programconsumerj{

Messagec_buf;while(1){

wait(full)；

wait(mutex)；

c_buf=buffers[out]；

out=(out+1)%K;

signal(mutex)；

signal(empty)；

consumethemessageinc_buf;}

}三.經(jīng)典進程同步問題1.生產(chǎn)者－消費者問題

如果將消費者的兩個wait()操作對調(diào)？生產(chǎn)者i

消費者j生產(chǎn)出一產(chǎn)品；

wait（full）；wait（empty

）；

wait（mutex）；wait（mutex

）

；從緩沖區(qū)取出一產(chǎn)品；將該產(chǎn)品放入緩沖區(qū)；

signal（mutex）；signal（mutex

）；

signal（empty）；

signal（full

）

；消費該產(chǎn)品；狀態(tài)：mutex=1,full=0,empty=n

先執(zhí)行消費者進程wait（mutex）;wait（full）；如果將消費者的兩個signal()操作對調(diào)？生產(chǎn)者i

消費者j生產(chǎn)出一產(chǎn)品；wait（full）；wait（empty）；wait（mutex）；wait（mutex）；從緩沖區(qū)取出一產(chǎn)品；將該產(chǎn)品放入緩沖區(qū)；signal（mutex）；signal（mutex）；signal（empty）；

signal（full）；消費該產(chǎn)品；signal(empty);Signal(mutex);1.生產(chǎn)者－消費者問題思考：請舉出一個計算機系統(tǒng)中可以用生產(chǎn)者-消費者問題描述的實際例子2.哲學家進餐問題問題描述：有五個哲學家坐在一張圓桌旁，在圓桌上有五個盤子有五只筷子，他們的生活方式就是交替地進行思考和進餐。平時，一個哲學家進行思考，饑餓時取其左右兩只筷子，只有拿到這兩只筷子時才能進餐；進餐完畢，放下筷子繼續(xù)思考?？?筷1筷4筷2筷3制約關系：只有拿到兩只筷子時,哲學家才能吃飯。

如果筷子已被別人拿走,則必須等別人吃完之后才能拿到筷子。3.4.3經(jīng)典進程同步問題

programphilosopher（i）{thinking…

wait(chopstick[i])；

wait(chopstick[(i+1)mod5]);eating;

signal(chopstick[i])；

signal(chopstick[(i+1)mod5]);

}

2.哲學家進餐問題算法描述1：

semaphorechopstick[0…4];筷0筷1筷4筷2筷3voidmain(){chopstick[0…4]={1,NULL};parbegin(philosopher(i));}programphilosopher(i){wait(sm)；

wait(chopstick[i])；

wait(chopstick[(i+1)mod5]);eating;

signal(chopstick[i])；

signal(chopstick[(i+1)mod5]);

signal(sm)；}算法描述2：筷筷筷筷筷semaphorechopstick[0…4];

semaphoresm;voidmain(){chopstick[0…4]={1,NULL};

sm={4,NULL};parbegin(philosopher(i));}2.哲學家進餐問題思考：請舉出一個計算機系統(tǒng)中可以用哲學家進程問題描述的實際例子3.讀者-寫者問題(thereaders-writersproblem)問題描述：

有多個讀者進程和多個寫者進程共享一數(shù)據(jù)。要求多進程對共享數(shù)據(jù)進行讀寫操作時，任一時刻“寫者”最多只允許一個，而“讀者”則允許多個，即：當有寫者在寫數(shù)據(jù)時，其他寫者和讀者必須等待；

當有讀者在讀數(shù)據(jù)時，其他寫者必須等待；但其他讀者可以同時讀數(shù)據(jù)。

3.4進程同步3.4.3經(jīng)典進程同步問題3.讀者－寫者問題(thereaders-writersproblem)問題分析及信號量設置：信號量wmutex表示“允許寫”，寫者與其他進程互斥使用數(shù)據(jù)公共整形變量Readcount表示“正在讀”的讀者數(shù)信號量Rmutex：實現(xiàn)多個讀者對Readcount的互斥操作

wmutex:semaphore=1//讀者與寫者之間、寫者與寫者之間互斥使用共享數(shù)據(jù)readcount:int=0;//當前正在讀的讀者數(shù)量

rmutex:semaphore=1//多個讀者互斥使用readcount3.4.3經(jīng)典進程同步問題3.讀者－寫者問題算法描述：semaphorewmutex,rmutex;intreadcount;voidmain(){wmutex=1;rmutex=1;readcount=0;

parbegin(writeri,readerj);}voidwriteri{while(1){

writing…

}}wait(wmutex);signal(wmutex);voidreaderj{while(1){

wait(rmutex)ifreadcount=0thenwait

(wmutex);readcount++;

signal(rmutex);

reading…

wait

(rmutex);readcount--;ifreadcount=0thensignal(wmutex);

signal(rmutex);}}3.讀者－寫者問題讀者優(yōu)先的讀者-寫者算法：3.讀者－寫者問題共享數(shù)據(jù)R1W1R2R3寫者優(yōu)先的讀者-寫者算法：寫進程與其他所有進程互斥允許多個讀者同時讀

寫者優(yōu)先于讀者（一旦有寫者，則后續(xù)讀者必須等待；若同時有讀者和寫者在等待，喚醒時優(yōu)先考慮寫者）

semaphore

wmutex=1//讀者與寫者之間、寫者與寫者之間互斥使用共享數(shù)據(jù)SemaphoreS=1//當至少有一個寫者準備訪問共享數(shù)據(jù)時，它可使后續(xù)的讀者等待寫完成SemaphoreS2＝1//阻塞第二個以后的等待讀者intReadcount,writecount=0,0;//當前讀者數(shù)量、寫者數(shù)量Semaphoremutex1=1//多個讀者互斥使用readcountSemaphoremutex2=1//多個寫者互斥使用writecount算法描述：寫者優(yōu)先的讀者－寫者問題算法Reader(){while(1){

wait(S2);

wait(S);wait(mutex1)

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

signal(mutex1);signal(S);signal(S2);

reading…

wait(mutex1);

readcount--;

ifreadcount=0thensignal(wmutex);

signal(mutex1);

}}寫者優(yōu)先的讀者－寫者問題算法算法描述：voidwriter(){while(1)wait(mutex2);ifwritecount=0thenwait(S);writecount++;signal（mutex2）;wait(wmutex);writing…signal(wmutex);wait(mutex2);writecount--;ifwritecount=0thensignal(S);signal（mutex2）;}}寫者優(yōu)先的讀者－寫者問題算法5.理發(fā)師問題問題描述：

理發(fā)店里有一位理發(fā)師、一把理發(fā)椅和n把供等候理發(fā)的顧客坐的椅子（等候椅）。如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺；第一個顧客到來時，他必須叫醒理發(fā)師；若理發(fā)師正在理發(fā)時又有顧客到達，則如果有空等候椅，顧客就坐下來等待，如果滿座了就離開理發(fā)店。理發(fā)店問題經(jīng)常被用來模擬各種排隊情形。3.4進程同步3.4.3經(jīng)典進程同步問題5.理發(fā)師問題算法描述：intwaiting;semaphorecust_ready,finished,mutex,chair;voidmain(){waiting=0;cust_ready=finished=0;mutex=chair=1;

parbegin(barber,customer-i);}

3.4.3經(jīng)典進程同步問題Cust_ready:理發(fā)椅上的顧客數(shù)Finished:顧客是否已完成理發(fā)mutex:互斥訪問waitingchair:空閑的理發(fā)椅數(shù)量表示坐在等候椅上的顧客數(shù)5.理發(fā)師問題voidbarber(){do{wait(cust_ready);cut_hair;signal（finished);}while(1);}3.4.3經(jīng)典進程同步問題voidcustomer-i(){wait(mutex)；if(waiting<n){waiting=waiting+1;signal(mutex);}}else{signal(mutex)；

離開理發(fā)店；return;}wait(chair);sit_in_chair;wait(mutex)；waiting=waiting-1;signal(mutex);signal(cust_ready);get-haircut;wait(finished);stand_from_chair;signal(chair);}例1：

桌上有個只能盛得下一個水果的空盤子。爸爸可向盤中放蘋果或桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定：當盤子空時，一次只能放入一個水果供吃者取用。試用信號量的PV操作實現(xiàn)爸爸、兒子和女兒這三個循環(huán)進程之間的同步。

所用信號量設置如下：

Ⅰ）同步信號量empty，初值為1，表示盤子是空的，即兒子或女兒已把盤中的水果取走。

Ⅱ）同步信號量orange，初值為0，表示爸爸尚未把桔子放入盤中。

Ⅲ）同步信號量apple，初值為0，表示爸爸尚未把蘋果放入盤中。3.4進程同步3.4.3經(jīng)典進程同步問題

算法同步描述：

爸爸進程（P）：

兒子進程（C1）：

女兒進程（C2）：P（empty）；

P（orange）；

P（apple）；將水果放入盤中；

從盤中取出桔子；

從盤中取出蘋果；若放入的是桔子，

V（empty）；

V（empty）；則V（orange）；吃桔子；

吃蘋果；否則，V（apple）；3.4經(jīng)典進程同步問題：小組討論：桌子上有一個空盤子，最多允許存放兩只水果，但一次只能一個人操作盤子（往盤子中放水果或從盤子中取水果），爸爸可以向盤中放蘋果，媽媽向盤子中放橘子，女兒專門吃盤子中的蘋果，兒子專門吃盤子中的橘子。請用信號量實現(xiàn)他們之間的同步與互斥關系。S:semaphore=2;盤子開始可以放兩只水果Mutex:semaphore=1;互斥使用盤子S1:semaphore=0;是否有蘋果S2:semaphore=0;是否有橘子3.4經(jīng)典進程同步問題：ProcessFather:Begin:

L1:P(S);

P（mutex）

PutApple;

V(mutex);

V(S1)；

GOTOL1；

End；ProcessMother:Begin:L2:P(S);P（mutex）

PutOrange;

V(S2)；

V(mutex);

GOTOL2；End；ProcessSon:

Begin:

L3:P(S2);P（mutex）

GetOrange;V(mutex);

V(S)；

GOTOL1；

End；ProcessDaughter:Begin:L4:P(S1);P（mutex）GetApple;V(mutex);V(S)；GOTOL4；End；鎖機制、專用指令等存在“忙等”現(xiàn)象由用戶編寫同步控制代碼：加重了用戶負擔！各同步原語操作分散在用戶程序中，系統(tǒng)無法有效地控制和管理；

用戶編程時若使用wait()/signal()操作不當，后果嚴重（死鎖）基于以上情況，1971年DIjkstra提出了“秘書進程”思想。1973年Hansan和Hoare又將“秘書進程”思想發(fā)展為“管程”概念，把并發(fā)進程間的同步操作分別集中在相應的管程中。3.4進程同步3.4.4管程機制1.管程的引人：前述互斥手段的不足：一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一組操作，這組操作能同步進程和改變管程中的數(shù)據(jù)3.4.4管程機制2.管程的定義：管程組成：管程名字局部于管程的共享變量的說明；對該數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程；初始化局部變量的語句。局部數(shù)據(jù)條件變量過程1過程n出口變量初始化代碼管程入口等待調(diào)用進程隊列3.4.4管程機制2.管程的定義管程特性：信息隱蔽性

任一時刻，管程中只能有一個活躍進程3.條件變量每個獨立的條件變量是和進程需要等待的某種原因（或說條件）相聯(lián)系的，當定義一個條件變量時，系統(tǒng)就建立一個相應的等待隊列。關于條件變量的操作：C.wait:阻塞調(diào)用進程，并使管程可用；C.signal:喚醒相應條件變量上的等待進程。Java:wait(),notify()C#:monitor.wait(),monitor.pulse()3.條件變量引入條件變量后的一個可能問題：進程Q執(zhí)行C.wait()阻塞；進程P執(zhí)行C.signal()喚醒進程Q后，管程中有兩個活躍進程問題：解決方法：P等待，直到Q退出管程或等待另一個條件Q等待，直到P退出管程或等待另一個條件Hanson采用了折中的方法:規(guī)定C.signal()為過程體最后一個操作，當進程P執(zhí)行完畢后，P退出管程，另一個進程Q執(zhí)行。typePC=monitor in,out,count:int;

buffer[N]:item; notfull,notempty:condition; procedureput(item)

procedureget(item){

{if(count==N)then

if(count=0)then

notfull.wait();notempty.wait();buffer(in)=item;

nextc=buffer(out);in=(in+1)modN;out=(out+1)modN;count=count+1;

count=count-1;

notempty.signal();notfull.signal();}

}Beginin=out=count=0;end3.4.4管程機制5.利用管程解決生產(chǎn)者--消費者問題

PC管程定義：procedureproducer

procedureconsumer{

{while(true)

while(true){

{produceranitem;

PC.get(item);PC.put(item);

consumetheitem;}

}}

}

monitor.enter;PC.put(item);monitor.leave;3.4.4管程機制5.利用管程解決生產(chǎn)者--消費者問題生產(chǎn)者及消費者算法描述：3.4.4管程機制思考題：3.4進程同步3.4.5Linux同步機制解析內(nèi)核程序使用的同步機制原子操作

自旋鎖

讀-寫自旋鎖

內(nèi)核信號量

讀-寫信號量用戶程序使用的同步機制IPC信號量（system信號量）POSIX信號量

有名信號量，無名信號量原子整數(shù)操作：主要用于實現(xiàn)計數(shù)器

原子操作可以保證指令以原子的方式被執(zhí)行，兩個原子操作絕對不可能同時訪問同一個變量。

typedefstruct{

volatileintcounter; }atomic_t;3.4進程同步3.4.5Linux同步機制解析1.原子操作volatile提醒編譯器它所定義的變量隨時都有可能改變，因此編譯后的程序每次需要訪問該變量時，都會直接從變量地址中讀取數(shù)據(jù)，而不是從寄存器中。1.原子操作原子整數(shù)操作操作功能說明ATOMIC_INIT(i）聲明一個atomic_t變量，并初始化為iatomic_read(&v)返回v的值atomic_set(&v,i)把v置為iatomic_add(i,&v)把v增加iatomic_sub(i,&v)對v減iatomic_sub_and_test(i,&v)對v減i，如果結(jié)果為0則返回1；否則返回0atomic_inc(&v)對v加1atomic_dec(&v)對v減1atomic_dec_and_test(&v)對v減1，如果結(jié)果為0則返回1；否則返回0atomic_inc_and_test(&v)對v加1，如果結(jié)果為0則返回1；否則返回03.4.5Linux同步機制解析原子位操作：

include/asm-x86/bitops_32.h針對“位”這一級數(shù)據(jù)的一組原子操作接口。格式如：set_bit(intnr,void*addr)3.4進程同步3.4.5Linux同步機制解析1.原子操作要操作的位號指向要操作的數(shù)據(jù)的指針概念：自旋鎖最多只能被一個內(nèi)核任務持有；在短期間內(nèi)進行輕量級的鎖定；自旋鎖不允許任務睡眠；自旋鎖是專為防止多處理器并發(fā)而引入的一種鎖3.4進程同步3.4.5Linux同步機制解析2.自旋鎖定義：typedefstruct{volatile

unsigned

int

lock;}spinlock_t;3.4進程同步3.4.5Linux同步機制解析2.自旋鎖操作函數(shù)：操作接口功能描述DEFINE_SPINLOCK(lock)申明一個自旋鎖lock，并置為開鎖狀態(tài)spin_lock_init(spinlock_t*)初始化指定的自旋鎖，置為開鎖狀態(tài)spin_lock(spinlock_t*)獲取指定的自旋鎖spin_unlock(spinlock_t*)釋放已獲得的指定自旋鎖spin_lock_irq(spinlock_t*)