0第4章处理机调度n

《0第4章处理机调度n》由会员分享，可在线阅读，更多相关《0第4章处理机调度n（102页珍藏版）》请在金锄头文库上搜索。

1、单击此处编辑母版标题样式单击此处编辑母版标题样式单击此处编辑母版副标题样式单击此处编辑母版副标题样式第第4章章 处理机调度处理机调度4.1 分级调度分级调度4.2 作业调度作业调度4.3 进程调度进程调度4.4 调度算法调度算法4.5 算法评价算法评价4.6 实时系统调度方法实时系统调度方法本章小结本章小结习题习题 CPU是计算机系统中一个十分重要的资源。在早期的计算机是计算机系统中一个十分重要的资源。在早期的计算机系统中，对它的管理是十分简单的。随着多道程序设计技术和各系统中，对它的管理是十分简单的。随着多道程序设计技术和各种不同类型的操作系统的出现，各种不同的种不同类型的操作系统的出现，各

2、种不同的CPU管理方法得到启管理方法得到启用。不同的用。不同的CPU管理方法将为用户提供不同性能的操作系统。例管理方法将为用户提供不同性能的操作系统。例如：在多道批处理系统中，为了提高处理机的效率和增加作业吞如：在多道批处理系统中，为了提高处理机的效率和增加作业吞吐率，当调度一批作业组织多道运行时，要尽可能使作业搭配合吐率，当调度一批作业组织多道运行时，要尽可能使作业搭配合理。这样，就能使系统中的各种资源可充分利用。在用户看来，理。这样，就能使系统中的各种资源可充分利用。在用户看来，这是一台没有交互、速度较慢的处理机。在分时系统中，在调度这是一台没有交互、速度较慢的处理机。在分时系统中，在调度

3、作业执行时要首先考虑每个用户作业得到处理机的均等性。这样，作业执行时要首先考虑每个用户作业得到处理机的均等性。这样，系统资源的利用率就不如批处理系统。由此可以看到，根据操作系统资源的利用率就不如批处理系统。由此可以看到，根据操作系统的要求不同，处理机管理的策略是不同的。系统的要求不同，处理机管理的策略是不同的。衡量调度策略的最常用的几个指标是：衡量调度策略的最常用的几个指标是：(1)周转时间周转时间是指将一个作业提交给计算机系统后是指将一个作业提交给计算机系统后到该作业的结果返回给用户所需要的时间。到该作业的结果返回给用户所需要的时间。(2)吞吐率吞吐率是指在单位时间内，一个计算机系统所是指在

4、单位时间内，一个计算机系统所完成的总工作量。完成的总工作量。(3)响应时间响应时间则是指从用户向计算机发出一个命令则是指从用户向计算机发出一个命令到计算机把相应的执行结果返回给用户所需要的时间。到计算机把相应的执行结果返回给用户所需要的时间。本章主要讨论：本章主要讨论：(1) 作业与进程的关系；作业与进程的关系；(2) 作业调度策略算法；作业调度策略算法；(3) 进程调度策略与算法；进程调度策略与算法；(4) 调度策略的评价。调度策略的评价。4.1 分分 级级 调调 度度4.1.1 作业的状态及其转换作业的状态及其转换以批处理系统为例一个作业处理的大致过程。以批处理系统为例一个作业处理的大致过

5、程。如图如图4.1 所示，一个作业从提交给计算机系统到执所示，一个作业从提交给计算机系统到执行结束退出系统，一般都要经历行结束退出系统，一般都要经历提交、收容、执行和提交、收容、执行和完成等完成等4个状态个状态。图图4.1 作业的状态及其转换作业的状态及其转换读卡机读卡机打印机打印机I/O请求磁盘磁盘通道P1P2P3P4P5提交状提交状态态后备状后备状态态执行状执行状态态完成状完成状态态提交后备执行完成退出SPOOLing输入作业调度1作业调度2SPOOLing输出(1)提交状态提交状态:一个作业在其处于从输入设备进入一个作业在其处于从输入设备进入外部存储设备的过程称为提交状态。外部存储设备的

6、过程称为提交状态。(2)收容状态收容状态(后备状态后备状态):若一个作业的全部信息若一个作业的全部信息已全部被输入进输入井，那么，在它还未被调度去执已全部被输入进输入井，那么，在它还未被调度去执行之前，该作业处于收容状态。行之前，该作业处于收容状态。(3)执行状态执行状态:作业调度程序从后备作业中选取若作业调度程序从后备作业中选取若干个作业到内存投入运行。这些被选中的作业处于执干个作业到内存投入运行。这些被选中的作业处于执行状态。行状态。 (4)完成状态完成状态:当作业运行完毕，但它所占用的资当作业运行完毕，但它所占用的资源尚未全部被系统回收时，该作业处于完成状态。源尚未全部被系统回收时，该作

7、业处于完成状态。4.1.2 调度的层次调度的层次处理机调度问题实际上是处理机的分配问题。处理机调度问题实际上是处理机的分配问题。显显然，只有那些参与竞争处理机所必需的资源都已得到然，只有那些参与竞争处理机所必需的资源都已得到满足的进程才能享有竞争处理机的资格。这时，它们满足的进程才能享有竞争处理机的资格。这时，它们处于内存就绪状态。这些必需的资源包括内存、外设处于内存就绪状态。这些必需的资源包括内存、外设及有关数据结构等。从而，在进程有资格竞争处理机及有关数据结构等。从而，在进程有资格竞争处理机之前，作业调度程序必须先调用存储管理、外设管理之前，作业调度程序必须先调用存储管理、外设管理程序，并

8、按一定的选择顺序和策略从输入井中选择出程序，并按一定的选择顺序和策略从输入井中选择出几个处于后备状态的作业，为它们分配内存等资源和几个处于后备状态的作业，为它们分配内存等资源和创建进程，使它们获得竞争处理机的资格。创建进程，使它们获得竞争处理机的资格。另外，由于处于执行状态下的作业一般包含有多另外，由于处于执行状态下的作业一般包含有多个进程，而在单机系统中，每一时刻只能有一个进程个进程，而在单机系统中，每一时刻只能有一个进程占有处理机。那么，其他进程就只能处于准备抢占处占有处理机。那么，其他进程就只能处于准备抢占处理机的就绪状态或等待得到某种新资源的等待状态。理机的就绪状态或等待得到某种新资源

9、的等待状态。为了提高资源的利用率，在有些操作系统中把一部分为了提高资源的利用率，在有些操作系统中把一部分在内存中处于就绪状态或等待状态而在短时期内又得在内存中处于就绪状态或等待状态而在短时期内又得不到执行的进程、作业换出内存，以让其他作业的进不到执行的进程、作业换出内存，以让其他作业的进程竞争处理机。这样，在外存中，除了处于后备状态程竞争处理机。这样，在外存中，除了处于后备状态的作业外，还存在有处于就绪状态而等待得到内存的的作业外，还存在有处于就绪状态而等待得到内存的作业。这就需要有一定的方法和策略为这部分作业分作业。这就需要有一定的方法和策略为这部分作业分配空间。配空间。一般来说，处理机调度

10、可以分为一般来说，处理机调度可以分为4级：级：(1) 作业调度作业调度：又称宏观调度，或高级调度。其主要任：又称宏观调度，或高级调度。其主要任务是按一定的原则对外存输入井上的大量后备作业进行选择，务是按一定的原则对外存输入井上的大量后备作业进行选择，给选出的作业分配内存、输入输出设备等必要的资源，并建给选出的作业分配内存、输入输出设备等必要的资源，并建立相应的进程。另外，当该作业执行完毕时，还负责回收系立相应的进程。另外，当该作业执行完毕时，还负责回收系统资源。统资源。(2) 交换调度交换调度：又称中级调度。其主要任务是按照给定：又称中级调度。其主要任务是按照给定的原则和策略，将处于外存交换区

11、中的就绪状态或等待状态的原则和策略，将处于外存交换区中的就绪状态或等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区。进程交换到外存交换区。 (3) 进程调度进程调度：又称微观调度或低级调度。其主要任务：又称微观调度或低级调度。其主要任务是按照某种策略和方法选取一个处于就绪状态的进程占用处是按照某种策略和方法选取一个处于就绪状态的进程占用处理机。在确定了占用处理机的进程后，系统必须进行进程上理机。在确定了占用处理机的进程后，系统必须进行进程上下文切换以建立与占用处理机进程相适应的执行环境。下文切换以建立与占用处理

12、机进程相适应的执行环境。(4) 线程调度线程调度。上述上述4级调度的关系如图级调度的关系如图4.1 在多道批处理系统中，存在着作业调度和进程调在多道批处理系统中，存在着作业调度和进程调度。但是，在分时系统和实时系统中，一般不存在作度。但是，在分时系统和实时系统中，一般不存在作业调度，而只有进程调度、交换调度和线程调度。这业调度，而只有进程调度、交换调度和线程调度。这是因为在分时系统和实时系统中，为了缩短响应时间是因为在分时系统和实时系统中，为了缩短响应时间或为了满足用户需求的截止时间，作业不是建立在外或为了满足用户需求的截止时间，作业不是建立在外存，而是直接建立在内存中。在这些系统中，一旦用存

13、，而是直接建立在内存中。在这些系统中，一旦用户和系统的交互开始，用户马上要进行控制。因而，户和系统的交互开始，用户马上要进行控制。因而，这些系统中没有作业提交状态和后备状态。它们的输这些系统中没有作业提交状态和后备状态。它们的输入信息经过终端缓冲区为系统所接收，或者立即处理，入信息经过终端缓冲区为系统所接收，或者立即处理，或者经交换调度暂存外存中。或者经交换调度暂存外存中。4.1.3 作业与进程的关系作业与进程的关系作业可被看作是用户向计算机提交任务的任务实作业可被看作是用户向计算机提交任务的任务实体，体，例如一次计算、一个控制过程等。反过来，例如一次计算、一个控制过程等。反过来，进程进程则是

14、计算机为了完成用户任务实体而设置的执行实体，则是计算机为了完成用户任务实体而设置的执行实体，是系统分配资源的基本单位是系统分配资源的基本单位。显然，计算机要完成一。显然，计算机要完成一个任务实体，必须要有一个以上的执行实体。也就是个任务实体，必须要有一个以上的执行实体。也就是说，说，一个作业总是由一个以上的多个进程组成的。一个作业总是由一个以上的多个进程组成的。那那么，作业怎样分解为进程呢？么，作业怎样分解为进程呢？首先，系统必须为一个首先，系统必须为一个作业创建一个根进程。然后，在执行作业控制语句时，作业创建一个根进程。然后，在执行作业控制语句时，根据任务要求，系统或根进程为其创建相应的子进

