2014.10.15操作系统第4章PPT课件

1、衡量调度策略的最常用的几个指标是：衡量调度策略的最常用的几个指标是：周转时间周转时间:周转时间是指将一个作业提交给计算机周转时间是指将一个作业提交给计算机系统后到该作业的结果返回给用户所需要的时间。系统后到该作业的结果返回给用户所需要的时间。吞吐率吞吐率:吞吐率是指在给定的时间内，一个计算机吞吐率是指在给定的时间内，一个计算机系统所完成的总工作量。系统所完成的总工作量。响应时间响应时间:响应时间则是指从用户向计算机发出一响应时间则是指从用户向计算机发出一个命令到计算机把相应的执行结果返回给用户所个命令到计算机把相应的执行结果返回给用户所需要的时间。需要的时间。设备利用率设备利用率:设备利用率主

2、要指输入输出设备的使设备利用率主要指输入输出设备的使用情况。用情况。第1页/共37页图图4.1 作业的状态及其转换作业的状态及其转换4.1 分 级 调 度4.1.1 作业的状态及其转换第2页/共37页(1) 作业调度：又称宏观调度，或高级调度。作业调度：又称宏观调度，或高级调度。 (2) 交换调度：又称中级调度。交换调度：又称中级调度。(3) 进程调度：又称微观调度或低级调度。进程调度：又称微观调度或低级调度。 (4) 线程调度。线程调度。4.1.2 调度的层次第3页/共37页4.1.3 作业与进程的关系作业与进程的关系1.作业可被看作是用户向计算机提交任务的任务作业可被看作是用户向计算机提交

3、任务的任务实体，进程则是计算机为了完成用户任务实体而实体，进程则是计算机为了完成用户任务实体而设置的执行实体，是系统分配资源的基本单位。设置的执行实体，是系统分配资源的基本单位。2.一个作业总是由一个以上的多个进程组成的。一个作业总是由一个以上的多个进程组成的。3.作业的概念主要用在批处理系统中。而进程的作业的概念主要用在批处理系统中。而进程的概念则用在几乎所有的多道系统中概念则用在几乎所有的多道系统中第4页/共37页4.2 作作 业业 调调 度度作业调度主要是完成作业从后备状态到执行状态作业调度主要是完成作业从后备状态到执行状态的转变，以及从执行状态到完成状态的转变。的转变，以及从执行状态到

4、完成状态的转变。4.2.1 作业调度功能作业调度功能(1) 记录系统中各作业的状况。记录系统中各作业的状况。 系统通过系统通过JCB而感知作业的存在。而感知作业的存在。作业名作业名作业类型作业类型资源要求资源要求资源使用情况资源使用情况优先级优先级(数数)当前状态当前状态其他其他第5页/共37页(2) 从后备队列中挑选出一部分作业投入执行。作从后备队列中挑选出一部分作业投入执行。作业调度程序根据选定的调度算法，从后备作业队业调度程序根据选定的调度算法，从后备作业队列中挑选出若干作业去投入执行。列中挑选出若干作业去投入执行。(3) 为被选中作业做好执行前的准备工作。作业调为被选中作业做好执行前的

5、准备工作。作业调度程序为选中的作业建立相应的进程，并为这些度程序为选中的作业建立相应的进程，并为这些进程分配它们所需要的系统资源进程分配它们所需要的系统资源.(4) 在作业执行结束时做善后处理工作。在作业执行结束时做善后处理工作。第6页/共37页图图4.3 作业调度中状态的转换过程作业调度中状态的转换过程第7页/共37页4.2.2 作业调度目标与性能衡量作业调度目标与性能衡量调度目标主要是以下调度目标主要是以下4点：点：(1) 对所有作业应该是公平合理的；对所有作业应该是公平合理的；(2) 应使设备有高的利用率；应使设备有高的利用率；(3) 每天执行尽可能多的作业；每天执行尽可能多的作业；(4

6、) 有快的响应时间。有快的响应时间。第8页/共37页1. 周转时间：周转时间：作业作业i的周转时间的周转时间Ti为为Ti=Tei-Tsi其中其中Tei为作业为作业i的完成时间，的完成时间，Tsi为作业的提交时间。为作业的提交时间。对于被测定作业流所含有的对于被测定作业流所含有的n（n=1）个作业来）个作业来说，其平均周转时间为：说，其平均周转时间为：一个作业的周转时间说明了该作业在系统内停留一个作业的周转时间说明了该作业在系统内停留的时间，包含两部分：等待时间；执行时间，即：的时间，包含两部分：等待时间；执行时间，即：Ti=TwiTri这里，这里，Twi主要指作业主要指作业i由后备状态到执行状

