第二章進程管理

第二章進程管理2.1進程的基本概念2.2進程控制2.3進程同步2.4經(jīng)典進程的同步問題2.5進程通信2.6線程2.1進程的基本概念2.1.1程序的順序執(zhí)行及其特征1.程序的順序執(zhí)行僅當前一操作(程序段)執(zhí)行完后，才能執(zhí)行后繼操作。例如，在進行計算時，總須先輸入用戶的程序和數(shù)據(jù)，然后進行計算，最后才能打印計算結(jié)果。

S1:a∶=x+y;S2:b∶=a-5;S3:c∶=b+1;圖2-1程序的順序執(zhí)行S1:a∶=x+y;S2:b∶=a-5;S3:c∶=b+1;2.程序順序執(zhí)行時的特征順序性：處理機的操作必須嚴格按照程序所規(guī)定的順序執(zhí)行(2)封閉性：程序在執(zhí)行時獨占系統(tǒng)的全部資源，因此機器資源狀態(tài)的改變只與執(zhí)行的程序有關(guān)，與外界環(huán)境無關(guān)(3)可再現(xiàn)性：只要初始條件相同，一個程序的多次重復(fù)執(zhí)行，將得到相同的結(jié)果2.1.2前趨圖

前趨圖(PrecedenceGraph)是一個有向無循環(huán)圖，記為DAG(DirectedAcyclicGraph)，用于描述進程之間執(zhí)行的前后關(guān)系。圖中的每個結(jié)點可用于描述一個程序段或進程，乃至一條語句；結(jié)點間的有向邊則用于表示兩個結(jié)點之間存在的偏序(PartialOrder)或前趨關(guān)系(PrecedenceRelation)“→”。

→={(Pi,Pj)|PimustcompletebeforePjmaystart},如果(Pi,Pj)∈→,可寫成Pi→Pj，稱Pi是Pj的直接前趨，而稱Pj是Pi的直接后繼。在前趨圖中，把沒有前趨的結(jié)點稱為初始結(jié)點(InitialNode)，把沒有后繼的結(jié)點稱為終止結(jié)點(FinalNode)。

每個結(jié)點還具有一個重量(Weight)，用于表示該結(jié)點所含有的程序量或結(jié)點的執(zhí)行時間。Ii→Ci→Pi和S1→S2→S3圖2-2前趨圖對于圖2-2(a)所示的前趨圖，存在下述前趨關(guān)系：P1→P2,P1→P3,P1→P4,P2→P5,P3→P5,P4→P6,P4→P7,P5→P8,P6→P8,P7→P9,P8→P9或表示為：

P={P1,P2,P3,P4,P5,P6,P7,P8,P9}→={(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P4,P7),(P5,P8),(P6,P8),(P7,P9),(P8,P9)}應(yīng)當注意，前趨圖中必須不存在循環(huán)，但在圖2-2(b)中卻有著下述的前趨關(guān)系：S2→S3,S3→S2

【聯(lián)48】已知一個求值公式：若A、B已賦值，試畫出該公式求值過程的前趨圖。2.1.3程序的并發(fā)執(zhí)行及其特征1.程序的并發(fā)執(zhí)行圖2-3并發(fā)執(zhí)行時的前趨圖在該例中存在下述前趨關(guān)系：

Ii→Ci，Ii→Ii+1,Ci→Pi,Ci→Ci+1，Pi→Pi+1而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之間，可以并發(fā)執(zhí)行。對于具有下述四條語句的程序段：

S1:a∶=x+2S2:b∶=y+4S3:c∶=a+bS4:d∶=c+b圖2-4四條語句的前趨關(guān)系S1:a∶=x+2S2:b∶=y+4S3:c∶=a+bS4:d∶=c+b2.程序并發(fā)執(zhí)行時的特征

程序的并發(fā)執(zhí)行是指二個或二個以上的程序或程序段可在同一時間間隔內(nèi)同時執(zhí)行。程序的并發(fā)執(zhí)行極大提高了資源利用率和系統(tǒng)吞吐量，也產(chǎn)生了不同于順序執(zhí)行的新特征：1.間斷性：由于資源共享和相互合作，并發(fā)執(zhí)行的程序間形成了相互制約關(guān)系，導(dǎo)致程序的運行過程出現(xiàn)“執(zhí)行-暫停-執(zhí)行”的現(xiàn)象2.失去封閉性：程序在執(zhí)行時與其他并發(fā)執(zhí)行的程序共享系統(tǒng)的資源，因此資源狀態(tài)的改變還與其他程序有關(guān)3.不可再現(xiàn)性：同樣的初始條件，一個程序的多次重復(fù)執(zhí)行，可能得到不同的結(jié)果

例如，有兩個循環(huán)程序A和B，它們共享一個變量N。程序A每執(zhí)行一次時，都要做N∶=N+1操作；程序B每執(zhí)行一次時，都要執(zhí)行Print(N)操作，然后再將N置成“0”。程序A和B以不同的速度運行。

(1)N∶=N+1在Print(N)和N∶=0之前，此時得到的N值分別為n+1,n+1,0。

(2)N∶=N+1在Print(N)和N∶=0之后，此時得到的N值分別為n,0,1。

(3)N∶=N+1在Print(N)和N∶=0之間，此時得到的N值分別為n,n+1,0。2.1.4進程的特征與狀態(tài)1.進程的特征和定義結(jié)構(gòu)特征：從結(jié)構(gòu)上說，每個進程實體中除了相應(yīng)的程序段、數(shù)據(jù)段外，必須包含一個數(shù)據(jù)結(jié)構(gòu)進程控制塊PCB2)動態(tài)性：進程是程序的一次執(zhí)行過程，因此是都動態(tài)的。動態(tài)性還表現(xiàn)在進程具有一定的生命期，它必須由創(chuàng)建而產(chǎn)生、由調(diào)度而執(zhí)行、由撤銷而消亡。3)并發(fā)性：指多個進程實體同存于內(nèi)存中，且能在一段時間內(nèi)同時運行。只有為程序創(chuàng)建進程后，多個程序才能正確地并發(fā)運行，并發(fā)是引入進程的目的。4)獨立性：進程實體是一個能獨立運行、獨立分配資源和獨立接受調(diào)度的基本單位5)異步性：進程可按各自獨立、不可預(yù)知的速度向前推進

較典型的進程定義有：

(1)進程是程序的一次執(zhí)行。

(2)進程是一個程序及其數(shù)據(jù)在處理機上順序執(zhí)行時所發(fā)生的活動。

