第3章并發(fā)進程

第三章并發(fā)進程一、概述

為了增強計算機系統(tǒng)處理數(shù)據(jù)的能力，提高資源的利用率，現(xiàn)代計算機系統(tǒng)采用多道程序設(shè)計技術(shù)，從而使得若干作業(yè)并存于內(nèi)存中且同時執(zhí)行。每個作業(yè)的操作步驟都是由相應(yīng)的進程完成的。多個作業(yè)同時執(zhí)行的狀態(tài)，表現(xiàn)為一個進程的工作還沒有全部完成之前，另一個進程就開始工作，把這些可同時進行工作的進程稱為“并發(fā)進程”。在并發(fā)進程的執(zhí)行過程中，進程同步是操作系統(tǒng)管理共享資源，避免出錯的一個有效手段。進程的同步包括進程的同步與進程的互斥兩個方面。進程的互斥是指并發(fā)進程即多個執(zhí)行進程，同時競爭共享資源時，若某共享正在被一個進程使用，其他申請該資源的進程必須等待，直至該資源被釋放后，另一個進程才能使用該資源。也就是說，共享資源應(yīng)該互斥的使用。進程的同步是指一個進程的執(zhí)行依賴于其他進程的執(zhí)行狀況，即并發(fā)進程中，一個進程在沒有得到其他進程發(fā)來的消息時必須等待，直至另一個進程送來消息后才能繼續(xù)執(zhí)行。進程的死鎖是并發(fā)進程之間相互等待對方占有的資源的現(xiàn)象。二、進程間的制約關(guān)系

在多道程序系統(tǒng)中，由于資源共享與進程合作，使諸進程之間可能產(chǎn)生兩種形式的制約關(guān)系：１．間接相互制約

這種制約主要源于資源共享。例如，有兩進程Ａ和Ｂ，如果在Ａ進程提出打印請求時，系統(tǒng)已將打印機分配給進程Ｂ，則進程Ａ阻塞；一旦進程Ｂ將打印機釋放，也就使進程Ａ由阻塞改為就緒狀態(tài)。２．直接相互制約

這種制約主要源于進程合作。例如，有一輸入進程A通過單緩沖向進程B提供數(shù)據(jù)。當(dāng)該緩沖空時，計算進程Ｂ因不能獲得所需數(shù)據(jù)而阻塞，當(dāng)進程A把數(shù)據(jù)送入緩沖時，便將B喚醒；反之，進程Ａ因不能再向緩沖區(qū)投放數(shù)據(jù)而阻塞，當(dāng)進程B將緩沖區(qū)內(nèi)數(shù)據(jù)取走時喚醒A。第三章并發(fā)進程

可見，諸進程在并發(fā)執(zhí)行時，必須按照一定的次序執(zhí)行。進程同步例子：對于共享一個緩沖區(qū)的輸入進程和計算進程，當(dāng)輸入進程未將數(shù)據(jù)送入緩沖區(qū)時，計算進程不能開動計算；同樣，若計算進程未從緩沖區(qū)中取走數(shù)據(jù)時，輸入進程不能再啟動下一次的輸入。輸入進程計算進程緩沖區(qū)

3.1進程的并發(fā)性1、雖然對于一個程序的輸入、計算和打印必須順序執(zhí)行，但在對一批程序進行處理時，則可使上述三種操作并發(fā)執(zhí)行，以提高系統(tǒng)的吞吐量。例如，輸入程序在輸入第三個程序（I3）的同時，計算程序可以正在對第二個程序進行計算（C2），而打印程序正在打印第一個程序（Ｐ1）的計算結(jié)果。如下圖所示：I1I2I3I4C1C2C3C4P1P2P3P4程序段并發(fā)執(zhí)行的有向圖

第三章并發(fā)進程2、與時間有關(guān)的錯誤例如，某展示廳設(shè)置了一個自動計數(shù)系統(tǒng)，用一個計數(shù)器count指示在場的人數(shù)。當(dāng)有一人進人時，進程pin實現(xiàn)計數(shù)加１，當(dāng)退出一人時，進程POUT實現(xiàn)計數(shù)減１。由于人場與退場是隨機的，因此，進程pin和pout是并發(fā)的。用cobegin和coend表示并發(fā)執(zhí)行，這兩個進程的程序如下：begincount:integer;count：=0;cobeginprocesspinR1：integer；beginR1：＝count；R1：=R1＋1；count：=R1；end；processpoutR2：integer；

