操作系統(tǒng)原理：第02章 進程管理

2022/11/19第二章進程管理第二章

進程管理2.1進程的基本概念2.2進程控制2.3進程同步2.4經(jīng)典進程的同步問題2.5進程通信2.6線程

2.1進程的基本概念進程的概念是操作系統(tǒng)中最基本、最重要的概念。它是在多道程序系統(tǒng)出現(xiàn)后，為了刻劃系統(tǒng)內(nèi)部出現(xiàn)的情況，描述系統(tǒng)內(nèi)部各作業(yè)的活動規(guī)律而引進的一個新的概念2.1.1程序的順序執(zhí)行及特征1.程序的順序執(zhí)行一個復(fù)雜的程序一般均含若干個程序段，并按一定先后順序執(zhí)行，每個操作必須在下一個操作開始之前結(jié)束。也即僅當前一個操作結(jié)束之后，后繼操作才開始執(zhí)行，此即程序的順序執(zhí)行性。

2.1.1程序的順序執(zhí)行及特征例如一般程序包括輸入(I)、計算(C)、輸出(P)三部分，而計算須在輸入完成后方可開始，而輸出須在計算完成后才能進行。I1C1P1I2C2P21.程序的順序執(zhí)行對一個程序段中的多條語句來說，也有一個執(zhí)行順序問題，例如對于下述三條語句的程序段:S1：a:=x+yS2：b:=a-5S3：c:=b+1

如下圖，語句S2必須在a被賦值后才能執(zhí)行；S3也只能在b被賦值后才能執(zhí)行。S1S2S32.程序的順序執(zhí)行的特征順序性：一個程序的各個部分的執(zhí)行，嚴格地按照某種先后次序執(zhí)行；封閉性：程序一旦開始執(zhí)行，其執(zhí)行結(jié)果不受外界因素影響?？稍佻F(xiàn)性：只要程序執(zhí)行時的環(huán)境和初始條件相同，當程序重復(fù)執(zhí)行時，將獲得相同的結(jié)果。2.1.2.前趨圖前趨圖：用于描述一個程序的各部分（程序段或語句）間的執(zhí)行順序關(guān)系，或者是一個大的計算的各個子任務(wù)間的因果關(guān)系。是一個有向無循環(huán)圖，每個結(jié)點用于表示一條語句、一個程序段或一個進程；結(jié)點間的有向邊表示兩個結(jié)點之間存在的偏序或前趨關(guān)系

“→”。2.1.2.前趨圖結(jié)點間的有向邊表示兩個結(jié)點之間存在的偏序(Partial_Order)或前趨關(guān)系(Precedence_Relation)“→”＝{(Pi,Pj)|在Pj開始前Pi必須完成}，如果(Pi,Pj)∈→，可寫成Pi→Pj，Pi是Pj的直接前趨，Pj是Pi的直接后繼。每個結(jié)點還具有一個重量。2.1.2.前趨圖2.1.2.前趨圖該前趨圖，存在下面的前趨關(guān)系：P1→P2，P1→P3，P1→P4，P2→P5，P3→P5，P4→P6，P4→P7，P5→P8，P6→P8，P7→P9，P8→P9；或表示為：Ｐ={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)}例：下述幾條語句的程序段畫出前趨圖P1→P2，P1→P3，P1→P4，P2→P5，P3→P5，P3→P6，P4→P6，2.1.2.前趨圖2.1.3程序并發(fā)執(zhí)行及特征并發(fā)環(huán)境：

在一定時間內(nèi)物理機器上有兩個或兩個以上的程序同處于開始運行但尚未結(jié)束的狀態(tài)，并且次序不是事先確定的，就稱這幾個程序是并發(fā)執(zhí)行的。1.程序的并發(fā)執(zhí)行在對一批程序進行處理時，可以并發(fā)執(zhí)行。例如，輸入、計算、打印三個程序?qū)σ慌鳂I(yè)進行處理時前趨關(guān)系圖如下：在該例中存在下述前趨關(guān)系：

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

S1:a∶=x+2S2:b∶=y+4S3:c∶=a+bS4:d∶=c+b1.程序的并發(fā)執(zhí)行假設(shè)有一個程序由S0～Sn+1個語句，其中S1～Sn語句是并發(fā)執(zhí)行的，程序如下：

S0;cobeginS1;S2;S3;...;SNcoend;Sn+1;三個并發(fā)執(zhí)行程序的謄抄假設(shè)有兩個緩沖區(qū)，每個緩沖區(qū)只存放一個字符。

get程序負責從輸入序列f中讀取字符并送到緩沖區(qū)s中;copy程序把緩沖區(qū)s中的數(shù)據(jù)復(fù)制到緩沖區(qū)t中去;put程序從緩沖區(qū)t中取出數(shù)據(jù)打印。getcopyputfstg輸入f輸出g{If(f不為空）

{Get(s,f)while(謄寫未完成）

{t=scobeginput(t,g)Get(s,f)coend}}}cpcgpcgpg并行環(huán)境下程序間的制約關(guān)系與時間有關(guān)的錯誤假定f系列中有記錄

f=(R1,R2,...,Rn)g=()在謄抄完成后：

f=()g=(R1,R2,...,Rn)算法中的：copy≡t=sput≡put(t,g)get≡get(s,f)與時間有關(guān)的錯誤若程序錯寫成：while(謄抄未完成）{cobegincopy;put;get;coend}初始狀態(tài)：

f=(R1,R2,...,Rn)s=()t=()g=()首先執(zhí)行了get(s,f)f=(R1,R2,...,Rn)s=R1,t=(),g=()copy,put,get三個程序段并發(fā)執(zhí)行，就有六種組合：1、copy;put;get導致結(jié)果：g=(R1,R2)2、copy;get;put導致結(jié)果：g=(R1,R2)3、put;copy;get導致結(jié)果：g=(R1,R1)4、put;get;copy導致結(jié)果：g=(R1,R1)5、get;copy;put導致結(jié)果：g=(R1,R3)6、get;put;copy導致結(jié)果：g=(R1,R1)這就是與時間有關(guān)的錯誤。與時間有關(guān)的錯誤2.程序的并發(fā)執(zhí)行的特征1)間斷性:程序在并發(fā)執(zhí)行時，由于它們共享資源或為完成某一項任務(wù)而合作，致使在并發(fā)程序之間存在相互制約的關(guān)系。

2)失去封閉性:程序在并發(fā)執(zhí)行時，是多個程序共享系統(tǒng)中的各種資源，因而這些資源的狀態(tài)將由多個程序來改變，致使程序的運行失去了封閉性。

3)不可再現(xiàn)性:程序在并發(fā)執(zhí)行時，由于失去了封閉性，也導致失去了可再現(xiàn)性。2.程序的并發(fā)執(zhí)行的特征并發(fā)程序A和B，共享變量n，程序A做n=n+1操作；程序B執(zhí)行print（n）操作。兩種情況：（假設(shè)當前變量n的值為100）執(zhí)行方式1：