(3)進程是程序在一個數(shù)據(jù)集合上運行的過程，它是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。在引入了進程實體的概念后，我們可以把傳統(tǒng)OS中的進程定義為：“進程是進程實體的運行過程，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位”?！韭?lián)1】以下對進程的描述中，錯誤的是A進程是動態(tài)的概念B進程執(zhí)行需要處理機C進程是有生命期的D進程是指令的集合【聯(lián)3】一個進程是A有處理機執(zhí)行的一個程序B一個獨立的程序+數(shù)據(jù)集C

PCB結(jié)構(gòu)、程序和數(shù)據(jù)的組合D一個獨立的程序【聯(lián)5】在單處理機系統(tǒng)中實現(xiàn)并發(fā)技術(shù)后，————A各進程在某一時刻并行運行，cpu與i/o設(shè)備間并行工作B各進程在一個時間段內(nèi)并行運行，cpu與i/o設(shè)備間串行工作C各進程在一個時間段內(nèi)并行運行，cpu與i/o設(shè)備間并行工作D各進程在某一時刻并行運行，cpu與i/o設(shè)備間串行工作總結(jié)：進程與程序的區(qū)別1.進程是程序的執(zhí)行，所以進程屬于動態(tài)概念，而程序是一組指令的有序集合，是靜態(tài)的概念2.進程既然是程序的執(zhí)行，或者說是“一次運行活動”，因而它是有生命過程的，從投入運行到運行完成，它的存在是暫時的，而程序的存在時永久的3.進程是程序的執(zhí)行，因此進程的組成應(yīng)包括程序和數(shù)據(jù)。除此之外，進程還由記錄進程狀態(tài)信息的PCB組成。4.進程是競爭計算機系統(tǒng)有限資源的基本單位5.一個進程能與其他進程并發(fā)地活動6.一個程序可能對應(yīng)多個進程，一個進程可以包含多個程序。進程和程序無一一對應(yīng)關(guān)系2.進程的三種基本狀態(tài)就緒(Ready)狀態(tài)：進程已獲得除cpu以外的所有必要資源，只要得到cpu便可立即執(zhí)行。可以有多個就緒狀態(tài)的進程2)執(zhí)行狀態(tài)：進程已得到cpu，其程序正在cpu上執(zhí)行3)阻塞狀態(tài)：正在執(zhí)行的進程因某種事件（如I/O請求）的發(fā)生而暫時無法繼續(xù)執(zhí)行，只有等相應(yīng)事件完成后，才能去競爭cpu

圖2-5進程的三種基本狀態(tài)及其轉(zhuǎn)換3.掛起狀態(tài)不少系統(tǒng)中，進程只有上述三種基本狀態(tài)，但另些系統(tǒng)中增加了掛起狀態(tài)，其實質(zhì)使進程不能繼續(xù)執(zhí)行，即掛起后的進程處于就緒狀態(tài)，它也不能參加cpu的競爭，被掛起的進程處于靜止狀態(tài)，相反，沒有被掛起的進程處于活動狀態(tài)，只有通過激活才能得以實現(xiàn)引入掛起狀態(tài)的原因

終端用戶的請求。

用戶發(fā)現(xiàn)可疑問題，希望暫時使自己的程序靜止下來，以便研究其執(zhí)行情況或修改(2)父進程請求。

父進程希望掛起某個子進程，考查或修改它，或協(xié)調(diào)各子進程之間的活動(3)負荷調(diào)節(jié)的需要。

當負荷較重，影響對實時任務(wù)的控制

(4)操作系統(tǒng)的需要。

檢查運行中的資源使用情況等另外，掛起進程可以騰出內(nèi)存空間給其它就緒進程使用2)進程狀態(tài)的轉(zhuǎn)換活動就緒→靜止就緒。(2)活動阻塞→靜止阻塞。(3)靜止就緒→活動就緒。(4)靜止阻塞→活動阻塞。圖2-6具有掛起狀態(tài)的進程狀態(tài)圖【聯(lián)8】分配到必要的資源并獲得處理機時間的進程狀態(tài)是A就緒B運行C阻塞D撤銷【聯(lián)9】當一個進程處于這樣的狀態(tài)時，______，稱為阻塞狀態(tài)A它正等著輸入一批數(shù)據(jù)B它正等著進程調(diào)度C它正等著分給它一個時間片D它正等著進入內(nèi)存批處理系統(tǒng)中作業(yè)處理及狀態(tài)【聯(lián)10】某運行中的進程要申請打印機，它將變?yōu)開__A就緒態(tài)B阻塞態(tài)C創(chuàng)建態(tài)D撤銷態(tài)【聯(lián)11】以下進程狀態(tài)轉(zhuǎn)變中，___轉(zhuǎn)變時不可能發(fā)生的。A運行---->就緒B運行---->阻塞C阻塞---->運行D阻塞---->就緒【聯(lián)13】一個進程的基本狀態(tài)可以從其他兩種基本狀態(tài)轉(zhuǎn)變過來，這個基本狀態(tài)一定是就緒狀態(tài)【聯(lián)19】進程自身決定______A從運行狀態(tài)到阻塞狀態(tài)B從運行狀態(tài)到就緒狀態(tài)C從就緒狀態(tài)到運行狀態(tài)D從阻塞狀態(tài)到就緒狀態(tài)【聯(lián)20】以下可能導(dǎo)致一個進程從運行狀態(tài)變?yōu)榫途w狀態(tài)的事件是___A一次I/O操作結(jié)束B運行進程需要做I/O操作C運行進程結(jié)束D出現(xiàn)了比現(xiàn)在進程優(yōu)先級更高的進程【聯(lián)21】一個進程釋放一種資源有可能導(dǎo)致一個或幾個進程_____A就緒變運行B運行變就緒C阻塞變運行D阻塞變就緒【聯(lián)22】一次i/o操作的結(jié)束，有可能導(dǎo)致___A一個進程由阻塞變?yōu)榫途wB幾個進程由阻塞變?yōu)榫途wC一個進程由阻塞變?yōu)檫\行D幾個進程由阻塞變?yōu)檫\行2.1.5進程控制塊1.進程控制塊的作用

進程控制塊的作用是使一個在多道程序環(huán)境下不能獨立運行的程序(含數(shù)據(jù))，成為一個能獨立運行的基本單位，一個能與其它進程并發(fā)執(zhí)行的進程。或者說，OS是根據(jù)PCB來對并發(fā)執(zhí)行的進程進行控制和管理的。PCB要被系統(tǒng)頻繁訪問，必須常駐內(nèi)存。2.進程控制塊中的信息1)進程標識符進程標識符用于惟一地標識一個進程。一個進程通常有兩種標識符：

(1)內(nèi)部標識符。在所有的操作系統(tǒng)中，都為每一個進程賦予一個惟一的數(shù)字標識符，它通常是一個進程的序號。設(shè)置內(nèi)部標識符主要是為了方便系統(tǒng)使用。

