操作系统教程-Linux实例分析孟庆昌第3章处理机调度.ppt

《操作系统教程-Linux实例分析孟庆昌第3章处理机调度.ppt》由会员分享，可在线阅读，更多相关《操作系统教程-Linux实例分析孟庆昌第3章处理机调度.ppt（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.1 作业状态 如前所述，作业从提交

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

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

4、的信息，收回该作业所占用的全部资源，撤消与该作业相关的全部进程和该作业的JCB。,3.3 进 程 调 度,3.3.1 进程调度的功能和时机 进程只有在得到CPU之后才能真正活动起来。一个就绪进程怎样获得CPU的控制权呢?这是由进程调度实现的，进程调度也被称为低级调度。进程调度程序也往往被称为低级调度程序，它完成进程状态从就绪态到运行态的转化。实际上，进程调度程序主要是完成一台物理的CPU转变成多台虚拟（或逻辑）的CPU的工作。,1.功能 进程调度的主要功能是：(1)保存现场。（2）挑选进程。（3）恢复现场。,2.时机 在什么情况下执行进程调度呢?一般是在以下事件发生后作进程调度：（1）完成任务

5、。（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利用率 CPU的利用率可从0100%。2.吞吐量 吞吐量表示单位时间内CPU完成作业（或进程）的数量。3.周转时间 从一个特定作业的观点出发，最重要的标准就是完成这个作业要花费多长时间。,作业i的周转时间Ti为,其中，tsi表示作业i的提

7、交时刻，tci表示作业i的完成时刻。系统中n个作业的平均周转时间T为,作业周转时间没有区分作业实际运行时间长短的特性，因为长作业不可能具有比运行时间还短的周转时间。为了合理反映长短作业的差别，定义了另一个衡量标准带权周转时间W，即W=T/R，其中T为周转时间，R为实际运行时间。平均带权周转时间W为,4.就绪等待时间 CPU调度算法并不真正影响作业执行或IO操作的时间数量。各种CPU调度算法仅影响作业(进程)在就绪队列中所花费的时间数量。,5.响应时间 在交互式系统中，周转时间不可能是最好的评价标准。一个进程往往可以很早地就产生某些输出，当前面的结果在终端上输出时它可以继续计算新的结果。于是，有

8、另一个评价标准，就是从提交第一个请求到产生第一个响应所用的时间，这就叫做响应时间。,3.5 常用调度算法,3.5.1 先来先服务（FCFS）最简单的CPU调度算法就是先来先服务（First Come First Served）方法，即按作业（进程）到来的先后次序进行调度。这样，在系统中等待时间最长的作业就优先被调度，而不管其所需运行时间的长短。FCFS的性能很差。考虑下面三个作业（如图3-6所示），对每个作业，设已知其运行时间，我们计算这三个作业的平均周转时间。,图3-6 三个作业,如果作业按1，2，3的顺序几乎同时到达，那么采用FCFS方式的服务顺序也是123，如图3-7所示。,图3-7 F

9、CFS方式,作业1的周转时间是24；作业2的周转时间是27；作业3的周转时间是30，平均周转时间是（24+27+30）/3=27。然而，若作业的到达顺序是2，3，1，则服务顺序如图3-8所示。,图3-8 另一种作业运行顺序,3.5.2 短作业优先（SJF）CPU调度的另一种方式是短作业优先（Shortest Job First)算法。所谓作业的长短是指作业要求运行时间的多少。当CPU可供使用时，SJF算法就把CPU分给最短的作业。例如，考虑如图3-9所示的一组作业（它们同时提交到系统）。,图3-9 同时到达的一组作业,利用短作业优先法调度，作业执行的顺序如图3-10所示。其平均周转时间是13。

10、,图3-10 SJF调度法,对于一组给定的作业来说，短作业优先法给出最小的平均等待时间。可以证明，在这方面它是最佳的。证明的办法是，把一个短作业移到长作业之前所减少的短作业的等待时间大于增加的长作业等待时间。相应地，平均等待时间也减少了，如图3-11所示。,图3-11 SJF有最小平均等待时间,3.5.3 优先级（Priority）短作业优先法是一般优先级调度算法的特例。每个进程有一个优先级，CPU分给优先级最高的进程。优先级相同的进程按FCFS调度。短作业优先法是简化的优先级算法，这里优先级（p）反比于估计的下一次CPU工作时间（）,p=1/。CPU工作时间越长，其优先级越低。,3.5.4

