第二章進(jìn)程管理

第二章進(jìn)程管理2.1進(jìn)程的基本概念2.2進(jìn)程控制2.3進(jìn)程同步2.4經(jīng)典進(jìn)程的同步問題2.5進(jìn)程通信2.6線程2.1進(jìn)程的基本概念2.1.1程序的順序執(zhí)行及其特征1.程序的順序執(zhí)行僅當(dāng)前一操作(程序段)執(zhí)行完后，才能執(zhí)行后繼操作。例如，在進(jìn)行計(jì)算時(shí)，總須先輸入用戶的程序和數(shù)據(jù)，然后進(jìn)行計(jì)算，最后才能打印計(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í)行時(shí)的特征順序性：處理機(jī)的操作必須嚴(yán)格按照程序所規(guī)定的順序執(zhí)行(2)封閉性：程序在執(zhí)行時(shí)獨(dú)占系統(tǒng)的全部資源，因此機(jī)器資源狀態(tài)的改變只與執(zhí)行的程序有關(guān)，與外界環(huán)境無關(guān)(3)可再現(xiàn)性：只要初始條件相同，一個(gè)程序的多次重復(fù)執(zhí)行，將得到相同的結(jié)果2.1.2前趨圖

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

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

每個(gè)結(jié)點(diǎn)還具有一個(gè)重量(Weight)，用于表示該結(jié)點(diǎn)所含有的程序量或結(jié)點(diǎn)的執(zhí)行時(shí)間。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)當(dāng)注意，前趨圖中必須不存在循環(huán)，但在圖2-2(b)中卻有著下述的前趨關(guān)系：S2→S3,S3→S2

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

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

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

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

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

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

較典型的進(jìn)程定義有：

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

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

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

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

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

終端用戶的請求。

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

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

當(dāng)負(fù)荷較重，影響對實(shí)時(shí)任務(wù)的控制

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

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

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

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

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

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

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

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

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

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

②保護(hù)錯(cuò)。進(jìn)程試圖去訪問一個(gè)不允許訪問的資源或文件，或者以不適當(dāng)?shù)姆绞竭M(jìn)行訪問，例如，進(jìn)程試圖去寫一個(gè)只讀文件；

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

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

1.進(jìn)程的掛起

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

2.進(jìn)程的激活過程

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

2.3.1進(jìn)程同步的基本概念

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

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

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

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

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

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

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

輸出指針加1表示成out∶=(out+1)modn。當(dāng)(in+1)modn=out時(shí)表示緩沖池滿；而in=out則表示緩沖池空。此外，還引入了一個(gè)整型變量counter,其初始值為0。每當(dāng)生產(chǎn)者進(jìn)程向緩沖池中投放一個(gè)產(chǎn)品后，使counter加1；反之，每當(dāng)消費(fèi)者進(jìn)程從中取走一個(gè)產(chǎn)品時(shí)，使counter減1。生產(chǎn)者和消費(fèi)者兩進(jì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)者和消費(fèi)者進(jìn)程的描述中，no-op是一條空操作指令，whilecondicationdono-op語句表示重復(fù)的測試條件(condication)，重復(fù)測試應(yīng)進(jìn)行到該條件變?yōu)閒alse(假)，即到該條件不成立時(shí)為止。在生產(chǎn)者進(jìn)程中使用一局部變量nextp，用于暫時(shí)存放每次剛生產(chǎn)出來的產(chǎn)品；而在消費(fèi)者進(jìn)程中，則使用一個(gè)局部變量nextc,用于存放每次要消費(fèi)的產(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)者程序和消費(fèi)者程序，在分別看時(shí)都是正確的，而且兩者在順序執(zhí)行時(shí)其結(jié)果也會是正確的，但若并發(fā)執(zhí)行時(shí)，就會出現(xiàn)差錯(cuò)，問題就在于這兩個(gè)進(jìn)程共享變量counter。生產(chǎn)者對它做加1操作，消費(fèi)者對它做減1操作，這兩個(gè)操作在用機(jī)器語言實(shí)現(xiàn)時(shí)，?？捎孟旅娴男问矫枋觯簉egister1∶=counter;register2∶=counter;register1∶=register1+1;register2∶=register2-1;counter∶=register1;counter∶=register2;假設(shè)：counter的當(dāng)前值是5。如果生產(chǎn)者進(jìn)程先執(zhí)行左列的三條機(jī)器語言語句，然后消費(fèi)者進(jìn)程再執(zhí)行右列的三條語句，則最后共享變量counter的值仍為5；反之，如果讓消費(fèi)者進(jìn)程先執(zhí)行右列的三條語句，然后再讓生產(chǎn)者進(jì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)

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

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

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

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

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

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