(2)外部標識符。它由創(chuàng)建者提供，通常是由字母、數(shù)字組成，往往是由用戶(進程)在訪問該進程時使用。為了描述進程的家族關(guān)系，還應(yīng)設(shè)置父進程標識及子進程標識。此外，還可設(shè)置用戶標識，以指示擁有該進程的用戶。2)處理機狀態(tài)處理機狀態(tài)信息主要是由處理機的各種寄存器中的內(nèi)容組成的。處理機在運行時，許多信息都存放在寄存器中，當處理機被中斷時，所有這些信息都必須保持在PCB中，以便在該進程重新執(zhí)行時，能從斷點繼續(xù)執(zhí)行。3)進程調(diào)度信息在PCB中還存放一些與進程調(diào)度和進程對換有關(guān)的信息，包括：①進程狀態(tài)，指明進程的當前狀態(tài)，作為進程調(diào)度和對換時的依據(jù)；②進程優(yōu)先級，用于描述進程使用處理機的優(yōu)先級別的一個整數(shù)，優(yōu)先級高的進程應(yīng)優(yōu)先獲得處理機；③進程調(diào)度所需的其它信息，它們與所采用的進程調(diào)度算法有關(guān)，比如，進程已等待CPU的時間總和、進程已執(zhí)行的時間總和等；④事件，是指進程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)所等待發(fā)生的事件，即阻塞原因。4)進程控制信息進程控制信息包括：①程序和數(shù)據(jù)的地址，是指進程的程序和數(shù)據(jù)所在的內(nèi)存或外存地(首)址，以便再調(diào)度到該進程執(zhí)行時，能從PCB中找到其程序和數(shù)據(jù)；②進程同步和通信機制，指實現(xiàn)進程同步和進程通信時必需的機制，如消息隊列指針、信號量等，它們可能全部或部分地放在PCB中；③資源清單，是一張列出了除CPU以外的、進程所需的全部資源及已經(jīng)分配到該進程的資源的清單；④鏈接指針，它給出了本進程(PCB)所在隊列中的下一個進程的PCB的首地址。3.進程控制塊的組織方式1)鏈接方式圖2-7PCB鏈接隊列示意圖2)索引方式圖2-8按索引方式組織PCB2.2進程控制2.2.1進程的創(chuàng)建1.進程圖(ProcessGraph)圖2-9進程樹2.引起創(chuàng)建進程的事件

用戶登錄。用戶在終端鍵入登錄命令后，如果是合法用戶，系統(tǒng)將建立一個進程，并插入就緒隊列中(2)作業(yè)調(diào)度。作業(yè)裝入內(nèi)存，立即分配資源，創(chuàng)建進程，插入就緒隊列(3)提供服務(wù)。用戶提出請求后，系統(tǒng)專門創(chuàng)建一個進程里提供用戶所需的服務(wù)(4)應(yīng)用請求。以上三種都是系統(tǒng)內(nèi)核創(chuàng)建的，應(yīng)用程序為自己創(chuàng)建一個新進程3.進程的創(chuàng)建(CreationofProgress)(1)申請空白PCB。

(2)為新進程分配資源。

(3)初始化進程控制塊。

(4)將新進程插入就緒隊列，如果進程就緒隊列能夠接納新進程，便將新進程插入就緒隊列。2.2.2進程的終止

1.引起進程終止(TerminationofProcess)的事件當進程完成任務(wù)或遇到異常情況和外界干預(yù)需要結(jié)束時，應(yīng)通過進程終止原語來終止進程。終止進程的實質(zhì)是收回PCB。具體的操作過程是：找到要終止進程的PCB；若該進程正在執(zhí)行，則終止它的執(zhí)行，并置重新調(diào)度的標志；終止屬于該進程的所有子孫進程；釋放終止進程所擁有的全部資源；將終止進程移出它所在的隊列并收回PCB。1)正常結(jié)束在任何計算機系統(tǒng)中，都應(yīng)有一個用于表示進程已經(jīng)運行完成的指示。例如，在批處理系統(tǒng)中，通常在程序的最后安排一條Holt指令或終止的系統(tǒng)調(diào)用。當程序運行到Holt指令時，將產(chǎn)生一個中斷，去通知OS本進程已經(jīng)完成。在分時系統(tǒng)中，用戶可利用Logsoff去表示進程運行完畢，此時同樣可產(chǎn)生一個中斷，去通知OS進程已運行完畢。2)異常結(jié)束在進程運行期間，由于出現(xiàn)某些錯誤和故障而迫使進程終止。這類異常事件很多，常見的有：①越界錯誤。這是指程序所訪問的存儲區(qū)，已越出該進程的區(qū)域；

②保護錯。進程試圖去訪問一個不允許訪問的資源或文件，或者以不適當?shù)姆绞竭M行訪問，例如，進程試圖去寫一個只讀文件；

③非法指令。程序試圖去執(zhí)行一條不存在的指令。出現(xiàn)該錯誤的原因，可能是程序錯誤地轉(zhuǎn)移到數(shù)據(jù)區(qū)，把數(shù)據(jù)當成了指令；④特權(quán)指令錯。用戶進程試圖去執(zhí)行一條只允許OS執(zhí)行的指令；⑤運行超時。進程的執(zhí)行時間超過了指定的最大值；⑥等待超時。進程等待某事件的時間，超過了規(guī)定的最大值；⑦算術(shù)運算錯。進程試圖去執(zhí)行一個被禁止的運算，例如，被0除；⑧I/O故障。這是指在I/O過程中發(fā)生了錯誤等。3)外界干預(yù)外界干預(yù)并非指在本進程運行中出現(xiàn)了異常事件，而是指進程應(yīng)外界的請求而終止運行。這些干預(yù)有：①操作員或操作系統(tǒng)干預(yù)。由于某種原因，例如，發(fā)生了死鎖，由操作員或操作系統(tǒng)終止該進程；②父進程請求。由于父進程具有終止自己的任何子孫進程的權(quán)利，因而當父進程提出請求時，系統(tǒng)將終止該進程；③父進程終止。當父進程終止時，OS也將他的所有子孫進程終止。2.2.3進程的阻塞與喚醒1.引起進程阻塞和喚醒的事件

請求系統(tǒng)服務(wù)，不能滿足2)啟動某種操作，等待完成3)新數(shù)據(jù)尚未到達4)無新工作可做進程的阻塞是進程自身的一種自主行為2.進程阻塞過程入口保存當前的CPU現(xiàn)場置進程的狀態(tài)為阻塞態(tài)被阻塞進程入等待隊列轉(zhuǎn)進程調(diào)度3.進程喚醒過程入口從等待隊列中摘下被喚醒的進程將被喚醒進程置為就緒態(tài)將被喚醒進程送入就緒隊列轉(zhuǎn)進程調(diào)度或返回Block原語和wakeup原語是一對作用剛好相反的原語。因此，如果在某進程中調(diào)用了阻塞原語，則必須在與之合作的另一進程中或其它相關(guān)的進程中安排喚醒原語；否則，被阻塞進程將會因不能被喚醒而長久地處于阻塞狀態(tài)，從而再無機會繼續(xù)運行。2.2.4進程的掛起與激活