A：n=n+1；

B：print（n）；結(jié)果：B打印n的值為101。執(zhí)行方式2：

B：print（n）；

A：n=n+1；結(jié)果：B打印n的值為100。2.1.4進程的特征與狀態(tài)在多道程序環(huán)境下，程序具有了并行、制約和動態(tài)的特征，程序概念已刻劃不清系統(tǒng)的這種并行情況，反映不了它們的活動規(guī)律和狀態(tài)變化。為了動態(tài)地看待操作系統(tǒng)，則以進程作為資源分配和獨立運行的基本單位，從進程觀點來研究操作系統(tǒng)，操作系統(tǒng)所具有的所有特征也都是基于進程而形成的。1.進程的特征和定義進程：是指在系統(tǒng)中能獨立運行并作為資源分配的基本單位，是一個活動實體。也可以說，進程是程序在數(shù)據(jù)集合上的一次運行過程，是系統(tǒng)進行資源分配和調(diào)度的基本單位。進程是一個動態(tài)的概念，是一個運行過程。它不同于程序，但又依賴于程序。對不同的數(shù)據(jù)集合，依照一定的程序運行處理的每一個過程是每個不同的進程。在系統(tǒng)中同時有多個進程存在，但歸納起來有兩大類：1、系統(tǒng)進程系統(tǒng)進程起著資源管理和控制的作用。

或者：執(zhí)行操作系統(tǒng)核心代碼的進程。2、用戶進程執(zhí)行用戶程序的進程。一般來講，在管態(tài)下執(zhí)行的進程稱為系統(tǒng)進程；在目態(tài)下執(zhí)行的進程稱為用戶進程。進程的特征結(jié)構(gòu)特征：為了控制和管理進程，系統(tǒng)為每個進程設(shè)立一個進程控制塊－PCB。動態(tài)性：進程的實質(zhì)是程序的一次執(zhí)行過程， 進程是動態(tài)產(chǎn)生，動態(tài)消亡的，進程在其生命周期內(nèi)，在三種基本狀態(tài)之間轉(zhuǎn)換并發(fā)性：任何進程都可以同其他進程一起向前推進獨立性：進程是一個能獨立運行的基本單位，同時也是系統(tǒng)分配資源和調(diào)度的獨立單位；異步性：由于進程間的相互制約，使進程具有執(zhí)行的間斷性，即進程按各自獨立的、不可預(yù)知的速度向前推進進程與程序的區(qū)別程序是靜態(tài)的，進程是動態(tài)的;進程更能真實地描述并發(fā),而程序不能;一個程序可對應(yīng)多個進程，反之亦然;程序可作為軟件資源長期保存，進程只是一次執(zhí)行過程，是暫時的；進程是系統(tǒng)分配調(diào)度的獨立單位，能與其他進程并發(fā)執(zhí)行;進程是由程序、數(shù)據(jù)和進程控制塊組成進程具有創(chuàng)建其他進程的功能，而程序沒有

2.進程的三種基本狀態(tài)在進程運行過程中，由于系統(tǒng)中多個進程的并發(fā)運行及相互制約的結(jié)果，使得進程的狀態(tài)不斷發(fā)生變化。進程在系統(tǒng)中的活動規(guī)律是：執(zhí)行暫停執(zhí)行進程的三種基本狀態(tài)：

運行狀態(tài)就緒狀態(tài)

阻塞狀態(tài)

2.進程的三種基本狀態(tài)1)就緒(Ready)狀態(tài)

當進程已經(jīng)分配到除CPU以外的所有必要的資源后，只要能獲得處理機，就可以立即執(zhí)行。這時的進程的狀態(tài)稱為就緒狀態(tài)2)執(zhí)行狀態(tài)(Running)（運行狀態(tài)）

指進程已獲得處理機，其程序正在執(zhí)行。在單處理機系統(tǒng)中，只能有一個進程處于執(zhí)行狀態(tài)。（在多處理機中，可能有多個進程處于執(zhí)行狀態(tài)）

2.進程的三種基本狀態(tài)3)阻塞狀態(tài)(Block)

進程因發(fā)生某個事件而暫停執(zhí)行時的狀態(tài)（如：請求I/O、申請緩沖空間等），也就是說，進程受到阻塞，所以稱這種暫停狀態(tài)為阻塞狀態(tài)，有時也稱“等待”狀態(tài)或“睡眠”狀態(tài)。進程的狀態(tài)及其轉(zhuǎn)換運行就緒等待

2.進程的三種基本狀態(tài)進程狀態(tài)轉(zhuǎn)換條件在進程運行過程中，由于自身進展情況及外界環(huán)境的變化，這三種基本狀態(tài)可以依據(jù)一定的條件相互轉(zhuǎn)換：就緒-->運行調(diào)度程序選擇一個新的進程運行運行-->就緒運行進程用完了時間片運行進程被中斷，因為一高優(yōu)先級進程處于就緒狀態(tài)進程狀態(tài)轉(zhuǎn)換條件運行-->阻塞當一進程必須等待時OS尚未完成服務(wù)對一資源的訪問尚不能進行初始化I/O且必須等待結(jié)果等待某一進程提供輸入(IPC)等待-->就緒當所等待的事件發(fā)生時3.掛起狀態(tài)在某些系統(tǒng)中，為了更好地管理和調(diào)度進程及適應(yīng)系統(tǒng)的功能目標，引入了掛起狀態(tài)。1)引入掛起狀態(tài)的原因(1)終端用戶的需要(2)父進程請求。(3)負荷調(diào)節(jié)的需要。(4)操作系統(tǒng)的需要。3.掛起狀態(tài)具有掛起和解掛功能的系統(tǒng)進程狀態(tài)中，新增加了兩個狀態(tài)：掛起就緒（ReadySuspend）掛起阻塞（BlockedSuspend）為了易于區(qū)分，將原來的就緒狀態(tài)和阻塞狀態(tài)分別稱為：活動就緒（ReadyActive）活動阻塞（BlockedActive）2)進程狀態(tài)的轉(zhuǎn)換在引入掛起狀態(tài)后，又將增加從掛起狀態(tài)到非掛起狀態(tài)的轉(zhuǎn)換?；蛘呦喾?，可以有以下幾種情況：

(1)活動就緒靜止就緒

(2)活動阻塞靜止阻塞

(3)靜止就緒活動就緒

(4)靜止阻塞活動阻塞3.掛起狀態(tài)執(zhí)行靜止就緒活動阻塞活動就緒靜止阻塞掛起釋放激活掛起激活掛起釋放請求I/O調(diào)度創(chuàng)建狀態(tài)終止狀態(tài)創(chuàng)建一個進程一般要通過兩個步驟：首先，為一個新進程創(chuàng)建PCB，并填寫必要的管理信息；其次，把該進程轉(zhuǎn)入就緒狀態(tài)并插入就緒隊列之中。4．創(chuàng)建狀態(tài)和終止狀態(tài)創(chuàng)建狀態(tài)OS已完成為創(chuàng)建一進程所必要的工作已構(gòu)造了進程標識符已創(chuàng)建了管理進程所需的表格但還沒有允許執(zhí)行該進程(尚未同意)

