計(jì)算機(jī)操作系統(tǒng)課件

計(jì)算機(jī)操作系統(tǒng)

OperatingSystemofComputer

第四章進(jìn)程同步

?:?主要內(nèi)容：

小進(jìn)程的同步與互斥

8經(jīng)典進(jìn)程同步問(wèn)題

8管程機(jī)制

8進(jìn)程通信。

知識(shí)點(diǎn)及要求：

8要求掌握用P、V操作解決進(jìn)程同步問(wèn)題，了解

進(jìn)程間的通信。

4.1進(jìn)程的同步

。在多道程序系統(tǒng)中，由于資源共享或進(jìn)程合作，使

進(jìn)程間形成間接相互制約和直接相互制約關(guān)系，這

需要用進(jìn)程互斥與同步機(jī)制來(lái)協(xié)調(diào)兩種制約關(guān)系。

進(jìn)程同步的主要任務(wù)是使并發(fā)執(zhí)行的進(jìn)程間有效的

共享資源和相互合作，從而使程序的執(zhí)行具有可再

現(xiàn)性。

進(jìn)程的同步機(jī)制—信號(hào)量及P.V操作（解決進(jìn)程同

步互斥問(wèn)題）

1.進(jìn)程間的關(guān)系

?:?直接作用（相互合作）：

進(jìn)程間的相互聯(lián)系是有意識(shí)的安排的,

直接作用只發(fā)生在相交進(jìn)程間

。間接作用（資源共享）：

進(jìn)程間要通過(guò)某種中介發(fā)生聯(lián)系，是

無(wú)意識(shí)安排的，可發(fā)生在相交進(jìn)程之

間，也可發(fā)生在無(wú)關(guān)進(jìn)程之間

相互感知程度交互關(guān)系一個(gè)進(jìn)程對(duì)其他進(jìn)

程的影響

相互不感知（完全不競(jìng)爭(zhēng)(competition)一個(gè)進(jìn)程的操作對(duì)

了解其它進(jìn)程的存其他進(jìn)程的結(jié)果無(wú)

在）影響

間接感知（雙方都與通過(guò)共享進(jìn)行協(xié)作一個(gè)進(jìn)程的結(jié)果依

第三方交互，如共賴于從其他進(jìn)程獲

享資源）得的信息

直接感知（雙方直接通過(guò)通信進(jìn)行協(xié)作一個(gè)進(jìn)程的結(jié)果依

交互，如通信）賴于從其他進(jìn)程獲

得的信息

2.進(jìn)程的同步（直接作用）

指系統(tǒng)中多個(gè)進(jìn)程中發(fā)生的事件

存在某種時(shí)序關(guān)系，需要相互合作，

共同完成一項(xiàng)任務(wù)。具體說(shuō)，一個(gè)進(jìn)

程運(yùn)行到某一點(diǎn)時(shí)要求另一伙伴進(jìn)程

為它提供消息，在未獲得消息之前，

該進(jìn)程處于等待狀態(tài)，獲得消息后被

喚醒進(jìn)入就緒狀態(tài)。

3.進(jìn)程的互斥（間接作用）

由于各進(jìn)程要求共享資源，而有些資

源需要互斥使用，因此各進(jìn)程間競(jìng)爭(zhēng)使用

這些資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥。

臨界資源：

系統(tǒng)中某些資源一次只允許一個(gè)進(jìn)程使用,

稱這樣的資源為臨界資源或互斥資源或共

享變量

4.基本概念

?:?進(jìn)程互斥：指在多道程序環(huán)境下，每次只

允許一個(gè)進(jìn)程對(duì)臨界資源進(jìn)行訪問(wèn)。

?:?進(jìn)程同步：指多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上

的協(xié)調(diào)。

?臨界資源:一次僅供一個(gè)進(jìn)程使用的資源。

在進(jìn)程中涉及到臨界資源的程序段叫臨界

區(qū)

?多個(gè)進(jìn)程訪問(wèn)同一資源的臨界區(qū)稱為相關(guān)

臨界區(qū)

共享變量

5.使用互斥區(qū)的原則

?:?空閑讓進(jìn)：當(dāng)無(wú)進(jìn)程在互斥區(qū)時(shí)，任何

有權(quán)使用互斥區(qū)的進(jìn)程可進(jìn)入

?:?忙則等待：不允許兩個(gè)以上的進(jìn)程同時(shí)

進(jìn)入互斥區(qū)

孝有限等待：任何進(jìn)入互斥區(qū)的要求應(yīng)在

有限的時(shí)間內(nèi)得到滿足

