第2章進程管理下

§2.3進程同步

進程同步的主要任務：對多個相關進程在執(zhí)行次序上進行協(xié)調，以使并發(fā)執(zhí)行的諸進程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。2.3.1進程同步的基本概念1.兩種形式的制約關系(1)間接相互制約關系源于資源共享（互斥方式）(2)直接相互制約關系源于進程合作（同步方式）1互斥：同步的特例，多個操作決不能同時執(zhí)行，如:進程Ａ和進程Ｂ共用一臺打印機的情形。同步：對于進程操作的時間順序所加的某種限制，如輸入進程I和計算進程C共用一個緩沖區(qū)的情形,輸入進程I必須在計算進程C之前完成?！?.3進程同步A打印機BI緩沖區(qū)C2

必須互斥訪問的資源稱為臨界資源（或者說一次僅允許一個進程訪問的資源）引起不可再現(xiàn)性是因為臨界資源沒有互斥訪問。

例如，打印機、變量、表格、隊列等。2.臨界資源—互斥訪問例如：有兩個進程共享一個count變量，當兩個進程按以下順序執(zhí)行時：P1 P2n1=count; n2=count;n1=n1+1; n2=n2+1;count=n1; count=n2;假定count初值為0，如果先執(zhí)行P1，后執(zhí)行P2，最后count變量的值為23但如果按下列順序并發(fā)執(zhí)行：P1：n1=count;P2：n2=count;P1：n1=n1+1;count=n1;P2：n2=n2+1;count=n2;

盡管P1與P2都有各自對count做了加1操作，但最后的count卻是增加1，即發(fā)生了與執(zhí)行順序有關的錯誤。

為防止這種錯誤，對臨界資源count必須互斥訪問。即P1訪問count變量，P2就不能訪問；當P1訪問結束時，才允許P2訪問count變量。

2.臨界資源—互斥訪問4

每個進程中訪問臨界資源的那段代碼對欲訪問的臨界資源進行檢查，………………進入?yún)^(qū)若此刻未被訪問，設正在訪問的標志訪問臨界資源………………臨界區(qū)將正在訪問的標志恢復為未被訪問的標志………退出區(qū)其余部分………………剩余區(qū)repeat

entrysection

criticalsection

exitsection

remaindersectionuntilfalse3.臨界區(qū)53.臨界區(qū)對臨界資源設一訪問標志flag對flag檢查，看是否被訪問？該進程可以進入臨界區(qū)，并設置已被訪問標志該進程不能進入臨界區(qū)YN進入臨界區(qū)流程64.同步機制應遵循的準則

空閑讓進

無進程處于臨界區(qū)內時，可讓一個申請進入該臨界區(qū)的進程進入。忙則等待

臨界區(qū)內有進程時，申請進入臨界區(qū)的進程必須等待。有限等待進程進入臨界區(qū)的請求，必須在有限的時間內滿足。讓權等待等待進入臨界區(qū)的進程，必須立即放CPU。7信號量機制中心街道樓宇1小區(qū)A小區(qū)B城市公路進程82.3.2解決方法——信號量機制

1、信號量機制

1965年荷蘭學者Dijkstra提出信號量機制，是一個卓有成效的進程同步機制。2、信號量的發(fā)展整型信號量、記錄型信號量、AND型信號量和信號量集機制。

92.3.2解決方法——信號量機制

信號量是一種數(shù)據(jù)結構信號量的值與相應資源的使用情況有關信號量的值僅由P、V操作改變10整型信號量整型量，除初始化外，僅能通過兩個原子操作來訪問。P操作wait(S):

WhileS<=0dono-op; S:=S-1;V操作signal(S):

S:=S+1;P、V操作是原子操作，不可中斷。信號量S：表示資源個數(shù)

S>0表示可獲得這個臨界資源的進程個數(shù)

S<=0表示等待該臨界資源的進程個數(shù)P操作：申請資源V操作：釋放資源2.3.2解決方法——信號量機制11整型信號量未遵循“讓權等待”原則，導致忙等

