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

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

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

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

“→”。2.1.2.前趨圖結(jié)點(diǎn)間的有向邊表示兩個(gè)結(jié)點(diǎn)之間存在的偏序(Partial_Order)或前趨關(guān)系(Precedence_Relation)“→”＝{(Pi,Pj)|在Pj開始前Pi必須完成}，如果(Pi,Pj)∈→，可寫成Pi→Pj，Pi是Pj的直接前趨，Pj是Pi的直接后繼。每個(gè)結(jié)點(diǎn)還具有一個(gè)重量。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)境：

在一定時(shí)間內(nèi)物理機(jī)器上有兩個(gè)或兩個(gè)以上的程序同處于開始運(yùn)行但尚未結(jié)束的狀態(tài)，并且次序不是事先確定的，就稱這幾個(gè)程序是并發(fā)執(zhí)行的。1.程序的并發(fā)執(zhí)行在對(duì)一批程序進(jìn)行處理時(shí)，可以并發(fā)執(zhí)行。例如，輸入、計(jì)算、打印三個(gè)程序?qū)σ慌鳂I(yè)進(jìn)行處理時(shí)前趨關(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í)行對(duì)于具有下述四條語句的程序段：

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

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

get程序負(fù)責(zé)從輸入序列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)系與時(shí)間有關(guān)的錯(cuò)誤假定f系列中有記錄

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

f=()g=(R1,R2,...,Rn)算法中的：copy≡t=sput≡put(t,g)get≡get(s,f)與時(shí)間有關(guān)的錯(cuò)誤若程序錯(cuò)寫成：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三個(gè)程序段并發(fā)執(zhí)行，就有六種組合：1、copy;put;get導(dǎo)致結(jié)果：g=(R1,R2)2、copy;get;put導(dǎo)致結(jié)果：g=(R1,R2)3、put;copy;get導(dǎo)致結(jié)果：g=(R1,R1)4、put;get;copy導(dǎo)致結(jié)果：g=(R1,R1)5、get;copy;put導(dǎo)致結(jié)果：g=(R1,R3)6、get;put;copy導(dǎo)致結(jié)果：g=(R1,R1)這就是與時(shí)間有關(guān)的錯(cuò)誤。與時(shí)間有關(guān)的錯(cuò)誤2.程序的并發(fā)執(zhí)行的特征1)間斷性:程序在并發(fā)執(zhí)行時(shí)，由于它們共享資源或?yàn)橥瓿赡骋豁?xiàng)任務(wù)而合作，致使在并發(fā)程序之間存在相互制約的關(guān)系。

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

3)不可再現(xiàn)性:程序在并發(fā)執(zhí)行時(shí)，由于失去了封閉性，也導(dǎo)致失去了可再現(xiàn)性。2.程序的并發(fā)執(zhí)行的特征并發(fā)程序A和B，共享變量n，程序A做n=n+1操作；程序B執(zhí)行print（n）操作。兩種情況：（假設(shè)當(dāng)前變量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進(jìn)程的特征與狀態(tài)在多道程序環(huán)境下，程序具有了并行、制約和動(dòng)態(tài)的特征，程序概念已刻劃不清系統(tǒng)的這種并行情況，反映不了它們的活動(dòng)規(guī)律和狀態(tài)變化。為了動(dòng)態(tài)地看待操作系統(tǒng)，則以進(jìn)程作為資源分配和獨(dú)立運(yùn)行的基本單位，從進(jìn)程觀點(diǎn)來研究操作系統(tǒng)，操作系統(tǒng)所具有的所有特征也都是基于進(jìn)程而形成的。1.進(jìn)程的特征和定義進(jìn)程：是指在系統(tǒng)中能獨(dú)立運(yùn)行并作為資源分配的基本單位，是一個(gè)活動(dòng)實(shí)體。也可以說，進(jìn)程是程序在數(shù)據(jù)集合上的一次運(yùn)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位。進(jìn)程是一個(gè)動(dòng)態(tài)的概念，是一個(gè)運(yùn)行過程。它不同于程序，但又依賴于程序。對(duì)不同的數(shù)據(jù)集合，依照一定的程序運(yùn)行處理的每一個(gè)過程是每個(gè)不同的進(jìn)程。在系統(tǒng)中同時(shí)有多個(gè)進(jìn)程存在，但歸納起來有兩大類：1、系統(tǒng)進(jìn)程系統(tǒng)進(jìn)程起著資源管理和控制的作用。

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

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

運(yùn)行狀態(tài)就緒狀態(tài)

阻塞狀態(tài)

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

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

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

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

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

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

(1)活動(dòng)就緒靜止就緒

(2)活動(dòng)阻塞靜止阻塞

(3)靜止就緒活動(dòng)就緒

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

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

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

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

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

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

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

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

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

就緒隊(duì)列………

阻塞隊(duì)列1

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

就緒隊(duì)列

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

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

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

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

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

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

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

R1=R1+1；

x=R1B：R2=x；

R2=R2+1；