?:?讓權(quán)等待：處于等待狀態(tài)的進(jìn)程應(yīng)放棄

占用CPU,以使其他進(jìn)程有機(jī)會(huì)得到CPU

的使用權(quán)

使用互斥區(qū)的原則

前提：任何進(jìn)程無(wú)權(quán)停止其它進(jìn)程的運(yùn)行

進(jìn)程之間相對(duì)運(yùn)行速度無(wú)硬性規(guī)定

進(jìn)程互斥的解決有兩種做法：

?由競(jìng)爭(zhēng)各方平等協(xié)商

?引入進(jìn)程管理者，由管理者來(lái)協(xié)調(diào)競(jìng)爭(zhēng)各方對(duì)互

斥資源的使用

具體方法：

硬件（利用Test-and-Set指令或利用swap指令

實(shí)現(xiàn)）

軟件（用編程解決，但常常忙等待）

6.進(jìn)程互斥的軟件方法

?：?通過(guò)平等協(xié)商方式實(shí)現(xiàn)進(jìn)程互斥的最初方法

是軟件方法

其基本思路是在進(jìn)入?yún)^(qū)檢查和設(shè)置一些標(biāo)志,

如果已有進(jìn)程在臨界區(qū)，則在進(jìn)入?yún)^(qū)通過(guò)循

環(huán)檢查進(jìn)行等待；在退出區(qū)修改標(biāo)志

其中的主要問(wèn)題是設(shè)置什么標(biāo)志和如何檢查

軟彳?！贩ǖ娜秉c(diǎn)：

L忙等待

2.實(shí)現(xiàn)過(guò)于復(fù)雜

3.需要高的編程技巧

軟件解法⑴

free:表示臨界區(qū)標(biāo)志

true:有進(jìn)程在臨界區(qū)

false:無(wú)進(jìn)程在臨界區(qū)（初值）

while(free);

free=true;

臨界區(qū)

free=false;

軟件解法⑵

turn:trueP進(jìn)入臨界區(qū)

falseQ進(jìn)入臨界區(qū)

????

P:while(notturn);

臨界區(qū)

turn=false;

Q:while(turn);

臨界區(qū)-

turn=true;

軟件解法⑶

pturn,qturn:初值為false

P進(jìn)入臨界區(qū)的條件：pturnAnotqturn

Q進(jìn)入臨界區(qū)的條件:notpturnAqturn

P????Q……

pturn=true;pturn=true;

while(qturn);while(pturn);

臨界區(qū)臨界區(qū)

pturn=false;qturn=false;

破件解法（1）—“測(cè)試并設(shè)置”指令

booleanTS

(boolean*lock)whileTS(&lock);

