第二章 进 程 管 理
第二章 进程管理
2.1 进程的基本概念
2.2 进程控制
2.3 进程同步
2.4 经典进程的同步问题
2.5 管程机制
2.6 进程通信
2.7 线程
第二章 进 程 管 理
2.1 进程的基本概念
2.1.1 前趋图
2.1.2 程序的顺序执行及其特征
2.1.3 程序的并发执行及其特征
2.1.4 进程的特征与状态
2.1.5 进程控制块
第二章 进 程 管 理
2.1.1 前趋图（ Precedence Graph）
是一个有向无循环图, 记为 DAG(Directed Acyclic
Graph),用于描述进程之间执行的前后关系 。
P1
P2
P3
P4
P5
P6
P7
P8 P9 结点有向边
直接前驱
直接后继
初始结点
终止结点
重量
例：具有九个结点的前趋图 P
i Pj
前趋关系,P1→P 2,P1→P 3,P1→P 4,P2→P 5,
P3→P 5,P4→P 6,P4→P 7,P5→P 8,P6→P 8,
P7→P 9,P8→P 9
第二章 进 程 管 理
S1
S2
S3
前驱图中不能存在循环关系。
如：
第二章 进 程 管 理
2.1.2 程序的顺序执行及其特征
各程序段间程序的顺序执行 如图：
在计算机系统中只有一个程序在运行，这个程
序独占系统中所有资源，其执行不受外界影响。一
道程序执行完后另一道才能开始。
I1 P1 O1 I2 P2 O2
作业 1 作业 2
第二章 进 程 管 理
一个程序段的多条语句的顺序执行：
S1 S2 S3
S1,a:=x+y
S2,b:=a-5
S3,c:=b+1
第二章 进 程 管 理
程序顺序执行的特征：
? 顺序性,一个程序开始执行必须要等到前一
个程序已执行完成 。
? 封闭性,程序一旦开始执行, 其计算结果不
受外界因素影响 。
? 可再现性,程序的结果与它的执行速度无关
（ 即与时间无关 ）, 只要给定相同的输入,
一定会得到相同的结果 。
第二章 进 程 管 理
2.1.3 程序的并发执行及其特征
1,程序的并发执行
所谓程序的 并发执行 是指：若干个程序同时在系统
中执行，这些程序的执行在时间上是重叠的，一个
程序的执行尚未结束，另一个程序的执行已经开始。
I1 I2 I3
C1 C2 C3
P1 P2 P3
I4
C4
P4
第二章 进 程 管 理
一个程序段的多条语句的并发执行：
S1,a:=x+2
S2,b:=y+5
S3,c:=a+b
S4,d:=c+6
S1
S3 S4
S2
第二章 进 程 管 理
程序并发执行的特征：
? 间断性
由于资源共享和相互合作，并发执行的程序间
形成了相互制约关系，导致程序的运行过程出现
“执行 —暂停 —执行”的现象。
? 失去封闭性
程序在并发执行时, 是多个程序共享系统中的
资源, 因此这些资源的状态将由多个程序来改变 。
? 不可再现性
由失去封闭性导致 。 同样的初始条件, 一个程
序的多次重复执行, 可得到不同的结果 。
第二章 进 程 管 理
例：程序 A,B，共享变量 N。代码如下：
程序 A
BEGIN
REPEAT
…
…
N,=N+1
…
…
UNTIL FALSE
END
程序 B
BEGIN
REPEAT
…
…
PRINT(N)
N:=0
…
UNTIL FALSE
END
第二章 进 程 管 理
两个程序以不同速度运行，可能出现三种情况：
?N:=N+1在 Print(N)和 N:=0之前
——N值分别为 N+1,N+1,0
?N:=N+1在 Print(N)和 N:=0之后
——N值分别为 N,0,1
?N:=N+1在 Print(N)和 N:=0之间
——N值分别为 N,N+1,0
思考：任何并发执行都是不可再现的吗？
第二章 进 程 管 理
并发执行的条件：
并发执行的条件：达到封闭性和可再现性。
并发执行失去封闭性的的原因是 共享资源的影响,
去掉这种影响就行了。 1966年，由 Bernstein给出并
发执行的条件。
将程序中任一语句或程序段 Pi划分为两个变量的
集合,R(pi)和 W(pi)。其中，
R(pi)={a1,a2,… an}，程序 pi在执行期间引用的
（读的）变量集，称为, 读集, 。
W(pi)={b1,b2,… bm}，程序 pi在执行期间改变的
（写的）变量集，称为, 写集, 。
第二章 进 程 管 理
Bernstein条件,
如果对于语句 p1,p2,如果同时满足以下
三个条件：
R(p1)∩W(p2) ={ }
R(p2)∩W(p1) ={ }
W(p1)∩W(p2) ={ }
则语句 p1,p2可以并发执行。
第二章 进 程 管 理
例如, 有如下四条语句：
S1,a,= x + y S2,b,= z + 1
S3,c,= a – b S4,w,= c + 1
其中,R(S1)={x,y} W(S1)={a}
R(S2)={z} W(S2)={b}
R(S3)={a,b} W(S3)={c}
R(S4)={c} W(S4)={w}
对于 S1和 S2,有：
R(S1)∩W(S2) ={ }, R(S2)∩W(S1) ={ },
W(S1)∩W(S2) ={ }
结论：语句 S1和 S2满足 Bernstein条件，可以并发执行。
其他语句之间自己分析。
第二章 进 程 管 理
2.1.4 进程的特征与状态
1,进程的定义
进程是操作系统中最基本、重要的概念。
是多道程序系统出现后，为了刻画系统内部出
现的 动态情况,描述系统内部各道程序的活动
规律引进的一个概念，所有多道程序设计操作
系统都建立在进程的基础上。
第二章 进 程 管 理
(1) 进程是程序的一次执行 。
(2) 进程是一个程序及其数据在处理机上顺序执
行时所发生的活动 。
(3) 进程是程序在一个数据集合上运行的过程,
它是系统进行资源分配和调度的一个独立单位 。
(4) 进程是进程实体的运行过程, 是系统进行资
源分配和调度的一个独立单位 。
(5) 进程是一个具有一定独立功能的程序关于某
个集合的一次运行活动。 (我国 78年庐山研讨会 )
第二章 进 程 管 理
2,进程同程序的比较：
? 进程是动态的, 程序是静态的,程序是有序代码的集
合；进程是程序的执行 。 通常进程不可在计算机之间
迁移；而程序通常对应着文件, 静态和可以复制 。
? 进程是暂时的, 程序是永久的,进程是一个状态变化
的过程, 是有一定生命期的；而程序可以作为一种软
件资料长久保存 。
? 进程与程序的组成不同,进程是由程序和数据, 进程
控制块三部分组成的 。
? 进程与程序的对应关系, 同一程序同时运行于若干个
数据集合上，它将属于若干个不同的进程。也就是说
同一程序可以对应多个进程；一个进程的执行也可以
涉及到一个或几个程序（调用）。
第二章 进 程 管 理
3,进程的特征：
? 结构特征,由程序段, 数据段, 进程控制块三部
分组成；
? 动态性,进程是程序的执行；
? 并发性,多个进程可同存于内存中, 能在一段时
间内同时运行；
? 独立性,独立运行的基本单位, 独立获得资源和
调度的基本单位；
? 异步性,各进程按各自独立的不可预知的速度向
前推进 。
第二章 进 程 管 理
4,进程的三种基本状态
? 不同系统设置的进程状态数目不同。
? 进程有三种基本状态：
1) 就绪状态,进程已获得除 CPU 以外的所有
必要资源，只要得到 CPU，便可立即执行。
2) 执行状态,进程已得到 CPU，其程序正在
CPU
3) 阻塞状态,正在执行的进程因某种事件 (如
I/O 请求 )的发生而暂时无法继续执行，只
有等相应事件完成后，才能去竞争 CPU。
第二章 进 程 管 理
进程的状态变迁图
执行
第二章 进 程 管 理
五状态进程模型
进程正常结束，
或因某种原因
被取消后,OS
释放出的进程。
刚刚建立的
进程，还未
送入就绪队
列。
执行新建态 终止态
第二章 进 程 管 理
5,七状态进程模型
引入挂起状态的原因：
? 终端用户的请求
? 父进程请求
? 负荷调节的需要
? 操作系统的需要
第二章 进 程 管 理
―挂起, 的实质 是使进程不能继续执行，即使
挂起后的进程处于就绪状态，它也不能参与对
CPU 的竞争。因此，称被挂起的进程处于静止状
态，相反，没被挂起的进程则处于活动状态。而
且，处于静止状态的进程，只有通过, 激活, 动
作，才能转换成活动状态。
进程挂起后,程序代码和数据集被调出到外存
的交换区中,腾出来的内存空间供其它进程使用。
第二章 进 程 管 理
激活
挂起
事件
发生
事件
发生 等待
事件
挂起
调度
超时
释放
激活
挂起
七状态进程模型
挂起
就绪态
挂起
阻塞态
就绪态
阻塞态
执行态 终止态
新建态
第二章 进 程 管 理
? 就绪态 （ ready）,进程在内存且可立即进入运
行状态 。
? 阻塞态 （ blocked）,进程在内存并等待某一个
事件的出现 。
? 挂起就绪态 （ ready suspend）,进程在外存,但
只要进入内存,即可运行 。
? 挂起阻塞态 （ blocked suspend）,进程在外存
并等待某一个事件的出现 。
第二章 进 程 管 理
【 思考题 】
? 有没有这样的状态转换，为什么？
阻塞 —运行
就绪 —阻塞
第二章 进 程 管 理
2.1.5 进程控制块 （ Process Control Block,PCB ）
1,进程控制块的作用
进程控制块的作用是使一个在多道程序环境
下不能独立运行的程序 (含数据 ),成为一个能独
立运行的基本单位, 一个能与其它进程并发执行
的进程 。 或者说, OS是根据 PCB来对并发执行
的进程进行控制和管理的 。
? 进程与 PCB是一一对应的。
? PCB应常驻内存。
第二章 进 程 管 理
2,进程控制块中的信息
? 进程标识符,用于惟一地标识系统中的每个进程。
另外，还可以用父进程的标识符及子进程的标识
符来描述进程的家族关系。
? 处理机状态,用于 CPU 切换时保存现场和恢复
现场，主要由处理机中各种寄存器的内容组成。
? 进程调度和控制信息,用于进程调度和控制，主
要包括进程状态、优先级、等待和使用 CPU 的
时间总和、程序和数据的地址、进程同步和通信
信息、资源清单和进程队列指针等。
第二章 进 程 管 理
3,进程控制块的组织方式
图 2-7 PCB链接队列示意图
在一个系统中通常有许多的 PCB，称为 PCB
集合 。
为了便于管理，系统必须用适当的方式将
PCB 组织起来，常用的方式有 链接方式 和 索引方
式 。
第二章 进 程 管 理
PCB1 4
PCB2
PCB3
PCB4
PCB5
PCB6
PCB7
PCB8
PCB9
3
0
8
7
9
0
1
执行指针
就绪队列指针
阻塞队列指针
空闲队列指针
…
1) 链接方式 相同状态的进程 PCB组成一个链表，不同状态对应多个不同的链表。
空指针
第二章 进 程 管 理
2) 索引方式
执行指针
就绪索引表
PCB1
PCB2
PCB3
PCB4
PCB5
PCB6
PCB7
阻塞索引表
就绪表指针
阻塞表指针
对具有相同状态的进程，分别设置各自的
PCB索引表，表明 PCB在 PCB表中的地址。
第二章 进 程 管 理
2.2 进 程 控 制
2.2.1 进程的创建
2.2.2 进程的终止
2.2.3 进程的阻塞与唤醒
2.2.4 进程的挂起与激活
第二章 进 程 管 理
进程控制是进程管理中最基本的功能，它用
于创建和撤消进程，并对进程在整个生命周期中
各种状态之间的转换进行有效控制。
进程控制是由 操作系统的内核 通过 原语 来实
现的。
原语,系统状态下执行的某些具有特定功能
的程序段称为原语。 (原语的执行具有原子性，
执行时不可分割 )。
第二章 进 程 管 理
2.2.1 进程的创建
1,进程图 (Process Graph),
用于描述一个进程的家族关系的有向树。
第二章 进 程 管 理
D E F G H
B C
I J K L M
A
祖先进程
父进程
子进程
? 子进程可以继承父进程的所有资源，当子进程被撤
消时，应将从父进程那里获得的资源归还给父进程。
? 撤消父进程时也必须同时撤消其所有的子进程。
第二章 进 程 管 理
2,引起创建进程的事件
(1) 用户登录。
(2) 作业调度。
(3) 提供服务。
(4) 应用请求。
第二章 进 程 管 理
3,进程的创建 (Creation of Progress)
(1) 申请空白 PCB。
(2) 为新进程分配资源。
(3) 初始化进程控制块。
(4) 将新进程插入就绪队列。
创建新进程通过 进程创建原语 creat（） 来完成。
进程创建原语的主要任务是 创建进程控制块 PCB。
第二章 进 程 管 理入 口
查 PCB链表
有空 PCB？
取空 PCB（ i）
将有关参数填入 PCB（ i）相应项
PCB（ i）入就绪队列
PCB(i)入进程家族或进程链
创建失败
返 回
创
建
原
语
流
程
图
N
Y
第二章 进 程 管 理
2.2.2 进程的终止
当某进程实现完成任务正常结束时, 或在运
行过程中遇到某些异常情况 （ 如越界错误, 非法
指令, 运行超时等 ）, 或外界干预需要结束时,
应予以终止 （ 撤消 ） 。 （ 参见 P35）
通过 进程终止原语 来终止进程 。
终止进程的实质是 收回 PCB。
第二章 进 程 管 理
(1) 查找对应的 PCB
(2) 终止该进程及子孙进程
(3) 释放资源
(4) 释放 PCB
第二章 进 程 管 理
终
止
原
语
流
程
图
入 口
查进程链表或进程家族
有此 PCB吗？
释放该进程所占有的资源
出错处理该 PCB有子进程吗？
释放该 PCB结构本身
Y
Y
N
N
返 回
第二章 进 程 管 理
2.2.3 进程的阻塞与唤醒
1,
当正在执行的进程需要等待某种事件的完成
或本身无新工作可做时, 应调用阻塞原语将自己
从执行状态转换成阻塞状态 。
进程阻塞是进程的一种主动行为。通过 阻塞原
语 block（） 来完成。
具体的操作过程是：停止进程的执行，将其状
态改为阻塞状态，并把它的 PCB 插入相应的阻塞
（等待）队列，转调度程序进行重新调度。
第二章 进 程 管 理
阻
塞
原
语
流
程
图
保存当前进程的 CPU现场
置该进程的状态
被阻塞进程入阻塞队列
转进程调度
入 口
第二章 进 程 管 理
2.
当阻塞进程所等待的事件完成时, 应调用
唤醒原语将该进程的状态从阻塞状态转换成就
绪状态 。 通过 唤醒原语 wakeup（ ） 来完成 。
处于阻塞状态的进程是绝不可能叫醒自己
的, 必须由它的合作进程用唤醒原语唤醒它 。
具体的操作过程是：在等待队列中移出该
进程的 PCB,将其置成就绪状态, 并把它插入
就绪队列 。
第二章 进 程 管 理
唤
醒
原
语
流
程
图
从等待队列中摘下被唤醒进程
将被唤醒进程置为就绪态
将被唤醒进程送入就绪队列
转进程调度或返回
入 口
第二章 进 程 管 理
2.2.4 进程的挂起与激活
1、进程的挂起
当出现了引起进程挂起的事件时，用户请求将自
己挂起，或者父进程请求挂起自己的子进程。系统
通过 挂起原语 suspend（） 将指定进程挂起。
具体的执行过程：检查被挂起进程的状态，如果
处于活动就绪状态，就将它改为静止就绪；如果处
于活动阻塞，则改为静止阻塞。将 PCB 复制到指定
的内存区域供用户或父进程考查。若挂起前进程正
在执行，则转调度程序重新进行进程调度。
第二章 进 程 管 理
2、进程的激活
当发生激活事件后，系统利用 激活原语 Active( )
将指定进程激活。
具体的操作过程是：若进程处于静止阻塞状态，
则将它转换成活动阻塞状态，否则将它转换成活动
就绪状态。若进程转换成活动就绪状态，而系统又
采用抢占调度策略，则应检查该进程是否有权抢占
CPU，若有则应进行进程调度。
第二章 进 程 管 理
2.3 进 程 同 步
2.3.1 进程同步的基本概念
2.3.2 信号量机制
2.3.3 信号量的使用
第二章 进 程 管 理
进程同步 是指对多个相关进程在执行次序
上进行协调。
进程同步的 主要任务 是使并发执行的诸进
程之间能有效的共享资源和相互合作，从而使
程序的执行具有可再现性。
第二章 进 程 管 理
1,两种形式的制约关系
? 间接相互制约关系
互斥关系，资源共享关系
? 直接相互制约关系
同步关系，相互合作关系
2.3.1 进程同步的基本概念
第二章 进 程 管 理
2,临界资源
一次仅允许一个进程访问的资源。如：进程Ａ、
Ｂ共享一台打印机，若让它们交替使用则得到的
结果肯定不是我们希望的。
临界资源可能是硬件，也可能是软件：变量，
数据，表格，队列等。
并发进程对临界资源的访问必须作某种限制，
否则就可能出现错误，如：联网售票，会出现与
时间有关的错误。
第二章 进 程 管 理
例：两进程共享一个变量 COUNT
P1,R1:=COUNT;
R1:=R1+1;
COUNT:=R1;
P2,P2:=COUNT;
R2:=R2+1;
COUNT:=R2;
试比较两进程顺序执行和并发执行的结果。
第二章 进 程 管 理
若 P1,P2按如下顺序
并发执行：
P1,R1:=COUNT;
P2,R2:=COUNT;
P1,R1:=R1+1;
COUNT:=R1;
P2,R2:=R2+1;
COUNT:=R2;
若 P1,P2顺序执行：
P1,R1:=COUNT;
R1:=R1+1;
COUNT:=R1;
P2,R2:=COUNT;
R2:=R2+1;
COUNT:=R2;
第二章 进 程 管 理
3,临界区 (Critical Section)
每个进程中，访问临界资源的那段代码称为
临界区 。
诸进程对临界资源的互斥访问就变为怎样使
诸进程互斥地进入临界区。
互斥的实质就是同步，或者说，互斥是同步
的一种特殊形式。
第二章 进 程 管 理
访问临界资源的循环进程描述如下：
REPEAT
ENTRY SECTION
CRITICAL SECTION
EXIT SECTION
REMAINDER SECTION
UNTIL FALSE
进入区
临界区
退出区
剩余区
第二章 进 程 管 理
4,同步机制应遵循的原则
用来实现互斥的同步机制必须遵循下述四条
准则：
(1) 空闲让进。
(2) 忙则等待。
(3) 有限等待。
(4) 让权等待。
第二章 进 程 管 理
2.3.2 信号量机制
信号量机制是荷兰学者 Dijkstra在 1965年
提出的一种卓有成效的同步工具，在长期且广
泛的应用中，已由早期的整型信号量发展为记
录型信号量，进而发展为信号量集。
第二章 进 程 管 理
1,整型信号量
整型信号量是一个非负的共享整数，除了初始化
外，它只能通过两个标准的原子操作 wait 和 signal 来
访问，即 P,V操作 。
wait和 signal
wait(S),while S≤0 do no-op
S∶ =S-1;
signal(S),S∶ =S+1;
整型信号量的主要问题是，只要 S≤0,wait 操作
就会不断地测试，因而，没能做到“让权等待”。
第二章 进 程 管 理
2,记录型信号量
记录型信号量中除了一个整型变量 value 外，还
增加了一个等待队列指针 L。记录型信号量采用了
记录型的数据结构，描述为：
type semaphore=record
value:integer;
L:list of process;
end
第二章 进 程 管 理
相应的 wait 和 signal 操作（即 P,V操作）可描述为：
procedure P(S)
var S,semaphore;
begin
S.value:=S.value-1;
if S.value＜ 0 then block(S.L)
end
当 S.value＜ 0 时，进程会立即将自己阻塞，因
此解决了整型信号量的“忙等”问题，做到了“让
权等待”。
该进程状态置为
阻塞状态；放弃
处理机；将该进
程的 PCB插入链
表 S.L中。
第二章 进 程 管 理
procedure V(S)
var S,semaphore;
begin
S.value:=S.value+1;
if S.value≤0 then wakeup(S.L)
end
唤醒 S.L链表 中的第
一个等待进程；改变
状态为就绪态；将其
插入就绪队列中。
第二章 进 程 管 理
? 一个信号量通常对应于一类临界资源，在使用
前，信号量必须经过定义并赋适当的初值，初值
表示系统中某类资源的数目。初值为 1表示对临界
资源进行访问，此时信号量转化为互斥信号量。
? 每次对信号量进行 wait 操作意味着申请一个单
位的该类资源,signal 操作意味着归还一个单位的
该类资源。
? 当 S.value＞ 0 时，它的值表示系统中该类资源
当前可用的数目； S.value≤0 时，表示该类资源已
分配完毕，其绝对值表示系统中因申请该类资源
而阻塞在 S.L 队列上的进程数目。
必须注意的几个问题：
第二章 进 程 管 理
2.3.3 信号量的使用
? 必须置一次且只能置一次初值
? 初值为整数，且不能为负数
? 只能执行 P,V操作
第二章 进 程 管 理
1,用信号量实现进程互斥
P(mutex)
V(mutex)
P1 P2 P3
互斥区
P(mutex)
P(mutex)
V(mutex)
V(mutex)
第二章 进 程 管 理
PA:
…
P(mutex);
critical section;
V(mutex);
…
PB:
…
P(mutex);
critical section;
V(mutex);
…
? mutex用于实现互斥，初值为 1。在每个进程中将
临界区代码置于 P(mutex)和 V(mutex)之间。
模
型
：
第二章 进 程 管 理
模
拟
执
行
：
序号 PA PB mutex 说明
0 1
1 P(mutex) 0 PA进入，占资源
2 P(mutex) -1 PB进入，无资源
3 V(mutex) 0 PA释放资源，PB解封
4 V(mutex) 1 PB释放资源
0 可反复执行
第二章 进 程 管 理
? 对于两个并发进程，互斥信号量的值仅取 1,0 和 -
1三个值：
若 mutex＝ 1表示没有进程进入临界区；若 mutex
＝ 0表示有一个进程进入临界区；若 mutex＝ -1表示一
个进程进入临界区，另一个进程等待进入。
? 当实现 n个进程并发时，互斥信号量的取值为 1,0、
-1,…, -(n-1)。
? P,V操作必须成对出现：遗漏 P(mutex)将不能保
证互斥访问，遗漏 V(mutex)将不能再使用临界资源之
后将其释放（给其他等待的进程）。
第二章 进 程 管 理
PA:
…
L1,P(proceed)
…
2,用信号量实现同步
PB:
…
L2,V(proceed)
…
? proceed用于实现同步，初值为 0。 PA在 L1点必
须与 PB在 L2点同步,PA受 PB的制约，而 PB不受
PA的制约，使非对称的。
? P,V操作必须成对出现,当用于实现互斥时，
它们同处于同一进程；当用于实现同步操作时，则
不在同一进程中出现。
模
型
：
第二章 进 程 管 理
3,利用信号量描述前趋关系
信号量可用来描述程序或语句之间的前趋
关系。
若 Pi是 Pj的直接前趋，即 Pi→Pj,则可设
置一个初值为 0 的公用信号量 S，并将 V(S)操
作放在 Pi后，而在 Pj前插入 P(S)操作，以保证
Pi在 Pj开始执行之前完成。
Pi Pj
第二章 进 程 管 理
Var a,b,c,d,e,f,g:semaphores;
Begin
parbegin
begin s1;v(a);v(b);end;
begin p(a);s2;v(c);end;
begin p(c);s4;v(e);v(f);end;
begin p(b);s3; v(d);end;
begin p(e);s5; v(g);end;
begin p(f);p(d);s6;v(h);end;
begin p(g);p(h);s7;end;
Parbegin
end
s1
s2 s3
s4
s5 s1s6
s7
a b
c
d
e f
g h
例：
第二章 进 程 管 理
2.4 经典进程的同步问题
2.4.1 生产者 —
2.4.2 哲学家进餐问题
2.4.3 读者 ——写者问题
第二章 进 程 管 理
2.4.1 生产者 —消费者问题
一次只可放一个产品
生产者 消费者
?只要仓库未满，生产者就可以把产品放入仓库。
?只要仓库未空，消费者就可以从仓库中取走物品。
问题描述：
第二章 进 程 管 理
inout
0
1
2345
6
7
8 9 10 11
? in,下一个可供投放产品的缓冲区,in:=(in+1)mod n；
out:下一个可供获取产品的缓冲区,out:=(out+1)mod n。
? 若 (in+1)mod n = out，有界缓冲区满；
若 in = out，有界缓冲区空。
环形缓冲池
设一个长度为 n的有界缓冲区：
（以 n=12为例）
第二章 进 程 管 理
问题分析,这是一个同步与互斥共存的问题。
1,生产者 —消费者问题是一个同步问题。即生产者
和消费者之间满足如下条件：
----消费者想接收数据时，有界缓冲区中至少有一
个单元是满的。
----生产者想发送数据时，有界缓冲区中至少有一
个单元是空的。
故设置两个信号量：
---- empty：说明空缓冲区的数目，初值为有界缓
冲区的大小 N。
---- full：说明已用缓冲区的数目，初值为０。
第二章 进 程 管 理
2,由于有界缓冲区是临界资源，因此，各生产者
进程和各消费者进程之间必须互斥执行。
故设置一个互斥信号量 mutex，其初值为１。
第二章 进 程 管 理
问题的解：
Var medex,empty,full:semaphore;
buffer:array[0,1,…n -1] of item;
in,out:integer;
Begin
metex:=1;
empty:=n; full:=0;
in:=0; out:=0;
Parbegin
procedure,… …
consumer,… …
Parend
end
第二章 进 程 管 理
Consumer：
begin
repeat
P(full);
P(mutex);
从 Buffer[out]取产品 ;
out = (out +1) mod n;
V(mutex);
V(empty);
…
消费产品 ;
…
until false;
end
Producter：
begin
repeat
…
生产产品 ;
…
P(empty);
P(mutex);
往 Buffer [in]放产品 ;
in= (in+1) mod n;
V(mutex);
V(full);
until false;
end
第二章 进 程 管 理
? 有五个哲学家围坐在一
圆桌旁，桌中央有一盘
通心粉，每人面前有一
只空盘子，每两人之间
放一只筷子。
2.4.2 哲学家就餐问题
问题描述：
? 每个哲学家的行为是思考，感到饥饿，然后吃通心
粉；吃完后继续思考。
? 为了吃通心粉，每个哲学家必须拿到两只筷子，并
且每个人只能直接从自己的左边或右边去取筷子。
第二章 进 程 管 理
问题的解,repeat
P(fork[i]);
P(fork[(i+1) mod 5])；
…
进食；
…
V(fork[i]);
V(fork[(i+1) mod 5])；
…
思考；
…
until false
设 fork[5]为 5 个信号
量（分别表示每支筷
子），初值均为 1。
此解可以保证互斥使
用筷子，但会产生死
锁。
第二章 进 程 管 理
为防止死锁发生可采取的措施：
? 最多允许 4个哲学家同时去拿左边的筷子；
? 仅当一个哲学家左右两边的筷子都可用时，才
允许他拿筷子进餐； （ ?）
? 给所有哲学家编号，奇数号的哲学家必须首先
拿左边的筷子，偶数号的哲学家则反之。
第二章 进 程 管 理
信号量集 ——AND型信号量集
? AND型信号量集的基本思想：
在一个原语中申请整段代码需要的多个临
界资源，要么全部分配给它，要么一个都不分
配。
? AND型信号量集 P原语为 Swait；
AND型信号量集 V原语为 Ssignal。
第二章 进 程 管 理
采用 AND信号量集解决哲学家就餐问题
repeat
Swait( fork[i],fork[(i+1) mod 5] )；
…
进食；
…
Ssignal( fork[i],fork[(i+1) mod 5] )；
…
思考；
…
until false
设 fork[5]
为 5 个信
号量（分
别表示每
支筷子），
初值为均
1。
第二章 进 程 管 理
2.4.3 读者 -写者问题
问题描述：
有两组并发进程 ——读者和写者，共享一组数
据区。要求：
? 允许多个读者同时执行读操作；
? 任一写者在完成写操作之前不允许其它读者或
写者工作 (读写文件 )；
? 写者执行写操作前，应让已有的写者和读者全
部退出。
第二章 进 程 管 理
? 如果读者来：
– 若无读者、写者，则新读者可以读；
– 若有写者等待，但有其它读者正在读，则新
读者也可以读；
– 若有写者写，则新读者等待。
? 如果写者来：
– 若无读者，则新写者可以写；
– 若有读者，则新写者等待；
– 若有其它写者，则新写者等待。
问题分析：
第二章 进 程 管 理
问题的解：
? 整形变量 readcount表示正在读的读者数目，初值
为 0。
? 信号量 w用于保证读者和写者、写者和写者之间
的互斥,初值为 1。
? 信号量 mutex用于保证对 readcount 这个临界资源
的互斥修改，初值为 1。
第二章 进 程 管 理读者：
begin
repeat
P(mutex);
readcount,= readcount+1;
if readcount=1 then P (w);
V(mutex);
…
执行读操作；
…
P(mutex);
readcount,= readcount-1;
if readcount=0 then V(w);
V(mutex);
until false
end
写者：
begin
repeat
P(w);
执行写操作；
V(w);
until false
end
第二章 进 程 管 理
【 思考题 】
桌上有一空盘，最多允许存放一只水果。爸爸
可向盘中放一个苹果或放一个桔子，儿子专等吃盘
中的桔子，女儿专等吃苹果。
试用 P,V操作实现爸爸、儿子、女儿三个并发
进程的同步与互斥。
提示,设置一个信号量表示可否向盘中放水果，一
个信号量表示可否取桔子，一个信号量表示可否取
苹果。
第二章 进 程 管 理问题的解：
Daughter:
repeat
P(Sa)；
取苹果；
V(S);
吃苹果 ;
until false
Son:
repeat
P(So)；
取桔子；
V(S);
吃桔子 ;
until false
Father:
repeat
P(S);
将水果放入盘中 ;
if 桔子
then V(So);
else V(Sa);
until false
设置三个信号量 S,So,Sa，初值分别为 1,0,0。
分别表示可否向盘中放水果，可否取桔子，可否取
苹果。
第二章 进 程 管 理
【 思考题 】
有一个仓库，可以存放 A和 B两种产品，但要求：
（ 1） 每次只能存入一种产品（ A或 B）；
（ 2） － N＜ A产品数量－ B产品数量＜ M；
其中,N和 M是正整数。试用 P,V操作描述产品
A与 B的入库过程。
提示,设两个信号量 Sa,Sb。 Sa表示允许 A产品比 B
产品多入库的数量； Sb表示允许 B产品比 A产品多入
库的数量
第二章 进 程 管 理
? 设两个信号量 Sa,Sb,初值分别为 M-1,N-1
--- Sa表示允许 A产品比 B产品多入库的数量
--- Sb表示允许 B产品比 A产品多入库的数量
? 设互斥信号量 mutex，初值为 1。
问题的解：
第二章 进 程 管 理
B产品入库进程：
repeat
P(Sb);
P(mutex);
B产品入库
V(mutex);
V(Sa);
…
消费产品 ;
…
until false
A产品入库进程：
repeat
…
生产产品 ;
…
P(Sa);
P(mutex);
A产品入库
V(mutex);
V(Sb);
until false
第二章 进 程 管 理
2.5 管 程 机 制
2.5.1 管程的基本概念
2.5.2 利用管程解决生产者 -消费者问题
第二章 进 程 管 理
2.5.1 管程的基本概念
为什么引入管程？
? 把分散在各进程中的临界区集中起来进行管理；
? 防止进程有意或无意的违法同步操作；
? 便于用高级语言来书写程序, 也便于程序正确性
验证 。
管程的基本概念：
一个管程定义了 一个数据结构 和能为并发进程所
执行（在该数据结构上）的 一组操作,这组操作能同
步进程和改变管程中的数据。
第二章 进 程 管 理
管程的特点：
(1) 管程内的局部变量只能被局部于管程内的过
程所访问；反之亦然，即局部于管程内的过程只能
访问管程内的变量。
(2) 任何进程只能通过调用管程提供的过程入口
进入管程。
(3) 任一时刻，最多只能有一个进程在管程中执
行。
第二章 进 程 管 理
type monitor-name=monitor
variable declarations
procedure entry P1(…);
begin … end;
procedure entry P2(…);
begin … end;
…
procedure entry Pn(…);
begin … end;
begin
initialization code;
end
管程的语法
局部于管程的
共享变量说明
对该数据结构
进行操作的一
组过程
对局部于管程
的数据设置初
始值
管程的组成部分
第二章 进 程 管 理
共享数据
…
一组操作过程
初始化代码
进入队列条件 (不忙 )队列
管程的示意图：
第二章 进 程 管 理
当进程通过管程请求临界资源未能满足时，将
排在队列上等待。等待的原因可能有多个，为了区
分它们，引入条件变量 condition 。每个 condition
表示一种等待原因。
针对条件变量 x,x.wait将自己阻塞在 x队列中，
x.signal将 x队列中的一个进程唤醒。
条件变量：
第二章 进 程 管 理
2.5.2 利用管程解决生产者 -消费者问题
PC管程描述：
Type
Producer-Consumer=monitor
Var
buffer,array[0,…,n-1] of item；
count,in,out,integer；
notempty,notfull,condition；
第二章 进 程 管 理
procedure entry put(item);
begin
if count>=n then notfull.wait;
buffer(in):=nextp;
in:=(in+1) mod n;
count:=count+1；
if notempty.queue then notempty.signal;
end;
procedure entry get(item);
begin
if count<=0 then notempty.wait;
nextc:=buffer(out);
out:=(out+1) mod n;
count:=count-1；
if notfull.queue then notfull.signal;
end;
Begin in:=0; out:=0;count:=0 End
第二章 进 程 管 理
producer：
begin
repeat
produce an item；
PC,put(item)；
until false；
end
consumer：
begin
repeat
PC,get (item)；
consume the item；
until false;
end
生产者和消费者描述：
第二章 进 程 管 理
2.6 进 程 通 信
2.6.1 进程通信的类型
2.6.2 消息缓冲队列通信机制
第二章 进 程 管 理
进程之间互相交换信息的工作称为 进程通信 。
进程通信的类型,
? 低级通信,归结为进程之间的互斥和同步，一般
只传送少量信息（信号量）。缺点：效率低，通
信对用户不透明。
? 高级通信,能够高效传输大量数量数据的通信方
式。又分为三类：共享存储器系统、消息传递系
统、管道通信系统。
2.6.1 进程通信的类型
第二章 进 程 管 理
1,共享存储器系统
相互通讯的进程通过 共享数据结构 和 共享存储
区 进行通讯，可进一步分为：
? 基于共享数据结构的通信方式
进程之间通过某种数据结构，如缓冲池进行通
信，属于低级通信方式。如生产者 -消费者问题中
的有界缓冲区。
? 基于共享存储区的通信方式
为了传送大量信息，在存储器中划出一块共享
存储区，诸进程可通过对共享存储区进行读或写
来实现通信，属高级通信方式。
第二章 进 程 管 理
2,消息传递系统
? 使用最广泛的一种进程通信机制。
? 进程间的数据交换以消息或报文为单位，程序
员直接利用一组通信命令（原语）来实现通信。
? 操作系统隐藏了通信的实现细节，简化了通信
程序编制的复杂性。
第二章 进 程 管 理
（ 1） 直接通信方式
两条通信原语：
Send（ Receiver,message） ;
Receive（ Sender,message） ;
例如,Send（ p2,m1） ;
Receive（ p1,m1） ;
发送进程可直接将消息发送给目标进程。
消息传递系统的分类：
——直接通信方式和间接通信方式
第二章 进 程 管 理
repeat
…
produce an item in nextp;
…
send(consumer,nextp);
until false;
利用直接通信原语解决生产者 -消费者问题：
repeat
receive(producer,nextc);
…
consume the item in nextc;
until false;
producer：
consumer：
第二章 进 程 管 理
（ 2）间接通信方式
进程间发送或接收消息通过信箱进行，消息
可被理解成信件。也称信箱通信。
两条通信原语：
Send（ mailbox,message）；
Receive（ mailbox,message）；
注意,用户不必写出接收进程标识符，从而
可以向不知名的进程发送消息；另外，消息在信
箱中可以安全的保存，只允许核准的目标用户随
时读取，可实现非实时通信。
第二章 进 程 管 理
发送
进程 A … 邮箱体
邮箱头
接收
进程 B
? 信箱由 信箱头 和由若干格子组成的 信箱体 组成。
? 信箱中每个格子存放一封信，信箱中格子的数目
和每格的大小在创建信箱时确定。
? 进程间的通信要满足如下条件：
a,发送进程发送消息时，邮箱中至少要有一个空
格存放该消息。
b,接收进程接收消息时，邮箱中至少要有一个消
息存在。
第二章 进 程 管 理
3,管道（ Pipe）通信系统
? 所谓 管道,是指用于连接一个读进程和一个写
进程以实现它们之间通信的一个共享文件，又称
pipe文件。
? 发送进程以字符流形式把大量数据送入管道，
接收进程从管道中接收数据，所以叫 管道通信 。
? 管道的实质是 一个共享文件,基本上可借助于
文件系统的机制实现，包括（管道）文件的创建、
打开、关闭和读写。
第二章 进 程 管 理
读写进程相互协调，必须做到：
? 互斥,进程对通信机构的使用应该互斥，一个
进程正在使用某个管道写入或读出数据时，另一
个进程就必须等待。
? 同步,管道长度有限,发送信息和接收信息之间
要实现正确的同步关系。当写进程把一定数量的
数据写入 pipe，就去睡眠等待，直到读进程取走
数据后，把它唤醒。
? 确定对方是否存在,发送者和接收者双方必须
能够知道对方是否存在，如果对方已经不存在，
就没有必要再发送信息。
第二章 进 程 管 理
写进程 共享文件 读进程
管道通信的思想：
（ 1） 发送进程可以源源不断的从 pipe一端写入
数据流, 在规定的 pipe文件的最大长度 （ 如 4096
字节 ） 范围内, 每次写入的信息长度是可变的；
（ 2） 接收进程在需要时可以从 pipe的另一端读
出数据, 读出单位长度也是可变的 。
第二章 进 程 管 理
2.6.2 消息缓冲队列通信机制
? 消息缓冲队列通信机制通过内存中公用的消息
缓冲区进行进程通信，属于直接通信方式。
? 发送进程利用 send原语将消息直接发送给接收
进程；接收进程利用 receive原语接收消息。
第二章 进 程 管 理
（ 1）消息缓冲区的数据结构
type message Buffer = record
sender； 发送者 ID;
size； 消息长度 ;
text； 消息正文 ;
next； 消息队列指针 ;
end
1,消息缓冲队列通信机制中的数据结构
第二章 进 程 管 理
（ 2） PCB中有关通信的数据项
type PCB=record
…
mq ; 消息队列首指针 ;
mutex; 消息队列互斥信号量 ;
sm ; 消息队列资源信号量 ;
…
end
第二章 进 程 管 理2,用 P,V操作来实现 Send原语
procedure send(receiver,a)
begin
getbuf(a.size,i);
i.sender:=a.sender;
i.size:=a.size;
i.text:=a.text;
i.next:=0;
getid(PCB set,receiver.j);
P(j.mutex);
insert(j.mq,i);
V(j.mutex);
V(j.sm);
end
根据 a.size申请缓冲区 i;
将发送区 a中的信息复制
到消息缓冲区之中 ;
获得接收进程内部标识符 ;
将消息缓冲区插入消息队列 ;
第二章 进 程 管 理3,用 P,V操作来实现 Receive原语
procedure receive(b)
begin
j:=internal name;
P(j.sm);
P(j.mutex);
remove(j.mq,i);
V(j.mutex);
b.sender:=i.sender;
b.size:=i.size;
b.text:=i.text;
release i;
end
j
将消息缓冲区 i中的信
息复制到接收区 b;
将消息缓冲 i 归还给系统 ;
第二章 进 程 管 理
mq
mutex
sm
Send(B,a)
sender:A
size,5
text:Hello
sender:A
size,5
text:Hello
next:0
receive(b)
sender:A
size,5
text:Hello
发
送
区
a
进程 A 进程 B
接
收
区
b
PCB(B)
第一消息缓冲区
ba
第二章 进 程 管 理
2.7 线 程
线程的引入,
? 引入进程的目的是为了使多个程序并发执行, 以
改善资源利用率, 提高系统吞吐量 。
? 引入线程则是为了减少程序并发执行时的所付出
的时空开销。
进程的两个基本属性：
? 进程是一个可拥有资源的基本单位。
? 进程同时又是一个可独立调度和分派的基本单位。
第二章 进 程 管 理
线程的属性,
? 轻型实体,线程自己基本不拥有系统资源，只
拥有少量必不可少的资源：程序计数器、一组
寄存器、栈。
? 独立调度和分派的基本单位,在引入线程的 OS
中，线程是进程中的一个实体，是被系统独立
调度和分派的基本单位。
? 可并发执行,同一进程中的多个线程之间可以
并发执行，不同进程中的线程也能并发执行。
? 共享进程资源,它可与同属一个进程的其它线
程共享进程所拥有的全部资源。
第二章 进 程 管 理
引入线程的好处,
? 创建一个新线程花费时间少（结束亦如此）；
? 两个线程的切换花费时间少；
? 因为同一进程内的线程共享内存和文件，因此
它们之间相互通信无须调用内核；
? 适合多处理机系统。
第二章 进 程 管 理
线程与进程的比较：
? 线程具有进程的许多特征，故又称 轻型进程,
传统进程称 重型进程 。
? 从以下几方面对其做出比较：
（ 1） 调度
（ 2） 并发性
（ 3） 拥有资源
（ 4） 系统开销
第二章 进程管理
2.1 进程的基本概念
2.2 进程控制
2.3 进程同步
2.4 经典进程的同步问题
2.5 管程机制
2.6 进程通信
2.7 线程
第二章 进 程 管 理
2.1 进程的基本概念
2.1.1 前趋图
2.1.2 程序的顺序执行及其特征
2.1.3 程序的并发执行及其特征
2.1.4 进程的特征与状态
2.1.5 进程控制块
第二章 进 程 管 理
2.1.1 前趋图（ Precedence Graph）
是一个有向无循环图, 记为 DAG(Directed Acyclic
Graph),用于描述进程之间执行的前后关系 。
P1
P2
P3
P4
P5
P6
P7
P8 P9 结点有向边
直接前驱
直接后继
初始结点
终止结点
重量
例：具有九个结点的前趋图 P
i Pj
前趋关系,P1→P 2,P1→P 3,P1→P 4,P2→P 5,
P3→P 5,P4→P 6,P4→P 7,P5→P 8,P6→P 8,
P7→P 9,P8→P 9
第二章 进 程 管 理
S1
S2
S3
前驱图中不能存在循环关系。
如：
第二章 进 程 管 理
2.1.2 程序的顺序执行及其特征
各程序段间程序的顺序执行 如图：
在计算机系统中只有一个程序在运行，这个程
序独占系统中所有资源，其执行不受外界影响。一
道程序执行完后另一道才能开始。
I1 P1 O1 I2 P2 O2
作业 1 作业 2
第二章 进 程 管 理
一个程序段的多条语句的顺序执行：
S1 S2 S3
S1,a:=x+y
S2,b:=a-5
S3,c:=b+1
第二章 进 程 管 理
程序顺序执行的特征：
? 顺序性,一个程序开始执行必须要等到前一
个程序已执行完成 。
? 封闭性,程序一旦开始执行, 其计算结果不
受外界因素影响 。
? 可再现性,程序的结果与它的执行速度无关
（ 即与时间无关 ）, 只要给定相同的输入,
一定会得到相同的结果 。
第二章 进 程 管 理
2.1.3 程序的并发执行及其特征
1,程序的并发执行
所谓程序的 并发执行 是指：若干个程序同时在系统
中执行，这些程序的执行在时间上是重叠的，一个
程序的执行尚未结束，另一个程序的执行已经开始。
I1 I2 I3
C1 C2 C3
P1 P2 P3
I4
C4
P4
第二章 进 程 管 理
一个程序段的多条语句的并发执行：
S1,a:=x+2
S2,b:=y+5
S3,c:=a+b
S4,d:=c+6
S1
S3 S4
S2
第二章 进 程 管 理
程序并发执行的特征：
? 间断性
由于资源共享和相互合作，并发执行的程序间
形成了相互制约关系，导致程序的运行过程出现
“执行 —暂停 —执行”的现象。
? 失去封闭性
程序在并发执行时, 是多个程序共享系统中的
资源, 因此这些资源的状态将由多个程序来改变 。
? 不可再现性
由失去封闭性导致 。 同样的初始条件, 一个程
序的多次重复执行, 可得到不同的结果 。
第二章 进 程 管 理
例：程序 A,B，共享变量 N。代码如下：
程序 A
BEGIN
REPEAT
…
…
N,=N+1
…
…
UNTIL FALSE
END
程序 B
BEGIN
REPEAT
…
…
PRINT(N)
N:=0
…
UNTIL FALSE
END
第二章 进 程 管 理
两个程序以不同速度运行，可能出现三种情况：
?N:=N+1在 Print(N)和 N:=0之前
——N值分别为 N+1,N+1,0
?N:=N+1在 Print(N)和 N:=0之后
——N值分别为 N,0,1
?N:=N+1在 Print(N)和 N:=0之间
——N值分别为 N,N+1,0
思考：任何并发执行都是不可再现的吗？
第二章 进 程 管 理
并发执行的条件：
并发执行的条件：达到封闭性和可再现性。
并发执行失去封闭性的的原因是 共享资源的影响,
去掉这种影响就行了。 1966年，由 Bernstein给出并
发执行的条件。
将程序中任一语句或程序段 Pi划分为两个变量的
集合,R(pi)和 W(pi)。其中，
R(pi)={a1,a2,… an}，程序 pi在执行期间引用的
（读的）变量集，称为, 读集, 。
W(pi)={b1,b2,… bm}，程序 pi在执行期间改变的
（写的）变量集，称为, 写集, 。
第二章 进 程 管 理
Bernstein条件,
如果对于语句 p1,p2,如果同时满足以下
三个条件：
R(p1)∩W(p2) ={ }
R(p2)∩W(p1) ={ }
W(p1)∩W(p2) ={ }
则语句 p1,p2可以并发执行。
第二章 进 程 管 理
例如, 有如下四条语句：
S1,a,= x + y S2,b,= z + 1
S3,c,= a – b S4,w,= c + 1
其中,R(S1)={x,y} W(S1)={a}
R(S2)={z} W(S2)={b}
R(S3)={a,b} W(S3)={c}
R(S4)={c} W(S4)={w}
对于 S1和 S2,有：
R(S1)∩W(S2) ={ }, R(S2)∩W(S1) ={ },
W(S1)∩W(S2) ={ }
结论：语句 S1和 S2满足 Bernstein条件，可以并发执行。
其他语句之间自己分析。
第二章 进 程 管 理
2.1.4 进程的特征与状态
1,进程的定义
进程是操作系统中最基本、重要的概念。
是多道程序系统出现后，为了刻画系统内部出
现的 动态情况,描述系统内部各道程序的活动
规律引进的一个概念，所有多道程序设计操作
系统都建立在进程的基础上。
第二章 进 程 管 理
(1) 进程是程序的一次执行 。
(2) 进程是一个程序及其数据在处理机上顺序执
行时所发生的活动 。
(3) 进程是程序在一个数据集合上运行的过程,
它是系统进行资源分配和调度的一个独立单位 。
(4) 进程是进程实体的运行过程, 是系统进行资
源分配和调度的一个独立单位 。
(5) 进程是一个具有一定独立功能的程序关于某
个集合的一次运行活动。 (我国 78年庐山研讨会 )
第二章 进 程 管 理
2,进程同程序的比较：
? 进程是动态的, 程序是静态的,程序是有序代码的集
合；进程是程序的执行 。 通常进程不可在计算机之间
迁移；而程序通常对应着文件, 静态和可以复制 。
? 进程是暂时的, 程序是永久的,进程是一个状态变化
的过程, 是有一定生命期的；而程序可以作为一种软
件资料长久保存 。
? 进程与程序的组成不同,进程是由程序和数据, 进程
控制块三部分组成的 。
? 进程与程序的对应关系, 同一程序同时运行于若干个
数据集合上，它将属于若干个不同的进程。也就是说
同一程序可以对应多个进程；一个进程的执行也可以
涉及到一个或几个程序（调用）。
第二章 进 程 管 理
3,进程的特征：
? 结构特征,由程序段, 数据段, 进程控制块三部
分组成；
? 动态性,进程是程序的执行；
? 并发性,多个进程可同存于内存中, 能在一段时
间内同时运行；
? 独立性,独立运行的基本单位, 独立获得资源和
调度的基本单位；
? 异步性,各进程按各自独立的不可预知的速度向
前推进 。
第二章 进 程 管 理
4,进程的三种基本状态
? 不同系统设置的进程状态数目不同。
? 进程有三种基本状态：
1) 就绪状态,进程已获得除 CPU 以外的所有
必要资源，只要得到 CPU，便可立即执行。
2) 执行状态,进程已得到 CPU，其程序正在
CPU
3) 阻塞状态,正在执行的进程因某种事件 (如
I/O 请求 )的发生而暂时无法继续执行，只
有等相应事件完成后，才能去竞争 CPU。
第二章 进 程 管 理
进程的状态变迁图
执行
第二章 进 程 管 理
五状态进程模型
进程正常结束，
或因某种原因
被取消后,OS
释放出的进程。
刚刚建立的
进程，还未
送入就绪队
列。
执行新建态 终止态
第二章 进 程 管 理
5,七状态进程模型
引入挂起状态的原因：
? 终端用户的请求
? 父进程请求
? 负荷调节的需要
? 操作系统的需要
第二章 进 程 管 理
―挂起, 的实质 是使进程不能继续执行，即使
挂起后的进程处于就绪状态，它也不能参与对
CPU 的竞争。因此，称被挂起的进程处于静止状
态，相反，没被挂起的进程则处于活动状态。而
且，处于静止状态的进程，只有通过, 激活, 动
作，才能转换成活动状态。
进程挂起后,程序代码和数据集被调出到外存
的交换区中,腾出来的内存空间供其它进程使用。
第二章 进 程 管 理
激活
挂起
事件
发生
事件
发生 等待
事件
挂起
调度
超时
释放
激活
挂起
七状态进程模型
挂起
就绪态
挂起
阻塞态
就绪态
阻塞态
执行态 终止态
新建态
第二章 进 程 管 理
? 就绪态 （ ready）,进程在内存且可立即进入运
行状态 。
? 阻塞态 （ blocked）,进程在内存并等待某一个
事件的出现 。
? 挂起就绪态 （ ready suspend）,进程在外存,但
只要进入内存,即可运行 。
? 挂起阻塞态 （ blocked suspend）,进程在外存
并等待某一个事件的出现 。
第二章 进 程 管 理
【 思考题 】
? 有没有这样的状态转换，为什么？
阻塞 —运行
就绪 —阻塞
第二章 进 程 管 理
2.1.5 进程控制块 （ Process Control Block,PCB ）
1,进程控制块的作用
进程控制块的作用是使一个在多道程序环境
下不能独立运行的程序 (含数据 ),成为一个能独
立运行的基本单位, 一个能与其它进程并发执行
的进程 。 或者说, OS是根据 PCB来对并发执行
的进程进行控制和管理的 。
? 进程与 PCB是一一对应的。
? PCB应常驻内存。
第二章 进 程 管 理
2,进程控制块中的信息
? 进程标识符,用于惟一地标识系统中的每个进程。
另外，还可以用父进程的标识符及子进程的标识
符来描述进程的家族关系。
? 处理机状态,用于 CPU 切换时保存现场和恢复
现场，主要由处理机中各种寄存器的内容组成。
? 进程调度和控制信息,用于进程调度和控制，主
要包括进程状态、优先级、等待和使用 CPU 的
时间总和、程序和数据的地址、进程同步和通信
信息、资源清单和进程队列指针等。
第二章 进 程 管 理
3,进程控制块的组织方式
图 2-7 PCB链接队列示意图
在一个系统中通常有许多的 PCB，称为 PCB
集合 。
为了便于管理，系统必须用适当的方式将
PCB 组织起来，常用的方式有 链接方式 和 索引方
式 。
第二章 进 程 管 理
PCB1 4
PCB2
PCB3
PCB4
PCB5
PCB6
PCB7
PCB8
PCB9
3
0
8
7
9
0
1
执行指针
就绪队列指针
阻塞队列指针
空闲队列指针
…
1) 链接方式 相同状态的进程 PCB组成一个链表，不同状态对应多个不同的链表。
空指针
第二章 进 程 管 理
2) 索引方式
执行指针
就绪索引表
PCB1
PCB2
PCB3
PCB4
PCB5
PCB6
PCB7
阻塞索引表
就绪表指针
阻塞表指针
对具有相同状态的进程，分别设置各自的
PCB索引表，表明 PCB在 PCB表中的地址。
第二章 进 程 管 理
2.2 进 程 控 制
2.2.1 进程的创建
2.2.2 进程的终止
2.2.3 进程的阻塞与唤醒
2.2.4 进程的挂起与激活
第二章 进 程 管 理
进程控制是进程管理中最基本的功能，它用
于创建和撤消进程，并对进程在整个生命周期中
各种状态之间的转换进行有效控制。
进程控制是由 操作系统的内核 通过 原语 来实
现的。
原语,系统状态下执行的某些具有特定功能
的程序段称为原语。 (原语的执行具有原子性，
执行时不可分割 )。
第二章 进 程 管 理
2.2.1 进程的创建
1,进程图 (Process Graph),
用于描述一个进程的家族关系的有向树。
第二章 进 程 管 理
D E F G H
B C
I J K L M
A
祖先进程
父进程
子进程
? 子进程可以继承父进程的所有资源，当子进程被撤
消时，应将从父进程那里获得的资源归还给父进程。
? 撤消父进程时也必须同时撤消其所有的子进程。
第二章 进 程 管 理
2,引起创建进程的事件
(1) 用户登录。
(2) 作业调度。
(3) 提供服务。
(4) 应用请求。
第二章 进 程 管 理
3,进程的创建 (Creation of Progress)
(1) 申请空白 PCB。
(2) 为新进程分配资源。
(3) 初始化进程控制块。
(4) 将新进程插入就绪队列。
创建新进程通过 进程创建原语 creat（） 来完成。
进程创建原语的主要任务是 创建进程控制块 PCB。
第二章 进 程 管 理入 口
查 PCB链表
有空 PCB？
取空 PCB（ i）
将有关参数填入 PCB（ i）相应项
PCB（ i）入就绪队列
PCB(i)入进程家族或进程链
创建失败
返 回
创
建
原
语
流
程
图
N
Y
第二章 进 程 管 理
2.2.2 进程的终止
当某进程实现完成任务正常结束时, 或在运
行过程中遇到某些异常情况 （ 如越界错误, 非法
指令, 运行超时等 ）, 或外界干预需要结束时,
应予以终止 （ 撤消 ） 。 （ 参见 P35）
通过 进程终止原语 来终止进程 。
终止进程的实质是 收回 PCB。
第二章 进 程 管 理
(1) 查找对应的 PCB
(2) 终止该进程及子孙进程
(3) 释放资源
(4) 释放 PCB
第二章 进 程 管 理
终
止
原
语
流
程
图
入 口
查进程链表或进程家族
有此 PCB吗？
释放该进程所占有的资源
出错处理该 PCB有子进程吗？
释放该 PCB结构本身
Y
Y
N
N
返 回
第二章 进 程 管 理
2.2.3 进程的阻塞与唤醒
1,
当正在执行的进程需要等待某种事件的完成
或本身无新工作可做时, 应调用阻塞原语将自己
从执行状态转换成阻塞状态 。
进程阻塞是进程的一种主动行为。通过 阻塞原
语 block（） 来完成。
具体的操作过程是：停止进程的执行，将其状
态改为阻塞状态，并把它的 PCB 插入相应的阻塞
（等待）队列，转调度程序进行重新调度。
第二章 进 程 管 理
阻
塞
原
语
流
程
图
保存当前进程的 CPU现场
置该进程的状态
被阻塞进程入阻塞队列
转进程调度
入 口
第二章 进 程 管 理
2.
当阻塞进程所等待的事件完成时, 应调用
唤醒原语将该进程的状态从阻塞状态转换成就
绪状态 。 通过 唤醒原语 wakeup（ ） 来完成 。
处于阻塞状态的进程是绝不可能叫醒自己
的, 必须由它的合作进程用唤醒原语唤醒它 。
具体的操作过程是：在等待队列中移出该
进程的 PCB,将其置成就绪状态, 并把它插入
就绪队列 。
第二章 进 程 管 理
唤
醒
原
语
流
程
图
从等待队列中摘下被唤醒进程
将被唤醒进程置为就绪态
将被唤醒进程送入就绪队列
转进程调度或返回
入 口
第二章 进 程 管 理
2.2.4 进程的挂起与激活
1、进程的挂起
当出现了引起进程挂起的事件时，用户请求将自
己挂起，或者父进程请求挂起自己的子进程。系统
通过 挂起原语 suspend（） 将指定进程挂起。
具体的执行过程：检查被挂起进程的状态，如果
处于活动就绪状态，就将它改为静止就绪；如果处
于活动阻塞，则改为静止阻塞。将 PCB 复制到指定
的内存区域供用户或父进程考查。若挂起前进程正
在执行，则转调度程序重新进行进程调度。
第二章 进 程 管 理
2、进程的激活
当发生激活事件后，系统利用 激活原语 Active( )
将指定进程激活。
具体的操作过程是：若进程处于静止阻塞状态，
则将它转换成活动阻塞状态，否则将它转换成活动
就绪状态。若进程转换成活动就绪状态，而系统又
采用抢占调度策略，则应检查该进程是否有权抢占
CPU，若有则应进行进程调度。
第二章 进 程 管 理
2.3 进 程 同 步
2.3.1 进程同步的基本概念
2.3.2 信号量机制
2.3.3 信号量的使用
第二章 进 程 管 理
进程同步 是指对多个相关进程在执行次序
上进行协调。
进程同步的 主要任务 是使并发执行的诸进
程之间能有效的共享资源和相互合作，从而使
程序的执行具有可再现性。
第二章 进 程 管 理
1,两种形式的制约关系
? 间接相互制约关系
互斥关系，资源共享关系
? 直接相互制约关系
同步关系，相互合作关系
2.3.1 进程同步的基本概念
第二章 进 程 管 理
2,临界资源
一次仅允许一个进程访问的资源。如：进程Ａ、
Ｂ共享一台打印机，若让它们交替使用则得到的
结果肯定不是我们希望的。
临界资源可能是硬件，也可能是软件：变量，
数据，表格，队列等。
并发进程对临界资源的访问必须作某种限制，
否则就可能出现错误，如：联网售票，会出现与
时间有关的错误。
第二章 进 程 管 理
例：两进程共享一个变量 COUNT
P1,R1:=COUNT;
R1:=R1+1;
COUNT:=R1;
P2,P2:=COUNT;
R2:=R2+1;
COUNT:=R2;
试比较两进程顺序执行和并发执行的结果。
第二章 进 程 管 理
若 P1,P2按如下顺序
并发执行：
P1,R1:=COUNT;
P2,R2:=COUNT;
P1,R1:=R1+1;
COUNT:=R1;
P2,R2:=R2+1;
COUNT:=R2;
若 P1,P2顺序执行：
P1,R1:=COUNT;
R1:=R1+1;
COUNT:=R1;
P2,R2:=COUNT;
R2:=R2+1;
COUNT:=R2;
第二章 进 程 管 理
3,临界区 (Critical Section)
每个进程中，访问临界资源的那段代码称为
临界区 。
诸进程对临界资源的互斥访问就变为怎样使
诸进程互斥地进入临界区。
互斥的实质就是同步，或者说，互斥是同步
的一种特殊形式。
第二章 进 程 管 理
访问临界资源的循环进程描述如下：
REPEAT
ENTRY SECTION
CRITICAL SECTION
EXIT SECTION
REMAINDER SECTION
UNTIL FALSE
进入区
临界区
退出区
剩余区
第二章 进 程 管 理
4,同步机制应遵循的原则
用来实现互斥的同步机制必须遵循下述四条
准则：
(1) 空闲让进。
(2) 忙则等待。
(3) 有限等待。
(4) 让权等待。
第二章 进 程 管 理
2.3.2 信号量机制
信号量机制是荷兰学者 Dijkstra在 1965年
提出的一种卓有成效的同步工具，在长期且广
泛的应用中，已由早期的整型信号量发展为记
录型信号量，进而发展为信号量集。
第二章 进 程 管 理
1,整型信号量
整型信号量是一个非负的共享整数，除了初始化
外，它只能通过两个标准的原子操作 wait 和 signal 来
访问，即 P,V操作 。
wait和 signal
wait(S),while S≤0 do no-op
S∶ =S-1;
signal(S),S∶ =S+1;
整型信号量的主要问题是，只要 S≤0,wait 操作
就会不断地测试，因而，没能做到“让权等待”。
第二章 进 程 管 理
2,记录型信号量
记录型信号量中除了一个整型变量 value 外，还
增加了一个等待队列指针 L。记录型信号量采用了
记录型的数据结构，描述为：
type semaphore=record
value:integer;
L:list of process;
end
第二章 进 程 管 理
相应的 wait 和 signal 操作（即 P,V操作）可描述为：
procedure P(S)
var S,semaphore;
begin
S.value:=S.value-1;
if S.value＜ 0 then block(S.L)
end
当 S.value＜ 0 时，进程会立即将自己阻塞，因
此解决了整型信号量的“忙等”问题，做到了“让
权等待”。
该进程状态置为
阻塞状态；放弃
处理机；将该进
程的 PCB插入链
表 S.L中。
第二章 进 程 管 理
procedure V(S)
var S,semaphore;
begin
S.value:=S.value+1;
if S.value≤0 then wakeup(S.L)
end
唤醒 S.L链表 中的第
一个等待进程；改变
状态为就绪态；将其
插入就绪队列中。
第二章 进 程 管 理
? 一个信号量通常对应于一类临界资源，在使用
前，信号量必须经过定义并赋适当的初值，初值
表示系统中某类资源的数目。初值为 1表示对临界
资源进行访问，此时信号量转化为互斥信号量。
? 每次对信号量进行 wait 操作意味着申请一个单
位的该类资源,signal 操作意味着归还一个单位的
该类资源。
? 当 S.value＞ 0 时，它的值表示系统中该类资源
当前可用的数目； S.value≤0 时，表示该类资源已
分配完毕，其绝对值表示系统中因申请该类资源
而阻塞在 S.L 队列上的进程数目。
必须注意的几个问题：
第二章 进 程 管 理
2.3.3 信号量的使用
? 必须置一次且只能置一次初值
? 初值为整数，且不能为负数
? 只能执行 P,V操作
第二章 进 程 管 理
1,用信号量实现进程互斥
P(mutex)
V(mutex)
P1 P2 P3
互斥区
P(mutex)
P(mutex)
V(mutex)
V(mutex)
第二章 进 程 管 理
PA:
…
P(mutex);
critical section;
V(mutex);
…
PB:
…
P(mutex);
critical section;
V(mutex);
…
? mutex用于实现互斥，初值为 1。在每个进程中将
临界区代码置于 P(mutex)和 V(mutex)之间。
模
型
：
第二章 进 程 管 理
模
拟
执
行
：
序号 PA PB mutex 说明
0 1
1 P(mutex) 0 PA进入，占资源
2 P(mutex) -1 PB进入，无资源
3 V(mutex) 0 PA释放资源，PB解封
4 V(mutex) 1 PB释放资源
0 可反复执行
第二章 进 程 管 理
? 对于两个并发进程，互斥信号量的值仅取 1,0 和 -
1三个值：
若 mutex＝ 1表示没有进程进入临界区；若 mutex
＝ 0表示有一个进程进入临界区；若 mutex＝ -1表示一
个进程进入临界区，另一个进程等待进入。
? 当实现 n个进程并发时，互斥信号量的取值为 1,0、
-1,…, -(n-1)。
? P,V操作必须成对出现：遗漏 P(mutex)将不能保
证互斥访问，遗漏 V(mutex)将不能再使用临界资源之
后将其释放（给其他等待的进程）。
第二章 进 程 管 理
PA:
…
L1,P(proceed)
…
2,用信号量实现同步
PB:
…
L2,V(proceed)
…
? proceed用于实现同步，初值为 0。 PA在 L1点必
须与 PB在 L2点同步,PA受 PB的制约，而 PB不受
PA的制约，使非对称的。
? P,V操作必须成对出现,当用于实现互斥时，
它们同处于同一进程；当用于实现同步操作时，则
不在同一进程中出现。
模
型
：
第二章 进 程 管 理
3,利用信号量描述前趋关系
信号量可用来描述程序或语句之间的前趋
关系。
若 Pi是 Pj的直接前趋，即 Pi→Pj,则可设
置一个初值为 0 的公用信号量 S，并将 V(S)操
作放在 Pi后，而在 Pj前插入 P(S)操作，以保证
Pi在 Pj开始执行之前完成。
Pi Pj
第二章 进 程 管 理
Var a,b,c,d,e,f,g:semaphores;
Begin
parbegin
begin s1;v(a);v(b);end;
begin p(a);s2;v(c);end;
begin p(c);s4;v(e);v(f);end;
begin p(b);s3; v(d);end;
begin p(e);s5; v(g);end;
begin p(f);p(d);s6;v(h);end;
begin p(g);p(h);s7;end;
Parbegin
end
s1
s2 s3
s4
s5 s1s6
s7
a b
c
d
e f
g h
例：
第二章 进 程 管 理
2.4 经典进程的同步问题
2.4.1 生产者 —
2.4.2 哲学家进餐问题
2.4.3 读者 ——写者问题
第二章 进 程 管 理
2.4.1 生产者 —消费者问题
一次只可放一个产品
生产者 消费者
?只要仓库未满，生产者就可以把产品放入仓库。
?只要仓库未空，消费者就可以从仓库中取走物品。
问题描述：
第二章 进 程 管 理
inout
0
1
2345
6
7
8 9 10 11
? in,下一个可供投放产品的缓冲区,in:=(in+1)mod n；
out:下一个可供获取产品的缓冲区,out:=(out+1)mod n。
? 若 (in+1)mod n = out，有界缓冲区满；
若 in = out，有界缓冲区空。
环形缓冲池
设一个长度为 n的有界缓冲区：
（以 n=12为例）
第二章 进 程 管 理
问题分析,这是一个同步与互斥共存的问题。
1,生产者 —消费者问题是一个同步问题。即生产者
和消费者之间满足如下条件：
----消费者想接收数据时，有界缓冲区中至少有一
个单元是满的。
----生产者想发送数据时，有界缓冲区中至少有一
个单元是空的。
故设置两个信号量：
---- empty：说明空缓冲区的数目，初值为有界缓
冲区的大小 N。
---- full：说明已用缓冲区的数目，初值为０。
第二章 进 程 管 理
2,由于有界缓冲区是临界资源，因此，各生产者
进程和各消费者进程之间必须互斥执行。
故设置一个互斥信号量 mutex，其初值为１。
第二章 进 程 管 理
问题的解：
Var medex,empty,full:semaphore;
buffer:array[0,1,…n -1] of item;
in,out:integer;
Begin
metex:=1;
empty:=n; full:=0;
in:=0; out:=0;
Parbegin
procedure,… …
consumer,… …
Parend
end
第二章 进 程 管 理
Consumer：
begin
repeat
P(full);
P(mutex);
从 Buffer[out]取产品 ;
out = (out +1) mod n;
V(mutex);
V(empty);
…
消费产品 ;
…
until false;
end
Producter：
begin
repeat
…
生产产品 ;
…
P(empty);
P(mutex);
往 Buffer [in]放产品 ;
in= (in+1) mod n;
V(mutex);
V(full);
until false;
end
第二章 进 程 管 理
? 有五个哲学家围坐在一
圆桌旁，桌中央有一盘
通心粉，每人面前有一
只空盘子，每两人之间
放一只筷子。
2.4.2 哲学家就餐问题
问题描述：
? 每个哲学家的行为是思考，感到饥饿，然后吃通心
粉；吃完后继续思考。
? 为了吃通心粉，每个哲学家必须拿到两只筷子，并
且每个人只能直接从自己的左边或右边去取筷子。
第二章 进 程 管 理
问题的解,repeat
P(fork[i]);
P(fork[(i+1) mod 5])；
…
进食；
…
V(fork[i]);
V(fork[(i+1) mod 5])；
…
思考；
…
until false
设 fork[5]为 5 个信号
量（分别表示每支筷
子），初值均为 1。
此解可以保证互斥使
用筷子，但会产生死
锁。
第二章 进 程 管 理
为防止死锁发生可采取的措施：
? 最多允许 4个哲学家同时去拿左边的筷子；
? 仅当一个哲学家左右两边的筷子都可用时，才
允许他拿筷子进餐； （ ?）
? 给所有哲学家编号，奇数号的哲学家必须首先
拿左边的筷子，偶数号的哲学家则反之。
第二章 进 程 管 理
信号量集 ——AND型信号量集
? AND型信号量集的基本思想：
在一个原语中申请整段代码需要的多个临
界资源，要么全部分配给它，要么一个都不分
配。
? AND型信号量集 P原语为 Swait；
AND型信号量集 V原语为 Ssignal。
第二章 进 程 管 理
采用 AND信号量集解决哲学家就餐问题
repeat
Swait( fork[i],fork[(i+1) mod 5] )；
…
进食；
…
Ssignal( fork[i],fork[(i+1) mod 5] )；
…
思考；
…
until false
设 fork[5]
为 5 个信
号量（分
别表示每
支筷子），
初值为均
1。
第二章 进 程 管 理
2.4.3 读者 -写者问题
问题描述：
有两组并发进程 ——读者和写者，共享一组数
据区。要求：
? 允许多个读者同时执行读操作；
? 任一写者在完成写操作之前不允许其它读者或
写者工作 (读写文件 )；
? 写者执行写操作前，应让已有的写者和读者全
部退出。
第二章 进 程 管 理
? 如果读者来：
– 若无读者、写者，则新读者可以读；
– 若有写者等待，但有其它读者正在读，则新
读者也可以读；
– 若有写者写，则新读者等待。
? 如果写者来：
– 若无读者，则新写者可以写；
– 若有读者，则新写者等待；
– 若有其它写者，则新写者等待。
问题分析：
第二章 进 程 管 理
问题的解：
? 整形变量 readcount表示正在读的读者数目，初值
为 0。
? 信号量 w用于保证读者和写者、写者和写者之间
的互斥,初值为 1。
? 信号量 mutex用于保证对 readcount 这个临界资源
的互斥修改，初值为 1。
第二章 进 程 管 理读者：
begin
repeat
P(mutex);
readcount,= readcount+1;
if readcount=1 then P (w);
V(mutex);
…
执行读操作；
…
P(mutex);
readcount,= readcount-1;
if readcount=0 then V(w);
V(mutex);
until false
end
写者：
begin
repeat
P(w);
执行写操作；
V(w);
until false
end
第二章 进 程 管 理
【 思考题 】
桌上有一空盘，最多允许存放一只水果。爸爸
可向盘中放一个苹果或放一个桔子，儿子专等吃盘
中的桔子，女儿专等吃苹果。
试用 P,V操作实现爸爸、儿子、女儿三个并发
进程的同步与互斥。
提示,设置一个信号量表示可否向盘中放水果，一
个信号量表示可否取桔子，一个信号量表示可否取
苹果。
第二章 进 程 管 理问题的解：
Daughter:
repeat
P(Sa)；
取苹果；
V(S);
吃苹果 ;
until false
Son:
repeat
P(So)；
取桔子；
V(S);
吃桔子 ;
until false
Father:
repeat
P(S);
将水果放入盘中 ;
if 桔子
then V(So);
else V(Sa);
until false
设置三个信号量 S,So,Sa，初值分别为 1,0,0。
分别表示可否向盘中放水果，可否取桔子，可否取
苹果。
第二章 进 程 管 理
【 思考题 】
有一个仓库，可以存放 A和 B两种产品，但要求：
（ 1） 每次只能存入一种产品（ A或 B）；
（ 2） － N＜ A产品数量－ B产品数量＜ M；
其中,N和 M是正整数。试用 P,V操作描述产品
A与 B的入库过程。
提示,设两个信号量 Sa,Sb。 Sa表示允许 A产品比 B
产品多入库的数量； Sb表示允许 B产品比 A产品多入
库的数量
第二章 进 程 管 理
? 设两个信号量 Sa,Sb,初值分别为 M-1,N-1
--- Sa表示允许 A产品比 B产品多入库的数量
--- Sb表示允许 B产品比 A产品多入库的数量
? 设互斥信号量 mutex，初值为 1。
问题的解：
第二章 进 程 管 理
B产品入库进程：
repeat
P(Sb);
P(mutex);
B产品入库
V(mutex);
V(Sa);
…
消费产品 ;
…
until false
A产品入库进程：
repeat
…
生产产品 ;
…
P(Sa);
P(mutex);
A产品入库
V(mutex);
V(Sb);
until false
第二章 进 程 管 理
2.5 管 程 机 制
2.5.1 管程的基本概念
2.5.2 利用管程解决生产者 -消费者问题
第二章 进 程 管 理
2.5.1 管程的基本概念
为什么引入管程？
? 把分散在各进程中的临界区集中起来进行管理；
? 防止进程有意或无意的违法同步操作；
? 便于用高级语言来书写程序, 也便于程序正确性
验证 。
管程的基本概念：
一个管程定义了 一个数据结构 和能为并发进程所
执行（在该数据结构上）的 一组操作,这组操作能同
步进程和改变管程中的数据。
第二章 进 程 管 理
管程的特点：
(1) 管程内的局部变量只能被局部于管程内的过
程所访问；反之亦然，即局部于管程内的过程只能
访问管程内的变量。
(2) 任何进程只能通过调用管程提供的过程入口
进入管程。
(3) 任一时刻，最多只能有一个进程在管程中执
行。
第二章 进 程 管 理
type monitor-name=monitor
variable declarations
procedure entry P1(…);
begin … end;
procedure entry P2(…);
begin … end;
…
procedure entry Pn(…);
begin … end;
begin
initialization code;
end
管程的语法
局部于管程的
共享变量说明
对该数据结构
进行操作的一
组过程
对局部于管程
的数据设置初
始值
管程的组成部分
第二章 进 程 管 理
共享数据
…
一组操作过程
初始化代码
进入队列条件 (不忙 )队列
管程的示意图：
第二章 进 程 管 理
当进程通过管程请求临界资源未能满足时，将
排在队列上等待。等待的原因可能有多个，为了区
分它们，引入条件变量 condition 。每个 condition
表示一种等待原因。
针对条件变量 x,x.wait将自己阻塞在 x队列中，
x.signal将 x队列中的一个进程唤醒。
条件变量：
第二章 进 程 管 理
2.5.2 利用管程解决生产者 -消费者问题
PC管程描述：
Type
Producer-Consumer=monitor
Var
buffer,array[0,…,n-1] of item；
count,in,out,integer；
notempty,notfull,condition；
第二章 进 程 管 理
procedure entry put(item);
begin
if count>=n then notfull.wait;
buffer(in):=nextp;
in:=(in+1) mod n;
count:=count+1；
if notempty.queue then notempty.signal;
end;
procedure entry get(item);
begin
if count<=0 then notempty.wait;
nextc:=buffer(out);
out:=(out+1) mod n;
count:=count-1；
if notfull.queue then notfull.signal;
end;
Begin in:=0; out:=0;count:=0 End
第二章 进 程 管 理
producer：
begin
repeat
produce an item；
PC,put(item)；
until false；
end
consumer：
begin
repeat
PC,get (item)；
consume the item；
until false;
end
生产者和消费者描述：
第二章 进 程 管 理
2.6 进 程 通 信
2.6.1 进程通信的类型
2.6.2 消息缓冲队列通信机制
第二章 进 程 管 理
进程之间互相交换信息的工作称为 进程通信 。
进程通信的类型,
? 低级通信,归结为进程之间的互斥和同步，一般
只传送少量信息（信号量）。缺点：效率低，通
信对用户不透明。
? 高级通信,能够高效传输大量数量数据的通信方
式。又分为三类：共享存储器系统、消息传递系
统、管道通信系统。
2.6.1 进程通信的类型
第二章 进 程 管 理
1,共享存储器系统
相互通讯的进程通过 共享数据结构 和 共享存储
区 进行通讯，可进一步分为：
? 基于共享数据结构的通信方式
进程之间通过某种数据结构，如缓冲池进行通
信，属于低级通信方式。如生产者 -消费者问题中
的有界缓冲区。
? 基于共享存储区的通信方式
为了传送大量信息，在存储器中划出一块共享
存储区，诸进程可通过对共享存储区进行读或写
来实现通信，属高级通信方式。
第二章 进 程 管 理
2,消息传递系统
? 使用最广泛的一种进程通信机制。
? 进程间的数据交换以消息或报文为单位，程序
员直接利用一组通信命令（原语）来实现通信。
? 操作系统隐藏了通信的实现细节，简化了通信
程序编制的复杂性。
第二章 进 程 管 理
（ 1） 直接通信方式
两条通信原语：
Send（ Receiver,message） ;
Receive（ Sender,message） ;
例如,Send（ p2,m1） ;
Receive（ p1,m1） ;
发送进程可直接将消息发送给目标进程。
消息传递系统的分类：
——直接通信方式和间接通信方式
第二章 进 程 管 理
repeat
…
produce an item in nextp;
…
send(consumer,nextp);
until false;
利用直接通信原语解决生产者 -消费者问题：
repeat
receive(producer,nextc);
…
consume the item in nextc;
until false;
producer：
consumer：
第二章 进 程 管 理
（ 2）间接通信方式
进程间发送或接收消息通过信箱进行，消息
可被理解成信件。也称信箱通信。
两条通信原语：
Send（ mailbox,message）；
Receive（ mailbox,message）；
注意,用户不必写出接收进程标识符，从而
可以向不知名的进程发送消息；另外，消息在信
箱中可以安全的保存，只允许核准的目标用户随
时读取，可实现非实时通信。
第二章 进 程 管 理
发送
进程 A … 邮箱体
邮箱头
接收
进程 B
? 信箱由 信箱头 和由若干格子组成的 信箱体 组成。
? 信箱中每个格子存放一封信，信箱中格子的数目
和每格的大小在创建信箱时确定。
? 进程间的通信要满足如下条件：
a,发送进程发送消息时，邮箱中至少要有一个空
格存放该消息。
b,接收进程接收消息时，邮箱中至少要有一个消
息存在。
第二章 进 程 管 理
3,管道（ Pipe）通信系统
? 所谓 管道,是指用于连接一个读进程和一个写
进程以实现它们之间通信的一个共享文件，又称
pipe文件。
? 发送进程以字符流形式把大量数据送入管道，
接收进程从管道中接收数据，所以叫 管道通信 。
? 管道的实质是 一个共享文件,基本上可借助于
文件系统的机制实现，包括（管道）文件的创建、
打开、关闭和读写。
第二章 进 程 管 理
读写进程相互协调，必须做到：
? 互斥,进程对通信机构的使用应该互斥，一个
进程正在使用某个管道写入或读出数据时，另一
个进程就必须等待。
? 同步,管道长度有限,发送信息和接收信息之间
要实现正确的同步关系。当写进程把一定数量的
数据写入 pipe，就去睡眠等待，直到读进程取走
数据后，把它唤醒。
? 确定对方是否存在,发送者和接收者双方必须
能够知道对方是否存在，如果对方已经不存在，
就没有必要再发送信息。
第二章 进 程 管 理
写进程 共享文件 读进程
管道通信的思想：
（ 1） 发送进程可以源源不断的从 pipe一端写入
数据流, 在规定的 pipe文件的最大长度 （ 如 4096
字节 ） 范围内, 每次写入的信息长度是可变的；
（ 2） 接收进程在需要时可以从 pipe的另一端读
出数据, 读出单位长度也是可变的 。
第二章 进 程 管 理
2.6.2 消息缓冲队列通信机制
? 消息缓冲队列通信机制通过内存中公用的消息
缓冲区进行进程通信，属于直接通信方式。
? 发送进程利用 send原语将消息直接发送给接收
进程；接收进程利用 receive原语接收消息。
第二章 进 程 管 理
（ 1）消息缓冲区的数据结构
type message Buffer = record
sender； 发送者 ID;
size； 消息长度 ;
text； 消息正文 ;
next； 消息队列指针 ;
end
1,消息缓冲队列通信机制中的数据结构
第二章 进 程 管 理
（ 2） PCB中有关通信的数据项
type PCB=record
…
mq ; 消息队列首指针 ;
mutex; 消息队列互斥信号量 ;
sm ; 消息队列资源信号量 ;
…
end
第二章 进 程 管 理2,用 P,V操作来实现 Send原语
procedure send(receiver,a)
begin
getbuf(a.size,i);
i.sender:=a.sender;
i.size:=a.size;
i.text:=a.text;
i.next:=0;
getid(PCB set,receiver.j);
P(j.mutex);
insert(j.mq,i);
V(j.mutex);
V(j.sm);
end
根据 a.size申请缓冲区 i;
将发送区 a中的信息复制
到消息缓冲区之中 ;
获得接收进程内部标识符 ;
将消息缓冲区插入消息队列 ;
第二章 进 程 管 理3,用 P,V操作来实现 Receive原语
procedure receive(b)
begin
j:=internal name;
P(j.sm);
P(j.mutex);
remove(j.mq,i);
V(j.mutex);
b.sender:=i.sender;
b.size:=i.size;
b.text:=i.text;
release i;
end
j
将消息缓冲区 i中的信
息复制到接收区 b;
将消息缓冲 i 归还给系统 ;
第二章 进 程 管 理
mq
mutex
sm
Send(B,a)
sender:A
size,5
text:Hello
sender:A
size,5
text:Hello
next:0
receive(b)
sender:A
size,5
text:Hello
发
送
区
a
进程 A 进程 B
接
收
区
b
PCB(B)
第一消息缓冲区
ba
第二章 进 程 管 理
2.7 线 程
线程的引入,
? 引入进程的目的是为了使多个程序并发执行, 以
改善资源利用率, 提高系统吞吐量 。
? 引入线程则是为了减少程序并发执行时的所付出
的时空开销。
进程的两个基本属性：
? 进程是一个可拥有资源的基本单位。
? 进程同时又是一个可独立调度和分派的基本单位。
第二章 进 程 管 理
线程的属性,
? 轻型实体,线程自己基本不拥有系统资源，只
拥有少量必不可少的资源：程序计数器、一组
寄存器、栈。
? 独立调度和分派的基本单位,在引入线程的 OS
中，线程是进程中的一个实体，是被系统独立
调度和分派的基本单位。
? 可并发执行,同一进程中的多个线程之间可以
并发执行，不同进程中的线程也能并发执行。
? 共享进程资源,它可与同属一个进程的其它线
程共享进程所拥有的全部资源。
第二章 进 程 管 理
引入线程的好处,
? 创建一个新线程花费时间少（结束亦如此）；
? 两个线程的切换花费时间少；
? 因为同一进程内的线程共享内存和文件，因此
它们之间相互通信无须调用内核；
? 适合多处理机系统。
第二章 进 程 管 理
线程与进程的比较：
? 线程具有进程的许多特征，故又称 轻型进程,
传统进程称 重型进程 。
? 从以下几方面对其做出比较：
（ 1） 调度
（ 2） 并发性
（ 3） 拥有资源
（ 4） 系统开销