x=R22.臨界資源其中：R1和R2為處理機(jī)中的兩個(gè)寄存器。這里，兩個(gè)進(jìn)程各自對(duì)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雖然兩個(gè)進(jìn)程也各自對(duì)x作了加1操作，但x卻只增加了1。為了防止這種錯(cuò)誤的發(fā)生，變量x應(yīng)按臨界資源處理，即讓兩個(gè)進(jìn)程順序使用變量x。2.臨界資源例2：生產(chǎn)者—消費(fèi)者問題：

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

生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程都以異步方式運(yùn)行，但它們之間必須保持同步。2.臨界資源例：生產(chǎn)者—消費(fèi)者問題環(huán)型緩沖池2.臨界資源2.臨界資源生產(chǎn)者進(jì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;初始值為0，放入產(chǎn)品使其加1，取出產(chǎn)品使其減1注意：緩沖池組織為循環(huán)緩沖，輸入指針加1表示為in:=(in+1)modn，輸出指針加1表示為out:=(out+1)modn，當(dāng)(in+1)modn=out時(shí)表示緩沖池滿，in=out表示緩沖池空。用數(shù)組表示具有n個(gè)緩沖區(qū)的緩沖池輸入指針in指示下一個(gè)可投放產(chǎn)品的緩沖區(qū)，輸出指針out指示下一個(gè)可從中獲取產(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í)行出錯(cuò)—counter生產(chǎn)者對(duì)它加1，消費(fèi)者對(duì)它減1機(jī)器語言實(shí)現(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)當(dāng)為5解決方法：把counter作為臨界資源，對(duì)其互斥訪問臨界區(qū)(互斥區(qū))：每個(gè)進(jìn)程中訪問臨界資源的那段程序段稱為臨界區(qū)(criticalsection)。3．臨界區(qū)對(duì)欲訪問的臨界資源進(jìn)行檢查，………………進(jìn)入?yún)^(qū)若此刻未被訪問，設(shè)正在訪問的標(biāo)志訪問臨界資源………………臨界區(qū)將正在訪問的標(biāo)志恢復(fù)為未被訪問的標(biāo)志……退出區(qū)其余部分………………剩余區(qū)repeat

entrysection

criticalsection

exitsection

remaindersectionuntilfalse3．臨界區(qū)

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

P/wait操作；

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

wait(S)：

whileS<=0dono-op；

S:=S-1；

signal(S)：

S:=S+1；信號(hào)量的物理意義

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

P2

wait(S)：表示請(qǐng)求分配一個(gè)資源

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

value:integer；

L:listofprocess；

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

varS：semaphore；

begin

S.value:=S.value-1；

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

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

varS:semaphore；

begin

S.value:=S.value+1；

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

end2．記錄型信號(hào)量3.AND型信號(hào)量前面介紹的進(jìn)程互斥問題，屬于多個(gè)進(jìn)程共享一個(gè)臨界資源。假如：兩個(gè)進(jìn)程A和B，共享數(shù)據(jù)D和E，為其分別設(shè)置互斥信號(hào)量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型信號(hào)量AND同步機(jī)制的基本思想：將進(jìn)程在整個(gè)運(yùn)行過程中需要的所有資源，一次性全部分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。只要尚有一個(gè)資源未能分配給進(jìn)程，其他所有可能為之分配的資源，也不分配給它。即對(duì)臨界資源的分配采取原子操作。Swait(S1,S2,…,Sn)ifS1>=1and…andSn>=1thenfori:=1tondoSi:=Si-1;endforelsePlacetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi<1,andsettheprogramcountofthisprocesstothebeginningofSwaitoperationendifSsignal(S1,S2,…,Sn)fori:=1tondoSi:=Si+1;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueueendfor

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

4．信號(hào)量集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．信號(hào)量集一般信號(hào)量集的幾種特殊情況Swait(S,d,d):表示每次申請(qǐng)d個(gè)資源，當(dāng)少于d個(gè)時(shí)，便不分配Swait(S,1,1):表示互斥信號(hào)量Swait(S,1,0):可作為一個(gè)可控開關(guān)（當(dāng)S1時(shí)，允許多個(gè)進(jìn)程進(jìn)入臨界區(qū)；當(dāng)S=0時(shí)，禁止任何進(jìn)程進(jìn)入臨界區(qū)）2.3.3信號(hào)量的應(yīng)用

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

begin

parbegin

process1:begin

repeat

wait(mutex)；

criticalsection

signal(mutex)；

remainderseetion

untilfalse；

end1．利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥process2:begin

repeat

wait(mutex)；

criticalsection

signal(mutex)；

remaindersection

untilfalse；

end

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

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

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

正常開車;

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

untilfalseend3.利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步busman():beginRepeat

關(guān)車門；

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

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

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

模塊化:一個(gè)管程是一個(gè)基本程序單位，可以單獨(dú)編譯

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

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

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

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

(TheProducer-ConsumerProblem)2、哲學(xué)家進(jìn)餐問題；

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

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

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

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

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

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

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

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

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

