第四章 处理机调度.ppt

第四章处理机调度 引言1 在早期的计算机系统中 对CPU的管理十分简单 因那时CPU和其他资源一样 为一个作业独占 不存在处理机分配和调度问题 2 随着多道程序设计技术和各种不同类型的os的出现 各种不同的CPU管理方法得到启用 不同的CPU管理方法为用户提供不同性能的os A 在多道批处理系统中 为了提高处理机效率和作业的吞吐量 当调度一批作业组织多道运行时 要尽可能使作业搭配合理 B 在分时系统中 由于用户使用交互会话的工作方 系统必须要有较快地响应时间 使每个用户均感到如同只有他一个人在使用计算机 因此系统在调度作业时 要考虑每个用户作业得到处理机的均等性 3 衡量调度策略的指标 1 周转时间 只讲一个作业提交给计算机后到作业的结果返回给用户所需的时间 2 吞吐量 率 在给定时间内 一个计算机系统所完成的总工作量 3 响应时间 从用户向计算机发出一条命令开始到计算机把相应结果返回给用户所需的时间 4 设备利用率 指I O的使用情况 4 1分级调度 一 作业状态及其转换 1 多级调度 一个作业从用户提交开始到真正占有处理机而被执行 则要有系统经过多级调度才能实现 2 作业状态 一个作业从提交给计算机系统开始到返回执行结果为止 一般要经历提交 收容 执行 完成四个状态 1 提交状态 一个作业在其处于从输入设备进入外部存储设备的过程 2 收容状态 后备状态 作业内容全部进入外存输入井 但该作业还未被作业调度程序 选中时所处的状态 3 执行状态 作业调度程序从后背作业队列中选择若干个作业投入运行 它为被选中作业建立进程并分配必要资源 这些被选中的作业处于执行态 4 完成态 当作业运行完毕 但它所占有的资源还未全部释放时所处的状态 二 调度的层次 1 作业调度 又称宏观调度 高级调度 其主要任务是按一定的原则对外存输入井中的大量后备作业进行选择 给选出的作业分配内存 输入输出设备等资 并建立相应进程 以使该作业的进程获得竞争CPU的权利 另外 当作业执行完毕 还负责回收系统资源 2 交换调度 也叫中级调度 其主要任务是按照给定的原则和策略 将处于外存交换区中的就绪进程调入内存 或把处于内存就绪状态或内存等待状态的进程交换到外存交换区 3 进程调度 又叫微观调度或低级调度 其主要任务是按照某种策略和方法选取一个处于就绪状态的进程占用处理机 在确定了占用处理机的进程后 系统必须进行进程上下文的切换以建立与占用处理机进程相应的执行环境 4 线程调度 其主要任务是选择一个适当的线程到处理机上去执行并进行描述标的切换 1 线程的调度状态 六个状态a 就绪状态 已具备执行条件以等待CPU执行 线程调度程序只从线程就绪池中选择线程进入备用状态 b 备用状态 系统中每个处理机只能有一个线程处于备用状态 处于备用状态的线程被选定为某一特定处理机的下一个执行对象 当条件合适时 调度程序为该线程进行描述表切换 c 运行状态 一旦调度程序对线程执行完描述表切换 线程便进入运行状态 d 等待状态 以下情况便可使线程进入等待状态 线程等待一对象 同步他的执行 因等待I O设备 环境子系统导致线程自己挂起 当线程等待结束 就回到就绪状态 e 转化状态 如果线程已准备好执行 但由于资源为不可用 从而成为转化状态 当资源为可用时 线程便由转化状态进入就绪状态 f 终止状态 线程完成了他的执行 2 引起线程调度的时机 a 当线程进入就绪状态时 b 当线程的时间片用完或线程终止时 c 当调度程序或执行体改变线程优先级时 d 当执行体或应用程序改变正在运行的处理机族时 3 线程描述表 是用于描述现行线程的现场 包括 程序计数器 处理机状态寄存器 其他寄存器内容 用户栈和核心栈指针 线程运行的地址空间的指针 三 作业与进程的关系1 作业可被看作用户向计算机提交任务的任务实体 而进程则是计算机为了完成用户任务实体而摄制的执行实体 是系统分配资源的基本单位 2 一个作业由一个或多个进程组成 第一步 系统为一个作业创建一个根进程 第二步 在执行作业控制语句时 根据任务要求 系统或根进程为其建立相应的子进程 第三步 系统为子进程分配资源和调度各子进程完成作业要求的任务 4 2作业调度 一 作业调度的功能 1 记录系统中各作业的状态 系统为每个作业建立一个作业控制块 JCB 来对作业进行控制管理并记录作业在运行过程中的状态 1 JCB的建立 作业进入后备状态时为该作业建立相应的JCB 从而使该作业能被系统感知 2 JCB的撤销 当作业执行完毕进入完成状态后 系统撤销其JCB而释放有关资源并撤销该作业 3 JCB内容 作业名 作业类型 资源要求 资源使用情况等 2 从后备作业队列中选出一部分作业投入运行 3 为被调度选中的作业做好执行前的准备工作 4 在作业执行结束时作善后处理工作 主要是输出作业管理信息 例如执行时间 回收该作业所占用的资源 撤销与该作业有关的进程和JCB P85图4 3二 作业调度目标与性能衡量 1 调度目标 1 对所有作业应是公平的 2 应使设备有高的利用率 3 每天执行尽可能多的任务 4 有快的相应时间 2 调度算法优劣的衡量 批处理系统 用作业的平均周转时间或平均带权周转时间衡量 分时系统 实时系统 用作业周转时间或平均带权周转时间及平均相应时间衡量 1 周转时间 指作业从提交时刻开始到完成时刻为止所经历时间 即 Ti Tei Tsi平均周转时间 T T1 Tn n 2 带权周转时间 指作业周转时间和作业执行时间的比值 即Wi Ti Tri 平均带权周转时间 W W1 Wn n 4 3进程调度 在计算机系统运行过程中 进程数一般多于处理机数目 从而导致进程对处理机的竞争 进程调度即按一定策略 动态地把处理机分配给处于就绪状态的进程 使之能被执行 一 进程调度的功能 指操作系统中的进程调度程序按照某种调度算法 从就绪进程队列中选择一个进程将他移出就绪队列并置为运行态 同时启动CPU立即执行该进程 具体描述为 1 记录系统中所有进程的执行情况 a 进程管理模块将系统中各进程状态和状态特征记录在PCB中 b 根据进程的状态特征和资源需求 将系统中所有进程PCB组织成多个队列 2 选择占有处理机的进程 根据不同的系统设计目标 有各种各样的选择策略 如 静态优先数调度法 轮转法等 3 进行进程上下文切换 a 进程上下文 包括进程的状态 有关变量 数据结构的值 硬件寄存器的值及PCB和有关程序 b 一个进程的执行实质上是在其上下文中执行 c 当出现进程调度时系统要做上下文的切换 二 进程调度的时机1 引起进程调度的原因a 正在执行的进程执行完毕 b 进行中的进程自己调用阻塞原语将自己阻塞起来 进入睡眠等待状态 c 执行中进程调用了P原语操作 从而因资源不足而被阻塞 或调用了V原语激活了等待资源的进程队列 d 执行中进程提出了I O请求后被阻塞 e 在分时系统中时间片已经用完 f 在执行完系统调用后 在系统程序返回用户程序时 可认为系统进程执行完毕 从而调度选择一新的进程执行 g 就绪队列中进程的优先级变得高于当前执行进程的优先级 从而引起进程调度 2 处理机调度的时机 当系统出现提上七种情况之一时 即发生处理机调度 3 处理机调度的方式 1 可剥夺式 即就绪队列中一旦有优先级高于当前进程的优先级时 便立即发生进程调度 转让处理机 2 非剥夺方式 即使在就绪进程队列存在优先级高于当前当前正在执行的进程的优先级时 当前进程仍将继续占用处理机 直到该进程因自己调用某原语或等待I O而进入阻塞状态 或时间片用完时才发生调度出让处理机 三 进程上下文切换 P88 1 进程上下文的内容 2 进程上下文切换的步骤 1 决定是否做上下文切换及其是否允许做上下文切换 2 保存当前执行进程的上下文 3 选择一个就绪状态进程 4 恢复或装配所选进程上下文 将CPU控制权交给所选进程 四 进程调度性能评价 1 定性评价 进程调度性能的衡量可分为定性和定量两种 在定性衡量方面 首先考虑调度的可能性包括一次进程调度是否引起数据结构的破坏 这要求对调度时机的选择和保存CPU现场十分谨慎 其次 简洁性也是衡量进程调度的一个重要指标 由于调度程序的执行涉及到多个进程和必须进行上下文的切换 如果调度过于频繁 将会耗去较大的系统开销 2 定量评价 包括CPU利用率 进城在就绪队列中的等待时间与执行时间之比 作业调度与进程调度程序的区别与联系 作业调度程序在挑选作业进入主存运行时 要为该作业建立相应的进程 在作业完成后要撤销该作业的全部进程 一个进程被建立后 系统为了便于对进程的管理 将系统中的所有进程按其状态将其组织成不同的进程队列 进程调度程序 负责进程调度功能的内核程序 作业调度与进程调度程序的区别 前者是挑选作业进主存运行 后者是挑选就绪进程到处理机上运行 进程调度的核心问题就是 采用什么算法把处理机分配给进程 4 4调度算法 1 先来先服务调度算法 FCFS 1 方法思想 按照进程进入就绪队列的先后次序选择进程投入运行 该法也可以用于作业调度 2 特点 优点 实现简单 公平 缺点 a 计算机效率可能不高 如系统中的进程偏向于需求某一类资源 导致有的资源高度繁忙 有的资源可能长期不用 b 对短进程可能不利 不能很好地满足用户的需求 3 例 设P1 P2 P3为三个进程 他们的本次CPU周期时值分别是21ms 6ms 3ms 且以P1 P2 P3的次序进入就绪队列中 则在 i 不剥夺方式下执行序列为 P1 P2 P3 且平均周转时间T 21 27 30 3 26ms平均等待时间W 0 21 27 3 16ms平均带权周转时间T1 21 21 27 6 30 3 ii 在分时系统中 若时间片为6ms 分析这三个进程的执行情况 2 最短者优先 SJF SPF 1 思想 以进程的本次CPU时间长短作为调度的依据来选择进程投入运行 2 例 设P1 P2 P3为三个进程 他们的本次CPU周期时值分别是21ms 6ms 3ms 分析他们的执行情况及有关指标的计算 3 性能分析 a 采用最短进程优先调度算法 可以降低平均周转时间 平均带权周转时间 平均等待时间 b 该算法实现简单 缺点 一般情况具有公平性 但是当系统中长进程 较少而短进程较多时 对长进程失去公平性 3 最高相应比者优先 HRN highestreponserationnext 1 当需要从就绪队列中选择进程投入运行时 先计算各进程的相应比 选择相应比最高的进程运行 2 例 设有四个作业 J1 J2 J3 J4 他们的进入时间分别为8 00 8 50 9 00 9 50 运行时间分别为 00 0 50 0 10 0 20 分析执行情况 略 3 性能 a 该算法较复杂 系统开销大 b 性能评价参数有升高趋势 c 克服了FCFS SPF各自的缺点 4 轮转法 RR roundrobin 1 思想 系统将所有就绪进程按先进先出原则组织成队列 调度程序每次选择队首进程投入运行 并按规定的时间片S值设置时钟 以便S到限时产生中断 若现行进程的CPU周期时值小于S值 则当该进程完成时就进入重新调度 S的剩余量交还给系统 如果当前CPU周期时值大于或等于S值 则当时间片中断发生时便进入剥夺态 将现行进程送至就绪队列尾部 而当前CPU周期剩余量放到下一轮再执行 同时选择队首进程投入运行 2 例 针对前面提到的P1 P2 P3三个进程 利用轮转法 分析他们的执行情况 略 3 关于时间片 a 长短适中 如太长 则使每一个进程均能在一个时间片内完成 RR算法褪化成了FCFS 若太短 导致频繁的时间片中断和调度 CPU额外开销大 b 时间片S可以采用基本时间片法和变长时间片法 c S的选取公式 S RT N其中RT为系统响应时间上限 N为系统中进程数目上限 4 性能 a 具有公平性 b 易于实现 算法简单 c CPU存在较大的额外开销 用于进程切换和调度 5 最高优先级法 HPF highestpriorityfirst 1 思想 在进行进程调度时 选择优先级最高者头投入运行 而忽略等待时间 运行时间等因素 a 优先级的表示方法 用一个整数表示 该数称为优先数 有的系统规定优先数越小 优先级越高 b 优先级的设置方法 静态优先级法 由系统在建立进程时确定一个优先数 它在整个生命期内保持不变 进程的优先数可以根据其类型 功能 资源需求等确定 动态优先数 在创建一个进程时 根据该进程的基本特性设置一个初始优先数 而后在进程运行 过程中 随着时间推移和运行环境的变化而动态地改变优先级 P Po at 2 例 设有5个进程P1 P2 P3 P4 P5它们各自的本次CPU时值 初始化优先级及进入就绪队列相对时刻如下 进程CPU时值优先数进入时刻P13250P2430P3850P4260P516416 1 分析在静态优先级调度算法下的有关指标 平均等待时间 平均周转时间 平均带权周转时间 2 在剥夺式的动态优先级方法中 设现行进程每 连续运行10毫秒以上后 优先数加1 而就绪进程每40毫秒后进程优先数减1 分析执行情况 3 性能 a 静态优先级法简单 但缺点是公平性差 可能会造成优先级低的长期等待 b 动态优先级法资源利用率高 公平性好 缺点是系统开销较大 实现复杂 6 多级反馈队列 1 思想 a 系统按优先级别设置若干n个就绪进程队列 第一级队列的优先级最高 以下逐级降低 第n级队列的优先级最低 b 每个就绪队列对应一个时间片Si i 1 2 n 且有S1 S2 Sn 一般有Si 1 2Sic 除对第n级队列按RR调度外 对其余各级均按 FCFS调度 d 当现行进程正在运行它的CPU周期时 如果有时间片中断或有进程进入更高级的就绪队列时将引起剥夺 对前一种情况 先行进程将进入下一级队列 对后一种情况 先行进程进入本级队列尾部 当一进程被唤醒时 它进入原来离开时的队列 2 特点 a 复杂 实现困难 b 是FCFS RR HPF的综合应用 选择调度算法时应考虑的问题 进程调度的算法较多 在设计进程调度算法时应考虑的因素多 比如 尽量提高资源利用率 减少处理机的空闲时间 对于用户作业要较合理的平均响应时间 以及尽可能地增强CPU的处理能力 补充 调度的实现 进程调度室内核原语 当发生了引起调度的某种事件时 由有关的内核程序转入 采用HPF算法的进程调度程序大致描述如下 procedurescheduler beginifRQ nilthenstart idler outqueue RQ I HPF ifEXENILthen beginifI priority EXE prioritythenbeginsave EXE EXE start ready EXE queue RQ insert RQ EXE end elsebegininsert RQ i returnend end start i end 4 6实时调度算法 一 实时系统的特点及功能 一 特点1 有限等待时间 确定性 与分时系统的多个进程的并发执行特性相比 分时系统中并发执行的进程具有不确定性 其执行顺序与执行环境有关 而实时系统则不然 他要求所有进程在处理事件时 都必须在有限时间内开始处理 2 有限响应时间 指从系统响应外部事件开始 必须在有限时间内处理完毕 3 用户控制 指用户可以控制进程的优先级并选择相应的调度算法 从而达到对进程执行先后顺序的控制 4 可靠性 要求很高5 系统出错处理能力 要求系统在出错时 既能处理发生的错误 又不影响当前正在执行的用户进程 二 实时系统的功能 1 很快的进程或线程切换速度与分时系统不同 公平性和最小平均响应时间指标在实时系统中并不重要 实时系统中调度算法的设计原则是满足所有硬实施任务的处理时限和尽可能多地满足软实时任务的处理时限 2 快速的外部中断响应能力3 基于优先级的随机抢先式调度策略 有四种 1 优先级 时间片轮转调度策略 2 基于优先级的非抢占式调度策略 3 基于优先级的固定点抢先式调度策略 4 基于优先级的随时抢先式调度策