计算机操作系统第四版第2章进程管理

第二章进程管理输入设备外围机磁盘主机外围机输出设备•–减少了CPU的空闲时间。–提高I/O速度。1.2.1无操作系统的计算机系统2.脱机输入/输出(Off-LineI/O)方式第二章进程管理把下一个作业的源程序转换为目标程序源程序有错吗？否装配目标程序还有下一个作业？是否停止运行目标程序是开始1.2.2单道批处理系统监督程序的处理过程第二章进程管理作业和进程的状态转换图数据进入状态退出状态后备状态运行状态作业控制进程…输入设备数据源程序输出设备作业说明书输入井运行等待就绪输出井输入程序输出程序作业调度进程调度多道批处理系统第二章进程管理分时技术：把处理机的响应时间分成若干个大小相等（或不相等）的时间单位，称为时间片（如100毫秒），每个终端用户获得CPU，就等于获得一个时间片，该用户程序开始运行，当时间片到（用完），用户程序暂停运行，等待下一次运行。例如：我们上课。分时操作系统：是利用分时技术实现多道程序设计的一种操作系统，它一般采用时间片轮转的办法，使一台计算机同时为多个终端用户服务，对每个用户都能保证足够快的响应时间，并提供交互会话功能。第二章进程管理第二章进程的描述与控制2.1前趋图和程序执行2.2进程的描述2.3进程控制2.4进程同步2.5经典进程的同步问题2.6管程机制2.7进程通信2.8线程的基本概念和实现第二章进程管理前趋图(PrecedenceGraph)是一个有向无循环图，记为DAG(DirectedAcyclicGraph)，用于描述进程之间执行的前后关系。图中每个结点可用于描述一条语句、一个程序段或进程结点间的有向边则表示在两结点之间存在的偏序或前趋关系“→”，→={（Pi，Pj）|PimustcompletebeforePjmaystart}如果（Pi，Pj）∈→，可写成Pi→Pj；，称Pi是Pj的直接前趋，而Pj是Pi的直接后继。在前趋图中，没有前趋的结点称为初始结点(InitialNode)，没有后继的结点称为终止结点(FinalNode)。2.1前趋图和程序执行2.1.1前趋图(a)程序的顺序执行(b)三条语句的顺序执行I1C1P1I2C2P2S1S2S3S1→S2→S3第二章进程管理每个结点还可具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。前趋图P1P3P8P9P4P2P5P6P7S1S2S3(a)具有九个结点的前趋图(b)具有循环的有向图第二章进程管理图2－l示出的前趋图，存在下面的前趋关系：P1→P2,P1→P3，P1→P4，P2→P5，P3→P5，P4→P6,P5→P7，P6→P7或表示为：P={P1,P2,P3,P4,P5,P6,P7}→={(P1，P2)，(P1，P3)，(P1，P4)，(P2，P5)，(P3，P5)，(P4，P6)，(P5，P7)，(P6，P7)}注意：前趋图中必须不存在循环。2.1.1前趋图第二章进程管理一、概念•一个程序由若干个程序段组成，在各程序段之间，必须按照某种先后次序顺序执行，仅当前一(程序段)执行完后，才能执行后继操作。这种程序执行的方式就称为程序的顺序执行。•例如：(a)程序的顺序执行(b)三条语句的顺序执行I1C1P1I2C2P2S1S2S32.1.2程序的顺序执行第二章进程管理1.顺序性处理机严格按照程序所规定的顺序执行，即每个操作必须在下一个操作开始之前结束。2.封闭性程序一旦开始执行，其执行结果不受外界的影响。3.可再现性程序执行的结果与初始条件有关，而与执行时间无关。二、程序顺序执行的特点第二章进程管理•例：在系统中有n个作业，每个作业都有三个处理步骤，输入数据、处理、输出，即Ii,Ci,Pi(i=1,2,...,n)。•这些作业在系统中执行时是对时间的偏序，有些操作必须在其它操作之前执行，这是有序的，但有些操作是可以同时执行的。例如:I1、C1、P1的执行必须严格按照I1，C1，P1的顺序，而P1与I2，C1与I2,I3与P1是可以同时执行的。图中存在下面的前趋关系：Ii→Ci,Ii→Ii＋1,Ci→Pi,Ci→Ci＋1,Pi→Pi＋1而Ii＋1和Ci及Pi－1是重迭的，它们可以并发执行。P1P2P3P4I1I2I3I4C1C2C3C42.1.3程序的并发执行并发执行时的前趋图第二章进程管理程序并发执行（定义）•若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。PQR并发执行区2.1.3程序的并发执行及其特征第二章进程管理程序并发执行的描述：cobeginS1;S2;S3;...;SNcoend;Si(i=1,2,3,...,n)表示n个语句（程序段），这n个语句用cobegin和coend括起来表示这n个语句是可以并发执行的。这是Dijkstra提出的。2.1.3程序的并发执行及其特征第二章进程管理假设有一个程序由S0～Sn+1个语句，其中S1～Sn语句是并发执行的，程序如下：S0;parbeginS1;S2;S3;...;SNparend;Sn+1;2.1.3程序的并发执行及其特征第二章进程管理程序并发执行时的特征1、间断性2、失去了程序的封闭性3、不可再现性；2.1.3程序的并发执行及其特征第二章进程管理例如:有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N∶=N+1操作；程序B每执行一次时，都要执行Print(N)操作，然后再将N置成“0”。程序A和B以不同的速度运行。A:B:L1:N=N+1;①L2:Print(N);②gotoL1;N=0;③gotoL2;第二章进程管理2.2进程的描述•在多道程序设计的环境下，系统中有多个程序同时运行。此时的程序具有间断性、失去了程序的封闭性、不可再现性等特征。•程序一旦运行起来，它不但与程序本身有关，而且与它运行时所处的运行环境有关，程序的活动不再是静态的、封闭的，而显现出并发性、动态性以及相互制约的关系。所以用程序的概念已经不能描述上述这些特征，于是引入进程的概念。•进程的概念来自于麻省理工的MULTICS、IBM的TSS/360，在IBM的OS/360/370系统中也曾叫过任务(task)。第二章进程管理•行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程（Dijkstra)。•进程是这样的计算部分，它是可以和其它计算并行的一个计算。(Donovan)•进程（有时称为任务）是一个程序与其数据一道通过处理机的执行所发生的活动。（Alan.C.Shaw)•进程是执行中的程序。（KenThompsonandDennisRitchie)•教材上给出的进程的定义：–进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。进程的定义第二章进程管理（1）结构特征：进程实体是由程序段、相关的数据段和进程控制块(PCB，processcontrolblock)三部分组成。（2）动态性：进程的实质是进程实体的一次执行过程，它有着创建、活动、暂停、终止等过程，具有一定的生命期。（3）并发性：多个进程实体同存于内存中，且能在一段时间内同时运行。（4）独立性：进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。（5）异步性：各个并发进程按照各自独立的、不可预知的速度向前推进。进程的特征第二章进程管理1、程序是指令的集合，是静态的概念。进程是程序在处理机上的一次执行过程，是动态的概念。程序可以作为软件资料长期保存。进程是有生命周期的。2、进程能与其它进程并发活动。而程序则不是。3、进程能独立运行、独立分配资源和独立接受调度。而未建立PCB的程序是不能作为一个独立单位运行的。4、一个进程可以运行多个程序。例如：一个进程进行C源程序编译时，它要执行前处理、词法语法分析、代码生成和优化等几个程序。反之，同一程序也可能由多个进程同时执行。例如：上述C编译程序可能同时被几个进程执行，它们对相同或不同的源程序分别进行编译，各自产生目标程序。进程与程序的区别与联系第二章进程管理•例子：光盘（CD、VCD）•光盘（程序）放光盘的活动（进程）进程与程序的区别与联系第二章进程管理进程在系统中的活动规律是：执行暂停执行进程的三种基本状态：执行状态就绪状态阻塞状态（又称等待，睡眠）进程的三种基本状态第二章进程管理1.就绪状态(Ready)•若进程已具备了运行条件，只因CPU被别的进程占用而不能被CPU执行，则称此时进程处于就绪状态。一旦把CPU分配给它，该进程就可以运行。•从宏观上讲，它是一种逻辑上的可运行状态。•系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。进程的三种基本状态第二章进程管理2.执行状态(Running）•当一个进程已分配到CPU，它的程序正在被CPU执行时进程所处的状态称执行状态，也称为运行状态。•对于单CPU系统而言，处于执行状态的进程只可能有一个。进程的三种基本状态第二章进程管理3.阻塞状态(Wait)•正在执行的进程由于发生某事件（如I/O请求、申请缓冲区失败等）暂时无法继续执行便放弃CPU时所处的状态称阻塞状态(等待状态)。•一旦引起阻塞的原因消失，进程便转为就绪状态。以便在适当的时候占用CPU。•系统中处于阻塞状态的进程可能有多个，通常也将它们排成一个队列。有的系统按照进程不同的阻塞原因，把处于阻塞状态的进程排成多个队列。进程的三种基本状态第二章进程管理1．就绪状态→执行状态2．执行状态→阻塞状态3．执行状态→就绪状态4.阻塞状态→就绪状态时间片完进程状态的转换：进程的三种基本状态的转换•进程的动态性决定了它不会固定处于某个状态，系统中的进程由于各种不同的原因在以上各个状态之间变化。其状态变化及原因如图所示。第二章进程管理创建状态和终止状态•（1）创建状态：一个进程刚刚建立(申请到了PCB)，但还未将它插入就绪队列时所处的状态。•（2）终止状态：一个进程已经正常结束或异常结束，等待操作系统进行善后处理时所处的状态。第二章进程管理创建进程的基本过程是：(进程创建原语Creat())•(1)申请空白PCB。从空闲的PCB集合中申请一个新的PCB，同时获得该进程的内部标识；•(2))为新进程分配其运行所需的资源；•(3)初始化进程控制块PCB。向该PCB中填写各种参数；•(4)将新进程插入到就绪队列。把该进程的状态设置成就绪状态，并将该PCB插入到就绪队列中。引入创建状态的原因：保证进程调度必须是在创建工作完成后进行，确保对PCB操作的完整性；增加管理的灵活性。进程的创建第二章进程管理进程状态的转换1．创建状态→就绪状态2．就绪状态→执行状态3．执行状态→阻塞状态4．执行状态→就绪状态5．执行状态→终止状态6．阻塞状态→就绪状态进程状态变迁图时间片完创建终止第二章进程管理进程的挂起状态使正在执行的进程暂停执行；若此时用户进程正处于就绪状态而未执行，则该进程暂不接受调度，我们把这种静止状态称为挂起状态(静止状态)。引入挂起状态的原因有：1．终端用户的需要终端用户在自己的程序运行期间发现有可疑问题，希望暂时使自己的程序静止下来。2．父进程请求3．负荷调节的需要4．操作系统的需要操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记帐。第二章进程管理带有挂起状态时的进程状态转换•所谓原语就是计算机机器指令的延伸，它是由若干条机器指令构成，并完成一种特定功能的程序段。•原语操作由操作系统内核提供。•为保证原语操作的正确性，还规定原语在执行期间必须一次执行完，中间不允许被中断。也就是说，原语具有原子性，即原语操作中的所有指令（动作）要么全做，要么全不做，不允许被分割。在单CPU系统中，在执行原语的过程中一般要关中断。第二章进程管理1．活动就绪→静止就绪：当进程处于未被挂起的就绪状态时，称此为活动就绪状态，表示为Readya。当用挂起原语Suspend将该进程挂起后，该进程便转变为静止就绪状态，表示为Readys。处于Readys状态的进程，不再被调度执行。2