《操作系统课程课件6》由会员分享，可在线阅读，更多相关《操作系统课程课件6（35页珍藏版）》请在金锄头文库上搜索。
1、操作系统概念 CPU调度 2 本章主要内容 基本概念调度准则调度算法多处理器调度实时调度算法评估进程调度模型 3 6 1基本概念 利用多道程序最大化CPU使用率 CPU I O周期 进程执行由CPU执行和I O等待周期组成 CPU区间分布情况 4 CPU区间和I O区间的交替序列 5 CPU区间时间直方图 6 CPU调度程序 调度程序从内存中就绪可执行的进程里选择一个 并为其中之一分配CPU CPU调度决策可以如下四种情况下发生当一个进程从运行状态切换到等待状态当一个进程从运行状态切换到就绪状态当一个进程从等待状态切换到就绪状态当一个进程终止时 当调度只能发生在第一和第四两种情况时 称调度方法
2、是非抢占的 nonpreemptive 否则调度方案就是可抢占 preemptive 的 7 分派程序 Dispatcher 分派程序是一个模块 用来将CPU的控制交给由短期调度程序所选择的进程 其功能包括切换上下文切换到用户模式跳转到用户程序的合适位置以重新启动这个程序分派延迟 dispatchlatency 分派程序停止一个进程而启动另一个进程执行所要花费的时间 8 6 2调度准则 SchedulingCriteria CPU使用率 使CPU尽可能忙吞吐量 Throughput 单位时间完成进程的数量周转时间 Turnaroundtime 从进程提交到进程完成的时间间隔称为周转时间等待时间
3、 Waitingtime 是在就绪队列中等待所花时间之和 响应时间 Responsetime 从提交请求到产生第一响应的时间 9 优化准则 OptimizationCriteria 最大化CPU使用率最大化吞吐量最小化周转时间最小化等待时间最小化响应时间 10 6 3调度算法 先到先服务调度 FirstCome FirstServed FCFS 最短作业优先调度 Shortest Job First SJR 优先权调度 PriorityScheduling 轮转法调度 RoundRobin RR 多级队列调度 multilevelqueue scheduling 多级反馈队列调度 multil
4、evelfeedbackqueuescheduling 11 先来先服务调度 FCFS 假设进程按P1 P2 P3的顺序到达 则该调度的Gantt图如下 等待时间 P1 0 P2 24 P3 27平均等待时间 0 24 27 3 17 12 假设进程按P2 P3 P1的顺序到来 则其调度的Gannt图如下 等待时间 P1 6 P2 0 P3 3平均等待时间 6 0 3 3 3优于前一种情况由于所有其他进程都等待一个大进程释放CPU 就会产生护航效果 convoyeffect 与可能允许较短进程先行相比 这种效果会导致CPU和设备的使用率真变得更低 13 最短作业优先调度 Shortest Jo
5、b First SJR 将每个进程与其下一个CPU区间段相关联 当CPU为可用时 它会赋给具有最短后续CPU区间的进程 如果两个进程具有同样长度的CPU区间 那么可以使用FCFS调度来处理 两种方式非抢占式 一旦进程获得CPU就一直占据CPU 直到其CPU区间完成为止抢占式 如果一个新来的进程其CPU区间小于当前进程的CPU区间 则抢占之 这种调度方式称为最短剩余时间作业优先 ShortestRemainingTimeFirst SRTF SJF是最佳的 对于给定的一组进程 SJF算法的平均等待时间最小 14 非抢占式SJF的实例 15 抢占式SJF的实例 16 确定下一CPU区间的长度 只能
6、估计CPU区间的长度 无法精确计算下一CPU区间的长度通常可预测为以前CPU区间的测量长度的指数平均 17 下一个CPU区间长度的预测 18 指数平均计算的实例 19 优先级调度 PriorityScheduling 每个进程被赋予一个优先级数字 优先权 CPU分配给优先权高的进程 优先级数字越小 则优先权越大 抢占式非抢占式SJF是一种特定的优先权调度方法 其优先权为下一个CPU区间的倒数该算法存在的问题 饥饿 starvation 低优先权的进程可能永远无法执行解决办法 老化 aging 随着时间的推进 进程的优先权逐渐提高 20 轮转法调度 RoundRobin 轮转法是专门为分时系统而
7、设计的 每个进程获得一小片CPU时间量 timequantum 通常为10 100毫秒 时间片结束后 进程被抢占并放入到就绪队列的最后重新参加调度 如果就绪队列中有n个进程 具时间片为q 则每个进程会得到1 n的CPU时间 每个长度不超过q时间单元 每个进程必须等待CPU的时间不会超过 n 1 q个时间单元 直到它的下一个时间片为止 性能低速于时间片的大小如果时间片非常大 无限 那么RR策略与FCFS策略一样 如果时间片很小 那么RR方法称处理器共享 n个进程对于用户来说都有它自己的处理器 速度各为真正处理器速度的1 nq必须大于上下文切换所需时间 21 时间片 20时的RR实例 22 时间片
8、与上下文切换开销 23 周转时间随时间片大小而改变 24 多级队列调度 就绪队列分成几个相对独立的队列前台 或交互式 后台 或批处理 每个队列有自己的调度算法前台 RR后台 FCFS队列之间必须有调度通常采用固定优先权可抢占调度来实现 另一种可能是在队列之间划分时间片 每个队列都有一定的CPU时间 这可用于调度队列内的不同进程20 给后台 80 给前台 25 多级队列调度示意图 26 多级反馈队列调度 进程可以在不同队列间移动通常 多级反馈队列调度程序可由下列参数来定义 队列数量每个队列的调度算法用以确定进程何时升级到较高优先权队列的方法用以确定进程何时降级到较低优先权队列的方法用以确定进程在
9、需要服务时应进入哪个队列的方法 27 多级反馈队列调度的实例 三个队列Q0 时间片为8毫秒Q1 时间片为16毫秒Q2 FCFS调度进入就绪队列的进程被放在队列Q0内 队列0的每个进程都有8ms的时间片 如果一个进程不能在这一时间内完成 那么它就被移到队列1的尾部 如果队列0为空 队列1头部进程会得到一个16ms的时间片 如果它不能完成 那么它将被抢占 并被放到队列2中 只有当队0和队1为空时 队列2内的进程才可根据FCFS来运行 28 多级反馈队列示意图 29 6 4多处理器调度 多处理器调度问题更复杂主要讨论处理器功能相同的系统 负载分配 LoadSharing 非对称多道程序 只有一个处理
10、器访问系统数据结构 减轻了数据共享的需要 30 6 5实时调度 硬实时系统 需要在保证的时间内完成关键任务在提交进程时 同时有一条语句告诉系统用来完成或执行I O所需要的时间 接着 调度程序或者允许进程并保证进程能按时完成 或者因不可能而拒绝请求 资源预约 软实时系统 要保证关键进程拥有比其他进程更高的优先权要求仔细设计调度程序和操作系统有关方面 第一 系统必须有优先权调度 且实时进程必须有最高的优先权 实时进程的优先权不能随时间而下降 尽管非实时进程的优先权可以 实时进程不应该老化第二 分派延迟必须小 内核抢占 31 分派延迟 32 6 6算法评估 确定性建模 采用特定预先确定的负荷 定义在
11、给定负荷下每个算法的性能 简单快速 给出了确切数字 以允许算法被比较但通常过分特殊且要求过多精确知识 故用处有限排队模型 在许多系统上运行的进程每天都在变化 因此没有静态的进程集合和时间用于确定性建模 n为平均队列长度 不包括正在服务的进程 为队列的平均等待时间 为新进程到达队列的平均到达率n W Little公式 可用于比较调度算法 但计算结果的精确性值得怀疑 33 通过模拟来评估CPU调度算法 34 实现 即使模拟其精确度也是有限的 针对评估调度算法 惟一完全精确的方法是对它进行程序编码 将其放在操作系统内 并观测它如何工作 主要困难是这种方法的代价对算法编码 修改操作系统以支持该算法用户对不断变化的操作系统的反应另一困难是算法所使用的环境会变化最为灵活的调度算法可以为系统管理员或用户所改变 35 Linux调度 两种算法 分时与实时分时基于信用度的算法信用度随着定时器中断的发生而降低当所有进程的信用度都为0的时候 则重新计算信用度这种算法似乎混合了两个因素 进程历史和它的优先级实时软实时实现了两种POSIX 1b所要求的实时调度类型 FCFS和RR高优先级的进程总是最先运行
