13.1并發(fā)進(jìn)程3.2臨界區(qū)管理3.3信號量與PV操作3.4管程3.5進(jìn)程通信3.6死鎖3.7Linux同步機(jī)制和通信機(jī)制3.8Windows2003同步機(jī)制和通信機(jī)制習(xí)題作業(yè)：

第三章同步、通信與死鎖

2主要內(nèi)容：一、順序程序設(shè)計二、進(jìn)程的并發(fā)性三、與時間有關(guān)的錯誤四、進(jìn)程的交互（InteractionAmongProcesses）：協(xié)作和競爭3.1并發(fā)進(jìn)程

3一、順序程序設(shè)計(1)

1.程序執(zhí)行的順序性程序執(zhí)行的順序性包括兩個含義：程序內(nèi)部的順序性和程序外部的順序性一個進(jìn)程只有當(dāng)一個操作結(jié)束后，才能開始后繼操作，這稱為程序內(nèi)部的順序性。如果完成一個任務(wù)需要若干個不同的程序，這些不同程序在時間上按調(diào)用次序嚴(yán)格有序執(zhí)行，這稱為程序外部的順序性。傳統(tǒng)的程序設(shè)計方法是順序程序設(shè)計（SequentialProgramming），即把一個程序設(shè)計成一個順序執(zhí)行的程序模塊，不同程序也是按序執(zhí)行的。4一、順序程序設(shè)計(2)

2.順序程序設(shè)計的特點順序程序設(shè)計具有如下的特點：（1）程序執(zhí)行的順序性：一個程序在處理器上的執(zhí)行是嚴(yán)格按序的，即每個操作必須在下一個操作開始之前結(jié)束。（2）程序環(huán)境的封閉性：運(yùn)行程序獨占全部資源，除初始狀態(tài)外，其所處的環(huán)境由程序本身決定，只有程序本身的動作才能改變其環(huán)境。（3）程序執(zhí)行結(jié)果的確定性：程序執(zhí)行過程中允許被中斷，但這種中斷對程序的最終結(jié)果無影響，也即程序的執(zhí)行結(jié)果與它的執(zhí)行速率無關(guān)。5一、順序程序設(shè)計(2)

（4）計算過程的可再現(xiàn)性：在同一個數(shù)據(jù)集合上重復(fù)執(zhí)行一個程序會得到相同結(jié)果，因而錯誤也可以重現(xiàn)，便于分析。順序程序設(shè)計的串行性表明程序與計算是一一對應(yīng)的關(guān)系。6二、進(jìn)程的并發(fā)性(1)

1.進(jìn)程的并發(fā)性含義一組進(jìn)程的執(zhí)行在時間上是重疊的。所謂執(zhí)行在時間上是重疊的，是指一個進(jìn)程執(zhí)行的第一條指令是在另一個進(jìn)程執(zhí)行的最后一條指令完成之前開始的。例如：有兩個進(jìn)程A和B，進(jìn)程A執(zhí)行操作a1、a2、a3，進(jìn)程B執(zhí)行操作b1、b2、b3。進(jìn)程A和B順序（串行）執(zhí)行的一種情況：在單處理器上，進(jìn)程A執(zhí)行完，進(jìn)程B才開始執(zhí)行，它們的操作次序為：a1、a2、a3、b1、b2、b3。進(jìn)程A和B并發(fā)執(zhí)行的一種情況：在單處理器上，進(jìn)程A和B交替（交叉）執(zhí)行，它們交替（交叉）執(zhí)行的操作次序可能為：a1、b1、b2、a2、a3、b3。7二、進(jìn)程的并發(fā)性(2)

從宏觀上看，并發(fā)性反映一個時間段中幾個進(jìn)程都在同一處理器上處于運(yùn)行還未運(yùn)行結(jié)束的狀態(tài)。從微觀上看，任一時刻僅有一個進(jìn)程在處理器上運(yùn)行。并發(fā)的實質(zhì)是一個處理器在幾個進(jìn)程之間的多路復(fù)用，并發(fā)是對有限的物理資源強(qiáng)制行使多用戶共享，消除計算機(jī)部件之間的互等現(xiàn)象，以提高系統(tǒng)資源利用率。8二、進(jìn)程的并發(fā)性(2)