(

臨界區(qū)

TS=*lock;

lock=false;

*lock=true;

破件解法⑵一“交換”指令

voidSWAP(intkey=true;

*a,int*b)do

((

inttemp;WAP(&lock,key);

temp=*a;}while(key);

*a=*b;

臨界區(qū)

*b=temp;

}lock:=false;

硬件解法⑶一“開(kāi)關(guān)中斷”指令

進(jìn)入臨界區(qū)前執(zhí)行：

執(zhí)行“關(guān)中斷”指令

離開(kāi)臨界區(qū)后執(zhí)行：

執(zhí)行“開(kāi)中斷”指令

7.進(jìn)程的同步機(jī)制——

信號(hào)量及P.V操作（解決進(jìn)程同步）

同步機(jī)制：

信號(hào)量及P、V操作；管程；條

件臨界域；路徑表達(dá)式等（用于

集中式系統(tǒng)中）

同步機(jī)制應(yīng)滿足的基本要求

?:?描述能力

?:?可以實(shí)現(xiàn)

?:?效率IWJ

?使用方便

解決互斥的鎖機(jī)制

*實(shí)現(xiàn)互斥的一種軟件方法是采用鎖機(jī)制,

即提供一對(duì)上鎖(Lock)和開(kāi)鎖(UnLock)

原語(yǔ)，以及一個(gè)鎖變量W。

。進(jìn)程進(jìn)入臨界區(qū)前，通過(guò)鎖變量來(lái)判斷

臨界資源是否被占用。

信號(hào)量機(jī)制

?信號(hào)量機(jī)制是一種卓有成效的進(jìn)程同步工具，

被廣泛應(yīng)用于單處理機(jī)和多處理機(jī)系統(tǒng)，以及

計(jì)算機(jī)網(wǎng)絡(luò)中。

?:?鎖機(jī)制僅能表示“開(kāi)”與“關(guān)”兩種狀態(tài)；開(kāi)、

關(guān)鎖原語(yǔ)必須作為原子操作來(lái)進(jìn)行；關(guān)鎖原語(yǔ)

中反復(fù)測(cè)試mutex狀態(tài)，浪費(fèi)了處理機(jī)的時(shí)間;

鎖機(jī)制只能解決互斥，不能用于同步。信號(hào)量

同步機(jī)制能完滿地解決上述問(wèn)題。

信號(hào)量：semaphores

是一個(gè)數(shù)據(jù)結(jié)構(gòu)

?定義如下：

strucsemaphore

{

intvalue;

pointer_PCBqueue;

?:?信號(hào)量說(shuō)明：

semaphores;

p操作

p(s)

s.value=s.value一一;

if(s.value<0)

(

該進(jìn)程狀態(tài)置為等待狀態(tài)；

將該進(jìn)程的PCB插入相應(yīng)的等待隊(duì)列末尾

s.queue;

P操作

?意味著請(qǐng)求分配一個(gè)單位資源

平.

s》o?-V

V操作

V(s)

s.value=s.value++;

if(s.value<=0)〃意味著原有資源已用完,

等待隊(duì)列非空

{

喚醒相應(yīng)等待隊(duì)列s.queue中等待的一個(gè)進(jìn)程

改變其狀態(tài)為就緒態(tài)

并將其插入就緒隊(duì)列

V操作

?意味著釋放一個(gè)單位資源

SWO?

Yl

從信號(hào)量的等待隊(duì)

列中取出等待量

P、V操作為原語(yǔ)操作

原語(yǔ)：是由若干多機(jī)器指令構(gòu)成的完成某種

特定功能的一段程序，具有不可分割性。

即原語(yǔ)的執(zhí)行必須是連續(xù)的，在執(zhí)行過(guò)程

中不允許被中斷。

實(shí)現(xiàn)：開(kāi)關(guān)中斷

信號(hào)量的使用：

必須置一次且只能置一次初值

初值不能為負(fù)數(shù)

只能執(zhí)行P、V操作

用P、V操作解決進(jìn)程間互斥問(wèn)題

互斥例子

?：?三個(gè)進(jìn)程共用兩個(gè)I/O緩沖區(qū)。

?:?解：設(shè)用信號(hào)量S表示共享資源，S初

始值為2

■A班和B過(guò)衽?CQtt

假設(shè)用個(gè)進(jìn)程使用緩沖區(qū)占兩個(gè)時(shí)間片

?表示正在占用時(shí)間片的進(jìn)程

同步例子

。有A、B兩進(jìn)程，A進(jìn)程從卡片機(jī)讀信息

入緩沖區(qū)，B進(jìn)程負(fù)責(zé)加工讀進(jìn)緩沖區(qū)

的卡片

。解：設(shè)信號(hào)量S1：緩沖區(qū)中有否可供加

工的信息，初始值為0;信號(hào)量S2：緩

沖區(qū)是否為空，初始值為1。

同步例子(續(xù))

榆入aHlA加工遞錢B

在輸入進(jìn)程A中，可以把P(S2)調(diào)到

V(S1)后面，而把信號(hào)量S2的初始值設(shè)

為0。

用P-V操作描述前趨關(guān)系的例子

?:?信號(hào)量還可以描述程序或語(yǔ)句之間的前

趨關(guān)系O

用P-V操作描述前趨關(guān)系（續(xù)）

描述如下:

Vara,b,c,d,e,f,g：semaphore：=0,0,0,0,0,0,0；

begin

parbegin

beginSI；V(a)；V(b)；end；

beginP(a)；S2；V(c)；V(d)；end；

beginP(b)；S3；V(e)；end；

beginP(c)；S4；V(f)；end；

beginP(d)；S5；Vg()；end；

beginP(e)；P(f);P(g);S6；end；

parend

經(jīng)典的生產(chǎn)者一消費(fèi)者問(wèn)題

生產(chǎn)者消費(fèi)者

一次只可放一個(gè)產(chǎn)品

經(jīng)典的生產(chǎn)者一消費(fèi)者問(wèn)題

同步問(wèn)題：

P進(jìn)程不能往“滿”的緩沖區(qū)中放

產(chǎn)品，設(shè)置信號(hào)量為S1

Q進(jìn)程不能從“空”的緩沖區(qū)中取

產(chǎn)品，設(shè)置信號(hào)量S2

P:

while(true){while(true){

生產(chǎn)一個(gè)產(chǎn)品；P(s2);

P(s1);從緩沖區(qū)取產(chǎn)品;

送產(chǎn)品到緩沖區(qū);V(s1);

V(s2);消費(fèi)產(chǎn)品；

)；)；

S1初值為1,S2初值為0

生產(chǎn)者-消費(fèi)者問(wèn)題

?生產(chǎn)者一消費(fèi)者(Producer-Consumer)問(wèn)題是著

名的進(jìn)程同步問(wèn)題。它描述一組生產(chǎn)者向一組

消費(fèi)者提供消息，它們共享一個(gè)有界緩沖池，

生產(chǎn)者向其中投放消息，消費(fèi)者從中取得消息。

以下用信號(hào)量解決生產(chǎn)者一消費(fèi)者問(wèn)題。

?:?假設(shè)緩沖池中有n個(gè)緩沖區(qū)，每個(gè)緩沖區(qū)存放一

個(gè)消息，可利用互斥信號(hào)量mutex使諸進(jìn)程對(duì)緩

沖泡實(shí)貌宣序齒問(wèn);劉用empty和full計(jì)數(shù)信號(hào)

量分別表示空緩沖及滿緩沖的數(shù)量。又假定這

些生產(chǎn)者和消費(fèi)者互相等效，只要緩沖池未滿,

生產(chǎn)者可將消息送入緩沖池；只要緩沖池未空,

消費(fèi)者可從緩沖池取走一個(gè)消息。

方文消息耳又消息、

(Buffer)

生產(chǎn)者-消費(fèi)者問(wèn)題(續(xù))

?:?其中，mutex,empty,full的初始值分別

為為n,0；

?i產(chǎn)弟班隹消費(fèi)者進(jìn)銀:

一生埼一件新產(chǎn)品?

P(CEply)|P(full)I

P(mulcx)|P(mutex)|

〔把產(chǎn)品放；把產(chǎn)品從緩

赴約沖池沖斑戢定n

V(mutex)V《mutex)|

---------1…V，<fu-一l.l一)，-」IV(empty)|

P操作的順序可換嗎?

P.V操作討論

1)信號(hào)量的物理含義：

s〉o表示有s個(gè)資源可用

s=0表示無(wú)資源可用

s<0則|S|表示S等待隊(duì)列中的進(jìn)程個(gè)數(shù)

P(s)：表示申請(qǐng)一個(gè)資源

V(S)表示釋放一個(gè)資源。信號(hào)量的初值應(yīng)該大于等于0

2)P.V操作必須成對(duì)出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作

