第四章互斥同步與通訊課件

第四章互斥、同步與通訊進程(線程)之間的相互作用：

互斥、同步、通訊4.1并發(fā)進程(concurrentprocesses)4.2進程互斥(mutualexclusion)4.3進程同步(synchronization)4.4進程高級通訊(communication)第四章互斥、同步與通訊進程(線程)之間的相互作用：4.1.1順序程序及其特性程序的順序性有兩層含義:(1)內(nèi)部順序性：指一個進程的所有指令

按序執(zhí)行;(2)外部順序性：指多個進程依次執(zhí)行;例如,假設(shè)有兩個進程P1和P2：P1活動:a1a2a3a4P2活動:b1b2b3順序執(zhí)行時,有如下兩種情形:情形1:a1a2a3a4

b1b2b3

情形2:b1b2b3

a1a2a3a4

4.1并發(fā)進程4.1.1順序程序及其特性4.1并發(fā)進程順序程序的特性：(1)順序性：處理機嚴格按指令次序依次執(zhí)行，僅當一條指令執(zhí)行完才開始執(zhí)行下一指令；(2)封閉性：程序在執(zhí)行過程中獨占系統(tǒng)的全部資源。該程序的運行環(huán)境只與其自身動作有關(guān)，不受其它程序及外界因素影響；(3)可再現(xiàn)性：程序的執(zhí)行結(jié)果只與初始條件有關(guān)，與執(zhí)行速度無關(guān)。給定相同的初始條件，程序的任意多次執(zhí)行一定得到相同結(jié)果。順序程序的特性：4.1.2并發(fā)程序及其特性程序的并發(fā)性有兩層含義:(1)內(nèi)部并發(fā)性：指一個進程的所有指令不一定按序執(zhí)行;(2)外部并發(fā)性:指多個進程交叉執(zhí)行。例如，假設(shè)有兩個進程：P1活動:a1a2a3a4P2活動:b1b2b3

內(nèi)部并發(fā)性如：P2:b1,b3,b2;……

外部并發(fā)性如:情形1:a1b1b2a2a3b3a4情形2:b1b2a1a2a3b3a4

