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

§2.3進(jìn)程同步

進(jìn)程同步的主要任務(wù)：對(duì)多個(gè)相關(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互斥：同步的特例，多個(gè)操作決不能同時(shí)執(zhí)行，如:進(jìn)程Ａ和進(jìn)程Ｂ共用一臺(tái)打印機(jī)的情形。同步：對(duì)于進(jìn)程操作的時(shí)間順序所加的某種限制，如輸入進(jìn)程I和計(jì)算進(jìn)程C共用一個(gè)緩沖區(qū)的情形,輸入進(jìn)程I必須在計(jì)算進(jìn)程C之前完成?！?.3進(jìn)程同步A打印機(jī)BI緩沖區(qū)C2

必須互斥訪問(wèn)的資源稱為臨界資源（或者說(shuō)一次僅允許一個(gè)進(jìn)程訪問(wèn)的資源）引起不可再現(xiàn)性是因?yàn)榕R界資源沒(méi)有互斥訪問(wèn)。

例如，打印機(jī)、變量、表格、隊(duì)列等。2.臨界資源—互斥訪問(wèn)例如：有兩個(gè)進(jìn)程共享一個(gè)count變量，當(dāng)兩個(gè)進(jìn)程按以下順序執(zhí)行時(shí)：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都有各自對(duì)count做了加1操作，但最后的count卻是增加1，即發(fā)生了與執(zhí)行順序有關(guān)的錯(cuò)誤。

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

2.臨界資源—互斥訪問(wèn)4

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

entrysection

criticalsection

exitsection

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

空閑讓進(jìn)

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

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

1、信號(hào)量機(jī)制

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

92.3.2解決方法——信號(hào)量機(jī)制

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

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

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

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

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

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

信號(hào)量值

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

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

定義：

typesemaphore=recordvalue：integer；信號(hào)量值

L：listofprocess

信號(hào)量等待隊(duì)列指針

end；12定義：VARS：Semaphore；

1.P操作（wait原語(yǔ)）每作一次P操作，申請(qǐng)分配一個(gè)單位的資源。

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

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

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

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

則釋放S等待隊(duì)列中的一個(gè)進(jìn)程，使之轉(zhuǎn)為就緒狀態(tài)。2記錄型信號(hào)量P、V操作原語(yǔ)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記錄型信號(hào)量14

說(shuō)明：

①

S.Value>0

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

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

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

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

考慮：

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

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

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

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

17

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

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

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

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

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

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

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

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

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

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

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

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

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

）關(guān)系。

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

）。

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

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

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

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

問(wèn)題？

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

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

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

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

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

empty—

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

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

定義消費(fèi)者進(jìn)程同步信號(hào)量：

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

0≤full≤nfull初值為；分析

n0

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

3、定義：

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

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

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

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

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

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

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

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

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

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

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

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

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

生產(chǎn)一個(gè)產(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;

消費(fèi)者進(jìn)程：

P（full）；

P（mutex）；

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

out：=（out+1）modn；

V（mutex）；

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

...

P（empty）；

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

in：=（in+1）modn；

V（mutex）；

V（full）；

消費(fèi)者進(jìn)程：

P（full）；

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

out：=（out+1）modn；

V（mutex）；

V（empty）；問(wèn)題1。能否交換兩個(gè)P操作？能否交換兩個(gè)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。每個(gè)程序中用于實(shí)現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對(duì)地出現(xiàn)。2。對(duì)資源信號(hào)量empty和full的wait和signal操作，同樣需要成對(duì)地出現(xiàn)，但處于不同的程序中。3。在每個(gè)程序中的多個(gè)wait操作順序不能顛倒。應(yīng)先執(zhí)行對(duì)資源信號(hào)量的wait操作，再執(zhí)行對(duì)互斥信號(hào)量的wait操作，否則可能引起進(jìn)程死鎖。4.在每個(gè)程序中的多個(gè)signal操作順序無(wú)要求。392.4經(jīng)典進(jìn)程的同步問(wèn)題2.利用AND信號(hào)量解決生產(chǎn)者——消費(fèi)者問(wè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)程的同步問(wèn)題2.利用AND信號(hào)量解決生產(chǎn)者——消費(fèi)者問(wè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)程的同步問(wèn)題403212.4.2哲學(xué)家進(jìn)餐問(wèn)題

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

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

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

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

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

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

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

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

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

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

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

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

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

在存儲(chǔ)器中劃出了一塊共享存儲(chǔ)區(qū)，諸進(jìn)程可通過(guò)對(duì)共享存儲(chǔ)區(qū)中數(shù)據(jù)的讀或?qū)憗?lái)實(shí)現(xiàn)通信。

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

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

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

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

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

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

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

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

所謂“管道”，是指用于連接一個(gè)讀進(jìn)程和一個(gè)寫進(jìn)程以實(shí)現(xiàn)他們之間通信的一個(gè)共享文件，又名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