當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程

當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn)

如果P(S1)和P(S2)兩個(gè)操作在一起，那么P操作的順序至

關(guān)重要，一個(gè)同步P操作與一個(gè)互斥P操作在一起時(shí)同步P操作

在互斥P操作前

而兩個(gè)V操作無(wú)關(guān)緊要

P.V操作的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

簡(jiǎn)單，而且表達(dá)能力強(qiáng)（用PY操作

可解決任何同步互斥問(wèn)題）

缺點(diǎn)：

“不夠安全；P.V操作使用不當(dāng)會(huì)出

現(xiàn)死鎖；遇到復(fù)雜同步互斥問(wèn)題時(shí)實(shí)

現(xiàn)復(fù)雜

8.信號(hào)量集一AND型信號(hào)量集

。AND型信號(hào)量集是指同時(shí)需要多種資源且

每種占用一個(gè)時(shí)的信號(hào)量操作

?AND型信號(hào)量集的基本思想：在一個(gè)原語(yǔ)

中申請(qǐng)整段代碼需要的多個(gè)臨界資源，要

么全部分配給它，要么一個(gè)都不分配

AND型信號(hào)量集P原語(yǔ)為Swait

?AND型信號(hào)量集V原語(yǔ)為Ssignal

Swait(S1ZS2ZSn)//P原語(yǔ)；