1.進程的掛起

當出現(xiàn)了引起進程掛起的事件時，系統(tǒng)將利用掛起原語suspend()將指定進程或處于阻塞狀態(tài)的進程掛起。掛起原語的執(zhí)行過程是：首先檢查被掛起進程的狀態(tài)，若處于活動就緒狀態(tài)，便將其改為靜止就緒；對于活動阻塞狀態(tài)的進程，則將之改為靜止阻塞。為了方便用戶或父進程考查該進程的運行情況而把該進程的PCB復(fù)制到某指定的內(nèi)存區(qū)域。最后，若被掛起的進程正在執(zhí)行，則轉(zhuǎn)向調(diào)度程序重新調(diào)度。

2.進程的激活過程

當發(fā)生激活進程的事件時，系統(tǒng)將利用激活原語active()將指定進程激活。激活原語先將進程從外存調(diào)入內(nèi)存，檢查該進程的現(xiàn)行狀態(tài)，若是靜止就緒，便將之改為活動就緒；若為靜止阻塞便將之改為活動阻塞。假如采用的是搶占調(diào)度策略，則每當有新進程進入就緒隊列時，應(yīng)檢查是否要進行重新調(diào)度。【聯(lián)28】以下說法中，__不是創(chuàng)建進程所必須的。A建立一個進程的進程表項B為進程分配內(nèi)存C為進程分配cpuD將進程表項插入就緒隊列中【聯(lián)30】以下__不會引起進程創(chuàng)建A用戶登錄B作業(yè)調(diào)度C設(shè)備分配D應(yīng)用請求2.3進程同步

2.3.1進程同步的基本概念

1.兩種形式的制約關(guān)系

間接相互制約關(guān)系。（資源共享）

進程A和B共享一臺打印機(2)直接相互制約關(guān)系。（進程合作）

進程A和B通過單緩沖區(qū)合作工作2.臨界資源(CriticalResouce)

生產(chǎn)者-消費者(producer-consumer)問題是一個著名的進程同步問題。它描述的是：有一群生產(chǎn)者進程在生產(chǎn)產(chǎn)品，并將這些產(chǎn)品提供給消費者進程去消費。為使生產(chǎn)者進程與消費者進程能并發(fā)執(zhí)行，在兩者之間設(shè)置了一個具有n個緩沖區(qū)的循環(huán)緩沖池，生產(chǎn)者進程將它所生產(chǎn)的產(chǎn)品放入一個緩沖區(qū)中；諸進程采取互斥方式訪問的資源即為臨界資源。

消費者進程可從一個緩沖區(qū)中取走產(chǎn)品去消費。盡管所有的生產(chǎn)者進程和消費者進程都是以異步方式運行的，但它們之間必須保持同步，即不允許消費者進程到一個空緩沖區(qū)去取產(chǎn)品；也不允許生產(chǎn)者進程向一個已裝滿產(chǎn)品且尚未被取走的緩沖區(qū)中投放產(chǎn)品。

我們可利用一個數(shù)組來表示上述的具有n個(0，1，…，n-1)緩沖區(qū)的緩沖池。用輸入指針in來指示下一個可投放產(chǎn)品的緩沖區(qū)，每當生產(chǎn)者進程生產(chǎn)并投放一個產(chǎn)品后，輸入指針加1；用一個輸出指針out來指示下一個可從中獲取產(chǎn)品的緩沖區(qū)，每當消費者進程取走一個產(chǎn)品后，輸出指針加1。由于這里的緩沖池是組織成循環(huán)緩沖的，故應(yīng)把輸入指針加1表示成in∶=(in+1)modn；

輸出指針加1表示成out∶=(out+1)modn。當(in+1)modn=out時表示緩沖池滿；而in=out則表示緩沖池空。此外，還引入了一個整型變量counter,其初始值為0。每當生產(chǎn)者進程向緩沖池中投放一個產(chǎn)品后，使counter加1；反之，每當消費者進程從中取走一個產(chǎn)品時，使counter減1。生產(chǎn)者和消費者兩進程共享下面的變量：Varn,integer;typeitem=…;varbuffer:array［0,1,…,n-1］ofitem;in,out:0,1,…,n-1;counter:0,1,…,n;

指針in和out初始化為1。在生產(chǎn)者和消費者進程的描述中，no-op是一條空操作指令，whilecondicationdono-op語句表示重復(fù)的測試條件(condication)，重復(fù)測試應(yīng)進行到該條件變?yōu)閒alse(假)，即到該條件不成立時為止。在生產(chǎn)者進程中使用一局部變量nextp，用于暫時存放每次剛生產(chǎn)出來的產(chǎn)品；而在消費者進程中，則使用一個局部變量nextc,用于存放每次要消費的產(chǎn)品。producer:repeat … produceaniteminnextp;… whilecounter=ndono-op; buffer［in］∶=nextp; in∶=in+1modn; counter∶=counter+1; untilfalse;consumer:repeat whilecounter=0dono-op; nextc∶=buffer［out］; out∶=(out+1)modn; counter∶=counter-1; consumertheiteminnextc; untilfalse;

雖然上面的生產(chǎn)者程序和消費者程序，在分別看時都是正確的，而且兩者在順序執(zhí)行時其結(jié)果也會是正確的，但若并發(fā)執(zhí)行時，就會出現(xiàn)差錯，問題就在于這兩個進程共享變量counter。生產(chǎn)者對它做加1操作，消費者對它做減1操作，這兩個操作在用機器語言實現(xiàn)時，?？捎孟旅娴男问矫枋觯簉egister1∶=counter;register2∶=counter;register1∶=register1+1;register2∶=register2-1;counter∶=register1;counter∶=register2;假設(shè)：counter的當前值是5。如果生產(chǎn)者進程先執(zhí)行左列的三條機器語言語句，然后消費者進程再執(zhí)行右列的三條語句，則最后共享變量counter的值仍為5；反之，如果讓消費者進程先執(zhí)行右列的三條語句，然后再讓生產(chǎn)者進程執(zhí)行左列的三條語句，counter值也還是5。但是，如果按下述順序執(zhí)行：

register1∶=counter;(register1=5)register1∶=register1+1;(register1=6)register2∶=counter;(register2=5)register2∶=register2-1;(register2=4)

counter∶=register1;(counter=6)counter∶=register2;(counter=4)

