第四章 处理机调度1.ppt

1、第四章 处理机调度,4.1 分级调度 4.2 作业调度 4.3 进程调度 4.4 调度算法,处理机调度的核心是对CPU资源进行合理的分配使用。,学习目标： 1.掌握：作业和进程的关系、作业的状态及其转换；作业调度和进程调度的功能；常用的调度算法。 2.理解：性能评价指标；调度算法的评价。 3.了解：其他调度算法。 学习要点： 本章的重点在于掌握系统中对作业和进程如何实施调度，作业调度和进程调度的功能；掌握常用调度算法的思想，并能简单分析常用调度算法的性能。,4.1 分级调度,返回,1. 调度层次 2. 作业的状态及转换 3. 作业和进程的关系 4. 调度性能的衡量,1. 调度层次,作业调度（宏

2、观调度、高级调度） 按一定原则选择外存后备队列中的作业，为其分配内存等资源，并建立进程，使其获得竞争处理机的资格，进入就绪队列。此外，在作业执行完毕时，回收系统资源。 交换调度（中级调度：内外存交换） 按给定策略，将外存中处于就绪状态或等待状态的进程调入内存，或将内存中暂时不能运行的进程调至外存，以提高内存利用率和系统吞吐量。,进程调度（微观调度、低级调度） 决定就绪队列中的哪个进程应获得处理机，为其进行进程上下文切换以建立相应的执行环境（即由处理机调度程序将处理机分配给某就绪进程，处理机调度程序常驻内存） 线程调度：进程中相关堆栈和控制表等的调度 可有OS内核完成，也可由用户程序进行,2.

3、作业的状态及其转换,作业从提交给系统，直到完成任务退出系统前，在整个活动过程中它会处于不同的状态。通常，作业的状态分为：提交、后备（收容）、执行和完成。,提交状态：一个作业处于从输入设备进入外部存储设备的过程时所处的状态 后备状态：作业的全部信息都已通过输入设备输入到外存输入井中，等待进入内存 执行状态：作业一旦被作业调度程序选中，则为其分配所需的资源，并创建进程，送入内存中投入运行 完成状态：作业运行完毕，准备退出系统时的状态（所占用的资源尚未全部被系统回收）,作业状态及其转换图,输入管理 系统,提交,后备,就绪,等待,执行,就绪,等待,交换调度,完 成,作业调度,进程调度,线程调度,内存,

4、外存,3. 作业与进程的关系,作业是用户向计算机提交任务的任务实体 进程是计算机为了完成用户任务实体而设置的 执行实体 计算机要完成一个任务实体，必须要有一个以上的执行实体，即一个作业是由一个以上的进程组成 系统必须为一个作业创建一个根进程，然后再根据任务要求创建相应的子进程,4. 调度性能的衡量,我们可从不同的角度来判断调度算法的性能，如用户的角度、处理机的角度和算法实现的角度。 实际的调度算法选择是一个综合的判断结果。,面向用户的性能衡量,周转时间：作业从提交到完成（得到结果）所经历的时间。包括：在收容队列中等待，CPU上执行，就绪队列和阻塞队列中等待，结果输出等待等 平均周转时间T 平均

5、带权周转时间W（综合考虑周转时间和执行时间） 响应时间：用户发出命令（如击键，输入一个请求）到系统响应给出执行结果（如屏幕显示）所经历的时间,面向系统的性能衡量,吞吐量：给定时间内所完成的作业总数。跟作业本身特性和调度算法都有关系 设备（处理机）利用率 设备的均衡利用：如CPU繁忙的作业和I/O繁忙的作业搭配 公平性：避免某些作业的等待时间过长 优先级,调度算法本身的性能衡量,易于实现 执行开销比,4.2 作业调度,返回,1. 作业控制块 2. 作业调度及功能 3. 作业调度目标与性能衡量,在调度一个进程占有CPU之前，系统必须按某种策略选择外存后备状态的作业，为其创建进程、分配内存，并准备进

6、程执行所必须的资源。,1.作业控制块,系统为每个作业设置了一个作业控制块（JCB），记录已进入系统的各作业的情况，以便于管理和调度作业。,JCB的主要内容,2. 作业调度功能,作业调度的任务：完成作业从后备状态到执行状态的转变，以及从执行态到完成态的转变。,作业调度中状态的转换过程 (1)作业从后备状态到执行状态 (2)作业从执行状态到完成状态,后备作业队列空？,按调度算法，从后备 作业中选出一作业,调用存储管理/设备管理 程序，审核资源要求,资源要求能满足？,放弃该 作业,否,分配资源,调用进程管理 程序建立进程,进程调度,否,是,出 口,作业从后备状态到执行状态,是,调用存储管理/设备管理

7、程序 回收分配给该作业的全部资源,撤消该作业的所有进程及JCB,调用会计程序，计算该作业的 执行费用,调度下一个作业,作业从执行状态到完成状态,作业调度的具体功能,记录系统中各个作业的情况； （记录情况） 按照某种调度算法从后备作业队列中选取作业；（挑选作业） 为被选取的作业分配内存、外设等需要的资源；（分配资源） 为选中的作业建立相应的进程。 （建立进程） 在作业运行完毕或运行过程中因某种原因需要撤离时，进行善后处理工作，回收所占用的全部资源，撤消相关的进程及JCB。 （善后处理）,3.作业调度的目标与性能衡量,调度目标：,尽量公平合理 尽可能高的设备利用率 执行尽可能多的作业 尽快的响应时