(

whil一(TRUE){

if(Si>=1&&S2>=1&&...&&sn>=1)

{//滿足資源要求時(shí)的處理；

for(i=1;i<=n;++i)——S1;

//注：與P的處理不同，這里是在確

信可滿足

口//資源要求時(shí)，才進(jìn)行減1操作；

break;

)

else{//某些資源不夠時(shí)的處理；

調(diào)用進(jìn)程進(jìn)入第一個(gè)小于1信號(hào)量的等待隊(duì)列

S..qu一u一；

阻塞調(diào)用進(jìn)程；

)

Ssignal(SlfS2<…,Sn)

(

for(i=1;i<=n;++i)

{

++Si；//釋放占用的資源；

for(在S].qu一u一中等待的每一^進(jìn)

程P)

//檢查每種資源的等待隊(duì)列的所有

進(jìn)程；

(

從等待隊(duì)列.qu一u一中取出進(jìn)程P;

if（判斷進(jìn)程P是否通過(guò)Swait中的測(cè)試）

//注：與signal不同，這里要進(jìn)行重新

判斷;

{//通過(guò)檢查（資源夠用）時(shí)的處理；

進(jìn)程P進(jìn)入就緒隊(duì)列；

}

一1s一

{//未通過(guò)檢查（資源不夠用）時(shí)的處理;

進(jìn)程P進(jìn)入某等待隊(duì)列；

}

)

9.一般“信號(hào)量集”

一般信號(hào)量集是指同時(shí)需要多種資

源、每種占用的數(shù)目不同、且可分

配的資源還存在一個(gè)臨界值時(shí)的信

號(hào)量處理

一般信號(hào)量集的基本思路就是在

AND型信號(hào)量集的基礎(chǔ)上進(jìn)行擴(kuò)充,

在一次原語(yǔ)操作中完成所有的資源

申請(qǐng)。

?:?進(jìn)程對(duì)信號(hào)量Sj的

測(cè)試值為tj（表示信號(hào)量的判斷條件，要

求Sj>=tj；即當(dāng)資源數(shù)量低于tj時(shí)，便

木予分配）

占用值為4(表示資源的申請(qǐng)量，即Sj二

Si-dp

對(duì)應(yīng)的P、V原語(yǔ)格式為：

c^Swait(S.,d.;???；St

_LrJ_1n1,1.1nA

dn)；

G^Ssignal(S.d.;???；Sd);

_LrJL1n1^11

一般“信號(hào)量集”可以用于各種情況的

資源分配和釋放，幾種特殊情況：

?Swait(S,d,d)表示每次申請(qǐng)d個(gè)資源,

當(dāng)少工d個(gè)時(shí)，便不分配

。Swag,1,1)表示互斥信號(hào)量

?Swait(S,1,0)可作為一個(gè)可控開(kāi)關(guān)

(當(dāng)S"時(shí)，允許多個(gè)進(jìn)程進(jìn)入臨界

區(qū)；當(dāng)s=o時(shí)，禁止任何進(jìn)程進(jìn)入臨

界區(qū))

10.經(jīng)典問(wèn)題

1）讀者寫(xiě)者問(wèn)題

有兩組并發(fā)進(jìn)程：

讀者和寫(xiě)者,共享一組數(shù)據(jù)區(qū)

要求：

允許多個(gè)讀者同時(shí)執(zhí)行讀操作

不允許讀者、寫(xiě)者同時(shí)操作

不允許多個(gè)寫(xiě)者同時(shí)操作

第一類：讀者優(yōu)先

如果讀者來(lái)：

1）無(wú)讀者、寫(xiě)者，新讀者可以讀

2）有寫(xiě)者等，但有其它讀者正在讀，則

新讀者也可以讀

3）有寫(xiě)者寫(xiě)，新讀者等

如果寫(xiě)者來(lái)：

1）無(wú)讀者，新寫(xiě)者可以寫(xiě)

2）有讀者，新寫(xiě)者等待

3）有其它寫(xiě)者，新寫(xiě)者等待

第一類讀者寫(xiě)者問(wèn)題的解法

讀者：

while(true){寫(xiě)者：

P(mutex);while(true){

readcount++;

if(readcount==1)P(w);

P(w);

V(mutex);寫(xiě)

讀V(w);

P(mutex);

readcount)；

if(readcount==0)

V(w);

V(mutex);

第一類讀者寫(xiě)者問(wèn)題的解法

（一般信號(hào)量集）

讀者:寫(xiě)者:

swait(wmutex,1,1;swait(rcount,1,1;

rcount,R,0);wmutex,1,0);

讀；寫(xiě)；

ssignal(wmutex,1);ssignal(rcount,1);

2）哲學(xué)家就餐問(wèn)題

有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌

中央有一盤通心粉，每人面前有一只空

盤子，每?jī)扇酥g放一只筷子

每個(gè)哲學(xué)家的行為是思考，感到饑

餓，然后吃通心粉

為了吃通心粉，每個(gè)哲學(xué)家必須拿

到兩只筷子，并且每個(gè)人只能直接從自

己的左邊或右邊去取筷子

#defineN5

voidphilosopher(inti){

while(true){

思考；

P(fork[i]);P(fork[(i+1)%5])；

進(jìn)食；

V(fork[i]);V(fork[(i+1)%5])；

}

}

為防止死鎖發(fā)生可采取的措施：

*最多允許4個(gè)哲學(xué)家同時(shí)坐在桌子周圍

?僅當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí),

才允許他拿筷子2

?:?給所有哲學(xué)家編號(hào)，奇數(shù)號(hào)的哲學(xué)家必須

首先拿左邊的筷子，偶數(shù)號(hào)的哲學(xué)家則反

之

為了避免死鎖，把哲學(xué)家分為三種狀態(tài)，

思考，饑餓，進(jìn)食，并且一次拿到兩只筷

子，否則不拿

Varchopstickarray[0,..,4]of

semaphore:=(1,1,1,1);

(

while(true){

思考；

Sswait(chopstick[(i+1)%5],chopstick[i])；

進(jìn)食；

Ssignal(chopstick[(i+1)%5],chopstick[i]);

}

}

3）第二類讀者寫(xiě)者問(wèn)題：

寫(xiě)者優(yōu)先

條件：

1）多個(gè)讀者可以同時(shí)進(jìn)行讀

2）寫(xiě)者必須互斥（只允許一個(gè)寫(xiě)者寫(xiě)，

也不能讀者寫(xiě)者同時(shí)進(jìn)行）

3）寫(xiě)者優(yōu)先于讀者（一旦有寫(xiě)者，則后

續(xù)讀者必須等待，喚醒時(shí)優(yōu)先考慮寫(xiě)

者）

4.2管程機(jī)制

1.管程的提出

采用P-V同步機(jī)制來(lái)編寫(xiě)并發(fā)程序，對(duì)于共享變量

及信號(hào)量變量的操作將被分散于各個(gè)進(jìn)程中

缺點(diǎn)：

1）易讀性差，因?yàn)橐私鈱?duì)于一組共享變量及信號(hào)

