20141015操作系统第4章

第4章处理机调度4.1分级调度4.2作业调度4.3进程调度4.4调度算法4.5算法评价4.6实时系统调度方法本章小结习题衡量调度策略的最常用的几个指标是：周转时间:周转时间是指将一个作业提交给计算机系统后到该作业的结果返回给用户所需要的时间。吞吐率:吞吐率是指在给定的时间内，一个计算机系统所完成的总工作量。响应时间:响应时间则是指从用户向计算机发出一个命令到计算机把相应的执行结果返回给用户所需要的时间。设备利用率:设备利用率主要指输入输出设备的使用情况。图4.1作业的状态及其转换4.1分级调度4.1.1作业的状态及其转换(1)作业调度：又称宏观调度，或高级调度。(2)交换调度：又称中级调度。(3)进程调度：又称微观调度或低级调度。(4)线程调度。4.1.2调度的层次4.1.3作业与进程的关系1.作业可被看作是用户向计算机提交任务的任务实体，进程则是计算机为了完成用户任务实体而设置的执行实体，是系统分配资源的基本单位。2.一个作业总是由一个以上的多个进程组成的。3.作业的概念主要用在批处理系统中。而进程的概念则用在几乎所有的多道系统中4.2作业调度作业调度主要是完成作业从后备状态到执行状态的转变，以及从执行状态到完成状态的转变。4.2.1作业调度功能(1)记录系统中各作业的状况。系统通过JCB而感知作业的存在。作业名作业类型资源要求资源使用情况优先级(数)当前状态其他(2)从后备队列中挑选出一部分作业投入执行。作业调度程序根据选定的调度算法，从后备作业队列中挑选出若干作业去投入执行。(3)为被选中作业做好执行前的准备工作。作业调度程序为选中的作业建立相应的进程，并为这些进程分配它们所需要的系统资源.(4)在作业执行结束时做善后处理工作。图4.3作业调度中状态的转换过程4.2.2作业调度目标与性能衡量调度目标主要是以下4点：(1)对所有作业应该是公平合理的；(2)应使设备有高的利用率；(3)每天执行尽可能多的作业；(4)有快的响应时间。1.周转时间：作业i的周转时间Ti为Ti=Tei-Tsi其中Tei为作业i的完成时间，Tsi为作业的提交时间。对于被测定作业流所含有的n（n=1）个作业来说，其平均周转时间为：一个作业的周转时间说明了该作业在系统内停留的时间，包含两部分：等待时间；执行时间，即：Ti=Twi＋Tri这里，Twi主要指作业i由后备状态到执行状态的等待时间，它不包括作业进入执行状态后的等待时间。nii=11T=Tn2.带权周转时间作业的周转时间包含了两个部分，即等待时间和执行时间。带权周转时间是作业周转时间与作业执行时间的比：Wi=Ti/Tri对于被测定作业流所含有的几个作业来说，其平均带权周转时间为：nii=11W=Wn4.3.1进程调度的功能进程调度的具体功能可总结如下：(1)记录系统中所有进程的执行情况(2)选择占有处理机的进程(3)进行进程上下文切换4.3进程调度4.3.2进程调度的时机引起进程调度的原因有以下几类：(1)正在执行的进程执行完毕。(2)执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等待状态。(3)执行中进程调用了P原语操作，从而因资源不足而被阻塞；或调用了V原语操作激活了等待资源的进程队列。(4)执行中进程提出I／O请求后被阻塞。(5)在分时系统中时间片已经用完。(6)在执行完系统调用，在系统程序返回用户进程时，可认为系统进程执行完毕，从而可调度选择一新的用户进程执行。(7)就绪队列中的某进程的优先级变得高于当前执行进程的优先级，从而也将引发进程调度。4.3.3进程上下文切换进程上下文由正文段、数据段、硬件寄存器的内容以及有关数据结构等组成。进程上下文切换包括4个步骤：(1)决定是否做上下文切换以及是否允许做上下文切换。(2)保存当前执行进程的上下文。(3)使用进程调度算法，选择一个处于就绪状态进程。(4)恢复或装配所选进程的上下文，将CPU控制权交给所选进程。进程调度性能的衡量方法可分为定性和定量两种。定性衡量方面，调度的可靠性,简洁性进程调度的定量评价包括CPU的利用率评价、进程在就绪队列中的等待时间与执行时间之比等。实际上，由于进程进入就绪队列的随机模型很难确定，而且进程上下文切换等也将影响进程的执行效率，从而对进程调度进行解析是很困难的。一般情况下，大多利用模拟或测试系统响应时间的方法来评价进程调度的性能。4.3.4进程调度性能评价4.4调度算法进程调度算法:1.先来先服务（FCFS）调度算法2.轮转法（roundrobin）时间片长度的选择是根据系统对响应时间的要求R和就绪队列中所允许的最大进程数Nmax确定的。它可表示为：q=R/Nmax思考:时间片长度选取不当的影响?3.多级反馈轮转法思考:加入到就绪队列的进程有几种情况?如果对这些进程区别对待，给予不同的优先级和时间片,每个队列按FCFS原则排列，各队列之间的进程享有不同的优先级，但同一队列内优先级相同。不同进程进入不同的就绪队列。例如：线性优先级调度策略（selfishroundrobin）线性优先级调度策略采用如下方式，即新创建的进程按FCFS方式排成就绪队列，而其他已得到过时间片服务的进程也按FCFS方式排成另一个就绪队列或称享受服务队列(图4.5）。图4.5线性优先级调度新创建进程就绪队列优先级P以P=a*t(a0)的速率增加。享受服务队列中进程的优先级P以P=b*t(ab0)的速率增长。设某一进程在时刻t1时被创建，在时刻t时，该进程的优先级为P(t)=a*(t-t1)(t1tt1′)又设该进程在t1′时刻转入享受服务队列，则在时刻t，该进程的优先级变为P(t)=a*(t1′-t1)+b*(t-t1′)(t1′tt2′)那么，一个新创建进程等待多长时间之后进入享受服务队列较为合适呢？当新创建进程就绪队列中的头一个进程的优先级P(t)=a*(t-t1)与享受服务队列中最后一个就绪进程的优先级P(t)=b*t相等时，新创建进程队列中的头一个进程可以转入享受服务进程队列。其优先级变化曲线如图4.6。图4.6优先级变化曲线另外，当享受服务进程队列为空时，新创建进程队列的头一个进程也将移入享受服务进程队列。显然，在上述线性优先级调度法中，ab0的条件是必要的。否则，当ba0时，两个不同队列中的就绪态进程的优先级将永远不会相等，从而，在享受服务进程队列中永远只有一个进程。因此，上述线性优先级调度策略退回到FCFS方式。另外，如果ab=0，则线性优先级调度策略退回到轮转法调度方式。事实上，线性优先级调度策略是一种介于轮转法和FCFS方式之间的调度策略。4.优先级法系统或用户按某种原则为作业或进程指定一个优先级来表示该作业或进程所享有的调度优先权。静态优先级：(1)按进程的类型给予不同的优先级。(2)将作业的静态优先级作为它所属进程的优先级。动态优先级:(1)根据进程占有CPU时间的长短来决定。(2)根据就绪进程等待CPU的时间长短来决定。思考:多级反馈轮转法与优先级法在原理上的区别作业调度算法:1.先来先服务调度算法2.优先级法(1)由用户自己根据作业的紧急程度输入一个适当的优先级。(2)由系统或操作员根据作业类型指定优先级。(3)系统根据作业要求资源情况确定优先级。3.最短作业优先法（shortestjobfirst）4.最高响应比优先法（highestresponserationext）R=(W+T)/T=1+W/T其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。例1：在单道批处理系统中，有五个作业进入输入井的时间及需要执行的时间如下表所示，约定当这五个作业全部进入输入井后立即进行调度，忽略调度的时间开销。要求：写出分别采用先来先服务和最短执行时间优先调度算法时的调度次序和作业平均周转时间。作业号进入输入井时间需执行时间（分钟）开始执行时间结束执行时间周转时间（分钟）110：0040210：1030310：2020410：3025510：4010先来先服务：12345108分钟最短作业优先：5342181分钟例2：一个多道程序系统，有一个作业序列，作业的提交时间及运行时间在下表中所列，当第一个作业进入系统后开始调度，假定作业都是仅作计算。请列出在分别采用先来先服务算法和计算时间短的优先算法管理作业时各个作业的开始时间、完成时间和周转时间。注意:忽略系统开销。作业号到达输入井时刻需计算时间110：002小时210：101小时310：200.5小时410：300.2小时4.6实时系统调度方法4.6.1实时系统的特点根据对处理外部事件的时限要求，实时系统中处理的外部事件可分为硬实时任务和软实时任务。硬实时任务要求系统必须完全满足任务的时限要求。软实时任务则允许系统对任务的时限要求有一定的延迟，其时限要求只是一个相对条件。实时系统的另一个特点是它所处理的外部任务可分为周期性的与非周期性的两大类。对于非周期性任务来说，存在有一个完成或开始进行处理时限，而周期性任务只要求在周期T内完成或开始进行处理。一般来说，实时操作系统具有以下特点：(1)有限等待时间（决定性）(2)有限响应时间(3)用户控制(4)可靠性高(5)系统出错处理能力强实时系统要求所有的进程在处理事件时，都必须在有限时间内开始处理。这一特性又被称为实时系统的决定性特性。实时系统的有限响应时间特性是指从系统响应外部事件开始，必须在有限时间内处理完毕。实时系统要求很高的可靠性。实时操作系统具有下述能力：(1)很快的进程或线程切换速度(2)快速的外部中断响应能力(3)基于优先级的随时抢先式调度策略基于优先级的调度策略大致有以下4种。即：①优先级+时间片轮转调度策略；②基于优先级的非抢先式调度策略；③基于优先级的固定点抢先式调度策略；④基于优先级的随时抢先式调度策略。基于优先级的固定点抢先式调度方式与基于优先级的随时抢先式调度策略是实时系统的主要调度策略。4.6.2实时调度算法的分类4类实时调度算法：(1)静态表格驱动类静态表格驱动类的实时调度算法，对可能的调度条件和参数进行静态分析，并将分析结果作为实际调度结果。这类调度方法多用于调度处理周期性任务(2)静态优先级驱动抢先式调度算法类该类算法的静态分析不直接产生调度结果，而只用来指定任务的优先级。频(3)动态计划调度算法类动态计划调度算法在调度任务执行之前排出调度计划，并分析计划的调度结果是否使得任务所要求的处理时限得到满足。如果能够满足，则按调度计划执行，否则修改调度计划。(4)尽力而为调度算法类这一类算法不进行可能性分析，只对到达的事件和相关任务指定相应的优先级，并进行调度。尽力而为调度方式开销较小，实现容易。但是，该算法不一定满足用户要求的处理时限。4.6.3时限调度算法与频率单调调度算法时限调度算法是一种以满足用户要求的时限为调度原则的算法。在实时系统中的用户要求时限有两种，即处理开始时限和处理结束时限。时限调度算法可以使用任一种时限。时限调度算法不可用于周期性调度与非周期性调度两种。时限调度算法所需要的相关输入信息包括以下几种：(1)任务就绪时间或事件到达时间(2)开始时限(3)完成时限(4)处理时间(5)资源需求(6)时限调度算法的基本思想是：按用户的时限要求顺序设置优先级，优先级高者占据处理机，也就是说，时限调度是抢先式的。下面是用时限调度算法调度周期性实时任务的例子。设实时系统从两个不同的数据源DA和DＢ周期性地收集数据并进行处理，其中DA的时限要求以30ms为周期，DB的时限要求以75ms为周期。设DA所需处理时限为15ms，DB所需处理时限为38ms，则与DA和DB有关进程的事件发生时限（就绪时限），执行时限以及结束时限如图4.11所示。图4.11周期性任务的预计发生、执行与结束时限如果使用时限调度算法，并按最近结束时限优先级最高的方法进行排列，可以给出图4.11所示各进程的调度顺序和相对时间。（如图4.12）图4.12时限调度算法给出的调度顺序频率单调调度算法是一种被广泛用于多周期性实时处理的调度算法。频率单调调度算法的基本原理是频率越低（周期越