2.記錄型信號量在整型信號量機(jī)制中的wait操作，只要是信號量S≤0，就會不斷地測試。因此，該機(jī)制并未遵循“讓權(quán)等待”的準(zhǔn)則，而是使進(jìn)程處于“忙等”的狀態(tài)。記錄型信號量機(jī)制，則是一種不存在“忙等”現(xiàn)象的進(jìn)程同步機(jī)制。但在采取了“讓權(quán)等待”的策略后，又會出現(xiàn)多個(gè)進(jìn)程等待訪問同一臨界資源的情況。為此，在信號量機(jī)制中，除了需要一個(gè)用于代表資源數(shù)目的整型變量value外，還應(yīng)增加一個(gè)進(jìn)程鏈表L，用于鏈接上述的所有等待進(jìn)程。記錄型信號量是由于它采用了記錄型的數(shù)據(jù)結(jié)構(gòu)而得名的。它所包含的上述兩個(gè)數(shù)據(jù)項(xiàng)可描述為：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

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

3.AND型信號量在兩個(gè)進(jìn)程中都要包含兩個(gè)對Dmutex和Emutex的操作，即processA: processB:wait(Dmutex); wait(Emutex);wait(Emutex); wait(Dmutex);若進(jìn)程A和B按下述次序交替執(zhí)行wait操作：processA:wait(Dmutex);于是Dmutex=0processB:wait(Emutex);于是Emutex=0processA:wait(Emutex);于是Emutex=-1A阻塞processB:wait(Dmutex);于是Dmutex=-1B阻塞AND同步機(jī)制的基本思想是：將進(jìn)程在整個(gè)運(yùn)行過程中需要的所有資源，一次性全部地分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。只要尚有一個(gè)資源未能分配給進(jìn)程，其它所有可能為之分配的資源，也不分配給他。亦即，對若干個(gè)臨界資源的分配，采取原子操作方式：要么全部分配到進(jìn)程，要么一個(gè)也不分配。由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。為此，在wait操作中，增加了一個(gè)“AND”條件，故稱為AND同步，或稱為同時(shí)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)。此時(shí)在信號量集中只有一個(gè)信號量S，但允許它每次申請d個(gè)資源，當(dāng)現(xiàn)有資源數(shù)少于d時(shí)，不予分配。

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