量的操作是否正確，則必須通讀整個(gè)系統(tǒng)或者并

發(fā)程序

2）不利于修改和維護(hù)，因?yàn)槌绦虻木植啃院懿?，?/p>

以任一組變量或一段代碼的修改都可能影響全局

3）正確性難以保證，因?yàn)椴僮飨到y(tǒng)或并發(fā)程序通常

很大，要保證這樣一個(gè)復(fù)雜的系統(tǒng)沒(méi)有邏輯錯(cuò)誤

是很難的

2.管程概念

?:?概念：指關(guān)于共享資源的數(shù)據(jù)及在其上操

作的一組過(guò)程或共享數(shù)據(jù)結(jié)構(gòu)及其規(guī)定的

所有操作。

?:?系統(tǒng)按資源管理的觀點(diǎn)分解成若干模塊，

用數(shù)據(jù)表示抽象系統(tǒng)資源，同時(shí)分析了共

享資源和專用資源在管理上的差別，按不

同的管理方式定義模塊的類型和結(jié)構(gòu)，使

同步操作相對(duì)集中，從而增加了模塊的相

對(duì)獨(dú)立性。

3.管程的組成

管程的四個(gè)組成部分：

名稱

數(shù)據(jù)結(jié)構(gòu)說(shuō)明

?對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過(guò)程/函數(shù)

初始化語(yǔ)句

局部于管程的數(shù)據(jù)結(jié)構(gòu)，僅被局部于管

程的過(guò)程訪問(wèn)。局部于管程的過(guò)程，也僅能

訪問(wèn)管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)。

管程（相當(dāng)于圍墻）把共享變量和對(duì)它

進(jìn)行操作的若干過(guò)程圍起來(lái)。

管程的形式

TYPEmonitor_name=MONITOR;

共享變量說(shuō)明一

define本管程內(nèi)所定義、本管程外可調(diào)用的過(guò)程（函數(shù)）

名字表

use本管程外所定義、本管程內(nèi)將調(diào)用的過(guò)程（函數(shù)）

名字表

PROCEDURE過(guò)程名（形參表）；

過(guò)程局部變量說(shuō)明；

BEGIN

語(yǔ)句序列；

END;

FUNCTION函數(shù)名（形參表）：值類型;

函數(shù)局部變量說(shuō)明；

BEGIN

語(yǔ)句序列；

END;

BEGIN

共享變量初始化語(yǔ)句序列;

END;

4.管程的三個(gè)主要的特性

?:?模塊化:一個(gè)管程是一個(gè)基本程序單位，可以

單獨(dú)編譯

?:?抽象數(shù)據(jù)類型:管程是一種特殊的數(shù)據(jù)類型,

其中不僅有數(shù)據(jù)，而且有對(duì)數(shù)據(jù)進(jìn)行操作的代

碼

?:?信息掩蔽:管程是半透明的，管程中的外部

過(guò)程（函數(shù)）實(shí)現(xiàn)了某些功能，至于這些功能