15、程，根据任务要求，系统或根进程为其创建相应的子进程，然后，为各子进程分配资源和调度各子进程执行以完然后，为各子进程分配资源和调度各子进程执行以完成作业要求的任务。成作业要求的任务。4.2 作作 业业 调调 度度作业调度主要是完成作业从后备状态到执行状态作业调度主要是完成作业从后备状态到执行状态的转变，以及从执行状态到完成状态的转变。的转变，以及从执行状态到完成状态的转变。4.2.1 作业调度功能作业调度功能(1) 记录系统中各作业的状况。记录系统中各作业的状况。作业调度程序要作业调度程序要能挑选出一个作业投入执行，并且在执行中对其进行能挑选出一个作业投入执行，并且在执行中对其进行管理，它就必须

16、掌握作业在各个状态，包括执行阶段管理，它就必须掌握作业在各个状态，包括执行阶段的有关情况。的有关情况。通常，系统为每个作业建立一个作业控通常，系统为每个作业建立一个作业控制表制表JCB记录这些有关信息。记录这些有关信息。系统通过系统通过JCB而感知作而感知作业的存在。系统在作业进入后备状态时为该作业建立业的存在。系统在作业进入后备状态时为该作业建立它的它的JCB，从而使得该作业可被作业调度程序感知。从而使得该作业可被作业调度程序感知。当该作业执行完毕进入完成状态之后，系统又撤消其当该作业执行完毕进入完成状态之后，系统又撤消其JCB而释放有关资源并撤消该作业。而释放有关资源并撤消该作业。图图4.

17、2给出了给出了JCB的主要内容。它包括作业名、作的主要内容。它包括作业名、作业类型、资源要求、当前状态、资源使用情况以及该业类型、资源要求、当前状态、资源使用情况以及该作业的优先级等。作业的优先级等。图图4.2 作业控制块作业控制块JCB作业名作业类型资源要求资源使用情况优先级(数)当前状态其他其中，作业名由用户提供并由系统将其转换为系其中，作业名由用户提供并由系统将其转换为系统可识别的作业标识符。作业类型指该作业属于计算统可识别的作业标识符。作业类型指该作业属于计算型（要求型（要求CPU时间多）还是管理型（要求输入输出时间多）还是管理型（要求输入输出量大）量大）,或图形设计型（要求高速图形显

18、示）等。而或图形设计型（要求高速图形显示）等。而资源要求则包括：该作业估计执行时间、要求最迟完资源要求则包括：该作业估计执行时间、要求最迟完成时间、要求的内存量和外存量、要求的外设类型及成时间、要求的内存量和外存量、要求的外设类型及台数以及要求的软件支持工具库函数等。资源要求均台数以及要求的软件支持工具库函数等。资源要求均由用户提供。资源使用情况包括有：作业进入系统时由用户提供。资源使用情况包括有：作业进入系统时间、开始执行时间、已执行时间、内存地址、外设台间、开始执行时间、已执行时间、内存地址、外设台数等。优先级则被用来决定该作业的调度次序。优先数等。优先级则被用来决定该作业的调度次序。优先

19、级既可以由用户给定，也可以由系统动态计算产生。级既可以由用户给定，也可以由系统动态计算产生。状态是指该作业当前所处的状态。显然，只有当作业状态是指该作业当前所处的状态。显然，只有当作业处于后备状态时，该作业才可以被调度。处于后备状态时，该作业才可以被调度。(2) 从后备队列中挑选出一部分作业投入执行。从后备队列中挑选出一部分作业投入执行。作业调度程序根据选定的调度算法，从后备作业队列作业调度程序根据选定的调度算法，从后备作业队列中挑选出若干作业去投入执行。中挑选出若干作业去投入执行。(3) 为被选中作业做好执行前的准备工作。为被选中作业做好执行前的准备工作。作业作业调度程序调度程序为选中的作业

20、建立相应的进程，为选中的作业建立相应的进程，并为这些进并为这些进程分配它们所需要的系统资源，如分配给它们内存、程分配它们所需要的系统资源，如分配给它们内存、外存、外设等。外存、外设等。(4) 在作业执行结束时做善后处理工作。在作业执行结束时做善后处理工作。主要是主要是输出作业管理信息，例如执行时间等。再就是回收该输出作业管理信息，例如执行时间等。再就是回收该作业所占用的资源，撤消与该作业有关的全部进程和作业所占用的资源，撤消与该作业有关的全部进程和该作业的作业控制块等等。该作业的作业控制块等等。作业从后备状态到执行状态，又从执行状态到完作业从后备状态到执行状态，又从执行状态到完成状态的转换过程

21、如图成状态的转换过程如图4.3所示。所示。图图4.3 作业调度中状态的转换过程作业调度中状态的转换过程4.2.2 作业调度目标与性能衡量作业调度目标与性能衡量作业调度的功能最主要的是从后备作业队列中选作业调度的功能最主要的是从后备作业队列中选取一批作业进入执行状态。根据不同的目标，将会有取一批作业进入执行状态。根据不同的目标，将会有不同的调度算法。这里先介绍调度目标。不同的调度算法。这里先介绍调度目标。一般来说，调度目标主要是以下一般来说，调度目标主要是以下4点：点：(1) 对所有作业应该是公平合理的；对所有作业应该是公平合理的；(2) 应使设备有高的利用率；应使设备有高的利用率；(3) 每天

22、执行尽可能多的作业；每天执行尽可能多的作业；(4) 有快的响应时间。有快的响应时间。由于这些目标的相互冲突，任一调度算法要想同由于这些目标的相互冲突，任一调度算法要想同时满足上述目标是不可能的。时满足上述目标是不可能的。作业调度的工作时机：作业调度的工作时机：（1）系统初启）系统初启（2）一个作业运行完成，撤离系统）一个作业运行完成，撤离系统（3）后备作业队列中到达一个新的作业）后备作业队列中到达一个新的作业（4）一个作业释放了一定的资源）一个作业释放了一定的资源 那么，怎样来衡量一个作业调度算法是否满足系那么，怎样来衡量一个作业调度算法是否满足系统设计的要求呢？对于批处理系统，由于主要用于计

23、统设计的要求呢？对于批处理系统，由于主要用于计算，对于作业的周转时间要求较高。因此，作业的平算，对于作业的周转时间要求较高。因此，作业的平均周转时间或平均带权周转时间，被作为衡量调度算均周转时间或平均带权周转时间，被作为衡量调度算法优劣的标准。但是，对于分时系统和实时系统来说，法优劣的标准。但是，对于分时系统和实时系统来说，外加平均响应时间被作为衡量调度策略优劣的标准。外加平均响应时间被作为衡量调度策略优劣的标准。1. 周转时间：周转时间：作业作业i的周转时间的周转时间Ti为为Ti=Tei-Tsi其中其中Tei为作业为作业i的完成时间，的完成时间，Tsi为作业的提交时间。为作业的提交时间。对于

24、被测定作业流所含有的对于被测定作业流所含有的n（n=1）个作业来说，个作业来说，其平均周转时间为：其平均周转时间为：一个作业的周转时间说明了该作业在系统内停留的时一个作业的周转时间说明了该作业在系统内停留的时间，包含两部分：等待时间、执行时间，即：间，包含两部分：等待时间、执行时间，即：Ti=TwiTri这里，这里，Twi主要指作业主要指作业i由后备状态到执行状态的等待由后备状态到执行状态的等待时间，它不包括作业进入执行状态后的等待时间。时间，它不包括作业进入执行状态后的等待时间。2. 带权周转时间带权周转时间作业的周转时间包含了两个部分，即等待时间和执作业的周转时间包含了两个部分，即等待时间

25、和执行时间。为了更进一步反映调度性能，使用带权周转行时间。为了更进一步反映调度性能，使用带权周转时间的概念。带权周转时间是作业周转时间与作业执时间的概念。带权周转时间是作业周转时间与作业执行时间的比：行时间的比：Wi=Ti/Tri对于被测定作业流所含有的几个作业来说，其平均对于被测定作业流所含有的几个作业来说，其平均带权周转时间为：带权周转时间为：对于分时系统，除了要保证系统吞吐量大、资源利对于分时系统，除了要保证系统吞吐量大、资源利用率高之外，还应保证有用户能够容忍的响应时间。用率高之外，还应保证有用户能够容忍的响应时间。因此，在分时系统中，仅仅用周转时间或带权周转时因此，在分时系统中，仅仅

26、用周转时间或带权周转时间来衡量调度性能是不够的。间来衡量调度性能是不够的。4.3 进进 程程 调调 度度无论是在批处理系统还是分时系统中，用户进程无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数，这将导致用户进程互相争夺数一般都多于处理机数，这将导致用户进程互相争夺处理机。另外，系统进程也同样需要使用处理机。这处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。分配给处于就绪队列中的某一个进程，以使之执行。本节介绍进程调度的功能、进程调度发生的时机以

27、及本节介绍进程调度的功能、进程调度发生的时机以及由进程调度引起的进程上下文切换等。由进程调度引起的进程上下文切换等。4.3.1 进程调度的功能进程调度的功能进程调度的具体功能可总结如下：进程调度的具体功能可总结如下：(1) 记录系统中所有进程的执行情况记录系统中所有进程的执行情况作为进程调度的准备，进程管理模块必须将系统中作为进程调度的准备，进程管理模块必须将系统中各进程的执行情况和状态特征记录在各进程的各进程的执行情况和状态特征记录在各进程的PCB表表中。并且，进程管理模式根据各进程的状态特征和资中。并且，进程管理模式根据各进程的状态特征和资源需求，将各进程的源需求，将各进程的PCB表排成相

28、应的队列并进行动表排成相应的队列并进行动态队列转接。进程调度模块通过态队列转接。进程调度模块通过PCB变化来掌握系统变化来掌握系统中所有进程的执行情况和状态特征，并在适当的时机中所有进程的执行情况和状态特征，并在适当的时机从就绪队列中选择出一个进程占据处理机。从就绪队列中选择出一个进程占据处理机。(2) 选择占有处理机的进程选择占有处理机的进程进程调度的主要功能是按照一定的策略选择一个处进程调度的主要功能是按照一定的策略选择一个处于就绪状态的进程，使其获得处理机执行。根据不同于就绪状态的进程，使其获得处理机执行。根据不同的系统设计目的，有各种各样的选择策略，例如系统的系统设计目的，有各种各样的

