计算机操作系统（王永茂）第3章处理机调度.pptVIP

第三章 处理机调度与死锁 内容要点 处理机调度算法 产生死锁的原因和必要条件 预防死锁的方法 银行家算法 第三章 处理机调度与死锁 重点 掌握进程调度算法 理解产生死锁的原因 掌握银行家算法避免死锁 难点 银行家算法 第三章 处理机调度与死锁 处理机调度的基本概念 调度算法 实时调度 产生死锁的原因和必要条件 预防死锁的方法 死锁的检测与解除 3.1 处理机调度的基本概念 操作系统调度级别 调度队列模型 选择调度方式和调度算法的若干准则 3.1.1 高级、中级和低级调度 1.高级调度 又称作业调度 主要任务是按一定的原则对外存上处于后备状态的作业进行选择，给选中的作业分配内存、输入/输出设备等必要的资源，并建立相应的进程，插入就绪队列，以使该作业的进程获得竞争处理机的权利 作 业 调 度 作业是用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合，包括用户程序、所需的数据及作业说明书等 作业状态:作业从提交给系统， 直到完成任务后退出系统前， 在整个活动过程中它会处于不同的状态。 通常， 作业状态分为四种： 提交、 后备、 执行和完成， 如图3-1所示。 作 业 调 度 作业状态间转换 （1） 提交状态——即用户向系统提交一个作业时， 该作业所处的状态。 （2） 后备状态——即用户作业经输入设备（如读卡机）送入输入井（磁盘）中存放， 等待进入内存时所处的状况。 （3） 执行状态——即作业分配到所需的资源， 被调入内存， 并且在处理机（CPU）上执行相应的程序时所处的状况。 （4） 完成状态——即作业完成了计算任务， 结果由打印机输出， 最后由系统回收分配给它的全部资源， 准备退出系统时的作业状况。 作 业 调 度 作业控制块（JCB） 在多道批处理系统中通常有上百个作业被收容在输入井（磁盘）中。 为了管理和调度作业， 系统为每个作业设置了一个作业控制块（JCB）， 它记录该作业的有关信息。 JCB的主要内容如图3-2所示。 作业调度的功能 作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转换。 (1) 记录系统中各个作业的情况。 (2) 按照某种调度算法从后备作业队列中挑选作业。 (3) 为选中的作业分配内存和外设等资源。 (4) 为选中的作业建立相应的进程。 (5) 作业结束后进行善后处理工作， 如输出必要的信息， 收回该作业所占用的全部资源， 撤消与该作业相关的全部进程和该作业的JCB。 高级、中级和低级调度 在每次作业调度时，须决定： 接纳多少个作业 即允许多少个作业同时在内存中运行 作业太多 服务质量下降 作业太少 资源利用率低 接纳哪些作业 取决于作业调度算法 先来先服务 短作业优先 作业优先权调度 响应比调度 3.1.1 高级、中级和低级调度 2.中级调度 引入目的是为了提高内存利用率和系统吞吐量。使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待 主要任务是按照给定的原则和策略，将处于外存对换区中的重又具备运行条件的就绪进程调入内存，或将处于内存就绪状态或内存阻塞状态的进程交换到外存对换区 3.1.1 高级、中级和低级调度 3.低级调度 进程调度 主要任务是按照某种策略和方法选取一个处于就绪状态的进程，将处理机分配给它 常见的低级调度有非抢占式和抢占式两种 进程调度方式 非抢占方式(Non-preemptive Mode) 引起进程调度的因素 正在执行的进程执行完毕， 或因发生某事件而不能再继续执行 执行中的进程因提出I/O请求而暂停执行； 在进程通信或同步过程中执行了某种原语操作，如wait、Block、Wakeup原语 进程调度方式 抢占方式 抢占式调度主要有以下原则 优先权原则 允许高优先权的新到进程抢占当前进程的处理机 短作业(进程)优先原则允许执行时间短的新到进程抢占当前进程的处理机 时间片原则 时间片用完后停止执行，重新进行调度，适用于分时系统 3.1处理机调度的基本概念 高级、中级和低级调度 调度队列模型 选择调度方式和调度算法的若干准则 3.1.5 调度队列模型 仅有进程调度的调度队列模型 具有高级和低级调度的调度队列模型 同时具有三级调度的调度队列模型 3.1.5 调度队列模型 仅有进程调度的调度队列模型 在分时系统中，通常仅设有进程调度 系统把这些进程组织成一个就绪队列 每个进程在执行时，可能有以下几种情况 进程获得CPU正在执行 任务在给定时间片内已完成，释放处理机后为完成状态 任务在时间片内未完成，进入就绪队列末尾