是怎樣實(shí)現(xiàn)的，在其外部則是不可見(jiàn)的

5.管程的要素

?:?管程中的共享變量在管程外部是不可

見(jiàn)的，外部只能通過(guò)調(diào)用管程中所說(shuō)

明的外部過(guò)程（函數(shù)）來(lái)間接地訪問(wèn)

管程中的共享變量

?:?為了保證管程共享變量的數(shù)據(jù)完整性,

規(guī)定管程互斥進(jìn)入

?:?管程通常是用來(lái)管理資源的，因而在

管程中應(yīng)當(dāng)設(shè)有進(jìn)程等待隊(duì)以及相應(yīng)

的等待及喚醒操作

問(wèn)題：多個(gè)進(jìn)程出現(xiàn)在管程中

當(dāng)一個(gè)進(jìn)入管程的進(jìn)程執(zhí)行等待操作時(shí)，它

應(yīng)當(dāng)釋放管程的互斥權(quán)；當(dāng)一個(gè)進(jìn)入管程的

進(jìn)程執(zhí)行喚醒操作時(shí)（如P喚醒Q）,管程

中便存在兩個(gè)同時(shí)處于活動(dòng)狀態(tài)的進(jìn)程

處理方法有三種：

?：.P等待Q繼續(xù)，直到Q退出或等待

。Q等待P繼續(xù)，直到P等待或退出

*規(guī)定喚醒為管程中最后一個(gè)可執(zhí)行的操作

因?yàn)楣艹淌腔コ膺M(jìn)入的，所以當(dāng)一個(gè)進(jìn)程

試圖進(jìn)入一個(gè)巳被占用的管程時(shí)它應(yīng)當(dāng)在管程

的入口處等待，因而在管程的入口處應(yīng)當(dāng)有一

個(gè)進(jìn)程等待隊(duì)列，稱作入口等待隊(duì)列

如果進(jìn)程P喚醒進(jìn)程Q,則P等待Q繼續(xù),

如果進(jìn)程Q在執(zhí)行又喚醒進(jìn)程R,則Q等待R

繼續(xù)，.?????，如此，在管程內(nèi)部，由于執(zhí)行喚

醒操作，可能會(huì)出現(xiàn)多個(gè)等待進(jìn)程，因而還需

要有一個(gè)進(jìn)程等待隊(duì)列，這個(gè)等待隊(duì)列被稱為

緊急等待隊(duì)列。它的優(yōu)先級(jí)應(yīng)當(dāng)高于入口等待

隊(duì)列的優(yōu)先級(jí)

由于管程通常是用于管理資源的，因而在管程內(nèi)

部，應(yīng)當(dāng)存在某種等待機(jī)制。當(dāng)進(jìn)入管程的進(jìn)程因資

源被占用等原因不能繼續(xù)運(yùn)行時(shí)使其等待。為此在管

程內(nèi)部可以說(shuō)明和使用一種特殊類型的變量，稱作條

件變量：

VARC:condition;

對(duì)于條件型變量，可以執(zhí)行wait和signal操作：

wait(c)：如果緊急等待隊(duì)列非空，則喚醒第一

個(gè)等待者；否則釋放管程的互斥權(quán)，執(zhí)行此操

作的進(jìn)程的PCB入c鏈尾部

signal(c)：如果c鏈為空,則相當(dāng)于空操作,執(zhí)

行此操作的進(jìn)程繼續(xù)；否則喚醒第一個(gè)等待者,

執(zhí)行此操作的進(jìn)程的PCB入緊急等待隊(duì)列的尾部

6.管程的實(shí)現(xiàn)

兩個(gè)主要途徑：

?:?直接構(gòu)造（效率高）

?:?間接構(gòu)造，即用某種已經(jīng)實(shí)現(xiàn)的同步機(jī)制

去構(gòu)造

例子：用P-V操作構(gòu)造管程

7.管程和進(jìn)程的異同點(diǎn)

(1)設(shè)置進(jìn)程和管程的目的不同

⑵系統(tǒng)管理數(shù)據(jù)結(jié)構(gòu)

進(jìn)程：PCB

管程：等待隊(duì)列

⑶管程被進(jìn)程調(diào)用

⑷管程是操作系統(tǒng)的固有成分,

無(wú)創(chuàng)建和撤消

4.3進(jìn)程通信

1.進(jìn)程通信概述

?P.v操作實(shí)現(xiàn)的是進(jìn)程之間的低級(jí)通訊，

所以P.V為低級(jí)通訊原語(yǔ)。它只能傳遞簡(jiǎn)