引入整型變量value(代表資源數(shù)目)、進程鏈表指針L(鏈接所有等待進程)2記錄型信號量其中：

信號量值

—表示某種資源的數(shù)量。

等待隊列指針—當信號量值為負時，表示該類資源已分配完，等待該類資源的進程排在等待隊列中。L為指向該信號量等待隊列的指針。

定義：

typesemaphore=recordvalue：integer；信號量值

L：listofprocess

信號量等待隊列指針

end；12定義：VARS：Semaphore；

1.P操作（wait原語）每作一次P操作，申請分配一個單位的資源。

P（S）—對信號量S進行P操作。

①S.value：=S.Value-1；②若S.Value≥0進程繼續(xù)執(zhí)行。若S.Value<0進程阻塞，并進入等待隊列（L）。2.V操作（Signal原語）

V（S）—對信號量S進行V操作，釋放一個單位的資源。①S.value：=S.Value+1；②若S.Value>0

進程繼續(xù)執(zhí)行。若S.Value≤0

則釋放S等待隊列中的一個進程，使之轉為就緒狀態(tài)。2記錄型信號量P、V操作原語13

P操作

ProcedureP（s）

Vars：semaphore；

begins.value：=s.value-1；ifs.value0thenblock（s.L）;

end；

V操作

ProcedureV（s）

Vars：semaphore；

begins.value：=s.value+1；ifs.value≤0thenwakeup（s.L）;

end；P、V操作的算法描述2記錄型信號量14

說明：

①

S.Value>0

時，其值表示某類資源可用數(shù)量。

S.Value≤0時，其絕對值表示在信號量隊列中等待該資源的進程數(shù)。②

P、V操作有嚴格的不可分割性；執(zhí)行過程不允許中斷；

③P、V操作成對出現(xiàn)。（根據(jù)同步機制的原則，分析P、V操作的特點，）？問題？如何使用P、V操作實現(xiàn)同步機制？實現(xiàn)同步機制基本思想是：加鎖、解鎖

考慮：

如何控制互斥地使用臨界資源？

如何控制進程并發(fā)執(zhí)行的時序？2記錄型信號量153信號量的應用

1.利用信號量實現(xiàn)進程互斥例1：用P（wait）、V（signal）原語實現(xiàn)3個進程（A、B、C）互斥進入臨界區(qū)。設互斥信號量mutex=1A B C…… …… ……P(mutex) P(mutex) P(mutex)CSA CSB CSCV(mutex) V(mutex) V(mutex)…… …… ……16

序號調用進程被調用操作進入臨界區(qū)運行的進程mutex值在mutex上等待的進程112AP(mutex)A03BP(mutex)A-1B4CP(mutex)A-2BC5AV(mutex)B-1C6BV(mutex)C07CV(mutex)13信號量的應用

17

例2：以計算進程C和打印進程P為例來描述兩個進程的合作關系，試用P、V原語實現(xiàn)。設：計算進程與打印進程共用一個緩沖區(qū)，為此可設置兩個信號量：full表示緩沖區(qū)滿，令full=0；empty表示緩沖區(qū)空，令empty=13信號量的應用

18計算進程與打印進程的P、V描述如下:計算進程C…產生一個數(shù)據(jù)P(empty);往緩沖區(qū)送數(shù)據(jù)V(full);…打印進程P…P(full);從緩沖區(qū)取數(shù)V(empty);輸出結果

…3信號量的應用

19S1S2S3S4S5S6abcdegf圖2－10前趨圖舉例例3:S1,S2,S3,S4,S5,S6為一組合作進程,其前趨圖如圖,試用P、V原語實現(xiàn)這6個進程的同步。

3信號量的應用

20Vara,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;Begin parbegin beginS1;signal(a);signal(b);end; beginwait(a);S2;signal(c);signal(d);end; beginwait(b);S3;signal(e);end; beginwait(c);S4;signal(f);end; beginwait(d);S1;signal(g);end; beginwait(e);wait(f);wait(g);S6;end; parendend3信號量的應用