2.并發(fā)程序設(shè)計

在采用多道程序設(shè)計的系統(tǒng)中，利用了處理器與外圍設(shè)備、外圍設(shè)備與外圍設(shè)備之間的并行工作能力，提高了計算機(jī)的工作效率。怎樣才能充分利用處理器與外圍設(shè)備、外圍設(shè)備與外圍設(shè)備之間的并行工作能力呢？很重要的方面是取決于程序的編制。9二、進(jìn)程的并發(fā)性(3)

例如：程序P1=while(I<Count){input(data[I]，processdata[I]，outputdata[I])}對一批數(shù)據(jù)（Count組）進(jìn)行處理。Input涉及對輸入設(shè)備的操作，process涉及處理器的計算工作，output涉及對輸出設(shè)備的操作。程序的編制決定了程序的執(zhí)行一次僅能操作一臺物理設(shè)備，設(shè)備之間存在等待現(xiàn)象，循環(huán)迭代一次僅能處理一組數(shù)據(jù)。程序P1屬于串行執(zhí)行的程序。10二、進(jìn)程的并發(fā)性(3)

若對這個計算問題改用三個程序來實現(xiàn)：（I=J=K=1）輸入程序PI：while(I<Count){input(data[I++])，send}計算程序PC：while(J<Count){receive，process(data[J++])，send}輸出程序PO：while(K<Count){receive，output(data[K++])}send、receive為通信控制操作。11二、進(jìn)程的并發(fā)性(4)

輸入程序PI 計算程序PC 輸出程序POinput(data[1])input(data[2]) process(data[1])input(data[3]) process(data[2]) output(data[1])input(data[4]) process(data[3]) output(data[2])input(data[5]) process(data[4]) output(data[3]) process(data[5]) output(data[4]) output(data[5])12二、進(jìn)程的并發(fā)性(5)

并發(fā)程序設(shè)計：使一個程序分成若干個可同時執(zhí)行的程序模塊的方法稱為并發(fā)程序設(shè)計。(如果這些模塊都屬于一個進(jìn)程，在進(jìn)程內(nèi)部執(zhí)行,則稱為并發(fā)多線程程序設(shè)計;若模塊屬于不同進(jìn)程,則稱為并發(fā)多進(jìn)程程序設(shè)計.)每個程序模塊和它執(zhí)行時所處理的數(shù)據(jù)組成一個進(jìn)程。13二、進(jìn)程的并發(fā)性(5)

3.并發(fā)進(jìn)程分類并發(fā)進(jìn)程之間的關(guān)系分為兩類：無關(guān)的和交互的。無關(guān)的并發(fā)進(jìn)程：一組并發(fā)進(jìn)程分別在不同的變量集合上操作，一個進(jìn)程的執(zhí)行與其他并發(fā)進(jìn)程的進(jìn)展無關(guān)，即一個并發(fā)進(jìn)程不會改變另一個并發(fā)進(jìn)程的變量值。交互的并發(fā)進(jìn)程：一組并發(fā)進(jìn)程共享某些變量，一個進(jìn)程的執(zhí)行可能影響其他并發(fā)進(jìn)程的執(zhí)行結(jié)果。交互的并發(fā)進(jìn)程之間具有制約關(guān)系，這種交互必須是有控制的，否則會出現(xiàn)不正確的結(jié)果。14二、進(jìn)程的并發(fā)性(6)

并發(fā)進(jìn)程的無關(guān)性是進(jìn)程的執(zhí)行與時間無關(guān)的一個充分條件，又稱為Bernstein條件。Bernstein條件：設(shè)

R(pi)={a1,a2,…an}，程序pi在執(zhí)行期間引用的變量集

