单处理器调度.ppt

第9章单处理器调度 处理机调度的调度类型 长程调度 作业调度中程调度 交换调度短程调度 进程调度 短程调度时机 当前阻塞或被剥夺 时钟中断I O中断操作系统调用信号 信号量 两种占用CPU的方式 可剥夺式 当有比正在运行的进程优先级更高的进程就绪时 系统可强行剥夺正在运行进程的CPU 提供给具有更高优先级的进程使用不可剥夺式 某一进程被调度运行后 除非由于它自身的原因不能运行 否则一直运行下去 短程调度准则 面向用户 响应时间 提交一条请求到响应出现在输出的时间间隔面向系统 吞吐量 处理器利用率 调度准则 一般来说 调度目标主要是以下五点 1 公平合理 对所有作业应该是公平合理的 2 高利用率 应使设备有高的利用率 3 吞吐量大 执行尽可能多的作业 进程 4 响应迅速 有快的响应时间 5 周转时间 尽可能短 任一调度算法要想同时满足上述目标是不可能的 1 如要想吞吐量大 调度算法就应选择那些估计执行时间短的作业 这对那些估计执行时间长的作业不公平 并且可能使它们的得不到调度执行或响应时间很长 2 如果考虑的因素过多 调度算法就会变得非常复杂 其结果是系统开销增加 资源利用率下降 衡量调度策略的常用指标 周转时间 指将一个作业提交给计算机系统后到该作业完成所需要的时间 吞吐量 指在给定的时间内 一个计算机系统所完成的总工作量 进程数 响应时间 指从用户向计算机发出一个命令到计算机把相应的执行结果返回给用户所需要的时间 设备利用率 设备的使用情况 周转时间 作业i的周转时间Ti为Tr Tei TsiTei为作业i的完成时间 Tsi为作业的提交时间 N个作业的平均周转时间T T1 T2 TN N带权 归一化 周转时间 周转时间Ti可分解为两部分Tr Twi TriTwi等待时间Tri执行时间周转时间与执行时间的比 Wi Ti TriN个作业的平均带权周转时间W W1 W2 WN N 调度策略 先来先服务 FirstComeFirstServed 短作业优先 ShortestProcessNext 短剩余优先 ShortestRemainingTime 高响应比优先 HighestResponseRatioNext 时间片轮转 RoundRobin 优先级 HighestPriorityFirst 多级队列反馈 MultilevelFeedback 常用作业调度算法1先来先服务 Firstcomefirstserve FCFS 方式 执行时间很短的作业是在那些长作业的后面到达系统的话 则必须等待很长时间2短作业优先 ShortestJobfirst SJF 方式选择那些估计需要执行时间最短的作业投入执行 为它们创建进程和分配资源 有可能使得那些长作业永远得不到调度执行3响应比高者优先 HighestResponse ratioNext HRN 方式 响应比R W T T 1 W TT 为估计需要的执行时间W 在后备状态队列中的等待时间作业调度时 系统计算每个作业的响应比 选择R最大者投入执行 长作业有机会获得调度执行 随着它等待时间的增加 W T也就随着增加 HRN的吞吐量小于SJF 由于长作业也有机会投入运行 在同一时间内处理的作业数显然要少于SJF法 系统开销增加 每次调度前要计算响应比 HRN是对FCFS方式和SJF方式的一种综合平衡 时间片轮转程序调度算法 RR 把CPU划分成若干时间片 并且按顺序赋给就绪队列中的每一个进程 进程轮流占有CPU 当时间片用完时 即使进程未执行完毕 系统也剥夺该进程的CPU 将该进程排在就绪队列末尾 同时系统选择另一个进程运行本算法主要用于进程调度分时系统和事务处理系统中常用时间片轮转法利于CPU限制的进程 不利于I O限制的进程 时间片长度的确定 时间片长度变化的影响过长 退化为FCFS算法 进程在一个时间片内都执行完 过短 用户的一次请求需要多个时间片才能处理完 上下文切换次数增加 响应时间长 时间片长度的影响因素 就绪进程的数目 数目越多 时间片越小 当响应时间一定时 系统的处理能力 应当交互中使用户输入通常在一个时间片内能处理完 优先级 每个进程被赋予一个优先级 每次调度选取就绪队列中优先级最高的进程投入运行 首先系统中设置多个就绪队列 A每个就绪队列分配给不同时间片 优先级高的为第一级队列 时间片最小 随着队列级别的降低 时间片加大优先级越高时间片越小 2i B各个队列按照先进先出调度算法 最后一级时间轮转 一个新进程就绪后进入第一级队列 进程由于等待而放弃CPU后 进入等待队列 一旦等待的事件发生 则回到原来的就绪队列 当有一个优先级更高的进程就绪时 可以抢占CPU 被抢占进程降级就绪队列末尾 当第一级队列空时 就去调度第二级队列 如此类推 多队列反馈调度算法 处罚长进程 例题 在一单道批处理系统中 一组作业的提交时刻和运行时间如表所示试计算以下三种作业调度算法的平均周转时间T和平均带权周转时间W 先来先服务 短作业优先算法 HRN 例2 假设作业在时刻0以1 2 3 4 5的顺序到达 用FCFS RR SJF 非剥夺优先级法 FCFS RR SJF 非剥夺优先级 线性优先级调度策略 新创建的进程按FCFS方式排成就绪队列 而其它已得到过时间片服务的进程也按FCFS方式排成另一个就绪队列或称享受服务队列 对于这两个不同队列中的进程 设新创建进程进入新创建进程就绪队列时的优先级P为0 进入就绪队列后以P a t a 0 的速率增加 享受服务队列中进程的优先级P以P b t a b 0 的速率增长 新创建进程进入享受服务队列条件 当新创建进程就绪队列中的头一个进程的优先级P t a t t1 与享受服务队列中最后一个就绪进程的优先级P t b t相等时当享受服务进程队列为空时 新创建进程队列的头一个进程也将移入享受服务进程队列 设某一进程在时刻t1时被创建 在时刻t时 该进程的优先级为P t a t t1 t1 t t2 又设该进程在t1 时刻转入享受服务队列 则在时刻t 该进程的优先级变为P t a t1 t1 b t t1 t2 t t3 P t b t t1 a t t1 t1t1 t2t2 t 在线性优先级调度法中 a b 0的条件是必要的 否则算法将发生退化情形 当b a 0时 上述线性优先级调度策略退化为FCFS方式 两个不同队列中的就绪态进程的优先级将永远不会相等 从而 在享受服务进程队列中永远只有一个进程 如果a b 0 则线性优先级调度策略退化为轮转法调度方式 线性优先级调度策赂是一种介于轮转法和FCFS方式之间的调度策略 进程调度 FCFS 1 2 3 4