It计算机课件 计算机操作系统进程

徐伶伶

Email:xll0903@163.com

qq:5705341

第三章进程管理2

■3.1进程的概念

■3.2进程的描述

■3.3进程状态及其转换

■3.4进程控制

■3.5进程互斥

■3.6进程同步

■3.7进程通信

■3.8死锁问题

■3.9线程的概念

-3.10线程分类与执行

《爹中网涔在以装M

3.1进程的概念

■1.程序的并发执行

■2.进程的定义

《爹中网涔在以装M

4

■现代操作系统的特点:

令程序的并发性

令系统资源共享

令用户操作的随机性

《爹中网涔在以装M

5

■问题：操作系统在多用户随机使用的环境下进行资源分配、

资源共享和控制程序并发执行的基本单位是什么？

■进程刚好是这样一个基本单位。

《爹中网涔在以装M

1.程序的并发执行6

■程序的执行有两种方式：顺序执行和并发执行。

令顺序执行是单道批处理系统的执行方式，也用于简单的单

片机系统；

RepeatIR-M[pc]

pc-pc+1

<Execute(InstructioninIR)>

UntilCPUhalt

令现在的操作系统多为并发执行，具有许多新的特征。引入

并发执行的目的是为了提高资源利用率。

《爹中网涔在灾盛th

令顺序性：按照程序结构所指定的次序（可能有分支或循环

）

令封闭性：独占全部资源，计算机的状态只由于该程序的控

制逻辑所决定

令可再现性：初始条件相同则结果相同。

《爹中网涔在以装M

令独立性：在多道环境下执行的每道程序逻辑上是独立的；

令随机性：多道环境下，程序和数据的输入与执行的开始时

间都是随机的；

令资源共享：多道程序共享硬件和软件资源。硬件资源包括

CPU、I/O设备、存储器等；软件资源包括例程、可共享的

数据等。

《爹中网涔在灾盛th

9

■一组在逻辑上互相独立的程序或程序段在执

行过程中，其执行时间在客观上互相重叠，即一个程序段的执

行尚未结束，另一个程序段的执行已经开始的这种执行方式。

并发执行区

《爹中网涔在以装M

10

■程序并发执行的描述

Pi(i=l,2,3,・・・，n)表示n个语句(程序段)，这n个语

句用cobegin和coend括起来表年这n个语句是可以并发执行

的oco是concurr6nt的头两个字符。

■这是Dijkstra提出的。

《爹中网涔在以装M

12

令间断（异步）性："走走停停"，一个程序可能走到中途停下

来，失去原有的时序关系；

令失去封闭性：共享资源，受其他程序的控制逻辑的影响。

如：一个程序写到存储器中的数据可能被另一个程序修改

,失去原有的不变特征。

令失去可再现性：失去封闭性->失去可再现性；外界环境

在程序的两次执行期间发生变化，失去原有的可重复特征

《爹中网涔在灾盛th

并发执行的条件：达到封闭性和可再现性13

■并发执行失去封闭性的原因是共享资源的影响，去掉这种影

口而就行了。1966年，由Bernstein给出并发执行的条件。(

这里没有考虑执行速度的影响。)

・程序P(i)针对共享变量的读集和写集R(i)和W(i)

■条件：任意两个程序P(i)和P(j),有：