beginR2：=count；R2：=R2-1；count:＝R2;end;coend;end；

假定某時刻的計數(shù)值count=ｎ，這時有一個人要進人，正好另一個人要退出，于是進程pin和pot都要執(zhí)行。如果進程ｎ和pout的執(zhí)行都沒有被打斷過，那么各自完成了count+1和count-1的工作，使計數(shù)值保持為ｎ，這是正確的。如果兩個進程執(zhí)行中，由于某種原因進程ＰＩＮ被打斷，且進程調(diào)度使它們的執(zhí)行呈下面的次序：占有CPU執(zhí)行過程進程執(zhí)行的操作count值pinR1:=countR1:=R1+1npin中斷，由pout占用CPU并執(zhí)行過程R2:=countR2:=R2+1Count:=R2n-1pin繼續(xù)執(zhí)行Count:=R1+1n+1按這樣的次序執(zhí)行后，count的最終值不能保持為ｎ，而變成ｎ+1。如果進程被打斷的情況如下：占用CPU執(zhí)行過程進程執(zhí)行的操作count值pinR1:=countR1:=R1+1npin被打斷，pout占用R2:=countR2:=R2+1npout被打斷，pin占用count:=R1n+1pin被打斷，pout占用count:=R2n-1于是，兩個進程執(zhí)行完后，count的終值為ｎ-1。也就是說，這兩個進程的執(zhí)行次序?qū)Y(jié)果是有影響的，關(guān)鍵是它們涉及到共享變量count，且兩者交替訪問了count，在不同的時間里訪問count，就可能使count的值不同。所以，造成計數(shù)值不正確的因素是與進程被打斷的時間和能占用處理的時間有關(guān)，由于這種原因造成的錯誤稱為“與時間有關(guān)的錯誤”。3.2進程的互斥與同步一、進程互斥

從上面例子可知：當(dāng)若干個進程都要使用某一共享資源時，任何時刻最多只允許一個進程使用，其他要使用該資源的進程必須等待，直到占有資源的進程釋放了該資源，這就是進程的互斥。具有互斥關(guān)系的進程并不是它們的所有操作都要互斥進行，只需要確保涉及共享變量操作的那一段程序?qū)崿F(xiàn)互斥。通常把這一段程序稱為臨界區(qū)或臨界段，進程的互斥實質(zhì)上就是并發(fā)進程對臨界區(qū)的訪問是互斥的。二、臨界區(qū)（criticalsection）1.臨界資源：一次僅允許一個進程使用的資源。

例如，有兩個進程共享一個變量count：（R1和R2是處理機中的寄存器）：

當(dāng)兩個進程按下述順序執(zhí)行時但若P1和P2按另一種順序?qū)ount進行修改

P1：R1：=count；P1：R1：=count;

R1:=R1+1;P2:R2:=count;

count:=R1;P1:R1:=R1+1;count:=R1;

P2:R2:=count;P2:R2:=R2+1;count:=R2;

R2:=R2+1;雖然P1和P2都各自對count作了加

count:=R2;1操作，但最后的count卻只增加了1。亦其結(jié)果使count增加了2；即發(fā)生了與執(zhí)行順序有關(guān)的錯誤。

為了預(yù)防這種錯誤，對變量count應(yīng)按臨界資源處理，即令P1和P2互斥地使用count。

2.

