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

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

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

進(jìn)程控制

進(jìn)程同步

經(jīng)典進(jìn)程的同步問題

進(jìn)程通信

線程

2.1進(jìn)程的基本概念

?程序的順序執(zhí)行及其特征

?前趨圖

?程序的并發(fā)執(zhí)行及其特征

?進(jìn)程的特征與狀態(tài)

?進(jìn)程控制塊

2

?、程序的順序執(zhí)行及其特征

3

程序的順序執(zhí)行

順序環(huán)境：

在系統(tǒng)中只有一個(gè)程序在運(yùn)行，該程序獨(dú)占

系統(tǒng)所有資源，其執(zhí)行不受外界影響。

4

特征：

?程序執(zhí)行的順序性

?程序執(zhí)行的封閉性

?程序執(zhí)行結(jié)果的可再現(xiàn)性

------

------

5

二、前趨圖

?有向無循環(huán)圖

?描述進(jìn)程之間執(zhí)行的前后關(guān)系

?圖中結(jié)點(diǎn)描述程序段、進(jìn)程或一條語句._______________

?結(jié)點(diǎn)間的有向邊表示結(jié)點(diǎn)間存在的關(guān)系

?如果節(jié)點(diǎn)之間是前趨關(guān)系，則表示為Pi-Pj,即Pi是Pj的直接

前趨，Pj是Pi的直接后繼。

6

P2

?5

PlP3?8

P6

p4

?7

?前趨關(guān)系：PI-PDP1-P3,Pl-P*P2一「5,P3一「5,P4一「6,

P4fp7,P5fp8,P6fp8,P7fp9,P8fp9

?前趨圖中必須不存在循環(huán)7

三、程序的并發(fā)執(zhí)行及其特征

并發(fā)環(huán)境：

在一定時(shí)間內(nèi)有兩個(gè)或兩個(gè)以上的程序

同處于開始運(yùn)行但尚未結(jié)束的狀態(tài)，并

且次序不是事先確定的

AB

AB

B11A

BA

8

四、進(jìn)程的特征與狀態(tài)

10

1、進(jìn)程的定義

進(jìn)程是一個(gè)具有獨(dú)立功能的程序關(guān)于某個(gè)

數(shù)據(jù)集合的一次運(yùn)行活動(dòng)。

11

2、進(jìn)程的特征

?結(jié)構(gòu)特征

?動(dòng)態(tài)性

?并發(fā)性

?獨(dú)立性

?異步性

12

3、進(jìn)程和程序的關(guān)系

?進(jìn)程是一個(gè)動(dòng)態(tài)概念，程序是靜態(tài)概念。

?程序可作為資料長(zhǎng)期保存，進(jìn)程有生命期

?進(jìn)程的組成是程序，數(shù)據(jù)，進(jìn)程控制塊

?同一程序運(yùn)行于不同數(shù)據(jù)集合，將屬于不同

進(jìn)程。

?一個(gè)程序可對(duì)應(yīng)多個(gè)進(jìn)程，一個(gè)進(jìn)程可包含

多個(gè)程序。

13

4、進(jìn)程狀態(tài)

進(jìn)程基本狀態(tài)

進(jìn)程掛起

14

?最簡(jiǎn)單的進(jìn)程狀態(tài)劃分：運(yùn)行狀態(tài)

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

分派

暫停

15

排隊(duì)圖

隊(duì)列

進(jìn)入分派

654321

暫停

16

⑴進(jìn)程基本狀態(tài)

17

?執(zhí)行態(tài)（Running）：

進(jìn)程占有CPU,并在CPU上運(yùn)行

?就緒態(tài)（Ready）：

一個(gè)進(jìn)程已經(jīng)具備運(yùn)行條件，但由于無CPU暫時(shí)不能

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

?阻塞（等待）態(tài)（Blocked）：

指進(jìn)程因等待某種事件的發(fā)生而暫時(shí)不能運(yùn)行的狀態(tài)

18

阻塞隊(duì)列

排隊(duì)圖

19

進(jìn)程的狀態(tài)及其轉(zhuǎn)換

20

進(jìn)程狀態(tài)轉(zhuǎn)換：

在進(jìn)程運(yùn)行過程中，由于進(jìn)程自身進(jìn)展情況及

外界環(huán)境的變化，這三種基本狀態(tài)可以依據(jù)一定

的條件相互轉(zhuǎn)換

①就緒一運(yùn)行----------------------------

②運(yùn)行一就緒