21思考：利用信號量實現(xiàn)前趨關系(p57)P1P3P4P2P5P63信號量的應用

222.3進程同步4.AND型信號量上述進程互斥問題，多個進程共享一個臨界資源。兩個進程A和B，共享數(shù)據(jù)D和E，為其分別設置互斥信號量Dmutex和Emutex，初值為1。ProcessA：

wait(Dmutex);wait(Emutex);ProcessB：

wait(Emutex);wait(Dmutex);ProcessA：wait(Dmutex);于是Dmutex=0ProcessB：wait(Emutex);于是Emutex=0ProcessA：wait(Emutex);于是Emutex=-1A阻塞ProcessB：wait(Dmutex);于是Dmutex=-1B阻塞設執(zhí)行過程為共享的資源越多，死鎖的可能越大232.3進程同步

AND同步機制的基本思想：將進程在整個運行過程中需要的所有資源，一次性全部分配給進程，待進程使用完后再一起釋放。只要尚有一個資源未能分配給進程，其他所有可能為之分配的資源，也不分配給它。即對臨界資源的分配采取原子操作。Swait(S1,S2,…,Sn)ifS1>=1and…andSn>=1thenfori:=1tondoSi:=Si-1;endforelsePlacetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi<1,andsettheprogramcountofthisprocesstothebeginningofSwaitoperationendifSsignal(S1,S2,…,Sn)fori:=1tondoSi:=Si+1;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueueendfor245信號量集(略)251．P、V操作是

。A．兩條低級進程通信原語B．兩組不同的機器指令C．兩條系統(tǒng)調用命令D．兩條高級進程通信原語2．若P、V操作的信號量S初值為2，當前值為－1，則表示有

等待進程。A．0個B．1個C．2個D．3個3．用P、V操作管理臨界區(qū)時，信號量的初值應定義為

。A．一1B．0C．1D．任意值4．對于兩個并發(fā)進程，設互斥信號量為mutex，若mutex=0，則

。A．表示沒有進程進入臨界區(qū)B．表示有一個進程進入臨界區(qū)C．表示有一個進程進入臨界區(qū)，另一個進程等待進入D．表示有兩個進程進入臨界區(qū)答：ABCB習題265．設有5個進程共享一個互斥段，如果最多允許有3個進程同時進入互斥段，則所采用的互斥信號量的初值應是

。A．5B．3C．1D．06.兩個進程合作完成一個任務，在并發(fā)執(zhí)行中，一個進程要等待其合作伙伴發(fā)來信息，或者建立某個條件后再向前執(zhí)行，這種關系是進程間的（

）關系。

A.同步B.互斥C.競爭D.合作7.在一段時間內，只允許一個進程訪問的資源稱為（

）。

A.共享資源B.臨界區(qū)C.臨界資源D.共享區(qū)8.系統(tǒng)中有N個進程，則進程就緒隊列中最多有()個進程。

A．NB．N-1C．N-2D．N-39．程序和與它有關的進程的對應關系是（）。A一對一B一對多C多對一D多對多習題答：BACBB271.進程A和進程B都要使用系統(tǒng)中同一臺打印機，為了保證打印結果的正確性，兩個進程要先后分別使用打印機，這屬于進程的同步關系。（×）2.臨界資源是指在一段時間內，一次僅允許一個進程使用的共享資源。（√）3.信號量機制是一種有效的實現(xiàn)進程同步與互斥的工具。信號量只能由P、V操作來改變。（√）4.V操作是對信號量執(zhí)行加1操作，意味著釋放一個單位資源，如果加1后信號量的值小于等于零，則從等待隊列中喚醒一個進程，現(xiàn)進程變?yōu)樽枞麪顟B(tài)，否則現(xiàn)進程繼續(xù)進行。（×）5.利用信號量的P，V操作，進程之間可以交換大量信息。（×）（×）6．用戶為每個自己的進程創(chuàng)建PCB，并控制進程的執(zhí)行過程。（√）7．原語是一種不可分割的操作。（√）8．對臨界資源應采取互斥訪問方式來實現(xiàn)共享。習題282.3.4管程機制一種新的進程同步工具管程的定義:

