计算机操作系统第2章

西安电子科技大学出版社 第三版 配套

第二章 进 程 管 理

第二章 进 程 管 理2.1 2.2 进程的基本概念 进程控制

2.3 进程同步2.4 经典进程的同步问题

2.5 进程通信2.6 线程

西安电子科技大学出版社 第三版 配套

第二章 进 程 管 理

2.1 进程的基本概念2.1.1 程序的顺序执行及其特征 1. 程序的顺序执行 通常可以把一个应用程序分成若干个程序段，在各程序 段之间，必须按照某种先后次序顺序执行，仅当前一操作(程 序段)执行完后，才能执行后继操作。例如，在进行计算时， 总须先输入用户的程序和数据，然后进行计算，最后才能打 印计算结果。这里，我们用结点(Node)代表各程序段的操作 (在图2-1中用圆圈表示),其中，I代表输入操作，C代表计算 操作，P为打印操作；另外，用箭头指示操作的先后次序。这 样，上述的三个程序段的执行顺序可示于图2-1(a)中。对一个 程序段中的多条语句来说，也有一个执行顺序问题，例如对 于下述三条语句的程序段:

西安电子科技大学出版社 第三版 配套

第二章 进 程 管 理

S1: a:=x+y;S2: b:=a-5; S3: c:=b+1; 其中，语句S2必须在语句S1之后(即a被赋值)才能执行；同样，

语句S3也只能在b被赋值后才能执行。因此，这三条语句应按图2-1(b)所示的顺序执行。

西安电子科技大学出版社 第三版 配套

第二章 进 程 管 理

I1

C 1

P1

I2

C 2

P2

S1

S2

S3

(a) 程序的顺序执行

(b) 三条语句的顺序执行

图 2-1

程序的顺序执行

西安电子科技大学出版社 第三版 配套

第二章 进 程 管 理 2. 程序顺序执行时的特征 (1) 顺序性：处理机的操作严格按照程序所规定的顺序 执行，即每一操作必须在上一个操作结束之后开始。 (2) 封闭性：程序是在封闭的环境下执行的，即程序运 行时独占全机资源，资源的状态(除初始状态外)只有本程序 才能改变它。程序一旦开始执行，其执行结果不受外界因素 影响。 (3) 可再现性：只要程序执行时的环境和初始条件相同， 当程序重复执行时，不论它是从头到尾不停顿地执行，还是 “停停走走”地执行，都将获得相同的结果。 程序顺序执行时的特性，为程序员检测和校正程序的错 误带来了很大的方便。

西安电子科技大学出版社 第三版 配套

第二章 进 程 管 理 2.1.2 前趋图 前趋图(Precedence Graph)是一个有向无循环图，记为 DAG(Directed Acyclic Graph),用于描述进程之间执行的前后 关系。图中的每个结点可用于描述一个程序段或进程，乃至 一条语句；结点间的有向边则用于表示两个结点之间存在的 偏序(Partial Order,亦称偏序关系)或前趋关系(Precedence Relation)“→”。

西安电子科技大学出版社 第三版 配套

第二章 进 程 管 理 →={(Pi,Pj)|Pi must complete before Pj may start},如果 (Pi,Pj)∈→,可写成Pi→Pj,称Pi是Pj的直接前趋，而称Pj是 Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结 点(Initial Node),把没有后继的结点称为终止结点(Final Node)。此外，每个结点还具有一个

重量(Weight),用于表示 该结点所含有的程序量或结点的执行时间。在图2-1(a)和21(b)中分别存在着这样的前趋关系： Ii→Ci→Pi 和 S1→S2→S3

西安电子科技大学出版社 第三版 配套

第二章 进 程 管 理 对于图2-2(a)所示的前趋图，存在下述前趋关系： P1→P2 , P1→P3 , P1→P4 , P2→P5 , P3→P5 , P4→P6 , P4→P7,P5→P8,P6→P8,P7→P9,P8→P9 或表示为： P={P1,P2,P3,P4,P5,P6,P7,P8,P9} →={(P1 ,P2),(P1 ,P3),(P1 ,P4),(P2 ,P5),(P3 ,P5),(P4 , P6),(P4,P7),(P5,P8),(P6,P8),(P7,P9),(P8,P9)}

应当注意，前趋图中必须不存在循环，但在图2-2(b)中却 有着下述的前趋关系： S2→S3,S3→S2

西安电子科技大学出版社 第三版 配套

第二章 进 程 管 理

P2 P5 P1 P3 P6 P4 P7 (a) 具有九个结点的前趋图 P8 P9 S2 S1

S3

(b) 具有循环的图

图 2-2 前趋图

西安电子科技大学出版社 第三版 配套

第二章 进 程 管 理 2.1.3 程序的并发执行及其特征 1.程序的并发执行 在图2-1中的输入程序、计算程序和打印程序三者之间， 存在着Ii→Ci→Pi这样的前趋关系，以至对一个作业的输入、 计算和打印三个操作，必须顺序执行，但并不存在Pi→Ii+1的 关系，因而在对一批程序进行处理时，可使它们并发执行。 例如，输入程序在输入第一个程序后，在计算程序对该程序 进行计算的同时，可由输入程序再输入第二个程序，从而使 第一个程序的计算操作可与第二个程序的输入操作并发执行。 一般来说，输入程序在输入第i+1个程序时，计算程序可能正 在对第i个程序进行计算，而打印程序正在打印第i-1个程序的 计算结果。图2-3示出了输入、计算和打印这三个程序对一批 作业进行处理的情况。

西安电子科技大学出版社 第三版 配套

第二章 进 程 管 理

I1

I2

I3

I4

C1

C2

C3

C4

P1

P2

P3

P4

图2-3 并发执行时的前趋图

西安电子科技大学出版社 第三版 配套

第二章 进 程 管 理 在该例中存在下述前趋关系：

Ii→Ci,Ii→Ii+1,Ci→Pi,Ci→Ci+1,Pi→Pi+1而Ii+1 和Ci 及Pi-1 是重迭的，亦即在Pi-1 和Ci 以及Ii+1 之间，

可以并发执行 …… 此处隐藏：1310字，全部文档内容请下载后查看。喜欢就下载吧 ……