③運(yùn)行一阻塞

④阻塞一就緒

21

進(jìn)程轉(zhuǎn)換

?就緒--〉運(yùn)行

-調(diào)度程序選擇一個(gè)新的進(jìn)程運(yùn)行.

?運(yùn)行一＞就緒

I-運(yùn)行進(jìn)程用完了時(shí)間片

-運(yùn)行進(jìn)程被中斷，因?yàn)橐桓邇?yōu)先級(jí)進(jìn)程處于

就緒狀態(tài)

22

進(jìn)程轉(zhuǎn)換

?運(yùn)行--〉阻塞

-當(dāng)一進(jìn)程必須等待時(shí)

?os尚未完成服務(wù)

?對(duì)一資源的訪問尚不能進(jìn)行

?初始化I/O且必須等待結(jié)果

-等待某一進(jìn)程提供輸入

?阻塞--〉就緒

-當(dāng)所等待的事件發(fā)生時(shí)

23

進(jìn)程的狀態(tài)轉(zhuǎn)換

分派程序■□□

運(yùn)行就緒阻塞

24

(2)進(jìn)程掛起

?進(jìn)程掛起功能

?進(jìn)程掛起的原因

?進(jìn)程狀態(tài)轉(zhuǎn)換?

?掛起進(jìn)程的特征

25

進(jìn)程掛起功能

將主存中某個(gè)進(jìn)程移到外存中，并釋放它

所占的主存空間

26

進(jìn)程掛起的原因

?終端用戶的請(qǐng)求

-父進(jìn)程請(qǐng)求

?負(fù)荷調(diào)節(jié)的需要

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

27

事件發(fā)生

進(jìn)程狀態(tài)轉(zhuǎn)換

28

具有掛起進(jìn)程功能的系統(tǒng)中的進(jìn)程狀態(tài)

?靜止就緒態(tài)：進(jìn)程具備運(yùn)行條件但目前

在輔存中，只有當(dāng)它被對(duì)換到主存后才

能被調(diào)度執(zhí)行

?靜止阻塞態(tài)：進(jìn)程正在等待某一個(gè)事件

且在輔存中

29

掛起進(jìn)程的特征

?不能立即執(zhí)行

?與是否阻塞無關(guān)

?由代理執(zhí)行

?只能由代理顯式激活

30

(3)創(chuàng)建狀態(tài)與終止?fàn)顟B(tài)

?創(chuàng)建狀態(tài)

-OS已完成為創(chuàng)建一進(jìn)程所必要的工作

-但還沒有允許執(zhí)行該進(jìn)程

?終止?fàn)顟B(tài)

-中止后進(jìn)程移入該狀態(tài)

-它不再有執(zhí)行資格

-表格和其它信息暫時(shí)由輔助程序保留

31

五、進(jìn)程控制塊

?進(jìn)程控制塊的作用

?進(jìn)程控制塊中的信息

?進(jìn)程控制塊的組織方式

32

1、進(jìn)程控制塊的作用

?操作系統(tǒng)根據(jù)進(jìn)程控制塊來對(duì)并發(fā)執(zhí)行

的進(jìn)程進(jìn)行控制和管理

33

進(jìn)程映像

用戶程序

用戶數(shù)據(jù)程序數(shù)據(jù)，用戶棧

系統(tǒng)棧參數(shù)/過程調(diào)用地址/系統(tǒng)調(diào)用地址

PCBOS控制進(jìn)程所需數(shù)據(jù)

PCB-processcontrolblock進(jìn)程控制塊

34

2、進(jìn)程控制塊中的信息

?進(jìn)程標(biāo)識(shí)符

?處理器狀態(tài)

?進(jìn)程調(diào)度信息

?進(jìn)程控制信息

35

進(jìn)程標(biāo)識(shí)信息：

-本進(jìn)程的標(biāo)識(shí)ID

?-建立本進(jìn)程的父進(jìn)程的標(biāo)識(shí)ID

-用戶標(biāo)識(shí)

36

處理器狀態(tài)信息：

-用戶使用的寄存器

--控制和狀態(tài)寄存器

-堆棧指針

37

進(jìn)程調(diào)度信息

?進(jìn)程狀態(tài)

?進(jìn)程優(yōu)先級(jí)

?進(jìn)程調(diào)度所需的其它信息

?事件

38

進(jìn)程控制信息：

-進(jìn)程在有關(guān)隊(duì)列中的鏈結(jié)指針