系統(tǒng)中的各種硬件和軟件資源,均可用數(shù)據(jù)結構加以抽象的描述,即用少量信息和對該資源所執(zhí)行的操作來表征該資源,而忽略它們的內部結構和實現(xiàn)細節(jié).

我們把這樣一組相關的數(shù)據(jù)結構和過程一并稱為管程（資源管理程序，如隊列的定義及其操作）.Hansan對管程的定義（P57）292.4經典進程同步問題2.4.1生產者－－消費者問題2.4.2哲學家進餐問題2.4.3讀者－－寫者問題30

問題？

一組生產者進程

Pi（P1，P2，…Pk）一組消費者進程

Ci（C1，C2，…Cm）互斥使用由n個緩沖區(qū)組成的緩沖池。inoutCiPi一、生產者—消費者問題31

1、同步關系：當緩沖池放滿產品時生產者必須等待。

定義生產者進程同步信號量：

empty—

表示空閑緩沖區(qū)數(shù)。

0≤empty≤nempty初值為；當緩沖池空時，消費者進程必須等待。

定義消費者進程同步信號量：

full—表示有產品的緩沖區(qū)數(shù)。

0≤full≤nfull初值為；分析

n0

2、互斥關系：兩組進程中的每個進程必須互斥的使用緩沖區(qū)。定義公共互斥信號量：mutex初值為1

3、定義：

in，out分別表示首空緩沖區(qū)序號及首滿緩沖區(qū)序號。inoutCiPi一、生產者—消費者問題32

empty—表示空閑緩沖區(qū)數(shù)。初值為n

empty=0緩沖區(qū)全滿，生產者進程不能工作。

full—表示有產品的緩沖區(qū)數(shù)。初值為0

full=0緩沖區(qū)全空，消費者進程不能工作。inoutCiPi一、生產者—消費者問題33

empty—表示空閑緩沖區(qū)數(shù)。初值為n

empty=0緩沖區(qū)全滿，生產者進程不能工作。

full—表示有產品的緩沖區(qū)數(shù)。初值為0

full=0緩沖區(qū)全空，消費者進程不能工作。outCiPiin一、生產者—消費者問題34

empty—表示空閑緩沖區(qū)數(shù)。初值為n

empty=0緩沖區(qū)全滿，生產者進程不能工作。

full—表示有產品的緩沖區(qū)數(shù)。初值為0

full=0緩沖區(qū)全空，消費者進程不能工作。inoutPiCi一、生產者—消費者問題35生產者—消費者問題算法：生產者進程：

生產一個產品m；

...

P（empty）；

P（mutex）；

將產品m放入緩沖區(qū)；

in：=（in+1）modn；

V（mutex）；

V（full）；

Varmutex，empty，full：semaphore:=1,n,0；

buffer：array[0..n-1]ofitem;in,out:0..n-1:=0,0;

消費者進程：

P（full）；

P（mutex）；

從緩沖區(qū)取產品m；

out：=（out+1）modn；

V（mutex）；

V（empty）；檢查有否空緩沖區(qū)檢查緩沖區(qū)中有無進程釋放緩沖區(qū)通知消費者進程使用檢查緩沖區(qū)中是否有產品檢查緩沖區(qū)中有無進程釋放緩沖區(qū)通知生產者進程使用36生產者—消費者問題算法：生產者進程：生產一個產品m；

...

P（empty）；

P（mutex）；將產品m放入緩沖區(qū)；

in：=（in+1）modn；

V（mutex）；

V（full）；

消費者進程：

P（full）；

P（mutex）；從緩沖區(qū)取產品m；

out：=（out+1）modn；

V（mutex）；

