操作系统课程第3章处理机调度.

Page12019/12/30Page22019/12/30第三章处理机调度与死锁处理机调度的基本概念处理机调度的目标充分有效地利用处理机（CPU）资源调度算法实时调度产生死锁的原因和必要条件预防死锁的方法死锁的检测与解除Page32019/12/303.1处理机调度的基本概念操作系统调度级别进程调度的任务确定算法的原则进程调度方式调度队列模型选择调度方式和调度算法的若干准则Page42019/12/303.1处理机调度的基本概念3.1.1操作系统调度级别1.高级调度2.低级调度3.中级调度Page52019/12/303.1.1高级、中级和低级调度1.高级调度又称作业调度主要任务是按一定的原则对外存上处于后备状态的作业进行选择，给选中的作业分配内存、输入/输出设备等必要的资源，并建立相应的进程，插入就绪队列，以使该作业的进程获得竞争处理机的权利作业调度作业是用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合，包括用户程序、所需的数据及命令等作业状态:作业从提交给系统，直到完成任务后退出系统前，在整个活动过程中它会处于不同的状态。通常，作业状态分为四种：提交、后备、执行和完成，如图3-1所示。Page72019/12/30运行状态作业调度后备状态完成状态就绪阻塞执行I/O完成I/O请求时间片完作业提交作业调度进程调度终止作业作业状态间转换图3-1作业的基本状态Page82019/12/30数据提交状态退出状态后备状态运行状态作业控制进程…输入设备数据源程序输出设备作业说明书输入井运行等待就绪输出井输入程序输出程序作业调度进程调度（1）提交状态——即用户向系统提交一个作业时，该作业所处的状态。（2）后备状态——即用户作业经输入设备（如读卡机）送入输入井（磁盘）中存放，等待进入内存时所处的状况。（3）执行状态——即作业分配到所需的资源，被调入内存，并且在处理机（CPU）上执行相应的程序时所处的状况。（4）完成状态——即作业完成了计算任务，结果由打印机输出，最后由系统回收分配给它的全部资源，准备退出系统时的作业状况。作业状态作业控制块（JCB）在多道批处理系统中通常有上百个作业被收容在输入井（磁盘）中。为了管理和调度作业，系统为每个作业设置了一个作业控制块（JCB），它记录该作业的有关信息。JCB的主要内容如图3-2所示。作业调度作业控制块作业调度的功能作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转换。(1)记录系统中各个作业的情况。(2)按照某种调度算法从后备作业队列中挑选作业。(3)为选中的作业分配内存和外设等资源。(4)为选中的作业建立相应的进程。(5)作业结束后进行善后处理工作，如输出必要的信息，收回该作业所占用的全部资源，撤消与该作业相关的全部进程和该作业的JCB。Page132019/12/30高级、中级和低级调度在每次作业调度时，须决定：接纳多少个作业即允许多少个作业同时在内存中运行作业太多服务质量下降作业太少资源利用率低接纳哪些作业取决于作业调度算法先来先服务短作业优先作业优先权调度响应比调度→周转时间太长→系统吞吐量太低适当的折衷周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔。吞吐量：是指在单位时间内系统所完成的作业数。Page142019/12/303.1.1高级、中级和低级调度2.中级调度目的：是为了提高内存利用率和系统吞吐量。功能：－暂时不能运行的进程挂起，释放宝贵的内存资源。－具备条件时：把外存上的就绪进程，重新调入内存，挂在就绪队列上等待进程调度。外存阻塞队列阻塞进程队列作业4作业3作业2作业1进程3进程2进程1内存Page152019/12/303.1.1高级、中级和低级调度3.低级调度进程调度主要任务是按照某种策略和方法选取一个处于就绪状态的进程，将处理机分配给它常见的低级调度有非抢占式和抢占式两种Page162019/12/30处理机调度的层次Page172019/12/30作业调度又称为[1]，它决定将那些在外存储器上的处于[2]状态的作业调入主机内存，系统经作业调度程序选中一个或多个作业后，就为它们分配必要的内存、设备及软资源。然后控制权就交给了[3]，由[3]将它们变为一个或一组[4]。[1]()：A、高级调度B、低级调度C、中级调度D、进城调度[2]（）：A、就绪B、阻塞C、提交D、后备[3]（）：A、存储管理模块B、处理机管理模块C、文件管理模块D、设备管理模块[4]（）：A、指令B、子程序C、进程D、程序段Page182019/12/30处于后备状态的作业存放在（）中。A、外存B、内存C、A和BD、扩展内存在操作系统中，作业处于（）状态时，已处于进程的管理之下。A、后备B、阻塞C、执行D、完成Page192019/12/303.1处理机调度的基本概念高级、中级和低级调度进程调度的任务确定算法的原则进程调度方式调度队列模型选择调度方式和调度算法的若干准则Page202019/12/303.1.2进程调度的任务进程调度的任务是控制、协调进程对CPU的竞争,即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程Page212019/12/30处理机调度的基本概念高级、中级和低级调度进程调度的任务确定算法的原则进程调度方式调度队列模型选择调度方式和调度算法的若干准则Page222019/12/303.1.3确定算法的原则具有公平性资源利用率高（特别是CPU利用率）在交互式系统情况下要追求响应时间（越短越好）在批处理系统情况下要追求系统吞吐量Page232019/12/30处理机调度的基本概念高级、中级和低级调度进程调度的任务确定算法的原则进程调度方式调度队列模型选择调度方式和调度算法的若干准则Page242019/12/303.1.4进程调度方式非抢占方式抢占方式Page252019/12/30进程调度方式非抢占方式(Non-preemptiveMode)引起进程调度的因素正在执行的进程执行完毕，或因发生某事件而不能再继续执行执行中的进程因提出I/O请求而暂停执行；在进程通信或同步过程中执行了某种原语操作，如wait、Block、Wakeup原语优点：算法简单，系统开销小缺点：紧急任务不能及时响应；短进程到达要等待长进程运行结束Page262019/12/30进程调度方式抢占方式抢占式调度主要有以下原则优先权原则允许高优先权的新到进程抢占当前进程的处理机短作业(进程)优先原则允许执行时间短的新到进程抢占当前进程的处理机时间片原则时间片用完后停止执行，重新进行调度，适用于分时系统优点：适于时间要求严格的实时系统缺点：调度算法复杂，系统开销大Page272019/12/303.1处理机调度的基本概念高级、中级和低级调度进程调度的任务确定算法的原则进程调度方式调度队列模型选择调度方式和调度算法的若干准则Page282019/12/303.1.5调度队列模型仅有进程调度的调度队列模型具有高级和低级调度的调度队列模型同时具有三级调度的调度队列模型Page292019/12/303.1.5调度队列模型仅有进程调度的调度队列模型在分时系统中，通常仅设有进程调度系统把这些进程组织成一个就绪队列每个进程在执行时，可能有以下几种情况进程获得CPU正在执行任务在给定时间片内已完成，释放处理机后为完成状态任务在时间片内未完成，进入就绪队列末尾在执行期间因某事件而阻塞Page302019/12/303.1.5调度队列模型仅有进程调度的调度队列模型就绪队列阻塞队列进程调度CPU进程完成等待事件交互用户事件出现时间片完Page312019/12/303.1.5调度队列模型具有高级和低级调度的调度队列模型在批处理系统中，不仅需要进程调度，而且还要有作业调度就绪队列的形式在批处理系统中，常用高优先权队列。进程进入就绪队列时，按优先权高低插入相应位置，调度程序总是把处理机分配给就绪队首进程设置多个阻塞队列根据事件的不同设置多个队列提高效率Page322019/12/303.1.5调度队列模型进程调度CPU进程完成时间片完就绪队列…12等待事件等待事件等待事件n12n事件出现事件出现…事件出现后备队列作业调度……与上一模型的主要区别：就绪队列的形式；设置多个阻塞队列阻队列塞2阻队列塞n阻队列塞1Page332019/12/303.1.5调度队列模型同时具有三级调度的调度队列模型就绪队列进程调度就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现事件出现CPUPage342019/12/303.1处理机调度的基本概念高级、中级和低级调度进程调度的任务确定算法的原则进程调度方式调度队列模型选择调度方式和调度算法的若干准则如果你是用户，你希望系统如何为你服务，如何考虑？？如果你是调度者，从系统整体角度出发，应如何考虑？？Page352019/12/303.1.6选择调度方式和调度算法的若干准则1.面向用户的准则2.Page362019/12/303.1.6选择调度方式和调度算法的若干准则1.面向用户的准则(1)周转时间短。(2)响应时间快。(3)截止时间的保证。(4)优先权准则。Page372019/12/30选择调度方式和调度算法的若干准则面向用户的准则周转时间短平均周转时间niiTnT11niSiiTTnW11带权周转时间：进程（或作业）的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS。而平均带权周转时间则可表示为:Page382019/12/30通常把周转时间作为评价批处理系统的性能、选择作业调度方式与算法的准则。所谓周转时间，是指从作业提交给系统开始，到作业完成为止的这段时间间隔(称为作业周转时间)。它包括：(1)作业在外存后备队列上等待(作业)调度的时间；(2)进程在就绪队列上等待进程调度的时间；(3)进程在CPU上执行的时间；(4)等待I／O操作完成的时间。其中，第(2)、(3)、(4)项在一个作业的处理过程中，可能发生多次。Page392019/12/30可把平均周转时间描述为：iiiTnT11niSiiTTnW11作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权周转时间，而平均带权周转时间则可表示为:系统以多个用户都满意为目标周转时间＝服务时间周转时间＝完成时间－到达时间Page402019/12/30选择调度方式和调度算法的若干准则面向用户的准则响应时间快响应时间是指从用户通过键盘提交一个请求开始，直至系统中首次产生响应为止的时间截止时间保证截止时间是指某任务必须开始执行的最迟时间或必须完成的最迟时间截止时间是实时系统中的重要指标Page412019/12/30选择调度方式和调度算法的若干准则面向用户的准则等待时间短等待时间是在就绪队列中等待所花的时间调度算法并不影响进程运行和执行I/O的时间量；只影响进程在就绪队列中等待所花费的时间优先权准则在批处理、实时和分时系统中都可以选择优先权准则，以便让紧急任务先处理有时还选择抢占式调度方式Page422019/12/30选择调度方式和调度算法的若干准则面向系统的准则系统吞吐量高吞吐量指单位时间内系统所完成的作业数作业调度的方式和算法对吞吐量的大小有较大影响处理机利用率高各类资源的平衡利用使内存、外存和I/O设备的利用率高基于这样的准则，你设计操作系统的调度策略应如何？Page432019/12/30（）是指从作业提交给系统到作业完成的时间间隔。A．周转时间B、响应时间C、等待时间D、运行时间作业从进入后备队列到被调度程序选中的时间间隔成为（）。A．周转时间B、响应