一-進(jìn)程間的通信信息

■-主存使用信息_

-進(jìn)程使用的其他資源信息

-進(jìn)程得到有關(guān)服務(wù)的優(yōu)先級(jí)

39

3、PCB的組織方法

?鏈接方式

?索引方式

40

鏈接方式

PCB14

PCB23

PCB30

PCB48

PCB5

PCB67

PCB79

PCB80一—

PCB91*

*—1

?

*n

41

索引方式

42

2.2進(jìn)程控制

?概念

?主要進(jìn)程控制原語

43

1、進(jìn)程控制的概念

職責(zé):對(duì)系統(tǒng)中所有進(jìn)程實(shí)施有效的

管理，它是處理機(jī)管理的一部分

任務(wù):創(chuàng)建進(jìn)程，撤消進(jìn)程，實(shí)現(xiàn)進(jìn)程間

狀態(tài)轉(zhuǎn)換

?進(jìn)程控制由內(nèi)核完成。內(nèi)核由原語實(shí)現(xiàn)

?原語：由若干條機(jī)器指令構(gòu)成，用以完成

特定功能的一段程序。

?原語操作具有不可分割性。44

2、主要進(jìn)程控制原語

創(chuàng)建進(jìn)程、終止進(jìn)程

掛起進(jìn)程、激活進(jìn)程

阻塞進(jìn)程、喚醒進(jìn)程

調(diào)度進(jìn)程

45

?進(jìn)程創(chuàng)建與終止

?當(dāng)子進(jìn)程創(chuàng)建時(shí)子進(jìn)程繼承父進(jìn)程所擁有的資源；當(dāng)子進(jìn)程終

止時(shí)將從父進(jìn)程那里繼承的資源歸還給父進(jìn)程。

46

為進(jìn)程的程序代碼、(1)將系統(tǒng)

數(shù)據(jù)用戶棧分配內(nèi)存分配的進(jìn)程

進(jìn)程創(chuàng)建過程ID、父進(jìn)程

空間。ID寫入PCB。

(2)將程序

計(jì)數(shù)器指向

創(chuàng)建進(jìn)程請(qǐng)求為進(jìn)程分配資源程序的入口

地址、棧指

針指向棧頂。

OS(3)設(shè)置進(jìn)

程狀態(tài)、優(yōu)

先級(jí)等。

調(diào)用創(chuàng)建進(jìn)程原語

Create)

將進(jìn)程放進(jìn)就緒隊(duì)列

申請(qǐng)PCB、

分配進(jìn)程ID

為新進(jìn)程分配一個(gè)唯一

的進(jìn)程ID,并申請(qǐng)一個(gè)

47

空白的PCB。

進(jìn)程的終止過程

引發(fā)進(jìn)程的二大類：‘冬止執(zhí)

終止事件

1、正常結(jié)束;

2、異常結(jié)束;

3、系統(tǒng)干預(yù);『所有的子

調(diào)用進(jìn)程終止原語

Destroy。

將進(jìn)程擁有的資源歸還給

父講程

從PCB集中檢索出

該進(jìn)程的PCB

把對(duì)應(yīng)的PCB設(shè)成空

讀出進(jìn)程的狀態(tài)

48

導(dǎo)致進(jìn)程終止的原因

?正常結(jié)束?系統(tǒng)干預(yù)

?異常結(jié)束-父進(jìn)程請(qǐng)求

?無內(nèi)存

?外界干預(yù)?父進(jìn)程終止

?越界

?正常結(jié)束?保護(hù)錯(cuò)誤

?超時(shí)?算術(shù)錯(cuò)誤

?系統(tǒng)干涉?I/O失敗

?無效指令

?特權(quán)指令

?數(shù)據(jù)誤用

49

。進(jìn)程的喚醒過程

明一.±如完成、期望

所等待的事件出現(xiàn)LI/O

------------------------的數(shù)據(jù)到達(dá)、有新

一I的任務(wù)要執(zhí)行等等。

調(diào)用喚醒原語

WakeupO

從等待隊(duì)列移出

I

在PCB中把把進(jìn)程插入到

等待—就緒就緒隊(duì)列

51

Q進(jìn)程的掛起過程

。進(jìn)程的激活過程

入到內(nèi)存

置成等待

Q進(jìn)程的調(diào)度過程

2.3進(jìn)程同步

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

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

?信號(hào)量的應(yīng)用

?管程機(jī)制

55

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

?進(jìn)程異步性導(dǎo)致的問題