因為資源有限終止狀態(tài)終止狀態(tài)的進程不再有執(zhí)行資格進程的終止也要通過兩個步驟：首先等待操作系統(tǒng)進行善后處理；然后將其PCB清零，并將PCB空間返還系統(tǒng)。當一個進程到達了自然結(jié)束點，或是出現(xiàn)了無法克服的錯誤，或是被操作系統(tǒng)所終結(jié)，或是被其他有終止權(quán)的進程所終結(jié)，它將進入終止狀態(tài)。五態(tài)模型

引進創(chuàng)建和終止狀態(tài)后，在進程狀態(tài)轉(zhuǎn)換時，需要增加考慮下面的幾種情況。(1)NULL→創(chuàng)建：(2)創(chuàng)建→活動就緒(3)創(chuàng)建→靜止就緒(4)執(zhí)行→終止七態(tài)模型

2.1.5進程控制塊（PCB）系統(tǒng)為了管理進程設(shè)置的一個專門的數(shù)據(jù)結(jié)構(gòu)，用來記錄進程的外部特征，描述進程的變化過程。進程的靜態(tài)描述(進程映像)：由三部分組成1)

PCB(ProcessControlBlock)2)程序段3)數(shù)據(jù)段用于描述進程情況及控制進程運行所需的全部信息。是進程中能被進程調(diào)度程序在CPU上執(zhí)行的程序代碼段。一個進程的數(shù)據(jù)段，可以是進程對應(yīng)的程序加工處理的原始數(shù)據(jù)，也可以是程序執(zhí)行后產(chǎn)生的中間或最終數(shù)據(jù)。1．進程控制塊的作用系統(tǒng)利用PCB來控制和管理進程，進程控制塊既能標識進程的存在，又能刻畫出進程的動態(tài)特征，所以PCB是系統(tǒng)感知進程存在的唯一標志進程與PCB是一一對應(yīng)的當系統(tǒng)或父進程創(chuàng)建一個進程時，實際上就是為其建立一個進程控制塊。2.進程控制塊中的信息1)進程標識符進程標識符用于惟一地標識一個進程。內(nèi)部標識符外部標識符家族聯(lián)系2.進程控制塊中的信息

2)處理機狀態(tài)說明進程當前所處的狀態(tài)。處理機狀態(tài)信息主要是由處理機的各種寄存器中的內(nèi)容組成的。通用寄存器指令計數(shù)器程序狀態(tài)字PSW

用戶棧指針2.進程控制塊中的信息3)進程調(diào)度信息存放一些與進程調(diào)度和進程對換有關(guān)的信息。①進程狀態(tài)②進程優(yōu)先級③進程調(diào)度所需的其它信息④事件2.進程控制塊中的信息4)進程控制信息①程序和數(shù)據(jù)的地址；②進程同步和通信機制；③資源清單；④鏈接指針。

3.進程控制塊的組織方式為了方便進程的調(diào)度和管理，需要將各進程的進程控制塊用適當?shù)姆椒ńM織起來，常用的組織方式有兩種：鏈接方式索引方式執(zhí)行指針就緒隊列指針阻塞隊列指針空閑隊列指針PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB94308

7900……PCB鏈接隊列示意圖(a)阻塞隊列分開PCB5執(zhí)行隊列

就緒隊列………

阻塞隊列1

阻塞隊列2………隊列表頭PCB8PCB1PCB4PCB3PCB2PCB7…(b)阻塞隊列不分開

就緒隊列

阻塞隊列…………PCB1PCB7PCB2PCB3………PCB8PCB4…執(zhí)行指針就緒索引表等待索引表PCB3PCB4PCB5PCB7PCB6PCB2PCB1按索引方式組織PCB就緒索引表等待索引表2.2進程控制進程的創(chuàng)建、撤銷以及完成進程各狀態(tài)之間的相互轉(zhuǎn)換。這些操作都要對應(yīng)地執(zhí)行一個特殊的程序段（原語），同時系統(tǒng)也通過系統(tǒng)調(diào)用給用戶提供進程控制的功能。進程控制原語：進程創(chuàng)建、進程終止、進程阻塞、進程喚醒、進程掛起、進程激活。原語(Primitive)原語：是機器指令的延伸，由若干條指令構(gòu)成的，系統(tǒng)狀態(tài)下執(zhí)行的某些具有特定功能的程序段。原語操作：一個操作中的動作要么全做，要么全不做。2.2.1進程的創(chuàng)建1進程圖進程圖是用來描述進程家族關(guān)系的有向樹。結(jié)點代表進程。一棵樹表示一個家族，根結(jié)點為該家族的祖先(Ancestor)。ABCDMEIJHGFLK進程樹1.進程圖關(guān)系子進程可以繼承父進程的所有資源子進程撤銷時，向父進程歸還資源父進程撤銷時，所有子進程也被撤銷進程圖和前趨圖之間的差異前趨圖描述的是任務(wù)(或進程)之間的前趨關(guān)系；只有在前趨進程完成后，其后繼進程才能運行；進程圖描述的是進程家族關(guān)系，創(chuàng)建者和被創(chuàng)建者可以并發(fā)執(zhí)行，也可以父進程等待其所有的子進程結(jié)束后再執(zhí)行，這完全取決于創(chuàng)建原語和創(chuàng)建者的需要。2引起創(chuàng)建進程的事件1.用戶登錄：為終端用戶建立一進程2.作業(yè)調(diào)度：（不是進程調(diào)度）為被調(diào)度的作業(yè)建立進程3.提供服務(wù)：如要打印時建立打印進程4.應(yīng)用請求：由應(yīng)用程序建立多個進程3進程的創(chuàng)建（creat）操作系統(tǒng)發(fā)現(xiàn)要求創(chuàng)建新進程的事件后，調(diào)用進程創(chuàng)建原語Creat()創(chuàng)建新進程。。創(chuàng)建原語Creat()功能：創(chuàng)建一個具有指定標識符進程入口信息：進程標識符、優(yōu)先級、進程開始地址、初始CPU狀態(tài)、資源清單等。3進程的創(chuàng)建（creat）創(chuàng)建過程：

1.申請空白PCB（一個系統(tǒng)的PCB是有限的）2.為新進程分配資源3.初始化PCB4.將新進程插入就緒隊列。入口查PCB鏈表有同名?將PCB入就緒隊列將PCB入總鏈將入口信息填入PCB相應(yīng)項向系統(tǒng)申請一個空的PCB結(jié)構(gòu)返回出錯有無有空PCB?出錯無有2.2.2進程的終止1．引起進程終止的事件正常結(jié)束