正確的值應(yīng)該為5，但現(xiàn)在是4.還可能出現(xiàn)答案為6的情況。－－失去可再現(xiàn)性3.臨界區(qū)(criticalsection)

諸進程須采取互斥方式訪問的軟硬件資源—臨界資源進程中訪問臨界資源的那段代碼稱為臨界區(qū)可把一個訪問臨界資源的循環(huán)進程描述如下：repeat

criticalsection;remaindersection;untilfalse;entrysectionexitsection4.同步機制應(yīng)遵循的規(guī)則

空閑讓進。臨界資源空閑時允許進程進入自己的臨界區(qū)(2)忙則等待。臨界資源被訪問時，其他要求進去臨界區(qū)的進程必須等待

(3)有限等待。進程應(yīng)在有限的時間內(nèi)進入自己的臨界區(qū)，以免死等

(4)讓權(quán)等待。不能進入臨界區(qū)的進程應(yīng)立即釋放CPU，以免忙等2.3.2信號量機制1.整型信號量最初由Dijkstra把整型信號量定義為一個整型量，除初始化外，僅能通過兩個標準的原子操作(AtomicOperation)wait(S)和signal(S)來訪問。這兩個操作一直被分別稱為P、V操作。wait和signal操作可描述為：

wait(S):whileS≤0dono-opS∶=S-1;signal(S):S∶=S+1;

2.記錄型信號量在整型信號量機制中的wait操作，只要是信號量S≤0，就會不斷地測試。因此，該機制并未遵循“讓權(quán)等待”的準則，而是使進程處于“忙等”的狀態(tài)。記錄型信號量機制，則是一種不存在“忙等”現(xiàn)象的進程同步機制。但在采取了“讓權(quán)等待”的策略后，又會出現(xiàn)多個進程等待訪問同一臨界資源的情況。為此，在信號量機制中，除了需要一個用于代表資源數(shù)目的整型變量value外，還應(yīng)增加一個進程鏈表L，用于鏈接上述的所有等待進程。記錄型信號量是由于它采用了記錄型的數(shù)據(jù)結(jié)構(gòu)而得名的。它所包含的上述兩個數(shù)據(jù)項可描述為：typesemaphore=recordvalue:integer;L:listofprocess;end相應(yīng)地，wait(S)和signal(S)操作可描述為：procedurewait(S)varS:semaphore;beginS.value∶=S.value-1;ifS.value＜0thenblock(S,L)endproceduresignal(S)varS:semaphore;beginS.value∶=S.value+1;ifS.value≤0thenwakeup(S,L);end

在記錄型信號量機制中，S.value的初值表示系統(tǒng)中某類資源的數(shù)目，因而又稱為資源信號量，對它的每次wait操作，意味著進程請求一個單位的該類資源，因此描述為S.value∶=S.value-1；當S.value＜0時，表示該類資源已分配完畢，因此進程應(yīng)調(diào)用block原語，進行自我阻塞，放棄處理機，并插入到信號量鏈表S.L中?？梢姡摍C制遵循了“讓權(quán)等待”準則。此時S.value的絕對值表示在該信號量鏈表中已阻塞進程的數(shù)目。對信號量的每次signal操作，表示執(zhí)行進程釋放一個單位資源，故S.value∶=S.value+1操作表示資源數(shù)目加1。若加1后仍是S.value≤0，則表示在該信號量鏈表中，仍有等待該資源的進程被阻塞，故還應(yīng)調(diào)用wakeup原語，將S.L鏈表中的第一個等待進程喚醒。如果S.value的初值為1，表示只允許一個進程訪問臨界資源，此時的信號量轉(zhuǎn)化為互斥信號量。

3.AND型信號量在兩個進程中都要包含兩個對Dmutex和Emutex的操作，即processA: processB:wait(Dmutex); wait(Emutex);wait(Emutex); wait(Dmutex);若進程A和B按下述次序交替執(zhí)行wait操作：processA:wait(Dmutex);于是Dmutex=0processB:wait(Emutex);于是Emutex=0processA:wait(Emutex);于是Emutex=-1A阻塞processB:wait(Dmutex);于是Dmutex=-1B阻塞AND同步機制的基本思想是：將進程在整個運行過程中需要的所有資源，一次性全部地分配給進程，待進程使用完后再一起釋放。只要尚有一個資源未能分配給進程，其它所有可能為之分配的資源，也不分配給他。亦即，對若干個臨界資源的分配，采取原子操作方式：要么全部分配到進程，要么一個也不分配。由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。為此，在wait操作中，增加了一個“AND”條件，故稱為AND同步，或稱為同時wait操作，即Swait(Simultaneouswait)定義如下：Swait(S1,S2,…,Sn)ifSi≥1and…andSn≥1thenfori∶=1tondoSi∶=Si-1;endforelseplacetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi＜1,andsettheprogramcountofthisprocesstothebeginningofSwaitoperationendifSsignal(S1,S2,…,Sn)fori∶=1tondoSi=Si+1;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue.endfor;4.信號量集Swait(S1,t1,d1,…,Sn,tn,dn)ifSi≥t1and…andSn≥tnthenfori∶=1tondoSi∶=Si-di;endforelsePlacetheexecutingprocessinthewaitingqueueofthefirstSiwithSi＜tiandsetitsprogramcountertothebeginningoftheSwaitOperation.endifsignal(S1,d1,…,Sn,dn)fori∶=1tondoSi∶=Si+di;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueueendfor;

一般“信號量集”的幾種特殊情況：

(1)Swait(S,d,d)。此時在信號量集中只有一個信號量S，但允許它每次申請d個資源，當現(xiàn)有資源數(shù)少于d時，不予分配。

(2)Swait(S,1,1)。此時的信號量集已蛻化為一般的記錄型信號量(S＞1時)或互斥信號量(S=1時)。