8、间,想要设计一个理想的调度算法，同时满足上述目标是不可能的。实际系统中，调度算法需折衷考虑下列因素： 调度算法应与系统设计目标保持一致 注意系统资源均衡使用 保证提交的作业在截止时间内完成 设法缩短作业平均周转时间 大多数操作系统都采用比较简单的调度算法,（假定某作业i的提交时间为Tsi，完成时间为Tei） 作业的周转时间为： TiTei Tsi 作业的平均周转时间为： T,平均周转时间,调度算法性能的衡量,（其中，n为作业流中的作业数）,平均带权周转时间,作业的带权周转时间为：WiTi /ri 作业的平均带权周转时间为： W= （其中，ri为作业i的实际执行时间）,平均响应时间（分时、实时系

9、统）,4.3 进程调度,进程调度要解决的问题： WHAT：按什么原则分配CPU 进程调度算法 WHEN：何时分配CPU 进程调度的时机 HOW：如何分配CPU 进程调度过程（进程上下文切换）,1. 进程调度的功能 2. 进程调度的时机 3. 进程调度的方式 4. 进程调度性能衡量,1. 进程调度的功能,进程调度的任务是控制协调进程对CPU的竞争，即按一定的调度算法从就绪队列中选择一个进程，并把CPU的使用权交给被选中的进程。,进程调度的功能： 1. 记录所有进程的执行状况（静态和动态） 2. 按一定策略，选择一个就绪进程 3. 完成进程上下文切换,进程（上下文）切换的步骤： 检查是否可以进行进

10、程切换（如:原语执行时不可） 保存被切换进程的现场（如：程序计数器、寄存器），并移至合适的（就绪、阻塞）队列 选取一个新进程 恢复被选中进程的现场：装配该进程的正文，使其获得CPU控制权,2. 进程调度的时机,正在执行的进程运行完毕，或由于某种错误而终止运行 执行中的进程自己调用阻塞原语，将自己阻塞起来进入等待状态 执行中的进程执行了P原语操作，因资源不足而被阻塞，或执行了V原语操作激活了等待资源的进程队列 执行中的进程提出I/O请求后被阻塞 执行完系统调用，在系统程序返回用户进程时，可调度选择一新的用户进程执行 分时系统中时间片到 当有一个优先级更高的进程就绪（可抢占式）,进程调度的时机与引

11、起进程调度的原因及进程调度方式有关。 引起进程调度的原因有（原因之一发生时引发）：,3. 进程调度的方式,非抢占式 Non-preemptive（非剥夺式） 某一进程被调度执行后，将一直执行直到完成或发生某事件被阻塞，即是由于自身的原因而让出CPU。 抢占式 Preemptive（可剥夺式） 由于优先权、短作业优先或时间片到等因素，系统强行剥夺正在执行进程的CPU。,4. 进程调度性能衡量,定性衡量 公平性 可靠性（避免因调度引起的破坏） 简洁性（避免调度程序消耗较大的系统开销） 定量评价 CPU利用率 响应时间（交互式系统） 吞吐量（批处理系统）,作业调度与进程调度,作业调度为进程调度做准备

12、 作业调度对除了CPU之外的所有系统资源进行分配 进程调度专门负责对CPU进行分配，使进程活动起来 作业调度次数少，进程调度频率高 有的操作系统无作业调度，但进程调度是必不可少的,4.4 调度算法,1. 先来先服务算法 2. 短作业优先法 3. 最高响应比优先法 4. 时间片轮转法 5. 多级队列算法 6. 优先级法 7. 多级反馈轮转法,返回,针对不同的系统，往往采用的调度算法不相同，在操作系统中存在着多种调度算法， 通常有的算法适用于作业调度，有的算法适用于进程调度，有的两者都适应。,先来先服务调度算法 FCFS法 （First Come First Serve）,基本思想：按照作业提交/

13、进程变为就绪状态的先后次序，调入系统或分派CPU，换句话说，调度程序每次选择的作业/进程是等待时间最久的，而不管其运行时间的长短。 FCFS算法既可用于作业调度，也可用于进程调度,例：假定有三个作业，编号为1，2，3，它们几乎同时到达，但进入系统的先后顺序为：1，2，3。三个作业要求的运行时间如下图：,特点 系统开销小，实现简单 比较有利于长作业和CPU繁忙的作业，而不利于短作业和I/O繁忙的作业。 在实际操作系统和一般应用程序中较常采用FCFS算法，且通常和其他算法配合起来,作为辅助算法。,2. 短作业优先法 SJF法 (Shortest Job First),基本思想：对预计执行时间短的作