表示進程已經(jīng)運行完成的指示。如Halt、logoff2)異常結(jié)束 越界錯誤、保護錯、非法指令、特權(quán)指令錯、運行超時等3)外界干預(yù)操作員或操作系統(tǒng)干預(yù)父進程請求父進程中止2進程終止過程進程的終止過程（1）檢查進程狀態(tài)；（2）執(zhí)行態(tài)――>終止，且置調(diào)度標志為真。（3）有無子孫需終止。（4）歸還資源給其父進程或系統(tǒng)。（5）從PCB隊列中移出PCB.

入口返回查進程鏈表或進程家族有此PCB嗎？該PCB有子進程嗎？釋放該進程所占有的資源釋放該PCB結(jié)構(gòu)本身出錯處理有無有無2.2.3進程的阻塞1.引起進程阻塞和喚醒的事件請求系統(tǒng)服務(wù)：而得不到滿足時，如問系統(tǒng)請求打印。啟動某種操作：如該操作和請求該操作的進程需同步運行（即非異步操作）。新數(shù)據(jù)尚未到達：如進程A寫，進程B讀，則A未寫，完B不能讀。無新工作可做。2．進程阻塞過程調(diào)block原語停止執(zhí)行，修改PCB入阻塞隊列（一個或多個）轉(zhuǎn)調(diào)度程序。是進程自身的一種主動行為入口將現(xiàn)行進程的CPU信息送該進程的PCB現(xiàn)場保護區(qū)置該進程狀態(tài)為“等待”把該進程插入相應(yīng)的等待隊列轉(zhuǎn)進程調(diào)度阻塞原語執(zhí)行過程3．進程喚醒過程進程所等待的事件發(fā)生時，則調(diào)用喚醒原語將等待該事件的進程喚醒。喚醒進程有兩種方法：（1）由系統(tǒng)進程喚醒。（2）由事件發(fā)生進程喚醒。一個處于阻塞狀態(tài)的進程不可能自己喚醒自己。3．進程喚醒過程

喚醒原語執(zhí)行的過程首先把被阻塞進程從等待該事件的阻塞隊列中移出，將其PCB中的阻塞狀態(tài)改為就緒狀態(tài)，然后把該進程插入到就緒隊列中。阻塞原語和喚醒原語是一對作用剛好相反的原語。入口將被喚醒進程從相應(yīng)的等待隊列中移出將被喚醒進程置為就緒狀態(tài)將被喚醒進程送入就緒隊列轉(zhuǎn)進程調(diào)度喚醒原語執(zhí)行過程2.2.4進程的掛起與激活1.進程的掛起當出現(xiàn)了引起進程掛起的事件時，用戶請求將自己掛起，或者父進程請求掛起自己的子進程。掛起的實現(xiàn)方式有多種：（1）把發(fā)出掛起原語的進程自身掛起。（2）掛起具有指定標識名的進程。（3）把某進程及其全部或部分（例如具有指定優(yōu)先數(shù)的）子孫進程掛起。1.進程的掛起掛起原語的主要操作過程首先檢查該進程的狀態(tài)（1）若狀態(tài)為就緒，則改為掛起就緒；（2）若狀態(tài)為阻塞，則改為掛起阻塞；（3）若狀態(tài)為執(zhí)行，則中斷處理機，把狀態(tài)改為掛起就緒。被掛起進程PCB的非常駐部分要交換到磁盤交換區(qū)2．進程的激活過程進程的激活過程:當發(fā)生激活事件后，系統(tǒng)利用激活原語Active()將指定進程激活。激活原語先將進程從外存調(diào)入內(nèi)存，然后檢查進程的狀態(tài)。靜止就緒活動就緒靜止阻塞活動阻塞2.3進程的同步多道程序環(huán)境下由于資源共享或進程合作，進程在活動中會相互制約所有進程都是相互獨立的進程以異步方式并發(fā)執(zhí)行直接制約：相互制約關(guān)系源于進程合作，表現(xiàn)為：進程---進程（同步）間接制約：相互制約關(guān)系源于資源共享,表現(xiàn)為：進程---資源---進程（互斥）1．兩種形式的制約關(guān)系用進程互斥與同步機制來協(xié)調(diào)兩種制約關(guān)系。2.3進程的同步進程同步的主要任務(wù)：并發(fā)進程在執(zhí)行次序上的進行協(xié)調(diào)，以達到有效的資源共享和相互合作，使程序執(zhí)行有可再現(xiàn)性。同步是進程間共同完成一項任務(wù)時直接發(fā)生相互作用的關(guān)系同步舉例同步進程間具有合作關(guān)系在執(zhí)行時間上必須按一定的順序協(xié)調(diào)進行互斥互斥是并發(fā)執(zhí)行的多個進程由于競爭同一資源而產(chǎn)生的相互排斥的關(guān)系互斥進程彼此在邏輯上是完全無關(guān)的它們的運行不具有時間次序的特征打印機編號分配標志用戶名用戶定義的設(shè)備名01LiLPT11021MengLPT2打印機分配表

假定進程P1負責為用戶作業(yè)分配打印機，進程P2負責釋放打印機，上圖為某時刻打印機的使用情況。互斥舉例P1：分配過程檢查標志位，找0；將01；將用戶名和打印機名填入表格。P2：釋放過程找用戶名與打印機名與要釋放的名字相同切標志位為1的表項；將10；將用戶名和打印機名清空。具體操作互斥舉例P1、P2順序執(zhí)行時，一切正常！當P1、P2交替執(zhí)行時（B先做前2步，A做完3步，B再做第3步），可能會出現(xiàn)以下現(xiàn)象：打印機編號分配標志用戶名用戶定義的設(shè)備名01

1021MengLPT22.臨界資源系統(tǒng)中某些資源一次只允許一個進程使用，稱這樣的資源為臨界資源或互斥資源或共享變量硬臨界資源：打印機、輸入機、磁帶機等軟臨界資源：多個進程共享的變量、數(shù)據(jù)、表格、隊列等例1：有兩個進程A、B，它們共享一個變量x，且兩個進程按以下方式對變量x進行訪問和修改：A：R1=x；

R1=R1+1；

x=R1B：R2=x；

R2=R2+1；

x=R22.臨界資源其中：R1和R2為處理機中的兩個寄存器。這里，兩個進程各自對x作了加1操作，相應(yīng)地，x增加了2。若按A、B交替執(zhí)行：A：R1=x；B：R2=x；A：R1=R1+1；

x=R1B：R2=R2+1；

x=R2雖然兩個進程也各自對x作了加1操作，但x卻只增加了1。為了防止這種錯誤的發(fā)生，變量x應(yīng)按臨界資源處理，即讓兩個進程順序使用變量x。2.臨界資源例2：生產(chǎn)者—消費者問題：