(3)Swait(S,1,0)。這是一種很特殊且很有用的信號量操作。當S≥1時，允許多個進程進入某特定區(qū)；當S變?yōu)?后，將阻止任何進程進入特定區(qū)。換言之，它相當于一個可控開關(guān)。2.3.3信號量的應(yīng)用1.利用信號量實現(xiàn)進程互斥利用信號量實現(xiàn)進程互斥的進程可描述如下：Varmutex:semaphore∶=1;beginparbeginprocess1:begin repeat wait(mutex); criticalsection signal(mutex); remainderseetion untilfalse; endprocess2:begin repeat wait(mutex); criticalsection signal(mutex); remaindersection untilfalse; endparend2.利用信號量實現(xiàn)前趨關(guān)系圖2-10前趨圖舉例圖2-10前趨圖舉例abcdfgeVara,b,c,d,e,f,g;semaphore∶=0,0,0,0,0,0,0;beginparbegin 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);S5;signal(g);end; beginwait(e);wait(f);wait(g);S6;end;parendend華中理工大學(xué)1999年試題，哈工大2000年試題司機和售票員之間的同步關(guān)系司機只有在售票員關(guān)車門后，才能啟動汽車。售票員只有在司機到站停車后，才能開車門。解：Semaphoreclose=0，stop=0；driver() { /*司機*/ while(True){ P(close);

啟動車輛;

正常行車;

到站停車; V(stop); }}Conductor(){ /*售票員*/ while(True){

關(guān)車門; V(close);

售票; P(stop);

開車門;

上下乘客; }}Main(){parbegin(driver,conductor);}2.4經(jīng)典進程的同步問題2.4.1生產(chǎn)者—消費者問題前面我們已經(jīng)對生產(chǎn)者—消費者問題(Theproceducer-consumerproblem)做了一些描述，但未考慮進程的互斥與同步問題，因而造成了數(shù)據(jù)Counter的不定性。由于生產(chǎn)者—消費者問題是相互合作的進程關(guān)系的一種抽象，例如，在輸入時，輸入進程是生產(chǎn)者，計算進程是消費者；而在輸出時，則計算進程是生產(chǎn)者，而打印進程是消費者，因此，該問題有很大的代表性及實用價值。1.利用記錄型信號量解決生產(chǎn)者—消費者問題假定在生產(chǎn)者和消費者之間的公用緩沖池中，具有n個緩沖區(qū)，這時可利用互斥信號量mutex實現(xiàn)諸進程對緩沖池的互斥使用；利用信號量empty和full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。又假定這些生產(chǎn)者和消費者相互等效，只要緩沖池未滿，生產(chǎn)者便可將消息送入緩沖池；只要緩沖池未空，消費者便可從緩沖池中取走一個消息。對生產(chǎn)者—消費者問題可描述如下：Varmutex,empty,full:semaphore∶=1,n,0;buffer:array［0,…,n-1］ofitem;in,out:integer∶=0,0;beginparbeginproceducer:beginrepeat…produceranitemnextp;…wait(empty);wait(mutex);buffer(in)∶=nextp;in∶=(in+1)modn;signal(mutex);signal(full);untilfalse;endconsumer:beginrepeatwait(full);wait(mutex);nextc∶=buffer(out);out∶=(out+1)modn;signal(mutex);signal(empty);consumertheiteminnextc;untilfalse;endparendend

在生產(chǎn)者—消費者問題中應(yīng)注意：首先，在每個程序中用于實現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對地出現(xiàn)；其次，對資源信號量empty和full的wait和signal操作，同樣需要成對地出現(xiàn)，但它們分別處于不同的程序中。例如，wait(empty)在計算進程中，而signal(empty)則在打印進程中，計算進程若因執(zhí)行wait(empty)而阻塞，則以后將由打印進程將它喚醒；最后，在每個程序中的多個wait操作順序不能顛倒。應(yīng)先執(zhí)行對資源信號量的wait操作，然后再執(zhí)行對互斥信號量的wait操作，否則可能引起進程死鎖。2.利用AND信號量解決生產(chǎn)者—消費者問題Varmutex,empty,full:semaphore∶=1,n,0;buffer:array［0,…,n-1］ofitem;inout:integer∶=0,0;beginparbeginproducer:beginrepeat…produceaniteminnextp;…Swait(empty,mutex);buffer(in)∶=nextp;in∶=(in+1)modn;Ssignal(mutex,full);untilfalse;endconsumer:beginrepeatSwait(full,mutex);nextc∶=buffer(out);out∶=(out+1)modn;Ssignal(mutex,empty);consumertheiteminnextc;untilfalse;endparendend

假定系統(tǒng)有3個并發(fā)進程get、copy和put共享緩沖器B1和B2。進程get負責(zé)從輸入設(shè)備上讀信息，每讀出一條記錄后放到B1中。進程copy從緩沖器B1中取出一條記錄拷貝后存入B2。進程put取出B2中的記錄打印輸出。B1和B2每次只能存放一條記錄。要求3個進程協(xié)調(diào)完成任務(wù)，使打印出來的與讀入的記錄個數(shù)、次序完全一樣。請用記錄型信號量寫出并發(fā)程序。解：

設(shè)置4個信號量，其中empty1對應(yīng)空閑的緩沖區(qū)1，其初值為1；full1對應(yīng)緩沖區(qū)1中的記錄，其初值為0；empty2對應(yīng)空閑的緩沖區(qū)2，其初值為1；full2對應(yīng)緩沖區(qū)2中的記錄，其初值為0。相應(yīng)進程描述為：get(){ while(1){

從輸入設(shè)備讀入一條記錄; P(empty1);

將記錄存入緩沖區(qū)1；

V(full1); }}copy(){ while(1){ P(full1);

從緩沖區(qū)1中取出一條記錄; V(empty1); P(empty2);

將取出的記錄存入緩沖區(qū)2；

V(full2); }}put(){ while(1){ P(full2);

從緩沖區(qū)2中取出一條記錄; V(empty2);

將取出的記錄打印出來；

}}Main(){parbegin(get,copy,put);}水果問題桌上有一只盤子，最多可容納兩個水果，每次只能放入或取出一個水果。爸爸專向盤中放蘋果，媽媽專向盤中放橘子；兒子專等吃盤子中的橘子，女兒專等吃盤子中的蘋果。請用P、V操作實現(xiàn)爸爸、媽媽、兒子、女兒之間的同步與互斥關(guān)系。水果問題桌上有一只盤子，最多可容納兩個水果，每次只能放入或取出一個水果。爸爸專向盤中放蘋果，媽媽專向盤中放橘子；兒子專等吃盤子中的橘子，女兒專等吃盤子中的蘋果。請用P、V操作實現(xiàn)爸爸、媽媽、兒子、女兒之間的同步與互斥關(guān)系。答：設(shè)置信號量empty表示還可以向盤中放幾個水果，其初值為2；apple對應(yīng)已放入盤中的蘋果，orange對應(yīng)已放入盤中的橘子，它們的初值均為0；mutex用來實現(xiàn)對盤子的互斥訪問（包括放和?。?，其初值為1。father(){ mother(){ while(1){ while(1){ P(empty); P(empty); P(mutex); P(mutex);

向盤中放蘋果； 向盤中放橘子；

V(mutex); V(mutex); V(apple); V(orange); } }} }son(){ daughter(){ while(1){ while(1){ P(orange); P(apple); P(mutex); P(mutex);

從盤中取橘子； 從盤中取蘋果；

V(mutex); V(mutex); V(empty); V(empty);

吃橘子； 吃蘋果；

} }} }2.4.2哲學(xué)家進餐問題

