苏州大学操作系统概念第五章

Chap5CPU调度6.2内容1.基本概念2.调度准则3.调度算法4.多处理器调度和线程调度5.调度实例1、基本概念6.4CPU脉冲周期CPU调度（进程调度或线程调度）是多任务操作系统的基础通过多道程序设计得到CPU的最高利用率进程的执行包括进程在CPU上执行和等待I/OCPU脉冲周期I/O脉冲周期6.5CPU脉冲周期统计6.6CPU调度程序选择内存中的就绪进程，并分配CPU给其中之一调度方案：非抢占式调度(nonpreemptive)一旦把处理机分配给某进程后，系统不允许其他进程抢占已分配给它的CPU。直至该进程完成，自愿释放CPU，或发生某事件而被阻塞，才再把CPU分配给其他进程抢占式调度(preemptive)允许调度程序根据某种原则去暂停某个正在执行的进程，将已分配给她的CPU重新分配给另一进程6.7CPU调度时机CPU调度可能发生在当一个进程:1.从运行转到等待2.从运行转到就绪3.从等待转到就绪4.终止运行非抢占式调度：1、4抢占式调度：2、36.8分派程序(Dispatcher)分派程序负责把CPU的控制权转交CPU调度程序，包括:切换上下文切换到用户态跳转到用户程序的适当位置并重新运行之分派延迟(Dispatchlatency)–分派程序终止一个进程的运行并启动另一个进程运行所花的时间2、调度准则6.10概念CPU利用率–固定时间内CPU运行事件的比例吞吐量–单位时间内运行完的进程数周转时间–进程从提交到运行结束的全部时间带权周转时间—周转时间/运行时间等待时间–进程等待调度（不在运行）的时间片总和响应时间–从进程提出请求到首次被响应[而不是输出结果]的时间段[在分时系统环境下]012345678910运行时间：1+2+3=6周转时间：10-0=10不运行运行等待时间：1+1+2=4或10-6=4响应时间：1=等待时间6.11优化准则最大的CPU利用率最大的吞吐量最短的周转时间最短的等待时间最短的响应时间解决方法调度算法：决定就绪队列中哪个进程被选中运行3、调度算法6.13First-ComeFirst-Served(FCFS)先来先服务调度算法调度依据：进入就绪队列的时间调度方法：先进入就绪队列的进程被优先选中运行使用FIFO队列实现举例:进程区间时间P124P23P33假定进程到达顺序如下:P1,P2,P3该调度的Gantt图为:等待时间：P1=0;P2=24;P3=27平均等待时间:(0+24+27)/3=17P1P2P324273006.14先来先服务调度算法假定进程到达顺序如下P2,P3,P1.该调度的Gantt图为:等待时间:P1=6;P2=0;P3=3平均等待时间:(6+0+3)/3=3比前例好得多护航效果convoyeffect：长进程先于短进程到达有利于长进程，而不利于短进程P1P3P2633006.15讨论1.FCFS是抢占式调度还是非抢占式调度？2.FCFS堆怎样的操作系统不利？可以用于什么操作系统？6.16Shortest-Job-First(SJF)短作业优先调度算法从FCFS存在的问题得到启发调度依据：每个进程下次运行的CPU脉冲长度调度方法：调度最短的进程运行两种模式:非抢占式调度：一旦进程拥有CPU，它可在该CPU脉冲结束后让出CPU抢占式调度：有比当前进程剩余时间更短的进程到达时，抢占当前运行进程的CPU，也称为最短剩余时间优先调度Shortest-Remaining-Time-First(SRTF)SJF最优–给出了最短的平均等待时间饥饿（Starvation）：长进程可能长时间等待6.17进程到达时间区间时间P10.07P22.04P34.01P45.04SJF(non-preemptive)平均等待时间=(0+6+3+7)/4=4非抢占式SJF例子P1P3P273160P48126.18抢占式SJF（SRTF）例子进程到达时间区间时间P10.07P22.04P34.01P45.04SJF(preemptive)平均等待时间=(9+1+0+2)/4=3P1P3P242110P457P2P1166.19CPU下一次脉冲的探测其长度只能估计可以通过先前的CPU脉冲长度及计算指数均值进行:Define4.10,3.burstCPUnexttheforvaluepredicted2.burstCPUoflenghtactual1.1nthnnt.11nnnt6.20例子：CPU下一次脉冲的探测6.21指数平均例子=0n+1=n近来历史没有影响=1n+1=tn只有最近的CPU区间才重要如果扩展公式，得到:n+1=tn+(1-)tn-1+…+(1-)jtn-j+…+(1-)n+10由于和(1-)都小于或等于1，所以后面项的权比前面项的权小6.22PriorityScheduling优先级调度调度依据：优先级调度方法：调度优先级最高进程运行优先数：表示优先级的整数[默认：最小整数最高优先级]优先级调度有：Preemptive（抢占式）Nonpreemptive（非抢占式）问题饥饿–低优先级的可能永远得不到运行解决方法老化–视进程等待时间的长提高其优先数6.23优先级调度优先数：静态优先数：在运行前每个进程获得一个优先数，在运行过程中不可变化动态优先数：在运行前每个进程获得一个基准优先数，在运行过程中可变化最大特点：灵活（可以模拟其它调度算法）目前大多数现代操作系统常用的调度算法6.24非抢占例子进程优先级区间时间到达时间P1350P2321P3112P4423平均等待时间=(0+5+3+5)/4=3.2510P1P2580P46P36.25抢占例子进程优先级区间时间到达时间P1350P2321P3112P4423平均等待时间=(0+5+0+5)/4=2.510P1P2260P43P3P186.268.0时：选择当时唯一的P110.0（作业1完成）：P2、P3、P4已到达，计算响应比:P1：(10-8.3)/0.5=3.4P2：(10-8.5)/0.1=15P3：(10-9.0)/0.4=2.510.1(作业3完成)：计算P2、P4响应比：P2：(10.1-8.3)/0.5=3.6P4：(10.1-9.0)/0.4=2.75最后，P2运行响应比高者优先调度算法要求服务时间要求服务时间等待时间优先权进程到达时间区间时间P18.02.0P28.30.5P38.50.1P49.00.46.27讨论P1645.96.28RoundRobin(RR)时间片轮转为分时系统设计时间片：较小单位的CPU时间，通常为10-100毫秒调度依据：和FCFS相似调度方法：每个进程运行时间长度为一个时间片。时间片用完后，该进程将被抢占并插入就绪队列末尾假定就绪队列中有n个进程、时间片为q则每个进程每次得到不超过q单位的成块CPU时间没有一个进程的等待时间会超过(n-1)q在不超过nq时间内，n个进程都运行一次特性q大FIFOq小系统开销过大6.29时间片为20的RR例子进程区间时间P153P217P368P424Gantt图如下:RR的平均周转时间比SJF长，但响应时间要短一些P1P2P3P4P1P3P4P1P3P3020375777971171211341541626.30时间片和上下文切换次数6.31时间片和周转时间的关系6.32MultilevelQueue多级队列就绪队列分为:前台[交互式]后台[批处理]每个队列有自己的调度算法前台–RR后台–FCFS调度须在队列间进行.固定优先级调度，即前台运行完后再运行后台。有可能产生饥饿给定时间片调度，即每个队列得到一定的CPU时间，进程在给定时间内执行；如，80%的时间执行前台的RR调度，20%的时间执行后台的FCFS调度6.33多级队列调度6.34MultilevelFeedbackQueue多级反馈队列调度进程能在不同的队列间移动；可实现老化多级反馈队列调度程序由以下参数定义:队列数每一队列的调度算法决定进程升级的方法决定进程降级的方法决定需要服务的进程将进入哪个队列的方法6.35多级反馈队列调度6.36多级反馈队列调度例子三个队列:Q0–时间片为8毫秒Q1–时间片为16毫秒Q2–FCFS调度新的作业进入FCFS的Q0队列，它得到CPU时能使用8毫秒，如果它不能在8毫秒内完成，将移动到队列Q1作业在Q1仍将作为FCFS调度，能使用附加的16毫秒，如果它还不能完成，将被抢占，移至队列Q24、多处理器调度和线程调度6.38多处理器调度多个CPU可用时，CPU调度将更为复杂对称多处理器(SMP)–每个处理器决定自己的调度方案非对称多处理器(ASMP)–仅一个处理器能处理系统数据结构，减轻了对数据的共享需求所有进程：一个就绪队列处理器：私有就绪队列调度算法：和单处理器相似6.39多处理器调度处理器亲和性进程要在某个给定的CPU上尽量长时间地运行而不被迁移到其他处理器的倾向性。高速缓存中的内容软亲和性：进程通常不会在处理器之间频繁迁移硬亲和性：进程不会在处理器之间迁移（Linux）例子：Linux的task_struct。与亲和性（affinity）相关的是cpus_allowed位掩码。这个位掩码由n位组成，与系统中的n个逻辑处理器一一对应，1表示进程可以在对应处理器上运行负载平衡将任务平均分配给各个处理器针对私有就绪队列和处理器亲和性矛盾6.40线程调度局部调度(LocalScheduling)–线程库怎样决定将哪个线程列入有效的轻量级进程LWP全局调度(GlobalScheduling)–内核怎样决定下一个运行的内核线程6.41Pthread线程调度API允许局部调度和全局调度局部：PTHREAD_SCOPE_PROCESS全局：PTHREAD_SCOPE_SYSTEMLinuxandMacOSX仅允许PTHREAD_SCOPE_SYSTEMscopePTHREAD_SCOPE_SYSTEMPTHREAD_SCOPE_PROCESS默认：PTHREAD_SCOPE_SYSTEM设置线程绑定状态部分Linux不支持PTHREAD_SCOPE_PROCESS，需要查看manschedpolicySCHED_OTHER(regular,non-realtimescheduling)SCHED_RR(realtime,round-robin)SCHED_FIFO(realtime,first-infirst-out)默认：SCHED_OTHER优先级类别Schedparam默认：0线程优先级参数如果schedpolicy的值为SCHED_OTHER，schedpolicy此属性无关紧要线程创建后可修改此属性6.42Pthread调度API#includepthread.h#includestdio.h#defineNUM_THREADS5intmain(intargc,char*argv[]){inti,scope;pthread_ttid[NUMTHREADS];pthread_attr_tattr;/*getthedefaultattributes*/pthread_attr_init(&attr);/*firstinquireonthecurrentscope*/if(pthread_attr_getscope(&attr,&scope)!=0)fprintf(stderr,Unabletogetschedulingscope\n);else{if(scope==PTHREAD_SCOPE_PROCESS)printf(PTHREAD_SCOPE_PROCESS);el