……并發(fā)進程在執(zhí)行過程中出現(xiàn)哪種交叉情形是不可預(yù)知的,這就是并發(fā)程序的不確定性。4.1.2并發(fā)程序及其特性并發(fā)程序的特性：(1)交叉性：一個進程的某些指令可交叉執(zhí)行，不同的進程亦可交叉執(zhí)行；程序并發(fā)執(zhí)行時，不同的交叉可能導(dǎo)致不同的計算結(jié)果。OS應(yīng)保證只產(chǎn)生導(dǎo)致正確結(jié)果的交叉，去除那些可能導(dǎo)致不正確結(jié)果的交叉。(2)非封閉性：一個進程的運行環(huán)境可能被其它進程改變，從而相互影響。(3)不可再現(xiàn)性：并發(fā)程序的多次執(zhí)行可能對應(yīng)不同的交叉，因而不能期望重新運行的程序能夠再現(xiàn)上次運行的結(jié)果。如運行時間并發(fā)程序的特性：4.1.2與時間有關(guān)的錯誤例如圖書借閱系統(tǒng)(設(shè)x:某種書冊數(shù)，當前x=1)終端1：終端2：CYCLECYCLE等待借書者；等待借書者；IFx>=1ThenIFx>=1ThenBeginBeginx:=x-1;x:=x-1;借書借書EndEndElse無書Else無書EndEnd12344.1.2與時間有關(guān)的錯誤例如圖書借閱系統(tǒng)(設(shè)x:某上述錯誤的發(fā)生與進程的推進速度有關(guān)(速度是時間的函數(shù))。當進程P1執(zhí)行到③處被中斷,之后P2插入,則不會發(fā)生上述錯誤。若一種錯誤的發(fā)生與進程的推進速度有關(guān)，則稱這種錯誤為與時間有關(guān)的錯誤。發(fā)生與時間有關(guān)錯誤的原因：(1)進程執(zhí)行交叉(interleave)。(2)涉及公共變量(x)。若兩個進程同時對變量x進行操作,其中一個進程對x的操作僅做了一部分時,另一個進程中途插入，則可能使變量x處于一種不確定狀態(tài)，從而失去其數(shù)據(jù)完整性。OS必須防止這種情況的發(fā)生。上述錯誤的發(fā)生與進程的推進速度有關(guān)(速度是時間的函數(shù)4.2進程互斥

(mutualexclusion)

進程互斥是進程間發(fā)生的一種間接相互作用,這種相互作用是進程本身不希望的,也是運行進程感覺不到的。

進程互斥可能發(fā)生在相關(guān)進程之間,也可能發(fā)生在無關(guān)進程之間。4.2進程互斥

(mutualexclusion)4.2.1共享變量與臨界區(qū)

(sharedvariable&criticalregion)1.共享變量與臨界區(qū)的概念共享變量：可以被多個進程訪問的變量。也稱公共變量。

臨界區(qū)：訪問共享變量的程序段。也稱為臨界段(criticalsection)。共享變量與臨界區(qū)的關(guān)系：

一組公共變量CR1CR2CRn…….4.2.1共享變量與臨界區(qū)一組公共變量CR1CR2CRn2.共享變量與臨界區(qū)的表示共享變量的表示(說明)：

shared<一組變量>

如，sharedx1,x2;臨界區(qū)的表示:

region<一組變量>do<語句>這是一個語句,稱作臨界區(qū)語句。其中<語句>可為任意語句,包括臨界區(qū)語句。例如，regionx1,x2do{…(訪問x1,x2)…}再如，sharedb:array[0,..,n-1]ofinteger;regionbdobegin……(訪問b)end;

2.共享變量與臨界區(qū)的表示若一個臨界區(qū)語句中的<語句>部分包括另一個臨界區(qū)語句,便發(fā)生了臨界區(qū)嵌套。例如，sharedx1,x2;sharedy1,y2;

regionx1,x2do{……

regiony1,y2do{……}……}若一個臨界區(qū)語句中的<語句>部分包括另一個臨界區(qū)語句,再如，sharedx1,x2;sharedy1,y2;

regionx1,x2doregiony1,y2dobeginbegin………….

regiony1,y2doregionx1,x2dobeginbegin…….…….endendend;end;再如，sharedx1,x2;4.2.2臨界區(qū)與進程互斥進程互斥:兩個或兩個以上的進程不能同時進入關(guān)于同一組共享變量的臨界區(qū),否則可能發(fā)發(fā)生與時間有關(guān)的錯誤,這種現(xiàn)象被稱作進

程互斥。進程互斥有兩層含義:(1)不容許多個進程同時進入關(guān)于同一組共享變量的相同的臨界區(qū)；(2)不容許多個進程同時進入關(guān)于同一組共享變量的不同的臨界區(qū)。注意：進程互斥是相對于共享變量而言的。4.2.2臨界區(qū)與進程互斥當然，若容許多個進程同時進入關(guān)于同一組共享變量的臨界區(qū)，也不是一定會發(fā)生錯誤。是否會發(fā)生錯誤與進程并發(fā)執(zhí)行時的推進速度有關(guān)。

不容許多個進程同時進入關(guān)于同一組共享變量的臨界區(qū)，是保證正確性的要求。這件事的實現(xiàn)應(yīng)由OS及并發(fā)程序設(shè)計者在編寫程序時保證，這需要必要的互斥機制。當然，若容許多個進程同時進入關(guān)于同一組共享變量使用嵌套的臨界區(qū)時需特別注意，否則可能會發(fā)生不期望的后果。例如，sharedx;sharedy;

regionxdo{regionydo{……(1)……(2)

regionydo{regionxdo{…………}}}}當進程P1執(zhí)行到(1)、進程P2執(zhí)行到(2)時，P1已進入關(guān)于x的臨界區(qū)，要求進入關(guān)于y的臨界區(qū)，P2則反之。由于臨界區(qū)是互斥的，因此二者均無法繼續(xù)向前推進，這種現(xiàn)象稱為死鎖(第五章)。使用嵌套的臨界區(qū)時需特別注意，否則可能會發(fā)生不4.2.3進程互斥的實現(xiàn)

進程互斥的實現(xiàn)就是實現(xiàn)對臨界區(qū)的管理。

對臨界區(qū)的管理應(yīng)滿足如下管理原則：(進程互斥的Requirements)(1)正確性原則(correctness)：mutualexclusion一次只允許一個進程活動在關(guān)于同一組公共變量的臨界區(qū)中。即任意時刻最多只能有一個進程處于關(guān)于同一組共享變量的臨界區(qū)中；4.2.3進程互斥的實現(xiàn)(2)公平性原則(fairness)：boundedwaiting一個請求進入臨界區(qū)的進程應(yīng)在有限時間內(nèi)獲得進入該臨界區(qū)的機會；(3)進展性原則(progress)：臨界區(qū)空閑時，競爭進入臨界區(qū)的多個進程在有限時間內(nèi)確定下一個進入臨界區(qū)的進程。以上原則是對互斥的實現(xiàn)而言的。臨界區(qū)的管理實現(xiàn)后，使用時，如果不慎可能會違背上述原則。例如，臨界區(qū)中的程序出現(xiàn)了死循環(huán)。

(2)公平性原則(fairness)：bounded臨界區(qū)相當于一個獨占型資源。對臨界區(qū)資源的管理應(yīng)滿足如下調(diào)度原則:

(1)當關(guān)于某一組共享變量的所有臨界區(qū)均為空閑時,一個要求進入該組共享變量某一臨界區(qū)的進程應(yīng)能立即進入;(2)當關(guān)于某一組共享變量的某一臨界區(qū)域被占用時,一個要求進入該組共享變量某一臨界區(qū)域的進程應(yīng)等待;(3)當一個進程離開關(guān)于某一組共享變量的某一臨界區(qū)時,應(yīng)容許某一個等待進入關(guān)于該組共享變量某一臨界區(qū)域的進程進入。臨界區(qū)相當于一個獨占型資源。4.2.3.1進程互斥的軟件實現(xiàn)

進程互斥的軟件實現(xiàn)指完全用程序?qū)崿F(xiàn)進程的互斥，不需特殊硬件指令的支持。進程互斥的軟件實現(xiàn)方法可用于單CPU和多CPU環(huán)境中。進程互斥的軟件實現(xiàn)有忙式等待問題。4.2.3.1進程互斥的軟件實現(xiàn)進程互斥的軟Repeat

criticalsection

remaindersectionUntilfalseentrysectionexitsectionFramework進程互斥的軟件實現(xiàn)算法：Lamport面包店算法Eisenberg算法兩種算法均假定系統(tǒng)中進程的個數(shù)有限，如n個實現(xiàn)進程互斥的軟件的結(jié)構(gòu)框架：Repeatentrysectionexitsectio面包店算法的基本思想來源于顧客在面包店購買面包時的排隊原理。顧客進入面包店前,首先抓一個號碼,然后按號碼由小到大的次序依次進入面包店購買面包。這里假定：

(1)面包店按由小到大的次序發(fā)放號碼,且兩個或兩個以上的顧客有可能得到相同號碼(要使顧客的號碼不同，需互斥機制)。

(2)若多個顧客抓到相同號碼,則按顧客名字的字典次序排序(假定顧客沒有重名)。計算機系統(tǒng)中,顧客相當于進程,每個進程有一個唯一的標識,用Pi,i=1,2,…表示。對于Pi和Pj，若有i<j，即Pi先進入臨界區(qū)，則先為Pi服務(wù)。1.Lamport面包店算法面包店算法的基本思想來源于顧客在面包店購買面包時的排面包店算法的基本思想：

首先設(shè)置一個發(fā)號器，按由小到大的次序發(fā)放號碼。進程進入臨界區(qū)前先抓一個號碼，然后按號碼由小到大的次序依次進入臨界區(qū)。若多個進程抓到相同的號碼，則按進程編號依次進入。面包店算法的基本思想：

實現(xiàn)面包店算法所需的數(shù)據(jù)結(jié)構(gòu):intchoosing[n]；intnumber[n]；或choosing:ARRAY[0..n-1]OFinteger;number:ARRAY[0..n-1]OFinteger;choosing[n]用來表示進程是否正在抓號，其初值均為0。若進程i正在抓號，則choosing[i]賦為1，否則choosing[i]為0。number[n]用來記錄進程抓到的號碼，其初值均為0。若number[i]為0,則進程Pi沒有抓號；若number[i]不為0,則其正整數(shù)值為進程Pi抓到的號碼。實現(xiàn)面包店算法所需的數(shù)據(jù)結(jié)構(gòu):為便于面包店算法的描述,引入下述表記法：<1>設(shè)(a,b):Pi，(c,d):Pj，則

(a,b)<(c,d)iff(a<c)or(a=candb<d)<2>max(a0,…,an-1)=k：對所有的i,0in-1,k≥ai,k為正整數(shù)。為便于面包店算法的描述,引入下述表記法：算法4.1Lamport面包店算法do{choosing[i]=1;number[i]=max(number[0],number[1],…,

number[n-1])+1;

choosing[i]=0;for(j=0;j<n;j++){

while(choosing[j])skip;while((number[j]<>0)&&(number[j],j)<(number[i],i))skip;};

臨界區(qū)

number[i]=0;

其余部分}while(1);(1)P1抓到1尚未賦值(2)P2抓到1(3)P3抓到2算法4.1Lamport面包店算法(1)P1抓到1尚未變量choosing的作用

當進程Pi計算完max(…)+1但尚未將值賦給number[i]時，進程Pj中途插入，計算max(…)+1，得到相同的值。在這種情況下，choosing[j]保證編號較小的進程先進入臨界區(qū)。

變量choosing的作用忙式等待：上述Lamport面包店算法中，若while循環(huán)的循環(huán)條件成立，則進程將重復(fù)測試，直到條件為假。實際上，當while循環(huán)條件成立時，進程Pi不能向前推進，而在原地踏步，這種原地踏步被稱為忙式等待(busywaiting)。忙式等待空耗CPU資源，因而是低效的。忙式等待：驗證面包店算法是否滿足臨界區(qū)管理原則：(1)正確性：若進程Pj已在CS，而進程Pi(ij)擁有與Pj不同的號，則(number[j],j)<(number[i],i))。此時進程Pi若試圖進入該臨界區(qū)，則忙式等待，直至進程Pj離開臨界區(qū)。(2)公平性：因進程按FIFO次序進入臨界區(qū)，且進程個數(shù)有限，故進程不會無限等待進入臨界區(qū)。(3)進展性：當多個進程競爭進入臨界區(qū)時，下述條件之一成立：<1>一個進程抓到最小號碼；<2>若干進程抓到最小號碼。情形<1>抓到最小號碼的進程獲準進入臨界區(qū)；情形<2>抓到最小號碼且編號最小的進程獲準進入臨界區(qū)。因而能在有限時間內(nèi)確定進入臨界區(qū)的進程。驗證面包店算法是否滿足臨界區(qū)管理原則：