V（empty）；問題1。能否交換兩個P操作？能否交換兩個V操作？為什么？2。如果缺少操作：P（empty）或P(full）,結果如何？37intin=0,out=0;itembuffer[n];semaphoremutex=1,empty=n,full=0;voidproceducer(){ do{ produceraniteminnexp;…

wait(empty);wait(mutex);buffer(in):=nexp;in=(in+1)%n;

signal(mutex);signal(full);

}while(TRUE);}

38

void

consumer(){

do{ wait(full);wait(mutex);nextc:=buffer[out];out=(out+1)%n;

signal(mutex);signal(empty);consumetheiteminnexc;……}while(TRUE);}voidmain(){cobegin proceducer();consumer();coend}注意：1。每個程序中用于實現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對地出現(xiàn)。2。對資源信號量empty和full的wait和signal操作，同樣需要成對地出現(xiàn)，但處于不同的程序中。3。在每個程序中的多個wait操作順序不能顛倒。應先執(zhí)行對資源信號量的wait操作，再執(zhí)行對互斥信號量的wait操作，否則可能引起進程死鎖。4.在每個程序中的多個signal操作順序無要求。392.4經典進程的同步問題2.利用AND信號量解決生產者——消費者問題intin=0,out=0;itembuffer[n];semaphoremutex=1,empty=n,full=0;voidproceducer(){ do{ produceraniteminnexp;…

Swait(empty,mutex);buffer(in):=nexp;in=(in+1)%n;

Ssignal(mutex,full);

}while(TRUE);}

402.4經典進程的同步問題2.利用AND信號量解決生產者——消費者問題void

consumer(){

do{

Swait(full,mutex);nextc:=buffer[out];out=(out+1)%n;

Ssignal(mutex,empty);

consumetheiteminnexc;……}while(TRUE);}

412.4經典進程的同步問題403212.4.2哲學家進餐問題

五個哲學家共用一張圓桌，分別坐在周圍的五張椅子上，在桌子上有五只碗和五只筷子，他們的生活方式是交替地進行思考和進餐。平時，一個哲學家進行思考，饑餓時便試圖取用其左右最靠近他的筷子，只有在他拿到兩只筷子時才能進餐。進餐畢，放下筷子繼續(xù)思考?？梢姡合噜弮晌徊荒芡瑫r進餐；最多只能有兩人同時進餐。422.4經典進程的同步問題2.4.2哲學家進餐問題分析筷子是臨界資源，在一段時間內只允許一個哲學家使用用一個信號量表示一支筷子，由這五個信號量構成信號量組。Varchopstick:array[0,…,4]ofsemaphore;所有的信號量被初始化為1432.4經典進程的同步問題1.利用記錄型信號量解決哲學家進餐問題

放在桌子上的筷子是臨界資源，在一段時間內只允許一個哲學家使用。為實現(xiàn)對筷子的互斥使用，用一個信號量表示一只筷子，五個信號量構成信號量數(shù)組。

semaphorechopstick[5]={1,1,1,1,1};

所有信號量均被初始化為1。44第i位哲學家的活動可描述為：

do{wait(chopstick[i]);wait(chopstick[(i+1)%5]);…//eat;…signal(chopstick[i]);signal(chopstick[(i+1)%5]);…//think;}while[TRUE];當哲學家進餐完畢，先放下左邊的筷子，再放下右邊的筷子。當哲學家饑餓時，總是先拿左邊的筷子，再拿右邊的筷子。452.4經典進程的同步問題算法雖能保證相鄰兩位不會同時進餐，但有可能引起死鎖。問題：假如五位哲學家同時饑餓而各自拿起左邊的筷子時，就會使五個信號量chopstick均為0，當他們再試圖去拿右邊的筷子時，都將因無筷子可拿而無限等待。4032146解決方法：至多只允許有四位哲學家同時去拿左邊的筷子，最終能保證至少有一位哲學家能夠進餐，并在用畢后釋放出他用過的兩只筷子，從而使更多的哲學家能夠進餐。僅當哲學家的左右兩只筷子均可用時，才允許他拿起筷子進餐。規(guī)定奇數(shù)號哲學家先拿他左邊的筷子，然后再去拿右邊的筷子；偶數(shù)號哲學家則相反。472.4經典進程的同步問題2.利用AND信號量機制解決哲學家進餐問題在哲學家進餐問題中，要求每個哲學家先獲得兩個臨界資源(筷子)后方能進餐。本質上是AND同步問題。48semaphorechopstickchopstick[5]={1,1,1,1,1};do{……//think;……Swait(chopstick[(i+1)%5],chopstick[i]);…… //eat; ……Ssignal(chopstick[(i+1)%5],chopstick[i]);

}whiletrue;492.4.3讀者——寫者問題50讀者——寫者問題問題描述一個數(shù)據(jù)文件或記錄可被多個進程共享。其中，有些進程要求讀；而另一些進程要求寫或修改。只要求讀的進程稱為“Reader進程”，其它進程稱為“Writer進程”。允許多個Reader進程同時讀一個共享對象，不允許一個Writer進程和其它Reader進程或Writer進程同時訪問共享對象。所謂讀者——寫者問題是指保證一個Writer進程必須與其它進程互斥地訪問共享對象的同步問題。51（2）用P、V操作實現(xiàn)讀者-寫者進程同步問題①設wmutex=1表示讀者進程與寫者進程，寫者進程與寫者進程之間的互斥信號量。②rcount=0；由于讀者進程與讀者進程之間不互斥，但要對多個讀者讀數(shù)據(jù)庫文件進行計數(shù)。③rmutex=1；由于rcount是臨界資源，因此在讀的過程中，需要對rcount變量進行互斥訪問。通過上述分析，讀者進程、寫者進程的同步描述如下：讀者——寫者問題52讀者——寫者問題53分析：①在讀者進程中，可以有多個讀者在讀數(shù)據(jù)庫，對讀者進程的計數(shù)要互斥，以免發(fā)生錯誤，同時注意當?shù)谝粋€讀者進程讀時，一定要封鎖寫者進程。當讀者進程逐漸撤離時，也要對計數(shù)變量進行互斥操作，若當前為最后一個讀者進程讀，則喚醒寫者進程。②當寫者進程在進行寫操作時，可以封鎖其它讀者或寫者進程，當寫操作完成時，喚醒其它讀者或寫者進程。讀者——寫者問題54例題例1:桌子上有一只盤子，最多可容納兩個水果，每次只能放入或取出一個水果，爸爸專向盤子中放蘋果（apple），媽媽專向盤子中放橘子（orange），兒子專等吃盤子中的橘子，女兒專等吃盤子中的蘋果，請用P.V操作來實現(xiàn)爸爸、媽媽、兒子、女兒間的同步與互斥關系。