W(pi)={b1,b2,…bm}，程序pi在執(zhí)行期間改變的變量集

若兩個程序p1、p2的引用變量集與改變變量集交集之和為空集：R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={}則并發(fā)進(jìn)程的執(zhí)行與時間無關(guān)。15二、進(jìn)程的并發(fā)性(6)

并發(fā)可以是程序內(nèi)部語句之間或模塊之間的并發(fā)，也可以是程序與程序之間的并發(fā)。16二、進(jìn)程的并發(fā)性(7)

例如，一個程序PS有如下四條語句：

S1:a=x+y；S2:b=z+1；

S3:c=a–b；S4:w=c+1； 這四條語句的書寫次序定義了一個串行程序的執(zhí)行流程，也定義了程序的邏輯意義，程序執(zhí)行時將按S1、S2、S3、S4的次序執(zhí)行?，F(xiàn)在要將該程序PS進(jìn)行變換，得到一個并發(fā)程序PC，而且PC與PS等價。分析：該問題的核心是找出哪些語句能夠同時執(zhí)行，而這些語句同時執(zhí)行時對變量的訪問和修改合乎程序PS的原有邏輯。17二、進(jìn)程的并發(fā)性(8)

首先求出各條語句的引用變量集與改變變量集：R(S1)={x,y},R(S2)={z}，R(S3)={a,b}，R(S4)={c}；W(S1)={a},W(S2)=，W(S3)={c}，W(S4)={w}。然后分析語句間的Bernstein條件是否滿足。(1)考察S1與S2之間的變量引用關(guān)系。由于R(S1)∩W(S2)∪W(S1)∩R(S2)∪W(S1)∩W(S2)=，所以S1與S2可以同時執(zhí)行?？梢援嫵鋈缦碌那摆厛D：S1S218二、進(jìn)程的并發(fā)性(9)

(2)考察S3與S1、S2之間的變量引用關(guān)系。首先考察S3與末結(jié)點S2的變量引用關(guān)系。由于R(S3)∩W(S2)∪W(S3)∩R(S2)∪W(S3)∩W(S2)=，所以S3與S2只能串行執(zhí)行。再考察S3與末結(jié)點S1的變量引用關(guān)系。由于R(S3)∩W(S1)∪W(S3)∩R(S1)∪W(S3)∩W(S1)={a}，所以S3與S1只能串行執(zhí)行。可以畫出如下的前趨圖：

S1S2S319二、進(jìn)程的并發(fā)性(10)

(3)考察S4與S3、

S2、S1之間的變量引用關(guān)系。首先考察S4與末結(jié)點S3之間的變量引用關(guān)系。由于R(S4)∩W(S3)∪W(S4)∩R(S3)∪W(S4)∩W(S3)={c}，所以S4與S3只能串行執(zhí)行。根據(jù)關(guān)系的傳遞性，這時可不必分析S4與S1、S2之間的變量引用關(guān)系。

可以畫出如下的前趨圖：

S1S2S3S420二、進(jìn)程的并發(fā)性(11)

(4)依據(jù)四條語句之間的前趨關(guān)系圖，可以得到并發(fā)程序PC：

S1:a=x+y；S2:b=z+1；S3:c=a–b；S4:w=c+1；

21二、進(jìn)程的并發(fā)性(12)

4.并發(fā)程序設(shè)計的特征

采用并發(fā)程序設(shè)計技術(shù)構(gòu)造的一組程序模塊在執(zhí)行時具有如下特征：

(1)并行性：進(jìn)程的執(zhí)行在時間上可以重疊，在單處理器系統(tǒng)中可以并發(fā)執(zhí)行，在多處理器環(huán)境中可以并行執(zhí)行。

(2)共享性：并發(fā)進(jìn)程通過引用共享變量交換信號，從而，程序運(yùn)行的環(huán)境不再是封閉的。

(3)制約性：進(jìn)程并發(fā)執(zhí)行或協(xié)同完成同一任務(wù)時，會產(chǎn)生相互制約關(guān)系，必須對它們并發(fā)執(zhí)行的次序加以協(xié)調(diào)。

