操作系统处理机调度

1、主要目的CPU调度是多道程序设计的基础，通过在进程之间切换CPU，操作系统可以使计算机做的事，提高CPU的利用率，并使不同的用户能够公平地得到CPU本节介绍处理机调度算法并对调度算法的特点进行简单分析。 调度的类型高级调度中级调度低级调度（CPU调度） 高级调度又称为“宏观调度”或者“作业调度”从用户工作流程的角度，一次提交的若干个作业，对 每个作业进行调度。时间上通常是分钟、小时或天。 接纳多少个作业，取决于允许多少个作业同时在内存运行（多道程序度）接纳哪些作业，取决于采用的调度算法作业调度出现在批处理系统中或者是实时系统中， 分时系统中没有作业调度程序 中级调度 内存与外存对换区交换内容：

2、从器的角度，将进程的部分或全部内容换出到外存上，将当前进程所需部分内容换入到内存 注意：CPU仅能直接内存，所以指令和数据放在内存，CPU方可执行与它们 低级调度（CPU调度） 从就绪队列中选择一个等待CPU的进程并分配CPU给它。调度程序负责将CPU分配给被选进程。又称： 微观调度 进程调度：讨论一般调度概念时采用 线程调度：特指线程概念决定就绪队列中的哪个进程将获得处理机 进程调度执行频繁，通常是几十毫秒执行一次 有两种实现方式： 非式nonpreemptive式，的原则如下：» 时间片原则(轮转RR)» 优先权原则/FCFS» 最短作业（进程）优先原则（SJ

3、F） 进程调度的队列（RR） 作业调度与进程调度队列 三级调度方式的队列 针对多个就绪对列的进程调度 CPU的三级调度示意图 调度准则Scheduling CriteriaCPU利用率（utilization）从使用的角度（系统利用率高）吞吐量（Throughput）周转时间（Turnaround time） 等待时间（Waiting time）响应时间（Response time）用户的角度（响应迅速）实际的处理机调度算法选择是一个综合的判断结果 面向用户的调度准则1周转时间(批处理系统)作业从提交到完成（得到结果）所经历的时间。包括：在收容队 列中等待，CPU上执行，就绪队列和阻塞队列中等

