四川大学 计算机学院 操作系统课件 CPU调度

CPU调度四川大学计算机学院左劼6.2基本概念多道程序设计的目标是任何时候都有一个进程在运行，以使CPU使用率最大化CPU–I/O区间周期：进程执行由CPU执行和I/O等待周期组成CPU区间分布CPU和I/O区间交替序列CPU区间时间直方图CPU调度器从就绪队列中选择一个进程，分配CPU资源给它，让他开始执行就绪队列不一定是一个先进先出的队列，根据不同的调度算法，可实现为FIFO队列、优先队列、树等CPU调度决策发生的4种环境：1.从运行状态切换到等待状态2.从运行状态切换到就绪状态3.从等待状态切换到就绪状态4.进程终止调度只能发生在1、4两种情况的称为非抢占调度(nonpreemptive).否则称为可抢占的(preemptive)抢占式调度需要考虑的问题两个进程共享数据进行系统调用或者I/O请求的时候抢占发生时，进程可能正在进行系统调用系统调用能否被抢占？中断处理(几乎任何时候都可能发生)受中断影响的代码必须保护禁止中断在多CPU环境中代价很高分派程序(Dispatcher)即调度程序的执行者进行上下文切换切换到用户态跳转到用户程序的相应位置，并开始执行分派延迟(Dispatchlatency)：停止一个进程而启动另一个进程执行所花费的时间6.2调度准则CPU利用率：尽量让CPU忙吞吐量：单位时间内完成的进程数量周转时间：进程从提交到完成的时间等待时间：进程就绪队列中等待的时间响应时间：从进程提交到第一次响应的时间优化准则最大化CPU使用率最大化吞吐量最小化周转时间

最小化等待时间

最小化响应时间调度算法

进程

区间时间

P124

P23

P33

假设进程到来的顺序是:P1,P2,P3

那么Gantt图为:

等待时间：P1:0;P2:24;P3:27平均等待时间:(0+24+27)/3=17P1P2P32427300先来先服务调度假设进程到来的顺序为：P2,P3,P1，则Gantt图为

等待时间：

P1=6;

P2=0;P3=3平均等待时间:(6+0+3)/3=3FCFS调度是非抢占的P1P3P263300最短作业优先调度

(SJF)CPU赋给具有最短后续CPU区间的进程两种模式:非抢占的：一旦分配了CPU给某一个进程的CPU区间，就只好等待它完成抢占的：如果有心的进程进入，并且具有更短的CPU区间长度，那么就抢占掉当前进程，除鞥为最短剩余时间优先调度(Shortest-Remaining-Time-First)SJF是最优的：对指定的进程集合，能得到最短平均等待时间非抢占SJF的例子

进程

到达时间

CPU区间长度

P1

0.0 7

P22.0 4

P34.0 1

P45.0 4Gantt图为平均等待时间：(0+6+3+7)/4=4P1P3P273160P4812抢占式SJF的例子

进程

到达时间

CPU区间长度

P1

0.0 7

P22.0 4

P34.0 1

P45.0 4Gantt图为平均等待时间：(9+1+0+2)/4=3P1P3P242110P457P2P116如何确定下一个CPU区间的长度只能对长度进行估计可以通过以前的CPU区间长度进行估计，使用指数平均算法指数平均的例子

=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，后面的项的权比前面的项的权要小优先权调度每一个进程都有一个优先权和其相关CPU资源分配给优先权最高的进抢占还是非抢占SJF是一种优先权调度，优先权时下以CPU区间长度的预测值问题：饿死

–低优先级的进程没有机会运行解决方法：老化

–逐渐增加系统中等待长时间进程的优先级轮转调度(Round-Robin)每一个进程分配一小块CPU时间单元(时间片，通常10-100毫秒)，时间片完成之后，进程被抢占，并且被添加到就绪队列尾部如果有n个进程在就绪队列中，且时间片为q，那么每个进程会得到1/n的CPU时间，并且每轮每个长度不超过q，每个进程必须等待的时间不超过(n-1)qq很大

FIFOq很小

处理器共享，但必须考虑q和上下文切换开销之间的比列，不能太低。时间片为20的RR调度例子

Process

CPU区间长度

P153

P217

P368

P424Gantt图为：

平均周转时间比SJF高，但能得到更好的响应时间P1P2P3P4P1P3P4P1P3P302037577797117121134154162更短的时间片导致更多的上下文切换周转时间随时间片的变化多级队列调度(MultilevelQueue)就绪队列被分成多个队列每个队列执行自己的调度算法

队列之间也需要执行调度算法固定优先级：先服务高优先级再服务低优先级

可能导致饿死时间片：给每个队列都有一定的时间片例如80%给前台进程，采用RR20%给后台，采用FCFS五个优先级别的多级队列多级反馈(Feedback)队列一个进程可以在队列之间移动(老化算法的一种方法)多级反馈队列的参数：队列数量每个队列的调度算法确定什么时候升级一个进程的方法确定什么时候将级一个进程的方法确定进程需要服务时应该进入那一个队列的方法一个多级反馈队列的例子三个队列:Q0–时间片8毫秒Q1–时间片16毫秒Q2–FCFS调度一个新作业进入Q0队列，并按FCFS调度，当他获得CPU，就得到8毫秒的时间，如果8毫秒内没有结束，作业就移动到队列Q1在Q1

中仍然按照FCFS进行调度，并且得到16毫秒的时间，如果他仍然没有结束，将被抢占并移动到队列

Q2多处理器(Multiple-Processor)调度当由多个CPU的时候，CPU调度将复杂得多对称多处理器(SymmetricMulti-processing,SMP)：每个CPU自己进行自己的调度选择非对称多处理器：只有一个处理器可以访问系统数据结构，进行调度处理，分配任务给其他的CPU，以避免对系统数据的共享访问实时(Real-Time)调度硬实时系统：对关键任务的完成时间有保障软实时系统：关键任务的优先级比其他任务的优先级高优先权调度，并且要保证实时进程的绝对优先级分派延迟必须小因为很多系统有些系统调用很慢需要允许系统调用是可抢占的分派延迟线程调度本地调度：线程库决定哪一个线程和LWP联系起来全局调度：内河决定下一步让那一个内核线程得到CPU资源进行执行Solaris2调度四类调度：实时，系统，分时和交互每一个类有不同的优先级和调度算法分时的调度策略采用多级反馈队列，动态地调整优先级别和时间片的长度

交互式进程通常具有较高的优先级别使用系统类来运行内核进程，如调度程序和换页后台服务。调度策略是不分时的实时类型的线程具有最高的优先级从类型优先级转换到全局优先级Solaris2调度Java线程调度JVM使用基于优先级的可抢占的调度算法如果有很多线程具有相同的优先级，那么采用FIFO队列来处理线程Java线程调度JVM进行线程调度的时机:当前运行的线程离开可执行状态有一个更高优先级的线程进入可执行状态注意：JVM规范并没有指定线程是否是分时执行的JVM中的分时问题对于不是分时的JVM，yield()方法就需要被使用到

while(true){//执行CPU密集任务

...

Thread.yield();}yield()方法将暂停当前线程的执行，让出CPU资源给其他相同优先级的线程这是协作式多任务的一种实现方式Java线程优先级优先级列表:

Priority

Comment

Thread.MIN_PRIORITY

最低优先级

Thread.MAX_PRIORITY

最高优先级

Thread.NORM_PRIORITY