14、业（进程）优先处理。通常后来的短作业不抢先正在执行的作业。,又称为“短进程优先” (SPN，Shortest Process Next)；这是对FCFS算法的改进，其目标是减少平均周转时间。,SJF算法既可用于作业调度，也可用于进程调度,举例：,SJF的特点,优点： 缩短作业的等待时间 提高系统的吞吐量 比FCFS平均周转时间和平均带权周转时间短,缺点： 对长作业非常不利，可能长时间得不到执行 未能依据作业的紧迫程度来划分执行的优先级 难以准确估计作业（进程）的执行时间，从而影响调度性能,SJF的变型,“最短剩余时间优先” SRT(Shortest Remaining Time) 允许比当前进

15、程的剩余时间更短的进程来抢占,3. 最高响应比优先法 HRN法 (Highest Response_Ratio Next),基本思想： （FCFS和SJF的折衷） 先来先服务和短作业优先算法都有其片面性。 FCFS算法只考虑作业的等待时间，而忽视了作业的运行时间 SJF算法则相反，只考虑了作业的运行时间，而忽视了作业的等待时间 响应比高者优先调度算法是介于这两种算法之间的一种拆衷的算法，同时考虑每个作业的等待时间和估计需要的运行时间，从中选出响应比最高的作业投入运行。,既可用于作业调度，也可用于进程调度,最高响应比优先法 HRN法（续）,每次调度前都要计算每个作业的响应比，从而选择其中最大者投

16、入运行，因此系统开销相应增加。同时，吞吐量也小于SJF法。,举例,11,4. 时间片轮转法 RR 法(Round Robin),将系统中所有的就绪进程按照FCFS原则，排成一个队列。 每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。 在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。 进程可以未使用完一个时间片，就提前调度（如完成/阻塞）,可用于进程调度，但不能用于作业调度？,基本思想：（使等待时间与享受服务的时间成正比）,时间片长度的确定,时间片长度的影响 过长： 退化为FCF

17、S算法，进程在一个时间片内可以都执行完。 过短： 一个进程需要多个时间片才能处理完，上下文切换频繁，开销增加。 对时间片长度的要求： q (时间片长度) = R(要求的响应时间) / N (最大进程数) 时间片长度的影响因素： 系统的响应时间：时间片越大，响应时间越长（当进程数一定时） 就绪进程的数目：数目越多，时间片越小（当响应时间一定时） CPU运行速度：CPU运行速度快，则时间片可以短些；反之，则取长些。,5. 多级队列算法 (Multiple-level Queue),根据作业或进程的性质或类型的不同，将后备或就绪队列再分为若干个子队列。 各队列有不同的调度算法。 例如， 前 台 队

18、列（前 台终 端 型 作 业） ：RR法调度 后 台 队 列（后 台批 处 理 作 业 ）：FCFS法调度 仅 当 前 台 队 列 中 出 现 空 闲 时 间 片 时， 才 把 处 理 机 分 配 给 后 台 队 列 中 的 进 程,既可用于作业调度，也可用于进程调度,6. 优先级算法(Priority Scheduling),(1) 静态优先级 (2) 动态优先级 (3) 线性优先级调度算法（SRR, Selfish Round Robin),本算法是对优先级高的作业/进程优先处理。 可分成抢先式和非抢先式。,既可用于作业调度，也可用于进程调度,(1) 静态优先级,确定静态优先级的依据： 作

19、业/进程类型（如：系统进程优先级较高） 用户要求（紧迫程度和付费多少：系统对高优先级用户收取较高的费用） 对资源的需求（对CPU和内存需求较少的进程，优先级较高）,根据作业/进程的静态特性，优先级在作业/进程开始执行前就确定，直到终止都不改变。通常是一个整数。 （静态优先级可由用户/系统/操作员确定）,(2) 动态优先级,在就绪队列中，等待CPU时间愈长，则优先级提高，从而使优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行 进程占有CPU时间愈长，或每执行一个时间片，则优先级降低，从而一个进程持续执行时，其优先级可降低到出让CPU,创建时赋予的优先级，在运行过程中可以不断改变，以

20、便获得更好的调度性能。如：,(3) 线性优先级调度算法 SRR法 （Selfish Round Robin）,就绪进程队列分成两个： 新创建进程队列：按FCFS方式排队；进程优先级按速率a增加； 享受服务进程队列：已得到过时间片服务的进程也按FCFS方式排队；进程优先级按速率b增加；（ab0） 新创建进程队列中的队首进程转入享受服务队列的条件： 当新创建进程队列中的头一个进程的优先级与享受服务进程队列中最后一个进程的优先级相同时 当享受服务队列为空时,基本思想：,设时刻t1进程被创建，时刻t2转入享受服务队列，则时刻t时，进程的优先级为：（ ab0 ） p(t)=a*(t-t1) （ t1tt2 ） p(t)=a*(t2-t1)+b*(t-t2) （ t2t ）,SRR算法的优先级变化,SRR与FCFS和RR算法的关系,当ba0时， SRR算法退化成FCFS算法：两队列中进程的优先级永远不可能相等，所以享受服务队列中永远只有一个进程 当ab=0时，SRR算法就是RR算法,7. 多级反馈轮转法(Rou