22二、進(jìn)程的并發(fā)性(12)

(4)交互性：由于并發(fā)進(jìn)程共享某些變量，所以，一個進(jìn)程的執(zhí)行可能影響其他進(jìn)程的執(zhí)行結(jié)果，程序運(yùn)行結(jié)果可能不確定，計算過程具有不可再現(xiàn)性。因此，這種交互必須是有控制的，否則會出現(xiàn)不正確的結(jié)果。

23二、進(jìn)程的并發(fā)性(13)

5.并發(fā)程序設(shè)計的優(yōu)點

(1)對于單處理器系統(tǒng),可讓處理器和各I/O設(shè)備、I/O設(shè)備與I/O設(shè)備同時工作,發(fā)揮硬部件的并行能力。(2)對于多處理器系統(tǒng),可讓各進(jìn)程在不同處理器上物理地并行，加快計算速度。(3)簡化了程序設(shè)計任務(wù)。24二、進(jìn)程的并發(fā)性(13)

6.采用并發(fā)程序設(shè)計的目的充分發(fā)揮硬件的并行性，提高系統(tǒng)效率。硬件能并行工作僅有了提高效率的可能性，硬部件并行性的實現(xiàn)需要軟件技術(shù)去利用和發(fā)揮，這種軟件技術(shù)就是并發(fā)程序設(shè)計。并發(fā)程序設(shè)計是多道程序設(shè)計的基礎(chǔ)，多道程序的實質(zhì)就是把并發(fā)程序設(shè)計引入到系統(tǒng)中。

25三、與時間有關(guān)的錯誤(1)

對于一組交互的并發(fā)進(jìn)程，若執(zhí)行的相對速度無法相互控制，則各種與時間有關(guān)的錯誤就可能出現(xiàn)。與時間有關(guān)的錯誤有兩種表現(xiàn)形式：結(jié)果不唯一永遠(yuǎn)等待1.結(jié)果不唯一例：購買飛機(jī)票問題：一個飛機(jī)訂票系統(tǒng)有兩個終端，分別運(yùn)行T1和T2。該系統(tǒng)的公共數(shù)據(jù)區(qū)Aj（j=1，2，…

…）中存放某月某日某次航班的余票數(shù)，X1、X2是T1、T2的局部變量。26三、與時間有關(guān)的錯誤(2)

processTi(i=1,2) varXi:integer;begin {按旅客定票要求找到Aj}；

Xi=Aj; ifXi>=1thenbeginXi=Xi-1;Aj=Xi;{輸出一張票}；end else{輸出票已售完}；end;27三、與時間有關(guān)的錯誤(3)

T1和T2并發(fā)執(zhí)行時導(dǎo)致出錯的一種可能情況如下：全局共享變量：Aj=m,m-1,m-1T1 T2局部變量：X1 =m,

m-1

局部變量：X2 =m,m-1X1=Aj; X2=Aj; X2=X2-1;Aj=X2;輸出一張票;X1=X1-1;Aj=X1;輸出一張票;這時出現(xiàn)了把同一張票出售給兩個旅客的情況，余票數(shù)本應(yīng)減少2張，但實際上余票數(shù)只減少1張。實例概括：兩個旅客同時搶購到了同一張機(jī)票，違背了一人一票一座的規(guī)矩，引起爭執(zhí)，這是一種錯誤的執(zhí)行結(jié)果。正確的做法：兩個人執(zhí)行購買操作時，只能一先一后，而不能同時。該順序操作的不能并發(fā)同時操作。并發(fā)進(jìn)程在關(guān)鍵片段需要保持必要的順序性。28三、與時間有關(guān)的錯誤(4)

2.永遠(yuǎn)等待

例：內(nèi)存管理問題：有2個并發(fā)進(jìn)程borrow和return分別負(fù)責(zé)申請和歸還主存資源，下面算法中，x表示現(xiàn)有空閑主存容量，B表示申請或歸還的主存量。并發(fā)進(jìn)程的算法及執(zhí)行描述如下：

