操作系统 第3章教学课件.pptx

《操作系统 第3章教学课件.pptx》由会员分享，可在线阅读，更多相关《操作系统 第3章教学课件.pptx（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、操作系统 第3章教学课件第第3 3章章 处理机调度处理机调度目录目录C C O O N N T T E E N N T T S S3.13.13.23.23.33.33.43.4分级调度分级调度作业调度作业调度进程调度进程调度调度算法调度算法进程的引入3.1处理机调度处理机调度在在计计算算机机系系统统中中，可能有许多批处理作业同时存放在磁盘的作业队列中，或者有许多终端与主机相连接。如何从这些作业中挑选作业进入主存运行、如何在进程之间分配处理器时间，便是处理机调度需要解决的问题。处处理理机机调调度度是是多多道道程程序序系系统统的的基基础础。在多道程序环境下，一个作业从提交到完成通常要经历多级调度

2、，如高级调度、中级调度、低级调度等。处理机调度算法的优劣直接影响到整个计算机系统的性能。本章主要介绍调度算法、周转时间及相关计算、调度目标、策略及评价方法等。3.1.13.1.1 作业调度作业调度作作业业调调度度又称宏观调度、高级调度或长程调度，其主要任务是按一定的原则从外存上处于后备状态的作业中选择一个或多个，给它们分配内存、输入/输出设备等必要的资源，并建立相应的进程，以使该作业具有获得竞争处理机的权利。作业调度的运行频率较低，通常为几分钟一次。在批处理系统中或者通用操作系统中的批处理部分，新提交的作业先存放在磁盘上，因此需要作业调度，将它们分批装入内存。而在其他类型的操作系统中，通常不需

3、要配置作业调度。中级调度又称交换调度或中程调度中级调度又称交换调度或中程调度，其主要任务是按照给定的原则和策略，将处于外存对换区中，且又具备运行条件的进程调入内存，或将处于内存的暂时不能运行的进程交换到外存对换区。中级调度的运行频率介于作业调度与进程调度之间。引入中级调度的主要目的是提高内存的利用率和系统吞吐量，它实际起着存储器管理中的交换功能，因此中级调度的内容将在内存管理中介绍。交换调度中程调度提高内存3.1.23.1.2 中级调度中级调度3.1.33.1.3 进程调度进程调度进进程程调调度度又又称称微微观观调调度度、低低级级调调度度或或短短程程调调度度，其主要任务是按照某种策略和方法从就

4、绪队列中选取一个进程，将处理机分配给它。进程调度的运行频率很高，一般几十毫秒一次。进程调度是操作系统中最基本的一种调度，在一般操作系统中都必须配置进程调度。3.1.43.1.4 调度性能的评价调度性能的评价调度算法的好坏直接影响到系统的效率。影响调度算法的因素很多，同时这些因素之间常常互相矛盾，所以实际采用的调度算法往往依赖于系统的设计目标，系统设计目标有以下系统设计目标有以下3 3种。种。（1）系统的处理能力高。使系统每天运行尽可能多的作业。（2）系统资源利用充分。使处理机保持忙碌状态，以达到充分利用系统资源的目的。（3）算法对所有的作业公平合理。使所有用户感到满意。由于这些目标往往相互冲突

5、，任何一个调度算法想要同时满足上述目标是不可能的。例如，要想执行尽可能多的作业，调度算法就应选择那些估计执行时间短的作业，而这对于那些估计执行时间长的作业不公平。由此看出，要设计一个理想的调度算法是一件很困难的事。1)1)调度算法应达到的目标调度算法应达到的目标3.1.43.1.4 调度性能的评价调度性能的评价设计目标设计目标。系统选择的调度算法应与系统的总体设计目标一致。例如，批处理系统应尽量提高系统的平均吞吐量；分时系统应保证用户所能忍受的响应时间；而实时系统则应在保证及时响应和处理有关事件的前提下，再去考虑系统资源的利用率。资源使用的均衡性资源使用的均衡性。注意系统资源的均衡使用，使输入

