计算机操作系统第2章-进程管理第一部分

1第二章进程管理第一部分进程的描述与控制•主讲：王斯锋2主要目录进程的引入2.1前趋图和程序执行2.2进程的描述2.3进程控制2.4线程的基本概念2.5总结本章基础要点练习及参考答案2.6作业3进程的引入进程的概念是操作系统中最基本、最重要的概念。它是在多道程序系统出现后，为了刻划系统内部出现的情况，描述系统内部各作业的活动规律而引进的一个新的概念。4在多道程序批处理系统和分时系统中，程序并不能独立运行，作为资源分配和独立运行的基本单位是进程。操作系统所具有的四大特征也都是基于进程而形成的，并可从进程的观点来研究操作系统，形成了所谓的进程观点。52.1前趋图和程序(顺序或并发)执行2.1.1前趋图的定义2.1.2程序顺序执行:说明有些进程是先后运行的。一、程序顺序执行二、程序顺序执行时的特征2.1.3程序并发执行一、程序并发执行二、程序并发执行时的特征2.1.4程序并发执行的条件62.1.1前趋图的定义前趋图(ProcedenceGraph)是一个有向无循环图DAG(DirectedAcyclicGraph)。用于描述进程之间执行的前后关系。图中的每个结点用于表示一条语句、一个程序段或进程，结点间的有向边表示在两结点之间存在的偏序(PartialOrder)或前趋关系(ProcedenceRelation)“”，={(Pi,Pj)|PimustcompletebeforePjmaystart}。若(Pi,Pj)属于，可写成PiPj,称Pi是Pj的前趋，而Pj是Pi的直接后继。没有前趋的结点称为初始结点，没有后继的结点称为终止结点。每个结点具有一个重量，用该结点所含的程序量或结点的执行时间来计量。7如上图示：有下面的前趋关系：P={P1,P2,P3,P4,P5,P6,P7}={(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P5,P7),(P6,P7)}注：前趋图中必须不存在循环。237651482.1.2程序顺序执行一、程序顺序执行一般一个程序的执行从整体上，必须按照某个次序顺序执行。此为程序内部的顺序性，不同的程序也按照调用次序严格有序执行，此为程序外部的顺序性。I1C1P1I2C2P29对某一个程序段中的多条语句，也有一个执行的先后顺序。二、程序顺序执行时的特征1、顺序性处理机的操作，严格按照程序所规定的顺序执行，即每一个操作必须在下一个操作开始之前结束。102、封闭性程序独占全机资源。因而本机各资源的状态(除初始状态外)，只有本程序才能改变它。一旦开始运行，其执行结果不受外界因素的影响。113、可再现性程序的执行结果与时间无关、与执行速度无关。2.1.3程序并发执行一、程序并发执行在前述问题中，以程序为整体不能实现并发运行，但同一个程序可以分成不同的程序段。不同程序段在不同时间需要的资源的是不一样的。所以以程序段为单位可以实现并发的运行。I1I2I3I4C4C3C2C1P3P2P1P4同时进行132.1前趋图和程序执行即两个不同的程序间，在不同的程序段间存在着前趋关系。142.1前趋图和程序执行二、程序并发执行时的特征1、间断性程序并发执行时，由于它们共享资源或为完成同一项任务而相互合作，致使在并发程序之间形成了相互制约的关系。15相互制约将导致并发程序具有“执行-暂停执行-执行”这种间断性的活动规律。162、失去封闭性程序并发执行时，多个并发程序共享系统中的各种资源，所以这些资源的状态被多个程序来改变，致使程序的运行失去了封闭性。这样一个程序在执行时，会受到其它程序的影响。173、不可再现性程序并发执行时，失去了封闭性，必然导致失去其运行结果的可再现性。出现了与时间有关的错误。18假定某时刻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,019从上可知，程序并发执行时，会失去封闭性，其计算结果与并发程序的执行速度有关，而使程序失去了可再现性，即程序经过多次执行后，虽其执行时的环境和初始条件相同，但结果却不相同。202.1.4程序并发执行的条件(可作一般了解)由上可知，程序并发执行，虽可有效地提高资源利用率和系统的吞吐量，但必须使并发程序能保持可再现性。也是使程序并发执行的条件。定义一些符号：R(pi)={a1,a2,…,am},用来表示程序pi在执行期间所需参考的所有变量的集合，称“读集”。W(pi)={b1,b2,…,bm}，是程序pi在执行期间要改变的所有变量的集合，称“写集”。21若有两条语句ci=a-b和wi=c+1，则它们的读集和写集分别为：R(c:=a-b)={a,b}，R(w:=c+1)={c}W(c:=a-b)={c}W(w:=c+1)={w}可得：R(c:=a-b)交W(c:=a-b)={}R(w:=c+1)交W(w:=c+1)={}22读集和写集的交，也可能不是空集。如：R(x:=x+1)=W(x:=x+1)={x}若两个程序p1和p2要并发执行，并具有可再现性，要满足下述条件，该条件在1966年首选由Bernstein提出，又称Bernstein条件。R(p1)交W(p2)={}W(p1)交R(p2)={}W(p1)交W(p2)={}23其中，前两个条件保证一个程序在两次操作之间存储器中的数据不会发生变化；最后一个条件保证程序写操作的结果不会丢失。只要同时满足三个条件，并发执行的程序就可以保持封闭性和可再现性。但这并没能解决所有问题，在实际程序执行过程中很难对这三个条件进行检查。如：四条语句：s1:a:=x+ys2:b:=z+1s3:c:=a-bs4:w:=c+124R(s1)={x,y},R(s2)={z},R(s3)={a,b},R(s4)={c},W(s1)={a},W(s2)={b},W(s3)={c},W(s4)={w}由此可见，s1和s2可并发执行，s1和s3不能并发执行，s2和s3也不能并发执行，s3和s4也不可并发执行。原因？252.2进程的描述2.2.1进程的定义与特征一、进程的定义二、进程的特征2.2.2进程的基本状态一、进程的三种基本状态二、新状态和终止状态三、进程状态的转换2.2.3进程的挂起状态一、挂起状态的引入二、进程状态的转换2.2.4进程控制块PCB一、进程控制块PCB二、进程控制块中的信息三、PCB的组织方式26为了使程序能在多程序环境下并发执行，并能对并发执行的程序加以控制和描述，专门配置了一个称为“进程控制块”的数据结构。其中放了进程标识符、进程运行的当前状态、程序和数据的地址，以及能保存该程序运行时CPU的环境信息。PCB或进程描述符processdescriptor这样，由程序段、数据段及进程控制块构成了一个进程的实体。272.2.1进程的定义与特征一、进程的定义进程的概念，在上世纪60年代初期，就由麻省理工学院的Multics系统和IBM的CTSS/360系统引入了，其后又有不同的定义。MIT称进程process，IBM称任务task，Univac称为活动action。能反映进程实质的定义有：28（1）进程是程序在处理机上的一次执行过程。（2）进程是可以和别的计算并发进行的计算。（3）进程可定义为一个数据结构及能在其上进行操作的一个程序（4）进程是一个程序及其数据在处理机上顺序执行时所发生的活动（5）进程是程序在一个数据集合上的运行进程，是系统进行资源分配和调度的一个独立单位。本教程中，将进程定义为：进程是一个程序段在一个数据段上的一次执行过程。又叫顺序进程Sequentialprocess29二、进程的特征(与程序比)进程具有五个基本特征，和程序不一样。1、动态性动态性是进程最基本的特性。其动态性表现在：它由创建而产生，由调度而执行，因得不到资源而暂停执行，以及由撤消而消亡。即进程有一定的生命期。程序只是一组有序指令的集合，并存放在某种介质上，本身无运动的含义，所以程序是静态实体。302、并发性并发性是进程的重要特征，也是OS的重要特征。引入进程的目的也是为使程序能和其它进程的程序并发执行。程序是不能并发执行的。3、独立性进程实体是一个能独立运行的基本单位，也是系统中独立获得资源和独立调度的基本单位，即为独立性。凡未建立进程的程序，都不能作为一个独立的单位参加运行。314、异步性进程按各自独立的、不可预知的速度向前推进；或者说，进程按异步方式运行。为异步性。5、结构特征进程是由程序段、数据段和进程控制块组成，这三部分统称为：进程映象processimage。32三、进程和程序的关系(一般了解)进程和程序是两个密切相关但又有所不同的概念，它们在以下几个方面存在区别和联系。（1）进程是程序及其数据在计算机上的一次运行活动，是一个动态的概念。进程的运行实体是程序，离开程序的进程没有存在的意义。从静态角度看，进程是由程序、数据和进程控制块组成的，而程序是一组有序的指令集合，是一种静态的概念。。（2）进程是暂时的，程序是永久的。进程是一个状态变化的过程，程序可以长久保存。（3）进程与程序的组成不同，进程的组成包括程序、数据和进程控制块。33（4）进程与程序是密切相关的。通过多次执行，一个程序可以对应多个进程，通过调用关系，一个进程可以包括多个程序。进程可创建其他进程，而程序并不能形成新的程序。m：n的关系。34一个进程的生命期可以划分为一组状态，这些状态刻画了整个进程。在进程的运行过程中，由于系统中多个进程的并发运行及相互制约的结果，使得进程的状态不断变化。通常，一个进程至少可划分为三种基本状态。352.2.2进程的基本状态:三态模型一、进程的三种基本状态1、就绪状态(ready)当进程已分配到除CPU以外的所有必要的资源后，只要能再获得处理机，就可执行，这种进程状态称为就绪状态。多个进程排成一个或多个就绪队列。三种情况的进程形成就绪队列。新建进程一般处于就绪状态。362、执行（运行）状态running单处理机系统中，只有一个进程处于执行状态，多处理机系统中，可有多个进程处于执行状态。又称运行状态。373、阻塞状态（blocked）或等待态wait或睡眠态sleep进程因发生某事件（请求I/O或申请缓冲空间等）而暂停执行时的状态，称为暂停状态或阻塞状态，又称等待或睡眠状态。多个处于阻塞状态的进程排成一阻塞队列。有的系统中，会按阻塞原因的不同而将处于阻塞状态的进程排成多个队列。38注意前两种状态在逻辑是类似的，处于这两种状态的进程都是可以运行的，只是对于第一种状态暂时没有CPU分配给它。第三种状态不能运行，即使CPU空闲也不行。39中断发生后操作系统最底层的工作步骤硬件压入堆栈程序计数器、PSW等硬件从中断向量(在内存低地址)装入新的程序计数器汇编语言过程保存寄存器值汇编语言过程设置新的堆栈C中断服务例程运行(典型地读和缓冲输入)调度程序决定下一个将运行的进程C过程返回至汇编代码汇编语言过程开始运行新的当前进程40可用一个进程状态变化图来说明系统中每个进程可能具备的状态，及这些状态发生变化的可能原因。执行阻塞就绪等待事件事件发生时间片用完进程调度进程状态图42从图中可以看出：就绪状态可以变为执行状态：就绪进程获得处理器资源（分派处理器时间片）执行状态可以变为阻塞状态：请求某一资源的使用和分配或等待某一事件发生。这时候会发生进程上下文的切换。（用户级上下文、寄存器上下文和系统级上下文）阻塞状态可以变为就绪状态：等待事件发生，由中断处理程序把相应进程由阻塞转换为就绪。执行状态可以转变为就绪状态：时间片用完或被抢占。43进程切换由内核实现，是指当前正在运行的进程被转换到其他状态后，再回到运行状态继续执行，这个过程中，进程的运行环境产生了实质性的变化。切换过程：1）保存处理器上下文，包括程序计数器和其他寄存器。2）更新进程控制块信息。3）把进程的进程控制块移入相应的队