有一群生產(chǎn)者進程生產(chǎn)產(chǎn)品供給消費者進程消費，為使兩者并發(fā)執(zhí)行，在兩者之間設(shè)置具有n個緩沖區(qū)的緩沖池，生產(chǎn)者進程所生產(chǎn)的產(chǎn)品放入一個緩沖區(qū)中，消費者進程可從一個緩沖區(qū)中取走產(chǎn)品去消費。

生產(chǎn)者進程和消費者進程都以異步方式運行，但它們之間必須保持同步。2.臨界資源例：生產(chǎn)者—消費者問題環(huán)型緩沖池2.臨界資源2.臨界資源生產(chǎn)者進程和消費者進程共享的變量：Varn,integer;typeitem=……;varbuffer:array[0,1,…,n-1]ofitem;in,out:0,1,…,n-1;counter:0,1,…,n;初始值為0，放入產(chǎn)品使其加1，取出產(chǎn)品使其減1注意：緩沖池組織為循環(huán)緩沖，輸入指針加1表示為in:=(in+1)modn，輸出指針加1表示為out:=(out+1)modn，當(in+1)modn=out時表示緩沖池滿，in=out表示緩沖池空。用數(shù)組表示具有n個緩沖區(qū)的緩沖池輸入指針in指示下一個可投放產(chǎn)品的緩沖區(qū)，輸出指針out指示下一個可從中獲取產(chǎn)品的緩沖區(qū)，初值均為0。Producer:repeat…produceaniteminnextp;…whilecounter=ndono-op;buffer[in]:=nextp;in:=in+1modn;counter:=counter+1;untilfalse;Consumer:repeatwhilecounter=0dono-op;nextc:=buffer[out];out:=out+1modn;counter:=counter-1;consumertheiteminnextc;untilfalse;空操作指令重復(fù)的測試條件2.臨界資源2.臨界資源并發(fā)執(zhí)行出錯—counter生產(chǎn)者對它加1，消費者對它減1機器語言實現(xiàn)：register1:=counter;register1:=register1+1;counter:=register1;register2:=counter;register2:=register2-1;counter:=register2;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)counter應(yīng)當為5解決方法：把counter作為臨界資源，對其互斥訪問臨界區(qū)(互斥區(qū))：每個進程中訪問臨界資源的那段程序段稱為臨界區(qū)(criticalsection)。3．臨界區(qū)對欲訪問的臨界資源進行檢查，………………進入?yún)^(qū)若此刻未被訪問，設(shè)正在訪問的標志訪問臨界資源………………臨界區(qū)將正在訪問的標志恢復(fù)為未被訪問的標志……退出區(qū)其余部分………………剩余區(qū)repeat

entrysection

criticalsection

exitsection

remaindersectionuntilfalse3．臨界區(qū)

4．同步機制應(yīng)遵循的規(guī)則空閑讓進忙則等待有限等待讓權(quán)等待2.3.2信號量機制人們從交叉路口的交通管理中使用的信號燈上得到啟發(fā)，通過信號燈的狀態(tài)(或顏色)實現(xiàn)交通管理。操作系統(tǒng)中引進信號燈(通常人們叫信號量)的概念既可用來解決同步問題，也可解決互斥問題。1965年荷蘭Dijkstra提出的進程同步工具2.3.2信號量機制信號量：除初始化外,僅能由同步原語對其進行操作的整型變量。同步原語：

P/wait操作；

V/signal操作；信號量機制目前已經(jīng)發(fā)展成多種類型，主要有：整型、記錄型、AND型和信號量集機制。1．整型信號量整型信號量定義為一個用于表示資源數(shù)目的整型量S，它與一般整型量不同，除初始化外，僅能通過兩個標準的原子操作wait(S)和signal(S)來訪問。Wait(S)和signal(S)操作可描述為：

wait(S)：

whileS<=0dono-op；

S:=S-1；

signal(S)：

S:=S+1；信號量的物理意義

wait原語和signal原語的執(zhí)行都必須是一個不可被中斷的整體。(1)物理意義：S>0時，S為可用資源量；S=0時，可用資源量正好用完；S<0時，|S|為等待資源的隊列長度，即還欠資源數(shù)(在信號量上等待的進程數(shù))例：S=4S=0S=–2P1

P2

wait(S)：表示請求分配一個資源

S>0立即可得S0要排隊(2)wait(S)Lock(S)S為二元信號量signal(S)unlock(S)signal(S)：表示釋放資源信號量的初值應(yīng)該大于等于0對應(yīng)2．記錄型信號量記錄型信號量：一般是由兩個成員組成的數(shù)據(jù)結(jié)構(gòu)，除了需要一個用于代表資源數(shù)目的整型變量value外，還應(yīng)增加一個進程鏈表指針L。整型信號量未遵循“讓權(quán)等待”原則，導致“忙等”。記錄型信號量機制則是一種不存在“忙等”現(xiàn)象的進程同步機制。信號量是一種數(shù)據(jù)結(jié)構(gòu)一般由兩個成員組成：數(shù)值指針2．記錄型信號量4∧PCB2∧PCB1指針-2指針有四個資源可用！有兩個進程等待使用資源！2．記錄型信號量typesemaphore=record

value:integer；

L:listofprocess；

end記錄型信號量數(shù)據(jù)結(jié)構(gòu)2．記錄型信號量相應(yīng)地，wait(S)和signal(S)操作可描述為：（1）s值減1；（2）若相減結(jié)果大于等于0，則進程繼續(xù)執(zhí)行；（3）若結(jié)果小于0，則該進程阻塞。procedurewait(S)

varS：semaphore；

begin

S.value:=S.value-1；

ifS.value<0thenblock(S.L)；

end2．記錄型信號量（1）s值加1；（2）若相加結(jié)果大于0，進程繼續(xù)執(zhí)行；（3）否則，喚醒一個（或多個）等待該信號量的進程，然后本進程繼續(xù)執(zhí)行。proceduresignal(S)

varS:semaphore；

begin

S.value:=S.value+1；

ifS.value<=0thenwakeup(S.L)；

end2．記錄型信號量3.AND型信號量前面介紹的進程互斥問題，屬于多個進程共享一個臨界資源。假如：兩個進程A和B，共享數(shù)據(jù)D和E，為其分別設(shè)置互斥信號量Dmutex和Emutex，初值為1。ProcessA：

wait(Dmutex);wait(Emutex);ProcessB：

wait(Emutex);wait(Dmutex);ProcessA：wait(Dmutex);于是Dmutex=0ProcessB：wait(Emutex);于是Emutex=0ProcessA：wait(Emutex);于是Emutex=-1A阻塞ProcessB：wait(Dmutex);于是Dmutex=-1B阻塞設(shè)執(zhí)行過程為共享的資源越多，死鎖的可能越大！3.AND型信號量AND同步機制的基本思想：將進程在整個運行過程中需要的所有資源，一次性全部分配給進程，待進程使用完后再一起釋放。只要尚有一個資源未能分配給進程，其他所有可能為之分配的資源，也不分配給它。即對臨界資源的分配采取原子操作。Swait(S1,S2,…,Sn)ifS1>=1and…andSn>=1thenfori:=1tondoSi:=Si-1;endforelsePlacetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi<1,andsettheprogramcountofthisprocesstothebeginningofSwaitoperationendifSsignal(S1,S2,…,Sn)fori:=1tondoSi:=Si+1;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueueendfor

4．信號量集在記錄型信號量機制中每次只能獲得或釋放一個單位的臨界資源。而當需要N個某類臨界資源時，便要進行N次操作，低效。一般信號量集在AND型信號量集的基礎(chǔ)上進行擴充，在一次原語操作中完成所有的資源申請。信號量Si測試值為ti要求Si>=ti；即當資源數(shù)量低于ti時，便不予分配占用值為di表示資源的申請量，即Si=Si-di對應(yīng)的P、V原語格式為：

4．信號量集Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);Swait(S1,t1,d1,…,Sn,tn,dn)ifS1>=t1and…andSn>=tnthenfori:=1tondoSi:=Si-di;endforelsePlacetheexecutingprocessinthewaitingqueueofthefirstSiwithSi<tiandsetitsprogramcountertothebeginningoftheSwaitOperationendifSsignal(S1,d1,…,Sn,dn)fori:=1tondoSi:=Si+di;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueueendfor4．信號量集一般信號量集的幾種特殊情況Swait(S,d,d):表示每次申請d個資源，當少于d個時，便不分配Swait(S,1,1):表示互斥信號量Swait(S,1,0):可作為一個可控開關(guān)（當S1時，允許多個進程進入臨界區(qū)；當S=0時，禁止任何進程進入臨界區(qū)）2.3.3信號量的應(yīng)用

1．利用信號量實現(xiàn)進程互斥為該每個臨界資源設(shè)置一互斥信號量mutex，并設(shè)其初始值為1將各進程訪問該資源的臨界區(qū)CS置于wait(mutex)和signal(mutex)操作之間即可。對同一信號量操作的wait與signal操作在進程中必須成對出現(xiàn)。Wait、Signal原語不能次序錯誤、重復(fù)或遺漏mutex的取值范圍為1,0,-1,-2，……,-nSignal(mutex);criticalsectionremaindersectionWait(mutex);1．利用信號量實現(xiàn)進程互斥Wait、Signal原語不能次序錯誤、重復(fù)或遺漏Varmutex:semaphore:=1；

begin

parbegin

process1:begin

repeat

wait(mutex)；

criticalsection

signal(mutex)；

remainderseetion

untilfalse；

end1．利用信號量實現(xiàn)進程互斥process2:begin

repeat

wait(mutex)；

criticalsection

signal(mutex)；

remaindersection

untilfalse；

end

parendend1．利用信號量實現(xiàn)進程互斥例：打印機分配表的使用問題（P87）：設(shè)互斥信號量mutex（初值為1）Pa為分配進程Pb為釋放進程1．利用信號量實現(xiàn)進程互斥Pa：...Wait（mutex）分配打印機（讀寫分配表）Signal（mutex）...Pb：...Wait（mutex）釋放打印機（讀寫分配表）Signal（mutex）...1．利用信號量實現(xiàn)進程互斥設(shè)有兩個并發(fā)執(zhí)行的進程P1和P2，P1中有語句S1，P2中有語句S2，希望在S1執(zhí)行后再執(zhí)行S2。使進程P1和P2共享一個公用信號量S，并賦予其初值為0。進程P1：S1；signal(S)；進程P2：wait(S)；S2；

2．利用信號量實現(xiàn)前趨關(guān)系S1S2S3S4S5S6

2．利用信號量實現(xiàn)前趨關(guān)系abcdefgVara,b,c,d,e,f,g：semaphore:=0,0,0,0,0,0,0；

begin

parbegin

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；

parend

end2．利用信號量實現(xiàn)前趨關(guān)系3.利用信號量實現(xiàn)進程同步公共汽車司機與售票員之間的活動。司機負責開車，售票員負責開、關(guān)車門及售票，其活動如下圖所示。雖然各負其責，但必須互相配合、協(xié)調(diào)活動，他們之間存在如下同步關(guān)系：3.利用信號量實現(xiàn)進程同步設(shè)置信號量close（同步信號量）表示車門是否關(guān)好，初值為0，表示門未關(guān)好，不允許司機啟動汽車；設(shè)置信號量stop（同步信號量）表示汽車是否停穩(wěn)，初值為0，表示未停穩(wěn)，售票員不能開車門。3.利用信號量實現(xiàn)進程同步Varstop,close:Semaphore:=0,0BeginparbeginDriver():beginrepeatwait(close);//先測試車門是否關(guān)好啟動汽車;

正常開車;

到站停車;signal(stop);//發(fā)送可開門信息

untilfalseend3.利用信號量實現(xiàn)進程同步busman():beginRepeat

關(guān)車門；

signal(close);//發(fā)送門已關(guān)的同步信息售車票；

wait(stop);//開門前先測試是否停車開車門；乘客上下車；

untilfalseendparend3.利用信號量實現(xiàn)進程同步2.3.4管程機制信號量機制存在下列3點不足：3、wait和signal操作的錯誤使用（次序錯誤、重復(fù)、遺漏等），編譯程序和操作系統(tǒng)都無法發(fā)現(xiàn)、糾正，可導致死鎖。1、criticalsection、entrysection和exitsection都由用戶編寫；2、信號量操作原語分散在各程序代碼中，由進程來執(zhí)行，系統(tǒng)無法有效控制、管理；2.3.4管程機制70年代初,ByE.W.Dijkstra,C.A.R.Hoare,P.B.Hansen.背景:Structuredprogramming管程的定義：管程是關(guān)于共享資源的數(shù)據(jù)結(jié)構(gòu)及針對該資源的可以并發(fā)執(zhí)行的一組操作。Java:synchronizedmethod1.管程定義將所有進程對某一臨界資源的同步操作都集中起來，構(gòu)成所謂的“秘書”進程，凡要訪問該臨界資源的進程，都需先報告“秘書”，由其實現(xiàn)諸進程的同步。能同步進程和改變管程中的數(shù)據(jù)，是進程間同步的機制，它保證進程互斥地使用臨界資源。1.管程定義管程的四個組成部分：管程的名稱：數(shù)據(jù)結(jié)構(gòu)說明：一組局部于管程的共享變量過程：對共享變量進行操作的一組原語過程（程序代碼）初始化代碼：對共享變量進行初始化的代碼管程（相當于圍墻）把共享變量和對它進行操作的若干過程圍起來。圖2-13管程的示意圖1.管程定義

typemonitor_name=MONITOR；<共享變量說明>；define<(能被其他模塊引用的)過程名列表>；use<(要調(diào)用的本模塊外定義的)過程名列表>；procedure<過程名>(<形式參數(shù)表>)；begin