6、/输出繁忙的作业与CPU繁忙的作业搭配运行。平衡系统和用户的要求平衡系统和用户的要求。由于系统和用户的要求往往是矛盾的对立双方，确定算法时要尽量缓和双方的矛盾。例如，任何用户都希望作业一进入系统就立即执行，从而很快得到计算结果，然而系统却往往不能满足用户的这一愿望和要求。2)2)确定调度算法时应考虑的因素确定调度算法时应考虑的因素3.1.43.1.4 调度性能的评价调度性能的评价CPUCPU利用率利用率CPU是计算机系统中最重要最昂贵的资源之一，其利用率是评价调度算法的重要指标。系统吞吐量系统吞吐量系统吞吐量表示单位时间内CPU完成作业的数量。对于长作业来说，由于它们要消耗较长的处理机时间，因

7、此会造成系统的吞吐量下降。周转时间周转时间从一个特定作业的观点出发，最重要的准则就是完成这个作业要花费多长时间，通常用周转时间或带权周转时间来衡量。响应时间响应时间在交互式系统中，周转时间不可能是最好的评价准则，一般采用响应时间作为衡量调度算法的重要准则之一。3)3)调度性能的评价准则调度性能的评价准则3.1.43.1.4 调度性能的评价调度性能的评价作业的周转时间是指从作业提交到作业完成之间的时间间隔。作业的周转时间Ti可用公式表示如下。Ti=Tei-Tsi其中Tei为作业i的完成时间，Tsi为作业i的提交时间。平均周转时间是指多个作业周转时间的平均值。个作业的平均周转时间T可用如下公式表示

8、。T=（T1+T2+Tn）/n带权周转时间是指作业周转时间与作业实际运行时间的比。作业的带权周转时间Wi可用如下公式表示。Wi=Ti/Tri其中Ti为作业i的周转时间，Tri为作业i的实际运行时间。平均带权周转时间是指多个作业带权周转时间的平均值。个作业的平均带权周转时间W可用公式表示如下。W=（W1+W2+Wn）/n3)3)调度性能的评价准则调度性能的评价准则进程的引入3.23.2.13.2.1 作业的状态及转换作业的状态及转换一个作业从进入系统到运行结束，一般需要经历提交、收容、运行和完成4个阶段。与这4个阶段相对应的作业处于提交、后备、运行和完成4种状态。作业的状态及其转换可用图3-2表

9、示。3.2.13.2.1 作业的状态及转换作业的状态及转换用户为了上机解题或进行某项事务处理，必须事先准备好自己的作业，然后将作业通过键盘等输入设备提交给计算机系统。用户作业由输入设备向系统外存输入时作业所处的状态称为提交状态。当作业调度程序选中一个作业，为它分配了必要的资源并建立相应的进程之后，这个作业就由后备状态转变为运行状态。当一个作业通过输入设备送入计算机，并由操作系统将其存放在磁盘中后，系统为这个作业建立一个作业控制块，并把它插入后备作业队列中等待调度运行。当作业正常运行结束或因发生错误而终止运行时，作业就处于完成状态。1 1）提交状态）提交状态2)2)后备状态后备状态3)3)运行状

10、态运行状态4)4)完成状态完成状态记录进入系统的各个作业情况记录进入系统的各个作业情况。为了挑选作业投入执行并在执行过程中对作业进行管理，作业调度程序必须掌握进入系统的作业情况，并随时记录作业在运行阶段的变化情况。为此，系统应为每个作业建立相应的数据结构。从后备作业中挑选一些作业投入执行从后备作业中挑选一些作业投入执行。一般来说，系统中处于后备状态的作业较多，有几十甚至几百个。后备作业的多少取决于存储后备作业的空间大小。但是处于运行状态（不是真正在CPU上执行）的作业一般只有有限的几个，如4个、10个。因此，作业调度程序的一个重要职能就是，适时按确定的调度策略从后备作业中选取若干作业进入运行状