Varmutex,empty,apple,orange:semphore:=1,2,0,0;爸爸媽媽女兒兒子repeat repeatrepeatrepeatP（empty）P（empty）P（apple）P（orange）

P（mutex）P（mutex）P（mutex）P（mutex）放蘋果放橘子取蘋果取橘子

V（mutex）V（mutex）V（mutex）V（mutex）

V（apple）V（orange）V（empty）V（empty）untilfalse;untilfalse;untilfalse;untilfalse;55例題例2:桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果，也可向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定當盤空時一次只能放一只水果供吃者取用，請用P、V原語實現(xiàn)爸爸、兒子、女兒三個并發(fā)進程的同步。561．在生產者—消費者問題中，能否將生產者進程的wait(empty)和wait(mutex)語句互換，為什么？不能。因為這樣可能導致系統(tǒng)死鎖。當系統(tǒng)中沒有空緩沖時，生產者進程的wait(mutex)操作獲取了緩沖隊列的控制權，而wait(empty)導致生產者進程阻塞，這時消費者進程也無法執(zhí)例題572.簡述進程的幾種狀態(tài)和引起狀態(tài)轉換的典型原因，以及相關的操作原語。進程的基本狀態(tài)有：新、就緒，阻塞，執(zhí)行、掛起和終止六種。新到就緒：交換，創(chuàng)建原語就緒到執(zhí)行：進程調度執(zhí)行到阻塞：I/O請求，阻塞原語阻塞到就緒：I/O完成，喚醒原語執(zhí)行到就緒：時間片完阻塞到掛起：掛起原語掛起到就緒：喚醒原語執(zhí)行到終止：進程執(zhí)行完畢例題58

