第2章進(jìn)程管理下

§2.3進(jìn)程同步

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

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

例如，打印機、變量、表格、隊列等。2.臨界資源—互斥訪問例如：有兩個進(jìn)程共享一個count變量，當(dāng)兩個進(jìn)程按以下順序執(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í)行順序有關(guān)的錯誤。

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

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

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

entrysection

criticalsection

exitsection

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

空閑讓進(jìn)

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

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

1、信號量機制

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

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

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

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

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

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

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

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

信號量值

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

等待隊列指針—當(dāng)信號量值為負(fù)時，表示該類資源已分配完，等待該類資源的進(jìn)程排在等待隊列中。L為指向該信號量等待隊列的指針。

定義：

typesemaphore=recordvalue：integer；信號量值

L：listofprocess

信號量等待隊列指針

end；12定義：VARS：Semaphore；

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

P（S）—對信號量S進(jìn)行P操作。

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

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

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

則釋放S等待隊列中的一個進(jìn)程，使之轉(zhuǎn)為就緒狀態(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時，其絕對值表示在信號量隊列中等待該資源的進(jìn)程數(shù)。②

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

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

考慮：

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

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

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

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

17

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

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

…3信號量的應(yīng)用

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

3信號量的應(yīng)用

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信號量的應(yīng)用

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

222.3進(jìn)程同步4.AND型信號量上述進(jìn)程互斥問題，多個進(jìn)程共享一個臨界資源。兩個進(jìn)程A和B，共享數(shù)據(jù)D和E，為其分別設(shè)置互斥信號量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阻塞設(shè)執(zhí)行過程為共享的資源越多，死鎖的可能越大232.3進(jìn)程同步

AND同步機制的基本思想：將進(jìn)程在整個運行過程中需要的所有資源，一次性全部分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。只要尚有一個資源未能分配給進(jìn)程，其他所有可能為之分配的資源，也不分配給它。即對臨界資源的分配采取原子操作。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．兩條低級進(jìn)程通信原語B．兩組不同的機器指令C．兩條系統(tǒng)調(diào)用命令D．兩條高級進(jìn)程通信原語2．若P、V操作的信號量S初值為2，當(dāng)前值為－1，則表示有

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

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

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

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

）關(guān)系。

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

）。

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

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

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

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

問題？

一組生產(chǎn)者進(jìn)程

Pi（P1，P2，…Pk）一組消費者進(jìn)程

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

1、同步關(guān)系：當(dāng)緩沖池放滿產(chǎn)品時生產(chǎn)者必須等待。

定義生產(chǎn)者進(jìn)程同步信號量：

empty—

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

0≤empty≤nempty初值為；當(dāng)緩沖池空時，消費者進(jìn)程必須等待。

定義消費者進(jìn)程同步信號量：

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

0≤full≤nfull初值為；分析

n0

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

3、定義：

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

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

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

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

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

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

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

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

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

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

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

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

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

生產(chǎn)一個產(chǎn)品m；

...

P（empty）；

P（mutex）；

將產(chǎn)品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;

消費者進(jìn)程：

P（full）；

P（mutex）；

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

out：=（out+1）modn；

V（mutex）；

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

...

P（empty）；

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

in：=（in+1）modn；

V（mutex）；

V（full）；

消費者進(jìn)程：

P（full）；

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

out：=（out+1）modn；

V（mutex）；

V（empty）；問題1。能否交換兩個P操作？能否交換兩個V操作？為什么？2。如果缺少操作：P（empty）或P(full）,結(jié)果如何？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操作順序不能顛倒。應(yīng)先執(zhí)行對資源信號量的wait操作，再執(zhí)行對互斥信號量的wait操作，否則可能引起進(jìn)程死鎖。4.在每個程序中的多個signal操作順序無要求。392.4經(jīng)典進(jìn)程的同步問題2.利用AND信號量解決生產(chǎn)者——消費者問題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經(jīng)典進(jìn)程的同步問題2.利用AND信號量解決生產(chǎn)者——消費者問題void

consumer(){

do{

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

Ssignal(mutex,empty);

consumetheiteminnexc;……}while(TRUE);}

412.4經(jīng)典進(jìn)程的同步問題403212.4.2哲學(xué)家進(jìn)餐問題

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

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

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

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

do{wait(chopstick[i]);wait(chopstick[(i+1)%5]);…//eat;…signal(chopstick[i]);signal(chopstick[(i+1)%5]);…//think;}while[TRUE];當(dāng)哲學(xué)家進(jìn)餐完畢，先放下左邊的筷子，再放下右邊的筷子。當(dāng)哲學(xué)家饑餓時，總是先拿左邊的筷子，再拿右邊的筷子。452.4經(jīng)典進(jìn)程的同步問題算法雖能保證相鄰兩位不會同時進(jìn)餐，但有可能引起死鎖。問題：假如五位哲學(xué)家同時饑餓而各自拿起左邊的筷子時，就會使五個信號量chopstick均為0，當(dāng)他們再試圖去拿右邊的筷子時，都將因無筷子可拿而無限等待。4032146解決方法：至多只允許有四位哲學(xué)家同時去拿左邊的筷子，最終能保證至少有一位哲學(xué)家能夠進(jìn)餐，并在用畢后釋放出他用過的兩只筷子，從而使更多的哲學(xué)家能夠進(jìn)餐。僅當(dāng)哲學(xué)家的左右兩只筷子均可用時，才允許他拿起筷子進(jìn)餐。規(guī)定奇數(shù)號哲學(xué)家先拿他左邊的筷子，然后再去拿右邊的筷子；偶數(shù)號哲學(xué)家則相反。472.4經(jīng)典進(jìn)程的同步問題2.利用AND信號量機制解決哲學(xué)家進(jìn)餐問題在哲學(xué)家進(jìn)餐問題中，要求每個哲學(xué)家先獲得兩個臨界資源(筷子)后方能進(jìn)餐。本質(zhì)上是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ù)文件或記錄可被多個進(jìn)程共享。其中，有些進(jìn)程要求讀；而另一些進(jìn)程要求寫或修改。只要求讀的進(jìn)程稱為“Reader進(jìn)程”，其它進(jìn)程稱為“Writer進(jìn)程”。允許多個Reader進(jìn)程同時讀一個共享對象，不允許一個Writer進(jìn)程和其它Reader進(jìn)程或Writer進(jìn)程同時訪問共享對象。所謂讀者——寫者問題是指保證一個Writer進(jìn)程必須與其它進(jìn)程互斥地訪問共享對象的同步問題。51（2）用P、V操作實現(xiàn)讀者-寫者進(jìn)程同步問題①設(shè)wmutex=1表示讀者進(jìn)程與寫者進(jìn)程，寫者進(jìn)程與寫者進(jìn)程之間的互斥信號量。②rcount=0；由于讀者進(jìn)程與讀者進(jìn)程之間不互斥，但要對多個讀者讀數(shù)據(jù)庫文件進(jìn)行計數(shù)。③rmutex=1；由于rcount是臨界資源，因此在讀的過程中，需要對rcount變量進(jìn)行互斥訪問。通過上述分析，讀者進(jìn)程、寫者進(jìn)程的同步描述如下：讀者——寫者問題52讀者——寫者問題53分析：①在讀者進(jìn)程中，可以有多個讀者在讀數(shù)據(jù)庫，對讀者進(jìn)程的計數(shù)要互斥，以免發(fā)生錯誤，同時注意當(dāng)?shù)谝粋€讀者進(jìn)程讀時，一定要封鎖寫者進(jìn)程。當(dāng)讀者進(jìn)程逐漸撤離時，也要對計數(shù)變量進(jìn)行互斥操作，若當(dāng)前為最后一個讀者進(jìn)程讀，則喚醒寫者進(jìn)程。②當(dāng)寫者進(jìn)程在進(jìn)行寫操作時，可以封鎖其它讀者或?qū)懻哌M(jìn)程，當(dāng)寫操作完成時，喚醒其它讀者或?qū)懻哌M(jìn)程。讀者——寫者問題54例題例1:桌子上有一只盤子，最多可容納兩個水果，每次只能放入或取出一個水果，爸爸專向盤子中放蘋果（apple），媽媽專向盤子中放橘子（orange），兒子專等吃盤子中的橘子，女兒專等吃盤子中的蘋果，請用P.V操作來實現(xiàn)爸爸、媽媽、兒子、女兒間的同步與互斥關(guā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ī)定當(dāng)盤空時一次只能放一只水果供吃者取用，請用P、V原語實現(xiàn)爸爸、兒子、女兒三個并發(fā)進(jìn)程的同步。561．在生產(chǎn)者—消費者問題中，能否將生產(chǎn)者進(jìn)程的wait(empty)和wait(mutex)語句互換，為什么？不能。因為這樣可能導(dǎo)致系統(tǒng)死鎖。當(dāng)系統(tǒng)中沒有空緩沖時，生產(chǎn)者進(jìn)程的wait(mutex)操作獲取了緩沖隊列的控制權(quán)，而wait(empty)導(dǎo)致生產(chǎn)者進(jìn)程阻塞，這時消費者進(jìn)程也無法執(zhí)例題572.簡述進(jìn)程的幾種狀態(tài)和引起狀態(tài)轉(zhuǎn)換的典型原因，以及相關(guān)的操作原語。進(jìn)程的基本狀態(tài)有：新、就緒，阻塞，執(zhí)行、掛起和終止六種。新到就緒：交換，創(chuàng)建原語就緒到執(zhí)行：進(jìn)程調(diào)度執(zhí)行到阻塞：I/O請求，阻塞原語阻塞到就緒：I/O完成，喚醒原語執(zhí)行到就緒：時間片完阻塞到掛起：掛起原語掛起到就緒：喚醒原語執(zhí)行到終止：進(jìn)程執(zhí)行完畢例題58

2.三個進(jìn)程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)這三個進(jìn)程的同步與互斥活動，并說明所定義的信號量的含義。要求用偽代碼描述。

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

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

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

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

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

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

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

在存儲器中劃出了一塊共享存儲區(qū)，諸進(jìn)程可通過對共享存儲區(qū)中數(shù)據(jù)的讀或?qū)憗韺崿F(xiàn)通信。

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

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

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

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

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

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

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

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

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

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

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