end;……管程的語法描述如下：1.管程定義function<函數(shù)名>(<形式參數(shù)表>)：值類型；begin

end；

begin<管程的局部數(shù)據(jù)初始化語句序列>；end……1.管程定義

模塊化:一個管程是一個基本程序單位，可以單獨編譯

抽象數(shù)據(jù)類型:管程是一種特殊的數(shù)據(jù)類型，其中不僅有數(shù)據(jù)，而且有對數(shù)據(jù)進行操作的代碼

信息掩蔽:管程是半透明的，管程中的內(nèi)部過程（函數(shù)）實現(xiàn)了某些功能，至于這些功能是怎樣實現(xiàn)的，在其外部則是不可見的。管程的三個主要的特性管程和進程的比較主要體現(xiàn)在以下幾個方面：(1)數(shù)據(jù)結(jié)構(gòu)；(2)操作；(3)目的；(4)工作方式；(5)并發(fā)；(6)動態(tài)性。2．條件變量管程通常是用來管理資源的，因而在管程中應(yīng)當設(shè)有進程等待隊列以及相應(yīng)的等待及喚醒操作；為此在管程內(nèi)部可以說明和使用一種特殊類型的變量----條件變量。每個條件變量表示一種等待原因，并不取具體數(shù)值－－相當于每個原因?qū)?yīng)一個隊列。urgentqueue2．條件變量Varx，y：condition。①x.wait：如緊急隊列非空，喚醒第一個等待者，否則釋放管程互斥權(quán);執(zhí)行此操作的進程（線程）進入x鏈尾。x.signal：如c鏈空，相當空操作。否則喚醒第一個，執(zhí)行此操作的進程（線程）進入緊急隊列。

當一個進入管程的進程執(zhí)行喚醒操作時（如Ｐ喚醒Ｑ），管程中便存在兩個同時處于活動狀態(tài)的進程。處理方法有三種：2．條件變量

Ｐ等待Ｑ繼續(xù)，直到Ｑ退出或等待Ｑ等待Ｐ繼續(xù)，直到Ｐ等待或退出規(guī)定喚醒為管程中最后一個可執(zhí)行的操作2.4經(jīng)典進程的同步問題三個經(jīng)典的進程同步問題：1、生產(chǎn)者--消費者問題；

(TheProducer-ConsumerProblem)2、哲學家進餐問題；

(TheDiningPhilosophersProblem)3、讀者--寫者問題；

(TheRead-WriteProblem)2.4.1生產(chǎn)者—消費者問題問題：有若干生產(chǎn)者、消費者，共享使用n個緩沖區(qū)組成的緩沖池：

生產(chǎn)者：每次產(chǎn)生一個數(shù)據(jù)，放入一個空緩沖區(qū)。若無空緩沖區(qū)，則阻塞；

消費者：每次從有數(shù)據(jù)的緩沖區(qū)取一個數(shù)據(jù)消費。若所有緩沖區(qū)皆為空，則阻塞；01……k-1箱子，容量kB:Array[0..k-1]Ofitem生產(chǎn)者消費者生產(chǎn)物品放入B中B中取物品消費之2.4.1生產(chǎn)者—消費者問題InOut分析：同步：若所有緩沖區(qū)皆空，消費者等待生產(chǎn)者生產(chǎn)；若所有緩沖區(qū)皆滿，生產(chǎn)者等待消費者消費。1.利用記錄型信號量解決生產(chǎn)者—消費者問題定義變量：itemTYPEbuffer[n];表示各緩沖區(qū)；

integerin=0,out=0;生產(chǎn)、消費緩沖區(qū)指針；設(shè)置同步信號量：

empty表示現(xiàn)有空緩沖區(qū)數(shù)，初值=nfull表示現(xiàn)有滿緩沖區(qū)數(shù)，初值=0

互斥：生產(chǎn)者、消費者對緩沖池的操作必須互斥。設(shè)置互斥信號量mutex，初值=1

1.利用記錄型信號量解決生產(chǎn)者—消費者問題Varmutex，empty，full:semaphore:=1,n,0；

buffer:array[0，…，n-1]ofitem；

in，out:integer:=0，0；

begin

parbegin

proceducer:begin

repeat

produceranitemnextp；

wait(empty)；

wait(mutex)；

buffer(in):=nextp；

in:=(in+1)modn；

signal(mutex)；

signal(full)；

untilfalse；

end

consumer:begin

repeat

wait(full)；

wait(mutex)；

nextc:=buffer(out)；

out:=(out+1)modn；

signal(mutex)；

signal(empty)；

consumertheiteminnextc；

untilfalse；

end

parend

end1.利用記錄型信號量解決生產(chǎn)者—消費者問題1.如果對調(diào)兩個wait原語，當按如下順序執(zhí)行時：1.利用記錄型信號量解決生產(chǎn)者—消費者問題消費者:wait(mutex);/*執(zhí)行語句后mutex為0*/消費者:wait(full);/*full為-1，消費者等待*/生產(chǎn)者:wait(empty);/*empty為k-1*/生產(chǎn)者:wait(mutex);/*mutex為-1，生產(chǎn)者等待*/2.如果對調(diào)兩個signal原語呢？結(jié)果：導致死鎖。所以wait原語的次序不能顛倒!3.在每個程序中的多個wait操作順序不能顛倒，應(yīng)先執(zhí)行對資源信號量wait操作，然后再執(zhí)行對互斥信號量wait操作。注意1.利用記錄型信號量解決生產(chǎn)者—消費者問題1.在每個程序中用于實現(xiàn)互斥的wait和signal必須成對地出現(xiàn)；2.對資源信號量的wait和signal操作，同樣需要成對地出現(xiàn)，但它們分別處于不同的程序中。2．利用AND信號量解決生產(chǎn)者—消費者問題在上面的解決方法中，進程中的兩個wait原語的位置不能顛倒，否則，可能導致死鎖，使用AND信號量機制來實現(xiàn)，將對信號量empty與mutex的兩個wait操作用一個swait(empty,mutex)操作來實現(xiàn)，將對信號量full與mutex的兩個wait操作用一個swait(full,mutex)操作來實現(xiàn)，就可以避免死鎖的產(chǎn)生。實現(xiàn)如下：2．利用AND信號量解決生產(chǎn)者—消費者問題Varmutex，empty，full:semaphore:=1，n，0；

buffer:array[0，…，n-1]ofitem；

inout:integer:=0，0；

begin

parbegin

producer:begin

repeat

produceaniteminnextp；

Swait(empty，mutex)；

buffer(in):=nextp；

in:=(in+1)modn；

Ssignal(mutex，full)；

untilfalse；

end…… consumer:begin

repeat

Swait(full，mutex)；

Nextc:=buffer(out)；

Out:=(out+1)modn；

Ssignal(mutex，empty)；

consumertheiteminnextc；

untilfalse；

end

parend