11、抢占式和非抢占式算法 SJF既可以为抢占式，又可以为非抢占式。当一个作业正在执行时，一个新作业到来，并进入就绪队列，而新作业比当前正在执行的作业还短，在此情况下，就有两种不同的处理方式：抢占式短作业优先算法强行中止当前正在执行的作业，调度新作业执行；而非抢占式SJF将允许当前作业继续运行，直到完成它的CPU运行工作。抢占式短作业优先法也叫做最短剩余时间优先法（SRTF，Shortes Remaining Time First）。作为例子，考虑下面4个作业（如图3-12所示）。,图3-12 4个作业示例,如果这些作业按上面所示的时间进入就绪队列并需要指定的运行时间，那么下面的示意图（如图3-13

12、所示）就说明了最短剩余时间优先法调度的结果。,图3-13 SRTF法调度示例,表3-1 SRTF调度算法的性能,3.5.5 轮转法（RR）轮转法（RR，Round Robin）主要是为分时系统设计的。一个极为重要的参数就是时间片，它是一个小的时间单位，不能取得过大或者过小，通常为10100 ms数量级。就绪队列可看成是一个环形队列，CPU调度程序轮流地把CPU分给就绪队列中的每个进程，时间长度都是一个时间片。,图3-14 RR法q=1和q=4时进程运行的情况,由图3-14可以看出，在轮转法中，一次轮回时间内分给任何进程的CPU时间都不会大于一个时间片。如果一个进程在一个时间片内没有做完自己的事

13、情，那么在时间片用完时，该进程就被剥夺对CPU的控制权，放回到就绪队列的末尾。所以，一个需运行较长时间的进程要经过多次轮转才能完成工作。表3-2给出各进程的周转时间和带权周转时间项等指标。,表3-2 RR调度算法的性能,时间片的长短通常由以下几个因素确定：（1）系统的响应时间：在进程数目一定时，时间片的长短直接正比于系统对响应时间的要求；（2）就绪队列进程的数目：当系统要求的响应时间一定时，时间片的大小反比于就绪队列中的进程数；（3）进程的转换时间：若进程的转换时间为t，时间片为q，为保证系统开销不大于某个标准，应使比值t/q不大于某一数值，如1/10；（4）CPU运行指令速度：CPU运行速度

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

15、队列中的，它们不能从一个队列移到另一个队列。而多级反馈队列法（MFQ，Multilevel Feedback Queue）允许进程在各队列间移动，其基本思想是把具有不同CPU工作时间这一特性的进程区分开来。,图3-16 多级反馈队列,3.5.8 多级调度综合示例 在一个系统中会采用多级调度，如作业调度和进程调度，并且各采用不同的调度算法，如作业调度可采用FCFS、SJF、SRTF等算法，而进程调度可采用最高优先权优先法（HPF）、RR、MQ等算法。例如，在一个有两道作业的批处理系统中，作业调度采用短作业优先的调度算法，进程调度采用抢占式优先级调度算法。设有以下作业序列（如图3-17所示）。,图

16、3-17 作业序列示例,其中，给出的作业优先数即为相应进程的优先数。其数值越小，优先级越高。在这种情况下，每个作业从到达系统到完成要经历两级调度：首先由作业调度程序根据其采用的算法和内存的实际情况，挑选作业送入内存，并建立相应进程；然后由进程调度程序依据自己的调度算法从就绪队列中选出合适进程，令其投入运行。这4个作业（进程）的活动情况如图3-18所示。,图3-18 4个作业的活动过程,表3-3 4个作业活动的有关数据,3.6 Linux系统中的进程调度,3.6.1 进程调度 1.调度方式 Linux内核的调度方式基本上采用“抢占式优先级”方式，即当进程在用户模式下运行时，不管是否自愿，在一定条

17、件下（如时间片用完或等待I/O），核心就可以暂时剥夺其运行而调度其他进程进入运行。,Linux系统中进程分为实时进程和非实时进程，它们的优先级由不同方式确定：实时进程的优先级采用静态优先级，即由用户预先指定，以后不会改变；非实时进程的优先级采用动态优先级，它由调度程序计算出来。实时进程的静态优先级通常比非实时进程的动态优先级要高。Linux系统中的调度策略基本上继承了UNIX的以优先级为基础的调度。,2.调度策略 Linux系统针对不同类别的进程提供了三种不同的调度策略，即SCHED_FIFO、SCHED_RR以及SCHED_OTHER。,3.调度时机 核心进行进程调度的时机有以下5种情况：(

18、1)当前进程调用nanosleep()或者pause()，使自己进入睡眠状态，主动让出一段时间CPU的使用权。(2)进程终止，永久地放弃对CPU的使用。(3)在时钟中断处理程序执行过程中，发现当前进程连续运行的时间过长。,(4)当唤醒一个睡眠进程时，发现被唤醒的进程比当前进程更有资格运行。(5)一个进程通过执行系统调用来改变调度策略或者降低自身的优先权(如nice命令)，从而引起立即调度。,4.调度算法 进程调度的算法应该比较简单，以便减少频繁调度时的系统开销。Linux执行进程调度时，首先查找所有在就绪队列中的进程，从中选出优先级最高且在内存的一个进程。,3.6.2 shell基本工作原理

