第02章_进程管理.ppt

第二章　进 程 管 理 2.1　进程的基本概念 2.2　进程控制 2.3　进程同步 2.4　经典进程的同步问题 2.5 进程通信 2.6　线程 2.1　进程的基本概念 2.1.1　程序的顺序执行及其特征 1. 程序的顺序执行 含义：前趋程序段未完成时，后继程序段不能开始，例如： 在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。如果用I代表输入操作，C代表计算操作，P为打印操作，上述的三个程序段的执行顺序可示于图2-1(a)中。 对一个程序段中的多条语句来说，也有一个执行顺序问题，例如对于下述三条语句的程序段应按图2-1(b)所示的顺序执行: S1: a:=x+y； S2: b:=a-5； S3: c:=b+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)和2-1(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 2.1.3　程序的并发执行及其特征 1．程序的并发执行 含义：为增强计算机系统的处理能力和提高资源利用率所采取的一种同时操作技术。 在图2-1中的输入程序、计算程序和打印程序三者之间，存在着Ii→Ci→Pi这样的前趋关系，以至对一个作业的输入、计算和打印三个操作，必须顺序执行，但并不存在Pi→Ii+1的关系，因而在对一批程序进行处理时，可使它们并发执行。一般来说，输入程序在输入第i+1个程序时，计算程序可能正在对第i个程序进行计算，而打印程序正在打印第i-1个程序的计算结果。 类似于指令流水线（取指、译码、取数、执行），在某一时刻，Pi-1，Ci，Ii+1并发执行。 尝试画出下述四条语句的前趋图： S1: a:=x+2 S2: b:=y+4 S3: c:=a+b S4: d:=c+b 先看一个例子 有一个公有变量i，其初值为1，现有两个程序： 程序1 程序2 ① i++; ③ i = 0; ② printf(“%d” , i); ④ printf(“%d” , --i); 如果让程序1和程序2并发执行，在不施加并发规则的情况下，屏幕上的显示结果可能是哪些？ ①→②→③→④，显示结果为：2 , -1 ①→③→②→④，显示结果为：0 , -1 ①→③→④→②，显示结果为：-1 , -1 。。。 思考：这个例子说明了什么问题？ 2．程序并发执行时的特征 1) 间断性 程序在并发执行时，由于它们共享系统资源