第3章 进程与处理机管理

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,、若程序,PA,和,PB,单独执行时分别用,TA,和,TB,，,TA=1,小时，,TB=1.5,小时，其中处理机工作时间分别为,TA=18,分钟，,TB=27,分钟。如采用多道程序设计方法，让,PA,、,PB,并行工作，假定处理机利用率达到,50%,，另加,15,分钟系统开销，问系统效率能提高百分之几,?,2,、某个异常事件在处理过程中又发生了新的异常事件（如处理溢出时，处理过程中又产生了溢出），可以再转该种中断处理程序吗？,3,、在操作系统中，并发性是指若干个事件,(),发生。,A,在同一时刻,B,一定在不同时刻,C,在某一时间间隔内,D,依次在不同时间间隔内,4,、作业在执行中发生了缺页中断，经操作系统处理后，应让其执行,(),指令。,A,被中断的前一条,B,被中断的那一条,C,被中断的后一条,D,启动时第一条,第,3,章 进程与处理机管理,3.1,进程描述,OS,内在的本质和特征是动态和并发，需引出新的概念。,进程,：是系统内独立运行的实体，也是独立争夺资源的基本实体。是程序在多道程序设计系统中特殊的活动形式。,下面分析程序基本特征，引申出进程概念。,一、程序的基本特征,1.,顺序执行：,每一个动作在前一个动作结束后开始,(,图,2.1),。,2.,程序与其执行过程一一对应：一个静态程序对应一个动态执行过程。,3.,封闭性：独占系统分配的所有资源，执行过程不受外界因素的影响。,4.,可再现性：程序对同一组数据的重复执行，必获得相同的结果。,二、多道程序设计系统中的程序运行环境,1.,资源共享：为提高资源利用率，许多资源不再由一道程序独占使用。,2.,程序并行执行：为提高系统效率，多道程序设计系统广泛采用并行技术，尽可能控制多道程序并行执行，表现为：存储器内保存多个程序，,I/O,设备被多个程序交替使用，多道程序交替占用,CPU(,图,2-1,）。,三、并发程序的基本特征,1.,并发性：对于一个程序内部原理在指令序列上必须顺序进行的操作，只要可能，操作系统便同时进行。例如：程序中一条,I/O,指令和后续的,CPU,计算指令可并行，破坏了顺序性，使得程序内部许多不同操作可以并发产生。,2.,程序与其执行活动不再一一对应：例如，一个程序段可在内部对应多个执行活动。,3.,失去封闭性。（例如，某公司两个职员将存款共同保存在,Count,变量中，使用一个增加存款的并发程序见下页。）,4.,程序活动时的相互制约性：独立运行的程序会因竞争同一资源相互制约。逻辑上协同完成同一任务的程序之间存在相互等待对方的执行结果。,Parbegin,program,A:begin,N:=count,N:=N+100,count:=N,end,program,B:begin,M:=count,M:=M+200,count:=M,end,Parend,（另见书,P16,页例）,假设,count,中原数为,300,。两职员同时存款，并发执行程序,A,、,B,，不同的执行序列使得,count,具有不同的存款数。并发执行的结果必须与串行的结果相同才可认为是正确的。,3.1.1,进程定义,进程由以下几方面组成：,一个可执行的程序,一个独立的用户地址空间,系统资源,一个执行栈区，包括运行现场信息,程序、数据、栈的集合称作进程映像。,P17,进程定义,3.1.2,进程控制结构,进程控制块（,PCB,）,：用以标识进程存在、刻画其瞬间特征的数据结构（,P23,图,2-5,）。,PCB,应包含以下信息：,（,1,）进程名和标识码。进程名是进程的外部名字，由进程的创建者规定。标识码是内部名，是一个唯一的进程编号。,（,2,）位置信息。指示在存储器中的物理位置。,（,3,）状态信息。指明进程当前所处活动状态。,（,4,）调度的优先数。,（,5,）通讯有关的信息。如消息队列指针等。,（,6,）现场保护区。将与运行有关的信息保存。,（,7,）资源需求、分配和控制方面的信息。,（,8,）其他。如计时等信息。,说明：进程控制块是进程存在的唯一标识，系统创建一个进程时，为其建立相应的,PCB,，进程消亡时，系统删除,PCB,，所有,PCB,均存储于系统空间。,P26,图,2-8,3.2.1,进程的创建与结束,进程是用于运行用户程序的实体，都要经历被创建到运行结束的过程。,1.,进程创建,系统提供了进程创建的系统调用。,2.,进程结束,释放进程占用的资源，释放进程控制块。,3.2,进程状态,3.2.2,进程状态变化模型,运行状态：一个进程正在处理机上运行。,就绪状态：一个进程获得了除处理机以往的一切所需资源，一旦得到处理机即可运行。,等待状态：又称阻塞状态。一个进程正在等待某一事件而暂停运行。,运行态,就绪态,阻塞态,P20,图,2-3,进程状态之间可能的变迁,P20,例,2-2,3.2.3,进程挂起,为了能使处于等待状态的进程释放主存空间，系统将其交换到辅存，进程便处于挂起状态。,P22,图,2-4,1,、当一个进程从等待态变成就绪态，则一定有一个进程从就绪态变成运行态。（）,2,、分时系统进程可能出现的状态变化图，说出每一个状态变化原因。,运行,等待磁盘读文件,等待打印机,输出结果,1,2,3,4,5,6,3,、兄弟俩共同使用一个帐号，每次限存或取十元，存钱与取钱的进程分别如下所示：,begin,amount:integer;,amount:=0;,cobegin,process,SAVE,m1:integer;,begin,m1:=amount;,m1:=m1+10;,amount:=m1;,end;,process,TAKE,m2:integer;,begin,m2:=amount;,m2:=m2-10;,amount:=m2;,end;,coend;,end;,由于兄弟俩可能同时存钱和取钱，因此两个进程是并发的。若哥哥先存了两次钱，但在第三次存钱的时候，弟弟在取钱。请问最后帐号,amount,上面可能出现的值？,4,、对基本的进程状态转换图中的状态转换编号,1,、,2,、,3,、,4,。令,I,和,J,分别取值,1,、,2,、,3,、,4(J,不等于,I),。请分别讨论在状态转换,I,和状态转换,J,之间是否存在因果关系；若存在，请指出这种关系是必然的，或是有条件的，条件是什么,?,运行,阻塞,就绪,1,2,3,4,5,、下列的进程状态变化中，,(),的变化是不可能发生的。,A,等待运行,B,运行等待,C,运行就绪,D,等待就绪,3.3,进程控制与调度,3.3.2,进程调度,1.,调度的概念,根本任务是按照某种原则为处于就绪状态的进程分配,CPU,。,进程调度不同于作业调度，作业调度主要是协调作业对计算,机系统内资源（如内存、,I/O,等）的争夺使用。,高调又称作业调度。,中调又称交换调度。,低调又称进程调度。,2.,进程调度方式,非剥夺方式：一旦某个进程被调度执行，则该进程一直执行下去至该进程结束，或因某种原因自行放弃,CPU,进入等待状态，才将,CPU,重新分配给其它进程。优点：有效减少调度活动。缺点：损失系统的并发性。,剥夺方式：一旦就绪状态中出现优先权更高的进程，或运行进程已运行了所规定的时间片时，便立即剥夺当前进程的运行（就绪态），把,CPU,分配给他人。特点：系统并发性强，进程控制较为复杂。,3.3.3,调度算法,相关概念：,周转时间,:,进程从创建到结束运行所经历的时间。,平均周转时间：,N,个进程周转时间的平均值。,等待时间：等待,CPU,的时间之和。,平均等待时间：,N,个进程的等待时间的平均值。,1.,先来先服务,(P27,图,2-10,）,例：有,5,个任务,A,到,E,几乎同时到达，它们预计运行时间为,10,，,6,，,2,，,4,，,8,分钟，其优先级分别为,3,，,5,，,2,，,1,和,4,，这里,5,为最高优先级。对于下列每一种调度，计算其平均进程周转时间（进程切换开销可不考虑）。,(1),先来先服务（按,A,，,B,，,C,，,D,，,E,）,2.,优先级调度,上例：,(2),优先级调度,3.,时间片轮转法,（,P28,图,2-11,）,时间片的大小对系统效率有影响，不可太大也不可太小，应能使,80%,的进程在时间片内完成一次所需的执行活动。,上例：,(3),时间片轮转（,P28,例,2-3,）,4.,短进程优先调度,例：在下表中给出进程的到达时间、执行时间和优先级，请给出三种调度算法的进程执行次序和三种调度算法的平均周转时间。这三种调度算法是：短作业优先调度算法、优先级高者优先调度算法和简单轮转法调度算法,(,简单轮转法中的时间片为,2,个单位,),。,进程,到达时间,执行时间,优先级,P1,0,10,3,P2,2,1,1,P3,3,2,2,P4,5,1,4,P5,5,5,3,证明：若同时到达，短进程优先是平均周转周期最短的调度算法。,（上例）,5.,最短剩余时间,6.,最高响应比优先,优先数,=,（等待时间,+,运行时间）,/,运行时间,例：有,3,个进程,A,、,B,、,C,，它们分别在,750,、,800,和,830,到达，它们需要执行的时间分别是,1.5,个小时、,1,小时和,0.4,小时。系统在,900,开始按响应比的高者优先算法，对它们进行调度。请回答下列问题：,(1),进程被选中的执行次序是什么,?,(2),三个进程被选中时的响应比分别是什么,?,7.,多级反馈队列调度,P30,图,2-13,P31,图,2-14,1,、下面列出的是进程调度算法中选择进程的准则，其中面向用户的有,(),。,1,吞吐量高,4,周转时间短,2,公平性原则,5,各类资源的平衡利用,3,响应时间快,2,、一种既有利于短小作业又兼顾到长作业的作业调度算法是,(),。,A,先来先服务,B,轮转,C,最高响应比优先,D,均衡,调度,3,、例：有,5,个待运行进程为,A,，,B,，,C,，,D,，,E,，各自估计运行时间为,9,，,6,，,3,，,5,，,x,。试问采用哪种运行次序使得平均响应时间为最短,?,答：响应时间是进程从就绪到调度运行的时间长度，即等待时间；而进程的周转周期,=,等待时间,+,运行时间，其中运行时间是不变的，等待时间随着运行情况而改变，因此平均响应时间为最短，即平均周转周期为最短。,短进程优先是平均周转周期最短的调度算法。,本题中，若,x,3,，则次序为,E,，,C,，,D,，,B,，,A,；,若,3,x,5,，次序为,C,，,E,，,D,，,B,，,A,；,若,5,x,6,，次序为,C,，,D,，,E,，,B,，,A,；,若,6,x,9,，次序为,C,，,D,，,B,，,E,，,A,；,若,x,9,，次序为,C,，,D,，,B,，,A,，,E,。,4,、假设有五个进程，它们的提交时刻及运行时间由下表给出：若采用,FCFS,和,SPF,两种调度算法，指出进程以,单道串行方式,和,多道并行方式,运行时的被调度顺序及周转时间。,进程,到达时间,执行时间（小时）,P1,10:00,2,P2,10:05,1,P3,10:25,0.75,P4,12:25,0.5,P5,12:50,0.25,作业调度,1.,用户与操作系统的接口,1,）特权指令、管态、目态,2,）系统调用命令,3,）操作命令,2.,作业,与作业管理,1,）作业与作业步（图,2-20,）,2,）作业控制块（表,2-2,）,3,）作业调度,4,）作业的状态与状态的变迁（图,2-21,）,3.,作业调度算法,1,）先来先服务（,P41,例,2-7,、例,2-8,、例,2-9,）,2,）短作业优先（例,2-10,、,2-11,3,）响应比高者优先（例,2-12,）,3.4,作业与进程关系,作业是用户向计算机提交任务的任务实体，而进程则是具体完成任务的运行实体。作业在何时、如何分解成独立运行的实体？,1.,批处理系统中作业与进程的关系,转变过程：选择一道后备作业运行时，首先为该作业创