操作系统教程—linux实例分析孟庆昌第3章处理机调度

《操作系统教程—linux实例分析孟庆昌第3章处理机调度》由会员分享，可在线阅读，更多相关《操作系统教程—linux实例分析孟庆昌第3章处理机调度（75页珍藏版）》请在金锄头文库上搜索。

1、第3章 处理机调度,3.1 调度级别 3.2 作业调度 3.3 进程调度 3.4 性能评价标准 3.5 常用调度算法 3.6 Linux系统中的进程调度 习题,3.1 调 度 级 别,一般来说， 作业从进入系统到最后完成， 可能要经历三级调度： 高级调度、 中级调度和低级调度。 (1) 高级调度： 又称作业调度。 (2) 中级调度： 为了使内存中同时存放的进程数目不至于太多， 有时就需要把某些进程从内存中移到外存上， 以减少多道程序的数目， 为此设立了中级调度。,(3) 低级调度： 又称进程调度。 其主要功能是根据一定的算法将CPU分派给就绪队列中的一个进程。,3.2 作 业 调 度,3.2.

2、1 作业状态 如前所述， 作业从提交给系统， 直到完成任务后退出系统前， 在整个活动过程中它会处于不同的状态。 通常， 作业状态分为四种： 提交、 后备、 执行和完成， 如图3-1所示。,图3-1 作业的基本状态,（1） 提交状态即用户向系统提交一个作业时， 该作业所处的状态。 （2） 后备状态即用户作业经输入设备（如读卡机）送入输入井（磁盘）中存放， 等待进入内存时所处的状况。 （3） 执行状态即作业分配到所需的资源， 被调入内存， 并且在处理机（CPU）上执行相应的程序时所处的状况。 （4） 完成状态即作业完成了计算任务， 结果由打印机输出， 最后由系统回收分配给它的全部资源， 准备退出系

3、统时的作业状况。,3.2.2 作业调度 1. 作业控制块（JCB） 在多道批处理系统中通常有上百个作业被收容在输入井（磁盘）中。 为了管理和调度作业， 系统为每个作业设置了一个作业控制块（JCB）， 它记录该作业的有关信息。 不同系统的JCB的组成内容有所区别。 JCB的主要内容如图3-2所示。,图3-2 作业控制块,2. 作业调度的功能 如上所述， 作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转换。 具体来说， 通常作业调度程序要完成以下工作(这就是作业调度的功能)。 (1) 记录系统中各个作业的情况。 (2) 按照某种调度算法从后备作业队列中挑选作业。 (3)

4、为选中的作业分配内存和外设等资源。 (4) 为选中的作业建立相应的进程。,(5) 作业结束后进行善后处理工作， 如输出必要的信息， 收回该作业所占用的全部资源， 撤消与该作业相关的全部进程和该作业的JCB。,3.3 进 程 调 度,3.3.1 进程调度的功能和时机 进程只有在得到CPU之后才能真正活动起来。 一个就绪进程怎样获得CPU的控制权呢? 这是由进程调度实现的， 进程调度也被称为低级调度。 进程调度程序也往往被称为低级调度程序， 它完成进程状态从就绪态到运行态的转化。实际上， 进程调度程序主要是完成一台物理的CPU转变成多台虚拟（或逻辑）的CPU的工作。,1. 功能 进程调度的主要功能

5、是： (1) 保存现场。 （2） 挑选进程。 （3） 恢复现场。,2. 时机 在什么情况下执行进程调度呢? 一般是在以下事件发生后作进程调度： （1） 完成任务。 （2） 等待资源。 （3） 运行到时。 （4） 发现标志。 （5） 创建新进程。,图3-3 进程调度流程,3.3.2 两级调度模型 作业调度和进程调度是CPU主要的两级调度， 二者的关系可用图3-4表示。,图3-4 两级调度简化队列图,3.3.3 三级调度模型 当一个系统中三级调度同时存在时， 其相互间的关系如图3-5所示。 简单来说， 作业调度从后备作业中选择一批合适的作业放入内存， 并创建相应的进程； 进程调度从就绪队列中选择一