29、选择策略，例如系统开销较少的静态优先数调度法，适合于分时系统的轮开销较少的静态优先数调度法，适合于分时系统的轮转法和多级反馈轮转法等。这些选择策略决定了调度转法和多级反馈轮转法等。这些选择策略决定了调度算法的性能。算法的性能。(3) 进行进程上下文切换进行进程上下文切换一个进程的上下文（一个进程的上下文（context）包括进程的状态、包括进程的状态、有关变量和数据结构的值、硬件寄存器的值和有关变量和数据结构的值、硬件寄存器的值和PCB以以及有关程序等。一个进程的执行是在进程的上下文中及有关程序等。一个进程的执行是在进程的上下文中执行。当正在执行的进程由于某种原因要让出处理机执行。当正在执行的

30、进程由于某种原因要让出处理机时，系统要做进程上下文切换，以使另一个进程得以时，系统要做进程上下文切换，以使另一个进程得以执行。当进行上下文切换时，系统要首先检查是否允执行。当进行上下文切换时，系统要首先检查是否允许做上下文切换。然后，系统要保留有关被切换进程许做上下文切换。然后，系统要保留有关被切换进程的足够信息，以便以后切换回该进程时，顺利恢复该的足够信息，以便以后切换回该进程时，顺利恢复该进程的执行。在系统保留了进程的执行。在系统保留了CPU现场之后，调度程序现场之后，调度程序选择一个新的处于就绪状态的进程，并装配该进程的选择一个新的处于就绪状态的进程，并装配该进程的上下文，使上下文，使C

31、PU的控制权转换到被选中进程中。的控制权转换到被选中进程中。4.3.2 进程调度的时机进程调度的时机引起进程调度的原因有以下几类引起进程调度的原因有以下几类：(1) 正在执行的进程执行完毕。正在执行的进程执行完毕。 (2) 执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等待状态。等待状态。(3) 执行中进程调用了执行中进程调用了P原语操作，从而因资源不足而被阻原语操作，从而因资源不足而被阻塞；或调用了塞；或调用了V原语操作激活了等待资源的进程队列。原语操作激活了等待资源的进程队列。(4) 执行中进程提出执行中进程提出IO请求后被阻塞。请求后被阻

32、塞。(5) 在分时系统中时间片已经用完。在分时系统中时间片已经用完。(6) 在执行完系统调用，可调度选择一新的用户进程执行。在执行完系统调用，可调度选择一新的用户进程执行。(7) 就绪队列中的某进程的优先级变得高于当前执行进程的就绪队列中的某进程的优先级变得高于当前执行进程的优先级，从而也将引发进程调度。优先级，从而也将引发进程调度。也可归纳为：也可归纳为：（1）正在执行的进程让出处理机（）正在执行的进程让出处理机（1、2、3、4、5、6）（2）就绪队列中到达一个新的就绪进程（）就绪队列中到达一个新的就绪进程（3）（3）就绪队列中一个进程的优先级升高（）就绪队列中一个进程的优先级升高（7） 可

33、剥夺方式可剥夺方式调度方式调度方式 非剥夺方式非剥夺方式所谓可剥夺方式，即就绪队列中一旦有优先级高所谓可剥夺方式，即就绪队列中一旦有优先级高于当前执行进程优先级的进程存在时，便立即发生进于当前执行进程优先级的进程存在时，便立即发生进程调度，转让处理机。而非剥夺方式或不可剥夺方式程调度，转让处理机。而非剥夺方式或不可剥夺方式即使在就绪队列存在有优先级高于当前执行进程时，即使在就绪队列存在有优先级高于当前执行进程时，当前进程仍将继续占有处理机，直到该进程自己因调当前进程仍将继续占有处理机，直到该进程自己因调用原语操作或等待用原语操作或等待IO而进入阻塞、睡眠状态，或而进入阻塞、睡眠状态，或时间片用

34、完时才重新发生调度让出处理机。时间片用完时才重新发生调度让出处理机。哪种调度方式开销大？哪种调度方式开销大？操作系统将在以上几种原因之一发生的情况下进行进操作系统将在以上几种原因之一发生的情况下进行进程调度。例如，程调度。例如，UNIX SystemV 就是在以下就是在以下5种情况之一种情况之一发生时进行进程调度的：发生时进行进程调度的：(1) 当前进程自己调用当前进程自己调用sleep，wait等进入睡眠状态时。等进入睡眠状态时。(2) 当前进程从系统调用执行结束后返回用户态时，当前进程从系统调用执行结束后返回用户态时，它的优先级已低于其他就绪状态进程，或调度标志被置它的优先级已低于其他就绪

35、状态进程，或调度标志被置位。位。(3) 当前进程在完成中断和陷阱处理后返回用户态时，当前进程在完成中断和陷阱处理后返回用户态时，它的优先级已低于其他就绪状态进程；或调度标志被置它的优先级已低于其他就绪状态进程；或调度标志被置位。位。(4) 时间片用完，而且当前进程的优先级低于其他就时间片用完，而且当前进程的优先级低于其他就绪进程。绪进程。(5) 当前进程调用当前进程调用exit，自我终止时。自我终止时。4.3.3 进程上下文切换进程上下文切换进程上下文由正文段、数据段、硬件寄存器的内进程上下文由正文段、数据段、硬件寄存器的内容以及有关数据结构等组成。硬件寄存器主要包括存容以及有关数据结构等组成

36、。硬件寄存器主要包括存放放CPU将要执行的下条指令虚拟地址的程序计数器将要执行的下条指令虚拟地址的程序计数器PC，指出机器与进程相关联的硬件状态的处理机状指出机器与进程相关联的硬件状态的处理机状态寄存器态寄存器PS，存放过程调用（或系统调用）时所传存放过程调用（或系统调用）时所传递参数的通用寄存器递参数的通用寄存器R以及堆栈指针寄存器以及堆栈指针寄存器S等。数等。数据结构则包括据结构则包括PCB等在内的所有与执行该进程有关的等在内的所有与执行该进程有关的管理和控制用表格、数组、链等。在发生进程调度时，管理和控制用表格、数组、链等。在发生进程调度时，系统要做进程上下文切换。系统要做进程上下文切换

37、。进程上下文切换包括进程上下文切换包括4个步骤：个步骤：(1) 决定是否做上下文切换以及是否允许做上下文决定是否做上下文切换以及是否允许做上下文切换。包括对进程调度原因的检查分析，以及当前执切换。包括对进程调度原因的检查分析，以及当前执行进程的资格和行进程的资格和CPU执行方式的检查等。执行方式的检查等。(2) 保存当前执行进程的上下文。这里所说的当前保存当前执行进程的上下文。这里所说的当前执行进程，实际上是指调用上下文切换程序之前的执执行进程，实际上是指调用上下文切换程序之前的执行进程。如果上下文切换程序不是被那个当前执行进行进程。如果上下文切换程序不是被那个当前执行进程所调用，且不属于该进

38、程，则所保存的上下文应是程所调用，且不属于该进程，则所保存的上下文应是先前执行进程的上下文，或称为先前执行进程的上下文，或称为“老老”进程上下文。进程上下文。显然，上下文切换程序不能破坏显然，上下文切换程序不能破坏“老老”进程的上下文进程的上下文结构。结构。(3) 使用使用4.5节中所述进程调度算法，选择一个处于节中所述进程调度算法，选择一个处于就绪状态进程。就绪状态进程。(4) 恢复或装配所选进程的上下文，将恢复或装配所选进程的上下文，将CPU控制权控制权交给所选进程。交给所选进程。4.3.4 进程调度性能评价进程调度性能评价进程调度虽然是系统内部的低级调度，但进程调进程调度虽然是系统内部的

39、低级调度，但进程调度的优劣直接影响作业调度的性能。反映作业调度优度的优劣直接影响作业调度的性能。反映作业调度优劣的周转时间和平均周转时间只在某种程度上反映了劣的周转时间和平均周转时间只在某种程度上反映了进程调度的性能，例如，其执行时间部分中实际上包进程调度的性能，例如，其执行时间部分中实际上包含有进程等待（包括就绪状态时的等待）时间，而进含有进程等待（包括就绪状态时的等待）时间，而进程等待时间的多少是要依靠进程调度策略和等待事件程等待时间的多少是要依靠进程调度策略和等待事件何时发生来决定的。因此，进程调度性能的衡量是操何时发生来决定的。因此，进程调度性能的衡量是操作系统设计的一个重要指标。作系

40、统设计的一个重要指标。进程调度性能的衡量方法可分为定性和定量两种。进程调度性能的衡量方法可分为定性和定量两种。在定性衡量方面，首先是在定性衡量方面，首先是调度的可靠性调度的可靠性。另外，。另外，简洁简洁性也是衡量进程调度的一个重要指标性也是衡量进程调度的一个重要指标。进程调度的定量评价包括进程调度的定量评价包括CPU的利用率的利用率评价、评价、进进程在就绪队列中的等待时间与执行时间之比程在就绪队列中的等待时间与执行时间之比等。实际等。实际上，由于进程进入就绪队列的随机模型很难确定，而上，由于进程进入就绪队列的随机模型很难确定，而且进程上下文切换等也将影响进程的执行效率，从而且进程上下文切换等也

41、将影响进程的执行效率，从而对进程调度进行解析是很困难的。一般情况下，大多对进程调度进行解析是很困难的。一般情况下，大多利用模拟或测试利用模拟或测试系统响应时间系统响应时间的方法来评价进程调度的方法来评价进程调度的性能。的性能。作业调度与进程调度的关系作业调度与进程调度的关系4.4 调度算法调度算法 包括进程调度、作业调度（两种不同的调度机制）包括进程调度、作业调度（两种不同的调度机制） 关于进程的关于进程的CPU burst 与与 I/O burst： 阵发期阵发期 : CPU burst cycle: 进程使用进程使用CPU计算；计算； I/O burst cycle: 进程使用设备进程使用

42、设备I/O。进程运行行为：进程运行行为： CPU burst, I/O burst, CPU burst, I/O burst, 进程调度：对处于进程调度：对处于CPU burst的进程集合的调度。的进程集合的调度。1. 先来先服务调度算法（先来先服务调度算法（FCFS） First Come First Serve将用户作业或就绪进程按提交顺序或变为就绪状态将用户作业或就绪进程按提交顺序或变为就绪状态的顺序排成队列，并按照先进先出的顺序排成队列，并按照先进先出(先来先服务先来先服务)的方的方式进行调度处理，是一种最简单的方法。式进行调度处理，是一种最简单的方法。特点特点:(1)实现简单实现简