procedureborrow(varB:integer)beginifB>xthen{申請進(jìn)程進(jìn)入等待隊列等主存資源}x:=x-B;{修改主存分配表，申請進(jìn)程獲得主存資源}end;29三、與時間有關(guān)的錯誤(5)

procedurereturn(varB:integer)beginx:=x+B;{修改主存分配表}{釋放等主存資源的進(jìn)程}end;cobegin varx:Integer; repeatborrow(varB:Integer); repeatreturn(varB:integer);coend30三、與時間有關(guān)的錯誤(6)

若borrow和return按如下次序執(zhí)行，則borrow將無限等待：全局共享變量x=3+9borrow（6） return（9）if6>xthen x:=x+9; {修改主存分配表} {釋放等主存資源的進(jìn)程}//空操作申請進(jìn)程進(jìn)入等待隊列等主存資源//永遠(yuǎn)等待，沒有其他進(jìn)程將其喚醒。31三、與時間有關(guān)的錯誤(6)

實例概括：現(xiàn)有可用內(nèi)存數(shù)x=3，進(jìn)程B要申請6個單位內(nèi)存，超過當(dāng)前可用內(nèi)存數(shù)，準(zhǔn)備等待，尚未等待，CPU切換給了進(jìn)程R，R歸還內(nèi)存9個單位，然后喚醒內(nèi)存等待者?？墒沁@會兒沒有進(jìn)程等待，于是喚醒信號丟棄。CPU切換回B，B執(zhí)行等待操作。以后沒有進(jìn)程喚醒B，于是B永遠(yuǎn)等待。

現(xiàn)實生活中的旅游：大家到景區(qū)分散旅游，約定在某個時間和地點集合。我到了那里，卻未見一個人，到底是等我的人等我等得時間太長已經(jīng)走了還是我到的比他們還早。我應(yīng)該去追趕他們還是在原地等候他們?32四、進(jìn)程的交互（InteractionAmongProcesses）：協(xié)作和競爭(1)

并發(fā)進(jìn)程之間存在兩種基本關(guān)系：競爭關(guān)系和協(xié)作關(guān)系。1.并發(fā)進(jìn)程之間的競爭關(guān)系

系統(tǒng)中的多個進(jìn)程之間彼此無關(guān)，相互并不知道其它進(jìn)程的存在，相互之間并不交換信息。但是由于這些進(jìn)程共用了一套計算機(jī)系統(tǒng)資源，因而必然產(chǎn)生競爭資源的問題，一個進(jìn)程的執(zhí)行可能影響到同其競爭資源的其它進(jìn)程。操作系統(tǒng)必須協(xié)調(diào)好諸進(jìn)程對資源的爭用。一旦一個進(jìn)程要使用已分配給另一個進(jìn)程的資源，則該進(jìn)程必須等待。資源競爭產(chǎn)生兩個問題：33四、進(jìn)程的交互（InteractionAmongProcesses）：協(xié)作和競爭(2)

一個是死鎖(Deadlock)問題，就是一組進(jìn)程如果都獲得了部分資源，還想要得到其他進(jìn)程所占用的資源，最終所有進(jìn)程都將陷入死鎖。

一個是饑餓(Starvation)問題，是指一個進(jìn)程由于其它進(jìn)程總是優(yōu)先于它而被無限期拖延。既要解決饑餓問題，又要解決死鎖問題。解決饑餓問題的最簡單策略是FCFS資源分配策略。由于操作系統(tǒng)負(fù)責(zé)資源分配，資源競爭的控制應(yīng)由系統(tǒng)來解決，操作系統(tǒng)應(yīng)該提供各種支持。34四、進(jìn)程的交互（InteractionAmongProcesses）：協(xié)作和競爭(2)

進(jìn)程互斥(MutualExclusion)：是解決進(jìn)程間競爭關(guān)系(間接制約關(guān)系