6、个合适进程， 令其投入运行； 中级调度将在内存中驻留时间较长的进程换到磁盘上： 从就绪队列转到就绪/挂起队列， 从阻塞队列转到阻塞/挂起队列。 当内存中有足够的可用空间时， 中级调度就从就绪/挂起队列中选择一些合适的进程放入内存， 使之进入就绪队列。,图3-5 三级调度简化队列,3.4 性能评价标准,(1) 所用算法应保证实现系统的设计目标。 (2) 对所有作业或进程应公平对待。 (3) 均衡使用资源， 尽量使系统中各种资源都同时得到利用。 (4) 兼顾响应时间和资源利用率。 (5) 基于相对优先级， 但避免无限延期。 (6) 系统开销不应太大。,3.4.2 性能评价标准 1. CPU利用率

7、CPU的利用率可从0100%。 2. 吞吐量 吞吐量表示单位时间内CPU完成作业（或进程）的数量。 3. 周转时间 从一个特定作业的观点出发， 最重要的标准就是完成这个作业要花费多长时间。,作业i的周转时间Ti为,其中， tsi表示作业i的提交时刻， tci表示作业i的完 成时刻。 系统中n个作业的平均周转时间T为,作业周转时间没有区分作业实际运行时间长短的特性， 因为长作业不可能具有比运行时间还短的周转时间。 为了合理反映长短作业的差别， 定义了另一个衡量标准带权周转时间W， 即W=T/R， 其中T为周转时间， R为实际运行时间。 平均带权周转时间W为,4. 就绪等待时间 CPU调度算法并不

8、真正影响作业执行或IO操作的时间数量。 各种CPU调度算法仅影响作业(进程)在就绪队列中所花费的时间数量。,5. 响应时间 在交互式系统中， 周转时间不可能是最好的评价标准。 一个进程往往可以很早地就产生某些输出， 当前面的结果在终端上输出时它可以继续计算新的结果。 于是， 有另一个评价标准， 就是从提交第一个请求到产生第一个响应所用的时间， 这就叫做响应时间。,3.5 常用调度算法,3.5.1 先来先服务（FCFS） 最简单的CPU调度算法就是先来先服务（First Come First Served）方法， 即按作业（进程）到来的先后次序进行调度。 这样， 在系统中等待时间最长的作业就优先

9、被调度， 而不管其所需运行时间的长短。 FCFS的性能很差。 考虑下面三个作业（如图3-6所示）， 对每个作业， 设已知其运行时间， 我们计算这三个作业的平均周转时间。,图3-6 三个作业,如果作业按1， 2， 3的顺序几乎同时到达， 那么采用FCFS方式的服务顺序也是123， 如图3-7所示。,图3-7 FCFS方式,作业1的周转时间是24； 作业2的周转时间是27； 作业3的周转时间是30， 平均周转时间是（24+27+30）/3=27。 然而， 若作业的到达顺序是2， 3， 1， 则服务顺序如图3-8所示。,图3-8 另一种作业运行顺序,3.5.2 短作业优先（SJF） CPU调度的另一

10、种方式是短作业优先（Shortest Job First)算法。 所谓作业的长短是指作业要求运行时间的多少。 当CPU可供使用时， SJF算法就把CPU分给最短的作业。 例如， 考虑如图3-9所示的一组作业（它们同时提交到系统）。,图3-9 同时到达的一组作业,利用短作业优先法调度， 作业执行的顺序如图3-10所示。其平均周转时间是13。,图3-10 SJF调度法,对于一组给定的作业来说， 短作业优先法给出最小的平均等待时间。 可以证明， 在这方面它是最佳的。 证明的办法是， 把一个短作业移到长作业之前所减少的短作业的等待时间大于增加的长作业等待时间。 相应地， 平均等待时间也减少了， 如图3

11、-11所示。,图3-11 SJF有最小平均等待时间,3.5.3 优先级（Priority） 短作业优先法是一般优先级调度算法的特例。 每个进程有一个优先级， CPU分给优先级最高的进程。 优先级相同的进程按FCFS调度。 短作业优先法是简化的优先级算法， 这里优先级（p）反比于估计的下一次CPU工作时间（）, p=1/。 CPU工作时间越长， 其优先级越低。,3.5.4 抢占式和非抢占式算法 SJF既可以为抢占式， 又可以为非抢占式。 当一个作业正在执行时， 一个新作业到来， 并进入就绪队列， 而新作业比当前正在执行的作业还短， 在此情况下， 就有两种不同的处理方式： 抢占式短作业优先算法强行

