操作系统原理：Chap 5CPU调度.ppt
51页
Chap 5 CPU调度调度 6.2内容内容1.基本概念2.调度准则3.调度算法4.多处理器调度和线程调度5.调度实例 1、基本概念、基本概念 6.4CPU脉冲周期脉冲周期nCPU调度（进程调度或线程调度）是多任务操作系统的基础n通过多道程序设计得到CPU的最高利用率n 进程的执行包括进程在CPU上执行和等待I/OlCPU脉冲周期lI/O脉冲周期 6.5CPU脉冲周期统计脉冲周期统计 6.6CPU调度程序调度程序n选择内存中的就绪进程，并分配CPU给其中之一n调度方案：l非抢占式调度非抢占式调度(nonpreemptive)n一旦把处理机分配给某进程后，系统不允许其他进程抢占已分配给它的CPU直至该进程完成，自愿释放CPU，或发生某事件而被阻塞，才再把CPU分配给其他进程l抢占式调度抢占式调度(preemptive )4允许调度程序根据某种原则去暂停某个正在执行的进程，将已分配给她的CPU重新分配给另一进程 6.7CPU调度时机调度时机nCPU调度可能发生在当一个进程:1. 从运行转到等待2. 从运行转到就绪3. 从等待转到就绪4. 终止运行n非抢占式调度：非抢占式调度：1、4n抢占式调度：抢占式调度：2、3 6.8分派程序分派程序(Dispatcher)n分派程序负责把CPU的控制权转交CPU调度程序，包括:l切换上下文l切换到用户态l跳转到用户程序的适当位置并重新运行之n分派延迟(Dispatch latency ) –分派程序终止一个进程的运行并启动另一个进程运行所花的时间 2、调度准则、调度准则 6.10概念概念nCPU利用率 – 固定时间内CPU运行事件的比例n吞吐量 – 单位时间内运行完的进程数n周转时间 – 进程从提交到运行结束的全部时间n带权周转时间—周转时间/运行时间n等待时间 – 进程等待调度（不在运行）的时间片总和 n响应时间 – 从进程提出请求到 首次被响应[而不是输出结果]的时间段[在分时系统环境下] 0 1 2 3 4 5 6 7 8 9 10运行时间：1+2+3=6周转时间：10-0=10 不运行 运行等待时间：1+1+2=4 或 10-6=4响应时间：1 <=等待时间 6.11优化准则优化准则n最大的CPU利用率n最大的吞吐量n最短的周转时间n最短的等待时间n最短的响应时间n解决方法l调度算法：决定就绪队列中哪个进程被选中运行 3、调度算法、调度算法 6.13First-Come First-Served (FCFS)First-Come First-Served (FCFS)先来先服务调度算法先来先服务调度算法先来先服务调度算法先来先服务调度算法n调度依据：进入就绪队列的时间n调度方法：先进入就绪队列的进程被优先选中运行n使用FIFO队列实现n举例:进程区间时间P124P2 3 P33 n假定进程到达顺序如下: P1 , P2 , P3 该调度的Gantt图为:n等待时间： P1 = 0; P2 = 24; P3 = 27n平均等待时间: (0 + 24 + 27)/3 = 17P1P2P32427300 6.14先来先服务调度算法先来先服务调度算法n假定进程到达顺序如下 P2 , P3 , P1 .n该调度的Gantt图为 :n等待时间: P1 = 6; P2 = 0; P3 = 3n平均等待时间 : (6 + 0 + 3)/3 = 3n比前例好得多n护航效果convoy effect：长进程先于短进程到达n有利于长进程，而不利于短进程P1P3P263300 6.15讨论讨论1.FCFS是抢占式调度还是非抢占式调度？2.FCFS堆怎样的操作系统不利？可以用于什么操作系统？ 6.16Shortest-Job-First (SJF) 短作业优先调度算法短作业优先调度算法n从FCFS存在的问题得到启发n调度依据：每个进程下次运行的CPU脉冲长度n调度方法：调度最短的进程运行n两种模式: l非抢占式调度：一旦进程拥有CPU，它可在该CPU 脉冲结束后让出CPUl抢占式调度 ：有比当前进程剩余时间更短的进程到达时，抢占当前运行进程的CPU，也称为最短剩余时间优先调度Shortest-Remaining-Time-First (SRTF)Shortest-Remaining-Time-First (SRTF)nSJF最优 –给出了最短的平均等待时间n饥饿饥饿（Starvation）：长进程可能长时间等待 6.17进程到达时间区间时间P10.07 P22.04 P34.01 P45.04nSJF (non-preemptive)n平均等待时间 = (0 + 6 + 3 + 7)/4 = 4非抢占式非抢占式SJF例子例子P1P3P273160P4812 6.18抢占式抢占式SJF（（ SRTF ）例子）例子进程到达时间区间时间P10.07 P22.04 P34.01 P45.04nSJF (preemptive)n平均等待时间 = (9 + 1 + 0 +2)/4 =3P1P3P242110P457P2P116 6.19CPU下一次脉冲的探测下一次脉冲的探测n其长度只能估计n可以通过先前的CPU脉冲长度及计算指 数均值进行 6.20例子：例子：例子：例子：CPUCPU下一次脉冲的探测下一次脉冲的探测下一次脉冲的探测下一次脉冲的探测 6.21指数平均例子指数平均例子n =0ln+1 = nl近来历史没有影响n =1l n+1 = tnl只有最近的CPU区间才重要n如果扩展公式，得到:n+1 = tn+(1 - ) tn-1 + … +(1 - )j tn-j + … +(1 - )n+1 0n由于 和 (1 - )都小于或等于1，所以后面项的权比前面项的权小 6.22Priority Scheduling优先级调度优先级调度n调度依据：优先级n调度方法：调度优先级最高进程运行n优先数：表示优先级的整数[默认：最小整数 最高优先级]n优先级调度有：lPreemptive（抢占式）lNonpreemptive （非抢占式）n问题 饥饿 – 低优先级的可能永远得不到运行n解决方法 老化 – 视进程等待时间的长提高其优先数 6.23优先级调度优先级调度n优先数：l静态优先数：在运行前每个进程获得一个优先数，在运行过程中不可变化l动态优先数：在运行前每个进程获得一个基准优先数，在运行过程中可变化n最大特点：灵活（可以模拟其它调度算法）n目前大多数现代操作系统常用的调度算法 6.24非抢占例子非抢占例子进程优先级区间时间到达时间P1350P2321P3112P4423n平均等待时间 = (0 + 5 + 3+5)/4 =3.2510P1P2580P46P3 6.25抢占例子抢占例子进程优先级区间时间到达时间P1350P2321P3112P4423n平均等待时间 = (0 + 5 + 0+5)/4 =2.510P1P2260P43P3P18 6.26n8.0时：选择当时唯一的P1n10.0（作业1完成）：P2、P3、P4已到达，计算响应比:lP1：(10-8.3)/0.5=3.4lP2：(10-8.5)/0.1=15lP3：(10-9.0)/0.4=2.5n10.1(作业3完成)：计算P2、P4响应比：lP2：(10.1-8.3)/0.5=3.6lP4：(10.1-9.0)/0.4=2.75n最后， P2运行响应比高者优先调度算法响应比高者优先调度算法进程到达时间区间时间P18.02.0P28.30.5P38.50.1P49.00.4 6.27讨论nP164 5.9 6.28Round Robin (RR)时间片轮转时间片轮转n为分时系统设计n时间片：较小单位的CPU时间，通常为10-100毫 秒n调度依据：和FCFS相似n调度方法：每个进程运行时间长度为一个时间片。
时间片用完后，该进程将被抢占并插入就绪队列末尾n假定就绪队列中有n个进程、时间片为ql则每个进程每次得到不超过q单位的成块CPU时间l没有一个进程的等待时间会超过(n-1) ql在不超过nq时间内，n个进程都运行一次n特性lq 大 FIFOlq 小 系统开销过大 6.29时间片为时间片为20的的RR例子例子进程区间时间P153 P2 17 P368 P4 24nGantt图如下: nRR的平均周转时间比SJF长，但响应时间要短一些P1P2P3P4P1P3P4P1P3P302037577797117121 134154 162 6.30时间片和上下文切换次数时间片和上下文切换次数 6.31时间片和周转时间的关系时间片和周转时间的关系 6.32Multilevel Queue多级队列多级队列n就绪队列分为:l前台[交互式]l后台[批处理]n每个队列有自己的调度算法 前台 – RR后台 – FCFSn调度须在队列间进行.l固定优先级调度，即前台运行完后再运行后台有可能产生饥饿l给定时间片调度，即每个队列得到一定的CPU时间，进程在给定时间内执行；如，80%的时间执行前台的RR调度，20%的时间执行后台的FCFS调度 6.33多级队列调度多级队列调度 6.34Multilevel Feedback Queue多级反馈队列调度多级反馈队列调度n进程能在不同的队列间移动；可实现老化n多级反馈队列调度程序由以下参数定义:l队列数l每一队列的调度算法l决定进程升级的方法l决定进程降级的方法l决定需要服务的进程将进入哪个队列的方法 6.35多级反馈队列调度多级反馈队列调度 6.36多级反馈队列调度例子多级反馈队列调度例子n三个队列: lQ0 – 时间片为8毫秒lQ1 –时间片为16毫秒lQ2 – FCFSn调度l新的作业进入FCFS的Q0队列，它得到CPU时能使用8毫秒，如果它不能在8毫秒内完成，将移动到队列Q1 l作业在Q1仍将作为FCFS调度，能使用附加的16毫秒，如果它还不能完成，将被抢占，移至队列Q2 4、、多处理器调度多处理器调度和和线程线程调度调度 6.38多处理器调度多处理器调度n多个CPU可用时，CPU调度将更为复杂n对称多处理器 (SMP) – 每个处理器决定自己的调度方案n非对称多处理器(ASMP) – 仅一个处理器能处理系统数据结构，减轻了对数据的共享需求n所有进程：一个就绪队列n处理器：私有就绪队列n调度算法：和单处理器相似 6.39多处理器调度多处理器调度n处理器亲和性l进程要在某个给定的 CPU 上尽量长时间地运行而不被迁移到其他处理器的倾向性。
l高速缓存中的内容l软亲和性：进程通常不会在处理器之间频繁迁移l硬亲和性：进程不会在处理器之间迁移 （Linux）4例子： Linux的task_struct与 亲和性（affinity）相关的是 cpus_allowed 位掩码这个位掩码由 n 位组成，与系统中的 n 个逻辑处理器一一对应，1表示进程可以在对应处理器上运行n负载平衡l将任务平均分配给各个处理器l针对私有就绪队列l和处理器亲和性矛盾 6.40线程调度线程调度n局部调度(Local Scheduling) – 线程库怎样决定将哪个线程列入有效的轻量级进程LWPn全局调度 (Global Scheduling) – 内核怎样决定下一个运行的内核线程 6.41Pthread 线程程调度度nAPI允许局部调度和全局调度l局部：PTHREAD_SCOPE_PROCESSl全局：PTHREAD_SCOPE_SYSTEMnLinux and Mac OS X 仅允许PTHREAD_SCOPE_SYSTEMscopePTHREAD_SCOPE_SYSTEMPTHREAD_SCOPE_PROCESS 默认：PTHREAD_SCOPE_SYSTEM设置线程绑定状态部分Linux不支持PTHREAD_SCOPE_ PROCESS，需要查看manschedpolicySCHED_OTHER (regular, non-realtime scheduling)SCHED_RR (realtime, round-robin)SCHED_FIFO (realtime, first-in first-out) 默认：SCHED_OTHER优先级类别Sched param默认：0线程优先级参数如果schedpolicy的值为SCHED_OTHER，schedpolicy此属性无关紧要线程创建后可修改此属性 6.42Pthread 调度度API#include