2.三個進程P1、P2、P3互斥使用一個包含N（N>0）個單元的緩沖區(qū)。P1每次用produce（）生成一個正整數(shù)并用put（）送入緩沖區(qū)某一空單元中；P2每次用getodd（）從該緩沖區(qū)中取出一個奇數(shù)并用countodd（）統(tǒng)計奇數(shù)個數(shù)；P3每次用geteven（）從該緩沖區(qū)中取出一個偶數(shù)并用counteven（）統(tǒng)計偶數(shù)個數(shù)。請用信號量機制實現(xiàn)這三個進程的同步與互斥活動，并說明所定義的信號量的含義。要求用偽代碼描述。

59定義信號量S1控制P1與P2之間的同步；S2控制P1與P3之間的同步；empty控制生產者與消費者之間的同步；mutex控制進程間互斥使用緩沖區(qū)。程序如下：

Var

s1=0,s2=0,empty=N,mutex=1;

Parbegin

P1:begin

X=produce();

P(empty);

P(mutex);

Put();

If

x%2==0

V(s2);

else

V(s1);

V(mutex);

end.

P2:begin

P(s1);

P(mutex);

Getodd();

Countodd():=countodd()+1;

V(mutex);

V(empty);

end.

P3:begin

P(s2)

P(mutex);

Geteven();

Counteven():=counteven()+1;

V(mutex);

V(empty);

end.

Parend.

602.5進程通信進程通信是指進程之間的信息交換。進程之間的互斥和同步——低級通信（因其所交換的信息最少）如在進程互斥中，進程通過只修改信號量來向其它進程表明臨界資源是否可用在生產者-消費者問題中，生產者通過緩沖池將所生產的產品傳送給消費者。信號量機制作為通信工具的缺點：(1)效率低(2)通信對用戶不透明。低級通信中共享數(shù)據(jù)的設置，數(shù)據(jù)的傳送，進程的互斥都是由程序員去實現(xiàn)，操作系統(tǒng)只提供共享存儲器，因此非常不方便612.5進程通信

高級進程通信是指用戶可直接利用操作系統(tǒng)所提供的一組通信命令，高效地傳送大量數(shù)據(jù)的一種通信方式。操作系統(tǒng)隱藏了進程通信的細節(jié)，對用戶透明，減少了通信程序編制上的復雜性。622.5進程通信2.5.1進程通信的類型低級通信高級通信(三大類)共享存儲器系統(tǒng)消息傳遞系統(tǒng)（主要用于網(wǎng)絡）管道通信（首創(chuàng)于Unix系統(tǒng)）

632.5進程通信1.共享存儲器系統(tǒng)在共享存儲器系統(tǒng)中，相互通信的進程共享某些數(shù)據(jù)結構或共享存儲區(qū)，進程之間能夠通過這些空間進行通信。(1)基于共享數(shù)據(jù)結構的通信方式(2)基于共享存儲區(qū)的通信方式642.5進程通信

基于共享數(shù)據(jù)結構的通信方式在這種通信方式中，諸進程公用某些數(shù)據(jù)結構，借以實現(xiàn)諸進程間的信息交換。

程序員：公用數(shù)據(jù)結構的設置及對進程間同步的處理操作系統(tǒng)：提供共享存儲器(如緩沖池、緩沖區(qū))

特點：低效，只適合傳遞相對少量的數(shù)據(jù)，屬于低級通信。652.5進程通信

基于共享存儲區(qū)的通信方式