。消費(fèi)者利用該過程從緩沖池中取出一個(gè)產(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)者—消費(fèi)者問題 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)者—消費(fèi)者問題

producer:begin

repeat

produceaniteminnextp；

PC.put(item)；

untilfalse；

end

consumer:begin

repeat

PC.get(item)；

consumetheiteminnextc；

untilfalse；

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

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

repeat

wait(chopstick[i])；

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

eat；

signal(chopstick[i])；

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

think；

untilfalse；………1．利用記錄型信號(hào)量解決哲學(xué)家進(jìn)餐問題哲學(xué)家饑餓時(shí)，總是先拿左邊的筷子，再拿右邊的筷子分析：假設(shè)5個(gè)哲學(xué)家同時(shí)拿起他們各自左邊（右邊）筷子，就會(huì)使五個(gè)信號(hào)量chopstick均為0；那么，他們都只能拿到一支筷子而等待右邊的人放下筷子，誰也不能拿到一雙筷子來吃飯，這種等待狀態(tài)將一直保持下去，產(chǎn)生了死鎖。1．利用記錄型信號(hào)量解決哲學(xué)家進(jìn)餐問題哲學(xué)家進(jìn)餐問題分析死鎖思考思考思考思考思考準(zhǔn)備進(jìn)餐準(zhǔn)備進(jìn)餐準(zhǔn)備進(jìn)餐準(zhǔn)備進(jìn)餐準(zhǔn)備進(jìn)餐思考Wait（left_stick）Wait（right_stick)Signal（left_stick）eatSignal（right_stick)解決方法：1.至多只允許有四位哲學(xué)家同時(shí)去拿左邊的筷子，最終能保證至少有一位哲學(xué)家能夠進(jìn)餐，并在用畢后釋放出他用過的兩只筷子，從而使更多的哲學(xué)家能夠進(jìn)餐。---限制并發(fā)執(zhí)行的進(jìn)程數(shù)2.僅當(dāng)哲學(xué)家的左右兩只筷子均可用時(shí)，才允許他拿起筷子進(jìn)餐。---采用信號(hào)量集3.規(guī)定奇數(shù)號(hào)哲學(xué)家先拿他左邊的筷子，然后再去拿右邊的筷子；偶數(shù)號(hào)哲學(xué)家則相反。---保證總會(huì)有一個(gè)哲學(xué)家能同時(shí)獲得兩只筷子而進(jìn)餐2.4.2哲學(xué)家進(jìn)餐問題2315423154方法3第一種方法來解決實(shí)現(xiàn)沒有死鎖的哲學(xué)家問題：至多只允許有四位哲學(xué)家同時(shí)去拿左邊的筷子，最終能保證至少有一位哲學(xué)家能夠進(jìn)餐，并在用完時(shí)能放下他用過的兩支筷子，從而使其他的哲學(xué)家能夠進(jìn)餐。在實(shí)現(xiàn)時(shí)只需增加一個(gè)限定就餐人數(shù)的信號(hào)量num（互斥信號(hào)量），其初值設(shè)為4。任何哲學(xué)家拿筷子前先檢測num，算法如下：2.4.2哲學(xué)家進(jìn)餐問題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信號(hào)量機(jī)制解決哲學(xué)家進(jìn)餐問題在哲學(xué)家進(jìn)餐問題中，要求每個(gè)哲學(xué)家先獲得兩個(gè)臨界資源(筷子)后方能進(jìn)餐，這在本質(zhì)上就是前面所介紹的AND同步問題，故用AND信號(hào)量機(jī)制可獲得最簡潔的解法。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信號(hào)量機(jī)制解決哲學(xué)家進(jìn)餐問題2.4.3讀者—寫者問題描述：在計(jì)算機(jī)系統(tǒng)中，讀數(shù)據(jù)(文件)及修改、寫數(shù)據(jù)(文件)是經(jīng)常的，并要求對(duì)數(shù)據(jù)(文件、記錄)進(jìn)行共享。也就是說，多個(gè)進(jìn)程同時(shí)讀／寫(共享數(shù)據(jù))。而對(duì)于讀／寫數(shù)據(jù)，會(huì)有幾種情況發(fā)生：1)同時(shí)讀，不會(huì)發(fā)生副作用。2)有一個(gè)寫，其它讀、寫，會(huì)產(chǎn)生副作用。3)讀時(shí)，出現(xiàn)寫，也會(huì)產(chǎn)生副作用。2.4.3讀者—寫者問題1．利用記錄型信號(hào)量解決讀者—寫者問題分析：2、由于允許有多個(gè)讀者，為了解目前的讀者數(shù)量，設(shè)置一讀者計(jì)數(shù)變量readcount,初值為0。多個(gè)讀者都對(duì)readcount進(jìn)行操作，須設(shè)置對(duì)其操作的互斥信號(hào)量Rmutex，初值為1.1、為保證寫者進(jìn)程與其它進(jìn)程互斥訪問共享對(duì)象，設(shè)置互斥信號(hào)量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．利用記錄型信號(hào)量解決讀者—寫者問題

wait(rmutex)；