计算机操作系统第二章(new)
1,第二章 进程的描述与控制,2,主要目录,进程的引入 2.1 前趋图和程序执行 2.2 进程的描述 2.3 进程控制 2.4 线程的基本概念 2.5 总结本章基础要点 2.6 作业,3,进程的引入,进程的概念是操作系统中最基本、最重要的概念。它是在多道程序系统出现后，为了刻划系统内部出现的情况，描述系统内部各作业的活动规律而引进的一个新的概念。,4,引 子,在多道批处理系统和分时系统中，程序并不能独立运行，作为资源分配和独立运行的基本单位是进程。 操作系统所具有的四大特征也都是基于进程而形成的，并可从进程的观点来研究操作系统，形成了所谓的进程观点。,5,2.1 前趋图和程序(顺序或并发)执行,2.1.1 程序顺序执行:说明有些进程是先后运行的。 一、程序顺序执行 二、程序顺序执行时的特征 2.1.2 前趋图的定义 2.1.3 程序并发执行 一、程序并发执行 二、程序并发执行时的特征 2.1.4 程序并发执行的条件,6,一、程序顺序执行 一般一个程序的执行从整体上，必须按照某个次序顺序执行。,2.1.1 程序顺序执行,7,对某一个程序段中的多条语句，也有一个执行顺序，如下三条语句的程序段： S1：a:=x+y S2: b:=a-5 S3: c:=b+1 S2必须在a被赋值后，才能执行，S3只能在b被赋值后才能执行。 二、程序顺序执行时的特征 1、顺序性 处理机的操作，严格按照程序所规定的顺序执行，即每一个操作必须在下一个操作开始之前结束。,2.1.1 程序顺序执行,8,2、封闭性 程序是在封闭的环境下运行的，即程序在运行时，它独占全机资源，因而本机各资源的状态(除初始状态外)，只有本程序才能改变它。一旦开始运行，其执行结果不受外界因素的影响。,2.1.1 程序顺序执行,9,3、可再现性 只要程序执行时的环境和初始条件相同，当程序多次重复执行时，不论它是从头到尾不停顿地执行，还是停停走走地执行，都将获得相同的结果。即程序的执行结果与时间无关。,2.1.1 程序顺序执行,10,前趋图(Procedence Graph)是一个有向无循环图DAG(Directed Acyclic Graph)。用于描述进程之间执行的前后关系。 图中的每个结点用于表示一条语句、一个程序段或进程，结点间的有向边表示在两结点之间存在的偏序(Partial Order)或前趋关系(Procedence Relation)“ ”， =(Pi,Pj)|Pi must complete before Pj may start。 若(Pi,Pj)属于 ，可写成Pi Pj ,称Pi是Pj的前趋，而Pj是Pi的直接后继。 没有前趋的结点称为初始结点，没有后继的结点称为终止结点。 每个结点具有一个重量，用该结点所含的程序量或结点的执行时间来计量。,2.1.2 前趋图的定义,11,如上图示：有下面的前趋关系： P=P1,P2,P3,P4,P5,P6,P7 =(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P5,P7),(P6,P7) 注：前趋图中必须不存在循环。,12,一、程序并发执行 在前述问题中，输入程序、计算程序和打印程序存在着Ii Ci Pi 的前趋关系，对每一个作业的输入、计算和打印三个操作，都必须顺序执行，但不存在Pi Ii+1的关系。,2.1.3 程序并发执行,13,所以，对一批这样的程序进行处理时，可使它们并发执行。 如：输入程序在输入第一个程序后，在计算程序对该程序进行计算的同时，可由输入程序再输入第二个程序，从而使第一个程序的计算操作与第二个程序的输入操作并发执行。 如图示：,2.1.3 程序并发执行,15,该图中存在着如下前趋关系： Ii Ci Ii Ii+1 Ci Pi Ci Ci+1 Pi Pi+1 其中 Ii+1 和 Ci 及 Pi-1 是重叠的。即Pi-1 和 Ci 及 Ii+1 可并发执行。 即两个不同的程序间，在不同的程序段间存在着前趋关系。,2.1.3 程序并发执行,16,同一程序内也可并发进行 如下四条语句的程序段： S1：a:=x+2 S2: b:=y+4 S3: c:=a+b S4: d:=c+6 其前趋关系如图： 从中看出：S3须在a和b被赋值后才能执行， S4须在S3后才能执行，但S1和S2可以并发 执行，互不依赖。,2.1.3 程序并发执行,17,二、程序并发执行时的特征 1、间断性 程序并发执行时，由于它们共享资源或为完成同一项任务而相互合作，致使在并发程序之间形成了相互制约的关系。,2.1.3 程序并发执行,18,一旦使某程序暂停的因素消失后，如Ii处理完成，C便可恢复对Ci的处理。 从中看出，相互制约将导致并发程序具有“执行-暂停执行-执行”这种间断性的活动规律。,2.1.3 程序并发执行,19,2、失去封闭性 程序并发执行时，多个并发程序共享系统中的各种资源，所以这些资源的状态被多个程序来改变，致使程序的运行失去了封闭性。这样一个程序在执行时，会受到其它程序的影响。 如：当处理机资源被某程序占用时，其他程序必须等待。,2.1.3 程序并发执行,20,3、不可再现性 程序并发执行时，失去了封闭性，必然导致失去其运行结果的可再现性。 如：有两个循环程序A和B，共享一个变量N。 A每执行一次时，要做一次N:=N+1操作。B每执行一次时，要执行一次Print(N)操作，然后，清N为0。A和B以不同的速度运行。,2.1.3 程序并发执行,21,假定某时刻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.3 程序并发执行,22,从上可知，程序并发执行时，会失去封闭性，其计算结果与并发程序的执行速度有关，而使程序失去了可再现性，即程序经过多次执行后，虽其执行时的环境和初始条件相同，但结果却不相同。,2.1.3 程序并发执行,23,由上可知，程序并发执行，虽可有效地提高资源利用率和系统的吞吐量，但必须使并发程序能保持可再现性。也是使程序并发执行的条件。 定义一些符号： R(pi)=a1,a2,am,用来表示程序pi在执行期间所需参考的所有变量的集合，称“读集”。 W(pi)=b1,b2,bm，是程序pi在执行期间要改变的所有变量的集合，称“写集”。,2.1.4 程序并发执行的条件,24,若有两条语句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)=,2.1.4 程序并发执行的条件,25,2.1.4 程序并发执行的条件,读集和写集的交，也可能不是空集。 如：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)=,26,其中，前两个条件保证一个程序在两次操作之间存储器中的数据不会发生变化；最后一个条件保证程序写操作的结果不会丢失。只要同时满足三个条件，并发执行的程序就可以保持封闭性和可再现性。但这并没能解决所有问题，在实际程序执行过程中很难对这三个条件进行检查。 如：四条语句： s1:a:=x+y s2:b:=z+1 s3:c:=a-b s4:w:=c+1,2.1.4 程序并发执行的条件,27,R(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也不可并发执行。原因？,2.1.4 程序并发执行的条件,28,2.2 进程的描述,2.2.1 进程的定义与特征 一、进程的定义 二、进程的特征 2.2.2 进程的基本状态 一、进程的三种基本状态 二、新状态和终止状态 三、进程状态的转换 2.2.3 进程的挂起状态 一、挂起状态的引入 二、进程状态的转换 2.2.4 进程控制块PCB 一、进程控制块PCB 二、进程控制块中的信息 三、PCB的组织方式,29,为了使程序能在多程序环境下并发执行，并能对并发执行的程序加以控制和描述，专门配置了一个称为“进程控制块”的数据结构。其中放了进程标识符、进程运行的当前状态、程序和数据的地址，以及能保存该程序运行时CPU的环境信息。 这样，由程序段、数据段及进程控制块构成了一个进程的实体。,2.2 进程的描述,30,一、进程的定义 进程的概念，在上世纪60年代初期，就由麻省理工学院的Multics系统和IBM的CTSS/360系统引入了，其后又有不同的定义。能反映进程实质的定义有：,2.2.1 进程的定义与特征,31,（1）进程是程序在处理机上的一次执行过程。 （2）进程是可以和别的计算并发进行的计算。 （3）进程可定义为一个数据结构及能在其上进行操作的一个程序 （4）进程是一个程序及其数据在处理机上顺序执行时所发生的活动 （5）进程是程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立单位。 本教程中，将进程定义为：,进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。,2.2.1 进程的定义与特征,32,二、进程的特征(与程序比) 进程具有五个基本特征，和程序不一样。 1、动态性 进程是进程实体的执行过程，所以，动态性是进程最基本的特性。其动态性表现在：它由创建而产生，由调度而执行，因得不到资源而暂停执行，以及由撤消而消亡。即进程有一定的生命期。 程序只是一组有序指令的集合，并存放在某种介质上，本身无运动的含义，所以程序是静态实体。,2.2.1 进程的定义与特征,33,2、并发性 当多个进程实体，同时存于内存中时，能在一段时间内同时运行。即为并发性。并发性是进程的重要特征，也是OS的重要特征。引入进程的目的也是为使进程实体能和其它进程实体并发执行。 程序是不能并发执行的。 3、独立性 进程实体是一个能独立运行的基本单位，也是系统中独立获得资源和独立调度的基本单位，即为独立性。 凡未建立PCB的程序，都不能作为一个独立的单位参与运行。,2.2.1 进程的定义与特征,34,4、异步性 进程按各自独立的、不可预知的速度向前推进；或者说，进程按异步方式运行。 当然，这样会导致程序的不可再现性。OS要采取某种措施保证各程序之间能协调运行。 5、结构特征 进程是由程序段、数据段和进程控制块组成，这三部分统称为：进程映象。,2.2.1 进程的定义与特征,35,三、进程和程序的关系 进程和程序是两个密切相关但又有所不同的概念，它们在以下几个方面存在区别和联系。 （1）进程是动态的，程序是静态的。进程是程序的执行；程序是有序代码的集合。 （2）进程是暂时的，程序是永久的。进程是一个状态变化的过程，程序可以长久保存。 （3）进程与程序的组成不同，进程的组成包括程序、数据和进程控制块。,2.2.1 进程的定义与特征,36,（4）进程与程序是密切相关的。通过多次执行，一个程序可以对应多个进程，通过调用关系，一个进程可以包括多个程序。进程可创建其他进程，而程序并不能形成新的程序。,2.2.1 进程的定义与特征,37,一个进程的生
