74第2章 进程管理

第2章进程管理第2章进程管理2.1进程的基本概念2.2进程控制2.3进程同步2.4经典进程的同步问题2.5进程通信2.6线程第2章进程管理本章学习目标在多道程序环境下，程序不能独立运行。作为资源分配和独立运行的基本单位是进程。操作系统所有的特征都是基于进程而体现的。所以，本章的学习目标为：理解进程的概念，掌握进程在系统中的表示方法理解进程的创建及其状态变化理解进程切换过程，进程调度的原因及调度切换时机理解进程同步的实现方法；掌握信号量机制及使用它解决进程同步问题的方法。掌握进程通信的机制（共享存储系统；消息传递系统；管道通信）了解管程机制掌握线程的基本概念，了解线程的控制方法及常见的两类线程第2章进程管理本章重难点提示进程和程序的比较，进程和线程的比较进程的三个基本状态的转换的因果关系判断临界区算法的正确与否（综合应用题）整型信号量和记录型信号量的定义（综合应用题）信号量的应用（综合应用题）第2章进程管理2.1进程的基本概念2.1.1程序的顺序执行及其特征2.1.2前趋图2.1.3程序的并发执行及其特征2.1.4进程的特征与状态2.1.5进程控制块第2章进程管理2.1.1程序的顺序执行及其特性由于各类软件的出现及日益复杂化，使得程序设计的概念和方法有了很大的发展，在单道程序工作环境中，我们把一个“程序”理解为“一个在时间上按严格次序前后相继的操作序列”。第2章进程管理程序顺序执行的图示例如，进行计算时，总需要首先输入数据，然后进行计算，最后才能打印计算结果。假如用I表示输入，C表示计算，P表示打印，并且用箭头表示操作的先后次序。则输入数据，计算数据，打印计算结果这样一段程序I1C1P1可表示为：I1C1P1两段这样的程序时，可表示为：I2C2P2图2-1（a）第2章进程管理程序顺序执行的图示对于程序段中的多条语句来说，也有一个执行顺序问题，如对于包含下述三条语句的程序段：S1:a=x+y;S2:b=a-5;S3:c=b+1;S1S2S3可表示为：图2-1（b）第2章进程管理一切顺序执行的程序都具有下列特性：（1）顺序性。即每一操作都必须在上一个操作结束之后开始。（2）封闭性。程序运行时独占全机资源；资源的状态（除初始状态外）只有本程序才能改变它。程序一旦开始运行，其执行结果不受外界因素影响。（3）可再现性。只要执行时的环境和初始条件相同，程序不论是连续执行还是“走走停停”地执行，都将获得相同的结果。第2章进程管理2.1.2前趋图定义：前趋图是一个有向无循环图，记为DAG(DirectedAcyclicGraph)，用于描述进程之间执行的前后关系。图中每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边表示两结点间的偏序关系或前趋关系“→”。前趋关系“→”的定义：→={(Pi,Pj)|PimustcompletebeforePjmaystart}。记作：Pi→Pj。称Pi是Pj的直接前趋，Pj是Pi的直接后继。没有前趋的称为初始结点（InitialNode），没有后继的称为终止结点（FinalNode）。第2章进程管理I1C1P1I2C2P2图2-1（a）图2-1（a）中有偏序关系:Ii→Ci→PiS1S2S3图2-1（b）中有偏序关系:S1→S2→S3图2-1（b）第2章进程管理P1P2P3P4P5P6P7P8P9(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章进程管理如图(b)就不是前趋图。前趋图中不应出现循环。S1S2S3因为存在前趋关系:S2→S3和S3→S2第2章进程管理2.1.3程序的并发执行及其特性无论是操作系统自身的程序还是用户程序，通常总是存在一些相对独立、但又能并发执行的程序段。这些“并发程序”就构成了一个“并发环境”。例如，输入程序在输入第一个程序后，在计算程序对该程序进行计算的同时，可由输入程序再输入第二个程序，从而使第一个程序的计算操作可与第二个程序的输入操作并发执行。第2章进程管理一般来说，输入程序在输入第i+1个程序时，计算程序可能正在对第i个程序进行计算，而打印程序正在打印第i-1个程序的计算结果。I1I2I3I4C1C2C3C4P1P2P3P4该例中存在下述前趋关系：Ii→Ci，Ii→Ii+1，Ci→Pi，Ci→Ci+1，Pi→Pi+1而Ii+1和Ci及Pi-1是重迭的，亦即Ii+1和Ci及Pi-1可以并发执行。第2章进程管理又如有程序段：S1:a:=x+2S2:b:=y+4S3:c:=a+bS4:d:=c+bs1S2S3S4该例中存在下述前趋关系：S3必须在a和b被赋值后方能执行；S4必须在S3之后执行；但S1和S2则可以并发执行。第2章进程管理程序并发执行时的特征•间断(异步)性：“执行——暂停——执行”，一个程序可能走到中途停下来，失去原有的时序关系。由于程序并发执行时共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间，形成了相互制约的关系。第2章进程管理I1I2I3I4C1C2C3C4P1P2P3P4上图中，I、C和P是三个相互合作的程序，当计算程序完成Ci-1的计算后，如果输入程序I尚未完成Ii的处理，则计算程序就无法进行Ci的处理，致使计算程序必须暂停运行。第2章进程管理•失去封闭性：共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。•失去可再现性：失去封闭性→失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。第2章进程管理失去可再现性的例子1例如：有两个循环程序A和B，它们共享一个变量N。程序A：N:=N+1；程序B:Print(N)；N=0程序A和B以不同的速度运行，这样，可能出现下述三种情况（假定某时刻变量Ｎ的值为ｎ）N:=N+1在Print(N)和N=0之前，得到的N值分别为：n+1,n+1,0N:=N+1在Print(N)和N=0之后，得到的N值分别为：n,0,1N:=N+1在Print(N)和N=0之间，得到的N值分别为：n,n+1,0第2章进程管理失去可再现性的例子2一飞机订票系统，两个终端，运行T1、T2进程T1:T2:......Read(x);Read(x);ifx=1thenifx=1thenx:=x-1;x:=x-1;write(x);write(x);......第2章进程管理2.1.3进程的特征和状态进程是操作系统中一个最基本也是最重要的概念，但目前没有一个非常确切的定义。很多人从不同角度对进程下过定义，较典型的进程定义有：（1）进程是程序的一次执行。（2）进程是一个程序及其数据在处理机上顺序执行时所发生的活动。（3）进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。本教材定义进程为：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。第2章进程管理进程与程序的区别•进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件、静态和可以复制。•进程是暂时的，程序是永久的：进程是一个状态变化的过程，程序可长久保存。•进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。•进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。第2章进程管理进程的特征•结构特征为使程序能并发执行，应为之配置一进程控制块，即PCB（ProcessControlBlock）。进程实体由程序段、相关的数据段和PCB三部分构成。创建进程实质上就是创建进程实体中的PCB，撤销进程实质上就是撤销进程的PCB。第2章进程管理进程的特征•动态性进程有一定的生命期。动态性表现在：进程由创建而产生，由调度而执行，由撤销而消亡。•并发性指多个进程实体同存于内存中，且能在一段时间内同时运行。•独立性指的是在传统的没有线程的OS中，进程是一个能独立运行、独立分配资源和独立接受调度的基本单位。•异步性指的是进程按各自独立的、不可预知的速度向前推进，或说进程实体按异步方式运行。第2章进程管理进程的三种基本状态及状态变化图（1）就绪状态：进程已分配到除CPU以外的所有必要资源，只要获得CPU，便可立即执行，此时的状态称为就绪状态。一个系统中处于就绪状态的进程有多个，通常排成一个就绪队列。（2）执行状态：进程已获得CPU，其程序正在执行。单处理机系统中，只有一个进程在执行；多处理机系统中，可以是多个进程在同时执行。（3）阻塞状态：正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，亦即进程的执行受到阻塞，这种状态称为阻塞状态（等待状态或封锁状态）。处于阻塞状态的进程也可排成队列。导致进程阻塞的事件有：请求I/O，申请缓冲空间等。第2章进程管理图进程的三种基本状态及其转换就绪执行阻塞时间片完进程调度I/O请求I/O完成1、处于就绪绪状态的进程，在调度程序为之分配了处理机之后，该进程便可执行，相应地它就由就绪态变为执行状态；2、如果因发生某事件而使进程的执行受阻，使之无法继续执行，该进程将由执行状态转变为阻塞状态；3、正在执行的当前进程，如果分配给它的时间片已完而被暂停执行时，该进程由执行状态回复到就绪状态。第2章进程管理状态变化有：（1）就绪状态变化到运行状态。（2）运行状态变化到就绪状态。（3）运行状态变化到阻塞状态。（4）阻塞状态变化到就绪状态。就绪图进程的三种基本状态及其转换执行时间片完进程调度I/O请求I/O完成阻塞第2章进程管理引入了挂起状态的进程状态转换引入挂起状态的原因：•终端用户的请求。当终端用户在自己的程序运行期间发现有可疑问题时，希望暂时使自己的程序静止下来。这种静止状态就是挂起状态。•父进程请求父进程要求挂起自己的子进程，以便考查和修改；•负荷调节的需要实时系统中负荷较重时，系统会把一些不重要的进程挂起；•操作系统的需要操作系统希望挂起一些进程，以便检查运行中的资源使用情况。第2章进程管理引入挂起状态后的进程状态转换引入挂起之后，增加了从挂起状态（又称静止状态）到非挂起状态（又称活动状态）的转换；或者相反。有以下几种情况：活动就绪→静止就绪当进程处于未被挂起的就绪状态时，称为活动就绪，表示为Readya。当用挂起原语Suspend将该进程挂起后，该进程转换为静止就绪状态，表示为Readys，处于Readys状态的进程不再被调度执行。第2章进程管理活动阻塞→静止阻塞当进程处于尚未挂起的阻塞状态时，称为处于活动阻塞状态，表示为Blockeda。当用Suspend原语将它挂起后，进程便转换为静止阻塞，表示为Blockeds。处于该状态的进程在期待的事件出现后，将从静止阻塞变为静止就绪。静止就绪→活动就绪处于Readys状态的进程，若用激活原语Active激活后，该进程将转变为Readya状态。静止阻塞→活动阻塞处于Blockeds状态的进程，若用激活原语Active激活后，进程将转变为Blockeda状态。第2章进程管理有挂起状态的进程转换图执行静止就绪静止阻塞活动就绪活动阻塞请求I/O挂起激活挂起激活挂起I/O完成I/O完成进程调度时间片完第2章进程管理创建状态和终止状态1）创建状态创建过程一般包括两个步骤：首先，为一个新进程创建PCB，并填写必要的管理信息；其次，把该进程转成就绪状态并插入就绪队列中。当新进程被创建时，系统已为其分配了PCB，填写了进程标识等信息，但由于该进程所必需的资源或其它信息，如主存资源尚未分配等。此时，进程已拥有了自己的PCB，但进程自身还未进入