Eisenberg算法采用的數(shù)據(jù)結(jié)構(gòu):enumflag[n](idle,want_in,in_cs);intturn;//intherangeof(0,n-1)intj;//intherangeof(0,n-1)或flag:ARRAY[0..n-1]OF(idle,want_in,in_cs);

其中,flag[i]=idle:進程Pi不想進入臨界區(qū),

flag[i]=want_in:進程Pi想進入臨界區(qū),

flag[i]=in_cs:進程Pi想進或已進臨界區(qū),flag的所有元素初值均為idle，

turn的初值為0到n-1之間的任一正整數(shù)，

j為每個進程擁有的一個局部變量,其初值為0到n-1之間的任一正整數(shù)。2.Eisenberg/Mcguire算法Eisenberg算法采用的數(shù)據(jù)結(jié)構(gòu):2.Eisenbe算法4.2

Eisenberg/Mcguire算法do{

do{

flag[i]=want_in;

j=turn;//turn表示允許進入CS的進程編號while(j!=i)if(flag[j]!=idle)

j=turn;elsej=(j+1)%n;//mod

flag[i]=in_cs;

j=0;while((j<n)&&(j==i||flag[j]!=in_cs))

j++;}while(j!=n);turn=i;

臨界區(qū)算法4.2Eisenberg/Mcguire算法//臨界區(qū)

j=(turn+1)%n;while(flag[j]==idle)

j=(j+1)%n;turn=j;flag[i]=idle;其余部分}while(1);