7、态的等由后备状态到执行状态的等待时间，它不包括作业进入执行状态后的等待时待时间，它不包括作业进入执行状态后的等待时间。间。nii = 11T =Tn第9页/共37页2. 带权周转时间带权周转时间作业的周转时间包含了两个部分，即等待时间和作业的周转时间包含了两个部分，即等待时间和执行时间。带权周转时间是作业周转时间与作业执行时间。带权周转时间是作业周转时间与作业执行时间的比：执行时间的比：Wi=Ti/Tri对于被测定作业流所含有的几个作业来说，其平对于被测定作业流所含有的几个作业来说，其平均带权周转时间为：均带权周转时间为：nii= 11W =Wn第10页/共37页4.3.1 进程调度的功能进程

8、调度的功能进程调度的具体功能可总结如下：进程调度的具体功能可总结如下：(1) 记录系统中所有进程的执行情况记录系统中所有进程的执行情况(2) 选择占有处理机的进程选择占有处理机的进程(3) 进行进程上下文切换进行进程上下文切换4.3 进 程 调 度第11页/共37页4.3.2 进程调度的时机进程调度的时机引起进程调度的原因有以下几类：引起进程调度的原因有以下几类：正在执行的进程执行完毕。正在执行的进程执行完毕。 (2) 执行中进程自己调用阻塞原语将自己阻塞起来进入睡执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等待状态。眠等待状态。(3) 执行中进程调用了执行中进程调用了P原语操作，从而因资

9、源不足而被阻原语操作，从而因资源不足而被阻塞；或调用了塞；或调用了V原语操作激活了等待资源的进程队列。原语操作激活了等待资源的进程队列。(4) 执行中进程提出执行中进程提出IO请求后被阻塞。请求后被阻塞。(5) 在分时系统中时间片已经用完。在分时系统中时间片已经用完。(6) 在执行完系统调用，在系统程序返回用户进程时，可在执行完系统调用，在系统程序返回用户进程时，可认为系统进程执行完毕，从而可调度选择一新的用户认为系统进程执行完毕，从而可调度选择一新的用户进程执行。进程执行。(7) 就绪队列中的某进程的优先级变得高于当前执行进程就绪队列中的某进程的优先级变得高于当前执行进程的优先级，从而也将引

10、发进程调度。的优先级，从而也将引发进程调度。第12页/共37页4.3.3 进程上下文切换进程上下文切换进程上下文由正文段、数据段、硬件寄存器的内进程上下文由正文段、数据段、硬件寄存器的内容以及有关数据结构等组成。容以及有关数据结构等组成。进程上下文切换包括进程上下文切换包括4个步骤：个步骤：(1) 决定是否做上下文切换以及是否允许做上下文决定是否做上下文切换以及是否允许做上下文切换。切换。(2) 保存当前执行进程的上下文。保存当前执行进程的上下文。 (3) 使用进程调度算法，选择一个处于就绪状态进使用进程调度算法，选择一个处于就绪状态进程。程。(4) 恢复或装配所选进程的上下文，将恢复或装配所

11、选进程的上下文，将CPU控制权控制权交给所选进程。交给所选进程。第13页/共37页进程调度性能的衡量方法可分为定性和定量两种。进程调度性能的衡量方法可分为定性和定量两种。定性衡量方面，调度的可靠性定性衡量方面，调度的可靠性,简洁性简洁性进程调度的定量评价包括进程调度的定量评价包括CPU的利用率评价、进程的利用率评价、进程在就绪队列中的等待时间与执行时间之比等。实在就绪队列中的等待时间与执行时间之比等。实际上，由于进程进入就绪队列的随机模型很难确际上，由于进程进入就绪队列的随机模型很难确定，而且进程上下文切换等也将影响进程的执行定，而且进程上下文切换等也将影响进程的执行效率，从而对进程调度进行解

12、析是很困难的。一效率，从而对进程调度进行解析是很困难的。一般情况下，大多利用模拟或测试系统响应时间的般情况下，大多利用模拟或测试系统响应时间的方法来评价进程调度的性能。方法来评价进程调度的性能。4.3.4 进程调度性能评价第14页/共37页4.4 调调 度度 算算 法法进程调度算法进程调度算法:先来先服务（先来先服务（FCFS）调度算法调度算法2. 轮转法（轮转法（round robin）时间片长度的选择是根据系统对响应时间的要求时间片长度的选择是根据系统对响应时间的要求R和就绪队列中所允许的最大进程数和就绪队列中所允许的最大进程数Nmax确定确定的。它可表示为：的。它可表示为： q=R/Nm

