【正文】 第3章 進程的同步與通信 基本點、重點和難點在多道程序系統(tǒng)中，程序的執(zhí)行失去了封閉性和再現(xiàn)性，程序的運行具有不確定性，這是我們所不希望看到的。如果多道程序系統(tǒng)中程序的執(zhí)行不加控制，程序的每次執(zhí)行就可能得到不同的結果。如何使多道程序的執(zhí)行的結果具有再現(xiàn)性和確定性？這就需要通過進程間的同步和互斥來實現(xiàn)，將原來無序的、不確定的程序的執(zhí)行轉換為有序的、確定的執(zhí)行。解決同步和互斥問題最常用的方法就是信號量的方法，通過在程序中使用P、V操作達到同步和互斥的目的。在使用信號量和P、V操作時，很多學生覺得無從下手，感到困惑。這主要是因為他們對進程的本質理解還不夠深入、對多道程序設計的原理還不夠清楚、對信號量的含義還不夠明白造成的。但這部分內容又是各類考試的必考點。本章有很多經典問題，其解題的方法和答案在很多資料上都可以見到。但這些解題的結果是專家們長期精煉而成的，初學者在開始時不可能得到這樣的結果。對于初學者而言，迫切想知道的已不單是解題的結果，而是問題解決的思考和分析過程。為此，本章中對一些問題的解答給出了詳細的分析過程。 進程的同步和互斥的概念1. 同步(Synchronization)相互合作的進程需要在某些點上協(xié)調，先到達某點的進程需要等待后到達的進程，進程間的這種協(xié)調關系叫同步。2. 互斥(Mutex)互斥是一種特殊的同步方式。當多個進程需要使用相同的資源，而此資源在任一時刻卻只能供一個進程使用，獲得資源的進程可以繼續(xù)執(zhí)行，沒有獲得資源的進程必須等待。進程間的這種相互排斥關系叫互斥。3. 臨界資源與臨界區(qū)(Critical Resource and Critical Section)臨界資源是一次只允許一個進程使用的資源。臨界區(qū)是在進程中操作臨界資源的程序段。1． 基本思想實現(xiàn)互斥的基本思想是使多個進程不能同時進入臨界區(qū)。給每個臨界資源分配一個鎖：鎖打開時，進程進入臨界區(qū)，將鎖關閉，開始操作臨界資源，離開臨界區(qū)時，將鎖打開；鎖關閉時，需要進入臨界區(qū)的進程要等待。2． 操作鎖的步驟(1) 確定臨界資源；(2) 確定臨界區(qū)；(3) 確定鎖個數；(4) 設置鎖操作。 信號量與P、V操作1. 信號量的引入1965年，荷蘭學者Dijkstra提出的信號量機制是一種卓有成效的進程同步工具。在長期且廣泛的應用中，信號量機制得到了很大的發(fā)展：它從整型信號量經記錄型信號量，進而發(fā)展為“信號量集”機制。現(xiàn)在的信號量機制已被廣泛的應用于單處理機、多處理機系統(tǒng)和計算機網絡中。2. 信號量(Semaphore)設S為信號量，可以將S看成一個信號燈，但S能比信號燈表達更豐富的含義。(1) 當S0時，是綠燈，進程看到綠燈可以通過。S值越大，通過進程的能力越大，供進程使用的相關資源越多。S值反映了可供進程使用的相關資源的數量。(2) 當S=0時，是紅燈，進程看到紅燈需要等待。此時|S|表示等待S信號的進程的個數。3． 信號量的操作最初由Dijkstra把整型信號量定義為一個整型量，除初始化外，僅能通過兩個標準的原子操作Wait(S)和Signal(S)來訪問，其它方法都不能操作信號量。這兩個操作很長時間以來，一直被分別稱為P、V操作，因為希臘語的Wait詞頭為P，Signal的詞頭為V。對信號量的操作定義如下：(1) P(S)或Wait(S)：是等待信號的操作，是查看信號的操作，是看燈操作。若為綠燈，進程繼續(xù)前進；若為紅燈，進程必須等待。在該操作中，進行S=S1，操作使S的值向負方向轉化，即操作使信號燈S向紅的方向轉化。(2) V(S)或Signal(S)：是發(fā)送信號的操作。在該操作中，進行S=S+1, 操作使S的值向正方向轉化，即操作使信號燈S向綠的方向轉化。4． P(S)、V(S)的實現(xiàn)(1) 整型信號量P(S)： while s=0 do noopS：=S1；V(S)：S：=S+1；(2) 記錄型信號量在整型信號量機制中的wait操作，只要是信號量S=0，就會不斷地測試。因此，該機制并未遵循“讓權等待”的準則，而是該進程處于“忙等”的狀態(tài)。記錄型信號量機制則是一種不存在“忙等”問題的進程同步機制。但在采取了“讓權等待”的策略后，又會出現(xiàn)多個進程等待訪問同一臨界資源的問題。為此，在信號量機制中，除了需要一個用于代表資源數目的整型變量value外，還應增加一個進程鏈表L，用于鏈接或記錄上述的所有因此信號量而等待的進程。記錄型信號量是由于它采用了紀錄型的數據結構而得名的。它所包含的上述兩個數據項可描述為：type semaphore=recordvalue:integer。L:list of process。End相應地，wait(s)和singal(s)操作可描述為：Procedure wait(s) var s:semaphore。 Begin :=。 If 0 then Begin Insert(*, )；Block(*)； EndEndProcedure signal (s)var S:semaphore。Begin:=+1。If =0 thenBegin N=remove() 。Wakeup(N)。 EndEnd每次的wait操作，意味著進程請求一個單位的資源，:=；0時，表示資源已分配完畢，進程需要等待而進入阻塞狀態(tài)。為了便于喚醒，在當前進程需要進入阻塞狀態(tài)前，進程調用block原語，進行自我阻塞，放棄處理機。0時進程才進入阻塞狀態(tài)，0時。每次signal操作，表示執(zhí)行進程釋放一個單位資源，:=+1操作表示資源數目加1。=0,則表示在該信號量鏈表中，仍有等待該資源的進程被阻塞，故還應從該信號量鏈表中移出一個進程，調用wakeup原語將該進程喚醒。 信號量實現(xiàn)進程的同步與互斥1. 利用信號量實現(xiàn)互斥當信號量用于互斥時，信號量mutex的含義是進程是否可以操作臨界資源，進程是否可以進入臨界區(qū)。mutex0時，進程可以操作臨界資源，可以進入臨界區(qū)，否則mutex=0時進程必須等待。為了使多個進程能互斥地訪問某臨界資源，只需為該臨界資源設置互斥信號量mutex。如果每次只允許一個進程操作臨界資源，其初值為1；如果最多允許k個進程使用某個資源，信號量的初值為 k。然后將各進程的臨界區(qū)CS置于wait(mutex)和signal(mutex)操作之間即可。這樣，每個欲訪問該臨界資源的進程，在進入臨界區(qū)之前，都要對mutex執(zhí)行wait操作。若該資源此刻未被訪問，本次wait操作成功，進程便可進入自己的臨界區(qū)，這時若有其他的進程欲進入自己的臨界區(qū)，進程執(zhí)行wait操作必然阻塞，從而保證了該臨界資源被互斥訪問。當訪問臨界資源的進程退出臨界區(qū)后，進程對mutex執(zhí)行signal操作，釋放該臨界資源。要注意的是，在利用信號量機制實現(xiàn)進程互斥時，wait(mutex)和signal(mutex)必須成對出現(xiàn)。缺少wait(mutex)將會導致系統(tǒng)混亂，不能保證對臨界資源的互斥訪問；而缺少signal(mutex)將會使臨界資源永遠不被釋放，從而使等待該資源而阻塞的進程永遠不能被喚醒。2. 利用信號量實現(xiàn)同步當信號量用于互斥時，信號量S的含義是某事件是否發(fā)生，某條件是否滿足。下面看一下如何用信號量來描述程序或語句之間的前趨關系。設有兩個并發(fā)執(zhí)行的進程P1和P2。P1中有語句S1；P2中有語句S2。如果我們希望執(zhí)行S1后再執(zhí)行S2。為實現(xiàn)這種前趨關系，我們只需使進程P1和P2共享一個公用信號量S，并賦予其初值為0，將signal(s)操作放在S1后面；而在S2語句前面插入wait(s)操作，即：在進程P1中，S1；signal(s)在進程P2中，wait(s)；S2S的含義是S1語句是否執(zhí)行：S1執(zhí)行后，信號量S0；，S1沒有執(zhí)行時，信號量S=0。初始狀態(tài)S1語句沒有執(zhí)行，因此S=0。因為S1執(zhí)行后S應變成大于0的值，所以S應被初始化為0。這樣，若P2先執(zhí)行必定阻塞自己，只有在進程P1執(zhí)行完S1；signal(s)后，使S增為1時，P2進程才能執(zhí)行語句S2。同樣，可以利用信號量，按下圖語句間的前趨關系，寫出一個可并發(fā)執(zhí)行的程序。詳細描述如下：var a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0。beginparbeginbegin S1。 signal(a)。signal(b)。end。begin wait(a)。S2。signal(c)。signal(d)。end。begin wait(b)。S3。signal(e)。end。begin wait(c)。S4。signal(f)。end。begin wait(d)。S5。signal(g)。end。begin wait(e)。wait(f)。wait(g)。S6。end。parendendS1S3S5S6S2S4 進程前趨關系圖3. 解決同步和互斥問題的步驟(1) 確定并發(fā)和順序操作哪些操作是并發(fā)的？哪些操作是順序的？這是解決同步和互斥問題時首先要確定的。并發(fā)操作可以用多個進程實現(xiàn)，同步和互斥就發(fā)生在這多個進程之間。多個進程操作同一臨界資源就是進程間的互斥問題，多個進程要按一定的順序進行操作就是進程間的同步問題。(2) 確定互斥和同步的規(guī)則分析具體問題，確定同步和互斥的基本方式，確定能夠進行正確操作的條件，在這些條件中隱含著同步和互斥的規(guī)則。(3) 確定同步、互斥的操作流程 按操作的步驟，寫出每個進程操作的流程(4) 確定信號量的個數和含義根據同步和互斥規(guī)則以及操作流程確定信號量的個數，確定信號量代表的含義，只有確切地知道信號量所代表的含義，設置這個信號量才有意義。(5) 確定信號量的初值同步信號量的初值則要根據進程的初始狀態(tài)確定，具體問題要具體分析，沒有統(tǒng)一的方法。(6) 確定P、V操作的位置根據同步和互斥規(guī)則和每個進程的操作流程就可以確定P、V操作的位置。需要說明的是無論是互斥問題還是同步問題，只要是需要進程進入阻塞狀態(tài)，就必須想到在什么時候將進程喚醒。初學者開始時可以按上述步驟解決同步和互斥問題，熟練后，就可以不局限于這些規(guī)則，靈活應用。這好象學騎自行車一樣，開始時需要左看右看，掌握了基本要領，熟練操作以后就可以隨心所欲。以上講述的只是一般的求解規(guī)則，雖然有一定的可操作性，但在實際應用中還是要針對具體情況，多做多想，領悟出其中的原理和竅門。4. 同步和互斥的經典問題(1) 生產者和消費者問題（PCP:ProducerConsumer Problem）。例如，消息緩沖通信的管理。(2) 讀者和寫者問題（RWP:ReaderWriter Problem）。例如，共享文件的讀寫問題。(3) 哲學家進餐問題（DPP:Dining Philosopher Problem）。例如，進程對多類資源的競爭使用。 例題解析 多道程序系統(tǒng)程序的執(zhí)行失去了封閉性和再現(xiàn)性，因此多道程序的執(zhí)行不需要這些特性，這種說法是否正確 ？解 這種說法不正確?？梢韵胂?，如果一個程序在多道程序系統(tǒng)中，在相同的輸入的情況下，多次執(zhí)行所得結果是不同的，有誰還敢使用這個程序？因此，多道程序的執(zhí)行也需要封閉性和再現(xiàn)性，只不過單道程序系統(tǒng)的封閉性和再現(xiàn)性是先天固有的，多道程序系統(tǒng)的程序執(zhí)行要想獲得封閉性和再現(xiàn)性，需通過程序員的精心設計才能得到。所使用的方法就是同步和互斥的方法。 多個進程對信號量S進行了5次 P操作，2次V操作后，現(xiàn)在信號量的值是 3，與信號量S相關的處于阻塞狀態(tài)的進程有幾個？信號量的初值是多少？ 解 (1) 因為S的當前值是3，因此因為S處于阻塞狀態(tài)的進程有3個；(2) 因為每進行一次P(S)操作，S的值都減1，每執(zhí)行1次V操作S的值加1，故信號量的初值為3+52=0。 如下鎖的實現(xiàn)方法存在什么缺點？如何改進？ LOCK(X) UNLOCK(X) { { do while X=1 。 X=0。 X=1 } } 解 存在的缺點是：當鎖是關閉時，采用的是循環(huán)等待的方法，這樣的等待還是要占用處理機的時間，應該采用阻塞等待的方法。 改進的鎖實現(xiàn)如下： LOCK(X) UNLOCK(X) { { if =1 if not empty(){ insert( *, )。 { P=remove()。 Block (*) Wakeup(P)} } else =1 else =0 } } 。insert( *, )，remove()。 使用多個進程計算Y=F1(X)+F2 (X).解 (1) 確定并發(fā)和順序操作在這個問題中，F(xiàn)1(X)和F2 (X)的計算是可以并行處理的，因此F1(X)和F2 (X)可以分別出現(xiàn)在兩個進程中。(2) 確定互斥或同步的規(guī)則在F1(X)+F2 (X)中，必須在F1(X)和F2(X)計算完畢，才能進行加法運算，因此