第二讲 进程管理

《第二讲 进程管理》由会员分享，可在线阅读，更多相关《第二讲 进程管理（223页珍藏版）》请在文档大全上搜索。

1、1第第2章章 进程管理进程管理 2.12.1 进程的基本概念进程的基本概念2.22.2 进程控制进程控制2.32.3 进程同步进程同步2.42.4 经典进程同步问题经典进程同步问题2.52.5 管程机制管程机制 实现互斥的软件机制和硬件机制实现互斥的软件机制和硬件机制( (补充补充) )2.62.6 进程通信进程通信2.72.7 线程线程第一次课内上机实验第一次课内上机实验22.12.1 进程的基本概念进程的基本概念n 程序的顺序执行及其特征程序的顺序执行及其特征n 程序的并发执行及其特征程序的并发执行及其特征n 进程的特征与状态进程的特征与状态n 进程控制块进程控制块32.1.1 程序的顺序

2、执行及其特征程序的顺序执行及其特征n程序的顺序执行程序的顺序执行仅当前一操作仅当前一操作( (程序段程序段) )执行完后，才能执行后继操作。执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。据，然后进行计算，最后才能打印计算结果。 S1: a=x+y;S1: a=x+y; S2: b=a-5;S2: b=a-5; S3: c=b+1;S3: c=b+1;(a) 程序的顺序执行(b) 三条语句的顺序执行I1C1P1I2C2P2S1S2S342.1.1 程序的顺序执行及其特征程序的顺序执行及其

3、特征顺序执行包含两层含义：顺序执行包含两层含义：l 对于多个用户程序来说，所有程序是依次执对于多个用户程序来说，所有程序是依次执行的。（外部顺序性）行的。（外部顺序性） l 对于一个程序来说，它的所有指令是按序执对于一个程序来说，它的所有指令是按序执行的。（内部顺序性）行的。（内部顺序性）5n程序顺序执行的特征程序顺序执行的特征 （1）顺序性：）顺序性： 处理机的操作严格按照程序所规定的顺序执行，处理机的操作严格按照程序所规定的顺序执行，即每一操作必须在下一操作开始之前结束（或者即每一操作必须在下一操作开始之前结束（或者说下一操作必须在当前操作结束后才能开始）。说下一操作必须在当前操作结束后才

4、能开始）。 （2）封闭性：）封闭性： 程序是在封闭的环境下执行的。即程序是在封闭的环境下执行的。即程序运行时独占全机资源，资源的状态（除初始程序运行时独占全机资源，资源的状态（除初始态外）只有本程序才能改变它。态外）只有本程序才能改变它。程序一旦开始执行，其执行结果不受外界影响。程序一旦开始执行，其执行结果不受外界影响。 （3）可再现性：）可再现性： 只要程序执行时的环境和初始条件相同，当程只要程序执行时的环境和初始条件相同，当程序重复执行时，都将获得相同的结果。序重复执行时，都将获得相同的结果。 6程序的并发执行程序的并发执行包括两层含义：包括两层含义： l 对于一个程序来说，它的所有指令是

5、对于一个程序来说，它的所有指令是按序执行的。（内部顺序性）按序执行的。（内部顺序性） l 对于多个程序（进程）来说，所有进对于多个程序（进程）来说，所有进程是交叉执行的。（外部并发性）程是交叉执行的。（外部并发性） 2.1.3 程序的并发执行及其特征程序的并发执行及其特征 7n前趋图前趋图 前趋图前趋图(Precedence Graph)是一个有向无循环图，记为是一个有向无循环图，记为DAG(Directed Acyclic Graph)，用于描述进程之间执行的前，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃后关系。图中的每个结点可用于描述一个程序段或进程，乃至

6、一条语句；结点间的有向边则用于表示两个结点之间存在至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序的偏序(Partial Order)或前趋关系或前趋关系(Precedence Relation)“”。 =(Pi, Pj)|Pi must complete before Pj may start, 如果如果(Pi, Pj),可写成可写成PiPj，称，称Pi是是Pj的直接前趋，而称的直接前趋，而称Pj是是Pi的直的直接后继。在前趋图中，把没有前趋的结点称为初始结点接后继。在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点，把没有后继的结点

7、称为终止结点(Final Node)。8n前趋图前趋图 每个结点还具有一个重量每个结点还具有一个重量(Weight)，用于表示该结点，用于表示该结点所含有的程序量或结点的执行时间。所含有的程序量或结点的执行时间。 IiCiPi和和S1S2S3 P1P3P8P9P4P2P5P6P7S1S2S3(a) 具有九个结点的前趋图(b) 具有循环的前趋图9n前趋图前趋图对于图对于图 2-2(a)所示的前趋图，所示的前趋图， 存在下述前趋关系：存在下述前趋关系： P1P2, P1P3, P1P4, P2P5, P3P5, P4P6, P4P7, P5P8, P6P8, P7P9, P8P9或表示为：或表示为

8、： 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)中却有着中却有着下述的前趋关系：下述的前趋关系：S2S3, S3S2 10n前趋图前趋图 前趋图前趋图(Precedence Graph)是一个有向无循环图，记为是一个有向无循环图，记为DAG(Directed

9、 Acyclic Graph)，用于描述进程之间执行的前，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序的偏序(Partial Order)或前趋关系或前趋关系(Precedence Relation)“”。 =(Pi, Pj)|Pi must complete before Pj may start, 如果如果(Pi, Pj),可写成可写成PiPj，称，称Pi是是Pj的直接前趋，而称的直接前趋，而称Pj

10、是是Pi的直的直接后继。在前趋图中，把没有前趋的结点称为初始结点接后继。在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点，把没有后继的结点称为终止结点(Final Node)。112.1.3 程序的并发执行及其特征程序的并发执行及其特征 P1P2P3P4I1I2I3I4C1C2C3C4图图 2-3 并发执行时的前趋图并发执行时的前趋图 122.1.3 程序的并发执行及其特征程序的并发执行及其特征 在该例中存在下述前趋关系：在该例中存在下述前趋关系： IiCi，IiIi+1, CiPi, CiCi+1，PiPi+1而而Ii+1和和Ci及及Pi-1

11、是重迭的，亦即在是重迭的，亦即在Pi-1和和Ci以及以及Ii+1之间，可之间，可以并发执行。以并发执行。 对于具有下述四条语句的程序段：对于具有下述四条语句的程序段： S1: a =x+2 S2: b =y+4 S3: c =a+b S4: d =c+b 131）间断性）间断性: : 程序在并发执行时，由于它们共享系统资程序在并发执行时，由于它们共享系统资源，以及为完成同一任务而相互合作，致源，以及为完成同一任务而相互合作，致使这些并发执行的程序之间形成了相互制使这些并发执行的程序之间形成了相互制约的关系。（互斥关系、同步关系）约的关系。（互斥关系、同步关系） 相互制约导致并发执行的程序具有相