1、第第4 4章章 处理机调度处理机调度 4.1 分级调度分级调度 4.2 作业调度作业调度 4.3 进程调度进程调度 4.4 调度算法调度算法 4.5 算法评价算法评价 4.6 实时系统调度方法实时系统调度方法第第4 4章章 处理机调度处理机调度 CPUCPU是计算机系统中一个十分重要的资源是计算机系统中一个十分重要的资源 不同的不同的CPUCPU管理方法将为用户提供不同性能的操作管理方法将为用户提供不同性能的操作系统系统 操作系统的要求不同，处理机管理的策略也是不操作系统的要求不同，处理机管理的策略也是不同的同的本章以本章以CPUCPU管理为核心，讨论管理、控制用户进程执管理为核心，讨论管理、
2、控制用户进程执行的方法。行的方法。包括：包括：作业与进程的关系；作业和进程的调度策作业与进程的关系；作业和进程的调度策略与算法；几种调度策略的评价略与算法；几种调度策略的评价概述概述第第4 4章章 处理机调度处理机调度衡量调度策略的常用指标：衡量调度策略的常用指标：周转时间周转时间：将一个作业提交给计算机系统后到：将一个作业提交给计算机系统后到该作业的结果返回给用户所需要的时间该作业的结果返回给用户所需要的时间 吞吐率吞吐率：在给定的时间内，一个计算机系统所：在给定的时间内，一个计算机系统所完成的总工作量完成的总工作量 响应时间响应时间：从用户向计算机发出一个命令到计：从用户向计算机发出一个命
3、令到计算机把相应的执行结果返回给用户所需的时间算机把相应的执行结果返回给用户所需的时间 设备利用率设备利用率：输入输出设备的使用情况：输入输出设备的使用情况第第4 4章章 处理机调度处理机调度4.1 4.1 分级调度分级调度 4.1.1 4.1.1 作业的状态及其转换作业的状态及其转换 4.1.2 4.1.2 调度的层次调度的层次 4.1.3 4.1.3 作业与进程的关系作业与进程的关系第第4 4章章 处理机调度处理机调度4.1.1 4.1.1 作业的状态及其转换作业的状态及其转换作业的基本概念作业的基本概念（1 1）作业作业 用户在一次计算过程中，或者一次事务处理过程用户在一次计算过程中，或
4、者一次事务处理过程中，要求计算机系统所做工作的总称中，要求计算机系统所做工作的总称（2 2）作业步作业步 一个作业可划分成若干部分，称为一个作业步一个作业可划分成若干部分，称为一个作业步第第4 4章章 处理机调度处理机调度4.1.1 4.1.1 作业的状态及其转换作业的状态及其转换 一个作业从用户提交开始到真正占有处理机而一个作业从用户提交开始到真正占有处理机而被执行，要由系统经过多级调度才能实现，作业被执行，要由系统经过多级调度才能实现，作业处理的过程处理的过程一般都要经历提交、收容、执行和完一般都要经历提交、收容、执行和完成等成等4 4个状态：个状态：提交提交：一个作业在其处于从设备进入外
5、部存储：一个作业在其处于从设备进入外部存储设备的过程称为提交状态设备的过程称为提交状态 收容收容：也称为后备状态，一个作业的全部信息：也称为后备状态，一个作业的全部信息都被输入进外存，在它还未被调度去执行之前，都被输入进外存，在它还未被调度去执行之前，该作业处于收容状态该作业处于收容状态第第4 4章章 处理机调度处理机调度执行执行：作业调度程序从后备作业中选取若干个作作业调度程序从后备作业中选取若干个作业到内存投入运行。它为被选中作业建立进程并业到内存投入运行。它为被选中作业建立进程并分配必要的资源，这时这些被选中的作业处于执分配必要的资源，这时这些被选中的作业处于执行状态。行状态。完成完成：
6、当作业运行完毕，但它所占有的资源尚未当作业运行完毕，但它所占有的资源尚未全部被系统回收时，该作业处于完成状态全部被系统回收时，该作业处于完成状态4.1.1 4.1.1 作业的状态及其转换作业的状态及其转换图图4.1 4.1 作业的状态及其转换图作业的状态及其转换图第第4 4章章 处理机调度处理机调度作业和进程的状态转换图作业和进程的状态转换图第第4 4章章 处理机调度处理机调度4.1.24.1.2调度的层次调度的层次 处理机调度策略处理机调度策略(处理机的分配处理机的分配)对整个计对整个计算机系统的综合性能指标有重要影响算机系统的综合性能指标有重要影响 处理机调度的描述处理机调度的描述 先要进
7、行作业调度，选择后备作业为其分先要进行作业调度，选择后备作业为其分 配资源创建进程，作业中的进程再进行竞争配资源创建进程，作业中的进程再进行竞争第第4 4章章 处理机调度处理机调度4.1.24.1.2调度的层次调度的层次一般处理机调度分为四级：一般处理机调度分为四级：作业调度作业调度 交换调度交换调度 进程调度进程调度 线程调度线程调度第第4 4章章 处理机调度处理机调度 作业调度（宏观调度或高级调度）作业调度（宏观调度或高级调度）按一定的原则对外存上的大量后备按一定的原则对外存上的大量后备作业进行选择，给选出的作业分配内存作业进行选择，给选出的作业分配内存等必要的资源，并建立相应的进程。另等
8、必要的资源，并建立相应的进程。另外当作业执行完毕时，还负责回收系统外当作业执行完毕时，还负责回收系统资源资源4.1.24.1.2调度的层次调度的层次第第4 4章章 处理机调度处理机调度 交换调度（中级调度）交换调度（中级调度）按给定的原则和策略，将处于外存按给定的原则和策略，将处于外存交换区中的就绪状态或就绪等待状态的交换区中的就绪状态或就绪等待状态的进程调入内存，或把处于内容就绪状态进程调入内存，或把处于内容就绪状态或内存等待状态的进程交换到外存或内存等待状态的进程交换到外存 主要涉及到内存管理与扩充，也归主要涉及到内存管理与扩充，也归入内存管理部分入内存管理部分4.1.24.1.2调度的层
9、次调度的层次第第4 4章章 处理机调度处理机调度 进程调度（微观调度或低级调度）进程调度（微观调度或低级调度）按某种策略和方法选取一个处于按某种策略和方法选取一个处于就绪状态的进程占用处理机就绪状态的进程占用处理机4.1.24.1.2调度的层次调度的层次第第4 4章章 处理机调度处理机调度 线程调度线程调度 按某种策略和方法选取一个处于就绪按某种策略和方法选取一个处于就绪状态的线程占用处理机状态的线程占用处理机4.1.24.1.2调度的层次调度的层次第第4 4章章 处理机调度处理机调度 在多道批处理系统中存在在多道批处理系统中存在作业作业调度和进程调度调度和进程调度 在分时系统和实时系统中，一
10、在分时系统和实时系统中，一般不存在作业调度而只有般不存在作业调度而只有进程调进程调度、交换调度和线程调度度、交换调度和线程调度4.1.24.1.2调度的层次调度的层次第第4 4章章 处理机调度处理机调度4.1.4.1.3 3 作业作业与与进程的关系进程的关系作业作业看作是用户向计算机提交任务的任务实体，看作是用户向计算机提交任务的任务实体，如一次计算机一个控制过程等如一次计算机一个控制过程等进程进程是计算机为了完成用户任务实体而设置的执是计算机为了完成用户任务实体而设置的执行实体，是系统分配资源的基本单位行实体，是系统分配资源的基本单位 计算机要完成一个任务实体，必须要有一计算机要完成一个任务
11、实体，必须要有一个以上的执行实体。一个作业总是由一个以上个以上的执行实体。一个作业总是由一个以上的多个进程组成的多个进程组成第第4 4章章 处理机调度处理机调度 作业如何分解为进程：作业如何分解为进程：系统必须为一个作业创建一个根进程，系统必须为一个作业创建一个根进程，根据任务要求，系统或根进程为其创建根据任务要求，系统或根进程为其创建相应的子进程，相应的子进程，为各子进程分配资源和调度各子进程执为各子进程分配资源和调度各子进程执行以完成作业要求的任务行以完成作业要求的任务4.1.4.1.3 3 作业作业与与进程的关系进程的关系第第4 4章章 处理机调度处理机调度4.2 4.2 作业调度作业调
12、度 4.2.1 4.2.1 作业调度功能作业调度功能 4.2.2 4.2.2 作业调度目标与性能衡量作业调度目标与性能衡量第第4 4章章 处理机调度处理机调度4.2.1 4.2.1 作业调度功能作业调度功能 作业调度主要是完成作业从后备到执作业调度主要是完成作业从后备到执行状态的转变，以及从执行到完成状态行状态的转变，以及从执行到完成状态的转变，做四方面的工作：的转变，做四方面的工作：(1)(1)记录系统中各作业的状况记录系统中各作业的状况(2)(2)从后备队列中挑选出一部分作业投从后备队列中挑选出一部分作业投入执行入执行(3)(3)为被选中作业作好执行前的准备工作为被选中作业作好执行前的准备
13、工作(4)(4)在作业执行结束时做善后处理在作业执行结束时做善后处理第第4 4章章 处理机调度处理机调度(1)(1)记录系统中各作业的状况记录系统中各作业的状况 作业调度程序要能挑出一个作业投入作业调度程序要能挑出一个作业投入执行，并且在执行过程中对其进行管理，执行，并且在执行过程中对其进行管理，它就必须掌握作业的各个状态和信息。它就必须掌握作业的各个状态和信息。系统为每个作业建立一个作业控制块系统为每个作业建立一个作业控制块JCBJCB记录有关信息，系统通过记录有关信息，系统通过JCBJCB而感知、而感知、调度和管理作业调度和管理作业4.2.1 4.2.1 作业调度功能作业调度功能第第4 4
14、章章 处理机调度处理机调度1.作业说明书作业说明书表达用户对作业的控制意图表达用户对作业的控制意图内容：内容：作业的基本描述作业的基本描述作业控制描述作业控制描述资源要求描述资源要求描述4.2.1 4.2.1 作业调度功能作业调度功能第第4 4章章 处理机调度处理机调度2.2.作业控制块（作业控制块（JCB)JCB)作业控制块是批作业控制块是批处理作业存在的标志处理作业存在的标志 保存有系统对于保存有系统对于作业进行管理所需要作业进行管理所需要的全部信息的全部信息4.2.1 4.2.1 作业调度功能作业调度功能作业名作业名作业类型作业类型资源要求资源要求资源使用情况资源使用情况优先级优先级(数
15、数)当前状态当前状态其他其他图图4.2 4.2 作业控制块作业控制块JCBJCB第第4 4章章 处理机调度处理机调度3 3、作业控制块的建立、作业控制块的建立 当作业开始由输入设备向磁盘传当作业开始由输入设备向磁盘传输时，系统输入程序为其建立一个作输时，系统输入程序为其建立一个作业控制块，并进行初始化业控制块，并进行初始化 初始化的大部分信息取自作业说初始化的大部分信息取自作业说明书明书 4.2.1 4.2.1 作业调度功能作业调度功能第第4 4章章 处理机调度处理机调度4 4、作业控制块的撤消、作业控制块的撤消作业完成后，其作业控制块由系统作业完成后，其作业控制块由系统撤消撤消 作业控制块被
16、撤消后其作业也不复作业控制块被撤消后其作业也不复存在存在4.2.1 4.2.1 作业调度功能作业调度功能第第4 4章章 处理机调度处理机调度 从后备队列中挑选出一部分作业投入执行从后备队列中挑选出一部分作业投入执行 系统中处于后备状态的作业较多，但是处系统中处于后备状态的作业较多，但是处于执行状态的作业一般只有有限的几个。作于执行状态的作业一般只有有限的几个。作业调度程序根据选定的调度算法，从后备作业调度程序根据选定的调度算法，从后备作业队列中挑选出若干作业去投入执行业队列中挑选出若干作业去投入执行4.2.1 4.2.1 作业调度功能作业调度功能第第4 4章章 处理机调度处理机调度 为被选中作
17、业作好执行前的准备工作为被选中作业作好执行前的准备工作 为选中的作业建立相应的进程，并为这为选中的作业建立相应的进程，并为这些进程分配它们所需要的系统资源，如些进程分配它们所需要的系统资源，如分配内存、外存、外设等。分配内存、外存、外设等。4.2.1 4.2.1 作业调度功能作业调度功能第第4 4章章 处理机调度处理机调度 在作业执行结束时做善后处理在作业执行结束时做善后处理 输出作业管理信息，如输出执行时输出作业管理信息，如输出执行时间等，回收该作业所占用的资源，撤销间等，回收该作业所占用的资源，撤销与该作业有关的全部进行和该作业的与该作业有关的全部进行和该作业的JCBJCB4.2.1 4.
18、2.1 作业调度功能作业调度功能第第4 4章章 处理机调度处理机调度第第4 4章章 处理机调度处理机调度4.2.2 4.2.2 作业调度目标与性能衡量作业调度目标与性能衡量 作业调度中最主要的是从后备作业调度中最主要的是从后备作业队列中选取一批作业进行执行作业队列中选取一批作业进行执行状态，根据不同的目标，将会有不状态，根据不同的目标，将会有不同的调度算法同的调度算法第第4 4章章 处理机调度处理机调度作业调度的目标：作业调度的目标：对所有作业应该是公平合理的对所有作业应该是公平合理的 应使设备有较高的利用率应使设备有较高的利用率 执行尽可能多的作业执行尽可能多的作业 响应时间快响应时间快4.
19、2.2 4.2.2 作业调度目标与性能衡量作业调度目标与性能衡量第第4 4章章 处理机调度处理机调度 任一调度算法要想同时满足上述任一调度算法要想同时满足上述目标是不可能的目标是不可能的 例如例如要想执行尽可能多的作业，调度要想执行尽可能多的作业，调度算法就应该选择那些估计执行时间短的算法就应该选择那些估计执行时间短的作业，但这样作的话对那些估计执行时作业，但这样作的话对那些估计执行时间长的作业又是不公平的，它们的响应间长的作业又是不公平的，它们的响应就会变的非常慢就会变的非常慢4.2.2 4.2.2 作业调度目标与性能衡量作业调度目标与性能衡量第第4 4章章 处理机调度处理机调度 如果考虑的
20、因素过多，调度算如果考虑的因素过多，调度算法就会变的非常复杂，这样系统开销法就会变的非常复杂，这样系统开销就会增加。因此大多就会增加。因此大多OSOS都有各自的目都有各自的目标实现作业调度算法标实现作业调度算法衡量一个作业调度算法优劣的标准衡量一个作业调度算法优劣的标准（批处理系统）：（批处理系统）：作业的平均周转时间或平均带权周转时间作业的平均周转时间或平均带权周转时间4.2.2 4.2.2 作业调度目标与性能衡量作业调度目标与性能衡量第第4 4章章 处理机调度处理机调度1.1.周转时间周转时间T Ti i：作业作业i i的周转时间的周转时间T Ti i：T Ti iT TeieiT Tsi
21、si T Teiei为作业为作业i i的完成时间，的完成时间，T Tsisi为作业的提交时间为作业的提交时间 含有含有n n个作业的作业流，个作业的作业流，平均周转时间平均周转时间为为 T T n1niiT14.2.2 4.2.2 作业调度目标与性能衡量作业调度目标与性能衡量第第4 4章章 处理机调度处理机调度 一个作业的周转时间说明了该作业一个作业的周转时间说明了该作业在系统内停留的时间，包含两部分：等在系统内停留的时间，包含两部分：等待时间和执行时间。待时间和执行时间。T Ti i=T TwiwiT Triri 等待时间等待时间T Twiwi：由后备状态到执行：由后备状态到执行状态的等待时
22、间状态的等待时间 4.2.2 4.2.2 作业调度目标与性能衡量作业调度目标与性能衡量第第4 4章章 处理机调度处理机调度2.2.带权周转时间带权周转时间W Wi i：是作业周转时间与作业执行时间的比是作业周转时间与作业执行时间的比 W Wi i 平均带权周转时间：平均带权周转时间：riiTT4.2.2 4.2.2 作业调度目标与性能衡量作业调度目标与性能衡量nii=11W=Wn第第4 4章章 处理机调度处理机调度4.3 4.3 进程调度进程调度 4.3.1 4.3.1 进程调度功能进程调度功能 4.3.2 4.3.2 进程调度的时机进程调度的时机 4.3.3 4.3.3 进程上下文切换进程上
23、下文切换 4.3.4 4.3.4 进程调度性能评价进程调度性能评价第第4 4章章 处理机调度处理机调度 用户进程和系统进程都要使用用户进程和系统进程都要使用处理机，因此进程调度程序应该按处理机，因此进程调度程序应该按照一定的策略动态地把处理机分配照一定的策略动态地把处理机分配给处于就绪队列中的某一个进程，给处于就绪队列中的某一个进程，使之执行使之执行4.3 4.3 进程调度进程调度第第4 4章章 处理机调度处理机调度4.3.1 4.3.1 进程调度功能进程调度功能进程调度的具体功能如下：进程调度的具体功能如下：(1)(1)记录系统中所有进程的执行情况记录系统中所有进程的执行情况(2)(2)选择
24、占有处理机的进程选择占有处理机的进程(3)(3)进行进程上下文切换进行进程上下文切换第第4 4章章 处理机调度处理机调度4.3.1 4.3.1 进程调度功能进程调度功能 1.1.记录系统中所有进程的执行情况记录系统中所有进程的执行情况 进程管理模块的准备工作。进程管理模块的准备工作。进程调度模块通过进程调度模块通过PCBPCB变化来掌握系统变化来掌握系统中所有进程的执行情况和状态特征，并在中所有进程的执行情况和状态特征，并在适当的时机从就绪队列中选择出一个进程适当的时机从就绪队列中选择出一个进程占据处理机。占据处理机。第第4 4章章 处理机调度处理机调度 2.选择占有处理机的进程选择占有处理机
25、的进程 按照一定的策略选择一个处于就绪状按照一定的策略选择一个处于就绪状态的进程，使其获得处理机执行态的进程，使其获得处理机执行。例如系统开销较少的例如系统开销较少的静态优先数调度法静态优先数调度法，适合于分时系统的适合于分时系统的轮转法和多级反馈轮转法轮转法和多级反馈轮转法等。等。这些选择策略决定了调度算法的性能。这些选择策略决定了调度算法的性能。4.3.1 4.3.1 进程调度功能进程调度功能第第4 4章章 处理机调度处理机调度3.3.进行进程上下文切换进行进程上下文切换 当正在执行的进程由于某种原因要当正在执行的进程由于某种原因要让出处理机时，系统要做进程上下文切让出处理机时，系统要做进
26、程上下文切换，以使得另一个进程得以执行。换，以使得另一个进程得以执行。4.3.1 4.3.1 进程调度功能进程调度功能第第4 4章章 处理机调度处理机调度4.3.2 4.3.2 进程调度的时机进程调度的时机1.1.正在执行的进程执行完毕正在执行的进程执行完毕2.2.执行中进程自己调用阻塞原语将自己执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等待状态阻塞起来进入睡眠等待状态3.3.执行中进程调用了执行中进程调用了P P原语操作，因为原语操作，因为资源不足而被阻塞；或用资源不足而被阻塞；或用V V原语激活原语激活了等待资源的进程队列了等待资源的进程队列 进程调度发生的时机与引起进程调度的进程调
27、度发生的时机与引起进程调度的原因以及进程调度的方式有关。原因以及进程调度的方式有关。引起进程调度的原因有以下几类引起进程调度的原因有以下几类：第第4 4章章 处理机调度处理机调度4.4.执行中进程提出了执行中进程提出了I/OI/O请求后被阻塞请求后被阻塞5.5.在分时系统中时间片已经用完在分时系统中时间片已经用完6.6.在执行完系统调用，返回用户进程时在执行完系统调用，返回用户进程时 对于对于CPUCPU执行方式可剥夺：执行方式可剥夺：7.7.就绪队列中的某进程的优先级高于当前就绪队列中的某进程的优先级高于当前执行进程的优先级执行进程的优先级4.3.2 4.3.2 进程调度的时机进程调度的时机
28、第第4 4章章 处理机调度处理机调度4.3.4.3.3 3 进程上下文切换进程上下文切换进程上下文切换包括进程上下文切换包括4 4个步骤：个步骤：1.1.决定是否做上下文切换以及是否决定是否做上下文切换以及是否允许作上下文切换允许作上下文切换 包括对进程调度原因的检查分析，包括对进程调度原因的检查分析，以及当前执行进程的资格和以及当前执行进程的资格和CPUCPU执行方式执行方式的检查等的检查等第第4 4章章 处理机调度处理机调度进程上下文切换步骤进程上下文切换步骤2 2：2.2.保存当前执行进程的上下文保存当前执行进程的上下文 要求：上下文切换程序不能破坏要求：上下文切换程序不能破坏“老老”进
29、程的上下文结构进程的上下文结构4.3.4.3.3 3 进程上下文切换进程上下文切换第第4 4章章 处理机调度处理机调度进程上下文切换步骤进程上下文切换步骤3 3：3.3.使用进程调度算法，选择一个处于使用进程调度算法，选择一个处于就绪状态的进程占用处理机就绪状态的进程占用处理机4.3.4.3.3 3 进程上下文切换进程上下文切换第第4 4章章 处理机调度处理机调度进程上下文切换步骤进程上下文切换步骤4 4：4.4.恢复或装配所选进程的上下文，恢复或装配所选进程的上下文，将将CPUCPU控制权交给所选进程控制权交给所选进程4.3.4.3.3 3 进程上下文切换进程上下文切换第第4 4章章 处理机
30、调度处理机调度4.3.4.3.4 4 进程进程调度性能评价调度性能评价 进程调度的优劣直接影响作业进程调度的优劣直接影响作业调度的性能，进程调度性能的衡量调度的性能，进程调度性能的衡量方法分为定形和定量两种方法分为定形和定量两种第第4 4章章 处理机调度处理机调度定形：定形：调度的可靠性，如进程调度是否引调度的可靠性，如进程调度是否引起数据结构的破坏起数据结构的破坏 简洁性，如果调度程序过于烦琐和简洁性，如果调度程序过于烦琐和复杂，将会耗去较大的系统开销，复杂，将会耗去较大的系统开销，并会使得响应时间增加并会使得响应时间增加4.3.4.3.4 4 进程进程调度性能评价调度性能评价第第4 4章章
31、 处理机调度处理机调度定量：定量：CPUCPU的利用率评价的利用率评价 进程在就绪队列中的等待时间与执行进程在就绪队列中的等待时间与执行时间之比时间之比 对于实际系统实现困难，一般采对于实际系统实现困难，一般采用模拟或测试系统响应时间的方法来用模拟或测试系统响应时间的方法来评价进程调度的性能评价进程调度的性能4.3.4.3.4 4 进程进程调度性能评价调度性能评价第第4 4章章 处理机调度处理机调度 在操作系统中要设计一个理想的调度算在操作系统中要设计一个理想的调度算法是十分困难的。法是十分困难的。设计设计调度算法时应考虑的因素：调度算法时应考虑的因素：调度算法应与系统设计目标保持一致调度算法
32、应与系统设计目标保持一致注意系统资源均衡使用注意系统资源均衡使用保证提交的作业在截止时间内完成保证提交的作业在截止时间内完成设法缩短作业平均周转时间设法缩短作业平均周转时间大多数操作系统都采用比较简单的调度算法大多数操作系统都采用比较简单的调度算法4.4 4.4 调度算法调度算法第第4 4章章 处理机调度处理机调度4.4 4.4 调度算法调度算法 显然，不同的的系统和系统目标，显然，不同的的系统和系统目标，通常采用不同的调度算法，目前存在着通常采用不同的调度算法，目前存在着多种调度算法，有的适用于作业调度；多种调度算法，有的适用于作业调度；有的适用于进程调度；也有的算法二者有的适用于进程调度；
33、也有的算法二者都适用都适用第第4 4章章 处理机调度处理机调度1.1.先来先服务（先来先服务（FCFSFCFS）调度算法）调度算法 是一种最简单的调度算法是一种最简单的调度算法 作业调度：每次调度是从后备作业队列作业调度：每次调度是从后备作业队列中选择一个最先进入该队列的作业中选择一个最先进入该队列的作业 进程调度：从就绪进程队列中选择一个进程调度：从就绪进程队列中选择一个最先进入该队列的进程最先进入该队列的进程4.4 4.4 调度算法调度算法第第4 4章章 处理机调度处理机调度u FCFSFCFS调度算法分析调度算法分析 实现简单，有利于执行时间长的作业实现简单，有利于执行时间长的作业/进程
34、，不利用短作业进程，不利用短作业/进程（在执行时进程（在执行时间长的作业间长的作业/进程之后到达，将等待很长进程之后到达，将等待很长的时间，带权周转时间大）的时间，带权周转时间大）在实际的在实际的OSOS中，很少单独适用中，很少单独适用FCFSFCFS，一般和其他算法配合起来使用。一般和其他算法配合起来使用。4.4 4.4 调度算法调度算法第第4 4章章 处理机调度处理机调度2.2.轮转法（轮转法（RRRound RobinRRRound Robin）算法思想：轮转法的基本概念是将算法思想：轮转法的基本概念是将CPUCPU的处理的处理时间分成固定大小的时间片。如果一个进程在时间分成固定大小的时
35、间片。如果一个进程在被调度选中之后用完了系统规定的时间片，但被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有未完成要求的任务，则它自行释放自己所占有的的CPUCPU而排到就绪队列的末尾，等待下一次调而排到就绪队列的末尾，等待下一次调度。同时，进程调度程序又去调度当前就绪队度。同时，进程调度程序又去调度当前就绪队列中的第一个进程。列中的第一个进程。4.4 4.4 调度算法调度算法第第4 4章章 处理机调度处理机调度4.4 4.4 调度算法调度算法2.2.轮转法轮转法第第4 4章章 处理机调度处理机调度 轮转法中时间片大小的关键性：轮转法中时间片大小的关键性：影响到
36、系统的开销和响应时间影响到系统的开销和响应时间 过短则剥夺处理机的次数增多，切换过短则剥夺处理机的次数增多，切换次数增加，加重系统开销次数增加，加重系统开销 过长，长到都能在时间片内执行完成，过长，长到都能在时间片内执行完成，则退化为则退化为FCFSFCFS算法算法2.2.轮转法轮转法第第4 4章章 处理机调度处理机调度时间片大小的确定应该考虑以下因素时间片大小的确定应该考虑以下因素 1.1.系统对响应时间的要求系统对响应时间的要求 2.2.就绪队列中的进程数目就绪队列中的进程数目 它可表示为：它可表示为：q=R/q=R/NmaxNmax 实际可行的办法：实际可行的办法：当一轮调度开始时，当一
37、轮调度开始时，系统根据就绪队列中的数目计算一次系统根据就绪队列中的数目计算一次q q2.2.轮转法轮转法第第4 4章章 处理机调度处理机调度3.3.多级反馈轮转法（多级反馈轮转法（Round Robin with Round Robin with Multiple FeedbackMultiple Feedback）算法思想：由于在轮转法中加入就绪队列的进程算法思想：由于在轮转法中加入就绪队列的进程情况不同，因此如果对这些进程区别对待可情况不同，因此如果对这些进程区别对待可以进一步改善系统效率。以进一步改善系统效率。方法如下：方法如下：1.1.设置多个就绪队列，为各个队列赋予不同的优设置多个就
38、绪队列，为各个队列赋予不同的优先权，第一队列最高，逐个降低先权，第一队列最高，逐个降低2.2.赋予各个队列中时间片的大小也不同，优先权赋予各个队列中时间片的大小也不同，优先权越高，时间片越小越高，时间片越小4.4 4.4 调度算法调度算法第第4 4章章 处理机调度处理机调度3.3.一个新进程进入内存后，先放入第一队列一个新进程进入内存后，先放入第一队列的末尾，按的末尾，按FCFSFCFS排队等待，当执行时如排队等待，当执行时如果能在该时间片内完成，便撤离系统；果能在该时间片内完成，便撤离系统；如未完成，将其放入第二队列末尾，再如未完成，将其放入第二队列末尾，再等待；如果在第二队列中运行一个时间
39、等待；如果在第二队列中运行一个时间片仍未完成则放入第三队列，依此类推，片仍未完成则放入第三队列，依此类推，到到n n3.多级反馈轮转法多级反馈轮转法第第4 4章章 处理机调度处理机调度4.4.仅当第一队列空闲时，才调度第二队仅当第一队列空闲时，才调度第二队列，列，如果第如果第i i队列中为某进程正占用处队列中为某进程正占用处理机，又有新进程进入优先级较高的队列，理机，又有新进程进入优先级较高的队列，则此时新进程将抢占处理机则此时新进程将抢占处理机3.多级反馈轮转法多级反馈轮转法第第4 4章章 处理机调度处理机调度就绪队列1就绪队列2就绪队列3就绪队列nS1S2S3至CPU至CPU至CPU至CP
40、U(时间片：S1 S2 S3)3.多级反馈轮转法多级反馈轮转法第第4 4章章 处理机调度处理机调度算法评价：算法评价：具有较好的性能，较好的满足各具有较好的性能，较好的满足各种类型用户的需要，是一种目前公认种类型用户的需要，是一种目前公认的较好的进程调度算法。的较好的进程调度算法。3.多级反馈轮转法多级反馈轮转法第第4 4章章 处理机调度处理机调度4.4.优先级法优先级法 系统将从就绪队列中选择一个优先级最高系统将从就绪队列中选择一个优先级最高的作业的作业/进程分配处理机：进程分配处理机：1.1.非抢占式优先级算法非抢占式优先级算法 2.2.抢占式优先级算法抢占式优先级算法4.4 4.4 调度
41、算法调度算法第第4 4章章 处理机调度处理机调度1.1.非抢占式优先级算法非抢占式优先级算法 优先级高的进程在得到处理机后一直执行优先级高的进程在得到处理机后一直执行下去，直至完成或自己放弃处理机时，系统下去，直至完成或自己放弃处理机时，系统才可将处理机分为给另一个优先级高的进程。才可将处理机分为给另一个优先级高的进程。主要用于批处理和某些实时性要求不高主要用于批处理和某些实时性要求不高的系统中的系统中 4.4.优先级法优先级法第第4 4章章 处理机调度处理机调度 2.2.抢占式优先级算法抢占式优先级算法 优先权高的进程在得到处理机后执行，优先权高的进程在得到处理机后执行，一旦出现了一个优先级
42、更高的进程时，系统一旦出现了一个优先级更高的进程时，系统就停止当前进程的执行，将处理机分配给优就停止当前进程的执行，将处理机分配给优先级更高的进程先级更高的进程 能更好的满足紧迫作业的要求，用于实能更好的满足紧迫作业的要求，用于实时性要求高的系统中时性要求高的系统中4.4.优先级法优先级法第第4 4章章 处理机调度处理机调度进程或作业优先级的确定方法：进程或作业优先级的确定方法：1.1.静态法静态法：在作业或进程开始执行前就确定其：在作业或进程开始执行前就确定其优先级，在其运行期间保持不变优先级，在其运行期间保持不变2.2.动态法：动态法：随着作业或进程的执行过程，其优随着作业或进程的执行过程
43、，其优先级不断变化，以获得更好的调度性能先级不断变化，以获得更好的调度性能优先级是用一定范围内的整数来表示：优先级是用一定范围内的整数来表示：0 07 7；0 0255255等，但各个系统的用法不同等，但各个系统的用法不同4.4.优先级法优先级法第第4 4章章 处理机调度处理机调度1.1.静态法确定进程或作业的优先级的依据：静态法确定进程或作业的优先级的依据：进程或作业类型进程或作业类型 进程或作业对资源的需求进程或作业对资源的需求 用户的要求用户的要求 简单易行，系统开销小，但不够精确简单易行，系统开销小，但不够精确4.4.优先级法优先级法第第4 4章章 处理机调度处理机调度2.2.动态法确
44、定进程或作业的优先级的依据：动态法确定进程或作业的优先级的依据：进程或作业占有进程或作业占有CPUCPU时间的长短（占有时间的长短（占有处理机时间越长，再次获得调度的优先级处理机时间越长，再次获得调度的优先级就越低）就越低）进程或作业等待进程或作业等待CPUCPU的时间长短（等待的时间长短（等待时间越长，优先级越高）时间越长，优先级越高）系统开销大系统开销大4.4.优先级法优先级法第第4 4章章 处理机调度处理机调度4.4.优先级法优先级法举例：举例：线性优先级调度策略（线性优先级调度策略（ssrssr）第第4 4章章 处理机调度处理机调度5.5.最短作业优先法最短作业优先法（Shortest
45、 Job FirstShortest Job First）算法思想：选择那些估计需要执行时间最算法思想：选择那些估计需要执行时间最短的作业占用处理机。短的作业占用处理机。算法分析：使得系统在同一时间内处理的算法分析：使得系统在同一时间内处理的作业个数最多，吞吐量大，但是有可能使得那作业个数最多，吞吐量大，但是有可能使得那些长作业永远得不到处理机执行的机会。些长作业永远得不到处理机执行的机会。4.4 4.4 调度算法调度算法第第4 4章章 处理机调度处理机调度6.6.最高响应比优先法最高响应比优先法(HRN)(HRN)HRN HRN是对是对FCFSFCFS和和SJFSJF方式的一种综合平衡方式的
46、一种综合平衡由于：由于：FCFSFCFS只考虑等待时间未考虑执行时间的长短只考虑等待时间未考虑执行时间的长短 SJFSJF只考虑执行时间未考虑等待时间只考虑执行时间未考虑等待时间HRNHRN同时考虑二者，从中选出响应比最高的作业投同时考虑二者，从中选出响应比最高的作业投入执行。入执行。4.4 4.4 调度算法调度算法第第4 4章章 处理机调度处理机调度6.6.最高响应比优先法（最高响应比优先法（HRNHRN）响应比响应比R R（W+TW+T）/T=1+W/T/T=1+W/T 其中其中T T为该作业估计需要的执行时间，为该作业估计需要的执行时间，W W为作为作业在后备状态队列中的等待时间。业在后
47、备状态队列中的等待时间。长作业随着它等待时间的增加，长作业随着它等待时间的增加，W/TW/T也也会增加，有机会获得会增加，有机会获得CPUCPU处理时间处理时间4.4 4.4 调度算法调度算法第第4 4章章 处理机调度处理机调度 本节主要利用解析技术从数学上分析本节主要利用解析技术从数学上分析几种主要调度方法的性能。几种主要调度方法的性能。详细过程请参考课本详细过程请参考课本93页页98页页4.5 4.5 算法评价算法评价第第4 4章章 处理机调度处理机调度 假设在单道批处理环境下有四个作业，假设在单道批处理环境下有四个作业，已知它们进入系统的时间、估计运行时已知它们进入系统的时间、估计运行时
48、间间 应用应用先来先服务先来先服务、最短作业优先最短作业优先和和最最高响应比优先高响应比优先作业调度算法，分别作业调度算法，分别计算计算出作业的平均周转时间和带权的平均周出作业的平均周转时间和带权的平均周转时间转时间4.5 4.5 算法评价算法评价第第4 4章章 处理机调度处理机调度第第4 4章章 处理机调度处理机调度先来先服务调度算法计算结果先来先服务调度算法计算结果第第4 4章章 处理机调度处理机调度最短作业优先作业算法计算结果最短作业优先作业算法计算结果第第4 4章章 处理机调度处理机调度最高响应比优先作业算法计算结果最高响应比优先作业算法计算结果第第4 4章章 处理机调度处理机调度4.
49、6 4.6 实时系统调度方法实时系统调度方法4.6.1 4.6.1 实时系统的特点实时系统的特点4.6.2 4.6.2 实时调度算法的分类实时调度算法的分类4.3.3 4.3.3 时限调度算法与频率时限调度算法与频率单调调度算法单调调度算法第第4 4章章 处理机调度处理机调度4.6.1 4.6.1 实时系统的特点实时系统的特点根据对处理外部事件的时限根据对处理外部事件的时限(deadlines)(deadlines)要要求，实时系统的外部事件可分为求，实时系统的外部事件可分为 硬实时任务硬实时任务hard real time taskhard real time task 要求系统必须满足任务
50、的时限要求要求系统必须满足任务的时限要求 软实时任务软实时任务sofesofe real time task real time task 允许系统对任务的时限要求有一定的延允许系统对任务的时限要求有一定的延迟迟第第4 4章章 处理机调度处理机调度 随着移动通信和网络计算技术的发展，随着移动通信和网络计算技术的发展，实时系统越来越重要实时系统越来越重要 ，具有以下特点，具有以下特点 有限等待时间有限等待时间 有限响应时间有限响应时间 用户控制用户控制 可靠性高可靠性高 系统出错处理能力强系统出错处理能力强4.6.1 4.6.1 实时系统的特点实时系统的特点第第4 4章章 处理机调度处理机调度