13、ax思考思考:时间片长度选取不当的影响时间片长度选取不当的影响?第15页/共37页3. 多级反馈轮转法多级反馈轮转法思考思考:加入到就绪队列的进程有几种情况加入到就绪队列的进程有几种情况?如果对这些进程区别对待，给予不同的优先级和如果对这些进程区别对待，给予不同的优先级和时间片时间片,每个队列按每个队列按FCFS原则排列，各队列之间原则排列，各队列之间的进程享有不同的优先级，但同一队列内优先级的进程享有不同的优先级，但同一队列内优先级相同。不同进程进入不同的就绪队列。相同。不同进程进入不同的就绪队列。例如：线性优先级调度策略（例如：线性优先级调度策略（selfish round robin）线

14、性优先级调度策略采用如下方式，即新创建的线性优先级调度策略采用如下方式，即新创建的进程按进程按FCFS方式排成就绪队列，而其他已得到方式排成就绪队列，而其他已得到过时间片服务的进程也按过时间片服务的进程也按FCFS方式排成另一个方式排成另一个就绪队列或称享受服务队列就绪队列或称享受服务队列(图）。图）。第16页/共37页图图4.5 线性优先级调度线性优先级调度新创建进程就绪队列优先级新创建进程就绪队列优先级P以以P=a*t (a0)的速的速率增加。率增加。享受服务队列中进程的优先级享受服务队列中进程的优先级P以以 P=b*t (ab0) 的速率增长。设某一进程在时刻的速率增长。设某一进程在时刻

15、t1时时被创建，在时刻被创建，在时刻t时，该进程的优先级为时，该进程的优先级为P(t)=a*(t-t1) (t1tt1)第17页/共37页又设该进程在又设该进程在t1时刻转入享受服务队列，则在时时刻转入享受服务队列，则在时刻刻t，该进程的优先级变为，该进程的优先级变为P(t)=a*(t1-t1)+b*(t-t1) (t1tb0 的条的条件是必要的。否则，当件是必要的。否则，当ba0 时，两个不同队时，两个不同队列中的就绪态进程的优先级将永远不会相等，从列中的就绪态进程的优先级将永远不会相等，从而，在享受服务进程队列中永远只有一个进程。而，在享受服务进程队列中永远只有一个进程。因此，上述线性优先

16、级调度策略退回到因此，上述线性优先级调度策略退回到FCFS方方式。另外，如果式。另外，如果ab=0，则线性优先级调度策略，则线性优先级调度策略退回到轮转法调度方式。事实上，线性优先级调退回到轮转法调度方式。事实上，线性优先级调度策略是一种介于轮转法和度策略是一种介于轮转法和FCFS方式之间的调方式之间的调度策略。度策略。第20页/共37页4. 优先级法优先级法系统或用户按某种原则为作业或进程指定一个优系统或用户按某种原则为作业或进程指定一个优先级来表示该作业或进程所享有的调度优先权。先级来表示该作业或进程所享有的调度优先权。静态优先级：静态优先级：按进程的类型给予不同的优先级。按进程的类型给予

17、不同的优先级。(2) 将作业的静态优先级作为它所属进程的优先级。将作业的静态优先级作为它所属进程的优先级。动态优先级动态优先级:(1) 根据进程占有根据进程占有CPU时间的长短来决定。时间的长短来决定。 (2) 根据就绪进程等待根据就绪进程等待CPU的时间长短来决定。的时间长短来决定。思考思考:多级反馈轮转法与优先级法在原理上的区别多级反馈轮转法与优先级法在原理上的区别第21页/共37页作业调度算法作业调度算法:1.先来先服务调度算法先来先服务调度算法2.优先级法优先级法(1) 由用户自己根据作业的紧急程度输入一个适当由用户自己根据作业的紧急程度输入一个适当的优先级。的优先级。(2) 由系统或

18、操作员根据作业类型指定优先级。由系统或操作员根据作业类型指定优先级。(3) 系统根据作业要求资源情况确定优先级。系统根据作业要求资源情况确定优先级。3. 最短作业优先法（最短作业优先法（shortest job first）4. 最高响应比优先法（最高响应比优先法（highest responseratio next）R=(W+T)/T=1+W/T其中其中T为该作业估计需要的执行时间，为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时为作业在后备状态队列中的等待时间。间。第22页/共37页例例1：在单道批处理系统中，有五个作业进入输入井的时间及需要执行：在单道批处理系统中，有五个作业

19、进入输入井的时间及需要执行的时间如下表所示，约定当这五个作业全部进入输入井后立即进行调的时间如下表所示，约定当这五个作业全部进入输入井后立即进行调度，忽略调度的时间开销。要求：写出分别采用先来先服务和最短执度，忽略调度的时间开销。要求：写出分别采用先来先服务和最短执行时间优先调度算法时的调度次序和作业平均周转时间。行时间优先调度算法时的调度次序和作业平均周转时间。作业号作业号进入输进入输入井时入井时间间需执行需执行时间时间（分钟）（分钟）开始执开始执行时间行时间结束执结束执行时间行时间周转时周转时间（分间（分钟）钟）110：0040210：1030310：2020410：3025510：401

20、0先来先服务：12345 108分钟最短作业优先：53421 81分钟第23页/共37页例例2：一个多道程序系统，有一个作业序列，作业的提：一个多道程序系统，有一个作业序列，作业的提交时间及运行时间在下表中所列，当第一个作业进入交时间及运行时间在下表中所列，当第一个作业进入系统后开始调度，假定作业都是仅作计算。请列出在系统后开始调度，假定作业都是仅作计算。请列出在分别采用先来先服务算法和计算时间短的优先算法管分别采用先来先服务算法和计算时间短的优先算法管理作业时各个作业的开始时间、完成时间和周转时间。理作业时各个作业的开始时间、完成时间和周转时间。注意注意:忽略系统开销。忽略系统开销。作业号作

21、业号到达输入井时刻到达输入井时刻需计算时间需计算时间110：002小时小时210：101小时小时310：200.5小时小时410：300.2小时小时第24页/共37页4.6 实时系统调度方法实时系统调度方法4.6.1 实时系统的特点实时系统的特点根据对处理外部事件的时限要求，实时系统中处根据对处理外部事件的时限要求，实时系统中处理的外部事件可分为理的外部事件可分为硬实时任务和软实时任务硬实时任务和软实时任务。硬实时任务要求系统必须完全满足任务的时限要硬实时任务要求系统必须完全满足任务的时限要求。软实时任务则允许系统对任务的时限要求有求。软实时任务则允许系统对任务的时限要求有一定的延迟，其时限要

22、求只是一个相对条件。一定的延迟，其时限要求只是一个相对条件。实时系统的另一个特点是它所处理的外部任务可实时系统的另一个特点是它所处理的外部任务可分为分为周期性的与非周期性周期性的与非周期性的两大类。对于非周期的两大类。对于非周期性任务来说，存在有一个完成或开始进行处理时性任务来说，存在有一个完成或开始进行处理时限，而周期性任务只要求在周期限，而周期性任务只要求在周期T内完成或开始内完成或开始进行处理。进行处理。第25页/共37页一般来说，实时操作系统具有以下特点：一般来说，实时操作系统具有以下特点：(1) 有限等待时间（决定性）有限等待时间（决定性）(2) 有限响应时间有限响应时间(3) 用户

23、控制用户控制(4) 可靠性高可靠性高(5) 系统出错处理能力强系统出错处理能力强实时系统要求所有的进程在处理事件时，都必须实时系统要求所有的进程在处理事件时，都必须在有限时间内开始处理。这一特性又被称为实时在有限时间内开始处理。这一特性又被称为实时系统的系统的决定性特性决定性特性。实时系统的实时系统的有限响应时间特性有限响应时间特性是指从系统响应外是指从系统响应外部事件开始，必须在有限时间内处理完毕。部事件开始，必须在有限时间内处理完毕。第26页/共37页实时系统要求很高的实时系统要求很高的可靠性可靠性。实时操作系统具有下述能力：实时操作系统具有下述能力：(1) 很快的进程或线程切换速度很快的

24、进程或线程切换速度(2) 快速的外部中断响应能力快速的外部中断响应能力(3) 基于优先级的随时抢先式调度策略基于优先级的随时抢先式调度策略基于优先级的调度策略大致有以下基于优先级的调度策略大致有以下4种。即：种。即： 优先级优先级+时间片轮转调度策略；时间片轮转调度策略； 基于优先级的非抢先式调度策略；基于优先级的非抢先式调度策略； 基于优先级的固定点抢先式调度策略；基于优先级的固定点抢先式调度策略； 基于优先级的随时抢先式调度策略。基于优先级的随时抢先式调度策略。基于优先级的固定点抢先式调度方式与基于优先基于优先级的固定点抢先式调度方式与基于优先级的随时抢先式调度策略是实时系统的主要调度级的

25、随时抢先式调度策略是实时系统的主要调度策略。策略。第27页/共37页4.6.2 实时调度算法的分类实时调度算法的分类4类实时调度算法：类实时调度算法：(1) 静态表格驱动类静态表格驱动类静态表格驱动类的实时调度算法，对可能的调度条件和参数进行静态静态表格驱动类的实时调度算法，对可能的调度条件和参数进行静态分析，并将分析结果作为实际调度结果。这类调度方法多用于调度分析，并将分析结果作为实际调度结果。这类调度方法多用于调度处理周期性任务处理周期性任务(2) 静态优先级驱动抢先式调度算法类静态优先级驱动抢先式调度算法类该类算法的静态分析不直接产生调度结果，而只用来指定任务的优先该类算法的静态分析不直

26、接产生调度结果，而只用来指定任务的优先级。频率单调调度算法就是一种静态优先级驱动的抢先式调度算法。级。频率单调调度算法就是一种静态优先级驱动的抢先式调度算法。(3) 动态计划调度算法类动态计划调度算法类动态计划调度算法在调度任务执行之前排出调度计划，并分析计划的动态计划调度算法在调度任务执行之前排出调度计划，并分析计划的调度结果是否使得任务所要求的处理时限得到满足。如果能够满足，调度结果是否使得任务所要求的处理时限得到满足。如果能够满足，则按调度计划执行，否则修改调度计划。则按调度计划执行，否则修改调度计划。(4) 尽力而为调度算法类尽力而为调度算法类这一类算法不进行可能性分析，只对到达的事件

27、和相关任务指定相应这一类算法不进行可能性分析，只对到达的事件和相关任务指定相应的优先级，并进行调度。尽力而为调度方式开销较小，实现容易。的优先级，并进行调度。尽力而为调度方式开销较小，实现容易。但是，该算法不一定满足用户要求的处理时限。但是，该算法不一定满足用户要求的处理时限。第28页/共37页4.6.3 时限调度算法与频率单调调度算法时限调度算法与频率单调调度算法时限调度算法是一种以满足用户要求的时限为调时限调度算法是一种以满足用户要求的时限为调度原则的算法。在实时系统中的用户要求时限度原则的算法。在实时系统中的用户要求时限有两种，即处理开始时限和处理结束时限。时有两种，即处理开始时限和处理

28、结束时限。时限调度算法可以使用任一种时限。时限调度算限调度算法可以使用任一种时限。时限调度算法不可用于周期性调度与非周期性调度两种。法不可用于周期性调度与非周期性调度两种。时限调度算法所需要的相关输入信息包括以下几时限调度算法所需要的相关输入信息包括以下几种：种：任务就绪时间或事件到达时间任务就绪时间或事件到达时间(2) 开始时限开始时限(3) 完成时限完成时限(4) 处理时间处理时间(5) 资源需求资源需求(6) 优先级优先级第29页/共37页时限调度算法的基本思想是：按用户的时限要求时限调度算法的基本思想是：按用户的时限要求顺序设置优先级，优先级高者占据处理机，也就顺序设置优先级，优先级高

29、者占据处理机，也就是说，时限要求最近的任务优先占有处理机。是说，时限要求最近的任务优先占有处理机。时限调度是抢先式的。下面是用时限调度算法调时限调度是抢先式的。下面是用时限调度算法调度周期性实时任务的例子。度周期性实时任务的例子。设实时系统从两个不同的数据源设实时系统从两个不同的数据源DA和和D周期性周期性地收集数据并进行处理，其中地收集数据并进行处理，其中DA的时限要求以的时限要求以30 ms为周期，为周期，DB的时限要求以的时限要求以75 ms为周期。为周期。设设DA所需处理时限为所需处理时限为15 ms，DB所需处理时限所需处理时限为为38 ms，则与，则与DA和和DB有关进程的事件发生

30、时有关进程的事件发生时限（就绪时限），执行时限以及结束时限如图所限（就绪时限），执行时限以及结束时限如图所示。示。第30页/共37页图图4.11 周期性任务的预计发生、执行与结束时限周期性任务的预计发生、执行与结束时限第31页/共37页如果使用时限调度算法，并按最近结束时限优先如果使用时限调度算法，并按最近结束时限优先级最高的方法进行排列，可以给出图所示各进程级最高的方法进行排列，可以给出图所示各进程的调度顺序和相对时间。（如图）的调度顺序和相对时间。（如图）图图4.12 时限调度算法给出的调度顺序时限调度算法给出的调度顺序第32页/共37页频率单调调度算法是一种被广泛用于多周期性实频率单调调度算法是一种被广泛用于多周期性实时处理的调度算法。