(3)Swait(S,1,0)。這是一種很特殊且很有用的信號量操作。當(dāng)S≥1時(shí)，允許多個(gè)進(jìn)程進(jìn)入某特定區(qū)；當(dāng)S變?yōu)?后，將阻止任何進(jìn)程進(jìn)入特定區(qū)。換言之，它相當(dāng)于一個(gè)可控開關(guān)。2.3.3信號量的應(yīng)用1.利用信號量實(shí)現(xiàn)進(jìn)程互斥利用信號量實(shí)現(xiàn)進(jìn)程互斥的進(jì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.利用信號量實(shí)現(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年試題司機(jī)和售票員之間的同步關(guān)系司機(jī)只有在售票員關(guān)車門后，才能啟動汽車。售票員只有在司機(jī)到站停車后，才能開車門。解：Semaphoreclose=0，stop=0；driver() { /*司機(jī)*/ while(True){ P(close);

啟動車輛;

正常行車;

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

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

售票; P(stop);

開車門;

上下乘客; }}Main(){parbegin(driver,conductor);}2.4經(jīng)典進(jìn)程的同步問題2.4.1生產(chǎn)者—消費(fèi)者問題前面我們已經(jīng)對生產(chǎn)者—消費(fèi)者問題(Theproceducer-consumerproblem)做了一些描述，但未考慮進(jìn)程的互斥與同步問題，因而造成了數(shù)據(jù)Counter的不定性。由于生產(chǎn)者—消費(fèi)者問題是相互合作的進(jìn)程關(guān)系的一種抽象，例如，在輸入時(shí)，輸入進(jìn)程是生產(chǎn)者，計(jì)算進(jìn)程是消費(fèi)者；而在輸出時(shí)，則計(jì)算進(jìn)程是生產(chǎn)者，而打印進(jìn)程是消費(fèi)者，因此，該問題有很大的代表性及實(shí)用價(jià)值。1.利用記錄型信號量解決生產(chǎn)者—消費(fèi)者問題假定在生產(chǎn)者和消費(fèi)者之間的公用緩沖池中，具有n個(gè)緩沖區(qū)，這時(shí)可利用互斥信號量mutex實(shí)現(xiàn)諸進(jìn)程對緩沖池的互斥使用；利用信號量empty和full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。又假定這些生產(chǎn)者和消費(fèi)者相互等效，只要緩沖池未滿，生產(chǎn)者便可將消息送入緩沖池；只要緩沖池未空，消費(fèi)者便可從緩沖池中取走一個(gè)消息。對生產(chǎn)者—消費(fèi)者問題可描述如下：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)者—消費(fèi)者問題中應(yīng)注意：首先，在每個(gè)程序中用于實(shí)現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對地出現(xiàn)；其次，對資源信號量empty和full的wait和signal操作，同樣需要成對地出現(xiàn)，但它們分別處于不同的程序中。例如，wait(empty)在計(jì)算進(jìn)程中，而signal(empty)則在打印進(jìn)程中，計(jì)算進(jìn)程若因執(zhí)行wait(empty)而阻塞，則以后將由打印進(jìn)程將它喚醒；最后，在每個(gè)程序中的多個(gè)wait操作順序不能顛倒。應(yīng)先執(zhí)行對資源信號量的wait操作，然后再執(zhí)行對互斥信號量的wait操作，否則可能引起進(jìn)程死鎖。2.利用AND信號量解決生產(chǎn)者—消費(fèi)者問題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個(gè)并發(fā)進(jìn)程get、copy和put共享緩沖器B1和B2。進(jìn)程get負(fù)責(zé)從輸入設(shè)備上讀信息，每讀出一條記錄后放到B1中。進(jìn)程copy從緩沖器B1中取出一條記錄拷貝后存入B2。進(jìn)程put取出B2中的記錄打印輸出。B1和B2每次只能存放一條記錄。要求3個(gè)進(jìn)程協(xié)調(diào)完成任務(wù)，使打印出來的與讀入的記錄個(gè)數(shù)、次序完全一樣。請用記錄型信號量寫出并發(fā)程序。解：

設(shè)置4個(gè)信號量，其中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)進(jìn)程描述為：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);}水果問題桌上有一只盤子，最多可容納兩個(gè)水果，每次只能放入或取出一個(gè)水果。爸爸專向盤中放蘋果，媽媽專向盤中放橘子；兒子專等吃盤子中的橘子，女兒專等吃盤子中的蘋果。請用P、V操作實(shí)現(xiàn)爸爸、媽媽、兒子、女兒之間的同步與互斥關(guān)系。水果問題桌上有一只盤子，最多可容納兩個(gè)水果，每次只能放入或取出一個(gè)水果。爸爸專向盤中放蘋果，媽媽專向盤中放橘子；兒子專等吃盤子中的橘子，女兒專等吃盤子中的蘋果。請用P、V操作實(shí)現(xiàn)爸爸、媽媽、兒子、女兒之間的同步與互斥關(guān)系。答：設(shè)置信號量empty表示還可以向盤中放幾個(gè)水果，其初值為2；apple對應(yīng)已放入盤中的蘋果，orange對應(yīng)已放入盤中的橘子，它們的初值均為0；mutex用來實(shí)現(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é)家進(jìn)餐問題

1.利用記錄型信號量解決哲學(xué)家進(jìn)餐問題經(jīng)分析可知，放在桌子上的筷子是臨界資源，在一段時(shí)間內(nèi)只允許一位哲學(xué)家使用。為了實(shí)現(xiàn)對筷子的互斥使用，可以用一個(gè)信號量表示一只筷子，由這五個(gè)信號量構(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é)家同時(shí)去拿左邊的筷子，最終能保證至少有一位哲學(xué)家能夠進(jìn)餐，并在用畢時(shí)能釋放出他用過的兩只筷子，從而使更多的哲學(xué)家能夠進(jìn)餐。

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