1.利用記錄型信號量解決哲學(xué)家進餐問題經(jīng)分析可知，放在桌子上的筷子是臨界資源，在一段時間內(nèi)只允許一位哲學(xué)家使用。為了實現(xiàn)對筷子的互斥使用，可以用一個信號量表示一只筷子，由這五個信號量構(gòu)成信號量數(shù)組。其描述如下：

Varchopstick:array［0,…,4］ofsemaphore;所有信號量均被初始化為1，第i位哲學(xué)家的活動可描述為：

repeat wait(chopstick［i］); wait(chopstick［(i+1)mod5］); … eat;… signal(chopstick［i］); signal(chopstick［(i+1)mod5］); … think;untilfalse;

可采取以下幾種解決方法：

(1)至多只允許有四位哲學(xué)家同時去拿左邊的筷子，最終能保證至少有一位哲學(xué)家能夠進餐，并在用畢時能釋放出他用過的兩只筷子，從而使更多的哲學(xué)家能夠進餐。

(2)僅當哲學(xué)家的左、右兩只筷子均可用時，才允許他拿起筷子進餐。

(3)規(guī)定奇數(shù)號哲學(xué)家先拿他左邊的筷子，然后再去拿右邊的筷子；而偶數(shù)號哲學(xué)家則相反。按此規(guī)定，將是1、2號哲學(xué)家競爭1號筷子；3、4號哲學(xué)家競爭3號筷子。即五位哲學(xué)家都先競爭奇數(shù)號筷子，獲得后，再去競爭偶數(shù)號筷子，最后總會有一位哲學(xué)家能獲得兩只筷子而進餐。2.利用AND信號量機制解決哲學(xué)家進餐問題在哲學(xué)家進餐問題中，要求每個哲學(xué)家先獲得兩個臨界資源(筷子)后方能進餐，這在本質(zhì)上就是前面所介紹的AND同步問題，故用AND信號量機制可獲得最簡潔的解法。Varchopsiickarray［0,…,4］ofsemaphore∶=(1,1,1,1,1);processirepeatthink;Sswait(chopstick［(i+1)mod5］,chopstick［i］);eat;Ssignat(chopstick［(i+1)mod5］,chopstick［i］);untilfalse;讀者寫者問題（1）問題描述：有兩組并發(fā)進程:讀者和寫者,共享一組數(shù)據(jù)區(qū)要求：允許多個讀者同時執(zhí)行讀操作不允許讀者、寫者同時操作不允許多個寫者同時操作2.4.3讀者-寫者問題

1.利用記錄型信號量解決讀者-寫者問題為實現(xiàn)Reader與Writer進程間在讀或?qū)憰r的互斥而設(shè)置了一個互斥信號量Wmutex。設(shè)置一個整型變量Readcount表示正在讀的進程數(shù)目。Readcount是一個可被多個Reader進程訪問的臨界資源，為它設(shè)置一個互斥信號量rmutex。僅當Readcount=0,Reader進程才需要執(zhí)行Wait(Wmutex)操作。若wait(Wmutex)操作成功，Reader進程便可去讀，相應(yīng)地，做Readcount+1操作。僅當Reader進程在執(zhí)行了Readcount減1操作后其值為0時，才須執(zhí)行signal(Wmutex)操作，以便讓W(xué)riter進程寫。讀者-寫者問題可描述如下：Varrmutex,wmutex:semaphore∶=1,1;Readcount:integer∶=0;beginparbeginReader:beginrepeatwait(rmutex);ifreadcount=0thenwait(wmutex);/*只有第一個進入臨界區(qū)

Readcount∶=Readcount+1;的讀進程才須執(zhí)行wait操作*/signal(rmutex);…performreadoperation;…wait(rmutex);readcount∶=readcount-1;ifreadcount=0thensignal(wmutex);/*最后一個退出臨界區(qū)的讀

signal(rmutex);進程才須執(zhí)行signal操作*/untilfalse;endwriter:beginrepeatwait(wmutex);performwriteoperation;signal(wmutex);untilfalse;endparendend2.利用信號量集機制解決讀者-寫者問題

VarRNinteger;L,mx:semaphore∶=RN,1;beginparbeginreader:beginrepeatSwait(L,1,1);Swait(mx,1,0);…performreadoperation;…Ssignal(L,1);untilfalse;endwriter:beginrepeatSwait(mx,1,1;L,RN,0);performwriteoperation;Ssignal(mx,1);untilfalse;endparendend例:一個主修動物行為學(xué)、輔修計算機科學(xué)的學(xué)生參加一個課題，調(diào)查花果山的猴子是否能理解死鎖。他找到一個峽谷，橫跨峽谷拉了一根繩索（假設(shè)為南北方向），以便于猴子越過峽谷。只要它們朝著相同的方向，同一時刻可以有多只猴子通過。但是如果在相反的方向同時有猴子通過則會發(fā)生死鎖(這些猴子將被卡在繩索中間，假設(shè)這些猴子無法在繩索上從另一只猴子身上翻過去)。如果一只猴子想越過峽谷，它必須看當前是否有別的猴子在逆向通過。請用信號量機制寫一個避免死鎖的算法來解決該問題。解：將猴子越過峽谷的南北方向分別標記為S和W；并用整形變量countS、countW分別表示往S、W方向上已爬上繩索的猴子數(shù)，它們的初值為0；再設(shè)置三個初值為1的互斥信號量：SS用來實現(xiàn)對countS的互斥訪問，SW用來實現(xiàn)對countW的互斥訪問。mutex用來實現(xiàn)兩個方向上猴子對繩索的互斥使用。則可將往S方向上猴子的動作描述為：

wait(SS); if(countS=0)thenwait(mutex); countS:=countS+1; sigal(SS);

猴子通過繩索由北向南越過峽谷；

wait(SS); countS:=countS-1;if(countS=0)thensingal(mutex); sigal(SS); W方向上猴子的算法與S方向類似，只需將SS替換為SW，countS替換成countW即可。車輛互斥過橋問題？（北京大學(xué)1992年試題）北南橋

