第3章 进程与处理机管理

1、若程序PA和PB单独执行时分别用TA和TB，TA=1小时，TB=1.5小时，其中处理机工作时间分别为TA=18分钟，TB=27分钟。如采用多道程序设计方法，让PA、PB并行工作，假定处理机利用率达到50%，另加15分钟系统开销，问系统效率能提高百分之几?2、某个异常事件在处理过程中又发生了新的异常事件（如处理溢出时，处理过程中又产生了溢出），可以再转该种中断处理程序吗？3、在操作系统中，并发性是指若干个事件()A在同一时刻BC在某一时间间隔内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.程序活动时的相互制约性：独立运行的程序会因竞争同一资源相互制约。逻辑上协同完成同一任务的程序之间存在相互等待对方的执行结果。ParbeginprogramA:beginN:=countN:=N+100count:=NendprogramB:beginM:=countM:=M+200count:=MendParend（另见书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-83.2.1进程的创建与结束进程是用于运行用户程序的实体，都要经历被创建到运行结束的过程。1.进程创建系统提供了进程创建的系统调用。2.进程结束释放进程占用的资源，释放进程控制块。3.2进程状态3.2.2进程状态变化模型①运行状态：一个进程正在处理机上运行。②就绪状态：一个进程获得了除处理机以往的一切所需资源，一旦得到处理机即可运行。③等待状态：又称阻塞状态。一个进程正在等待某一事件而暂停运行。运行态就绪态阻塞态P20图2-3进程状态之间可能的变迁P20例2-23.2.3进程挂起为了能使处于等待状态的进程释放主存空间，系统将其交换到辅存，进程便处于挂起状态。P22图2-41、当一个进程从等待态变成就绪态，则一定有一个进程从就绪态变成运行态。（）2、分时系统进程可能出现的状态变化图，说出每一个状态变化原因。运行等待磁盘读文件等待打印机输出结果1234563、兄弟俩共同使用一个帐号，每次限存或取十元，存钱与取钱beginamount:integer;amount:=0;cobeginprocessSAVEm1:integer;beginm1:=amount;m1:=m1+10;amount:=m1;end;processTAKEm2:integer;beginm2:=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之间是否存在因果关系；若存在，请指出这种关系是必然的，或是有条件的，条件是什么?运行阻塞就绪12345、下列的进程状态变化中，()的变化是不可能发生的。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，E2.优先级调度上例：(2)优先级调度3.时间片轮转法（P28图2-11）时间片的大小对系统效率有影响，不可太大也不可太小，应能使80%的进程在时间片内完成一次所需的执行活动。上例：(3)时间片轮转（P28例2-3）4.短进程优先调度例：在下表中给出进程的到达时间、执行时间和优先级，请给出三种调度算法的进程执行次序和三种调度算法的平均周转时间。这三种调度算法是：短作业优先调度算法、优先级高者优先调度算法和简单轮转法调度算法(简单轮转法中的时间片为2个单位)。进程到达时间执行时间优先级P10103P2211P3322P4514P5553证明：若同时到达，短进程优先是平均周转周期最短的调度算法。（上例）5.最短剩余时间6.最高响应比优先优先数=（等待时间+运行时间）/运行时间例：有3个进程A、B、C，它们分别在7∶50、8∶008∶30到达，它们需要执行的时间分别是1.5个小时、1小时和0.4小时。系统在9∶00开始按响应比的高者优先算法，对它们进行调度。请回答下列问题：(1)进程被选中的执行次序是什么?(2)三个进程被选中时的响应比分别是什么?7.多级反馈队列调度P30图2-13P31图2-141、下面列出的是进程调度算法中选择进程的准则，其中面向用户的有()1吞吐量高42公平性原则53响应时间快2、一种既有利于短小作业又兼顾到长作业的作业调度算法是()A先来先服务BC最高响应比优先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，E4、假设有五个进程，它们的提交时刻及运行时间由下表给出：若采用FCFS和SPF两种调度算法，指出进程以单道串行方式和多道并行方式运行时的被调度顺序及周进程到达时间执行时间（小时）P110:002P210:051P310:250.75P412:250.5P512:500.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-113）响应比高者优先（例2-12）3.4作业与进程关系作业是用户向计算机提交任务的任务实体，而进程则是具体完成任务的运行实体。作业在何时、如何分解成独立运行的实体？1.批处理系统中作业与进程的关系转变过程：选择一道后备作业运行时，首先为该作业创建一个根进程，该进程解释作业说明书，并动态创建一个或多个子进程，具体执行说明书中的语句。一个作业就动态地转换成一组运行实体“进程族”。说明：一道作业处于运行状态，实际上是指与作业相应的进程正在内部活动。P68图3.102.分时系统中作业与进程的关系转变过程：交互式作业在用户接通终端时系统为之建立一个进程（称为终端进程），该进程解释执行用户输入的每一条命令。用户每输入一条命令直接在内部对应一个（或若干）进程。