end2．利用AND信號量解決生產(chǎn)者—消費者問題3．利用管程解決生產(chǎn)者—消費者問題建立一個管程ProclucerConsumer，包括兩個過程：(1)put(item)

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

。消費者利用該過程從緩沖池中取出一個產(chǎn)品。typeproducer-consumer=monitor

Varin,out,count:integer；

buffer:array[0,…,n-1]ofitem；

notfull，notempty:condition；

procedureentryput(item)

begin

ifcount>=nthennotfull.wait；

buffer(in):=nextp；

in:=(in+1)modn；

count:=count+1；

ifnotempty.queuethennotempty.signal；

end3．利用管程解決生產(chǎn)者—消費者問題 procedureentryget(item)

begin

ifcount<=0thennotempty.wait；

nextc:=buffer(out)；

out:=(out+1)modn；

count:=count-1；

ifnotfull.quenethennotfull.signal；

end

beginin:=out:=0；

count:=0end3．利用管程解決生產(chǎn)者—消費者問題

producer:begin

repeat

produceaniteminnextp；

PC.put(item)；

untilfalse；

end

consumer:begin

repeat

PC.get(item)；

consumetheiteminnextc；

untilfalse；

end生產(chǎn)者和消費者可描述為：3．利用管程解決生產(chǎn)者—消費者問題2.4.2哲學家進餐問題問題：五個哲學家同座一張圓桌，每人一個碗，左右各一只筷子；其習慣為：思考-吃飯-思考......；只有拿到左右兩只筷子才開始吃飯，吃完后繼續(xù)思考......。哲學家進餐問題

哲學家思考問題時，并不影響他人；只有當他就完餐后才放下筷子重新開始思考問題。只有當哲學家饑餓的時候，他才試圖拿起左、右兩根筷子；如果筷子已在他人手上，則需等待；只有當饑餓的哲學家同時拿到了兩根筷子，他才可以開始就餐；2.4.2哲學家進餐問題思考思考思考思考思考準備進餐進餐準備進餐進餐分析1．利用記錄型信號量解決哲學家進餐問題放在桌子上的筷子是臨界資源，在一段時間內(nèi)只允許一位哲學家使用。為了實現(xiàn)對筷子的互斥使用，可以用一個信號量表示一只筷子，由這五個信號量構(gòu)成信號量數(shù)組：Varchopstick:array[0，…，4]ofsemaphore所有信號量均被初始化為1，第i位哲學家的活動可描述為：

repeat

wait(chopstick[i])；

wait(chopstick[(i+1)mod5])；

eat；

signal(chopstick[i])；

signal(chopstick[(i+1)mod5])；

think；

untilfalse；………1．利用記錄型信號量解決哲學家進餐問題哲學家饑餓時，總是先拿左邊的筷子，再拿右邊的筷子分析：假設(shè)5個哲學家同時拿起他們各自左邊（右邊）筷子，就會使五個信號量chopstick均為0；那么，他們都只能拿到一支筷子而等待右邊的人放下筷子，誰也不能拿到一雙筷子來吃飯，這種等待狀態(tài)將一直保持下去，產(chǎn)生了死鎖。1．利用記錄型信號量解決哲學家進餐問題哲學家進餐問題分析死鎖思考思考思考思考思考準備進餐準備進餐準備進餐準備進餐準備進餐思考Wait（left_stick）Wait（right_stick)Signal（left_stick）eatSignal（right_stick)解決方法：1.至多只允許有四位哲學家同時去拿左邊的筷子，最終能保證至少有一位哲學家能夠進餐，并在用畢后釋放出他用過的兩只筷子，從而使更多的哲學家能夠進餐。---限制并發(fā)執(zhí)行的進程數(shù)2.僅當哲學家的左右兩只筷子均可用時，才允許他拿起筷子進餐。---采用信號量集3.規(guī)定奇數(shù)號哲學家先拿他左邊的筷子，然后再去拿右邊的筷子；偶數(shù)號哲學家則相反。---保證總會有一個哲學家能同時獲得兩只筷子而進餐2.4.2哲學家進餐問題2315423154方法3第一種方法來解決實現(xiàn)沒有死鎖的哲學家問題：至多只允許有四位哲學家同時去拿左邊的筷子，最終能保證至少有一位哲學家能夠進餐，并在用完時能放下他用過的兩支筷子，從而使其他的哲學家能夠進餐。在實現(xiàn)時只需增加一個限定就餐人數(shù)的信號量num（互斥信號量），其初值設(shè)為4。任何哲學家拿筷子前先檢測num，算法如下：2.4.2哲學家進餐問題Varnum:semaphore:=4;chopstick:array(0,…4)ofemaphore:=(1，1，1，1，1)；processirepeatthink;wait(num); wait(chopstick［i］);wait(chopstick［(i+1)%5］);…eat;…signal(num);signal(chopstick［i］);signal(chopstick［(i+1)%5］);…Untilefalse2．利用AND信號量機制解決哲學家進餐問題在哲學家進餐問題中，要求每個哲學家先獲得兩個臨界資源(筷子)后方能進餐，這在本質(zhì)上就是前面所介紹的AND同步問題，故用AND信號量機制可獲得最簡潔的解法。Varchopsiickarrayofsemaphore:=(1,1,1,1,1)；

processi

repeat

think；

Sswait(chopstick[(i+1)mod5]，chopstick[i])；

eat；

Ssignat(chopstick[(i+1)mod5]，chopstick[i])；

untilfalse；2．利用AND信號量機制解決哲學家進餐問題2.4.3讀者—寫者問題描述：在計算機系統(tǒng)中，讀數(shù)據(jù)(文件)及修改、寫數(shù)據(jù)(文件)是經(jīng)常的，并要求對數(shù)據(jù)(文件、記錄)進行共享。也就是說，多個進程同時讀／寫(共享數(shù)據(jù))。而對于讀／寫數(shù)據(jù)，會有幾種情況發(fā)生：1)同時讀，不會發(fā)生副作用。2)有一個寫，其它讀、寫，會產(chǎn)生副作用。3)讀時，出現(xiàn)寫，也會產(chǎn)生副作用。2.4.3讀者—寫者問題1．利用記錄型信號量解決讀者—寫者問題分析：2、由于允許有多個讀者，為了解目前的讀者數(shù)量，設(shè)置一讀者計數(shù)變量readcount,初值為0。多個讀者都對readcount進行操作，須設(shè)置對其操作的互斥信號量Rmutex，初值為1.1、為保證寫者進程與其它進程互斥訪問共享對象，設(shè)置互斥信號量Wmutex，初值為1：

讀者—寫者問題可描述如下:Varrmutex，wmutex:semaphore:=1,1；

Readcount:integer:=0；

begin

parbegin

Reader:begin

repeat

wait(rmutex)；

ifreadcount=0thenwait(wmutex)；

Readcount:=Readcount+1；

signal(rmutex)；

performreadoperation；……1．利用記錄型信號量解決讀者—寫者問題

wait(rmutex)；