?進(jìn)程間的相互作用

?臨界資源與臨界區(qū)

?同步機(jī)制應(yīng)遵循的規(guī)則

56

1、進(jìn)程異步性導(dǎo)致的問題

進(jìn)程的相對(duì)執(zhí)行速度不可預(yù)測(cè)

?難以定位程序錯(cuò)誤

57

舉例：回顯字符的Echo過程

Voidecho()

(

chin=getchar();

Chout=chin;

Putchar(chout);

58

Processp2

Processpl

chin=getchar();chin=getchar();

Chout=chin;

Putchar(chout);

Chout=chin;

Putchar(chout);

59

2、兩種形式的制約關(guān)系

?間接相互制約關(guān)系（互斥）

-進(jìn)程之間并不協(xié)同工作，彼此因相互爭(zhēng)奪

資源而產(chǎn)生的競(jìng)爭(zhēng)制約關(guān)系

?直接相互制約關(guān)系（同步）

-進(jìn)程之間協(xié)同工作。各進(jìn)程按一定的速度

執(zhí)行

60

3、臨界資源與臨界區(qū)

?臨界資源：一次僅能為一個(gè)進(jìn)程使用的

資源。

硬件資源：輸入機(jī)，打印機(jī)。--------

軟件資源：變量，隊(duì)列，表格。

?臨界區(qū)：進(jìn)程中訪問臨界資源的代碼段。

61

Pl

p2

—a:=a+1

互斥互斥

print(a)print(a)

P3Ifa<0

then

互斥a:=a+1

else

a:=a-1

4、同步機(jī)制應(yīng)遵循的原則

?空閑讓進(jìn)

?忙則等待

?有限等待

?讓權(quán)等待

63

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

信號(hào)量概念

信號(hào)量的實(shí)現(xiàn)

64

1、信號(hào)量的概念

?整型信號(hào)量：表示資源的物理實(shí)體，是一

個(gè)與隊(duì)列有關(guān)的整型變量，除對(duì)其初始化

外，其值僅能由wait和signal兩種不可中斷

的操作來改變。

?對(duì)信號(hào)量S的操作：wait與signal。通常表

示為wait⑸,signa](s).

65

?記錄型信號(hào)量

types=record

value:integer;

■L:pointertoPCB;指向等待隊(duì)列的指針

end

66

2、信號(hào)量的實(shí)現(xiàn)

?阻塞等待方式

?忙等待方式

67

?對(duì)信號(hào)量的wait操作和signa臊作由原語

實(shí)現(xiàn)，保證一旦對(duì)信號(hào)量的操作開始，

其它進(jìn)程不允許訪問該信號(hào)量。

68

阻塞等待方式

采用記錄型信號(hào)量

WAIT(S)SIGNAL(S)

S=S4S=S+1

判斷s

s<=o

阻塞該進(jìn)程

進(jìn)程繼續(xù)喚醒等待隊(duì)列

進(jìn)程

將進(jìn)程插入S的等待中的一個(gè)進(jìn)程,

隊(duì)列L中，重新調(diào)度繼續(xù)重新調(diào)度

69

忙等待方式

采用整型信號(hào)量

WAIT(S)

Y

S<0

N

S—S-l

SIGNAL(S)

s<-s+i

70

忙等待方式和阻塞等待方式的差別

?忙等待方式不會(huì)出現(xiàn)負(fù)值。

?阻塞等待方式適用于單處理機(jī)方式。

?忙等待方式適用于多處理機(jī)方式。

71

關(guān)于信號(hào)量的討論

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

S>0表示有S個(gè)資源可用

s=o表示無資源可用

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

wait(S):表示申請(qǐng)一個(gè)資源

signal(S)表示釋放一個(gè)資源。

信號(hào)量的初值應(yīng)該大于等于0

?對(duì)信號(hào)量的wait操作和signa臊作的要求

wait和signal操作必須成對(duì)出現(xiàn)

72

三、信號(hào)量應(yīng)用

1、用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥

2、用信號(hào)量實(shí)現(xiàn)進(jìn)程同步

73

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

設(shè)信號(hào)量S初值=1

A、B、C、D分別為四個(gè)進(jìn)程

ABC進(jìn)程中包含：wait(s)

D進(jìn)程中包含：signal(s)

就緒隊(duì)列CDBA

74

S=1

執(zhí)行A

75

執(zhí)行c

C

S=-1BA

執(zhí)行AB

BAC->s=-3-

76

1、用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥

?設(shè)置信號(hào)量，賦初值1,表示臨界資源未

被使用。

?進(jìn)程描述

77

例1設(shè)進(jìn)程P,Q共享一臺(tái)打印機(jī)，打印機(jī)任何時(shí)

刻只能被一個(gè)進(jìn)程使用，而不能同時(shí)使用。試用

信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程互斥使用打印機(jī)。

定義信號(hào)量S：表示打印機(jī)數(shù)目，初值為1；

進(jìn)程P:

wait(s);

使用打印機(jī)

signal(s);

78

n個(gè)進(jìn)程Pl,P2,…，Pn共享m臺(tái)打印機(jī)

79

定義信號(hào)量S：表示打印機(jī)數(shù)目，初值為m；

進(jìn)程描述

wait(s);

使用打印機(jī)

signal(s);

80

信號(hào)量S取值范圍:

最大值：m

最小值：m-n

81

Pl

p2

—a:=a+1

互斥互斥

print(a)print(a)

P3Ifa<0

then

互斥a:=a+1

else

a:=a-1

2、用信號(hào)量實(shí)現(xiàn)進(jìn)程同步

例1：進(jìn)程Pl、P2

P1

P2

83

定義信號(hào)量

S,表示Pl是否已執(zhí)行，初值為0

84

進(jìn)程描述

PlP2

Doworkwait(S)

Signal(S)Dowork

85

例2：進(jìn)程Pl、P2共享單緩沖區(qū)

Pl：計(jì)算數(shù)據(jù)，將結(jié)果寫入緩沖區(qū)

P2：從緩沖區(qū)讀出數(shù)據(jù)，并打印

同步關(guān)系：P1-P2-P1-P2

定義信號(hào)量

進(jìn)程描述

86

定義信號(hào)量

SL表示Pl是否將計(jì)算結(jié)果寫入緩沖區(qū)，初值為0

S2,表示緩沖區(qū)中是否為空，初值為1

87

進(jìn)程描述

PlP2

Wait(S2)Wait(SI)

DoworkDowork

Signal(SI)Signal(S2)

88

有父母子女四人圍坐一起吃水果，父親不

斷削蘋果往盆中放，母親不斷削梨往盆中

放，女兒則從盆中取蘋果吃，兒子則從盆

中取梨吃，假如盆中最多只能放N只水果,

試用信號(hào)量機(jī)制協(xié)調(diào)他們的關(guān)系。

89

父親母親女兒兒子

削蘋果削梨吃蘋果吃梨

90

S:盆中的空位數(shù)；

S1:盆中的蘋果數(shù);

S2:盆中的梨數(shù)；

91

父親母親女兒兒子

wait(s)wait(s)wait(sl)wait(s2)

削蘋果削梨吃蘋果吃梨

signal(sl)signal(s2)signal(s)signal(s)

92

四、管程機(jī)制

-管程的提出

-管程的定義

?用管程實(shí)現(xiàn)同步

93

1、管程的提出

?信號(hào)量機(jī)制的缺點(diǎn)

-易讀性差

-不利于修改和維護(hù)

-正確性難以保證

94

2、管程的定義

指關(guān)于共享資源的數(shù)據(jù)及在其上操作的一組

過程（或共享數(shù)據(jù)結(jié)構(gòu)及其規(guī)定的所有操作）

管程是管理進(jìn)程間同步的機(jī)制，它保證進(jìn)

程互斥地訪問共享變量，并且提供了一個(gè)

方便的阻塞和喚醒進(jìn)程的機(jī)構(gòu)。

進(jìn)程在需要的時(shí)候可以調(diào)用管程中的過程

95

管程的特點(diǎn)

管程是由若干過程、局部數(shù)據(jù)、初始化序

列組成的軟件模塊

?局部數(shù)據(jù)變量只能被管程的過程訪問

?一個(gè)進(jìn)程通過調(diào)用某過程進(jìn)入管程

?只有一個(gè)進(jìn)程能夠進(jìn)入，其他進(jìn)程被掛起一

互斥一

96

3、用管程實(shí)現(xiàn)同步

管程中支持同步的組成部分：

?局限于管程并僅能從管程內(nèi)進(jìn)行訪問的

若干條件變量(Condition)

?在條件變量上進(jìn)行操作的兩個(gè)函數(shù)過程

Cwait(C)和Csignal(C)

97

利用條件變量實(shí)現(xiàn)同步

?Cwait(c)