//臨界區(qū)

驗證Eisenberg算法是否滿足臨界區(qū)管理原則：(1)互斥性：僅當對所有的ji且flag[j]in-cs時,進程Pi才進入其臨界區(qū),故滿足互斥性原則。(2)公平性：一個進程離開臨界區(qū)時，它必須在循環(huán)次序中指定唯一一個競爭進程作為其后繼，故任一要求進入臨界區(qū)的進程最多在n-1個進程進入并離開臨界區(qū)后一定能進入臨界區(qū),故滿足公平性。(3)進展性：如果沒有進程正處于臨界區(qū)或離開臨界區(qū)，則turn的值不變。競爭進程按循環(huán)次序turn,

turn+1,…,n-1,0,…,turn-1進入臨界區(qū)，故滿足進展性原則。Eisenberg算法同樣存在忙式等待問題。驗證Eisenberg算法是否滿足臨界區(qū)管理原則：4.2.3.2進程互斥的硬件實現(xiàn)用硬件方法實現(xiàn)互斥通常比軟件方法簡單。

1.硬件提供“測試并建立”(TestandSet,TS)指令

“測試并建立”指令實質(zhì)上是取出內(nèi)存某一單元的值，再給該單元賦一個新值。該指令在執(zhí)行時不可被分割，是原子的。

“測試并建立”指令的定義如下:intTS(int&target){inttemp;temp:=*target;*target=1;return(temp);}4.2.3.2進程互斥的硬件實現(xiàn)用硬件方法實現(xiàn)互斥若硬件提供了“測試并建立”指令,則可按如下方法實現(xiàn)進程互斥：對每組共享變量,定義一個全局變量：intlock;//lock初值為0,表示無進程在臨界區(qū)

算法4.3

基于TS指令的互斥算法

(不公平)do{while(TS(lock))skip;

臨界區(qū)

lock=0;其余部分}while(1);若lock當前值為0,則賦為1,進入臨界區(qū)；若lock當前值為1,則反復(fù)測試直到lock變?yōu)?,存在忙式等待。若硬件提供了“測試并建立”指令,則可按如下方法實2.硬件提供“交換”(swap)指令

交換指令將兩個內(nèi)存單元中的內(nèi)容相互交換。交換指令也是原子的。

交換指令的定義如下:voidswap(int&a,&b){inttemp;temp=*a;*a=*b;*b=temp;}交換指令在執(zhí)行時也是不可分割的,即要求在一個指令周期內(nèi)執(zhí)行完。2.硬件提供“交換”(swap)指令若硬件提供了“交換”指令,則可按如下方法實現(xiàn)進程互斥：對每組共享變量，定義一個全局變量:int

lock

;//lock初值為0

對每個要求進入關(guān)于該組共享變量的臨界區(qū)的進程，定義一個局部變量:intkey;算法4.4基于swap指令的互斥算法

(不公平)do{key=1;do{swap(&lock,&key);}while(key==1)

臨界區(qū)

lock=0;其余部分}while(1);若硬件提供了“交換”指令,則可按如下方法實現(xiàn)進程互斥：上述兩個互斥算法均不滿足有限等待原則。

為滿足有限等待原則,需引入新的全局變量:intwaiting[n];//初值均為0intlock;//初值為0每一進程亦需引入新的局部變量:intj;intkey;