4、待，结果输出 等待 外存等待时间、就绪等待时间、CPU执行时间、I/O操作时间 Ti = 作业完成时间Tic 作业到达时间Tia平均周转时间平均周转时间T=(Ti) / n （n为作业总数）带权平均周转时间W= (Wi) = ( ( Ti /Tir) / n （ Tir 为实际运行时间）响应时间(分时系统)用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示） 的时间 面向用户的调度准则2截止时间的保证(实时系统) ：开始截止时间，任务必须开始的最迟时间完成截止时间，任务必须完成的最迟时间是评价实时性能的重要指标。优先级：代表任务运行的紧迫程度，紧迫的任务具有高优先级别，严格的情况可采用公

5、平性：调度方式。不因作业或进程本身的特性而影响对作业的调度性能， 比如造成长作业等待很长时间一直得不到运行的情况。 面向系统的调度性能准则吞吐量：时间内所完成的作业数（批处理系统调度考虑的因素）处理机利用率：使CPU尽量处于忙碌状态（大型主机考虑的因素）各种的均衡利用：如CPU繁忙的作业和I/O繁忙的作业搭配（大型主机考虑的因素） 调度算法 操作系统中的调度的实质是一种分配 这些调度算法有的适用于作业调度，有的适用于进程调度，有的两者都适用。 先来先服务(FCFS, First Come First Service) 这是最简单的调度算法，按先后顺序调度。按照作业提交或进程变为就绪状态的先后次

6、序，分派CPU当前作业或进程占用CPU，直到执行完或因申请而阻塞，如申请I/O，才出让CPU（非方式）。在得到满足后作业或进程则被唤醒（如I/O完成），并不立即恢复执行，通常等到正在运行的作业或进程出让CPU （因为是非 FCFS的特点比较有利于长作业，而不利于短作业。有利于CPU繁忙的作业，不利于I/O繁忙的作业。方式） FCFS 最短作业优先(SJF, Shortest Job First) 又称为“短进程优先”SPN(Shortest Process Next)；这是对FCFS算法的改进，其目标是减少平均周转时间对预计执行时间短的作业（进程）优先分派处理机。该算法与每个进程的下一个CPU

7、处理周期相关 SJF的特点 优点：比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量； 缺点：对长作业非常不利，可能长时间得不到执行；存在饥饿现象未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业（进程）的执行时间，从而影响调度性能。 SJF举例 SJF举例 时间片轮转算法(Round Robin) 本算法基本思路是通过以时间片轮转，提高进程并发性和加快响应时间，从而提高利用率 轮转调度最初的队列形成可按照FCFS 或者按照优先级排队为每个进程分配一个时间片， 轮流运行调度信息包括了进程进入就绪队列的时间和时间片大小 时间片轮转算法将系统中所有的就绪进程

8、按照FCFS原则，排成一个队列。每次调度时将CPU分派给队首进程，让其执行一个时间片。 时间片大小可以规定为几毫秒到几百毫秒不等。在时间片结束时，会产生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的 末尾，并通过上下文切换执行当前的队首进程。进程可以在时间片没用完之前，自愿放弃使用CPU（如运 行完毕，或者由于等I/O而被阻塞） 时间片长度的确定时间片长度 q过长：为FCFS算法，进程在一个时间片内都执行完，导致对短的交互式请求的响应时间变长。过短：用户的一次请求需要多个时间片才能处理完， 导致过多的进程切换降低了CPU效率比较合理的折衷考虑，可设时间片为100ms响应时间T ：

9、T(响应时间)=N(进程数目)*q(时间片)就绪进程的数目N ：如果响应时间固定，就绪进程的数目越多，时间片越小带权周转时间的计算:W=作业周转时间Ti/作业的实际运行时间Tr A进程：W=15/4=3.75=周转时间/服务时间周转时间：作业完成时间Tic-作业到达时间Tia 平均周转时间T= S (Ti)/n带权平均周转时间W= S (Wi)= (S(Ti/Tri)/n五个进程分时运行的周转时间运算 TiaTr TicTiTWiTicWTTiWiW2.73.253.433.25 五个进程按时间片运行的情况q=1q=4 小时间片导致进程切换时间增多 周转时间随时间片变化的方式 优先级算法(Pr

10、iority Scheduling) 平衡各进程对响应时间的要求。适用于作业调度和进程调度，可分成可式非可式；优先级调度 静态优先级 创建进程时确定，直到进程终止前都不改变。通常是一个整数。决定优先级的因素有： 进程类型（系统进程优先级较高） 对的需求（对CPU和内存需求较少的进程，优先级较高） 用户要求（紧迫程度和多少） 优先级算法存在饥饿问题 动态优先级 在创建进程时赋予的优先级，可以在进程运行过程中自动改变 如：等待时间越长优先级越高 在就绪队列中的进程，随着等待时间的积累，其优先级不断提 高，经过一段时间后，其优先级可达到最高，从而获得调度执 行；执行的时间越长优先级越低 运行中的进程

11、每执行一个时间片，其优先级便降低一定的值， 如果一个进程持续执行，其优先级便可降低到不再为最高的而 让出CPU，次高优先级的进程获得CPU执行。一种替代算法 为每个进程分配一个时间片，当最高优先级用尽时间片时，CPU让给次高优先级的进程运行。算法评价评价方法： 建模排队模型n=l ´ W其中：l为进程平均到达率W为进程在队列中的平均等待时间n为平均队列长度 模拟：通过模拟机模拟这些调度算法 实现：在操作系统中实现评价功能 算法评价排队模型n=l ´ W其中：l为进程平均到达率W为进程在队列中的平均等待时间 n为平均队列长度例如：平均每秒7个进程到达队列中，通常有14个进程在

12、队列中，则每个进程平均等待时间为2秒， 即：W=n/ l =14/7=2 算法评价 评价方法： 模拟：通过模拟机模拟这些调度算法最高响应比优先调度算法响应比的计算等待时间相同，短作业优先（要求服务的时间短）要求服务时间相同，优先权决定于等待时间，（FCFS)对于长作业，若等待时间过长，优先权可提高带权周转时间=周转时间/服务时间 多级队列算法(Multiple-level Queue) 本算法引入多个就绪队列，通过各队列的区别对待，达到对不同类型的作业的处理(比如交互型作业为前台,批处理型作业为作业)根据作业或进程的性质或类型的不同，将就绪队列再分为若干个子队列。每个作业固定归入一个队列。不同

13、队列可有不同的优先级、不同的时间片大小、不同的调度策略等 多级队列调度(Multiple Queue Scheduling)多级反馈队列调度(Multiple Feedback Queue Scheduling)具有多级反馈的轮转算法 (Round Robin with Multiple Feedback) 多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展。其特点是：为提高系统吞吐量和缩短平均周转时间而照顾短进程为获得较好的I/O设备利用率和缩短响应时间而照顾I/O 型进程不必事先知道进程的执行时间，可在不同队列中动态调节 多级反馈队列算法设置多个就绪队列，分别赋予不同的优先级，如逐级

14、降低， 队列1的优先级最高。每个队列执行时间片的长度也不同， 规定优先级越低则时间片越长，如逐级加倍新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成。仅当较高优先级的队列为空，才调度较低优先级的队列中 的进程执行。如果进程执行时有新进程进入较高优先级的 队列，则抢先执行新进程，并把被抢先的进程投入原队列 的末尾。 分级轮转法FCFS链头指针¼¼¼¼轮转刚从CPU上退下来的进程最高优先级次高优先级

15、8;最低优先级 实时调度要求更详细的调度信息：如，就绪时间、开始或完成截止时间、处理时间、 要求、绝对或相对优先级（硬实时或软实时）采用可式调度快速中断响应，在中断处理时（硬件）关中断的时间尽量短快速任务分派。相应地采用较小的调度线程）（如 实时调度算法时间片轮转非式优先权调度基于时钟中断式优先权调度立即式调度用于实时信息处理各种算法的调度时机用于不严格的实时控制系统基于时钟中断，用于大多数实时系统中用于对外部快速响应的实时系统中 基于开始截止时间的任务调度 基于完成截止时间的任务调度A5(90) A6(110) A7(130) A8(150)B任务周期是50，执行长 A1(10) A2(30

16、) A3(50)度是25；A任务周期为20,执行长度为10图中指示的位置是完成截止时间 B1(25) B2(75) B3(125)A4 A5 A6 A7 A1 A2 A3 B1(20) B1(5) B2(15) B2(10) B3(20)A4(70) 多处理机调度 与单处理机调度的区别：注重整体运行效率（而不是个别处理机的利用率） 调度方式增多(同构/异构有不同的调度方式)进程的调度比单处理机的复杂 调度广泛采用线程提高并行度 对称式多处理系统(SMP) 按控制方式，同构的SMP调度可分为：集中控制 静态调度（进程固定处理机） 动态调度（进程不固定处理机）分散控制 自调度 （空闲处理机主动地从

17、一个公共就绪队列中选择进程） 非对称式多处理系统(ASMP) 主从处理机系统由主处理机管理一个公共就绪队列，并分派进程给从处理机执行 各个处理机有固定分工如：执行OS的系统功能、I/O处理、应用程序等OS的驻留在主机上 进程调度由主机执行，主机一旦故障，会使整个系统瘫痪 固定和非固定的处理机分配 静态分配(static assignment)：每个CPU设立一个就绪队列，进程从开始执行到完成，都在同一 个CPU上。优点：调度算法开销小。缺点：容易出现忙闲不均。 动态分配(dynamic assignment)：各个CPU采用一个公共就绪队列，队首进程每次分派到当前空闲的CPU上执行。 每个处理

18、机为各自选取运行的进程 自调度(self-scheduling)：各个CPU采用一个公共就绪队列，每个处理机都可以从 队列中选择适当进程来执行。需要对就绪队列的数据结构进行互斥控制。是最常用的算法，实现时易于移植采用单处理机的调度技术。 自调度的问题瓶颈问题各处理机共享的就绪队列低效问题被阻塞的进程重新运行时不一定仍在阻塞前的处理机上运行，那么高速缓存中的内容需要重置线程切换问题由于合作中的几个线程没有同时运行而受阻，进而被切换下来 成组调度(gang scheduling) 将一个进程中的一组线程，每次同时分派到一组处理机上执行，在处理机时要同时对这一组线程进行 优点。通常这样的一组线程在应用逻辑上相互合作，成组调 度提高了这些线程的执行并行度，有利于减少阻塞并加快推进速度，提高系统吞吐量。每次调度可以完成多个线程的分派，能够减少调度次数，从而减少调度算法的开销 两种成组调度空闲时间为：1/5和3/4相乘=15%空闲时间为：1/2和3/4相乘=37.5% 面向所有的应用程序平均分配处理机时间(2个应用程序) 面向所有的线程平均分配处理机时间（5个线程）N个处理机M个应用程序，每个应用程序可有1/M的时间去占有N个处理机 处理机调度(d