11、态。作业调度的调度策略和调度时机通常与系统的设计目标有关，并由许多因素决定。为此，在设计作业调度程序时，必须综合平衡各种因素，确定符合系统设计目标的调度算法。为选中的作业做好执行前的准备工作为选中的作业做好执行前的准备工作。作业调度程序在让一个作业从后备状态进入运行状态之前，必须为该作业建立相应的进程，为其分配运行所需要的资源，分配的资源包括内存、磁盘空间和外设等。在作业运行结束或运行过程中因某种原因需要撤离时在作业运行结束或运行过程中因某种原因需要撤离时，作业调度程序还要完成作业的善后处理工作。3.2.23.2.2 作业调度程序作业调度程序1)1)作业调度程序的功能作业调度程序的功能3.2.

12、23.2.2 作业调度程序作业调度程序2)2)作业控制块作业控制块资源要求资源要求资源要求是指作业运行所需要的资源情况，包括估计运行时间、最迟完成时间、需要的内存容量、外设类型及数量等。资源使用情况资源使用情况资源使用情况包括作业进入系统的时间、开始运行时间、已运行时间、内存地址、外设台号等。作作业业的的控控制制方方式式、类型和优先级等类型和优先级等作业的控制方式有联机作业控制（又称为直接控制）和脱机作业控制（又称为自动控制两种）。作业名、作业状态作业名、作业状态记录作业的标识信息及作业的当前状态。进程的引入3.33.3.13.3.1 进程调度程序进程调度程序为为了了实实现现进进程程调调度度，

13、必须将系统中各进程的执行情况和状态特征记录在各进程的PCB中，同时还应根据各进程的状态特征和资源需求等信息将进程的PCB组织成相应的队列，并依据运行情况将进程的PCB在不同状态队列之间进行转换。进程调度程序通过PCB的变化来掌握系统中所有进程的执行情况和状态特征。1)1)记录系统中所有进程的有关情况及状态特征记录系统中所有进程的有关情况及状态特征3.3.13.3.1 进程调度程序进程调度程序按照一定的策略选择一个处于就绪状态的进程，使其获得处理机执行。根据不同的系统设计目标，有多种选择策略，如先来先服务、时间片轮转等，这些选择策略决定了调度算法的性能。2)2)选择获得处理机的进程选择获得处理机

14、的进程当正在执行的进程由于某种原因要放弃处理机时，进程调度程序应保护当前执行进程的CPU现场，将其状态由执行变成就绪或阻塞，并插入相应队列中；同时，进程调度程序还应根据一定原则从就绪队列中挑选出一个进程，将该进程从就绪队列中移出，恢复其CPU现场，并将其状态改为执行。引起进程调度的原因有以下几种引起进程调度的原因有以下几种。当前运行进程运行结束。因任务完成而正常结束，或者因出现错误而异常结束。当前运行进程因某种原因，如I/O请求，从运行状态进入阻塞状态。当前运行进程执行某种原语操作，如P操作、阻塞原语等，进入阻塞状态。执行完系统调用等系统程序后返回用户进程，这时可以看做是系统进程执行完毕，从而

15、可以调度一个新的用户进程。在采用剥夺调度方式的系统中，一个具有更高优先级的进程要求使用处理机，则使当前运行进程进入就绪队列（这与调度方式有关）。在分时系统中，分配给该进程的时间片已用完（这与系统类型有关，多用于分时系统中）。3.3.13.3.1 进程调度程序进程调度程序3)3)处理机分配处理机分配进程调度方式进程调度方式是指当某一个进程正在处理机上执行时，有某个更为重要或紧迫的进程需要进行处理（即有更高优先级的进程进入就绪队列），此时应如何分配处理机。通常有以下两种进程调度方式。抢占方式抢占方式。抢占方式又称剥夺方式、可剥夺方式、可抢占方式，这种进程调度方式是指当一个进程正在处理机上执行时，若

16、有某个更为重要或紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更为重要或紧迫的进程。非抢占方式非抢占方式。非抢占方式又称非剥夺方式、不可剥夺方式、不可抢占方式。这种进程调度方式是指当某一个进程正在处理机上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程完成或发生某种事件而进入阻塞状态时，才把处理机分配给更为重要或紧迫的进程。进程调度抢占方式非抢占方式3.3.23.3.2 进程调度方式进程调度方式进程的引入3.43.4.13.4.1 先来先服务调度算法先来先服务调度算法先来先服务调度算法先来先服务调度算法是最简单的一种调度算法，该调