43、单(2)适于作业调度、进程调度适于作业调度、进程调度(3)公平公平?对于执行时间较短的作业或进程来说，等对于执行时间较短的作业或进程来说，等待时间可能较长。待时间可能较长。先来先服务调度算法（续）先来先服务调度算法（续）考虑下面的例子考虑下面的例子:如果作业队列依次如果作业队列依次(几乎同时几乎同时)到达如下到达如下3个作个作业业,按按“先来先服务先来先服务”的方式进行调度完成后，计算平均等待时间：的方式进行调度完成后，计算平均等待时间：作业需运行时间J150J210J31运行情况：运行情况：0506061平均等待时间平均等待时间=（0+50+60）/336.67如果到达顺序为如果到达顺序为J

44、3、J2、J1，运行情况：，运行情况：011161平均等待时间平均等待时间=（0+1+11）/3=4J1J2J3J3J2J12. 轮转调度算法（轮转调度算法（Round Robin）轮转法的基本概念是将轮转法的基本概念是将CPU的处理时间分成固定大小的时间片（的处理时间分成固定大小的时间片（T）。）。如果一个进程在被调度选中之后用完了系统规定的时间片，但未完成要求的如果一个进程在被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有的任务，则它自行释放自己所占有的CPU而排到就绪队列的末尾，等待下一次而排到就绪队列的末尾，等待下一次调度。同时，进程调度程序又去调度当前

45、就绪队列中的第一个进程。调度。同时，进程调度程序又去调度当前就绪队列中的第一个进程。注意注意：（1）该算法）该算法适于进程调度，一般不适于作业调度（为什么？）适于进程调度，一般不适于作业调度（为什么？）（2）适应系统：分时系统适应系统：分时系统图图4.4轮转法调度轮转法调度或进入等待队列或进入等待队列或进入等待队列或进入等待队列时间片到时间片到时间片到时间片到轮转调度算法（续）轮转调度算法（续）例：设某系统时间片值为20，下列进程的调度情况： Process Burst TimeP153 P2 17 P368 P4 24 在实际系统中，通常情况下随着时间的推移，某些进程运行完成本次的CPU B

46、urst而撤离就绪队列，同时还会有新的就绪进程不断地加入。02037577797117121 134154 162P1P2 P3P4 P1 P3P3P1 P3P4（3）时间片长度的取值）时间片长度的取值固定时间片固定时间片时间片长度：时间片长度：几十毫秒几十毫秒 几百毫秒几百毫秒(例如例如 50ms) 过长：过长： 过短：过短：可变时间片可变时间片设系统对响应时间的要求是设系统对响应时间的要求是R，就绪队列中最大进程数为，就绪队列中最大进程数为Nmax。 因为因为 R |T|*Nmax 所以所以 |T| R/Nmax一种可行的办法是，每当一轮调度开始时，系统便根据就绪队列中已有进一种可行的办法

47、是，每当一轮调度开始时，系统便根据就绪队列中已有进程数目计算一次程数目计算一次T值，作为新一轮调度的时间片。这种方法得到的时间片值值，作为新一轮调度的时间片。这种方法得到的时间片值随就绪队列中的进程数变化。随就绪队列中的进程数变化。轮转调度算法（续）轮转调度算法（续）响应速度慢响应速度慢 算法会退化为算法会退化为FCFS；进程切换过于频繁进程切换过于频繁系统开销系统开销(overhead)大。大。3. 最短作业优先调度算法（最短作业优先调度算法（SJF） Shortest Job First最短作业优先法（最短作业优先法（SJF）就是选择那些估计需要）就是选择那些估计需要执行时间最短的作业投入

48、执行。执行时间最短的作业投入执行。例：如果作业队列依次例：如果作业队列依次(几乎同时几乎同时)到达如下到达如下3个作个作业业,按最短作业优先法（按最短作业优先法（SJF）调度。）调度。作业需运行时间J150J210J31011161平均等待时间平均等待时间=（0+1+11）/3=4J3J2J1最短作业优先调度算法（续）最短作业优先调度算法（续）优点：优点：（1）可使得系统在单位时间内处理的作业个数最多）可使得系统在单位时间内处理的作业个数最多吞吐吞吐量最大。量最大。（2）对同一批作业而言，该算法使得作业的平均等待时间最）对同一批作业而言，该算法使得作业的平均等待时间最短。短。缺点：缺点： 可能

49、使得某些运行时间较长的作业得不到调度执行的机会。可能使得某些运行时间较长的作业得不到调度执行的机会。 两种调度方式：两种调度方式： （1）非剥夺方式）非剥夺方式 （2）剥夺方式，即最短剩余时间优先）剥夺方式，即最短剩余时间优先Shortest-Remaining-Time First (SRTF)。最短作业优先调度算法（续）最短作业优先调度算法（续）非剥夺方式示例非剥夺方式示例： Process Arrival Time Burst TimeP10.07 P22.04 P34.01 P45.04平均等待时间 =P1P3P273160P4812(0 + 6 + 3 + 7)/4 = 4最短作业优

50、先调度算法（续）最短作业优先调度算法（续）剥夺方式示例：剥夺方式示例：Process Arrival Time Burst TimeP10.07 P22.04 P34.01 P45.04平均等待时间 =P1P3P242110P457P2P116(9 + 1 + 0 +2)/4 = 3 最短作业优先调度算法（续）最短作业优先调度算法（续） 对运行时间的估计：对运行时间的估计： （1）作业调度：系统要求用户在提交作业时声明估计作业的）作业调度：系统要求用户在提交作业时声明估计作业的运行时间。运行时间。 （2）进程调度：）进程调度：CPU burst时间的确定时间的确定根据进程以前的行根据进程以前的

51、行为推测为推测。 =0时，时， n+1 = n，即估计时间为常量，没考虑实际运行时间即估计时间为常量，没考虑实际运行时间 =1时，时， n+1 = tn，即估计时间为上次的实际运行时间即估计时间为上次的实际运行时间通常，可以选择通常，可以选择 =1/2 即即 n+1 =( n+ tn)/2最短作业优先调度算法（续）最短作业优先调度算法（续）例：现有某进程，各例：现有某进程，各CPU burst实际时间为：实际时间为：6、4、6、4、13、13、13。给出系统每次调度前给出系统每次调度前CPU burst的估计值。的估计值。系统设定的系统设定的 1=10 ，选择选择 =1/2。 2= 3= 4=

52、 5= 6= 7= 8=(10+6)/2=8(8+4)/2=6(6+6)/2=6(6+4)/2=5(5+13)/2=9(9+13)/2=11(11+13)/2=12 4. 最高响应比优先调度算法（最高响应比优先调度算法（HRN） Highest Response ratio Next 最高响应比优先法（最高响应比优先法（HRN）是对）是对FCFS方式和方式和SJF 方式的一方式的一种综合平衡。种综合平衡。 响应比响应比R定义如下：定义如下：R=(W+T)/T=1+W/T 其中其中T为该作业估计需要的执行时间，为该作业估计需要的执行时间，W为作业的等待时为作业的等待时间。间。 每当要进行作业调度

53、时，系统计算每个作业的响应比，选每当要进行作业调度时，系统计算每个作业的响应比，选择其中择其中R最大者投入执行。最大者投入执行。 这种算法是介于这种算法是介于FCFS和和SJF 之间的一种折中算法。由于之间的一种折中算法。由于每次调度前要计算响应比，系统开销也要相应增加。每次调度前要计算响应比，系统开销也要相应增加。 最高响应比优先调度算法（续最高响应比优先调度算法（续） R=(W+T)/T=1+W/T 考虑下面的例子考虑下面的例子作业到达时间需运行时间开始时间完成时间等待时间J18:0050分8:008:500分J28:3020分J38:4015分J48:555分8:50 9:10 20分分

54、9:15 9:30 35分分9:10 9:15 15分分 平均等待时间平均等待时间(0203515)417.5 分别采用分别采用FCFS、SJF算法进行调度，各自的平均等待算法进行调度，各自的平均等待时间？反映了什么问题？时间？反映了什么问题？5. 优先级调度算法（优先级调度算法（HPF） Highest Priority First 系统或用户按某种原则为作业或进程指定一个优先级，系统按优先级进系统或用户按某种原则为作业或进程指定一个优先级，系统按优先级进行调度。行调度。 优先级法可被用于作业或进程的调度策略。优先级法可被用于作业或进程的调度策略。 （1）优先级的确定）优先级的确定 静态法：

55、在作业或进程开始执行之前就确定它们的优先级，一旦静态法：在作业或进程开始执行之前就确定它们的优先级，一旦开始执行之后就不能改变。开始执行之后就不能改变。 动态法：随着作业或进程的执行，其优先级不断变化。动态法：随着作业或进程的执行，其优先级不断变化。 （2）影响优先级因素）影响优先级因素 外部因素：任务的紧迫程度、付费、进程类型外部因素：任务的紧迫程度、付费、进程类型(系统、用户进程系统、用户进程)。例如，在操作系统中，对于键盘中断的处理优先级和对于电源掉电中断的例如，在操作系统中，对于键盘中断的处理优先级和对于电源掉电中断的处理优先级是不相同的。处理优先级是不相同的。 内部因素：作业类型（内

56、部因素：作业类型（IO型、计算型）、资源需求型、计算型）、资源需求 （3）剥夺）剥夺非剥夺优先级调度非剥夺优先级调度 非剥夺方式：获得处理机的进程，直至终止、等待非剥夺方式：获得处理机的进程，直至终止、等待 剥夺方式：获得处理机的进程，直至终止、等待、出现高优先级剥夺方式：获得处理机的进程，直至终止、等待、出现高优先级的就绪进程的就绪进程 优先级调度算法（优先级调度算法（续）续） 其实优先级调度算法仅仅是一种思想，前面介绍的所有算其实优先级调度算法仅仅是一种思想，前面介绍的所有算法都可看成是优先级调度。法都可看成是优先级调度。 UNIX例子：可剥夺、动态优先级调度例子：可剥夺、动态优先级调度

