第二章进程管理 第二章进程管理 2.1进程的基本概念 2.2进程控制 2.3进程同步 2.4经典迸程的同步问题 2.5管程机制 2.6进程通信 2.7线程 BACK
第二章 进 程 管 理 第二章 进程管理 2.1 进程的基本概念 2.2 进程控制 2.3 进程同步 2.4 经典进程的同步问题 2.5 管程机制 2.6 进程通信 2.7 线程
第二章进程管理 21进程的基本概念 211程序的顺序执行及其特征 1.程序的顺序执行 仅当前一操作(程序段)执行完后,才能执行后继操作 例如,在进行计算时,总须先输入用户的程序和数据,然后 进行计算,最后才能打印计算结果。 - Xty 2 a-5; b+1:
第二章 进 程 管 理 2.1 进程的基本概念 2.1.1 程序的顺序执行及其特征 1. 程序的顺序执行 仅当前一操作(程序段)执行完后，才能执行后继操作。 例如，在进行计算时，总须先输入用户的程序和数据，然后 进行计算，最后才能打印计算结果。 S1 : a ∶=x+y; S2 : b ∶=a-5; S3 : c ∶=b+1;
第二章进程管理 CHP (a)程序的顺序执行 (b)三条语句的顺序执行 图2-1程序的顺序执行
第二章 进 程 管 理 图 2-1 程序的顺序执行 (a) 程序的顺序执行 (b) 三条语句的顺序执行 I 1 C1 P1 I 2 C2 P2 S1 S2 S3
第二章进程管理 2.程序顺序执行时的特征 (1)顺序性: (2)封闭性: (3)可再现性:
第二章 进 程 管 理 2. 程序顺序执行时的特征 (1) 顺序性： (2) 封闭性： (3) 可再现性：
第二章进程管理 212前趋图 前趋图( Precedence Graph)是一个有向无循环图,记为 DAG( Directed Acyclic Graph),用于描述进程之间执行的前后 关系。图中的每个结点可用于描述一个程序段或进程,乃至 条语句;结点间的有向边则用于表示两个结点之间存在的 偏序( Partial order)或前趋关系( Precedence relation)N =(P,P) Pi must complete before Pi may start}2如果(P P)∈→可写成P→P,称P是P的直接前趋,而称P是P的直 接后继。在前趋图中,把没有前趋的结点称为初始结 ( nitial node),把没有后继的结点称为终止结点( Final node)
第二章 进 程 管 理 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),用于表示该结点所 含有的程序量或结点的执行时间 I→C1→P;和S1→S2→S3 (a)具有九个结点的前趋图 (b)具有循环的前趋图 图2-2前趋图
第二章 进 程 管 理 每个结点还具有一个重量(Weight)，用于表示该结点所 含有的程序量或结点的执行时间。 Ii→Ci→Pi和S1→S2→S3 图 2-2 前趋图 P1 P3 P8 P9 P4 P2 P5 P6 P7 S1 S2 S3 (a) 具有九个结点的前趋图 (b) 具有循环的前趋图
第二章进程管理 对于图2-2(a)所示的前趋图,存在下述前趋关系 P1→→P2,P1→P3,P1→→P P2→少P5,P3→Ps,P4→>P6,P4→P P82P6→→Pg,P→P9,P8→+P 或表示为: P={P1,P2,P3,P4,PP62P7,Pg,P9} ={(P1,P2),(P1P3),(P1,P4,(P2,P5)2(P3,P5),(P42P6),(P4,P7 (P5,Pg),(P6,Pg),(Pn,P9),(P8,P9)} 应当注意,前趋图中必须不存在循环,但在图2-2(b)中却有着 下述的前趋关系:
第二章 进 程 管 理 对于图 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
第二章进程管理 213程序的并发执行及其特征 程序的并发执行 图2-3并发执行时的前趋图
第二章 进 程 管 理 2.1.3 程序的并发执行及其特征 1. 程序的并发执行 图 2-3 并发执行时的前趋图 P1 P2 P3 P4 I 1 I 2 I 3 I 4 C1 C2 C3 C4
第二章进程管理 在该例中存在下述前趋关系: )C1,I;)l11,Ci→P12C→C+1,P→P1+1 而I和C及P1是重迭的,亦即在P1和C以及1之间,可以 并发执行。对于具有下述四条语句的程序段: S1:a:=x+2 b:≡y+4 S3: c.=a+b S: d:=c+b
第二章 进 程 管 理 Ii→Ci，Ii→Ii+1 , Ci→Pi , Ci→Ci+1，Pi→Pi+1 而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之间，可以 并发执行。 S1 : a∶=x+2 S2 : b∶=y+4 S3 : c∶=a+b S4 : d∶=c+b
第二章进程管理 图24四条语句的前趋关系
第二章 进 程 管 理 图 2-4 四条语句的前趋关系 S1 S2 S3 S4