17、度算法既可以用于作业调度，也可以用于进程调度。在在作作业业调调度度中中，先来先服务调度算法每次从后备作业队列中选择最先进入该队列的一个或几个作业，将它们调入内存，为其分配必要的资源，创建进程并放入就绪队列。在进程调度中，先来先服务调度算法每次从就绪队列中选择最先进入该队列的进程，将处理机分配给它，使之投入运行，该进程一直运行下去，直到完成或因某种原因而阻塞时才释放处理机。下面通过一个例子来说明先来先服务调度算法的性能。假设系统中有4个作业，它们的提交时间、运行时间、开始时间、完成时间、周转时间和带权周转时间如表3-1所示。3.4.13.4.1 先来先服务调度算法先来先服务调度算法时间时间提交时

18、间提交时间运行时间运行时间开始时间开始时间完成时间完成时间周转时间周转时间带权周转时带权周转时间间作业作业1828102128.4110112.62.638.80.51111.52.75.4490.211.511.72.713.5短短作作业业优优先先调调度度算算法法用于进程调度时称为短进程优先调度算法，该调度算法既可以用于作业调度，也可以用于进程调度。在在作作业业调调度度中中，短作业优先调度算法每次从后备作业队列中选择估计运行时间最短的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。在在进进程程调调度度中中，短进程优先调度算法每次从就绪队列中选择估计运行时间最短的进程，

19、将处理机分配给它，使之投入运行，该进程一直运行下去，直到完成或因某种原因而阻塞时才释放处理机。3.4.23.4.2 短作业优先调度算法短作业优先调度算法对表3-2给出的一组作业采用短作业优先调度算法。3.4.23.4.2 短作业优先调度算法短作业优先调度算法时间时间提交时间提交时间运行时间运行时间开始时间开始时间完成时间完成时间周转时间周转时间带权周转时带权周转时间间作业作业1828102128.4110.711.73.33.338.80.510.210.71.93.8490.21010.21.26短作业优先调度算法可以是非抢占式的，也可以是抢占式的短作业优先调度算法可以是非抢占式的，也可以是

20、抢占式的。若无特别说明，通常是指非抢占式的算法。抢占式的短作业优先调度算法也称为最短剩余时间优先调度算法，即当一个新进程进入就绪队列时，若它需要的运行时间比当前运行进程的剩余时间短，则将抢占CPU。对表33所示的一组作业采用最短剩余时间优先调度算法。3.4.23.4.2 短作业优先调度算法短作业优先调度算法时间时间提交时间提交时间运行时间运行时间开始时间开始时间完成时间完成时间周转时间周转时间带权周转时带权周转时间间作业作业108017172.12521415413291726242.6743551071.43.4.33.4.3 优先级调度算法优先级调度算法在作业调度中在作业调度中，优先级调度

21、算法每次从后备作业队列中选择优先级最高的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。非抢占式优先级调度算法非抢占式优先级调度算法的实现思想是系统一旦将处理机分配给就绪队列中优先级最高的进程，该进程便一直运行下去，直到由于其自身的原因主动让出处理机时，才将处理机分配给另一个优先级高的进程。在进程调度中在进程调度中，优先级调度算法每次从就绪队列中选择优先级最高的进程，将处理机分配给它，使之投入运行。根据进程调度方式的不同，又可以将优先级调度算法分为非抢占式优先级调度算法和抢占式优先级调度算法。抢占式优先级调度算法抢占式优先级调度算法的实现思想是将处理机分配给优先级最高的

22、进程，使之运行。在进程运行过程中，一旦出现了另一个优先级更高的进程，进程调度程序就停止当前进程的运行，而将处理机分配给新出现的高优先级进程。1 1）优先级调度算法的实现）优先级调度算法的实现3.4.33.4.3 优先级调度算法优先级调度算法通常系统中有系统进程和用户进程两类进程。各进程运行速度以及系统资源的利用率在很大程度上依赖于系统进程。例如，若系统中某种共享输入/输出设备由一系统进程管理，那么使用这种设备的所有进程的运行速度都依赖于这一系统进程。根据作业要求系统提供的处理机时间、内存大小、I/O设备的类型及数量来确定作业的优先级。由于作业的执行时间事先难以确定，所以只能根据用户提出的估计时

