处理机调n.pptx

第第4章章 处理机调度处理机调度4.1 分级调度分级调度4.2 作业调度作业调度4.3 进程调度进程调度4.4 调度算法调度算法4.5 算法评价算法评价4.6 实时系统调度方法实时系统调度方法本章小结本章小结习题习题 CPU是计算机系统中一个十分重要的资源。在早期的计算机是计算机系统中一个十分重要的资源。在早期的计算机系统中，对它的管理是十分简单的。随着多道程序设计技术和各系统中，对它的管理是十分简单的。随着多道程序设计技术和各种不同类型的操作系统的出现，各种不同的种不同类型的操作系统的出现，各种不同的CPU管理方法得到启管理方法得到启用。不同的用。不同的CPU管理方法将为用户提供不同性能的操作系统。例管理方法将为用户提供不同性能的操作系统。例如：在多道批处理系统中，为了提高处理机的效率和增加作业吞如：在多道批处理系统中，为了提高处理机的效率和增加作业吞吐率，当调度一批作业组织多道运行时，要尽可能使作业搭配合吐率，当调度一批作业组织多道运行时，要尽可能使作业搭配合理。这样，就能使系统中的各种资源可充分利用。在用户看来，理。这样，就能使系统中的各种资源可充分利用。在用户看来，这是一台没有交互、速度较慢的处理机。在分时系统中，在调度这是一台没有交互、速度较慢的处理机。在分时系统中，在调度作业执行时要首先考虑每个用户作业得到处理机的均等性。这样，作业执行时要首先考虑每个用户作业得到处理机的均等性。这样，系统资源的利用率就不如批处理系统。由此可以看到，根据操作系统资源的利用率就不如批处理系统。由此可以看到，根据操作系统的要求不同，处理机管理的策略是不同的。系统的要求不同，处理机管理的策略是不同的。衡量调度策略的最常用的几个指标是：衡量调度策略的最常用的几个指标是：(1)周转时间周转时间是指将一个作业提交给计算机系统后是指将一个作业提交给计算机系统后到该作业的结果返回给用户所需要的时间。到该作业的结果返回给用户所需要的时间。(2)吞吐率吞吐率是指在单位时间内，一个计算机系统所是指在单位时间内，一个计算机系统所完成的总工作量。完成的总工作量。(3)响应时间响应时间则是指从用户向计算机发出一个命令则是指从用户向计算机发出一个命令到计算机把相应的执行结果返回给用户所需要的时间。到计算机把相应的执行结果返回给用户所需要的时间。本章主要讨论：本章主要讨论：(1)作业与进程的关系；作业与进程的关系；(2)作业调度策略算法；作业调度策略算法；(3)进程调度策略与算法；进程调度策略与算法；(4)调度策略的评价。调度策略的评价。4.1 分分 级级 调调 度度4.1.1 作业的状态及其转换作业的状态及其转换以批处理系统为例一个作业处理的大致过程。以批处理系统为例一个作业处理的大致过程。如图如图4.1 所示，一个作业从提交给计算机系统到执所示，一个作业从提交给计算机系统到执行结束退出系统，一般都要经历行结束退出系统，一般都要经历提交、收容、执行和提交、收容、执行和完成等完成等4个状态个状态。图图4.1 作业的状态及其转换作业的状态及其转换读卡机读卡机打印机打印机I/O请求磁盘磁盘通道P1P2P3P4P5提交状提交状态态后备状后备状态态执行状执行状态态完成状完成状态态提交后备执行完成退出SPOOLing输入作业调度1作业调度2SPOOLing输出(1)提交状态提交状态:一个作业在其处于从输入设备进入外一个作业在其处于从输入设备进入外部存储设备的过程称为提交状态。部存储设备的过程称为提交状态。(2)收容状态收容状态(后备状态后备状态):若一个作业的全部信息已若一个作业的全部信息已全部被输入进输入井，那么，在它还未被调度去执行全部被输入进输入井，那么，在它还未被调度去执行之前，该作业处于收容状态。之前，该作业处于收容状态。(3)执行状态执行状态:作业调度程序从后备作业中选取若干作业调度程序从后备作业中选取若干个作业到内存投入运行。这些被选中的作业处于执行个作业到内存投入运行。这些被选中的作业处于执行状态。状态。(4)完成状态完成状态:当作业运行完毕，但它所占用的资源当作业运行完毕，但它所占用的资源尚未全部被系统回收时，该作业处于完成状态。尚未全部被系统回收时，该作业处于完成状态。4.1.2 调度的层次调度的层次处理机调度问题实际上是处理机的分配问题。处理机调度问题实际上是处理机的分配问题。显显然，只有那些参与竞争处理机所必需的资源都已得到然，只有那些参与竞争处理机所必需的资源都已得到满足的进程才能享有竞争处理机的资格。这时，它们满足的进程才能享有竞争处理机的资格。这时，它们处于内存就绪状态。这些必需的资源包括内存、外设处于内存就绪状态。这些必需的资源包括内存、外设及有关数据结构等。从而，在进程有资格竞争处理机及有关数据结构等。从而，在进程有资格竞争处理机之前，作业调度程序必须先调用存储管理、外设管理之前，作业调度程序必须先调用存储管理、外设管理程序，并按一定的选择顺序和策略从输入井中选择出程序，并按一定的选择顺序和策略从输入井中选择出几个处于后备状态的作业，为它们分配内存等资源和几个处于后备状态的作业，为它们分配内存等资源和创建进程，使它们获得竞争处理机的资格。创建进程，使它们获得竞争处理机的资格。另外，由于处于执行状态下的作业一般包含有多另外，由于处于执行状态下的作业一般包含有多个进程，而在单机系统中，每一时刻只能有一个进程个进程，而在单机系统中，每一时刻只能有一个进程占有处理机。那么，其他进程就只能处于准备抢占处占有处理机。那么，其他进程就只能处于准备抢占处理机的就绪状态或等待得到某种新资源的等待状态。理机的就绪状态或等待得到某种新资源的等待状态。为了提高资源的利用率，在有些操作系统中把一部分为了提高资源的利用率，在有些操作系统中把一部分在内存中处于就绪状态或等待状态而在短时期内又得在内存中处于就绪状态或等待状态而在短时期内又得不到执行的进程、作业换出内存，以让其他作业的进不到执行的进程、作业换出内存，以让其他作业的进程竞争处理机。这样，在外存中，除了处于后备状态程竞争处理机。这样，在外存中，除了处于后备状态的作业外，还存在有处于就绪状态而等待得到内存的的作业外，还存在有处于就绪状态而等待得到内存的作业。这就需要有一定的方法和策略为这部分作业分作业。这就需要有一定的方法和策略为这部分作业分配空间。配空间。一般来说，处理机调度可以分为一般来说，处理机调度可以分为4级：级：(1)作业调度作业调度：又称宏观调度，或高级调度。其主要任务：又称宏观调度，或高级调度。其主要任务是按一定的原则对外存输入井上的大量后备作业进行选择，是按一定的原则对外存输入井上的大量后备作业进行选择，给选出的作业分配内存、输入输出设备等必要的资源，并建给选出的作业分配内存、输入输出设备等必要的资源，并建立相应的进程。另外，当该作业执行完毕时，还负责回收系立相应的进程。另外，当该作业执行完毕时，还负责回收系统资源。统资源。(2)交换调度交换调度：又称中级调度。其主要任务是按照给定的：又称中级调度。其主要任务是按照给定的原则和策略，将处于外存交换区中的就绪状态或等待状态的原则和策略，将处于外存交换区中的就绪状态或等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区。程交换到外存交换区。(3)进程调度进程调度：又称微观调度或低级调度。其主要任务：又称微观调度或低级调度。其主要任务是按照某种策略和方法选取一个处于就绪状态的进程占用处是按照某种策略和方法选取一个处于就绪状态的进程占用处理机。在确定了占用处理机的进程后，系统必须进行进程上理机。在确定了占用处理机的进程后，系统必须进行进程上下文切换以建立与占用处理机进程相适应的执行环境。下文切换以建立与占用处理机进程相适应的执行环境。(4)线程调度线程调度。上述上述4级调度的关系如图级调度的关系如图4.1 在多道批处理系统中，存在着作业调度和进程调在多道批处理系统中，存在着作业调度和进程调度。但是，在分时系统和实时系统中，一般不存在作度。但是，在分时系统和实时系统中，一般不存在作业调度，而只有进程调度、交换调度和线程调度。这业调度，而只有进程调度、交换调度和线程调度。这是因为在分时系统和实时系统中，为了缩短响应时间是因为在分时系统和实时系统中，为了缩短响应时间或为了满足用户需求的截止时间，作业不是建立在外或为了满足用户需求的截止时间，作业不是建立在外存，而是直接建立在内存中。在这些系统中，一旦用存，而是直接建立在内存中。在这些系统中，一旦用户和系统的交互开始，用户马上要进行控制。因而，户和系统的交互开始，用户马上要进行控制。因而，这些系统中没有作业提交状态和后备状态。它们的输这些系统中没有作业提交状态和后备状态。它们的输入信息经过终端缓冲区为系统所接收，或者立即处理，入信息经过终端缓冲区为系统所接收，或者立即处理，或者经交换调度暂存外存中。或者经交换调度暂存外存中。4.1.3 作业与进程的关系作业与进程的关系作业可被看作是用户向计算机提交任务的任务实作业可被看作是用户向计算机提交任务的任务实体，体，例如一次计算、一个控制过程等。反过来，例如一次计算、一个控制过程等。反过来，进程进程则是计算机为了完成用户任务实体而设置的执行实体，则是计算机为了完成用户任务实体而设置的执行实体，是系统分配资源的基本单位是系统分配资源的基本单位。显然，计算机要完成一。显然，计算机要完成一个任务实体，必须要有一个以上的执行实体。也就是个任务实体，必须要有一个以上的执行实体。也就是说，说，一个作业总是由一个以上的多个进程组成的。一个作业总是由一个以上的多个进程组成的。那那么，作业怎样分解为进程呢？么，作业怎样分解为进程呢？首先，系统必须为一个首先，系统必须为一个作业创建一个根进程。然后，在执行作业控制语句时，作业创建一个根进程。然后，在执行作业控制语句时，根据任务要求，系统或根进程为其创建相应的子进程，根据任务要求，系统或根进程为其创建相应的子进程，然后，为各子进程分配资源和调度各子进程执行以完然后，为各子进程分配资源和调度各子进程执行以完成作业要求的任务。成作业要求的任务。4.2 作作 业业 调调 度度作业调度主要是完成作业从后备状态到执行状态作业调度主要是完成作业从后备状态到执行状态的转变，以及从执行状态到完成状态的转变。的转变，以及从执行状态到完成状态的转变。4.2.1 作业调度功能作业调度功能(1)记录系统中各作业的状况。记录系统中各作业的状况。作业调度程序要能作业调度程序要能挑选出一个作业投入执行，并且在执行中对其进行管挑选出一个作业投入执行，并且在执行中对其进行管理，它就必须掌握作业在各个状态，包括执行阶段的理，它就必须掌握作业在各个状态，包括执行阶段的有关情况。有关情况。通常，系统为每个作业建立一个作业控制通常，系统为每个作业建立一个作业控制表表JCB记录这些有关信息。记录这些有关信息。系统通过系统通过JCB而感知作业而感知作业的存在。系统在作业进入后备状态时为该作业建立它的存在。系统在作业进入后备状态时为该作业建立它的的JCB，从而使得该作业可被作业调度程序感知。当，从而使得该作业可被作业调度程序感知。当该作业执行完毕进入完成状态之后，系统又撤消其该作业执行完毕进入完成状态之后，系统又撤消其JCB而释放有关资源并撤消该作业。而释放有关资源并撤消该作业。图图4.2给出了给出了JCB的主要内容。它包括作业名、作的主要内容。它包括作业名、作业类型、资源要求、当前状态、资源使用情况以及该业类型、资源要求、当前状态、资源使用情况以及该作业的优先级等。作业的优先级等。图图4.2 作业控制块作业控制块JCB作业名作业名作业类型作业类型资源要求资源要求资源使用情况资源使用情况优先级优先级(数数)当前状态当前状态其他其他其中，作业名由用户提供并由系统将其转换为系其中，作业名由用户提供并由系统将其转换为系统可识别的作业标识符。作业类型指该作业属于计算统可识别的作业标识符。作业类型指该作业属于计算型（要求型（要求CPU时间多）还是管理型（要求输入输出时间多）还是管理型（要求输入输出量大）量大）,或图形设计型（要求高速图形显示）等。而或图形设计型（要求高速图形显示）等。而资源要求则包括：该作业估计执行时间、要求最迟完资源要求则包括：该作业估计执行时间、要求最迟完成时间、要求的内存量和外存量、要求的外设类型及成时间、要求的内存量和外存量、要求的外设类型及台数以及要求的软件支持工具库函数等。资源要求均台数以及要求的软件支持工具库函数等。资源要求均由用户提供。资源使用情况包括有：作业进入系统时由用户提供。资源使用情况包括有：作业进入系统时间、开始执行时间、已执行时间、内存地址、外设台间、开始执行时间、已执行时间、内存地址、外设台数等。优先级则被用来决定该作业的调度次序。优先数等。优先级则被用来决定该作业的调度次序。优先级既可以由用户给定，也可以由系统动态计算产生。级既可以由用户给定，也可以由系统动态计算产生。状态是指该作业当前所处的状态。显然，只有当作业状态是指该作业当前所处的状态。显然，只有当作业处于后备状态时，该作业才可以被调度。处于后备状态时，该作业才可以被调度。(2)从后备队列中挑选出一部分作业投入执行。从后备队列中挑选出一部分作业投入执行。作业调度程序根据选定的调度算法，从后备作业队列作业调度程序根据选定的调度算法，从后备作业队列中挑选出若干作业去投入执行。中挑选出若干作业去投入执行。(3)为被选中作业做好执行前的准备工作。为被选中作业做好执行前的准备工作。作业作业调度程序调度程序为选中的作业建立相应的进程，为选中的作业建立相应的进程，并为这些进并为这些进程分配它们所需要的系统资源，如分配给它们内存、程分配它们所需要的系统资源，如分配给它们内存、外存、外设等。外存、外设等。(4)在作业执行结束时做善后处理工作。在作业执行结束时做善后处理工作。主要是主要是输出作业管理信息，例如执行时间等。再就是回收该输出作业管理信息，例如执行时间等。再就是回收该作业所占用的资源，撤消与该作业有关的全部进程和作业所占用的资源，撤消与该作业有关的全部进程和该作业的作业控制块等等。该作业的作业控制块等等。作业从后备状态到执行状态，又从执行状态到完作业从后备状态到执行状态，又从执行状态到完成状态的转换过程如图成状态的转换过程如图4.3所示。所示。图图4.3 作业调度中状态的转换过程作业调度中状态的转换过程4.2.2 作业调度目标与性能衡量作业调度目标与性能衡量作业调度的功能最主要的是从后备作业队列中选作业调度的功能最主要的是从后备作业队列中选取一批作业进入执行状态。根据不同的目标，将会有取一批作业进入执行状态。根据不同的目标，将会有不同的调度算法。这里先介绍调度目标。不同的调度算法。这里先介绍调度目标。一般来说，调度目标主要是以下一般来说，调度目标主要是以下4点：点：(1)对所有作业应该是公平合理的；对所有作业应该是公平合理的；(2)应使设备有高的利用率；应使设备有高的利用率；(3)每天执行尽可能多的作业；每天执行尽可能多的作业；(4)有快的响应时间。有快的响应时间。由于这些目标的相互冲突，任一调度算法要想同由于这些目标的相互冲突，任一调度算法要想同时满足上述目标是不可能的。时满足上述目标是不可能的。作业调度的工作时机：作业调度的工作时机：（1）系统初启）系统初启（2）一个作业运行完成，撤离系统）一个作业运行完成，撤离系统（3）后备作业队列中到达一个新的作业）后备作业队列中到达一个新的作业（4）一个作业释放了一定的资源）一个作业释放了一定的资源 那么，怎样来衡量一个作业调度算法是否满足系那么，怎样来衡量一个作业调度算法是否满足系统设计的要求呢？对于批处理系统，由于主要用于计统设计的要求呢？对于批处理系统，由于主要用于计算，对于作业的周转时间要求较高。因此，作业的平算，对于作业的周转时间要求较高。因此，作业的平均周转时间或平均带权周转时间，被作为衡量调度算均周转时间或平均带权周转时间，被作为衡量调度算法优劣的标准。但是，对于分时系统和实时系统来说，法优劣的标准。但是，对于分时系统和实时系统来说，外加平均响应时间被作为衡量调度策略优劣的标准。外加平均响应时间被作为衡量调度策略优劣的标准。1.周转时间：周转时间：作业作业i的周转时间的周转时间Ti为为Ti=Tei-Tsi其中其中Tei为作业为作业i的完成时间，的完成时间，Tsi为作业的提交时间。为作业的提交时间。对于被测定作业流所含有的对于被测定作业流所含有的n（n=1）个作业来说，）个作业来说，其平均周转时间为：其平均周转时间为：一个作业的周转时间说明了该作业在系统内停留的时一个作业的周转时间说明了该作业在系统内停留的时间，包含两部分：等待时间、执行时间，即：间，包含两部分：等待时间、执行时间，即：Ti=TwiTri这里，这里，Twi主要指作业主要指作业i由后备状态到执行状态的等待由后备状态到执行状态的等待时间，它不包括作业进入执行状态后的等待时间。时间，它不包括作业进入执行状态后的等待时间。2.带权周转时间带权周转时间作业的周转时间包含了两个部分，即等待时间和执作业的周转时间包含了两个部分，即等待时间和执行时间。为了更进一步反映调度性能，使用带权周转行时间。为了更进一步反映调度性能，使用带权周转时间的概念。带权周转时间是作业周转时间与作业执时间的概念。带权周转时间是作业周转时间与作业执行时间的比：行时间的比：Wi=Ti/Tri对于被测定作业流所含有的几个作业来说，其平均对于被测定作业流所含有的几个作业来说，其平均带权周转时间为：带权周转时间为：对于分时系统，除了要保证系统吞吐量大、资源利对于分时系统，除了要保证系统吞吐量大、资源利用率高之外，还应保证有用户能够容忍的响应时间。用率高之外，还应保证有用户能够容忍的响应时间。因此，在分时系统中，仅仅用周转时间或带权周转时因此，在分时系统中，仅仅用周转时间或带权周转时间来衡量调度性能是不够的。间来衡量调度性能是不够的。4.3 进进 程程 调调 度度无论是在批处理系统还是分时系统中，用户进程无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数，这将导致用户进程互相争夺数一般都多于处理机数，这将导致用户进程互相争夺处理机。另外，系统进程也同样需要使用处理机。这处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。分配给处于就绪队列中的某一个进程，以使之执行。本节介绍进程调度的功能、进程调度发生的时机以及本节介绍进程调度的功能、进程调度发生的时机以及由进程调度引起的进程上下文切换等。由进程调度引起的进程上下文切换等。4.3.1 进程调度的功能进程调度的功能进程调度的具体功能可总结如下：进程调度的具体功能可总结如下：(1)记录系统中所有进程的执行情况记录系统中所有进程的执行情况作为进程调度的准备，进程管理模块必须将系统中作为进程调度的准备，进程管理模块必须将系统中各进程的执行情况和状态特征记录在各进程的各进程的执行情况和状态特征记录在各进程的PCB表表中。并且，进程管理模式根据各进程的状态特征和资中。并且，进程管理模式根据各进程的状态特征和资源需求，将各进程的源需求，将各进程的PCB表排成相应的队列并进行动表排成相应的队列并进行动态队列转接。进程调度模块通过态队列转接。进程调度模块通过PCB变化来掌握系统变化来掌握系统中所有进程的执行情况和状态特征，并在适当的时机中所有进程的执行情况和状态特征，并在适当的时机从就绪队列中选择出一个进程占据处理机。从就绪队列中选择出一个进程占据处理机。(2)选择占有处理机的进程选择占有处理机的进程进程调度的主要功能是按照一定的策略选择一个处进程调度的主要功能是按照一定的策略选择一个处于就绪状态的进程，使其获得处理机执行。根据不同于就绪状态的进程，使其获得处理机执行。根据不同的系统设计目的，有各种各样的选择策略，例如系统的系统设计目的，有各种各样的选择策略，例如系统开销较少的静态优先数调度法，适合于分时系统的轮开销较少的静态优先数调度法，适合于分时系统的轮转法和多级反馈轮转法等。这些选择策略决定了调度转法和多级反馈轮转法等。这些选择策略决定了调度算法的性能。算法的性能。(3)进行进程上下文切换进行进程上下文切换一个进程的上下文（一个进程的上下文（context）包括进程的状态、）包括进程的状态、有关变量和数据结构的值、硬件寄存器的值和有关变量和数据结构的值、硬件寄存器的值和PCB以以及有关程序等。一个进程的执行是在进程的上下文中及有关程序等。一个进程的执行是在进程的上下文中执行。当正在执行的进程由于某种原因要让出处理机执行。当正在执行的进程由于某种原因要让出处理机时，系统要做进程上下文切换，以使另一个进程得以时，系统要做进程上下文切换，以使另一个进程得以执行。当进行上下文切换时，系统要首先检查是否允执行。当进行上下文切换时，系统要首先检查是否允许做上下文切换。然后，系统要保留有关被切换进程许做上下文切换。然后，系统要保留有关被切换进程的足够信息，以便以后切换回该进程时，顺利恢复该的足够信息，以便以后切换回该进程时，顺利恢复该进程的执行。在系统保留了进程的执行。在系统保留了CPU现场之后，调度程序现场之后，调度程序选择一个新的处于就绪状态的进程，并装配该进程的选择一个新的处于就绪状态的进程，并装配该进程的上下文，使上下文，使CPU的控制权转换到被选中进程中。的控制权转换到被选中进程中。4.3.2 进程调度的时机进程调度的时机引起进程调度的原因有以下几类引起进程调度的原因有以下几类：(1)正在执行的进程执行完毕。正在执行的进程执行完毕。(2)执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等待状态。等待状态。(3)执行中进程调用了执行中进程调用了P原语操作，从而因资源不足而被阻塞；原语操作，从而因资源不足而被阻塞；或调用了或调用了V原语操作激活了等待资源的进程队列。原语操作激活了等待资源的进程队列。(4)执行中进程提出执行中进程提出IO请求后被阻塞。请求后被阻塞。(5)在分时系统中时间片已经用完。在分时系统中时间片已经用完。(6)在执行完系统调用，可调度选择一新的用户进程执行。在执行完系统调用，可调度选择一新的用户进程执行。(7)就绪队列中的某进程的优先级变得高于当前执行进程的就绪队列中的某进程的优先级变得高于当前执行进程的优先级，从而也将引发进程调度。优先级，从而也将引发进程调度。也可归纳为：也可归纳为：（1）正在执行的进程让出处理机（）正在执行的进程让出处理机（1、2、3、4、5、6）（2）就绪队列中到达一个新的就绪进程（）就绪队列中到达一个新的就绪进程（3）（3）就绪队列中一个进程的优先级升高（）就绪队列中一个进程的优先级升高（7）可剥夺方式可剥夺方式调度方式调度方式 非剥夺方式非剥夺方式所谓可剥夺方式，即就绪队列中一旦有优先级高所谓可剥夺方式，即就绪队列中一旦有优先级高于当前执行进程优先级的进程存在时，便立即发生进于当前执行进程优先级的进程存在时，便立即发生进程调度，转让处理机。而非剥夺方式或不可剥夺方式程调度，转让处理机。而非剥夺方式或不可剥夺方式即使在就绪队列存在有优先级高于当前执行进程时，即使在就绪队列存在有优先级高于当前执行进程时，当前进程仍将继续占有处理机，直到该进程自己因调当前进程仍将继续占有处理机，直到该进程自己因调用原语操作或等待用原语操作或等待IO而进入阻塞、睡眠状态，或而进入阻塞、睡眠状态，或时间片用完时才重新发生调度让出处理机。时间片用完时才重新发生调度让出处理机。哪种调度方式开销大？哪种调度方式开销大？操作系统将在以上几种原因之一发生的情况下进行进操作系统将在以上几种原因之一发生的情况下进行进程调度。例如，程调度。例如，UNIX SystemV 就是在以下就是在以下5种情况之一种情况之一发生时进行进程调度的：发生时进行进程调度的：(1)当前进程自己调用当前进程自己调用sleep，wait等进入睡眠状态时。等进入睡眠状态时。(2)当前进程从系统调用执行结束后返回用户态时，它当前进程从系统调用执行结束后返回用户态时，它的优先级已低于其他就绪状态进程，或调度标志被置位。的优先级已低于其他就绪状态进程，或调度标志被置位。(3)当前进程在完成中断和陷阱处理后返回用户态时，当前进程在完成中断和陷阱处理后返回用户态时，它的优先级已低于其他就绪状态进程；或调度标志被置它的优先级已低于其他就绪状态进程；或调度标志被置位。位。(4)时间片用完，而且当前进程的优先级低于其他就绪时间片用完，而且当前进程的优先级低于其他就绪进程。进程。(5)当前进程调用当前进程调用exit，自我终止时。，自我终止时。4.3.3 进程上下文切换进程上下文切换进程上下文由正文段、数据段、硬件寄存器的内进程上下文由正文段、数据段、硬件寄存器的内容以及有关数据结构等组成。硬件寄存器主要包括存容以及有关数据结构等组成。硬件寄存器主要包括存放放CPU将要执行的下条指令虚拟地址的程序计数器将要执行的下条指令虚拟地址的程序计数器PC，指出机器与进程相关联的硬件状态的处理机状，指出机器与进程相关联的硬件状态的处理机状态寄存器态寄存器PS，存放过程调用（或系统调用）时所传，存放过程调用（或系统调用）时所传递参数的通用寄存器递参数的通用寄存器R以及堆栈指针寄存器以及堆栈指针寄存器S等。数等。数据结构则包括据结构则包括PCB等在内的所有与执行该进程有关的等在内的所有与执行该进程有关的管理和控制用表格、数组、链等。在发生进程调度时，管理和控制用表格、数组、链等。在发生进程调度时，系统要做进程上下文切换。系统要做进程上下文切换。进程上下文切换包括进程上下文切换包括4个步骤：个步骤：(1)决定是否做上下文切换以及是否允许做上下文决定是否做上下文切换以及是否允许做上下文切换。包括对进程调度原因的检查分析，以及当前执切换。包括对进程调度原因的检查分析，以及当前执行进程的资格和行进程的资格和CPU执行方式的检查等。执行方式的检查等。(2)保存当前执行进程的上下文。这里所说的当前保存当前执行进程的上下文。这里所说的当前执行进程，实际上是指调用上下文切换程序之前的执执行进程，实际上是指调用上下文切换程序之前的执行进程。如果上下文切换程序不是被那个当前执行进行进程。如果上下文切换程序不是被那个当前执行进程所调用，且不属于该进程，则所保存的上下文应是程所调用，且不属于该进程，则所保存的上下文应是先前执行进程的上下文，或称为先前执行进程的上下文，或称为“老老”进程上下文。进程上下文。显然，上下文切换程序不能破坏显然，上下文切换程序不能破坏“老老”进程的上下文进程的上下文结构。结构。(3)使用使用4.5节中所述进程调度算法，选择一个处于节中所述进程调度算法，选择一个处于就绪状态进程。就绪状态进程。(4)恢复或装配所选进程的上下文，将恢复或装配所选进程的上下文，将CPU控制权控制权交给所选进程。交给所选进程。4.3.4 进程调度性能评价进程调度性能评价进程调度虽然是系统内部的低级调度，但进程调进程调度虽然是系统内部的低级调度，但进程调度的优劣直接影响作业调度的性能。反映作业调度优度的优劣直接影响作业调度的性能。反映作业调度优劣的周转时间和平均周转时间只在某种程度上反映了劣的周转时间和平均周转时间只在某种程度上反映了进程调度的性能，例如，其执行时间部分中实际上包进程调度的性能，例如，其执行时间部分中实际上包含有进程等待（包括就绪状态时的等待）时间，而进含有进程等待（包括就绪状态时的等待）时间，而进程等待时间的多少是要依靠进程调度策略和等待事件程等待时间的多少是要依靠进程调度策略和等待事件何时发生来决定的。因此，进程调度性能的衡量是操何时发生来决定的。因此，进程调度性能的衡量是操作系统设计的一个重要指标。作系统设计的一个重要指标。进程调度性能的衡量方法可分为定性和定量两种。进程调度性能的衡量方法可分为定性和定量两种。在定性衡量方面，首先是在定性衡量方面，首先是调度的可靠性调度的可靠性。另外，。另外，简洁简洁性也是衡量进程调度的一个重要指标性也是衡量进程调度的一个重要指标。进程调度的定量评价包括进程调度的定量评价包括CPU的利用率的利用率评价、评价、进进程在就绪队列中的等待时间与执行时间之比程在就绪队列中的等待时间与执行时间之比等。实际等。实际上，由于进程进入就绪队列的随机模型很难确定，而上，由于进程进入就绪队列的随机模型很难确定，而且进程上下文切换等也将影响进程的执行效率，从而且进程上下文切换等也将影响进程的执行效率，从而对进程调度进行解析是很困难的。一般情况下，大多对进程调度进行解析是很困难的。一般情况下，大多利用模拟或测试利用模拟或测试系统响应时间系统响应时间的方法来评价进程调度的方法来评价进程调度的性能。的性能。作业调度与进程调度的关系作业调度与进程调度的关系4.4 调度算法调度算法 包括进程调度、作业调度（两种不同的调度机制）包括进程调度、作业调度（两种不同的调度机制）关于进程的关于进程的CPU burst 与与 I/O burst：阵发期阵发期:CPU burst cycle:进程使用进程使用CPU计算；计算；I/O burst cycle:进程使用设备进程使用设备I/O。进程运行行为：进程运行行为：CPU burst,I/O burst,CPU burst,I/O burst,进程调度：对处于进程调度：对处于CPU burst的进程集合的调度。的进程集合的调度。1.先来先服务调度算法（先来先服务调度算法（FCFS）First Come First Serve将用户作业或就绪进程按提交顺序或变为就绪状态将用户作业或就绪进程按提交顺序或变为就绪状态的顺序排成队列，并按照先进先出的顺序排成队列，并按照先进先出(先来先服务先来先服务)的方式的方式进行调度处理，是一种最简单的方法。进行调度处理，是一种最简单的方法。特点特点:(1)实现简单实现简单(2)适于作业调度、进程调度适于作业调度、进程调度(3)公平公平?对于执行时间较短的作业或进程来说，等对于执行时间较短的作业或进程来说，等待时间可能较长。待时间可能较长。先来先服务调度算法（续）先来先服务调度算法（续）考虑下面的例子考虑下面的例子:如果作业队列依次如果作业队列依次(几乎同时几乎同时)到达如下到达如下3个作个作业业,按按“先来先服务先来先服务”的方式进行调度完成后，计算平均等待时间：的方式进行调度完成后，计算平均等待时间：作业作业需运行时间需运行时间J150J210J31运行情况：运行情况：0506061平均等待时间平均等待时间=（0+50+60）/336.67如果到达顺序为如果到达顺序为J3、J2、J1，运行情况：，运行情况：011161平均等待时间平均等待时间=（0+1+11）/3=4J1J2J3J3J2J12.轮转调度算法（轮转调度算法（Round Robin）轮转法的基本概念是将轮转法的基本概念是将CPU的处理时间分成固定大小的时间片（的处理时间分成固定大小的时间片（T）。）。如果一个进程在被调度选中之后用完了系统规定的时间片，但未完成要求的如果一个进程在被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有的任务，则它自行释放自己所占有的CPU而排到就绪队列的末尾，等待下一次而排到就绪队列的末尾，等待下一次调度。同时，进程调度程序又去调度当前就绪队列中的第一个进程。调度。同时，进程调度程序又去调度当前就绪队列中的第一个进程。注意注意：（1）该算法）该算法适于进程调度，一般不适于作业调度（为什么？）适于进程调度，一般不适于作业调度（为什么？）（2）适应系统：分时系统适应系统：分时系统图图4.4轮转法调度轮转法调度或进入等待队列或进入等待队列或进入等待队列或进入等待队列时间片到时间片到时间片到时间片到轮转调度算法（续）轮转调度算法（续）例：设某系统时间片值为例：设某系统时间片值为20，下列进程的调度情况：，下列进程的调度情况：Process Burst TimeP153 P2 17 P368 P4 24 在实际系统中，通常情况下随着时间的推移，某些进程运在实际系统中，通常情况下随着时间的推移，某些进程运行完成本次的行完成本次的CPU Burst而撤离就绪队列，同时还会有新的就而撤离就绪队列，同时还会有新的就绪进程不断地加入。绪进程不断地加入。02037577797117121 134154 162P1P2 P3P4 P1 P3P3P1 P3P4（3）时间片长度的取值）时间片长度的取值固定时间片固定时间片时间片长度：几十毫秒时间片长度：几十毫秒 几百毫秒几百毫秒(例如例如 50ms)过长：过长：过短：过短：可变时间片可变时间片设系统对响应时间的要求是设系统对响应时间的要求是R，就绪队列中最大进程数为，就绪队列中最大进程数为Nmax。因为因为 R|T|*Nmax 所以所以|T|R/Nmax一种可行的办法是，每当一轮调度开始时，系统便根据就绪队列中已有进一种可行的办法是，每当一轮调度开始时，系统便根据就绪队列中已有进程数目计算一次程数目计算一次T值，作为新一轮调度的时间片。这种方法得到的时间片值值，作为新一轮调度的时间片。这种方法得到的时间片值随就绪队列中的进程数变化。随就绪队列中的进程数变化。轮转调度算法（续）轮转调度算法（续）响应速度慢响应速度慢 算法会退化为算法会退化为FCFS；进程切换过于频繁进程切换过于频繁系统开销系统开销(overhead)大。大。3.最短作业优先调度算法（最短作业优先调度算法（SJF）Shortest Job First最短作业优先法（最短作业优先法（SJF）就是选择那些估计需要）就是选择那些估计需要执行时间最短的作业投入执行。执行时间最短的作业投入执行。例：如果作业队列依次例：如果作业队列依次(几乎同时几乎同时)到达如下到达如下3个作个作业业,按最短作业优先法（按最短作业优先法（SJF）调度。）调度。作业作业需运行时间需运行时间J150J210J31011161平均等待时间平均等待时间=（0+1+11）/3=4J3J2J1最短作业优先调度算法（续）最短作业优先调度算法（续）优点：优点：（1）可使得系统在单位时间内处理的作业个数最多）可使得系统在单位时间内处理的作业个数最多吞吐吞吐量最大。量最大。（2）对同一批作业而言，该算法使得作业的平均等待时间最）对同一批作业而言，该算法使得作业的平均等待时间最短。短。缺点：缺点：可能使得某些运行时间较长的作业得不到调度执行的机会。可能使得某些运行时间较长的作业得不到调度执行的机会。两种调度方式：两种调度方式：（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最短作业优先调度算法（续）最短作业优先调度算法（续）剥夺方式示例：剥夺方式示例：Process Arrival Time Burst TimeP10.07 P22.04 P34.01 P45.04平均等待时间平均等待时间=P1P3P242110P457P2P116(9+1+0+2)/4=3 最短作业优先调度算法（续）最短作业优先调度算法（续）对运行时间的估计：对运行时间的估计：（1）作业调度：系统要求用户在提交作业时声明估计作业的）作业调度：系统要求用户在提交作业时声明估计作业的运行时间。运行时间。（2）进程调度：）进程调度：CPU burst时间的确定时间的确定根据进程以前的行根据进程以前的行为推