理發(fā)師問題：一個理發(fā)店由一個有N張沙發(fā)的等候室和一個放有一張理發(fā)椅的理發(fā)室組成。沒有顧客理發(fā)時，理發(fā)師便去睡覺。當一個顧客走進理發(fā)店時，如果所有的沙發(fā)都已被占用，他便離開理發(fā)店；否則，如果理發(fā)師正在為其他顧客理發(fā)，則該顧客找一張空沙發(fā)坐下等待；如果無顧客則直接由理發(fā)師理發(fā)。在理發(fā)完成后，顧客必須付費，直到理發(fā)師收費后才能離開理發(fā)店。試用信號量實現(xiàn)這一同步問題。本題中，顧客進程和理發(fā)師進程之間存在多種同步關(guān)系：1.只有在理發(fā)椅空閑時，顧客才能做到理發(fā)椅上等待理發(fā)師理發(fā)，否則顧客必須等待，只有當理發(fā)椅上有顧客時，理發(fā)師才理發(fā)，否則他也必須等待。這種同步關(guān)系類似單緩沖的生存者-消費者問題，故可通過信號量empty和full來控制。2.顧客理完發(fā)后必須向理發(fā)師付費，并等理發(fā)師收費后顧客才能離開，而理發(fā)師需要等待顧客付費，并在收費后通知顧客離開，這可以通過兩個信號量payment和receipt來控制。3.等待室中的N張沙發(fā)是顧客進程競爭的資源，故還需要為它設(shè)置一個資源信號量sofa4.為了控制顧客人數(shù)，使顧客能在所有的沙發(fā)都被占用時離開，還必須設(shè)置一個整型變量count來對理發(fā)店中的顧客進行計數(shù)，該變量將被多個顧客進程互斥地訪問并修改，這可通過一個互斥信號量mutex來實現(xiàn)。Varcount：integer：=0；

mutex，sofa，empty，full：semaphore：=1,N,1,0payment,receipt:semaphore:=0,0改進的生產(chǎn)者問題設(shè)有二個生產(chǎn)者進程A、B和一個銷售進程C，他們共享一個無限大的倉庫，生產(chǎn)者每次循環(huán)生產(chǎn)一個產(chǎn)品，然后入庫供銷售者銷售；銷售者每次循環(huán)從倉庫中取出一個產(chǎn)品進行銷售，如果不允許同時入庫，也不允許邊入庫邊出庫，而且要求生產(chǎn)A產(chǎn)品和B產(chǎn)品的件數(shù)滿足以下關(guān)系：-n≤A的件數(shù)-B的件數(shù)≤m，其中n，m是正整數(shù)，但對倉庫中A產(chǎn)品和B產(chǎn)品的件數(shù)無上述要求，請用信號量機制寫出A，B，C三個進程的工作流程。1.生產(chǎn)者A、B和消費者C之間不能同時將產(chǎn)品入庫出庫，故倉庫是一個臨界資源，設(shè)置一初始值為1的互斥信號量mutex；2.兩個生產(chǎn)者之間必須進行同步，當AB之差大于等于m時，生產(chǎn)者A必須等待；小于等于-n時，B必須等待。設(shè)置兩個令牌（也是臨界資源），SA表示當前允許A生產(chǎn)的產(chǎn)品數(shù)量，初值m，SB表示當前允許B生產(chǎn)的產(chǎn)品數(shù)量，初值為n；3.生產(chǎn)者和銷售者之間必須同步，只有生產(chǎn)者生產(chǎn)出產(chǎn)品并入庫后，銷售者才能進行銷售，設(shè)置一個初值為0的資源信號量S，對應(yīng)倉庫中的產(chǎn)品量；2.5管程機制2.5.1管程的基本概念1.管程的定義

管程由三部分組成：①局部于管程的共享變量說明；②對該數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程；③對局部于管程的數(shù)據(jù)設(shè)置初始值的語句。此外，還須為管程賦予一個名字。圖2-11管程的示意圖管程的語法如下：

typemonitor-name=monitorvariabledeclarationsprocedureentryP1(…);begin…end;procedureentryP2(…);begin…end;…procedureentryPn(…);begin…end;begininitializationcode;end2.條件變量

管程中對每個條件變量，都須予以說明，其形式為：Varx,y:condition。該變量應(yīng)置于wait和signal之前，即可表示為X.wait和X.signal。例如，由于共享數(shù)據(jù)被占用而使調(diào)用進程等待，該條件變量的形式為：nonbusy:condition。此時，wait原語應(yīng)改為nonbusy.wait，相應(yīng)地，signal應(yīng)改為nonbusy.signal。應(yīng)當指出，X.signal操作的作用，是重新啟動一個被阻塞的進程，但如果沒有被阻塞的進程，則X.signal操作不產(chǎn)生任何后果。這與信號量機制中的signal操作不同。因為，后者總是要執(zhí)行s∶=s+1操作，因而總會改變信號量的狀態(tài)。

如果有進程Q處于阻塞狀態(tài)，當進程P執(zhí)行了X.signal操作后，怎樣決定由哪個進行執(zhí)行，哪個等待，可采用下述兩種方式之一進行處理：

(1)P等待，直至Q離開管程或等待另一條件。

(2)Q等待，直至P離開管程或等待另一條件。采用哪種處理方式，當然是各執(zhí)一詞。但是Hansan卻采用了第一種處理方式。2.5.2利用管程解決生產(chǎn)者-消費者問題

在利用管程方法來解決生產(chǎn)者-消費者問題時，首先便是為它們建立一個管程，并命名為Proclucer-Consumer,或簡稱為PC。其中包括兩個過程：

(1)put(item)過程。生產(chǎn)者利用該過程將自己生產(chǎn)的產(chǎn)品投放到緩沖池中，并用整型變量count來表示在緩沖池中已有的產(chǎn)品數(shù)目，當count≥n時，表示緩沖池已滿，生產(chǎn)者須等待。(1)put(item)過程。生產(chǎn)者利用該過程將自己生產(chǎn)的產(chǎn)品投放到緩沖池中，并用整型變量count來表示在緩沖池中已有的產(chǎn)品數(shù)目，當count≥n時，表示緩沖池已滿，生產(chǎn)者須等待。

(2)get(item)過程。消費者利用該過程從緩沖池中取出一個產(chǎn)品，當count≤0時，表示緩沖池中已無可取用的產(chǎn)品，消費者應(yīng)等待。typeproducer-consumer=monitorVarin,out,count:integer;buffer:array［0,…,n-1］ofitem;notfull,notempty:condition;procedureentryput(item)beginifcount≥nthennotfull.wait;buffer(in)∶=nextp;in∶=(in+1)modn;count∶=count+1;ifnotempty.queuethennotempty.signal;endprocedureentryget(item)beginifcount≤0thennotempty.wait;nextc∶=buffer(out);out∶=(out+1)modn;count∶=count-1;ifnotfull.quenethennotfull.signal;endbeginin∶=out∶=0;count∶=0end

在利用管程解決生產(chǎn)者-消費者問題時，其中的生產(chǎn)者和消費者可描述為：producer:beginrepeatproduceaniteminnextp;PC.put(item);untilfalse;endconsumer:beginrepeatPC.get(item);consumetheiteminnextc;untilfalse;end低級通信：只能傳遞狀態(tài)和整數(shù)值（控制信息），包括進程互斥和同步所采用的信號量和管程機制。優(yōu)點的速度快。缺點是：傳送信息量?。盒实?，每次通信傳遞的信息量固定，若傳遞較多信息則需要進行多次通信。編程復(fù)雜：用戶