1
第二章进程的描述与控制
OS的基本任务是对“进程”的管理；
多个进程可以并发执行；
进程在系统中有多种状态，状态间
可转换；
进程与线程的区别。
操
作
系
统
|
进
程
的
描
述
与
控
制
2
CUIT 徐虹
2．1前趋图和程序执行
?前趋图的定义
?前趋图（Procedence Graph）是一个有向
无循环图DAG（Directed Acyclic Graph）。
?结点：语句、程序段或进程。
?初始节点
?终止节点
?边：执行顺序。
?重量：程序量或执行时间。
2
操
作
系
统
|
进
程
的
描
述
与
控
制
3
CUIT 徐虹
1
2
3
4
5
6
7
例：有7个结点的前趋图。
P = { P1，P2，P3，P4，P5，P6，P7 }
→= {（P1，P2），（P1，P3），（P1，P4），（P2，P5），
（P3，P5），（P4，P6），（P5，P7），（P6，P7）}
操
作
系
统
|
进
程
的
描
述
与
控
制
4
CUIT 徐虹
?程序的顺序执行
?一个复杂的程序通常可以分为若干程序
段，并且必须按照某种先后次序来执行。
?例1：输入——计算——打印
?例2：语句执行顺序
?S1：a ：= x + y
?S2：b ：= a – 5
?S3：c ：= b + 1
3
操
作
系
统
|
进
程
的
描
述
与
控
制
5
CUIT 徐虹
?顺序执行程序的特点：
?程序的顺序性。
?程序在运行时独占主机资源。
?程序的执行结果与其执行速度无关。
?程序执行时的初始条件相同，其结
果必相同。
操
作
系
统
|
进
程
的
描
述
与
控
制
6
CUIT 徐虹
?程序的并发执行
?程序执行环境
?独立性，逻辑上是独立的。
?随机性：输入和执行开始时间都是随机的。
?资源共享：资源共享导致对进程执行速度
的制约。
4
操
作
系
统
|
进
程
的
描
述
与
控
制
7
CUIT 徐虹
?程序的并发执行
并发执行是指两个程序执行时间上是重叠
的。凡是能由一组并发程序完成的任务，都
能由相应的单个程序完成。
例1：有一批程序，而每个程序需输入，计算，
打印三项操作。其程序段并发执行的前趋图:
I1 →I2 →I3 →I4 →
↘↘↘↘
C1 →C2 →C3 →C4 →
↘↘↘↘
P1 →P2 →P3 →P4 →
操
作
系
统
|
进
程
的
描
述
与
控
制
8
CUIT 徐虹
例2．Begin integer N:=0;
Cobegin
Program A : begin Program B : begin
L1 : N:=N+1; L2 : Print (N); N:=0;
Goto L1；Goto L2；
End End
Coend End
当N=5时，如果N=N+1 在print（N）和N:=0
前中间后
打印655
执行后N=001
5
操
作
系
统
|
进
程
的
描
述
与
控
制
9
CUIT 徐虹
例3．设有堆栈S，栈指针top ，栈中存放相应的数
据块地址，程序getaddr（top）从栈中取地址，
reladdr（blk）将地址放入栈S中。
Procedure getaddr (top) Procedure reladdr(blk)
Begin begin
Local r top+1——> top
(top)——> r blk ——> (top)
top-1——> top end
return (r)
end
先执行reladdr 的top=top+1，接着执行getaddr的(top)—> r
操
作
系
统
|
进
程
的
描
述
与
控
制
10
CUIT 徐虹
?程序并发执行过程及条件
（Bernstein条件）
S0;
Cobegin
S1；S2；S3；……；Sn;
Coend
Sn+1;
S1、S2、……、Sn可以由同一程序段
中的不同语句组成。
6
操
作
系
统
|
进
程
的
描
述
与
控
制
11
CUIT 徐虹
将任一语句划分为两个变量的集合R
（Si）和W（Si）:
读集R（Si）= {a1，a2，……，am}
写集W（Si）= {b1，b2，……，bn}
如对语句S1和S2有：
R（S1）∩W（S2）= {Ф}
W（S1）∩R（S2）= {Φ}
W（S1）∩W（S2）= {Φ}
成立，则语句S1和S2可并发执行。
操
作
系
统
|
进
程
的
描
述
与
控
制
12
CUIT 徐虹
例1．语句c = a – b 和w = c + 1
R（c = a – b ）= {a, b }
W（c = a – b ）= { c }
R（w = c + 1 ）= { c }
W（w = c + 1 ）= { w }
R（w = c + 1 ）∩W（c = a – b ）= { c }
语句c = a – b 和w = c + 1 不能并发执行。
7
操
作
系
统
|
进
程
的
描
述
与
控
制
13
CUIT 徐虹
例2．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 能并发执行。
语句S1 和S3，S2 和S3，S3 和S4 不能并发执行。
S1
S3 →S4
S2
操
作
系
统
|
进
程
的
描
述
与
控
制
14
CUIT 徐虹
?资源共享
?资源共享是指系统中的硬件资源和
软件资源不再由单个用户所独占，而
为n 个用户共同使用。
?由系统进行统一分配（硬件）和由
程序自行使用（数据基，变量、队列
等）
?程序共行执行与资源共享之间互为
存在条件。
8
操
作
系
统
|
进
程
的
描
述
与
控
制
15
CUIT 徐虹
?程序并发执行的特点
?失去程序的封闭性和可再现性
?程序与计算不再一一对应
?程序并发执行的相互制约
?执行——暂停——执行
操
作
系
统
|
进
程
的
描
述
与
控
制
16
CUIT 徐虹
2．2 进程的概念
?进程的定义
?进程的定义: 进程是程序在一个数据集
合上的运行过程，是系统进行资源分配
和调度的一个独立的基本单位。
?进程的特征
?动态性
?并发特征
?独立特征
?异步特征
?机构特征
9
操
作
系
统
|
进
程
的
描
述
与
控
制
17
CUIT 徐虹
?进程与程序的关系
进程程序
概念动态实体，静态实体，
强调执行过程是指令的有序集合
特征并发性、独立性、无并行特征，
异步性，是静止的
是竞争计算机系统
资源的基本单位
两者联系不同的进程可以共享同一个程序，
只要对应的数据集不同
操
作
系
统
|
进
程
的
描
述
与
控
制
18
CUIT 徐虹
2．3进程状态及其转换
?进程状态
一个进程的生命期可以划分为一组状
态，这些状态刻画了这个进程。系统根据
PCB结构中的状态值控制进程。
?就绪状态（Ready）
?执行状态
?等待状态（阻塞状态）
?新（New）状态
?终止状态（Terminated）
10
操
作
系
统
|
进
程
的
描
述
与
控
制
19
CUIT 徐虹
?挂起状态（Suspend）
把一个进程挂起使之处于静止状
态，以便研究它的执行情况获对它进
行修改。
?用户终端需要；
?父进程的需要：考查、修改获协调各子
进程时；
?OS的需要：改善系统运行性能，调节负
荷；
?对换的需要：缓和内存紧张的情况；
操
作
系
统
|
进
程
的
描
述
与
控
制
20
CUIT 徐虹
?进程状态转换
11
操
作
系
统
|
进
程
的
描
述
与
控
制
21
CUIT 徐虹
操
作
系
统
|
进
程
的
描
述
与
控
制
22
CUIT 徐虹
12
操
作
系
统
|
进
程
的
描
述
与
控
制
23
CUIT 徐虹
具有挂起状态的进程演变图
操
作
系
统
|
进
程
的
描
述
与
控
制
24
CUIT 徐虹
活动就绪（Readya）和活动阻塞（Blockeda）
静止就绪（Readys）和静止阻塞（Blockeds）
13
操
作
系
统
|
进
程
的
描
述
与
控
制
25
CUIT 徐虹
2．4进程的描述
?进程的组成（进程上下文）
?PCB
?程序
?数据
操
作
系
统
|
进
程
的
描
述
与
控
制
26
CUIT 徐虹
?进程控制块PCB
?描述信息
?控制信息
?资源管理信息
?CPU现场保护：对CPU的处理
?PCB的组织方式
?链接方式
?将具有相同状态的PCB，用其中的
链接字，链接成一个队列。
?索引方式
?根据进程的状态，建立索引表。
14
操
作
系
统
|
进
程
的
描
述
与
控
制
27
CUIT 徐虹
2．5进程控制
?进程间的关系
?非结构系统（Unstructured System）
?树形结构系统（Tree-Structured
System）:一个进程能创建另一个进程，形成
进程家族。
操
作
系
统
|
进
程
的
描
述
与
控
制
28
CUIT 徐虹
?操作系统内核（Kernel）
?支撑功能
?中断处理
?时钟管理
?原语操作：完成特定功能的一段程
序。原语在执行期间是不可分割的。
?资源管理功能
?进程管理
?存储器管理
?设备管理
15
操
作
系
统
|
进
程
的
描
述
与
控
制
29
CUIT 徐虹
?进程的创建
?引起进程创建的事件
?创建原语（Create Primitive）
Void Create(n,S0,P0,M0,R0,acc)
{ i = getinternal name (n); id (i) = n;
priority (i) = P0; cpupstate (i) = S0;
main store (i) = M0; resources (i) = R0;
status (i) = “readys”; sdata (i) = RL;
parent (i) = *; progeny (i) = NULL;
insert (progeny (*), i);
set accounting data; insert (RL, i); }
操
作
系
统
|
进
程
的
描
述
与
控
制
30
CUIT 徐虹
?进程的终止
?进程终止事件
?撤消原语（Destroy Primitive）
Void destroy(n)
{ sched = false;
i = getinternal name (n);
Kill(i);
If sched then scheduler; }
16
操
作
系
统
|
进
程
的
描
述
与
控
制
31
CUIT 徐虹
void kill(i)
{ if status(i) = “executing” then
{ stop(i); sched = true; }
remove(sdata(I),I);
for all s ∈progeny(i) do kill(s);
for all r ∈(main store(i) ∪resoruces(i)) do
if owned(r) then insert(avail (semaphore(r)) data(r));
for all R ∈created resources(i) do
remove resource descriptor(R);
remove PCB(i); }
操
作
系
统
|
进
程
的
描
述
与
控
制
32
CUIT 徐虹
?进程阻塞
?阻塞事件
?阻塞原语（Block Primitive）
Void block (n)
{ i = getinternal name (n);
stop(i);
status(i) = “blockeda”;
insert (WL(r),i);
scheduler; }
17
操
作
系
统
|
进
程
的
描
述
与
控
制
33
CUIT 徐虹
?进程的唤醒
?进程唤醒的事件
?唤醒原语（Wakeup Primitive）
Void wakeup(n)
{ i = getinternal name (n);
remove (WL(r),i);
status = “ready”;
insert(RL,i);
scheduler; }
操
作
系
统
|
进
程
的
描
述
与
控
制
34
CUIT 徐虹
?进程的挂起
?挂起方式
?把发出本原语的进程自身挂起；
?挂起指定进程名的进程；
?把某进程及其全部或部分子孙一起挂起。
?方式（2）的挂起原语（Suspend
Primitive）
18
操
作
系
统
|
进
程
的
描
述
与
控
制
35
CUIT 徐虹
Void suspend (n,a)
{ i = getinternal name (n);
s = status(i);
if s = “executing” then stop(i);
a = copy PCB(i);
status(i) = if s = “blockeda” then “blockeds”;
else “readys”;
if s = “executing” then scheduler; }
操
作
系
统
|
进
程
的
描
述
与
控
制
36
CUIT 徐虹
?进程的激活
?进程激活过程
?激活原语（Activate Primitive）
?由创建原语创建的进程处于“静止就
绪“状态，后跟一个激活原语，使之
变为活跃就绪，就能引起CPU的重
新调度。
19
操
作
系
统
|
进
程
的
描
述
与
控
制
37
CUIT 徐虹
Void activate (n)
{ i = getinternal name (n);
status(i) = if status = “readys” then “readya”;
else “blockeda”;
if status(i) = “readya” then scheduler;
}
操
作
系
统
|
进
程
的
描
述
与
控
制
38
CUIT 徐虹
2．6线程
?线程的引入
?进程的缺陷
?线程的概念
?线程是进程中的一个实体，是被系
统独力调度和分派的基本单位。
?一个线程可以创建和撤消另一个线
程；同一进程中的多个线程之间可
以并发执行。
20
操
作
系
统
|
进
程
的
描
述
与
控
制
39
CUIT 徐虹
操
作
系
统
|
进
程
的
描
述
与
控
制
40
CUIT 徐虹
21
操
作
系
统
|
进
程
的
描
述
与
控
制
41
CUIT 徐虹
每个线程的内容每个进程的内容
程序计数器地址空间
堆栈全局变量
寄存器组打开文件
子线程子进程
状态定时器
信号
信号量
记帐信息
线程和进程的内容比较
操
作
系
统
|
进
程
的
描
述
与
控
制
42
CUIT 徐虹
22
操
作
系
统
|
进
程
的
描
述
与
控
制
43
CUIT 徐虹
?线程的状态
?产生
?运行
?阻塞
?解除阻塞
?结束
操
作
系
统
|
进
程
的
描
述
与
控
制
44
CUIT 徐虹
23
操
作
系
统
|
进
程
的
描
述
与
控
制
45
CUIT 徐虹
?线程与进程的比较
?调度
?并发性
?拥有资源
?系统开销
操
作
系
统
|
进
程
的
描
述
与
控
制
46
CUIT 徐虹
?用户级线程和内核支持线程
内核支持线程
用户级线程
?线程的调度与切换速度
?系统调用
?线程执行时间
24
操
作
系
统
|
进
程
的
描
述
与
控
制
47
CUIT 徐虹
操
作
系
统
|
进
程
的
描
述
与
控
制
48
CUIT 徐虹
?Solaris 中的线程
?用户线程：栈、程序计数器
?内核线程：子数据结构和栈
?LWP 轻进程：PCB（状态、寄存
器等）
?线程间的状态变化
内核线程发生阻塞，则相连的多个
LWP阻塞，进而相应的用户线程阻塞。
如进程只有一个LWP，则进程阻塞。
25
操
作
系
统
|
进
程
的
描
述
与
控
制
49
CUIT 徐虹
操
作
系
统
|
进
程
的
描
述
与
控
制
50
CUIT 徐虹
26
操
作
系
统
|
进
程
的
描
述
与
控
制
51
CUIT 徐虹
2．7 UNIX 的进程描述和控制
操
作
系
统
|
进
程
的
描
述
与
控
制
52
CUIT 徐虹
?UNIX 的进程状态转换图
27
操
作
系
统
|
进
程
的
描
述
与
控
制
53
CUIT 徐虹
?Linux 中的线程
操
作
系
统
|
进
程
的
描
述
与
控
制
54
CUIT 徐虹
?本章重点
?程序的并发执行；
?进程的概念和组成；
?进程的状态，状态转换的原因和
相应的原语操作；
?线程的概念，进程与线程的区别，
内核支持线程和用户级线程。
