第4章处理机调度.ppt

《第4章处理机调度.ppt》由会员分享，可在线阅读，更多相关《第4章处理机调度.ppt（48页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第4章处理机调度 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望4.1.1 调度的层次从处理机调度的对象、时间、功能等不同角度，我们可从处理机调度的对象、时间、功能等不同角度，我们可把处理机调度分成不同层次。把处理机调度分成不同层次。处理机调度的层次2作业调度：作业调度：又称为“宏观调度”、“高级调度”。从用户工作流程的角度，一次提交的若干个流程，其中每个程序按照进程调度。时间上通常是分钟、小时或天。内外存交换调度：内外存交换调度：又称为“中级调度”。从存储器资源

2、的角度。将进程的部分或全部换出到外存上，将当前所需部分换入到内存。指令和数据必须在内存里才能被CPU直接访问。进程调度：进程调度：又称为“微观调度”、“低级调度”。从CPU资源的角度，执行的单位。时间上通常是毫秒。因为执行频繁，要求在实现时达到高效率。调度层次3作业调度作业调度功能记录系统中各作业的状况从后备队列中挑选出一部分作业投入执行在作业执行结束时作善后处理工作作业调度主要是完成作业从后备状态到执行状态作业调度主要是完成作业从后备状态到执行状态的转变，以及从执行状态到完成状态的转变。的转变，以及从执行状态到完成状态的转变。4作业调度时机一个作业完成后有新作业提交处理器利用率较低作业调度程

3、序检查系统是否满足作业的资作业调度程序检查系统是否满足作业的资源要求，并按一定算法选取作业。也称为宏观源要求，并按一定算法选取作业。也称为宏观/高级调度。高级调度。5进程调度在一般的多任务和多用户的系统中，用户的进程数一般都大于处理器数，这必将导致用户进程争夺处理器。操作系统本身的进程也同样需要使用处理器。6进程调度（续）功能：功能：调度程序(dispatcher)记录记录所有进程的运行状况（静态和动态）选择选择适当的进程分派CPU时间完成上下文切换切换进程调度的时机：进程调度的时机：当进程出让CPU或调度程序剥夺执行状态进程占用的CPU进程执行完毕执行中进程自己调用阻塞原语将自己阻塞执行中进

4、程由于I/O资源而阻塞或唤醒时间片用完高优先级进程就绪或唤醒(可剥夺方式)7 进程调度分类进程调度分类从调度方式上看，进程调度有两种类型：一种是非抢占式调度，另一种是抢占式调度。1.非抢占调度 可能引起当前进程主动放弃处理机控制权的情况有两个:l进程运行完毕退出或遇到不可挽回的故障。l运行受阻。82.2.抢占调度抢占调度 剥夺调度也称作剥夺调度，主要指的是，在系统正常运转期间，如果某种事件出现，系统将迫使正在运行的进程停下来，将CPU控制权交给其它进程。抢占调度的思想源自对高紧迫度作业的响应，优优先先级级是多道程序系统中进程紧迫度的具体体现。当一个紧迫性较高的进程到来，要求在限定的时间内做出响

5、应，管理程序应及时停止正在运行的程序。将控制权交给紧迫性较高的进程。当紧迫性较高的进程有阻塞转为就绪（所等待的操作完成），管理程序立即停止低优先级进程的运行，让高优先级进程立即恢复运行。管理程序要做的工作:比较当前进程与新到来的进程的优先级，如果确认需要剥夺时，将当前进程由运行状态转入就绪状态，然后，将控制权交给紧迫性高的进程。此外，采用时间片轮转或短进程优先原则调度时也归此类。94.1.2调度的分类调度的分类 l批处理调度 l分时调度 l实时调度10调度算法的公共目标对各作业公平、合理，使用户满意：执行时间长短、等待时间等充分利用资源：CPU忙、I/O设备忙将各种类型的作业合理搭配起来进行调

6、度4.2调度算法的设计目标和性能准则调度算法的设计目标和性能准则11批处理系统：吞吐量、周转时间、CPU利用率分时调度：响应时间、均衡性实时调度：时限要求12性能指标：1平均周转时间平均周转时间T越小，系统吞吐量就越大。T的计算公式为：其中：n为单位时间内的作业数量。tfi为作业i的完成时间。tbi为作业的开始时间。132.平均带权周转时间这一准则主要是针对批处理系统的。为了描述系统对短小作业的优惠程度，可使用作业的平均带权周转时间W作为评价参数。W的计算公式为:其中：tsi为作业i的服务时间（也就是运行时间）。W越小，说明系统对短小作业越优惠。143.其它指标响应时间：响应时间：用户输入一个

7、请求（如击键）到系统给出首次响应（如屏幕显示）的时间分时系统。系统吞吐量：系统吞吐量：单位时间内系统所完成的作业数批处理系统。15 4.3 4.3 调度算法调度算法调度算法决定了系统追求的目标。调度算法决定了系统追求的目标。基本的调度算法有以下几种：基本的调度算法有以下几种：lFCFS算法，先来先服务调度。lSJF/SPF（ShortestProcessFirst）算法，短作业/进程优先调度。lHRF（HighestResponseFirst）算法，高响应比优先调度。lRR（RoundRobin）算法，时间片轮转调度。lHPF（HighestProcessFirst）算法，高优先级调度。l多级