12、中止当前正在执行的作业， 调度新作业执行； 而非抢占式SJF将允许当前作业继续运行， 直到完成它的CPU运行工作。 抢占式短作业优先法也叫做最短剩余时间优先法（SRTF， Shortes Remaining Time First）。 作为例子， 考虑下面4个作业（如图3-12所示）。,图3-12 4个作业示例,如果这些作业按上面所示的时间进入就绪队列并需要指定的运行时间， 那么下面的示意图（如图3-13所示）就说明了最短剩余时间优先法调度的结果。,图3-13 SRTF法调度示例,表3-1 SRTF调度算法的性能,3.5.5 轮转法（RR） 轮转法（RR， Round Robin）主要是为分时系

13、统设计的。 一个极为重要的参数就是时间片， 它是一个小的时间单位， 不能取得过大或者过小， 通常为10100 ms数量级。 就绪队列可看成是一个环形队列， CPU调度程序轮流地把CPU分给就绪队列中的每个进程， 时间长度都是一个时间片。,图3-14 RR法q=1和q=4时进程运行的情况,由图3-14可以看出， 在轮转法中， 一次轮回时间内分给任何进程的CPU时间都不会大于一个时间片。 如果一个进程在一个时间片内没有做完自己的事情， 那么在时间片用完时， 该进程就被剥夺对CPU的控制权， 放回到就绪队列的末尾。 所以， 一个需运行较长时间的进程要经过多次轮转才能完成工作。 表3-2给出各进程的周

14、转时间和带权周转时间项等指标。,表3-2 RR调度算法的性能,时间片的长短通常由以下几个因素确定： （1） 系统的响应时间： 在进程数目一定时， 时间片的长短直接正比于系统对响应时间的要求； （2） 就绪队列进程的数目： 当系统要求的响应时间一定时， 时间片的大小反比于就绪队列中的进程数； （3） 进程的转换时间： 若进程的转换时间为t， 时间片为q， 为保证系统开销不大于某个标准， 应使比值t/q不大于某一数值， 如1/10； （4） CPU运行指令速度： CPU运行速度快， 则时间片可以短些； 反之， 则应取得长些。,3.5.6 多级队列法（MQ） 另一类调度算法是把多个进程分成不同级别的

15、组。 例如， 通常的划分方式是分为前台进程（交互）和后台进程（批处理）。 这两类进程的响应时间要求是完全不同的， 所以有不同的调度算法。 多级队列（MQ， Multilevel Queue）调度算法把就绪队列划分成几个单独的队列（如图3-15所示）。,图3-15 多级队列调度,下面是多级队列调度法的一个例子， 有如下5个队列： （1） 系统进程； （2） 交互进程； （3） 交互编辑进程； （4） 批处理进程； （5） 学生批处理进程。,3.5.7 多级反馈队列法（MFQ） 通常在多级队列法中， 进程是永久性地放到一个队列中的， 它们不能从一个队列移到另一个队列。 而多级反馈队列法（MFQ，

16、Multilevel Feedback Queue）允许进程在各队列间移动， 其基本思想是把具有不同CPU工作时间这一特性的进程区分开来。,图3-16 多级反馈队列,3.5.8 多级调度综合示例 在一个系统中会采用多级调度， 如作业调度和进程调度， 并且各采用不同的调度算法， 如作业调度可采用FCFS、 SJF、 SRTF等算法， 而进程调度可采用最高优先权优先法（HPF）、 RR、 MQ等算法。例如， 在一个有两道作业的批处理系统中， 作业调度采用短作业优先的调度算法， 进程调度采用抢占式优先级调度算法。 设有以下作业序列（如图3-17所示）。,图3-17 作业序列示例,其中， 给出的作业优先数即为相应进程的优先数。 其数值越小， 优先级越高。 在这种情况下， 每个作业从到达系统到完成要经历两级调度： 首先由作业调度程序根据其采用的算法和内存的实际情况， 挑选作业送入内存， 并建立相应进程； 然后由进程调度程序依据自己的调度算法从就绪队列中选出合适进程， 令其投入运行。 这4个作业（进程）的活动情况如图3-18所示。,图3-18 4个作业的活动