上述兩個互斥算法均不滿足有限等待原則。算法4.5公平性硬件互斥算法do{waiting[i]=1;key=1;while(waiting[i]&&key)

key=TS(&lock);//忙式等待waiting[i]=0;

臨界區(qū)

j=(i+1)%n;//modwhile((j!=i)&&(!waiting[j]))

j=(j+1)%n;if(j==i)lock=0;elsewaiting[j]=0;其余部分}while(1);算法4.5公平性硬件互斥算法3.硬件提供“開/關(guān)中斷”指令開/關(guān)中斷是實現(xiàn)進程互斥的一種特殊硬件方法。若硬件提供了開/關(guān)中斷指令,則進程進入臨界區(qū)前只需執(zhí)行一條關(guān)中斷指令,離開臨界區(qū)時只需執(zhí)行一條開中斷指令。算法4.6開/關(guān)中斷互斥算法do{關(guān)中斷

臨界區(qū)

開中斷其余部分}while(1)3.硬件提供“開/關(guān)中斷”指令由于中斷是進程切換的必要條件，關(guān)中斷后不會發(fā)生進程切換，故進入臨界區(qū)的進程將連續(xù)不斷地執(zhí)行完臨界區(qū)的全部指令，因而滿足互斥性。易證，它亦滿足公平性。

用開關(guān)中斷法實現(xiàn)進程互斥的優(yōu)點:(1)實現(xiàn)效率高。(2)不存在忙式等待問題。(3)簡單易行。

用開關(guān)中斷法實現(xiàn)進程互斥的缺點:(1)僅在單CPU系統(tǒng)中有效。{因為在多CPU系統(tǒng)中，關(guān)中斷不能阻止代表不同進程的多個CPU同時對關(guān)于同一組共享變量的臨界區(qū)進行訪問}(2)影響系統(tǒng)的并發(fā)性。由于中斷是進程切換的必要條件，關(guān)中斷后不會發(fā)生進程4.2.4多處理機環(huán)境下的進程互斥

單處理機環(huán)境中可使用硬件提供的swap指令或TS指令實現(xiàn)進程互斥，這些指令涉及對同一存儲單元的兩次或兩次以上操作，這些操作將在幾個指令周期內(nèi)完成。由于中斷只發(fā)生在兩條機器指令之間，同一指令內(nèi)的多個指令周期不可中斷，因而swap或TS指令的執(zhí)行不會交叉進行。

多處理機環(huán)境中情況有所不同。例如，兩個CPU執(zhí)行TS(lock)可能發(fā)生指令周期的交叉。由于TS指令包括取數(shù)、送數(shù)兩個指令周期，若lock初始為0，CPU1和CPU2可能分別執(zhí)行完前一指令周期并通過檢測(均為0)，然后分別執(zhí)行后一指令周期將lock置為1，結(jié)果都取回0作為判斷臨界區(qū)空閑的依據(jù)，故不能實現(xiàn)互斥。4.2.4多處理機環(huán)境下的進程互斥單處理機環(huán)境中可使用內(nèi)存Initial:0CPU1CPU2Bus1.讀03.寫1