在存儲器中劃出了一塊共享存儲區(qū)，諸進程可通過對共享存儲區(qū)中數(shù)據(jù)的讀或寫來實現(xiàn)通信。

通信過程：（1）向系統(tǒng)申請一個或多個分區(qū)（2）獲得分區(qū)后即可讀/寫.特點：高效，速度快。662.5進程通信2.消息傳遞系統(tǒng)（主要用于網(wǎng)絡）操作系統(tǒng)隱藏了通信的實現(xiàn)細節(jié)，簡化了通信程序編制的復雜性。信息單位：格式化的消息（報文）是目前的主要通信方式，分為直接通信方式、間接通信方式實現(xiàn)：一組通信命令（原語），具有透明性--->同步的實現(xiàn)。672.5進程通信直接通信方式發(fā)送進程直接把消息發(fā)送給目標進程發(fā)送進程和接收進程都以顯式方式分別提供對方的標識符系統(tǒng)提供兩條通信原語Send（Receiver,message）;Receive（Sender,message）;例如：Send(P2,m1);Receive(P1,m1);試用直接通信方式解決生產者-消費者問題682.5進程通信解決生產者一消費者問題repeat…produceaniteminnextp;…Send(consumer,nextp);untilfalse;

repeatReceive(producer,nextp);…Consumertheiteminnextc;untilfalse;692.5進程通信間接通信方式進程之間的通信需要通過某種中間實體，該實體用來暫存發(fā)送進程發(fā)送給目標進程的消息；接收進程則從該實體中取出對方發(fā)給自己的消息。這種中間實體成為信箱消息在信箱中可以安全地保存，只允許核準的目標用戶隨時讀取，故可實現(xiàn)非實時通信。70間接通信方式

信箱可由操作系統(tǒng)創(chuàng)建，也可由用戶進程創(chuàng)建，創(chuàng)建者是信箱的擁有者。據(jù)此，可把信箱分為以下三類。1)私用信箱用戶進程建立，作為該進程的一部分。擁有者有權讀消息，其它用戶只能發(fā)送。采用單向通信鏈路。進程結束時信箱也消失。2.5進程通信712)公用信箱它由操作系統(tǒng)創(chuàng)建。提供給系統(tǒng)中的所有核準進程使用。進程既發(fā)送也可取出。采用雙向通信鏈路的信箱來實現(xiàn)。系統(tǒng)運行期間始終存在。3)共享信箱它由某進程創(chuàng)建，創(chuàng)建指出共享進程(用戶)的名字。信箱的擁有者和共享者，都有權從信箱中取走發(fā)送給自己的消息。2.5進程通信72

在利用信箱通信時，在發(fā)送進程和接收進程之間，存在以下四種關系：

(1)一對一關系。這時可為發(fā)送進程和接收進程建立一條兩者專用的通信鏈路，使兩者之間的交互不受其他進程的干擾。

(2)多對一關系。允許提供服務的進程與多個用戶進程之間進行交互，也稱為客戶/服務器交互(client/serverinteraction)。

(3)一對多關系。允許一個發(fā)送進程與多個接收進程進行交互，使發(fā)送進程可用廣播方式，向接收者(多個)發(fā)送消息。

(4)多對多關系。允許建立一個公用信箱，讓多個進程都能向信箱中投遞消息；也可從信箱中取走屬于自己的消息。2.5進程通信733.管道通信（首創(chuàng)于Unix系統(tǒng)）

所謂“管道”，是指用于連接一個讀進程和一個寫進程以實現(xiàn)他們之間通信的一個共享文件，又名pipe文件。

向管道提供輸入的進程（稱寫進程），以字符流的形式將大量數(shù)據(jù)送入管道，而接受管道輸出的進程（讀進程）可從管道中接收數(shù)據(jù)。該方式首創(chuàng)于UNIX，它能傳送大量數(shù)據(jù)，被廣泛采用。

發(fā)送進程接收進程字符流方式寫入讀出先進先出順序2.5