-掛起當(dāng)前進(jìn)程

-管程變成可用狀態(tài)

?Csignal(c)

-執(zhí)行等待隊(duì)列中的頭個(gè)進(jìn)程

-隊(duì)列空則什么都不做

98

管程的結(jié)構(gòu)進(jìn)入進(jìn)程隊(duì)列

XZ

局部數(shù)據(jù)

條件變量

過程1

■

過程k

初始化代碼

管程等待區(qū)管程出99

Monitorboundedbuffer;

Charbufferfn];

Intnextin,nextout;

Intcount;

Intnotfull,notempty;Nextin=0;nextout=0;count=0;

Voidappend(charx)Voidtake(charx)

{ifcount==ncwait(notfull);{ifcount==0cwait(notempty);

Buffer[nextin]=x;x=Bufferfnextout];

Nextin=(nextin+1)%n;Nextout=(nextout+1)%n;

Count++;Count-;

Csignal(notempty);Csignal(notfull);

1UU

2.4經(jīng)典進(jìn)程的同步問題

?生產(chǎn)者一消費(fèi)者問題

?讀者一寫者問題

?哲學(xué)家進(jìn)餐問題

101

(1)生產(chǎn)者一消費(fèi)者問題

由多個(gè)緩沖區(qū)構(gòu)成的一個(gè)緩沖存儲(chǔ)器，

每個(gè)緩沖區(qū)可存放一個(gè)數(shù)據(jù)項(xiàng)。

?生產(chǎn)者：生產(chǎn)數(shù)據(jù)并將其放入緩沖區(qū)中的進(jìn)程。

?消費(fèi)者：消耗并處理緩沖區(qū)中數(shù)據(jù)的進(jìn)程。

要求進(jìn)程互斥地使用緩沖區(qū)

102

生產(chǎn)者進(jìn)程消費(fèi)者進(jìn)程

produceQ;take();

appendQ;consumeQ;

103

定義信號(hào)量

n=0;表示滿緩沖區(qū)的個(gè)數(shù)e=sob;表示空緩沖區(qū)的個(gè)數(shù)

生產(chǎn)者進(jìn)程消費(fèi)者進(jìn)程

produceQ;wait(n);

wait(e);

take();

append();

Signal(e);

signal(n);consumeQ;

104

定義信號(hào)量

n=0;表示滿緩沖區(qū)的個(gè)數(shù)e=sob;表示空緩沖區(qū)的個(gè)數(shù)

s=1;表示緩沖區(qū)是否可用

生產(chǎn)者進(jìn)程消費(fèi)者進(jìn)程

produceQ;wait(n);

wait(e);wait(s);

wait(s);takeQ;

append();signal(s);

signal(s);Signal(e);

consumeQ;

signal(n);105

{{XU)_EU6_S

{xoEnsuoQosnpcud)g_EU6-s

u&SEd)

()U_EEpo>①

x)puddE

gEEM

{3①Ensuoo

-(0)_PU6-Sg七EM

XS)_EU6-S(OQOnpcud)

①

0M--LIM)

通