2.讀04.寫1內(nèi)存Initial:0CPU1CPU2Bus1.讀03.多CPU環(huán)境中要利用TS指令實現(xiàn)進程互斥，需提供進一步的硬件支持，以保證TS指令執(zhí)行的原子性。這種支持目前多以“鎖總線”(bus-locking)的形式提供。由于TS指令對內(nèi)存的兩次操作都需經(jīng)過總線，故在執(zhí)行TS指令前鎖住總線，在執(zhí)行TS指令后開放總線，可保證TS指令執(zhí)行的原子性。多CPU環(huán)境中要利用TS指令實現(xiàn)進程互斥，需提供進一步算法4.6多處理機互斥算法do{b=1;while(b){

lock(bus);//忙式等待

b=TS(&lock);

unlock(bus);}

臨界區(qū)

lock=0;其余部分}while(1)算法4.6多處理機互斥算法自旋鎖：忙式等待鎖稱為自旋鎖(spin-lock)。上述多處理機互斥算法中的鎖為自旋鎖。自旋鎖是在多處理機系統(tǒng)中經(jīng)常采用的互斥方法。自旋鎖一般是低效的。在許多SMP系統(tǒng)中，允許多個CPU同時執(zhí)行目態(tài)程序。由于一次只允許一個CPU執(zhí)行OS代碼，因而利用自旋鎖可實現(xiàn)這種控制。一次只允許一個CPU執(zhí)行核心代碼，使得系統(tǒng)的并發(fā)性不高。若期望核心程序在多CPU之間的并行執(zhí)行，可將核心分為若干相對獨立的部分，不同的CPU可同時進入并執(zhí)行核心中的不同部分。實現(xiàn)時可為每個相對獨立的區(qū)域設(shè)置一個自旋鎖。自旋鎖：忙式等待鎖稱為自旋鎖(spin-lock4.3進程同步例如，司機-售票員問題司機活動：售票員活動：do{do{啟動車輛關(guān)車門正常行駛售票到站停車開車門}while(1)}while(1)進程同步是進程之間的直接相互作用，是合作進程之間有意識的行為,這種相互作用只發(fā)生在相關(guān)進程之間。4.3進程同步例如，司機-售票員問題

4.3.1進程同步的概念

進程同步：一組進程，為了協(xié)調(diào)其推進速度，在某些點處需要相互等待與相互喚醒，進程之間的這種相互制約關(guān)系稱為進程同步。

注意：進程同步僅發(fā)生于有邏輯關(guān)系的進程之間；進程互斥可能發(fā)生于任意兩個進程之間。與進程同步相關(guān)的另一概念是進程合作。

進程合作：一組進程單獨不能正常進行,但并發(fā)可以正常進行的現(xiàn)象稱為進程合作。參與合作的進程稱為合作進程。進程同步是合作進程之間的直接相互作用。4.3.1進程同步的概念4.3.2進程同步機制

同步機制：用于實現(xiàn)進程間同步的工具稱作同步機制，亦稱同步設(shè)施。

典型的同步機制：

信號燈與PV操作(semaphoreandPVoperations)管程(monitor)條件臨界區(qū)(conditionalcriticalregion)路徑表達式(pathexpression)會合(rendezvous)(用于分布式系統(tǒng)）事件(traditionalUNIX)4.3.2進程同步機制

同步機制應(yīng)滿足的基本要求:

(1)描述能力夠用。即用此種同步機制應(yīng)能描述操作系統(tǒng)及并發(fā)程序設(shè)計中所遇到的各種同步問題(例如，生產(chǎn)者消費者問題、讀者寫者問題、哲學(xué)家就餐問題);(2)可以實現(xiàn);(3)效率高;(4)使用方便。同步機制應(yīng)滿足的基本要求:4.3.3信號燈與PV操作荷蘭E.W.Dijkstra于1965年提出。這種同步機制包括一種信號燈變量及對此種變量所能進行的操作：P操作和V操作。

1.信號燈與PV操作的定義

信號燈類型定義如下：typedefsemaphorestruct{intvalue;pointer_to_PCBqueue;}

信號燈變量說明如下：

semaphore

s;4.3.3信號燈與PV操作荷蘭E.W.Dijk可見,一個信號燈變量包括兩部分：值部分s.value和指針部分s.queue。在任意時刻，s.queue可能指向空，也可能指向一個PCB隊列的首部。初始時s.queue指向空。S.valueS.queuePCBPCBPCBS.valueS.queue…可見,一個信號燈變量包括兩部分：值部分s.val

P操作原語的定義:voidP(semaphore*s){s->value--；if(s->value<0)

asleep(s->queue);}

asleep(s->queue)：(1)將執(zhí)行此操作的那個進程的PCB插入s->queue所指PCB隊列的尾部,其狀態(tài)由運行轉(zhuǎn)為等待；(2)轉(zhuǎn)到處理機調(diào)度程序。

原語:一段不可間斷執(zhí)行的程序稱為原語。說明：P操作對應(yīng)申請資源。P操作原語的定義:

V操作原語的定義:voidV(semaphore*s){s->value++;if(s->value<=0)

wakeup(s->queue);}wakeup(s->queue)：將s->queue所指隊列首部的PCB取出并將其插入就緒隊列,其狀態(tài)由等待轉(zhuǎn)為就緒。

說明：V操作對應(yīng)釋放資源

V操作原語的定義:使用信號燈變量的規(guī)定：(1)必須置一次初值,只能置一次初值,且初值必需為非負整數(shù)：(2)只能執(zhí)行P操作和V操作,其它操作均非法。關(guān)于信號燈變量的幾個有用結(jié)論：(1)當s->value<0時,|s->value|為s->queue中等待進程的個數(shù);(2)當s->value≥0時,s->queue為空;使用信號燈變量的規(guī)定：(3)當s->value初值為1,可用來實現(xiàn)進程互斥。這只需在進入CS時執(zhí)行一次P操作,離開CS時執(zhí)行一次V操作。(4)當s->value初值為0,可用來實現(xiàn)進程同步。這只需在后進行的動作前執(zhí)行一次P操作，在先進行的動作后執(zhí)行一次V操作。(5)當s->value初值為正整數(shù),可用來管理同種組

合資源。使用資源前執(zhí)行一次P操作(申請),用完后執(zhí)行一次V操作(歸還)。(3)當s->value初值為1,可用來實現(xiàn)進程互斥。組合資源：若干相對獨立的資源構(gòu)成的資源集合,其中每個相對獨立的資源稱為子資源。同種組合資源:相同類型子資源構(gòu)成的組合資源.對同種組合資源進行管理時semaphoreS=子資源個數(shù);//初值例如，2臺打印機semaphoreS=2;P(S)；//申請使用V(S)；//釋放組合資源：若干相對獨立的資源構(gòu)成的資源集用信號燈變量實現(xiàn)進程互斥……sharedx,y,z:integer;CR1CR2CRnsharedx,y,z:integer;P(mutex)P(mutex)P(mutex)CR1CR2CRnV(mutex)V(mutex)V(mutex)……semaphoremutex=1;用信號燈變量實現(xiàn)進程互斥……sharedx,y,z:semaphoremutex=1;終端1：終端2：CYCLECYCLE等待借書者；等待借書者；

P(mutex)

P(mutex)IFx>=1ThenIFx>=1ThenBeginBeginx:=x-1;x:=x-1;

V(mutex)

V(mutex)

借書借書EndEndElseV(mutex);ElseV(mutex);//無書EndEnd例圖書借閱系統(tǒng)

semaphoremutex=1;例圖書借閱系統(tǒng)用信號燈變量實現(xiàn)進程同步semaphoreS=0;

P(S)后動作先動作

V(S)P1P2用信號燈變量實現(xiàn)進程同步P(S)先動作P1P2例司機-售票員問題semaphores1=0,s2=0;司機活動：售票員活動：RepeatRepeat

P(S1)關(guān)車門啟動車輛V(S1)正常行駛售票到站停車P(S2)

V(S2)開車門UntilfalseUntilfalse例司機-售票員問題2.信號燈與PV操作的應(yīng)用用信號燈與PV操作解決進程同步及互斥問題.Classicalsynchronizationproblems

(1)Producersandconsumersproblem(2)Readersandwritersproblem(3)Diningphilosophersproblem(4)Cigarettesmokersproblem(5)Sleepybarbersproblem……

2.信號燈與PV操作的應(yīng)用例1生產(chǎn)者-消費者問題假設(shè)某工廠生產(chǎn)線上有一只用來裝物品的箱子,其中有k個位置(k≥1),每個位置可容納一件物品，如圖所示01……k-1箱子(容量k)用數(shù)組表示itemtypeB[n];

生產(chǎn)者消費者生產(chǎn)物品放入B中從B中取物品消費之例1生產(chǎn)者-消費者問題假設(shè)某工廠生產(chǎn)線上10K-1in(in+1)%kout(out+1)%kin為放入指針,初值0out為取出指針,初值0為實現(xiàn)方便,將箱子中的位置(緩沖區(qū))作成環(huán)形。10K-1in(in+1)%kout(out+1)%k生產(chǎn)者-消費者問題分析需解決的同步問題：箱子滿時,P1等待于①,P2執(zhí)行到④將其喚醒；箱子空時,P2等待于③,P1執(zhí)行到②將其喚醒。生產(chǎn)者活動P1:do{加工一件物品;物品放入箱中;}while(1);消費者活動P2:do{箱中取一物品;消耗這件物品;}while(1);─①─④─③─②生產(chǎn)者-消費者問題分析需解決的同步問題：生產(chǎn)者活動P1:消費從資源角度看：箱子中的位置相當于生產(chǎn)者資源,可用一個信號燈變量S1表示,其初值為k；物品相當于消費者資源,可用一個信號燈變量S2

表示,其初值為0。生產(chǎn)者資源：箱子B消費者資源：物品semaphoreS1=k;semaphoreS2=0;放前：P(S1)取前：P(S2)放后：V(S2)取后：V(S1)從資源角度看：同步問題的解決：生產(chǎn)者活動：消費者活動：

RepeatRepeat

加工一件物品

P(S2)P(S1)

箱中取一物品

物品放入箱中

V(S1)V(S2)

消耗這件物品

UntilfalseUntilfalse同步問題的解決：需解決的互斥問題：需解決對關(guān)于共享變量B,in,out的臨界區(qū)的互斥:semaphoremutex=1;互斥問題的解決：生產(chǎn)者活動：消費者活動：RepeatRepeat

加工一件物品P(S2)

P(S1)

P(mutex)

P(mutex)

箱中取一物品物品放入箱中V(mutex)

V(mutex)

V(S1)

V(S2)

消耗這件物品UntilfalseUntilfalse需解決的互斥問題：互斥問題的解決：生產(chǎn)者-消費者問題的自動機描述22…10-1-2P(S)P(S)P(S)P(S)P(S)V(S)

V(S)

V(S)

V(S)

V(S)

S.value=空閑資源數(shù)|S.value|=等待進程數(shù)...S.queue=空空閑資源數(shù)=0生產(chǎn)者-消費者問題的自動機描述22…10-1-2P(S)P(

生產(chǎn)者-消費者問題的求解程序itemTypeB[k];semaphore

S1=k;//S1表示箱子中的位置semaphoreS2=0;//S2表示物品intin=0;intout=0;semaphoremutex=1;//初值為1,用于實現(xiàn)進程互斥voidproducer(){whlie(1){produceItem(&item);//生產(chǎn)一件產(chǎn)品P(S1);P(mutex);B[in]=item;

in=(in+1)%k;V(mutex);V(S2);}}生產(chǎn)者-消費者問題的求解程序voidconsumer(){itemTypetemp;while(1){P(S2);P(mutex);

temp=B[out];

out=(out+1)%k;V(mutex);V(S1);//然后消費一件產(chǎn)品}}fork(producer,0);…;fork(producer,m-1);fork(consumer,0);…;fork(consumer,n-1);voidconsumer(){并發(fā)性提高策略生產(chǎn)者的共享變量:B[in],in消費者的共享變量:B[out],out當inout時,生產(chǎn)者和消費者不操作B的相同分量;當in=out時,緩沖區(qū)或空或滿,PV操作已保證空時

消費者不會取,滿時生產(chǎn)者不會放。可見,生產(chǎn)者和消費者任何情況下均不操作B的相同分量。為提高程序的并發(fā)性,可將用于互斥的信號燈變量分為兩個:mutex1和mutex2,分別用于生產(chǎn)者的互斥和消費者的互斥:semaphoremutex1=1,mutex2=1;并發(fā)性提高策略生產(chǎn)者活動：消費者活動：RepeatRepeat

加工一件物品P(S2)P(S1)P(mutex2)

P(mutex1)

箱中取一物品物品放入箱中V(mutex2)V(mutex1)V(S1)V(S2)消耗這件物品UntilfalseUntilfalse生產(chǎn)者活動：消費生產(chǎn)者-消費者問題在OS及并發(fā)程序設(shè)計中經(jīng)常遇到。箱子相當于緩沖區(qū)生產(chǎn)者和消費者相當于進程進程之間通過一個長度有界的緩沖區(qū)通訊生產(chǎn)者-消費者問題又稱作有界緩沖區(qū)問題生產(chǎn)者-消費者問題在OS及并發(fā)程序設(shè)計中經(jīng)常遇到一組公共數(shù)據(jù)DBRm…W1R1Wn…設(shè)有一組共享數(shù)據(jù)DB和兩組并發(fā)進程,一組進程只對此組數(shù)據(jù)執(zhí)行讀操作,另一組進程可對此組數(shù)據(jù)執(zhí)行寫操作和讀操作。前一組進程稱作讀者,后一組進程稱作寫者.要求:(1)R-R可同時(2)W-W不可同時(2)R-W不可同時例2讀者—寫者問題一組公共數(shù)據(jù)DBRm…W1R1Wn…設(shè)有一組共Solution1:不考慮R-R不互斥semaphorer_w_w=1;Reader()Writer()P(r_w_w);P(r_w_w);{讀操作}{寫操作}V(r_w_w);V(r_w_w);分析:寫者活動正確,但R-R不能并發(fā)。改進:最先進入的R執(zhí)行P,最后離開的R執(zhí)行VSolution1:不考慮R-R不互斥Solution2:考慮R-R不互斥intreadCount=0;Reader()readCount:=readCount+1;IfreadCount=1ThenP(r_w_w);{讀操作}readCount:=readCount-1;IfreadCount=0ThenV(r_w_w);分析:對Read_count操作不互斥.改進:用信號燈變量mutex實現(xiàn)對readCount的互斥.Solution2:考慮R-R不互斥Solution3:考慮對readCount的互斥intreadCount=0;semaphoremutex=1;Reader()

P(mutex);readCount:=readCount+1;IfreadCount=1ThenP(r_w_w);V(mutex);{讀操作}P(mutex);readCount:=readCount-1;IfreadCount=0ThenV(r_w_w);V(mutex);Solution3對應(yīng)的程序如下：Solution3:考慮對readCount的互斥intreadCount=0;//readCount記錄讀者的數(shù)目semaphorer_w_w=1;semaphoremutex=1;reader(){while(1){<otheractions>P(&mutex);//mutex實現(xiàn)對readCount的互斥

readCount=readCount+1;if(readCount==1)P(&r_w_w);

//r_w_w實現(xiàn)R-W間及W-W間的互斥

V(&mutex);<readoperations>P(&mutex);

readCount=readCount-1;if(readCount==0)V(&r_w_w);V(&mutex);}}intreadCount=0;//readwriter(){while(1){<otheraction>

P(&r_w_w);<writeoperation>

V(&r_w_w);}}fork(reader,0);…;fork(reader,m-1);fork(writer,0);…;fork(writer,n-1);分析:R-R不互斥.若讀者源源不斷,寫者可能餓死.事實上,寫者的操作是更新數(shù)據(jù),應(yīng)優(yōu)先進行,否則讀者將讀到過時的數(shù)據(jù).改進:寫者優(yōu)先,即一旦有寫者等待,正在讀的讀者都結(jié)束后,寫者進入,新到達的讀者等待.writer(){分析:R-R不互斥.若例3哲學(xué)家就餐問題(DiningPhilosophersProblem)ProposedandsolvedbyE.W.Dijkstrain1965.Roomph0ph4ph3ph2ph1f0f4f3f2f1例3哲學(xué)家就餐問題(DiningPhilosopher哲學(xué)家活動：Repeat思考進食Untilfalse進食：需要“叉子”叉子：不同種組合資源哲學(xué)家活動：哲學(xué)家活動(包含資源活動)Repeat

思考取左叉取右叉

進食放左叉放右叉Untilfalse哲學(xué)家活動(包含資源活動)哲學(xué)家問題的解法：VARforkArray[0..4]ofSemophore=(1,1,1,1,1)philosopher(i):beginrepeatTHINK;P(fork[i])P(fork[i+1]mod5)EATV(fork[i])V(fork[i+1]mod5)untilfalseend;死鎖情況：每位哲學(xué)家拿到左叉，等待右叉。哲學(xué)家問題的解法：死鎖情況：每位哲學(xué)家拿到左叉，等待右叉。解決死鎖的辦法：限制最多4位哲學(xué)家同時進餐，VARforkArray[0..4]ofSemophore=(1,1,1,1,1)VARcount:semophore=4philosopher(i):beginrepeatTHINK;P(count)P(fork[i])P(fork[i+1]mod5)EATV(fork[i+1]mod5)V(fork[i])