令R(i)cW(j)=(D;

令W(i)cR(j)=(D;

令W(i)cW(j)=(D;

■前两条保证一个程序的两次读之间数据不变化；最后一条保

证写的结果不丢掉。

令

《爹中网涔在以装M

举例：栈的读、写程序段并发执行14

Procedurereladdr(blk)

begin

top-top+1

(top)-blk

endProceduregetaddr(top)

begin

localr

r-(top)

top—top-1

return(r)

end

寸风法汗丸也人

读、写并发可能导致错误：

-geladdr()

Topf■取数据失败

Topfa(Reladdr。执aa

行语句：

bbb

top-top+1

e后)e

fff

(a)(b)(c)

《爹中网涔在灾盛th

回顾16

■程序的执行有两种方式：顺序执行和并发执行。

令R(i)cW(j)=(D;

令W(i)cR(j)=(D;

令W⑴cW(j)=(D;

中网涔注以依4

2.进程的定义17

■在多道程序设计的环境下，为了描述程序在计算机系统内的

执行情况，必须引入新的概念--进程。

■进程的概念来自于麻省理工的MULTICS、IBM的TSS/360,

在IBM的OS/360/370家统中也曾叫过任务(task)。

《爹中网涔在灾盛th

18

■进程是可以并发执行的计算部分(Madnick,Donovan)

■进程是一个独立的可以调度的活动(Cohen,Jofferson)

■进程(有时称为任务)是一个程序与其数据一道通过处理机

的执行所发生而活动。(Alan.C.Shaw)

■进程是执行中的程序。(KenThompsonandDennis

Ritchie)

■行为的一个规则叫做程序，程序在处理机上执行时所发生的

法功衣为进程(Dijkstra)o

■教材上给出的进程的定义：

《爹中网涔在以装M

进程与程序的区别

■进程是动态的，程序是静态的：程序是有序代码的集合；进

程是程序的执行。程序可以祚为软件资料长期保存，而进程

是有生命周期的。

如果把程序比作菜谱，那么进程则是按照菜谱炒菜的

过程。

■进程具有并发特征，而程序没有：程序不反映执行过程，所

以不具有并发特征。

■进程是竞争系统资源的基本单位；

■进程与程序的对应关系：通过多次执行，一个程序可对应多

个进程；通过调用关系，一个进程可包括多个程序。

《爹中网涔在以装M

3.2进程的描述20

■1.进程控制块PCB

■2.进程上下文

■3.进程上下文切换

■4.进程空间

《爹中网涔在以装M

21

■进程的静态描述：

令进程控制块PCB：

进程控制块包含了进程的描述信息、控制信息及资源信息

,是进程动态特征的集中反映。

令有关程序段

描述进程所要完成的功能。

令数据结构集

进程执行时必不可少的工作区和操作对象。

《爹中网涔在灾盛th

1.进程控制块PCB22

进程控制块是由OS维护的用来记录进程相关信息的一块内存

O

■在创建一个进程时，OS首先创建其PCB,然后才能根据PCB中

的信息对进程实施有效的管理和控制。

■当一个进程完成其功能后，系统释放PCB,进程随之消亡。

《爹中网涔在灾盛th

进程控制块PCB的内容:23

令进程描述信息

令进程控制信息

令资源管理信息

令CPU现场保护结构

《爹中网涔在灾盛th

24

令进程名或进程标识符(processID),唯一，通常是一个整

数；

令用户标识符(userID);

令进程家族关系(processgroup)

《爹中网涔在以装M

25

令当前状态；（就绪态、执行态、等待态）

令优先级（priority）;

^占有CPU时间；

/进程优先级偏移；

/占据内存时间；

令代码执行入口地址、程序的外存地址；

令计时信息（进程占有和利用资源的有关情况）；

令进程间同步和通信；

《爹中网涔在灾盛th

26

资源占用信息：存储器的信息、I/O信息、文件系统信息等

令占用内存大小及其管理用数据结构指针；

令在复杂系统中，内存对换和覆盖用的有关信息；

令共享程序段大小及其起始地址；

令I/O设备号、要传送的数据长度、缓冲区地址和长度、与

设备相关的数据结构指针

令指向文件系统的指针及有关标识。

《爹中网涔在灾盛th

27

:寄存器值（通用、程序计数器PC、状态

PSW,地址包括栈指针）

《爹中网涔在灾盛th

28

PCB结构

name进程标识符

status进程当前状态

next当前队列指针

all-q-next总琏指针

start-addr执行程序开始地址

priority进程优先级

cpustatusCPU现场保护区

communication进程通信

information

process-family家族联系

own-resource占有资源清单

《爹中网涔在灾盛th

PCB小结29

■进程控制块PCB是系统感知进程存在的唯一实体。

■通过对PCB的操作，系统为有关进程分配资源从而使得有关

进程得以被调度执行；

■与进程有关的所有现场信息都保存在PCB中；

■进程执行结束后，OS通过释放PCB释放进程占有的资源。

PCB就象是我们的户口

《爹中网涔在灾盛th

回顾30

■程序的执行有两种方式：顺序执行和并发执行。

令R(i)cW(j)=(D;

令W(i)cR(j)=(D;

令W(i)cW(j)=(D;

■进程与程序的区别

■进程的静态描述：PCB、程序、数据集

中网涔注以依4

PCB的作用31

1）记录进程的有关信息（描述信息、控制信息等），是进

程动态特性的集中反映。

2）标志进程的存在，是进程在系统中的唯一标识。

3）通过对PCB的操作，系统为有关进程分配资源从而使得有

关进程得以被调度执行；

4）进程执行结束后，OS通过释放PCB释放进程占有的资源。

《爹中网涔在灾盛th

进程管理（PCB组织方式）32

■系统中有若干进程，为调度和管理个进程，将各进程的PCB

用适当的方式组织起乘，方便管理。

1）线性表方式：将所有的PCB不分状态组织在一个表中，

PCB表。

优点：方便、简单，适用于系统中进程数目不多的类型。

缺点：调度进程时要扫描整个表。

PCB1PCB2PCB3.......PCBn

《爹中网涔在灾盛th

进程管理（PCB组织方式）续33

2）索引方式：分别将具有不同状态的PCB组织成各自的PCB索

引表。素引表中存放PCB在PCB表中的地址。

内存固定单元设置三个指针，分别指示就绪索引表、等待索

引表、执行态PCB在PCB表中的地址。

《爹中网涔在灾盛th

进程管理（PCB组织方式）续34

3）链接方式：对于具有相同状态的进程的PCB,通过PCB中的

链接字构成一个队列。

就绪队列可按优先数排序，也可按先进先出排队（依据调度

原则）O

等待队列可有多个，对应不同的等待原因。如：等待I/O完成

PCBPCBPCB

《爹中网涔在灾盛th

2.进程上下文35

■进程上下文是对进程执行活动全过程的静态描述。

■进程上下文是个抽象的概念，它包含了每个进程执行过的、

执行时的以及等待执行的指令和数据，在指令寄存器、堆栈

、状态字寄存器等中的内容。

■进程上下文的构成：

令与进程有关的各种寄存器（如通用寄存器、程序计数器PC

、程序状态字PSW等）

令程序段经过编译后形成的机器指令代码集（正文段）

令数据集和各种堆栈值

令PCB结构

《爹中网涔在灾盛th

进程上下文的结构36

P

C

B

37

・用户级上下文：进程的用户地址空间（包括用户栈各层次）

,包括用户正文段、用户数据段和用户栈；

■寄存器级上下文：程序寄存器、处理机状态寄存器、栈指针

、通用寄存器的值；

■系统级上下文：

令静态部分（PCB结构和资源表格）

令动态部分：核心栈（核心过程的栈结构，不同进程在调用

相同核心过程时有不同核心栈）

《爹中网涔在灾盛th

4.进程空间38

■进程在执行时所拥有的地址空间称为进程空间；

■进程空间的大小只与处理机的位数有关；

■进程空间分为：用户空间和系统空间；

■用户程序在用户空间内执行，操作系统内核程序在系统空间

内执行;

■进程在用户空间的执行模式称为用户态，在系统空间的执行

模式称为系统态或核心态。

・用户态时不可直接访问受保护的OS代码；

■核心态时执行OS代码，可以访问全部进程空间。

《爹中网涔在以装M

3.3进程状态及其转换39

■1.进程状态

■2.进程状态转换

《爹中网涔在以装M

40

■一个进程的生命期可以划分为就绪状态、执行状态和等

待状态（又称为阻塞状态）；

《爹中网涔在以装M

回顾41

■进程定义

■进程与程序的区别

■进程的静态描述：PCB、程序、数据集

■进程状态

就绪状态、执行状态、等待状态

《爹中网涔在以装M

1.进程状态

■运行状态（Running）：占用处理机资源；处于此状态的进程

的数目小于等于CPU的数目。

令在没有其他进程可以执行时（如所有进程都在等待状态）

,通常会自动执行系统的idle进程（相当于空操作）。

■就绪状态（Ready）:进程已获得除处理机外的所需资源，等

待分配处理机资源；只要分配CPU就可执行。

令可以按多个优先级来划分队列，如：时间片用完-＞低优

,I/O完成-＞中优，页面调入完成-＞高优

■等待状态（Wait）:由于进程等待某种条件（如I/O操作或进

程同步），在条件满足之前无法继续执行。该事件发生前即

使初处理机分配给该进程，也无法运行。如：等待I/O操作

的完成。

《爹中网涔在灾盛th

43

■就绪状态又可分为：

令内存就绪状态

令外存就绪状态

■执行状态又可分为：

令用户态：进程的用户程序段在执行

令核心态：进程的系统程序段在执行

■也有把进程状态分为5个状态和9个状态的说法

中网涔注以依4

3.3进程控制45

■1.进程创建与撤销

■2.进程阻塞与唤醒

《爹中网涔在以装M

46

■进程控制：系统使用一些具有特定功能的程序段来创建

、撤消进程以及完成进程各状态间的转换，从而达到多

进程高效率并发执行和协调、实现资源共享的目的。

《爹中网涔在以装M

47

■原语：把系统态下执行的某些具有特定功能的程序段称为原

语。

■原语分为：

令指令级原语：在执行期间不允许中断；

令功能级原语：不允许并发执行。

用于进程控制的原语有：

《爹中网涔在灾盛th

1.进程创建与撤销

■进程的创建方式：

令由系统程序模块统一创建

由系统统一创建的进程之间的关系是平等的，它们

之间一般不存在资源继承关系。

令由父进程创建

在父进程与子进程之间存在隶属关系，且互相构成

树型结构的家族关系。属于某个家族的一个进程可以继承

其父进程所拥有的资源。

■无论以哪一种方式创建进程，在系统生成时，都必须由操作

系统创建一部分承担系统资源分配和管理工作的系统进程。

-无论是系统创建方式还是父进程创建方式，都必须调用创建

原语来实现。

《爹中网涔在以装M

50

■以下几种情况下进程被撤消：

令该进程已完成所要求的功能而正常终止;

令由于某种错误导致非正常终止；

令祖先进程要求撤消某个子进程。

《爹中网涔在以装M

撤消原语流图51

9中网法注/*M

2.进程的阻塞和唤醒52

■阻塞原语：圈进程由执行状态变为阻塞状态（等待状态）；

■唤醒原语：将进程由阻塞状态变为就绪状态。

・阻塞原语在一个进程期待某一事件（例如键盘输入数据、写

盘、其他进程发来的数据等）发生，但发生条件尚不具备时

,被该进程自己调用来阻塞自己。

《爹中网涔在以装M

阻塞原语唤醒原语53

9中网法注/*M

54

■当等待队列中的进程所等待的事件发生时，等待该事件的所

有进程都圈被唤醒。

■唤醒进程的两种方法：

令由系统进程唤醒

令由等待事件发生唤醒

《爹中网涔在以装M

回顾

56

■原语：把系统态下执行的某些具有特定功能的程序段称为原

语。

《爹中网涔在以装h

3.5进程互斥57

1.临界^区

■2.互斥的加锁实现

瞭3.信号量与P,V原语

■4.用P,V原语实现进程互斥

《爹中网涔在以装M

58

■资源共享引起并发进程的相互制约。

■多个进程在对硬件或软件（如外设、共享代码段、共享数据

结构）进行访问时（关键是进行写入或修改），必须互斥地

进行--有些共享资源可以同时访问，如只读数据。

《爹中网涔在以装M

多进程共享内存栈区示例59

////

系统区

进程

PaIIII

的程序

1111

--A

IIII

top进程Pb

的程序

////

栈s

《爹中网涔在灾盛th

共享栈区的两个并发进程必须互斥60

Proceduregetspace

begin

localg

g-stack[top]

top-top-1

end

Procedurerelease(ad)

begin

top-top+1

stack[top]-ad

end

《爹中网涔在灾盛th

61

•进程间资源访问冲突

令共享变量的修改冲突

令操作顺序冲突

■进程间的制约关系

令间接制约：进行竞争--独占分配到的部分或全部共享资

源，“互斥”

令直接制约：进行协作--等待来自其他进程的信息，“同

步”

《爹中网涔在以装M

共享变量的修改冲突62

一个飞机订票系统，两个终端，运行Tl、T2进

程

T1:T2:

Fbad(x);Read(x);

ifx>=1thenifx>=1then

x:=x-1;x:=x-1;

vrite(x);wite(x);

1.临卷^区63

■不允许多个并发进程交叉执行的一段程序称为临界区(

CriticalSectionorCriticalRegion);

■临界区是由属于不同并发进程的程序段共享公用数据或变量

而引起的；

■临界区不可能用增加硬件的方法来解决。因此，临界区也可

以被称为访问公用数据的那段程序。

《爹中网涔在灾盛th

64

■互斥：不允许两个以上的并发进程同时进入临界区称为互斥

O

■并发进程互斥执行必须满足：

＞不能假设各并发进程的相对执行速度；

»某个进程不在临界区时，它不能阻止其他进程进入临界区

»若干个并发进程申请进入临界区时，只能有一个进程进入

临乐区；

＞申请进入临界区的进程应在有限时间内得以进入临界区

《爹中网涔在灾盛th

65

■上述准则中，（1）（2）（3）是保证各并发进程享有平等的、独

立竞争资源的权利，且保证每一时刻最多只有一个进程在临

界区；（4）保证了并发进程不发生死锁。

■死锁，指多个进程互不相让，都得不到足够的资源，只好一

直处于等待状态；

■饥饿，指一个进程一直得不到资源（其他进程可能轮流占用

资源）。

《爹中网涔在灾盛th

2.互斥的加锁实现

■使用临界区加锁的方法可以实现并发进程互斥地访问临界区

当某个进程进入临界区之后，它修锁上临界区，直到

它退出临界区时为止。其他并发进程在申请进入临界区时，

首先测试该临界区是否是上锁的，如果该临界区已被锁住，

则该进程要等到该临界区开锁之后才有可能获得临界区。

《爹中网涔在灾盛th

67

■设临界区的类名为S,为了保证每一次临界区中只能有一个

程序段被执行，又设锁定位Key[S]oKey[S]表示该锁定位

属于类名为S的临界区，加锁后的临界区程序如下：

Lock(Key[S])

(临界区)

Unlock(Key[S])

Key[S]=0时表示临界区不可用，

Key[S]=1时表示临界区可用o

《爹中网涔在天盛th

68

■unlock(Key[S])可用语句：Key[S]-1

■下面的算法可以实现lock(Key[S])的功能:

Lock(x)=beginlocalv

repeat

v-x

unti1v=l

x—0

end

《爹中网涔在以装h

69

■上面的Lock算法存在的问题：

令1、不能保证当Key[S]=l时仅有一个进程进入临界区。

有些机器在硬件中设置了“测试与设置指令(test

andset)5,,从而保证读操作和写操作的不可分离。以解

决该问题

令2、循环测试锁定位将损耗较多的CPU时间，当进程很多时

,这种开销将无法忍受。

令3、可能会导致不公平：有些进程一直占有临界区而另一

些进程可能“饿死”。

《爹中网涔在灾盛th

3.信号量和P,V原语70

■下面两个进程Pa、Pb并发使用临界区时，如果Pa先使用临界

区,则Pb有可能被“饿死”：

Pa:Pb:

A:lock(key[S])B:lock(key[S])

<S><S>

unlock(key[S])unlock(key[S])

gotoAgotoB

《爹中网涔在以装机

回顾71

■进程互斥：

多个进程在对硬件或软件（如外设、共享代码段、共享

数据结构）进行访问时（关键是进行写入或修改），必须互

斥地迸行。

不允许多个并发进程交叉执行的一段程序，是由

属于不同并发进程的程序段共享公用数据或变量而引起的；

不可能用增加硬件的方法来解决。因此，临界区也可以被称

为访问公用数据的那段程序。

不允许两个以上的并发进程同时进入临界区。

《爹中网涔在灾盛th

72

3.互斥的加锁实现：锁定位key[s]

Lock(Key[S])rLock(x)=beginloca1v

repeat

v—x

（临界区）unti1v=l

x—0

、end

Unlock(Key[S])Key[S]-1

《爹中网涔在灾盛th

73

一个进程能否进入临界区是依靠进程自己调用lock过程

去测试相应的锁定位，这样，没有获得执行机会的进程就

无法进行判断，从而出现不公平现象。

解决办法：需要一个地位高于进程的管理者来解决公有资源

的使用问题。OS可从进程管理者的角度来处理互斥的问题，

信号量就是OS提供的管理公有资源的有效手段。

由管理员管理的公共机房

《爹中网涔在灾盛th

信号量74

■1965年，信号量及P、V原语由荷兰学者Dijkstra提出(所以

P、V分别是荷兰语的test(proberen)和

increment(verhogen)),是一种卓有成效的进程互斥和同

步的机制。

■通常，信号量sem大于等于零时，代表可供并发进程使用的

资源数，小于零时表示等待使用临界区的进程数。

《爹中网涔在以装M

75

■信号量的数值仅能由P,V原语操作改变，一次P原语操作使

信号量sem减1,而一次V原语操作将使信号量sem加1。

■当某个进程正在临界区内执行时，其他进程如果执行了P原

语操作，则该进程并不象调用lock时那样因进不了临界区而

返回到起点，等以后重新执行测试，而是在等待队列中等待

有其他进程做V原语操作释放资源后，进入临界区，这时P原

语的执行才真正结束。

■另外，当有好几个进程执行P原语未通过而进入待状态之后

,如果有某个进程作了V原语操作，则等待进程中的一个可

以进程临界区，其他进程必须等待。

《爹中网涔在灾盛th

P原语的实现78

P(sem):

begin

封锁中断；

lock(lockbit)

va1[sem]=val[sem]-1

ifval[sem]<0

保护当前进程CPU现场

当前进程状态置为“等待”

将当前进程插入信号sem的等待队列

转进程调度

fi

unlock(lockbit);开放中断

end

《爹中网涔在灾盛th

V原语的实现79

V(sem):

begin

封锁中断；

lock(lockbit)

va1[sem]=val[sem]+1

ifval[sem]<0

localk

从sem的等待队列中选一进程，其指针置为k

将k插入就绪队列

进程状态置为“就绪”

fi

unlock(lockbit);开放中断

end

寸帽洛汗丸也人

4.用P,V原语实现进程互斥80

■利用P,V原语和信号量可以方便地解决并发进程的互斥问题

,而且不会产生使用加锁法解决互斥问题所出现的问题。

■为临界资源设置一个互斥信号量sem,其初值为1;在每个进

程中修临界区代码置于P(sem)和V(sem)原语之间

■必须成对使用P和V原语：遗漏P原语则不能保证互斥访问，

遗漏V原语则不能在使用临界资源之后修其释放(给其他等

待的进程)；P、V原语不能次序错误、重复或遗漏

《爹中网涔在以装M

例：用信号量实现两个进程Pa和Pb的互斥81

■设sem为互斥信号量，其取值范围为(1,0,-1);其中

sem=l表示进程Pa和Pb都未进入临界区，sem=0表示进程Pa或

Pb已进入临界区,sem=T表示进程Pa和Pb中一个已进入临界

区，而另一个等待进入临界区。

《爹中网涔在以装M

82

描述：

Pa:Pb:

P(sem)P(sem)

<S><S>

V(sem)V(sem)

《爹中网涔在灾盛th

回顾83

(a)信号量sem大于等于零时，代表可供并发进程使用

的资源数，小于零时表示等待使用临界区的进程数。

(b)信号量的数值仅能由P,V原语操作改变，一次P原

语操作使信号量sem或1,总一次V原语操作将使信号量sem加

转进程调度

返回或转进程调度

《爹中网涔在灾盛th

信号量的应用——互斥

■设民航售票系统有n个售票处，每个BeginS:semaphore;

售票处通过终端访问系统中的公用S=l;

数据区，假定数据区的Xk(k=l,2,…Cobegin

)单元分别存放某月某日某次航班Pi(i=l,2,...n)

Begin按旅客订票要求找到Xk;

的现存票数,Pl,P2,・・.Pn表示各售票

P(S)；

处的进程，表示各进程

Rl,R2,..RnRi=Xk;

执行时所用的工作单元，用信号量IfRi三1thenbeginRi=Ri-1;

实现进程间的互斥的程序：保证数Xk=Ri;

据的完整性(读者一写者问题)V(S);

输出一张票

end

elsebeginV(S);

输出”票已售完”

end

endif

Coend

End

《爹中网涔在以装h

3.6进程同步85

■1.同步的概念

■2.私用信号量

■3,用「，V原语操作实现同步

■4.生产者-消费者问题

《爹中网涔在以装M

1.同步的概念86

・同步：所谓同步就是并发进程在一些关键点上可能需要相互

等待与互通消息，这样的相互制约关系称为进程同步。

■互斥的概念来自于诸进程对独占使用资源（设备）的竞争，

同步来源于多个进程的合作。在人类社会中竞争与合作是永

恒的。

《爹中网涔在以装M

引例：计算进程和打印进程使用同一缓冲区

Pc:Pp:

A:localBufB:localPri

repeatrepeat

Buf-BufPri-Buf

untilBuf=^unti1Prir空

计算打印Buf中的数据

Buf-计算结果清除Buf中的数据

gotoAgotoB

《爹中网涔在灾盛th

88

■存在的问题：

令反复测试语句降低系统效率

令进程PC和Pp之间存在直接制约，PC的结果是Pp执行的条件

,Pp打印完后才能继续执行Pc。

令不能并发执行，必须按顺序执行

■解决办法：

令两个进程互相给对方发送条件已具备的信号。这样被制约

进程可以省去对执行条件的测试，只要收到了制约进程发

来的信号便开始执行，未收到信号时便进入等待状态。

《爹中网涔在以装M

改进算法89

Pc:Pp:

A:wait(Bufempty)B:wait(Bufful1)

计算打印Buf中的数据

Buf-计算结果清除Buf中的数据

Bufempty-falseBufful1-false

signal(Bufful1)signal(Bufempty)

gotoAgotoB

《爹中网涔在灾盛th

2.私用信号量90

■私用信号量：为解决这类阻塞的需要，为每个进程设置初值

为。的信号量S(i),表示合作进程间发送的消息。当一个进

程要阻塞自己等待某个事件的完成，执行P(S(i)),初值为0

,结果S(i)=-1,主动阻塞在自己的信号量上，相关协同进

程完成了它的操作后，唤醒等待它的进程，执行V(S(i)),使

之变为0。

■私用信号量，代表该进程要等待的事件，自愿阻塞，实现同

步；

■公用信号量，代表临界资源，被迫阻塞。实现互斥；

《爹中网涔在以装M

3.用P,V原语操作实现同步一

■利用P,V原语实现进程同步的方法与利用Wait和Signal过程

相同，也是分三步：

令首先为各并发进程设置私用信号量

令为私用信号量赋初值

令最后用P,V原语和私用信号量规定各进程的执行顺序。

《爹中网涔在以装M

进程同步小结92

■进程同步：

所谓同步就是并发进程在一些关键点上可能需要相互等

待与互通消息，这样的相互制约关系称为进程同步。

互斥的概念来自于诸进程对独占使用资源(设备)的竞

争，同步来源于多个进程的合作。

为解决这类阻塞的需要，为每个进程设置初

值为。的信号量S(i),表示合作进程间发送的消息。当一个

进程要阻塞自己等待某个事件的完成，执行P(S(i)),初值为

0,结果S(i)=-1,主动阻塞在自己的信号量上，相关协同进

程完成了它的操作后，唤醒等待它的进程，执行V(S(i)),使

之变为0。

《爹中网涔在灾盛th

进程同步小结93

■2.用p、V、原语实现同步：

令首先为各并发进程设置私用信号量

令为私用信号量赋初值

令最后用P,V原语和私用信号量规定各进程的执行顺序。

《爹中网涔在以装M

进程同步举例：缓冲区队列读、写操作:94

■设进程Pa和Pb通过缓冲区队列发送数据，Pa为发送进程，Pb

为接收进程，Pa发送数据时调用发送过程deposit(data),

Pb接收数据时调用过程remove(data),数据的发送和接收满

足：

令在Pa至少送一块数据入一个缓冲区之前，Pb不可能从缓冲

区中取出数据；

令Pa往缓冲区队列发送数据时，至少有一个缓冲区是空的；

令由Pa发送的数据块在缓冲队列中按FIFO方式排列。

Buf2

《爹中网涔在灾盛th

Deposit(data)和Remove(data)描述:95

Pa:deposit(data):Pb:remove(data)

beginlocalxbeginlocalx

P(Bufempty)P(Buffull)

按FIFO方式选择一个按FIFO方式选择一个满

空缓冲区Buf(x)缓冲区Buf(x)

Buf(x)-datadata—Buf(x)

Buf(x)置满标记Buf(x)置空标记

V(Buffull)V(Bufempty)

endend

《爹中网涔在灾盛th

思考题96

■在上面的例题中需要考虑互斥吗？为什么？如果每次只允

许一个进程对缓冲区队列进行操作时怎么办？

《爹中网涔在以装M

97

■答案：(1)不需要考虑互斥。因为deposit过程每次都选择空

缓冲区进行数据写入，remove过程每次都从装满数据的缓冲

区中选择一个，然后取出数据。

(2)圈缓冲区看作临界资源。

《爹中网涔在以装M

进程互斥、同步小结98

■引起的相互制约。进程间的制约关系：

令间接制约：进行竞争--独占分配到的部分或全部共享资

源，“互斥”

令直接制约：进行协作--等待来自其他进程的信息，“同

步”

《爹中网涔在灾盛th

进程互斥小结

■进程互斥：

多个进程在对硬件或软件（如外设、共享代码段、共享

数据结构）进行访问时（关键是进行写入或修改），必须互

斥地迸行。

不允许多个并发进程交叉执行的一段程序，是由

属于不同并发进程的程序段共享公用数据或变量而引起的；

不可能用增加硬件的方法来解决。因此，临界区也可以被称

为访问公用数据的那段程序。

不允许两个以上的并发进程同时进入临界区。

《爹中网涔在灾盛th

多进程共享内存栈区示例100

////

系统区

进程

PaIIII

的程序

1111

--A

IIII

top进程Pb

的程序

////

栈s

《爹中网涔在灾盛th

共享栈区的两个并发进程必须互斥101

Proceduregetspace

begin

localg

g-stack[top]

top-top-1

end

Procedurerelease(ad)

begin

top-top+1

stack[top]-ad

end

《爹中网涔在灾盛th

进程互斥小结102

3.互斥的加锁