23、间来确定。进程所申请的资源越多，估计的运行时间越长，进程的优先级就越低。系统可以按用户提出的要求设置进程优先级，为防止用户将自己的进程都设置为高优先级，可以采用高优先级高收费的策略。进程类型进程类型进程对资源的要求进程对资源的要求用户要求用户要求2 2）进程的优先级）进程的优先级3.4.33.4.3 优先级调度算法优先级调度算法进进程程占占用用CPUCPU的的时时间间。一个进程占用CPU的时间越长，则优先级越低，再次获得调度的可能性就越小；反之，一个进程占用CPU的时间越短，则优先级越高，获得调度的可能性就越大。进进程程等等待待CPUCPU的的时时间间。一个进程在就绪队列中等待的时间越长，则优

24、先级越高，获得调度的可能性就越大；反之，一个进程在就绪队列中等待的时间越短，则优先级越低，获得调度的可能性就越小。确定动态优先级的主要依据有以下几种。确定动态优先级的主要依据有以下几种。时时间间片片轮轮转转调调度度算算法法主要用于分时系统中的进程调度。在时间片轮转调度算法中，系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是选择就绪队列中的第一个进程执行，并规定执行一定时间，如100ms，该时间称为时间片。当该进程用完这一时间片时（即使进程并未完成其运行），系统将它送至就绪队列队末尾，再把处理机分配给就绪队列的队首进程。这样，处于就绪队列中的进程就可以依次轮流地获得一个时间片

25、的处理时间，然后回到队列尾部，如此不断循环，直至完成为止。进程调度进程执行不断循环3.4.43.4.4 时间片轮转调度算法时间片轮转调度算法例如，表3-4所示的A、B、C、D、E 5个进程，到达时间分别为0、1、2、3、4，要求运行时间依次为3、6、4、5、2，采用时间片轮转调度算法，时间片大小q为1。3.4.43.4.4 时间片轮转调度算法时间片轮转调度算法进程名进程名到达时间到达时间运行时间运行时间开始时间开始时间完成时间完成时间周转时间周转时间带权周转时带权周转时间间A030772.33B16119183C24316143.5D35520173.4E4271284对于表3-5所示的A、B

26、、C、D、E 5个进程，到达时间分别为0、1、2、3、4，要求运行时间依次为3、6、4、5、2，采用时间片轮转调度算法，时间片大小q为4。3.4.43.4.4 时间片轮转调度算法时间片轮转调度算法进程名进程名到达时间到达时间运行时间运行时间开始时间开始时间完成时间完成时间周转时间周转时间带权周转时带权周转时间间A030331B16319183C2471192.25D351120173.4E421517136.5系系统统的的响响应应时时间间。分时系统必须满足系统对响应时间的要求，系统响应时间与时间片的关系可以表示为T=Nq，其中，T为系统的响应时间，q为时间片的大小，N为就绪队列中的进程数。若系

27、统中的进程数目一定，时间片的大小与系统响应时间成正比。就绪队列中的进程数目就绪队列中的进程数目。在响应时间固定的情况下，就绪队列中的进程数目与时间片成反比。系系统统的的处处理理能能力力。通常要求用户输入的常用命令能够在一个时间片内处理完毕。因此，计算机的速度越快，时间片就越短。相应时间进程数目处理能力3.4.43.4.4 时间片轮转调度算法时间片轮转调度算法时间片的长短通常由以下因素确定。时间片的长短通常由以下因素确定。先来先服务调度算法只考虑作业的等待时间而未考虑作业运行时间，短作业优先调度算法只考虑作业运行时间而忽略了作业的等待时间，这两种调度算法都有不足之处，为此引入了高响应比优先调度算

