第二章 进程管理

第二章进程管理第二章进程管理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)所示的顺序执行。第二章进程管理图2-1程序的顺序执行(a)程序的顺序执行(b)三条语句的顺序执行I1C1P1I2C2P2S1S2S3第二章进程管理2.程序顺序执行时的特征(1)顺序性：处理机的操作严格按照程序所规定的顺序执行，即每一操作必须在上一个操作结束之后开始。(2)封闭性：程序是在封闭的环境下执行的，即程序运行时独占全机资源，资源的状态(除初始状态外)只有本程序才能改变它。程序一旦开始执行，其执行结果不受外界因素影响。(3)可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都将获得相同的结果。程序顺序执行时的特性，为程序员检测和校正程序的错误带来了很大的方便。第二章进程管理2.1.2前趋图前趋图(PrecedenceGraph)是一个有向无循环图，记为DAG(DirectedAcyclicGraph)，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序(PartialOrder，亦称偏序关系)或前趋关系(PrecedenceRelation)“→”。第二章进程管理→={(Pi，Pj)|PimustcompletebeforePjmaystart}，如果(Pi，Pj)∈→，可写成Pi→Pj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结点(InitialNode)，把没有后继的结点称为终止结点(FinalNode)。此外，每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。在图2-1(a)和2-1(b)中分别存在着这样的前趋关系：Ii→Ci→PiS1→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-2前趋图P1P3P8P9P4P2P5P6P7S1S2S3(a)具有九个结点的前趋图(b)具有循环的图第二章进程管理2.1.3程序的并发执行及其特征1．程序的并发执行在图2-1中的输入程序、计算程序和打印程序三者之间，存在着Ii→Ci→Pi这样的前趋关系，以至对一个作业的输入、计算和打印三个操作，必须顺序执行，但并不存在Pi→Ii+1的关系，因而在对一批程序进行处理时，可使它们并发执行。例如，输入程序在输入第一个程序后，在计算程序对该程序进行计算的同时，可由输入程序再输入第二个程序，从而使第一个程序的计算操作可与第二个程序的输入操作并发执行。一般来说，输入程序在输入第i+1个程序时，计算程序可能正在对第i个程序进行计算，而打印程序正在打印第i-1个程序的计算结果。图2-3示出了输入、计算和打印这三个程序对一批作业进行处理的情况。第二章进程管理图2-3并发执行时的前趋图P1P2P3P4I1I2I3I4C1C2C3C4第二章进程管理在该例中存在下述前趋关系：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+2S2:b:=y+4S3:c:=a+bS4:d:=c+b第二章进程管理图2-4四条语句的前趋关系S1S2S3S4第二章进程管理2．程序并发执行时的特征1)间断性程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间，形成了相互制约的关系。例如，图2-3中的I、C和P是三个相互合作的程序，当计算程序完成Ci－1的计算后，如果输入程序I尚未完成Ii的处理，则计算程序就无法进行Ci的处理，致使计算程序必须暂停运行。又如，当打印程序完成Pi的打印后，若计算程序尚未完成Ci＋1的计算，则打印程序就无法对Ci＋1的计算结果进行打印。一旦使程序暂停的因素消失后(如Ii已处理完成)，计算程序便可恢复执行对Ci的处理。简而言之，相互制约将导致并发程序具有“执行—暂停—执行”这种间断性的活动规律。第二章进程管理2)失去封闭性程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。这样，某程序在执行时，必然会受到其它程序的影响。例如，当处理机这一资源已被某个程序占有时，另一程序必须等待。第二章进程管理3)不可再现性程序在并发执行时，由于失去了封闭性，也将导致其再失去可再现性。例如，有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N:=N+1操作；程序B每执行一次时，都要执行Print(N)操作，然后再将N置成“0”。程序A和B以不同的速度运行。这样，可能出现下述三种情况(假定某时刻变量N的值为n)。第二章进程管理(1)N:=N+1在Print(N)和N:=0之前，此时得到的N值分别为n+1，n+1，0。(2)N:=N+1在Print(N)和N:=0之后，此时得到的N值分别为n，0，1。(3)N:=N+1在Print(N)和N:=0之间，此时得到的N值分别为n，n+1，0。上述情况说明，程序在并发执行时，由于失去了封闭性，其计算结果已与并发程序的执行速度有关，从而使程序的执行失去了可再现性，亦即，程序经过多次执行后，虽然它们执行时的环境和初始条件相同，但得到的结果却各不相同。第二章进程管理2.1.4进程的特征与状态1.进程的特征和定义在多道程序环境下，程序的执行属于并发执行，此时它们将失去其封闭性，并具有间断性及不可再现性的特征。这决定了通常的程序是不能参与并发执行的，因为程序执行的结果是不可再现的。这样，程序的运行也就失去了意义。为使程序能并发执行，且为了对并发执行的程序加以描述和控制，人们引入了“进程”的概念。为了能较深刻地了解什么是进程，我们将先对进程的特征加以描述。第二章进程管理1)结构特征通常的程序是不能并发执行的。为使程序(含数据)能独立运行，应为之配置一进程控制块，即PCB(ProcessControlBlock)；而由程序段、相关的数据段和PCB三部分便构成了进程实体。在早期的UNIX版本中，把这三部分总称为“进程映像”。值得指出的是，在许多情况下所说的进程，实际上是指进程实体，例如，所谓创建进程，实质上是创建进程实体中的PCB；而撤消进程，实质上是撤消进程的PCB，本教材中也是如此。第二章进程管理2)动态性进程的实质是进程实体的一次执行过程，因此，动态性是进程的最基本的特征。动态性还表现在：“它由创建而产生，由调度而执行，由撤消而消亡”。可见，进程实体有一定的生命期，而程序则只是一组有序指令的集合，并存放于某种介质上，其本身并不具有运动的含义，因而是静态的。第二章进程管理3)并发性这是指多个进程实体同存于内存中，且能在一段时间内同时运行。并发性是进程的重要特征，同时也成为OS的重要特征。引入进程的目的也正是为了使其进程实体能和其它进程实体并发执行；而程序(没有建立PCB)是不能并发执行的。4)独立性在传统的OS中，独立性是指进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。凡未建立PCB的程序都不能作为一个独立的单位参与运行。第二章进程管理5)异步性这是指进程按各自独立的、不可预知的速度向前推进，或说进程实体按异步方式运行。现在我们再来讨论进程的定义。曾有许多人从不同的角度对进程下过定义，其中较典型的进程定义有：(1)进程是程序的一次执行。(2)进程是一个程序及其数据在处理机上顺序执行时所发生的活动。(3)进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。第二章进程管理2.进程的三种基本状态进程执行时的间断性决定了进程可能具有多种状态。事实上，运行中的进程可能具有以下三种基本状态。1)就绪(Ready)状态当进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行，进程这时的状态称为就绪状态。在一个系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。第二章进程管理2)执行状态进程已获得CPU，其程序正在执行。在单处理机系统中，只有一个进程处于执行状态；在多处理机系统中，则有多个进程处于执行状态。3)阻塞状态正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，亦即进程的执行受到阻塞，把这种暂停状态称为阻塞状态，有时也称为等待状态或封锁状态。致使进程阻塞的典型事件有：请求I/O，申请缓冲空间等。通常将这种处于阻塞状态的进程也排成一个队列。有的系统则根据阻塞原因的不同而把处于阻塞状态的进程排成多个队列。第二章进程管理图2-5进程的三种基本状态及其转换就绪阻塞执行时间片完进程调度I/O完成I/O请求第二章进程管理3.挂起状态1)引入挂起状态的原因在不少系统中进程只有上述三种状态，但在另一些系统中，又增加了一些新状态，最重要的是挂起状态。引入挂起状态的原因有：(1)终端用户的请求。当终端用户在自己的程序运行期间发现有可疑问题时，希望暂时使自己的程序静止下来。亦即，使正在执行的进程暂停执行；若此时用户进程正处于就绪状态而未执行，则该进程暂不接受调度，以便用户研究其执行情况或对程序进行修改。我们把这种静止状态称为挂起状态。第二章进程管理(2)父进程请求。有时父进程希望挂起自己的某个子进程，以便考查和修改该子进程，或者协调各子进程间的活动。(3)负荷调节的需要。当实时系统中的工作负荷较重，已可能影响到对实时任务的控制时，可由系统把一些不重要的进程挂起，以保证系统能正常运行。(4)操作系统的需要。操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记账。第二章进程管理2)进程状态的转换在引入挂起状态后，又将增加从挂起状态(又称为静止状态)到非挂起状态(又称为活动状态)的转换；或者相反。可有以下几种情况：(1)活动就绪→静止就绪。当进程处于未被挂起的就绪状态时，称此为活动就绪状态，表示为Readya。当用挂起原语Suspend将该进程挂起后，该进程便转变为静止就绪状态，表示为Readys，处于Readys状态的进程不再被调度执行。第二章进程管理图2-6具有挂起状态的进程状态图活动就绪静止就绪执行挂起激活释放挂起活动阻塞静止阻塞挂起激活释放请求I/O调度第二章进程管理(2)活动阻塞→静止阻塞。当进