一()①(Konpcudpo>

g七EM

gEEM)(qosHe①」olldEEQS

(Hs9-0lldBE8

S

9ml9--LIM)OHU①

ooEnsuoopo>9-0lldBES

二

g但半HqoswSus

Voidappend(charx)Voidtake(charx)

{ifcount==ncwait(notfull);{ifcount==0cwait(notempty);

Buffer[nextin]=x;x=Bufferfnextout];

Nextin=(nextin+1)%n;Nextout=(nextout+1)%n;

Count++;Count-;

Csignal(notempty);Csignal(notfull);

1U/

108

(2)讀者一寫者問題

一個(gè)數(shù)據(jù)集為若干并發(fā)進(jìn)程共享。

讀者：要求讀取數(shù)據(jù)

寫者：要求修改數(shù)據(jù)

?概念：保證一個(gè)寫者必須與其它進(jìn)程互

斥地訪問數(shù)據(jù)。

讀者寫者

110

定義信號(hào)量

Wsem=l：表示數(shù)據(jù)集是否可用

S=l：互斥使用全局變量readcoimt

in

(3)哲學(xué)家進(jìn)餐問題

有五個(gè)哲學(xué)家，他們的生活方式是交替地

進(jìn)行思考和進(jìn)餐，哲學(xué)家們共用一張圓桌,

周圍放有五張椅子，每人坐一張，在圓桌

上有五碗面和五個(gè)叉子。當(dāng)哲學(xué)家思考時(shí),

他不與同事交談。饑餓時(shí)，便試圖取用左

邊和右邊的叉子，他可能一個(gè)也

拿不到，只有在他拿到兩個(gè)叉子^^^^

時(shí)，方能就餐，吃完后，放下叉

又繼續(xù)思考。

進(jìn)程描述（第i個(gè)哲學(xué)家的活動(dòng)）

think()

eat()

114

信號(hào)量設(shè)置

為每個(gè)叉子設(shè)置信號(hào)量:

Semaphorefork[5]={1};

信號(hào)量的初值均為1。

115

解法1

Semaphorefork[5]={1};Voidmain()

IntI;{parbegin

Voidphilosopher(inti)(philosopher(O),

(philosopher(l),

{whiletrue

(philosopher(2),

{thinkQ;(philosopher(3),

Wait(fork[i]);(philosopher(4))

Wait(fork[(i+1)mod5]);

Eat();

signal(fork[(i+1)mod

5])；

signal(fork[i]);

116

改進(jìn)

Semaphorefork[5]={1};Voidmain()

Sem叩horeroom={4};{parbegin

Inti;(philosopher(O),

Voidphilosopher(inti)(philosopher(l),

{whiletrue(philosopher(2),

{thinkQ;(philosopher(3),

Wait(room);(philosopher(4))

Wait(fork[i]);

Wait(fork[(i+1)mod5]);

Eat();

signal(fork[(i+1)mod5]);

signal(fork[i]);

signal(room);

})

117

2.5進(jìn)程通信

?進(jìn)程通信的類型

?消息傳遞通信的實(shí)現(xiàn)方法

?消息緩沖隊(duì)列通信機(jī)制

118

一、進(jìn)程通信的類型

?:?共享存儲(chǔ)器系統(tǒng)

＞基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式

＞基于共享存儲(chǔ)區(qū)的通信方式

。消息傳遞系統(tǒng)

＞直接通信

＞間接通信

管道通信

基于共享存儲(chǔ)區(qū)的通信方式

在內(nèi)存劃出一塊公共的存儲(chǔ)區(qū)域，諸進(jìn)程可通過

對(duì)共享存儲(chǔ)區(qū)的讀或?qū)懖僮鱽韺?shí)現(xiàn)通信

120

消息傳遞系統(tǒng)

進(jìn)程之間的數(shù)據(jù)交換以消息為單位，操作系統(tǒng)提

供一組高級(jí)通信原語實(shí)現(xiàn)進(jìn)程間通信

管道通信

管道是連接讀寫進(jìn)程的一個(gè)特殊的共享文件。寫

進(jìn)程將數(shù)據(jù)從管道的一端送入管道，讀進(jìn)程則從

管道的另一端讀取數(shù)據(jù)。

寫進(jìn)程I\共享文件\讀進(jìn)程

122

二、消息傳遞通信的實(shí)現(xiàn)方法

1.直接通信方式

發(fā)送進(jìn)程發(fā)消息時(shí)要指定接收進(jìn)程的名字

Send（接收者，消息）

?-4旨定接收進(jìn)程

receive（發(fā)送者，消息）

I-指定發(fā)送進(jìn)程

一?不指定發(fā)送進(jìn)程，返回參數(shù)123

2.間接通信方式

?發(fā)送進(jìn)程發(fā)消息時(shí)指定一個(gè)中間媒介，即信箱。

進(jìn)程間通過信箱實(shí)現(xiàn)通信

發(fā)送原語：send(MB,Message)

接收原語：receive(MB,Message)

124

三、消息緩沖隊(duì)列通信機(jī)制

1.消息緩沖隊(duì)列通信機(jī)制中的數(shù)據(jù)結(jié)構(gòu)

消息緩沖區(qū)PCB中有關(guān)通信的數(shù)據(jù)項(xiàng)

typetype

messageprocesscontrolblock=

buffer=recordrecord

sender;發(fā)送進(jìn)程標(biāo)識(shí)符

size;消息長(zhǎng)度mq;消息隊(duì)列隊(duì)首指針

text;消息正文mutex;消息隊(duì)列互斥信號(hào)量

next;下一個(gè)消息緩沖區(qū)指針sm;消息隊(duì)列資源信號(hào)量

end

end

消息的格式

。消息類型

目標(biāo)ID

消息頭,源ID

消息長(zhǎng)度

〔控制信息

消息內(nèi)容

消息體

126

2.發(fā)送原語

proceduresend(receiver,a)

begin

getbuf(a.size,i)；根據(jù)a.size申請(qǐng)緩沖區(qū)；

i.sender:：=a.sender;將發(fā)送區(qū)a中的信息復(fù)制到消息緩沖區(qū)

i.size:=a.size;

i.text:=a.text;

i.next:=0;

getid(PCBset,receiver.]);獲得接收進(jìn)程內(nèi)部標(biāo)識(shí)符；

wait(j.mutex);

inserta.mq,i);將消息緩沖區(qū)插入消息隊(duì)列；

signal(j.mutex);

signal(j.sm);

end

127

進(jìn)程A進(jìn)程B

send(B,a)?receive(b)-

第一消息緩沖區(qū)

sendenAsender:A

size:5size:5

text:Hellotext:Hello

消息緩沖通信

3.接收原語

procedurereceive(b)

begin

j:=internalname;j為接收進(jìn)程內(nèi)部的標(biāo)識(shí)符；

wait(j.sm);

wait(j.mutex);

remove(j.mq,i);將消息隊(duì)列中第一個(gè)消息移出；

signal(j.mutex);

b.sender：=i.sender;將消息緩沖區(qū)i的信息復(fù)制到接收區(qū)b

b.size:=i.size;

b.text:=i.text;

end

129

使用消息傳遞機(jī)制實(shí)現(xiàn)互斥

Constintn二進(jìn)程數(shù);Voidmain()

Voidp(inti){create_mailbox(mutex);

{messagemsg;Send(mutex,null);

Parbegin(p(1)...p(n));}

Whiletrue5

{receivefmutex^sg);

臨界區(qū)；

Send(mutex,msg);}}

130

使用消息解決生產(chǎn)者/消費(fèi)者問題

Constintcapadty=buf容量[voidconsumerQ

Constintnull二空消息；

Im,f{messagecmsg;

'Whiletrue

_________________________{receive(mayconsume,cmsg);

Voidproducer。Consume(cmsg);

{messagepmsg;Send(mayproduce,null);}}

Whiletrue_____

{receive(mayproduce,pmsg);

Pmsg=produce();

Send(mayconsume,pmsg);}}

131

VoidmainQ

{create_mailbox(mayproduce);

Create_mailbox(mayconsume);

For(inti=1;i<=capacity;i++)

Send(mayproduce,null);

Parbegin(producer,consumer);}

132

133

2.6線程

線程的基本概念

線程間的同步和通信

線程的實(shí)現(xiàn)方式

134

?、線程的基本概念

-線程的引入

-線程的定義及特征

?線程的狀態(tài)和管理

135

1、線程的引入

進(jìn)程的兩個(gè)基本屬性

?資源的擁有者

?調(diào)度單元

以上兩個(gè)屬性構(gòu)成進(jìn)程并發(fā)執(zhí)行的基礎(chǔ)

136

系統(tǒng)必須完成的操作

?創(chuàng)建進(jìn)程缺點(diǎn):

時(shí)高空間開銷大，

?撤消進(jìn)程

限制并發(fā)度的提高

?進(jìn)程切換

線程的引入正是為了簡(jiǎn)化進(jìn)程間的通信,

以小的開銷來提高進(jìn)程內(nèi)的并發(fā)程度

137

2、線程的定義及特征

線程:進(jìn)程內(nèi)一個(gè)相對(duì)獨(dú)立的、可調(diào)度的執(zhí)行單元

線程具有以下性質(zhì)：

-線程是進(jìn)程內(nèi)的一個(gè)相對(duì)獨(dú)立的可執(zhí)行單元。

-線程是操作系統(tǒng)中的基本調(diào)度單元。

?一個(gè)進(jìn)程中至少應(yīng)有一個(gè)線程。

-線程并不擁有資源，而是共享和使用包含它的進(jìn)

程所擁有的所有資源。

?線程在需要時(shí)也可創(chuàng)建其他線程。

138

引入線程的好處:

?創(chuàng)建一個(gè)新線程花費(fèi)時(shí)間少

?兩個(gè)線程的切換花費(fèi)時(shí)間少

?因?yàn)橥贿M(jìn)程內(nèi)的線程共享內(nèi)存和文件,

因此它們之間相互通信無須調(diào)用內(nèi)核

?適合多處理機(jī)系統(tǒng)

139

3、線程的狀態(tài)和管理

?線程的狀態(tài)

?線程的描述

?線程的管理