臨界區(qū)：訪問臨界資源的那段代碼。諸進程在訪問臨界資源時，必須互斥。我們把每個進程中訪問臨界資源的那段代碼稱為臨界區(qū)。為了實現(xiàn)對臨界區(qū)的互斥訪問，應(yīng)保證諸進程互斥地進入自己的臨界區(qū)。為此，每個進程在進入其臨界區(qū)前，必須先提出申請，經(jīng)允許后方可進入。若干個并發(fā)進程臨界區(qū)程序的執(zhí)行準(zhǔn)則如下：（1）若干個進程都要求進入臨界區(qū)訪問共享變量時，只允許一人進程進入，其他進程必須等待；（2）任何一個進入臨界區(qū)的進程必須在有限的時間內(nèi)退出臨界區(qū)；（3）當(dāng)某一進程退出臨界區(qū)時，若有其他進程等待進入，同必須允許一個進程進入臨界區(qū)。3、P-V操作20世60年代中期發(fā)明的P-V操作能夠滿足對臨界區(qū)的管理要求。P-V操作由兩個原語：P操作原語與V操作原語組成。P-V操作是一個整型變量上的兩個操作，設(shè)整型變量S稱作信號量或信號燈。通過s的操作，對進程和資源進行管理，從而實現(xiàn)對臨界區(qū)的互斥訪問。（1）P操作：s：=s-1，若s大于等于0，則表示有資源，當(dāng)前進程繼續(xù)運行，若s小于0，表示已無資源，則當(dāng)前進程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)，將其插入到與信號量s有關(guān)的等待隊列中，直到其他進程在s上執(zhí)行V操作為止。（2）V操作：s:=s+1，若s大0，則本進程繼續(xù)執(zhí)行，若s小于等于0，則從與信號s相關(guān)的等待隊列中移出列首的進程，將其由阻塞狀態(tài)轉(zhuǎn)變?yōu)榫途w狀態(tài)，插入到就緒隊列中，當(dāng)前進程仍繼續(xù)執(zhí)行。利用P-V操作實現(xiàn)互斥：A進程B進程…….……..p(s)p(s)臨界區(qū)臨界區(qū)v(s)v(s)…….…….前面例子中的兩個并發(fā)進程都要使用共享的計數(shù)器count，從分析中看到，只有當(dāng)一個進程不在使用count時另一個進程再去使用，才不會出錯．如果它們交叉地使用count則會現(xiàn)與時間有關(guān)的鍺。為了保證兩個進程互斥地使用計數(shù)器count，可以用ＰＶ操作來管理。定義一個信號量s的初值為１，把兩個并發(fā)進程的程序改寫成如下：begincount：integer；s：semphorecount:=0；s:=1；cobeginprocesspinR1：integer;beginp(s)；R1：＝count;R1：=R1+1;count：=R1;v(s)end；processpoutR2：integer;beginp(s);R2：＝count；R2：=R2—1;count:=R2；v(s)end；coend；end；這里p操作p(s)限制了一次只有一個進程在臨界區(qū)執(zhí)行。如果一個進程在臨界區(qū)執(zhí)行時被打斷，另一個進程想進入臨界區(qū)，但由于進人臨界區(qū)前必須先調(diào)用p(s)，而此時已在臨界區(qū)的進程尚未退出臨界區(qū)，所以s的值為“０”，想進人臨界區(qū)的進程調(diào)用p(G)的結(jié)果必然是等待，直到已進入臨界區(qū)的進程再次得到處理器執(zhí)行完臨界區(qū)中的操作調(diào)用v(s)后才結(jié)束等待．所以，改寫后的程序在執(zhí)行中即使被打斷，也不會出現(xiàn)兩個進程交叉訪問count，保證了進程互斥地使用共享的計數(shù)器。一般說，當(dāng)ｎ個進程Ｐ1，Ｐ2，…Pn要共享某一資源時，為保證資源的互斥，首先找出ｎ個進程各自的臨界區(qū)，對每個進程都用ＰＶ操作來實現(xiàn)進入和退出臨界，進程Ｐｉ（ｉ=１，２，…ｎ）互斥的一般形式為：begins：semphore；s:=1;cobeginprocessPibeginp(s);臨界區(qū)v(s);......end；coend;end；processPibeginp(s);臨界區(qū)v(s);end；coendend；但是，任何粗心地使用PV操作會違反臨界區(qū)的管理要求．例如對7．2中的第二個例子，用PV操作管理臨界區(qū)時，若粗心地把程序改寫成：