(3)規(guī)定奇數(shù)號哲學(xué)家先拿他左邊的筷子，然后再去拿右邊的筷子；而偶數(shù)號哲學(xué)家則相反。按此規(guī)定，將是1、2號哲學(xué)家競爭1號筷子；3、4號哲學(xué)家競爭3號筷子。即五位哲學(xué)家都先競爭奇數(shù)號筷子，獲得后，再去競爭偶數(shù)號筷子，最后總會有一位哲學(xué)家能獲得兩只筷子而進(jìn)餐。2.利用AND信號量機(jī)制解決哲學(xué)家進(jìn)餐問題在哲學(xué)家進(jìn)餐問題中，要求每個(gè)哲學(xué)家先獲得兩個(gè)臨界資源(筷子)后方能進(jìn)餐，這在本質(zhì)上就是前面所介紹的AND同步問題，故用AND信號量機(jī)制可獲得最簡潔的解法。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ā)進(jìn)程:讀者和寫者,共享一組數(shù)據(jù)區(qū)要求：允許多個(gè)讀者同時(shí)執(zhí)行讀操作不允許讀者、寫者同時(shí)操作不允許多個(gè)寫者同時(shí)操作2.4.3讀者-寫者問題

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

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

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

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例:一個(gè)主修動物行為學(xué)、輔修計(jì)算機(jī)科學(xué)的學(xué)生參加一個(gè)課題，調(diào)查花果山的猴子是否能理解死鎖。他找到一個(gè)峽谷，橫跨峽谷拉了一根繩索（假設(shè)為南北方向），以便于猴子越過峽谷。只要它們朝著相同的方向，同一時(shí)刻可以有多只猴子通過。但是如果在相反的方向同時(shí)有猴子通過則會發(fā)生死鎖(這些猴子將被卡在繩索中間，假設(shè)這些猴子無法在繩索上從另一只猴子身上翻過去)。如果一只猴子想越過峽谷，它必須看當(dāng)前是否有別的猴子在逆向通過。請用信號量機(jī)制寫一個(gè)避免死鎖的算法來解決該問題。解：將猴子越過峽谷的南北方向分別標(biāo)記為S和W；并用整形變量countS、countW分別表示往S、W方向上已爬上繩索的猴子數(shù)，它們的初值為0；再設(shè)置三個(gè)初值為1的互斥信號量：SS用來實(shí)現(xiàn)對countS的互斥訪問，SW用來實(shí)現(xiàn)對countW的互斥訪問。mutex用來實(shí)現(xiàn)兩個(gè)方向上猴子對繩索的互斥使用。則可將往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ā)師問題：一個(gè)理發(fā)店由一個(gè)有N張沙發(fā)的等候室和一個(gè)放有一張理發(fā)椅的理發(fā)室組成。沒有顧客理發(fā)時(shí)，理發(fā)師便去睡覺。當(dāng)一個(gè)顧客走進(jìn)理發(fā)店時(shí)，如果所有的沙發(fā)都已被占用，他便離開理發(fā)店；否則，如果理發(fā)師正在為其他顧客理發(fā)，則該顧客找一張空沙發(fā)坐下等待；如果無顧客則直接由理發(fā)師理發(fā)。在理發(fā)完成后，顧客必須付費(fèi)，直到理發(fā)師收費(fèi)后才能離開理發(fā)店。試用信號量實(shí)現(xiàn)這一同步問題。本題中，顧客進(jìn)程和理發(fā)師進(jìn)程之間存在多種同步關(guān)系：1.只有在理發(fā)椅空閑時(shí)，顧客才能做到理發(fā)椅上等待理發(fā)師理發(fā)，否則顧客必須等待，只有當(dāng)理發(fā)椅上有顧客時(shí)，理發(fā)師才理發(fā)，否則他也必須等待。這種同步關(guān)系類似單緩沖的生存者-消費(fèi)者問題，故可通過信號量empty和full來控制。2.顧客理完發(fā)后必須向理發(fā)師付費(fèi)，并等理發(fā)師收費(fèi)后顧客才能離開，而理發(fā)師需要等待顧客付費(fèi)，并在收費(fèi)后通知顧客離開，這可以通過兩個(gè)信號量payment和receipt來控制。3.等待室中的N張沙發(fā)是顧客進(jìn)程競爭的資源，故還需要為它設(shè)置一個(gè)資源信號量sofa4.為了控制顧客人數(shù)，使顧客能在所有的沙發(fā)都被占用時(shí)離開，還必須設(shè)置一個(gè)整型變量count來對理發(fā)店中的顧客進(jìn)行計(jì)數(shù)，該變量將被多個(gè)顧客進(jìn)程互斥地訪問并修改，這可通過一個(gè)互斥信號量mutex來實(shí)現(xiàn)。Varcount：integer：=0；

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

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

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

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

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

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

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

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

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

(2)get(item)過程。消費(fèi)者利用該過程從緩沖池中取出一個(gè)產(chǎn)品，當(dāng)count≤0時(shí)，表示緩沖池中已無可取用的產(chǎn)品，消費(fèi)者應(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)者-消費(fèi)者問題時(shí)，其中的生產(chǎn)者和消費(fèi)者可描述為：producer:beginrepeatproduceaniteminnextp;PC.put(item);untilfalse;endconsumer:beginrepeatPC.get(item);consumetheiteminnextc;untilfalse;end低級通信：只能傳遞狀態(tài)和整數(shù)值（控制信息），包括進(jìn)程互斥和同步所采用的信號量和管程機(jī)制。優(yōu)點(diǎn)的速度快。缺點(diǎn)是：傳送信息量?。盒实停看瓮ㄐ艂鬟f的信息量固定，若傳遞較多信息則需要進(jìn)行多次通信。編程復(fù)雜：用戶