8、反馈队列调度算法。16先来先服务(FCFS,First Come First Service)这是最简单的调度算法，按先后顺序进行调度。这是最简单的调度算法，按先后顺序进行调度。先来先服务（先来先服务（FCFS）：）：按照作业进入系统的先后次序进行调度，先进入系统者先调度；即启动等待时间最长的作业。优点：实现简单、公平缺点：没考虑资源利用率和作业的特殊性17按照进程变为就绪状态的先后次序，分派CPU。当前进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。在进程唤醒后（如I/O完成），并不立即恢复执行，通常在阻塞队列中等到当前进程出让CPU。这是最简单的算法。1.FCFS算法算法2.

9、FCFS的特点比较有利于长进程，而不利于短进程。有利于CPU繁忙的进程，而不利于I/O繁忙的进程。18短作业优先（短作业优先（SJF）：）：以要求运行时间长短进行调度，即启动要求运行时间最短的作业。优点：易于实现，强调了资源的充分利用，保证了系统的最大吞吐量（单位时间里处理作业的个数）缺点：不公平，会造成长作业长期等待短作业优先SJF(ShortestJobFirst)这是对这是对FCFS算法的改进，其目标是减少平均周转时间算法的改进，其目标是减少平均周转时间T。19短进程优先1.SPF算法算法对预计执行时间短的进程优先分派处理机。通常后来的短进程不抢先正在执行的进程。2.SPF的特点的特点提

10、高系统的吞吐量；对长进程非常不利，可能长时间得不到执行；难以准确估计进程的执行时间，从而影响调度性能。20SJF的变型“最短剩余时间优先”SRT(ShortestRemainingTime)允许比当前进程剩余时间更短的进程来抢占高响应比优先（高响应比优先（HRF）：）：响应比最高的作业优先启动。（响应比（响应比=（等待时间（等待时间+估计运行时间）估计运行时间）/估计运行时间）估计运行时间）该算法是FCFS和SJF的结合，克服了两种算法的缺点优点:公平，吞吐率大缺点:增加了计算，增加了开销21时间片轮转(Round Robin)算法前几种算法主要说明怎样选择一个进程或作业前几种算法主要说明怎样

11、选择一个进程或作业开始运行，开始运行后的做法都相同，即运行到结开始运行，开始运行后的做法都相同，即运行到结束或阻塞，阻塞结束时等待当前进程放弃束或阻塞，阻塞结束时等待当前进程放弃CPU。本算法本算法基本思路是通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率；221.时间片轮转算法将系统中所有的就绪进程按照FCFS原则，排成排成一个队列一个队列。每次调度时将CPU分派给队首进程队首进程，让其执行执行一个时间片一个时间片。时间片的长度从几个ms到几百ms。在一个时间片结束时，发生时钟中断时钟中断。调度程序据此暂停当前进程的执行暂停当前进程的执行，将其送到就绪队列的末尾就绪队列的末尾

12、，并通过上下文切换执行当前执行当前的队首进程的队首进程。进程可以未使用完一个时间片未使用完一个时间片，就出让出让CPU（如阻塞或者执行结束）。231.RR算法的调度过程RR算法是分时系统中采用的主要算法。当然，RR也可用于批处理系统或实时系统中。下图是分时系统的4个终端用户使用计算机轮转运行的CPU运行图。242.时间片长度的确定时间片长度变化的影响过长退化为FCFS算法，进程在一个时间片内都执行完。交互请求响应时间长。过短用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，系统开销大。影响时间片长度的因素：就绪进程的数目：数目越多，时间片越小（当响应时间一定时）系统的处理能力：应当使

13、用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。响应时间的要求：T(响应时间)=N(进程数目)*q(时间片)25优先级算法(Priority Scheduling)静态优先级动态优先级线性优先级调度算法（SRR,SelfishRoundRobin）26静态优先级依据：进程类型（系统进程优先级较高）对资源的需求（对CPU和内存需求较少的进程，优先级较高）用户要求（紧迫程度和付费多少）创建进程时就确定，直到进程终止前都不改变。创建进程时就确定，直到进程终止前都不改变。通常是一个整数。通常是一个整数。27动态优先级在就绪队列中，等待时间延长则优先级提高，从而使

14、优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行。进程每执行一个时间片，就降低其优先级，从而一个进程持续执行时，其优先级降低到出让CPU。在创建进程时赋予的优先级，在进程运行过程在创建进程时赋予的优先级，在进程运行过程中可以自动改变，以便获得更好的调度性能。中可以自动改变，以便获得更好的调度性能。如：注意：改变优先级是要占用系统开销的28根据不同情况分成不同的就绪队列。各队列的不同处理：不同队列可有不同的优先级、时间片长度、调度策略等。本算法是一种混合算法，引入多个就绪本算法是一种混合算法，引入多个就绪队列，通过各队列的区别对待，达到一个综队列，通过各队列的区别对待，达到一个综合