19、Linux系统提供给用户的最重要的系统程序是shell命令语言解释程序。它不属于内核部分，而是在核心之外以用户态方式运行。其基本功能是解释并执行用户键入的各种命令，实现用户与Linux核心的接口。系统初启后，核心为每个终端用户建立一个进程去执行shell解释程序。它的执行过程基本上按照如下步骤：,(1)读取用户由键盘输入的命令行。(2)分析命令，以命令名作为文件名，并将其他参数改造为系统调用execve()内部处理所要求的形式。(3)终端进程调用fork()建立一个子进程。(4)终端进程本身用系统调用wait4()来等待子进程完成(如果是后台命令，则不等待)。（5）如果命令末尾有&号（后台命令

20、符号），则终端进程不用执行系统调用wait4()，而是立即发提示符，让用户输入下一个命令，转步骤（1）。shell基本执行过程以及父子进程之间的关系如图3-19所示。,图3-19 shell命令执行过程,3.6.3 系统初启 1.硬件检测 当PC启动时，首先CPU进入实模式，开始执行ROM-BIOS起始位置的代码。2.加载引导程序 整个硬盘的第一个扇区是引导扇区，加电后从这个扇区“引导”，所以它称为“主引导记录块”MBR。MBR中会有磁盘分区的数据和一段简短的程序，共512字节。,引导扇区中的程序及其辅助程序（不包括LILO）采用汇编语言编写，共有三个：（1）bootsect.S，这是Linu

21、x引导扇区的源代码，汇编后不能超过512字节。（2）setup.S，这是辅助程序的一部分。（3）video.S，这是另一部分辅助程序，用于引导过程中的屏幕显示。,3.系统初始化 辅助程序setup为内核映像的执行作好了准备（包括解压缩）以后，就跳转到0 x100000开始执行内核本身，下面就是内核的初始化过程。初始化过程可以分为三个阶段。第一阶段主要是CPU本身的初始化，例如页式映射的建立；第二阶段主要是系统中一些基础设施的初始化，例如内存管理和进程管理的建立和初始化；最后是对上层部分初始化，如根设备的安装和外部设备的初始化等。,在初始化的第一阶段，首先设置内核页表，并启动页面映射机制。在第二

22、阶段调用函数start_kernel()，继续进行内核的初始化，甚至可以说这才真正开始内核初始化，这是在较高层次上的初始化。,在第三阶段，内核线程init首先锁定内核，然后调用过程来初始化外部设备及加载驱动程序（对外设的初始化包括PCI总线的初始化、网络初始化、一系列其他设备的初始化等）；创建第二个内核线程keventd，由它充当“代理人”角色，使得某些函数在它的上下文中执行；设置“初始化代码段”和“初始化调用段”等；初始化文件系统，并加载它。,4.用户登录 在用户态初始化阶段init程序在每个tty端口上创建一个进程，用来支持用户登录。每个进程都运行一个getty程序，它监测tty端口等待用

23、户使用。,习 题,1.处理机调度的主要目的是什么?2.高级调度与低级调度的主要功能是什么?为什么要引入中级调度?3.处理机调度一般可分为哪三级?其中哪一级调度必不可少?为什么?4.作业在其存在过程中分为哪四种状态?5.作业提交后是否马上放在内存中?为什么?,6.在OS中，引起进程调度的主要因素有哪些?7.作业调度与进程调度之间有什么差别?二者间如何协调工作?8.在确定调度方式和调度算法时，常用的评价准则有哪些?9.简述FCFS、RR和优先级调度算法的实现思想。10.假定在单CPU条件下有下列要执行的作业：,作业到来的时间是按作业编号顺序进行的(即后面作业依次比前一个作业迟到一个时间单位)。(1)用一个执行时间图描述在下列算法时各自执行这些作业的情况：FCFS、RR(时间片=1)和非抢占式优先级。(2)对于上述每种算法，各个作业的周转时间是多少?平均周转时间是多少?(3)对于上述每种算法，各个作业的带权周转时间是多少?平均带权周转时间是多少?,11.Linux系统中，进程调度的时机和算法是什么?对用户进程和核心进程如何调度?12.简述一条shell命令在Linux系统中的实现过程。13.针对3.5.8节中综合示例，如果进程调度采用非抢占式优先级方式，那么平均周转时间和平均带权周转时间各是多少？14.简述Linux系统初启的基本过程。,