处理机调度 (2)ppt课件.ppt

4 1分级调度4 2作业调度4 3进程调度4 4调度算法4 5算法评价4 6实时系统调度方法 CPU是计算机系统中一个十分重要的资源不同的CPU管理方法将为用户提供不同性能的操作系统操作系统的要求不同 处理机管理的策略也是不同的本章以CPU管理为核心 讨论管理 控制用户进程执行的方法 包括 作业与进程的关系 作业和进程的调度策略与算法 几种调度策略的评价 概述 衡量调度策略的常用指标 周转时间 将一个作业提交给计算机系统后到该作业的结果返回给用户所需要的时间吞吐率 在给定的时间内 一个计算机系统所完成的总工作量响应时间 从用户向计算机发出一个命令到计算机把相应的执行结果返回给用户所需的时间设备利用率 输入输出设备的使用情况 4 1分级调度 4 1 1作业的状态及其转换4 1 2调度的层次4 1 3作业与进程的关系 4 1 1作业的状态及其转换 作业的基本概念 1 作业用户在一次计算过程中 或者一次事务处理过程中 要求计算机系统所做工作的总称 2 作业步一个作业可划分成若干部分 称为一个作业步 4 1 1作业的状态及其转换 一个作业从用户提交开始到真正占有处理机而被执行 要由系统经过多级调度才能实现 作业处理的过程一般都要经历提交 收容 执行和完成等4个状态 提交 一个作业在其处于从设备进入外部存储设备的过程称为提交状态收容 也称为后备状态 一个作业的全部信息都被输入进外存 在它还未被调度去执行之前 该作业处于收容状态 执行 作业调度程序从后备作业中选取若干个作业到内存投入运行 它为被选中作业建立进程并分配必要的资源 这时这些被选中的作业处于执行状态 完成 当作业运行完毕 但它所占有的资源尚未全部被系统回收时 该作业处于完成状态 4 1 1作业的状态及其转换 图4 1作业的状态及其转换图 作业和进程的状态转换图 4 1 2调度的层次 处理机调度策略 处理机的分配 对整个计算机系统的综合性能指标有重要影响处理机调度的描述先要进行作业调度 选择后备作业为其分配资源创建进程 作业中的进程再进行竞争 4 1 2调度的层次 一般处理机调度分为四级 作业调度交换调度进程调度线程调度 作业调度 宏观调度或高级调度 按一定的原则对外存上的大量后备作业进行选择 给选出的作业分配内存等必要的资源 并建立相应的进程 另外当作业执行完毕时 还负责回收系统资源 4 1 2调度的层次 交换调度 中级调度 按给定的原则和策略 将处于外存交换区中的就绪状态或就绪等待状态的进程调入内存 或把处于内容就绪状态或内存等待状态的进程交换到外存主要涉及到内存管理与扩充 也归入内存管理部分 4 1 2调度的层次 进程调度 微观调度或低级调度 按某种策略和方法选取一个处于就绪状态的进程占用处理机 4 1 2调度的层次 线程调度按某种策略和方法选取一个处于就绪状态的线程占用处理机 4 1 2调度的层次 在多道批处理系统中存在作业调度和进程调度在分时系统和实时系统中 一般不存在作业调度而只有进程调度 交换调度和线程调度 4 1 2调度的层次 4 1 3作业与进程的关系 作业看作是用户向计算机提交任务的任务实体 如一次计算机一个控制过程等进程是计算机为了完成用户任务实体而设置的执行实体 是系统分配资源的基本单位计算机要完成一个任务实体 必须要有一个以上的执行实体 一个作业总是由一个以上的多个进程组成 作业如何分解为进程 系统必须为一个作业创建一个根进程 根据任务要求 系统或根进程为其创建相应的子进程 为各子进程分配资源和调度各子进程执行以完成作业要求的任务 4 1 3作业与进程的关系 4 2作业调度 4 2 1作业调度功能4 2 2作业调度目标与性能衡量 4 2 1作业调度功能 作业调度主要是完成作业从后备到执行状态的转变 以及从执行到完成状态的转变 做四方面的工作 1 记录系统中各作业的状况 2 从后备队列中挑选出一部分作业投入执行 3 为被选中作业作好执行前的准备工作 4 在作业执行结束时做善后处理 1 记录系统中各作业的状况作业调度程序要能挑出一个作业投入执行 并且在执行过程中对其进行管理 它就必须掌握作业的各个状态和信息 系统为每个作业建立一个作业控制块JCB记录有关信息 系统通过JCB而感知 调度和管理作业 4 2 1作业调度功能 1 作业说明书 表达用户对作业的控制意图内容 作业的基本描述作业控制描述资源要求描述 4 2 1作业调度功能 2 作业控制块 JCB 作业控制块是批处理作业存在的标志保存有系统对于作业进行管理所需要的全部信息 4 2 1作业调度功能 图4 2作业控制块JCB 3 作业控制块的建立当作业开始由输入设备向磁盘传输时 系统输入程序为其建立一个作业控制块 并进行初始化初始化的大部分信息取自作业说明书 4 2 1作业调度功能 4 作业控制块的撤消作业完成后 其作业控制块由系统撤消作业控制块被撤消后其作业也不复存在 4 2 1作业调度功能 从后备队列中挑选出一部分作业投入执行系统中处于后备状态的作业较多 但是处于执行状态的作业一般只有有限的几个 作业调度程序根据选定的调度算法 从后备作业队列中挑选出若干作业去投入执行 4 2 1作业调度功能 为被选中作业作好执行前的准备工作为选中的作业建立相应的进程 并为这些进程分配它们所需要的系统资源 如分配内存 外存 外设等 4 2 1作业调度功能 在作业执行结束时做善后处理输出作业管理信息 如输出执行时间等 回收该作业所占用的资源 撤销与该作业有关的全部进行和该作业的JCB 4 2 1作业调度功能 4 2 2作业调度目标与性能衡量 作业调度中最主要的是从后备作业队列中选取一批作业进行执行状态 根据不同的目标 将会有不同的调度算法 作业调度的目标 对所有作业应该是公平合理的应使设备有较高的利用率执行尽可能多的作业响应时间快 4 2 2作业调度目标与性能衡量 任一调度算法要想同时满足上述目标是不可能的例如要想执行尽可能多的作业 调度算法就应该选择那些估计执行时间短的作业 但这样作的话对那些估计执行时间长的作业又是不公平的 它们的响应就会变的非常慢 4 2 2作业调度目标与性能衡量 如果考虑的因素过多 调度算法就会变的非常复杂 这样系统开销就会增加 因此大多OS都有各自的目标实现作业调度算法衡量一个作业调度算法优劣的标准 批处理系统 作业的平均周转时间或平均带权周转时间 4 2 2作业调度目标与性能衡量 1 周转时间Ti 作业i的周转时间Ti Ti Tei TsiTei为作业i的完成时间 Tsi为作业的提交时间含有n个作业的作业流 平均周转时间为T 4 2 2作业调度目标与性能衡量 一个作业的周转时间说明了该作业在系统内停留的时间 包含两部分 等待时间和执行时间 Ti Twi Tri等待时间Twi 由后备状态到执行状态的等待时间 4 2 2作业调度目标与性能衡量 2 带权周转时间Wi 是作业周转时间与作业执行时间的比Wi 平均带权周转时间 4 2 2作业调度目标与性能衡量 4 3进程调度 4 3 1进程调度功能4 3 2进程调度的时机4 3 3进程上下文切换4 3 4进程调度性能评价 用户进程和系统进程都要使用处理机 因此进程调度程序应该按照一定的策略动态地把处理机分配给处于就绪队列中的某一个进程 使之执行 4 3进程调度 4 3 1进程调度功能 进程调度的具体功能如下 记录系统中所有进程的执行情况选择占有处理机的进程进行进程上下文切换 4 3 1进程调度功能 1 记录系统中所有进程的执行情况进程管理模块的准备工作 进程调度模块通过PCB变化来掌握系统中所有进程的执行情况和状态特征 并在适当的时机从就绪队列中选择出一个进程占据处理机 2 选择占有处理机的进程按照一定的策略选择一个处于就绪状态的进程 使其获得处理机执行 例如系统开销较少的静态优先数调度法 适合于分时系统的轮转法和多级反馈轮转法等 这些选择策略决定了调度算法的性能 4 3 1进程调度功能 3 进行进程上下文切换当正在执行的进程由于某种原因要让出处理机时 系统要做进程上下文切换 以使得另一个进程得以执行 4 3 1进程调度功能 4 3 2进程调度的时机 正在执行的进程执行完毕执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等待状态执行中进程调用了P原语操作 因为资源不足而被阻塞 或用V原语激活了等待资源的进程队列 进程调度发生的时机与引起进程调度的原因以及进程调度的方式有关 引起进程调度的原因有以下几类 4 执行中进程提出了I O请求后被阻塞5 在分时系统中时间片已经用完6 在执行完系统调用 返回用户进程时对于CPU执行方式可剥夺 7 就绪队列中的某进程的优先级高于当前执行进程的优先级 4 3 2进程调度的时机 4 3 3进程上下文切换 进程上下文切换包括4个步骤 1 决定是否做上下文切换以及是否允许作上下文切换包括对进程调度原因的检查分析 以及当前执行进程的资格和CPU执行方式的检查等 进程上下文切换步骤2 2 保存当前执行进程的上下文要求 上下文切换程序不能破坏 老 进程的上下文结构 4 3 3进程上下文切换 进程上下文切换步骤3 3 使用进程调度算法 选择一个处于就绪状态的进程占用处理机 4 3 3进程上下文切换 进程上下文切换步骤4 4 恢复或装配所选进程的上下文 将CPU控制权交给所选进程 4 3 3进程上下文切换 4 3 4进程调度性能评价 进程调度的优劣直接影响作业调度的性能 进程调度性能的衡量方法分为定形和定量两种 定形 调度的可靠性 如进程调度是否引起数据结构的破坏简洁性 如果调度程序过于烦琐和复杂 将会耗去较大的系统开销 并会使得响应时间增加 4 3 4进程调度性能评价 定量 CPU的利用率评价进程在就绪队列中的等待时间与执行时间之比对于实际系统实现困难 一般采用模拟或测试系统响应时间的方法来评价进程调度的性能 4 3 4进程调度性能评价 在操作系统中要设计一个理想的调度算法是十分困难的 设计调度算法时应考虑的因素 调度算法应与系统设计目标保持一致注意系统资源均衡使用保证提交的作业在截止时间内完成设法缩短作业平均周转时间大多数操作系统都采用比较简单的调度算法 4 4调度算法 4 4调度算法 显然 不同的的系统和系统目标 通常采用不同的调度算法 目前存在着多种调度算法 有的适用于作业调度 有的适用于进程调度 也有的算法二者都适用 1 先来先服务 FCFS 调度算法是一种最简单的调度算法作业调度 每次调度是从后备作业队列中选择一个最先进入该队列的作业进程调度 从就绪进程队列中选择一个最先进入该队列的进程 4 4调度算法 FCFS调度算法分析实现简单 有利于执行时间长的作业 进程 不利用短作业 进程 在执行时间长的作业 进程之后到达 将等待很长的时间 带权周转时间大 在实际的OS中 很少单独适用FCFS 一般和其他算法配合起来使用 4 4调度算法 2 轮转法 RR RoundRobin 算法思想 轮转法的基本概念是将CPU的处理时间分成固定大小的时间片 如果一个进程在被调度选中之后用完了系统规定的时间片 但未完成要求的任务 则它自行释放自己所占有的CPU而排到就绪队列的末尾 等待下一次调度 同时 进程调度程序又去调度当前就绪队列中的第一个进程 4 4调度算法 4 4调度算法 2 轮转法 轮转法中时间片大小的关键性 影响到系统的开销和响应时间过短则剥夺处理机的次数增多 切换次数增加 加重系统开销过长 长到都能在时间片内执行完成 则退化为FCFS算法 2 轮转法 时间片大小的确定应该考虑以下因素1 系统对响应时间的要求2 就绪队列中的进程数目它可表示为 q R Nmax实际可行的办法 当一轮调度开始时 系统根据就绪队列中的数目计算一次q 2 轮转法 3 多级反馈轮转法 RoundRobinwithMultipleFeedback 算法思想 由于在轮转法中加入就绪队列的进程情况不同 因此如果对这些进程区别对待可以进一步改善系统效率 方法如下 1 设置多个就绪队列 为各个队列赋予不同的优先权 第一队列最高 逐个降低2 赋予各个队列中时间片的大小也不同 优先权越高 时间片越小 4 4调度算法 3 一个新进程进入内存后 先放入第一队列的末尾 按FCFS排队等待 当执行时如果能在该时间片内完成 便撤离系统 如未完成 将其放入第二队列末尾 再等待 如果在第二队列中运行一个时间片仍未完成则放入第三队列 依此类推 到n 3 多级反馈轮转法 4 仅当第一队列空闲时 才调度第二队列 如果第i队列中为某进程正占用处理机 又有新进程进入优先级较高的队列 则此时新进程将抢占处理机 3 多级反馈轮转法 3 多级反馈轮转法 算法评价 具有较好的性能 较好的满足各种类型用户的需要 是一种目前公认的较好的进程调度算法 3 多级反馈轮转法 4 优先级法系统将从就绪队列中选择一个优先级最高的作业 进程分配处理机 1 非抢占式优先级算法2 抢占式优先级算法 4 4调度算法 1 非抢占式优先级算法优先级高的进程在得到处理机后一直执行下去 直至完成或自己放弃处理机时 系统才可将处理机分为给另一个优先级高的进程 主要用于批处理和某些实时性要求不高的系统中 4 优先级法 2 抢占式优先级算法优先权高的进程在得到处理机后执行 一旦出现了一个优先级更高的进程时 系统就停止当前进程的执行 将处理机分配给优先级更高的进程能更好的满足紧迫作业的要求 用于实时性要求高的系统中 4 优先级法 进程或作业优先级的确定方法 1 静态法 在作业或进程开始执行前就确定其优先级 在其运行期间保持不变2 动态法 随着作业或进程的执行过程 其优先级不断变化 以获得更好的调度性能优先级是用一定范围内的整数来表示 0 7 0 255等 但各个系统的用法不同 4 优先级法 1 静态法确定进程或作业的优先级的依据 进程或作业类型进程或作业对资源的需求用户的要求简单易行 系统开销小 但不够精确 4 优先级法 2 动态法确定进程或作业的优先级的依据 进程或作业占有CPU时间的长短 占有处理机时间越长 再次获得调度的优先级就越低 进程或作业等待CPU的时间长短 等待时间越长 优先级越高 系统开销大 4 优先级法 4 优先级法 举例 线性优先级调度策略 ssr 5 最短作业优先法 ShortestJobFirst 算法思想 选择那些估计需要执行时间最短的作业占用处理机 算法分析 使得系统在同一时间内处理的作业个数最多 吞吐量大 但是有可能使得那些长作业永远得不到处理机执行的机会 4 4调度算法 6 最高响应比优先法 HRN HRN是对FCFS和SJF方式的一种综合平衡由于 FCFS只考虑等待时间未考虑执行时间的长短SJF只考虑执行时间未考虑等待时间HRN同时考虑二者 从中选出响应比最高的作业投入执行 4 4调度算法 6 最高响应比优先法 HRN 响应比R W T T 1 W T其中T为该作业估计需要的执行时间 W为作业在后备状态队列中的等待时间 长作业随着它等待时间的增加 W T也会增加 有机会获得CPU处理时间 4 4调度算法 本节主要利用解析技术从数学上分析几种主要调度方法的性能 详细过程请参考课本93页 98页 4 5算法评价 假设在单道批处理环境下有四个作业 已知它们进入系统的时间 估计运行时间应用先来先服务 最短作业优先和最高响应比优先作业调度算法 分别计算出作业的平均周转时间和带权的平均周转时间 4 5算法评价 先来先服务调度算法计算结果 最短作业优先作业算法计算结果 最高响应比优先作业算法计算结果 4 6实时系统调度方法 4 6 1实时系统的特点4 6 2实时调度算法的分类4 3 3时限调度算法与频率单调调度算法 4 6 1实时系统的特点 根据对处理外部事件的时限 deadlines 要求 实时系统的外部事件可分为硬实时任务hardrealtimetask要求系统必须满足任务的时限要求软实时任务soferealtimetask允许系统对任务的时限要求有一定的延迟 随着移动通信和网络计算技术的发展 实时系统越来越重要 具有以下特点有限等待时间有限响应时间用户控制可靠性高系统出错处理能力强 4 6 1实时系统的特点 实时系统的特点要求实时操作系统具有以下能力 1 很快的进程或线程切换速度根据算法选择某一个进程执行后 最重要的就是进程切换 切换速度快节省执行时间 4 6 1实时系统的特点 实时操作系统的能力 2 快速的外部中断响应能力只有对外部中断信号反应迅速 系统才能对外部事件作出迅速反应 4 6 1实时系统的特点 实时操作系统的能力 3 基于优先级的随时抢先式调度策略实时系统的目的是保证反应快因此对用户的高优先级作业或进程要保证及时响应 4 6 1实时系统的特点 实时调度算法分为4类 静态表格驱动类静态优先级驱动抢先式调度算法类动态计划调度算法类尽力而为调度算法类 4 6 2实时调度算法的分类 4 6 2实时调度算法的分类 1 静态表格驱动类对可能的调度条件和参数进行静态分析 并将分析结果作为实际调度结果多用于调度处理周期性任务 参数为周期 执行时间 周期性结束时间 任务优先级典型 最早时限优先法 优先调度时限最早的任务 2 静态优先级驱动抢先式调度算法类也是静态分析 但是分析结果不直接产生调度结果 而只用来指定任务的优先级举例 频率单调调度算法 4 6 2实时调度算法的分类 3 动态计划调度算法类在调度任务执行之前排出调度计划 并分析调度结果是否使得任务所要求的处理时限得到满足 如果可以 则按照调度计划执行 否则修改计划 4 6 2实时调度算法的分类 4 尽力而为调度算法类不进行可能性分析 只对到达的事件和相关任务指定相应的优先级 并进行调度 4 6 2实时调度算