單的信號(hào)，不能傳遞交換大量信息

。如果要在進(jìn)程間傳遞大量信息則要用

Send/Receive原語(yǔ)（高級(jí)通訊原語(yǔ)）

2.實(shí)現(xiàn)進(jìn)程通信的方式

?:?共享存儲(chǔ)器方式：相互通信的進(jìn)程通過(guò)共享

某些數(shù)據(jù)結(jié)構(gòu)或存儲(chǔ)區(qū)來(lái)進(jìn)行通信，可分為

共享數(shù)據(jù)結(jié)構(gòu)方式、共享存儲(chǔ)區(qū)方式；

?:?消息通信方式：進(jìn)程間的消息交換以消息或

報(bào)文為單位，程序員利用一組通信命令（原語(yǔ)）

來(lái)實(shí)現(xiàn)通信，可分為直接、間接通信方式；

?:?共享文件方式：利用共享文件來(lái)實(shí)現(xiàn)進(jìn)程間

的通信。

3.管道通信

?:?在UNIX系統(tǒng)中，利用一個(gè)打開(kāi)的共享

文件來(lái)連接兩個(gè)相互通信的進(jìn)程，該

共享文件稱為管道(Pipe),因而該方

式又稱為管道通信。

?:?為了協(xié)調(diào)雙方通信，管道通信必須提

供三方面的協(xié)調(diào)能力：互斥、同步、

對(duì)方是否存在。

4.消息傳遞模式

?：?系統(tǒng)為進(jìn)程提供了兩個(gè)高級(jí)通訊原語(yǔ)

send和receive。要進(jìn)行消息傳遞時(shí)執(zhí)

行send，當(dāng)接收者要接收消息時(shí)執(zhí)行

receive

?:?消息緩沖：在內(nèi)存中開(kāi)設(shè)緩沖區(qū)，發(fā)

送進(jìn)程將消息送入緩沖區(qū)，接收進(jìn)程

接收傳遞來(lái)的緩沖區(qū)

*信箱通信

5.直接方式

共享文件模式：管道通信發(fā)送進(jìn)程發(fā)消

息時(shí)要指定接收進(jìn)程的名字，

反過(guò)來(lái)，接收時(shí)要指明發(fā)送進(jìn)程的名字

Send(receiver,message)

Receiver(sender,message)

?:?對(duì)稱形式：一對(duì)一

?:?非對(duì)稱形式：多對(duì)一(顧客/服務(wù)員).

有緩沖(有界，無(wú)界)，無(wú)緩沖

直接通信方式

-進(jìn)嘏P17操作系統(tǒng)卜通信通道

直接通信方式模型

6.消息緩沖（有界緩沖區(qū)）

在操作系統(tǒng)空間設(shè)置一組緩沖區(qū)，當(dāng)發(fā)送進(jìn)程需

要發(fā)送消息時(shí)，執(zhí)行send系統(tǒng)調(diào)用，產(chǎn)生自愿性中斷,

進(jìn)入操作系統(tǒng)，操作系統(tǒng)為發(fā)送進(jìn)程分配一個(gè)空緩沖

區(qū)，并將所發(fā)送的消息從發(fā)送進(jìn)程copy到緩沖區(qū)中，

然后將該載有消息的緩沖區(qū)連接到接收進(jìn)程的消息鏈

鏈尾，如此就完成了發(fā)送過(guò)程。發(fā)送進(jìn)程返回到用戶

態(tài)繼續(xù)執(zhí)行。

在以后某個(gè)時(shí)刻，當(dāng)接收進(jìn)程執(zhí)行到receive接

收原語(yǔ)時(shí)，也產(chǎn)生自愿性中斷進(jìn)入操作系統(tǒng)，由操作

系統(tǒng)將載有消息的緩沖區(qū)從消息鏈中取出，并把消息

內(nèi)容copy到接收進(jìn)程空間，之后收回緩沖區(qū)，如此就

完成了消息的接收，接收進(jìn)程返回到用戶態(tài)繼續(xù)進(jìn)行。

直接通信方式實(shí)例-消息緩沖通信

?:?消息緩沖數(shù)據(jù)結(jié)構(gòu)（下圖）

sender消息發(fā)送者

size消息長(zhǎng)度

text消息正文

next指向下一個(gè)消息緩沖區(qū)的指針

?:?此外，進(jìn)程的PCB塊中增加一些數(shù)據(jù)項(xiàng)以

支持消息緩沖區(qū)的通信機(jī)制實(shí)現(xiàn)；如：

mq,消息鏈?zhǔn)字羔?；mutex,消