begins：semaphores：=1；cobeginprocessPi（i＝1，2，…n）begin按旅客訂票要求找到Aj；p(s)；Ri：=AjifRi＞=lthenbeginRi：=Ri—1;Ai:=Ri；v(s);輸出一張票endelse輸出“票已售完”end;coend；end進程執(zhí)行時調(diào)用P(S）決定是否能進入臨界區(qū)，由于S的初值為1，故每次只能有一個進程進入臨界區(qū)，其它想進入臨界區(qū)執(zhí)行的進程必須等待，這符合臨界區(qū)管理的第一個要求。但在改寫的程序中忽略了當(dāng)條件Ri＞=1不成立時執(zhí)行else部分的V操作，以致使進程在臨界區(qū)中判到條件Ri＞=1不成立時無法退出臨界區(qū)，當(dāng)然也就不能釋放等待進入臨界區(qū)的進程，造成進程無限地等待進入臨界區(qū)，這就違反了對臨界區(qū)管理的第二、第三的兩個要求。正確的做法應(yīng)該是；beginS：semphore；S：＝1；cobeginprocessPi(0，1,2,…,n）begin按旅客訂票要求找到Aj；p(s)；Ri:=Aj；ifRi>=1thenbeginRi：=Ri－1，Aj：=Ri；v(s)；輸出一張票endelsebeginv(s);輸出“票已售完”……2、P-V操作實現(xiàn)同步進程的同步是并發(fā)進程之間存在一種制約關(guān)系，一個進程的執(zhí)行依賴另一個進程的消息，當(dāng)一個進程沒有得到另一個進程的消息時應(yīng)等待，直到消息到這才被喚醒。先看一個例子。設(shè)有兩個進程A和B，它們共享一個緩沖器，進程A不斷地讀人記錄并送到緩沖器，進程B不斷地從緩沖器中取出記錄并加工。假定緩沖器的容量為每次只能存放一個記錄，于是正確的工作應(yīng)該是這樣的：進程A把一個記錄送人緩沖器后．應(yīng)等到進程B發(fā)來消息（已將緩沖器的記錄取走）才能把下一個送入緩沖器。進程B也應(yīng)等到進程A發(fā)來消息（緩沖器中已送入一個記錄），才能從緩沖器中取出記錄并加工。如果這兩個進程不是相互制約的話，那么可能出現(xiàn)：進程A又向緩沖器送入一個新記錄而把上一個尚未取走的記錄覆蓋了；進程B在下一個記錄送入緩沖器之前又去取緩沖器中的記錄，造成重復(fù)地取同一個記錄加工。PV操作不僅可以用來實現(xiàn)互斥進入臨界區(qū)而且還是一個簡單而又方便的同步工具，用它來解決生產(chǎn)者/消費者問題，可以防止生產(chǎn)者把物品放入已經(jīng)裝有物品的緩沖器中，也可防止消費者在物品存入緩沖器之前去取物品，現(xiàn)在假定有一個生產(chǎn)者和一個消費者，它們公用一個緩沖器，生產(chǎn)者不斷地生產(chǎn)物品，每生產(chǎn)一件物品就要存入緩沖器，但緩沖器中每次只能存入一件物品，只有當(dāng)消費者把物品取走后，生產(chǎn)者才能把第二件物品存入緩沖器，同樣地，消費者要不斷地取出物品去消費，，當(dāng)緩沖器中有物品進他就可去取，每取走一件物品后必須等生產(chǎn)者放入一件物品才可再取，用PV操作實現(xiàn)生產(chǎn)者/消費者之間的同步，可以定義兩個信號量：

SP：表示是否可以把物品存入緩沖器，由于緩沖器中只能放一件物品，所以SP的初值取為“1”。SG；表示緩沖器中是否存有物品，顯然，它的初值應(yīng)該為“0”，表示還沒有物品。對生產(chǎn)者來說，生產(chǎn)一件物品后應(yīng)調(diào)用P（SP），當(dāng)緩沖器中無物品時（這時SP=1）則調(diào)用p（SP）后不會成為等待狀態(tài)，可繼續(xù)執(zhí)行，把物品存入緩沖器。調(diào)用一次P（SP）后，SP=0，若消費者尚未取走物品，而生產(chǎn)者又生產(chǎn)了一件物品欲存入緩沖器，這時調(diào)用P（SP）將使生產(chǎn)者處于等待狀態(tài)而阻止它把物品再存人緩沖器。當(dāng)在緩沖器存人一件物品后，應(yīng)調(diào)用V（SG），告訴消費者緩沖器中已經(jīng)有一件物品了（調(diào)用V（SG）后，SG的值從“0”變?yōu)椤發(fā)”）。對消費者來說，取物品前應(yīng)查看緩沖器中是否有物品，即調(diào)用P（SG）。當(dāng)無物品時，由于SG＝0，調(diào)用p（SG）后消費者等待，不能去取物品；當(dāng)有物品時，由于SG=1調(diào)用P(SG)后消費者可繼續(xù)執(zhí)行去取物品。每取走一件物品后，應(yīng)調(diào)用V（SP），通知生產(chǎn)看緩沖器中物品已取走，可以存入一件新的物品。生產(chǎn)者和消費者并發(fā)執(zhí)行時，可按如下方式同步：beginBuffer：integer；SP，SG：semaphore；Sp：=1；SG：=0;cobeginprocessproducerbeginL1：produceaproduct；P（SP）；Buffer：＝product；v（SG）;gotoL1endbeginL2：P（SG）；takeaproductV（SP）；consume；gotoL2end;coend；end；

如果一個生產(chǎn)者和一個消費者他們共享的緩沖器容量為可以存放n件物品，那么只要把信號量SP的初值定為n。當(dāng)緩沖器中沒有放滿n件物品時，生產(chǎn)者調(diào)用P（SP）都不會成為等待狀態(tài)而可把物品存人緩沖器。但當(dāng)緩沖器中已經(jīng)有n件物品，生產(chǎn)者想再存入一件物品將被拒絕。每存人一件物品后，由于調(diào)用V（SG），故SG的值表示緩沖器中可用的物品數(shù)，只要SG40，消費者調(diào)用P（SG）后總可去取物品。每取走一件物品后，由于調(diào)用V（SP），便增加了一個可用來存放物品的位置。用指針k和t分別指示生產(chǎn)者往緩沖器存物品和消費者從緩沖器中取物品的相對位置，它們的初值為“0”，那么，一個生產(chǎn)者和一個消費者共用容量為n的緩沖器時，可如下同步工作：beginB：array［0...n—1]ofInteger；k，t：integer;Sp，SG：Semphore；K：=t:=0;SP：＝n；SG：＝0；cobeginprocessproducerbeginL1：produceaproduct；P(SP)；B[K］：=product;k：=（k+1）modn;

v（SG）;gotoL1endprocessconsumerbeginL1：P（SG）；takeaproductfromB[t];t：＝（t＋1）modn；V（SP）；consumegotoL2end；coend；end；3.3進程通信一、

低級和高級進程通信方式

雖然一個作業(yè)可分為若干個能并發(fā)執(zhí)行的進程，但它們應(yīng)經(jīng)常保持聯(lián)系，以便協(xié)調(diào)一致地完成指定任務(wù)。這種聯(lián)系是指在進程之間交換一定數(shù)量的信息。信息量可多可少，多是指能交換成千個數(shù)據(jù)，少則僅是一個狀態(tài)或數(shù)值。顯然，進程同步是一種簡單通信方式，進程通過修改信號量，可向另一進程表明臨界資源是否可用。在生產(chǎn)者－消費者問題中，可由生產(chǎn)者進程向消費者進程傳送一批消息，或者說，生產(chǎn)者通過緩沖池與消費者通信。應(yīng)當(dāng)指出，信號量機制作為同步工具是卓有成效的，但作為通信工具則不夠理想，因為其效率甚低，因此，稱為低級通信方式。

1、低級進程通信

進程的互斥和同步可歸結(jié)為低級進程通信。在進程互斥中進程通過修改信號量，向其他進程表明臨界資源是否可用；在生產(chǎn)者－消費者問題中，生產(chǎn)者通過緩沖池與消費者通信。應(yīng)當(dāng)指出，信號量機制作為同步工具是卓有成效的，但作為通信工具則不夠理想，主要表現(xiàn)在：

（１）效率低生產(chǎn)者每次只能向緩沖區(qū)中投放一個消息，消費者每次只能從緩沖區(qū)中取得一個消息；

（２）通信對用戶不透明即設(shè)置共享數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)的傳送、進程的互斥與同步都是由程序員去實現(xiàn)，操作系統(tǒng)只提供共享存儲器。

簡言之，這種通信方式的效率低，不方便，故只適用于傳送少量信息的情況。

2.

高級進程通信

以較高的效率傳送大量數(shù)據(jù)的一種通信方式。高級通信的目的不是為了控制進程的執(zhí)行速度，而是為了交換信息。在這種通信方式中，程序員可直接利用系統(tǒng)提供的一組通信命令（通信原語），高效地傳送大量數(shù)據(jù)，操作系統(tǒng)隱藏了實現(xiàn)通信的細(xì)節(jié)，這大大簡化了通信程序編制上的復(fù)雜性。高級通信原語不僅保證相互制約的進程之間的正確關(guān)系，還同時實現(xiàn)了進程之間的信息交換。目前常用的高級通信機構(gòu)有消息緩沖通信、管道通信和信箱通信。二、進程通信的類型(１）消息緩沖通信消息緩沖通信方式也稱為直接通信方式，即一個進程直接發(fā)送一個消息給接收進程。所謂消息