进程调度3.ppt

1、第七节 处理机调度（CPU调度）,UNIPROCESSOR SCHEDULING(单处理机调度） 调度的任务是按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。 问题提出：多个进程竞争一个CPU，怎样解决进程竞争CPU的问题 要解决的问题 WHAT：按什么原则分配CPU 调度算法 WHEN：何时分配CPU 调度的时机 HOW： 如何分配CPU CPU调度实现过程（进程的上下文切换）,一个作业从提交开始直到完成，往往要经过下述三级调度： 高级调度(HighLevelScheduling) 低级调度（LowLevelScheduling） 中级调度(Intermediat

2、e-LevelScheduling),一、处理机的三级调度,1、高级调度 又称为作业调度，它决定将哪些在外存上处于后备状态的作业调入主机内存，准备执行。因此，有时把它称做接纳调度（Admission Scheduling)。 系统一旦接纳了一个作业，便将它变为一个或一组进程，为它们分配必要的资源，并挂到就绪队列上，在批处理系统中，大多配有高级调度。但在分时系统中，却往往不配置高级调度(?)。高级调度的执行频率较低，它与作业的大小、到达的速率有关，通常为几分钟一次，甚至更久。,2、低级调度 又称为进程调度。它决定内存的就绪队列中哪个进程将获得处理机，并实际执行将处理机分配给该进程的操作。执行分配

3、处理机的程序称为分派程序(Dispatcher)。分派程序的执行频率非常高，典型情况是几十毫秒一次，因此它必须常驻内存。进程调度是操作系统中最基本的调度，在批处理及分时系统中都必须配置它。,3、中级调度 在有些系统中，特别是分时系统及具有虚拟存储器的系统中，可能增加一级中级调度。其主要作用是在内存和外存对换区之间进行进程对换，以解决内存紧张问题。即它将内存中处于等待状态的某些进程调至外存对换区，以腾出内存空间，而将外存对换区上已具备运行条件的进程重新调入内存，准备运行，一个进程在运行期间可能要多次调进调出。,调度目标和原则主要有以下几点： 1、从用户的角度来看： 周转时间要短（周转时间TT？）

4、； 响应时间（响应时间RT？）要短； 截止时间内完成； 优先权； 2、从系统、 吞吐量要大； 资源利用率要高（主要指CPU利用率）； 平衡使用资源； Fairness（公平性） 二者可能有冲突，更偏重于用户的角度。,二、进程调度的原则,1、非剥夺方式：当一个进程获得处理机之后，除非它因某种原因阻塞or运行完毕，不能从该进程夺走处理机控制权； 主要用于批处理系统。 2、剥夺方式：当一个进程运行时，系统可基于某种原则，强行将其撤下，把处理机分配给其它进程。 剥夺准则：优先权原则；短进程优先、；时间片、；强制性剥夺；,三、进程调度的基本方式,一个进程运行完毕，或由于某种错误而终止运行 当一个进程在运

5、行中处于等待状态（等待I/O） 分时系统中时间片到 当有一个优先级更高的进程就绪（可抢占式），例如：新创建一个进程，一个等待进程变成就绪 在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语，唤醒原语）,四、进程调度的时机,五、进程调度算法,1、先来先服务FCFS非剥夺 算法思想：进程进入就绪队列的先后 特点：简单易行，性能不好（不利于短作业）。 例：有三个进程P1.P2.P3依次进入就绪队列： 进程运行实际占用CPU时间 P124 P23 P33,FCFS算法执行如上图： 周转时间：TT1=24 TT2=27 TT3=30（不利于短作业） 平均周转时间：ATT(Average)=(

6、24+27+30)/3=27 观察，如果将执行顺序改变如下图，则： TT3=30 ，ATT=(3+6+30)/3=13,2、短进程（作业）优先SP（J）F 算法思想：调度当前就绪队列中的CPU周期最短的进程（作业）运行。 例：进程P1、P2、P3、P4依次进入就绪队列 进程实际运行占用CPU时间 P116 P212 P34 P43,SPF：ATT=(3+7+19+35)/4=16 FCFS:ATT=(16+28+32+35)/4=27.75 SPF的ATT最短 缺点：不易实现，不利于长作业,3、高优先权优先调度算法（HPFHighest Priority First） 算法思想：调度就绪队列中

7、优先数最高的进程运行。 确定优先权的方法 静态优先权：在进程创建时指定优先数，在进程运行时优先数不变 动态优先权：在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变,高响应比优先算法： 是优先权算法的一个典型示例，根据每个进程的响应比来确定进程执行的先后顺序,高响应比优先算法具有FCFS和SPF的特点，是二者的结合,4、时间片轮转调度算法(RRRound Robin) 把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个

8、进程运行。 分时系统中常用时间片轮转法 时间片的选择问题 时间片大，蜕化成FCFS；时间片短，CPU花费在进程的切换时间较多。,例：对于如下三个进程，q=4s 进程 实际运行占用CPU时间 P124 P23 P33 TT1=30 TT2=7 TT3=10 ATT=(30+7+10)/316 SPF:ATT=(3+6+30)/3=13,5、多队列反馈调度算法 将就绪队列分为N级； 每个就绪队列分配给不同的时间片，队列级别越高，时间越长，级别越小，时间片越小； 最后一级采用时间片轮转，其他队列采用先进先出； 一个新进程就绪后进入第一级队列的末尾 仅当上一级队列空时，才能调度下一级队列 UNIX系统采用多级反馈队列轮转法进行调度,6、随机算法 符合统计规律（eg：扔硬币等）,六、调度实现,进程调度时须完成2个进程在CPU上的切换。从CPU上换下的进程称为下行进程，换上的进程称为上行进程，正在CPU上运行的进程称为现行进程。因此进程调度程序由三步组成： 保存下行进程的上下文； 按调度算法从就绪队列