28、法。高响应比优先调度算法主要用于作业调度，该算法是对先来先服务调度算法和短作业优先调度算法的一种综合平衡，该算法既考虑作业运行时间，也考虑作业的等待时间。响应比的定义如下。响应比的定义如下。响应比响应比=作业响应时间作业响应时间/估计运行时间估计运行时间3.4.53.4.5 高响应比优先调度算法高响应比优先调度算法对表3-6所示的进程采用高响应比优先调度算法。3.4.53.4.5 高响应比优先调度算法高响应比优先调度算法进程名进程名到达时间到达时间运行时间运行时间开始时间开始时间完成时间完成时间周转时间周转时间带权周转时带权周转时间间A030331B163981.35C241115133.25

29、D351520173.4E4291173.53.4.63.4.6 多级队列调度算法多级队列调度算法多多级级队队列列调调度度算算法法用用于于进进程程调调度度，其实现思想是根据进程的性质或类型，将就绪队列划分为若干子队列，每个进程固定属于一个就绪队列，每个就绪队列采用一种调度算法，不同的队列可以采用不同的调度算法。例如，为交互型作业设置一个就绪队列，该队列采用时间片轮转调度算法；为批处理作业设置另一个就绪队列，该队列采用先来先服务调度算法。多级反馈队列调度算法多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合和发展。通过动态调整进程优先级和时间片大小，多级反馈队列调度算法可以兼顾多方面

30、的系统目标。例如，为提高系统吞吐量和缩短平均周转时间而照顾短进程；为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程；同时，也不必事先估计进程的执行时间。3.4.73.4.7 多级反馈队列调度算法多级反馈队列调度算法系统中应设置多个就绪队列系统中应设置多个就绪队列，每个就绪队列对应一个优先级，第一个队列的优先级最高，第二个队列次之，其余队列的优先级逐次降低。每个队列中进程的时间片大小各不相同每个队列中进程的时间片大小各不相同，进程所在队列的优先级越高，其相应的时间片就越短。当一个新进程进入系统时当一个新进程进入系统时，首先将它放入第一个队列的末尾，按先来先服务的原则排队等待调度。当轮

31、到该进程执行时，如能在此时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二个队列的末尾，再同样地按先来先服务原则等待调度执行；如果它在第二个队列中运行一个时间片后仍未完成，再以同样方法转入第三个队列。如此下去，最后一个队列中使用时间片轮转调度算法。仅当第一个队列为空时仅当第一个队列为空时，调度程序才从第二个队列中选择进程运行；仅当第一个队列至第（i-1）个队列均为空时，才会调度第i个队列中的进程运行。3.4.73.4.7 多级反馈队列调度算法多级反馈队列调度算法多级反馈队列调度算法的示意图多级反馈队列调度算法实现思想如下。多级反馈队列调度算法的示意图多

32、级反馈队列调度算法实现思想如下。对表3-7所示的进程采用多级反馈队列调度算法。设系统中建立了3个队列，第一个队列的时间片q为1，第二个队列的时间片q为2，第三个队列的时间片q为4。3.4.73.4.7 多级反馈队列调度算法多级反馈队列调度算法进程名进程名到达时间到达时间运行时间运行时间开始时间开始时间完成时间完成时间周转时间周转时间带权周转时带权周转时间间A030993B18127263.25C34320174.25D45422183.6E57526213公平分享调度算法基于进程组来分配CPU时间，其实现思想是对系统中的每个用户赋予某种权值，根据用户权值大小，按比例分配处理机时间。公平分享调度

33、有许多实现方案，这里讲述UNIX系统中的一种实现方案。NIX系统基于优先权调度，优先数越大优先权越低。对进程组k中进程j的优先数计算公式如下。CPUj(i)=CPUj(i-1)/2GCPUk(i)=GCPUk(i-1)/2Pj(i)=Basej+CPUj(i)/2+GCPUk(i)/4Wk其中，CPUj(i)为进程j在时间段i使用的CPU时间；GCPUk(i)为进程组k在时间段i使用的CPU时间；Pj(i)为进程j在时间段i的优先数，其值越小表示其优先权越高，Basej为进程j的基本优先数，Wk为进程组k的权值，且满足下面两个约束条件。（1）0Wk1（2）kWk=13.4.83.4.8 公平分享调度算法公平分享调度算法习题习题1 1）选择题）选择题2 2）填空题）填空题3 3）解答题）解答题感感 谢谢 观观 看看