57、优先级计算公式：优先级计算公式： p_pri=min127, USER+p_cpu/16+p_nice 定义定义USER=100； p_cpu: 运行进程每运行进程每20ms加加1（优先级降低）（优先级降低），其它，其它就绪就绪进程每进程每1200ms减减10（优先级提高）；（优先级提高）； p_nice: 可以通过系统调用可以通过系统调用nice()修改的量修改的量。 优先级调度算法（优先级调度算法（续）续）例如：线性优先级调度策略（例如：线性优先级调度策略（selfish round robin）使用轮转法调度进程时，新创建的进程也放入就绪使用轮转法调度进程时，新创建的进程也放入就绪队列末

58、尾享受平等的处理机时间片。这对于执行时间队列末尾享受平等的处理机时间片。这对于执行时间长的进程来说是有点不公平的，因为它们需要多个时长的进程来说是有点不公平的，因为它们需要多个时间片才能完成。因此，线性优先级调度策略采用如下间片才能完成。因此，线性优先级调度策略采用如下方式，即新创建的进程按方式，即新创建的进程按FCFS方式排成就绪队列，而方式排成就绪队列，而其他已得到过时间片服务的进程也按其他已得到过时间片服务的进程也按FCFS方式排成另方式排成另一个就绪队列或称享受服务队列一个就绪队列或称享受服务队列(图图4.5）。）。图图4.5 线性优先级调度线性优先级调度对于这两个不同队列中的进程，设

59、新创建进程就绪对于这两个不同队列中的进程，设新创建进程就绪队列中进程的优先级队列中进程的优先级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) (t

60、1tb0 的条的条件是必要的。否则，当件是必要的。否则，当ba0 时，两个不同队列中的时，两个不同队列中的就绪态进程的优先级将永远不会相等，从而，在享受就绪态进程的优先级将永远不会相等，从而，在享受服务进程队列中永远只有一个进程。因此，上述线性服务进程队列中永远只有一个进程。因此，上述线性优先级调度策略退回到优先级调度策略退回到FCFS方式。另外，如果方式。另外，如果ab=0，则线性优先级调度策略退回到轮转法调度方则线性优先级调度策略退回到轮转法调度方式。事实上，线性优先级调度策略是一种介于轮转法式。事实上，线性优先级调度策略是一种介于轮转法和和FCFS方式之间的调度策略。这几种方式的调度性方

61、式之间的调度策略。这几种方式的调度性能，将在下一节中更进一步讨论。能，将在下一节中更进一步讨论。 6.多级队列算法多级队列算法(MLQ)Multilevel Queue 多个就绪队列，进程所属的队列固定。不同就绪队列具有多个就绪队列，进程所属的队列固定。不同就绪队列具有不同优先级；各个队列拥有自己的调度算法；处理机要在不不同优先级；各个队列拥有自己的调度算法；处理机要在不同队列中调度。同队列中调度。 例如：某通用系统例如：某通用系统 队列队列1 1：实时进程就绪队列（：实时进程就绪队列（HPF） 队列队列2 2：分时进程就绪队列（：分时进程就绪队列（RR） 队列队列3 3：批处理进程就绪队列（

62、：批处理进程就绪队列（HPF） 7. 多级反馈队列调度算法（多级反馈队列调度算法（MFQ） Multilevel Feedback Queue （1）多个就绪进程队列）多个就绪进程队列 （2）进程会在不同队列中移动）进程会在不同队列中移动 （3）该算法的关键点：）该算法的关键点： 就绪队列个数就绪队列个数 每个队列采用的调度算法每个队列采用的调度算法 何时提升、降低进程优先级何时提升、降低进程优先级 进程就绪该进程进入哪个就绪队列进程就绪该进程进入哪个就绪队列Q1（RR，HPF）Q2（RR，HPF）Qn（RR，HPF）运行运行s1时间片时间片运行运行s2时间片时间片.创建创建唤醒唤醒高高 优优

63、先先级级 低低运行运行sn时间片时间片多级反馈队列调度算法（续）多级反馈队列调度算法（续）一个实例一个实例: n个就绪队列；每个队列采用类似的个就绪队列；每个队列采用类似的RR算法；队列之间采用剥算法；队列之间采用剥夺夺HPF算法；算法；Q1优先级最高，对应的时间片优先级最高，对应的时间片S1最小，最小，Qn优先级最低，优先级最低，对应的时间片对应的时间片Sn最大；就绪进程进入最大；就绪进程进入Q1就绪队列。就绪队列。运行结束退出运行结束退出运行结束退出运行结束退出运行结束退出运行结束退出小小 时时间间片片大大（1）该算法宗旨：以）该算法宗旨：以IO为主的进程响应速度较快，以计算为主的进程响应

64、速度较快，以计算为主的进程运行一段时间后，会下降到低优先级队列运行。为主的进程运行一段时间后，会下降到低优先级队列运行。（2）系统效率较高、资源利用率高。）系统效率较高、资源利用率高。（3）算法的改进：）算法的改进： 考虑某些以计算为主的进程，偶尔一次考虑某些以计算为主的进程，偶尔一次IO； 开始时以计算为主，后来变为以开始时以计算为主，后来变为以IO为主。为主。 改进方法：改进方法： 每一次每一次IO结束后，再次就绪时进入高一级就绪队列。例结束后，再次就绪时进入高一级就绪队列。例如如VAX VMS操作系统的处理。操作系统的处理。 多级反馈队列调度算法（续）多级反馈队列调度算法（续）4.5 算

65、算 法法 评评 价价本节主要利用解析技术从数学上分析几种主要调本节主要利用解析技术从数学上分析几种主要调度方法的性能。度方法的性能。4.5.1 FCFS方式的调度性能分析方式的调度性能分析设处理机或系统资源为服务器，一个进程或一个设处理机或系统资源为服务器，一个进程或一个作业为享受该服务器服务的顾客。当这些顾客按作业为享受该服务器服务的顾客。当这些顾客按FCFS方式排队享受服务的系统模型如图方式排队享受服务的系统模型如图4.7。图图4.7 FCFS方式的评价模型方式的评价模型这里，假定该系统模型中只有一个服务器。这里，假定该系统模型中只有一个服务器。设新顾客到达等待队列的时间与系统的当前状态、

66、以前的顾客设新顾客到达等待队列的时间与系统的当前状态、以前的顾客到达时间都无关，也就是新顾客到达系统的时间是服从泊松分到达时间都无关，也就是新顾客到达系统的时间是服从泊松分布的。设布的。设为到达率，则在单位时间内为到达率，则在单位时间内x个顾客到达的概率为：个顾客到达的概率为：P(x)=e-x/x!单位时间内顾客到达的期望值，即算术平均值为：单位时间内顾客到达的期望值，即算术平均值为： （ y=x-1）由于由于所以，所以，E(x)也即单位时间内顾客到达的平均值等于其到达率。也即单位时间内顾客到达的平均值等于其到达率。设服务器为顾客提供服务的概率也服从泊松分布，且设服务器为顾客提供服务的概率也服

67、从泊松分布，且为服务率，则单位时间内为服务率，则单位时间内x 个顾客被服务的概率是个顾客被服务的概率是P(x)=e-x/x!同理，单位时间内被服务顾客个数的算术平均值等于其服同理，单位时间内被服务顾客个数的算术平均值等于其服务率务率。将单位时间换成任意时间将单位时间换成任意时间t，可得到在已知时间可得到在已知时间t 内内x 个顾个顾客到达的概率为：客到达的概率为：P(x(t)=et(t)x/x!在在t时间内，一个顾客也不到达的概率为：时间内，一个顾客也不到达的概率为：P(0)=e-t从而，从而，t时间内至少到达一个顾客的概率为：时间内至少到达一个顾客的概率为：P(x(t)0)=1-e-t如果把

68、时间如果把时间t 换成固定的时间间隔换成固定的时间间隔，则有，在任何时间则有，在任何时间间隔间隔内至少有一个到达发生的概率仍为内至少有一个到达发生的概率仍为1-e-t。这个概率和上这个概率和上一次顾客到达的时刻无关。新顾客在下一个一次顾客到达的时刻无关。新顾客在下一个时间内到达的概时间内到达的概率和以前顾客的到达无关，这个特性称为无记忆特性或马尔率和以前顾客的到达无关，这个特性称为无记忆特性或马尔可夫性质。利用该性质，可以简化顾客和服务的排队模型。可夫性质。利用该性质，可以简化顾客和服务的排队模型。由于服务器的服务概率也服从泊松分布，也可推出它在由于服务器的服务概率也服从泊松分布，也可推出它在

69、时间间隔内至少为一个顾客服务的概率为时间间隔内至少为一个顾客服务的概率为1-e-t，且与以前的且与以前的服务过程无关。因此，服务器的服务特性也是满足马尔可夫服务过程无关。因此，服务器的服务特性也是满足马尔可夫性质的。性质的。由于由于 P(x(t)0)=1-e-t其密度函数其密度函数 P(x(t)0)=e-tt的的期望值等于期望值等于E(t)0te-tdt=-te-t|0+0e-t=1/即两个连续到达的顾客之间的平均时间间隔为即两个连续到达的顾客之间的平均时间间隔为1。同理，同理，可得服务器服务时间的平均值为可得服务器服务时间的平均值为1。显然，只有当显然，只有当 11 也就是也就是 时时系统才

70、是稳定的。否则，等待服务队列将无限增长。系统才是稳定的。否则，等待服务队列将无限增长。设设i为系统的一个状态，表示等待服务的等待队列中有为系统的一个状态，表示等待服务的等待队列中有i-1个顾客，服务器中有个顾客，服务器中有1 个顾客存在。由概率密度函数可知，在个顾客存在。由概率密度函数可知，在dt时间内时间内1个新顾客到达的概率是：个新顾客到达的概率是： P(dt时间内时间内1个顾客到达个顾客到达)e-dtdt将将上式做多项式展开得：上式做多项式展开得：e-dtdtdtO(dt2)同理可得，在同理可得，在dt时间内服务器为时间内服务器为1个顾客提供服务的概率是个顾客提供服务的概率是：P(dt时

71、间内时间内1个顾客离开个顾客离开)dtO(dt2)省略以上两式的二次方项，在省略以上两式的二次方项，在dt时间内时间内1个顾客到达或离开的个顾客到达或离开的概率为：概率为：P(dt时间内时间内1个顾客到达个顾客到达)=dtP(dt时间内时间内1个顾客离开个顾客离开)=dt对于对于i0时，有：时，有： P(dt时间内时间内1个顾客离开个顾客离开)0在在dt时间内，顾客一个也不到达和顾客一个也不离开的概率为：时间内，顾客一个也不到达和顾客一个也不离开的概率为：1-P(dt时间内时间内1个顾客到达个顾客到达) -P(dt时间内时间内1个顾客离开个顾客离开) -P(dt时间内时间内2个以上顾客到达个以

72、上顾客到达) -P(dt时间内时间内2个以上顾客离开个以上顾客离开)。由于上式的后两项实际上是由于上式的后两项实际上是dt的二次方以上的函数，从的二次方以上的函数，从而上式可合并为：而上式可合并为：P(dt时间内不发生变化时间内不发生变化)1-() dt-O(dt2)(i0)或或 P(dt时间内不发生变化时间内不发生变化)1-dt-O(dt2) (i0)忽略二次方项，可得状态变化图如图忽略二次方项，可得状态变化图如图4.8。图图4.8 状态转换图状态转换图设系统在设系统在t+dt时间内处于状态时间内处于状态i的概率为的概率为Pi(t+dt)，则由状态则由状态转换图有：转换图有：Pi(tdt)1

73、-() dt Pi(t)dt Pi-1(t)dt Pi+1(t) 式中式中i1。对于对于i0时，有：时，有：P0(tdt)(1-dt)P0(t)dt P1(t)当系统到达稳定状态时，上述概率将会趋于一个常量，当系统到达稳定状态时，上述概率将会趋于一个常量，Pi(tdt)的导数为的导数为0，即：，即：Pi(tdt) -()Pi(t)Pi-1 (t) Pi+1 (t)0P0(tdt)-P0(t)P1(t)0即：即： P1() P0(t) () Pi(t)Pi-1 (t) Pi+1 (t)令令，采用代入法可得：采用代入法可得：Pi(t)iP0(t) 另外，系统运行中的任一时刻总是处于图另外，系统运行

74、中的任一时刻总是处于图4.8 所示状态图中的所示状态图中的任一状态中，从而有：任一状态中，从而有：由此可得：由此可得：由于在由于在1 时有：时有： 从而有：从而有： P0(t)1- 即，在稳态条件下，系统内不存在顾客的概率为即，在稳态条件下，系统内不存在顾客的概率为1-(-)，而系统内存在顾客的概率为而系统内存在顾客的概率为。系统内顾客的算术平系统内顾客的算术平均值是：均值是：把上述按把上述按FCFS方式排列和调度，并只有一个服务器的系方式排列和调度，并只有一个服务器的系统称为统称为M/M/1系统。第一个字母系统。第一个字母M表示顾客到达时间间隔是指数表示顾客到达时间间隔是指数分布，具有马尔可

75、夫性质，第二个字母分布，具有马尔可夫性质，第二个字母M表示从服务器离开的表示从服务器离开的顾客的时间间隔服从指数分布，具有马尔可夫性质，第三个字顾客的时间间隔服从指数分布，具有马尔可夫性质，第三个字母母1表示只有一个服务器。表示只有一个服务器。设响应时间设响应时间R为从顾客到达等待队列后开始到离开服务器的为从顾客到达等待队列后开始到离开服务器的时间，则在系统进入稳定状态之后，系统中的顾客数时间，则在系统进入稳定状态之后，系统中的顾客数n 和平均响和平均响应时间之间存在一个非常简单的关系，即应时间之间存在一个非常简单的关系，即n=R，为顾客的平均为顾客的平均到达率。该公式称为到达率。该公式称为L

76、ittle结果（结果（Littles result），），是一个在是一个在系统分析中广泛使用的公式。系统分析中广泛使用的公式。利用利用Little结果可求出结果可求出M/M/1系统的平均响应时间：系统的平均响应时间：Rn(1(1-)1(1-)平均响应时间和平均响应时间和的关系图如图的关系图如图4.9。图图4.9 平均响应时间平均响应时间R和和的关系的关系由图由图4.9可以看出，可以看出，M/M/1系统的服务性能是由系统的服务性能是由决定决定的。如果的。如果趋近趋近1，即，即趋近趋近，则响应时间急剧增大，则响应时间急剧增大，系统性能变差。而当系统性能变差。而当小于小于1/2 时，等待队列中为空的

77、时，等待队列中为空的可能性较大，因为平均响应时间小于平均服务时间的可能性较大，因为平均响应时间小于平均服务时间的2倍。倍。下面再来看看下面再来看看M/M/1系统对短作业或短进程的影响。系统对短作业或短进程的影响。设短作业的到达率和服务率分别为（设短作业的到达率和服务率分别为（1，1），），长作长作业的到达率和服务率为（业的到达率和服务率为（2，2），），且二者都服从泊松且二者都服从泊松分布。二者的合成仍是泊松过程，其到达率分布。二者的合成仍是泊松过程，其到达率12，平均服务时间为：平均服务时间为：11(12)*11 2(12)*121(12)*(11 22) 从而有：从而有：11 2212一般

78、来说，短作业的服务时间一般来说，短作业的服务时间11远小于长作业的远小于长作业的服务时间服务时间12。FCFS调度策略时有响应时间调度策略时有响应时间R为：为：R1*(1-)其中，其中，1 2，12由于由于和和中包含了中包含了1，2，1和和2，所有作业的平均所有作业的平均响应时间相同，从而，短作业在系统中的驻留平均时响应时间相同，从而，短作业在系统中的驻留平均时间与长作业的驻留平均时间相同，这对短作业是不利间与长作业的驻留平均时间相同，这对短作业是不利的。的。4.5.2 轮转法调度性能评价轮转法调度性能评价轮转法调度时的顾客到达率要大大高于轮转法调度时的顾客到达率要大大高于FCFS方式。方式。

79、设时间片为设时间片为q，服务时间平均值为服务时间平均值为1，每个顾客平每个顾客平均需要均需要k 个时间片。从而有，个时间片。从而有，1k*q。如果某个如果某个顾客刚好需要顾客刚好需要k 个时间片的服务时间，则这个顾客就个时间片的服务时间，则这个顾客就会到达等待队列会到达等待队列k 次（次（k1）。）。对于短作业，对于短作业，11k1*q，而对于长作业，而对于长作业，12k2*q。设新顾客的到达率等于设新顾客的到达率等于12，服务时间：服务时间：1(1) k1*q(2) k2*q(1)(1122)从而有：从而有： 12这看上去好像在平均响应时间方面，轮转法和这看上去好像在平均响应时间方面，轮转法

80、和FCFS调度方式上变化不大。但事实上，在等待队列调度方式上变化不大。但事实上，在等待队列中享受过中享受过k次时间片服务的顾客的响应时间是：次时间片服务的顾客的响应时间是：R(k) (1-) 1(1-)k*q (1-)也就是说，响应时间与服务时间成正比。从而，所也就是说，响应时间与服务时间成正比。从而，所需服务时间短的顾客的响应时间将会小于所需服务时需服务时间短的顾客的响应时间将会小于所需服务时间长的顾客的响应时间。因此，轮转法在响应时间上间长的顾客的响应时间。因此，轮转法在响应时间上要优于要优于FCFS调度方式。调度方式。4.5.3 线性优先级法的调度性能线性优先级法的调度性能线性优先级调度

81、策略（线性优先级调度策略（SRR）是介于是介于FCFS方式和方式和轮转法之间的一种调度策略。轮转法之间的一种调度策略。SRR方式把新到达的顾方式把新到达的顾客首先送入等待室休息一段时间后，再送到等待服务客首先送入等待室休息一段时间后，再送到等待服务队列。（如图队列。（如图4.10）设顾客到达等待室的到达率为设顾客到达等待室的到达率为，到达等待队列的到达等待队列的到达率为到达率为。依赖于等待室的到达率依赖于等待室的到达率和线性参数和线性参数r，其中其中r1-ba。由由4.4 节可知，有节可知，有ab，且，且a和和b分分别为等待室内顾客和等待队列中顾客优先级的线性增别为等待室内顾客和等待队列中顾客

82、优先级的线性增加系数。加系数。图图4.10 线性优先级调度的评价模型线性优先级调度的评价模型设设t1和和t2分别为两顾客接连到达等待室的时间，则分别为两顾客接连到达等待室的时间，则有：有： 1t2 -t1设设t和和t分别为两顾客从等待室接连到达等待分别为两顾客从等待室接连到达等待队列的时间，则有：队列的时间，则有： 1t-t由图由图4.6可知，有：可知，有： (t2-t1)(t2-t)r即：即： r，r由于由于r1，所以等待室以所以等待室以r的比率滞留到达的顾客。的比率滞留到达的顾客。线性优先级调度系统的响应时间是线性优先级调度系统的响应时间是s*r。且且s*r由等待室的平均等待时间由等待室的

83、平均等待时间d和进入等待队列后得到和进入等待队列后得到服务的平均响应时间服务的平均响应时间s 之和组成。由对轮转法的分之和组成。由对轮转法的分析，则有：析，则有： s1(-)r*s1(-)从而：从而： dr*s-s1(-) -1(-) (-) (-)(-)另外，由轮转法可知：另外，由轮转法可知： s(k)kq(1 -)其中，其中，。从而有：从而有：sr(k) ds(k) (-)(-)(-) kq(1-)1 (-) -(1 -kq)(-) 其中其中k是一个顾客享受服务的时间片的次数，是一个顾客享受服务的时间片的次数，q是时间片常是时间片常数。数。可以比较一下可以比较一下FCFS方式、方式、SRR

84、方式以及轮转法等三种调度方方式以及轮转法等三种调度方式的平均响应时间。式的平均响应时间。FCFS方式时，我们有：方式时，我们有： fc(k)1 (-)轮转法时有：轮转法时有： rr(k)k q(-)SRR方式时，则响应时间为：方式时，则响应时间为： sr(k)1 (-) -(1 -k q)(-)如果如果kq1，即顾客的服务时间由其平均服务时间相等的即顾客的服务时间由其平均服务时间相等的话，则话，则sr(k)中第二项变为中第二项变为0，上述，上述fc(k)rr(k)sr(k)。当然，对于需要服务时间短的顾客来说，有当然，对于需要服务时间短的顾客来说，有kq1，而对而对于需要服务时间长的顾客来说，

85、则有于需要服务时间长的顾客来说，则有kq 1。从而，对于服从而，对于服务时间短的顾客其响应时间：务时间短的顾客其响应时间：rrsrfc而而对于服务时间长的顾客来说，其响应时间则为：对于服务时间长的顾客来说，其响应时间则为：fcsrrr上面只是从响应时间的角度对几种常见的调度策略进行了评上面只是从响应时间的角度对几种常见的调度策略进行了评价分析。除了响应时间之外，价分析。除了响应时间之外，CPU利用率也是评价调度性能的利用率也是评价调度性能的另一个标准。另一个标准。4.6 实时系统调度方法实时系统调度方法4.6.1 实时系统的特点实时系统的特点 随着移动通信和网络计算技术的发展，实时系统随着移动

86、通信和网络计算技术的发展，实时系统正变得越来越重要。操作系统是实时系统中最重要的正变得越来越重要。操作系统是实时系统中最重要的部分之一。它负责在用户要求的时限内进行事件处理部分之一。它负责在用户要求的时限内进行事件处理和控制。和控制。 实时系统与其他系统的最大区别在于，其处理和实时系统与其他系统的最大区别在于，其处理和控制的正确性不仅仅取决于计算的逻辑结果，而且取控制的正确性不仅仅取决于计算的逻辑结果，而且取决于计算和处理结果产生的时间。因此，实时系统的决于计算和处理结果产生的时间。因此，实时系统的调度与工业生产中的生产过程调度有许多相同之处，调度与工业生产中的生产过程调度有许多相同之处，即把

87、给定的任务，按所要求的时限调配到相应的设备即把给定的任务，按所要求的时限调配到相应的设备上去处理完成。上去处理完成。 根据对处理外部事件的时限要求，实时系统中处理的外部根据对处理外部事件的时限要求，实时系统中处理的外部事件可分为硬实时任务和软实时任务事件可分为硬实时任务和软实时任务。硬实时任务要求系统硬实时任务要求系统必须完全满足任务的时限要求。软实时任务则允许系统对任必须完全满足任务的时限要求。软实时任务则允许系统对任务的时限要求有一定的延迟，其时限要求只是一个相对条件。务的时限要求有一定的延迟，其时限要求只是一个相对条件。 实时系统的另一个特点是它所处理的外部任务可分为周期实时系统的另一个

88、特点是它所处理的外部任务可分为周期性的与非周期性的两大类。对于非周期性任务来说，存在有性的与非周期性的两大类。对于非周期性任务来说，存在有一个完成或开始进行处理时限，而周期性任务只要求在周期一个完成或开始进行处理时限，而周期性任务只要求在周期T内完成或开始进行处理。内完成或开始进行处理。 一般来说，实时操作系统具有以下特点：一般来说，实时操作系统具有以下特点： (1) 有限等待时间（决定性）有限等待时间（决定性） (2) 有限响应时间有限响应时间 (3) 用户控制用户控制(4) 可靠性高可靠性高(5) 系统出错处理能力强系统出错处理能力强与分时系统的多个进程并发执行相比，分时系统与分时系统的多

89、个进程并发执行相比，分时系统中并发执行的进程具有不确定性，其执行顺序与执行中并发执行的进程具有不确定性，其执行顺序与执行环境有关。实时系统则不然，它要求所有的进程在处环境有关。实时系统则不然，它要求所有的进程在处理事件时，都必须在有限时间内开始处理。这一特性理事件时，都必须在有限时间内开始处理。这一特性又被称为实时系统的决定性特性。又被称为实时系统的决定性特性。实时系统的有限响应时间特性是指从系统响应外实时系统的有限响应时间特性是指从系统响应外部事件开始，必须在有限时间内处理完毕。部事件开始，必须在有限时间内处理完毕。另外，在分时系统的非实时系统中，用户不能参另外，在分时系统的非实时系统中，用

90、户不能参与对进程调度的控制。在实时系统中，用户可以控制与对进程调度的控制。在实时系统中，用户可以控制进程的优先级并选择相应的调度算法，从而达到对进进程的优先级并选择相应的调度算法，从而达到对进程执行先后顺序的控制。程执行先后顺序的控制。实时系统要求很高的可靠性。实时系统主要是对实时系统要求很高的可靠性。实时系统主要是对外部事件进行处理和控制，例如导弹系统的控制，这外部事件进行处理和控制，例如导弹系统的控制，这样的系统不允许出现控制错误。样的系统不允许出现控制错误。实时系统要求系统在出错时，既能够处理所发生实时系统要求系统在出错时，既能够处理所发生的错误，又不影响当前正在执行的用户应用。的错误，

91、又不影响当前正在执行的用户应用。上述特性要求实时操作系统具有下述能力：上述特性要求实时操作系统具有下述能力：(1) 很快的进程或线程切换速度很快的进程或线程切换速度进程或线程切换速度是实时系统设计的核心。调进程或线程切换速度是实时系统设计的核心。调度算法的设计原则是满足所有硬实时任务的处理时限度算法的设计原则是满足所有硬实时任务的处理时限和尽可能多地满足软实时任务的处理时限。和尽可能多地满足软实时任务的处理时限。(2) 快速的外部中断响应能力快速的外部中断响应能力(3) 基于优先级的随时抢先式调度策略基于优先级的随时抢先式调度策略基于优先级的调度策略大致有以下基于优先级的调度策略大致有以下4种

92、。即：种。即： 优先级优先级+时间片轮转调度策略；时间片轮转调度策略； 基于优先级的非抢先式调度策略；基于优先级的非抢先式调度策略； 基于优先级的固定点抢先式调度策略；基于优先级的固定点抢先式调度策略； 基于优先级的随时抢先式调度策略。基于优先级的随时抢先式调度策略。对于调度策略对于调度策略来说，因为调度必须在时间片到来来说，因为调度必须在时间片到来时才能发生，实时进程必须等待占有处理机的进程执时才能发生，实时进程必须等待占有处理机的进程执行到时间片结束时才能获得处理机。因此，这种方法行到时间片结束时才能获得处理机。因此，这种方法不能用作实时调度。同理，基于优先级的非抢先式调不能用作实时调度。

93、同理，基于优先级的非抢先式调度策略也不能用作实时调度，因为高优先级的实时进度策略也不能用作实时调度，因为高优先级的实时进程，只有在当前执行进程自动让出处理机之后，才能程，只有在当前执行进程自动让出处理机之后，才能获得处理机。获得处理机。基于优先级的固定点抢先式调度方式与基于优先级基于优先级的固定点抢先式调度方式与基于优先级的随时抢先式调度策略是实时系统的主要调度策略。的随时抢先式调度策略是实时系统的主要调度策略。基于优先级的固定点抢先式调度方式与优先级基于优先级的固定点抢先式调度方式与优先级+时间时间片轮转调度方式有相似之处，其主要区别在于允许抢片轮转调度方式有相似之处，其主要区别在于允许抢先

94、的固定点间隔要比时间片小得多，并保证能满足所先的固定点间隔要比时间片小得多，并保证能满足所有硬实时的处理时限。有硬实时的处理时限。4.6.2 实时调度算法的分类实时调度算法的分类17把实时调度算法分为把实时调度算法分为4类，并介绍了时限调类，并介绍了时限调度算法和频率单调调度算法。度算法和频率单调调度算法。4类实时调度算法：类实时调度算法：(1) 静态表格驱动类静态表格驱动类静态表格驱动类的实时调度算法，对可能的调度静态表格驱动类的实时调度算法，对可能的调度条件和参数进行静态分析，并将分析结果作为实际调条件和参数进行静态分析，并将分析结果作为实际调度结果。这类调度方法多用于调度处理周期性任务，

95、度结果。这类调度方法多用于调度处理周期性任务，其主要分析参数为周期，执行时间、周期行结束时限其主要分析参数为周期，执行时间、周期行结束时限和任务优先级等。最早时限优先法是比较典型的静态和任务优先级等。最早时限优先法是比较典型的静态表格驱动算法。这里，最早时限优先法是优先调度时表格驱动算法。这里，最早时限优先法是优先调度时限最早的任务获得处理机的调度方法。限最早的任务获得处理机的调度方法。(2) 静态优先级驱动抢先式调度算法类静态优先级驱动抢先式调度算法类该类算法也进行静态分析，不过，它们的静态分析该类算法也进行静态分析，不过，它们的静态分析不直接产生调度结果，而只用来指定任务的优先级。不直接产

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

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

98、任一种时限。时时限调度算法可以使用任一种时限。时限调度算法不可用于周期性调度与非周期性调度两种。限调度算法不可用于周期性调度与非周期性调度两种。时限调度算法所需要的相关输入信息包括以下几种：时限调度算法所需要的相关输入信息包括以下几种：(1) 任务就绪时间或事件到达时间任务就绪时间或事件到达时间指的是进程进入就绪状态，可以被调度执行的时间。对于指的是进程进入就绪状态，可以被调度执行的时间。对于周期性任务来说，该时间是可以预知的，而且时间间隔是周周期性任务来说，该时间是可以预知的，而且时间间隔是周期性的。对于非周期性任务来说，这些时间可能是可预知的，期性的。对于非周期性任务来说，这些时间可能是可

99、预知的，但大部分时候是不可预知的，需要事件发生来驱动。但大部分时候是不可预知的，需要事件发生来驱动。(2) 开始时限开始时限处理机必须开始对任务进行处理的时限。处理机必须开始对任务进行处理的时限。(3) 完成时限完成时限指的是任务必须完成的时间指的是任务必须完成的时间(4) 处理时间处理时间完成相关任务所需占用处理机的时间。完成相关任务所需占用处理机的时间。(5) 资源需求资源需求除了处理机之处，另外还需要的其他硬软件资源。除了处理机之处，另外还需要的其他硬软件资源。如果所处理的任务有处理机之外的其他资源需求，则如果所处理的任务有处理机之外的其他资源需求，则调度算法要相对复杂得多。调度算法要相

100、对复杂得多。(6) 优先级优先级可由分析计算后获得，也可根据时限要求，由用户可由分析计算后获得，也可根据时限要求，由用户指定。指定。时限调度算法的基本思想是：按用户的时限要求顺序设置时限调度算法的基本思想是：按用户的时限要求顺序设置优先级，优先级高者占据处理机，也就是说，时限要求最近优先级，优先级高者占据处理机，也就是说，时限要求最近的任务优先占有处理机。的任务优先占有处理机。时限调度是抢先式的。抢先式时时限调度是抢先式的。抢先式时限调度算法必须把新到达任务的时限要求和当前正在执行任限调度算法必须把新到达任务的时限要求和当前正在执行任务的时限要求进行比较，如果新到达任务的时限要求更近，务的时限

101、要求进行比较，如果新到达任务的时限要求更近，则应执行新到达的任务。则应执行新到达的任务。下面是用时限调度算法调度周期性实时任务的例子。下面是用时限调度算法调度周期性实时任务的例子。设实时系统从两个不同的数据源设实时系统从两个不同的数据源DA和和D周期性地收集数周期性地收集数据并进行处理，其中据并进行处理，其中DA的时限要求以的时限要求以30 ms为周期，为周期，DB的时的时限要求以限要求以75 ms为周期。设为周期。设DA所需处理时限为所需处理时限为15 ms，DB所需所需处理时限为处理时限为38 ms，则与则与DA和和DB有关进程的事件发生时限有关进程的事件发生时限（就绪时限），执行时限以及

102、结束时限如图（就绪时限），执行时限以及结束时限如图4.11所示。所示。图图4.11 周期性任务的预计发生、执行与结束时限周期性任务的预计发生、执行与结束时限如果使用时限调度算法，并按最近结束时限优先如果使用时限调度算法，并按最近结束时限优先级最高的方法进行排列，可以给出图级最高的方法进行排列，可以给出图4.11所示各进程所示各进程的调度顺序和相对时间。（如图的调度顺序和相对时间。（如图4.12）图图4.12 时限调度算法给出的调度顺序时限调度算法给出的调度顺序如图如图4.12所示，在开始时，进程所示，在开始时，进程DA（1）和）和DB（1）的结束时限比较结果，的结束时限比较结果，DA（1）的结

103、束时限的结束时限最近，从而调度进程最近，从而调度进程DA（1）执行。执行。DA（1）的实际的实际结束时间为结束时间为15，小于，小于30的时限要求。紧接着，进程的时限要求。紧接着，进程DB（1）被调度执行。在执行到时间为被调度执行。在执行到时间为30 ms时，进时，进程程DA（2）进入就绪状态。由于进入就绪状态。由于DA（2）的结束时限的结束时限为为60，近于，近于DB（1）的结束时限的结束时限75，从而，从而DB（1）被）被DA（2）抢先。抢先。DA（2）的实际结束时间为的实际结束时间为45，小于，小于要求时限要求时限60。在在DA（2）结束之后，结束之后，DB（1）再次占有处理机再次占有处

104、理机继续执行，当继续执行，当DB（1）执行到时间为执行到时间为60 ms时，进程时，进程DA（3）进入就绪状态。但是，由于进入就绪状态。但是，由于DA（3）的结束的结束时限为时限为90，远于，远于DB（1）的结束时限的结束时限75，从而，从而DB（1）继续执行。继续执行。时限调度算法也可以用于非周期性任务调度。时限调度算法也可以用于非周期性任务调度。频率单调调度算法是一种被广泛用于多周期性实频率单调调度算法是一种被广泛用于多周期性实时处理的调度算法。时处理的调度算法。频率单调调度算法的基本原理是频率越低（周期频率单调调度算法的基本原理是频率越低（周期越长）的任务的优先级越低。越长）的任务的优先

105、级越低。另外，设任务周期问题，任务的执行时间为另外，设任务周期问题，任务的执行时间为C，则则使用频率单调调度算法的必要条件是使用频率单调调度算法的必要条件是C T。已经证明，对于已经证明，对于n(n1)个周期的不同任务来说，设个周期的不同任务来说，设每个周期为每个周期为Ti，其相应任务的执行时间为其相应任务的执行时间为Ci，则使用则使用频率单调调度算法的充分条件是频率单调调度算法的充分条件是例如，对于由例如，对于由3个周期组成的实时任务序列来说，个周期组成的实时任务序列来说，其执行时间与周期之比应是：其执行时间与周期之比应是：如果进程执行时间与周期比之和大于如果进程执行时间与周期比之和大于n(

106、21/n-1)，则则用户所要求的时限无法保证。用户所要求的时限无法保证。本本 章章 小小 结结CPU是计算机系统中一个十分重要的资源，本章主是计算机系统中一个十分重要的资源，本章主要介绍处理机的调度目标、策略以及评价方法等。要介绍处理机的调度目标、策略以及评价方法等。因为处理机调度程序不可能选择全部驻留在外存的因为处理机调度程序不可能选择全部驻留在外存的进程，因此，在调度一个进程占有处理机之前，系统进程，因此，在调度一个进程占有处理机之前，系统必须按某种策略把外存中处于后备状态的作业选择出必须按某种策略把外存中处于后备状态的作业选择出来，并创建进程和分配内存，为进程执行准备必需的来，并创建进程

107、和分配内存，为进程执行准备必需的资源。这一步称为作业调度或高级调度。作业调度的资源。这一步称为作业调度或高级调度。作业调度的目标是尽量做到公平合理，能执行尽可能多的作业、目标是尽量做到公平合理，能执行尽可能多的作业、尽快地响应时间以及高的设备利用率等。任一调度算尽快地响应时间以及高的设备利用率等。任一调度算法要同时满足这些调度目标是不可能的。大多数操作法要同时满足这些调度目标是不可能的。大多数操作系统都是根据用户需要而采用兼顾某些目标的方法。系统都是根据用户需要而采用兼顾某些目标的方法。比较常用的作业调度算法有：比较常用的作业调度算法有：FCFS方法、方法、SJF（最短作业优先）法、最短作业优

108、先）法、HRN（最高响应比）法等。最高响应比）法等。这几种方法各有特点。其中这几种方法各有特点。其中FCFS法系统开销小，且法系统开销小，且对每个作业来说按其到达顺序被依次调度。对每个作业来说按其到达顺序被依次调度。FCFS法法不利于短作业。不利于短作业。SJF法可得到最大系统吞吐率，即每法可得到最大系统吞吐率，即每天处理的作业个数最多。但是天处理的作业个数最多。但是SJF法有可能使长作业法有可能使长作业永远没有机会执行。永远没有机会执行。HRN法是介于法是介于FCFS法和法和SJF法法之间的一种方法。之间的一种方法。除了作业调度之外，还介绍了一种称为交换调度除了作业调度之外，还介绍了一种称为

109、交换调度的中级调度。在有的系统中，把那些处于等待状态或的中级调度。在有的系统中，把那些处于等待状态或就绪状态的进程换出内存，而把那些等待事件已经发就绪状态的进程换出内存，而把那些等待事件已经发生或已在外存交换区中等待了较长时间的进程换入内生或已在外存交换区中等待了较长时间的进程换入内存。存。只有在进程被建立起来并且已获得足够的资源之只有在进程被建立起来并且已获得足够的资源之后，系统才使用进程调度策略把处理机分配给选出进后，系统才使用进程调度策略把处理机分配给选出进程。因此，处理机的调度涉及到三个层次的调度。进程。因此，处理机的调度涉及到三个层次的调度。进程调度的主要任务是选择一个合适的进程占据

110、处理机。程调度的主要任务是选择一个合适的进程占据处理机。根据系统的要求不一样，进程调度方法变化较大。比根据系统的要求不一样，进程调度方法变化较大。比较常用的有较常用的有RR（轮转）法、轮转）法、FCFS（先来先服务）法、先来先服务）法、优先级法和优先级法和SRR（线性优先级）法等。其中轮转法主线性优先级）法等。其中轮转法主要用于分时系统，它具有较好的响应时间，且对每个要用于分时系统，它具有较好的响应时间，且对每个进程来说都具有较好的公平性。进程来说都具有较好的公平性。FCFS法不利于执行法不利于执行时间短的进程，而时间短的进程，而SRR法则是介于法则是介于FCFS法和法和RR法之法之间的一种进

111、程调度方法。间的一种进程调度方法。习习 题题 4.1 什么是分级调度？分时系统中有作业调度的概什么是分级调度？分时系统中有作业调度的概念吗？如果没有，为什么？念吗？如果没有，为什么？4.2 试述作业调度的主要功能。试述作业调度的主要功能。4.3 作业调度的性能评价标准有哪些？这些性能评作业调度的性能评价标准有哪些？这些性能评价标准在任何情况下都能反映调度策略的优劣吗？价标准在任何情况下都能反映调度策略的优劣吗？4.4 进程调度的功能有哪些？进程调度的功能有哪些？4.5 进程调度的时机有哪几种？进程调度的时机有哪几种？4.6 进程上下文切换由哪几部分组成？形式化地描进程上下文切换由哪几部分组成？

112、形式化地描述进程上下文切换过程。述进程上下文切换过程。4.7 为什么说在进程上下文切换过程中，上下文切为什么说在进程上下文切换过程中，上下文切换程序不能破坏换程序不能破坏“老老”进程的上下文结构？进程的上下文结构？4.8 假设有假设有4道作业，它们的提交时刻及执行时间道作业，它们的提交时刻及执行时间由下表给出：由下表给出：计算在单道程序环境下，采用先来先服务调度算计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。带权周转时间，并指出它们的调度顺序。作 业 号提交时刻（小时）执

113、行时间（小时）110.002210.201310.400.5410.500.34.9 设某进程所需要的服务时间设某进程所需要的服务时间t=k*q，其中，其中，k为时间片的个数，为时间片的个数，q为时间片长度且为常数。当为时间片长度且为常数。当t为为一定值时，令一定值时，令q趋于趋于0，则有，则有k趋于无穷，从而服务时趋于无穷，从而服务时间为间为t的进程响应时间的进程响应时间T为为t的连续函数。对应于时间的连续函数。对应于时间片调度方式片调度方式RR，先来先服务方式先来先服务方式FCFS和线性优先级和线性优先级调度方式调度方式SRR，其响应时间函数分别为：其响应时间函数分别为：Trr(t)=t*

114、/(-)Tfc(t)=1/(-)Tsr(t)=1/(-)-(1-t *)/(-)其中其中=(1-b）/a)*=r*取取 (,)=(50,100)和和(,)=(80,100)，分别分别改变改变r的值，画出的值，画出Trr (t)、Tfc (t)和和Tsr (t)的时间变的时间变化图。化图。4.10 什么是多处理机系统？并行处理系统、计算机什么是多处理机系统？并行处理系统、计算机网络、分布式系统和多处理机系统的操作系统之间有网络、分布式系统和多处理机系统的操作系统之间有何区别？何区别？4.11 什么是实时调度？它与非实时调度相比，有何什么是实时调度？它与非实时调度相比，有何区别？区别？4.12 写出图写出图4.11所示周期性任务调度用的时限调度所示周期性任务调度用的时限调度算法。算法。4.13 设周期性任务设周期性任务P1，P2，P3的周期的周期T1，T2，T3分分别为别为100，150，350，执行时间分别为，执行时间分别为20，40，100，问：是否可用频率单调调度算法进行调度？问：是否可用频率单调调度算法进行调度？