15、的调度目标。合的调度目标。多级反馈队列调度多级反馈队列调度2930 多级反馈队列调度是一种被普遍认可的调度方法。该方法需要在系统中设置多个就绪队列，每个队列有一个优先数（p）和一个时间片（q）。系统按照队列的优先数大小进行调度。即，优先调度p较高的队列，当队列为空时再调度p较低的队列。在各个队列内部的调度上，系统采用轮转调度算法。当一个进程在某个队列上运行完一个时间片后，若不能运行完成，则转入下一个队列。31设置多个就绪队列，分别赋予不同的优先级，并逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，并逐级加倍新进程进入内存后，先投入队列1的末尾，按FCF

16、S算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成。仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。32几点说明I/O型进程：让其进入最高优先级队列，以及时响应I/O交互。通常执行一个小的时间片，要求可处理完一次I/O请求的数据，然后转入到阻塞队列。计算型进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。为适应一个进程在不同时间段的运行特点，I/O完

17、成时，提高优先级；时间片用完时，降低优先级。33优点：为提高系统吞吐量和缩短平均周转时间而照顾短进程为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程不必估计进程的执行时间，动态调节34例子：通过作业平均周转时间T和平均带权周转时间W来分析一下作业调度中的4种算法的性能。为了便于分析，我们设想的是一个单道批处理系统。选用的例子中有4个作业，按照下图所示。其中,作业的到达顺序为A,B,C,D。时间为：8,8.5,9,9.5。运行时间：2,0.5,0.1,0.2。优先级为：10，25，7，18。35364.4 实时调度4.4.1实时调度的特点4.4.2实时调度算法374.4.1 实时调度

18、的特点要求更详细的调度信息：要求更详细的调度信息：如，就绪时间、开始或完成截止时间、处理时间、资源要求、绝对或相对优先级（硬实时或软实时），优先级用户可控。采用抢先式调度。采用抢先式调度。快速中断响应，快速中断响应，在中断处理时（硬件）关中断的时间尽量短。快速上下文切换：快速上下文切换：相应地采用较小的调度单位（如线程）。提高响应时间。38实时型作业1、硬实时和软实时2、周期性和非周期性4.4.2 4.4.2 实时任务的分类及其调度方法实时任务的分类及其调度方法39紧迫型实时任务调度立即抢占式优先级调度 普通型的实时任务调度基于时钟中断的抢占式优先级调度 宽松型的实时任务调度 非抢占的HPF调

19、度算法 RR算法非周期性任务非周期性任务40周期性任务调度周期性任务调度 在一些信号检测和过程控制系统中，有许多任务呈现周期性的运行规律。比如，气象信息检测中每隔2小时要读取一次数据，窑炉控制中每隔5分钟需检测一次炉温。这些任务的共同特点是，周期性强，而且有固定的时间间隔和相同的工作流程。通常，我们将这类任务称为周期性任务。目前，生产过程中的大多数数据信号采集系统，精密的过程检测与控制系统都属于此类。一个周期性任务进入时，需要向系统提交的信息有：代码长度和资源需求，还要包括间隔周期和每个周期内的执行时间等。41最早截止时间优先调度算法根据任务的截止时间来确定任务的优先级，截止时间越早，其优先级

20、越高，称为最早截止时间优先算法。在系统中保持一个实时任务就绪队列，该队列按各任务截止时间的早晚排序，具有最早截止时间的任务排在队列的最前面。调度程序在选择任务时，总是选择队列中的第一个任务，为之分配处理机，使之投入运行。该算法既可用于抢占式调度，也可用于非抢占式调度。42一个任务A的第i次执行的松弛度FA（i）的计算公式是：TA：任务A的周期长度，Tsi：任务A的执行时间，t：系统的当前时间。松弛度越小，说明任务的截止时间离当前时间越近。系统可以按照最小松弛度优先原则进程调度，相应的算法也称为最小剩余时间SRT调度算法。*注意：当任务Ai的松弛度大于一个周期长度时，系统认为Ai当前无权被调度。

21、最低松弛度优先算法43周期性任务的预计发生、执行与结束时限44时限调度算法给出的调度顺序45周期性任务调度定理：周期性任务调度定理：当下式成立时，系统有望实现调度。当下式成立时，系统有望实现调度。Ti：任务A的周期长度，Tsi：任务A的执行时间。46作业四1、什么是调度？什么是分级调度？分时系统中有作业调度的概念吗？有进程调度的概念吗？为什么？472、假设有4道作业，它们的提交时间和运行时间分别为计算在单道环境下，采用先来先服务和最短作业优先的调度算法所需的平均周转时间和平均带权周转时间，并指出调度顺序。作业号提交时间执行时间110:002:00210:201:00310:400:30410:500:1848