第3章_调度20050722

1、2022年5月24日星期二12时49分17秒计算机操作系统3.1 3.1 3.1 3.1 3.1 3.1 3.2 3.2 3.2 3.2 3.2 3.2 3.3 3.3 3.3 3.3 3.3 3.3 3.4 3.4 3.4 3.4 3.4 3.4 3.5 3.5 3.5 3.5 3.5 3.5 3.63.63.63.63.63.6 2022年5月24日星期二12时49分18秒计算机操作系统3.1.1 调度的意义调度的意义调度策略有两个最根本的目标：调度策略有两个最根本的目标： 1、合理性合理性：在多道作业在多道作业(进程进程)并发时，使各道作并发时，使各道作业合理地分配到处理机份额。业合理地

2、分配到处理机份额。 2、有效性：有效性： 使处理机和使处理机和I/O设备得到合理有效的设备得到合理有效的分配，从而使系统资源得到充分的利用。分配，从而使系统资源得到充分的利用。 2022年5月24日星期二12时49分18秒计算机操作系统3.1.2 调度模式调度模式调度一般分为三级：调度一般分为三级： 1、高级调度高级调度又称为作业调度。其主要功能是按照又称为作业调度。其主要功能是按照某种原则从批作业队列或交互作业中选取某种原则从批作业队列或交互作业中选取某一作业进入主存，并为作业做好运行前某一作业进入主存，并为作业做好运行前的准备工作和作业完成后的后期处理。的准备工作和作业完成后的后期处理。

3、2022年5月24日星期二12时49分18秒计算机操作系统3.1.2 调度模式调度模式2、低级调度低级调度又称为处理器调度，其主要功能是按又称为处理器调度，其主要功能是按照调度策略将处理器分配给就绪进程或线照调度策略将处理器分配给就绪进程或线程。完成此功能的程序称之为程。完成此功能的程序称之为“进程（或进程（或线程）调度程序线程）调度程序”，是操作系统内核的主，是操作系统内核的主要部分。要部分。 2022年5月24日星期二12时49分18秒计算机操作系统3.1.2 调度模式调度模式3、中级调度中级调度又称中程调度，对换调度。为提高内又称中程调度，对换调度。为提高内存的利用率和系统的呑吐量，中级

4、调度决存的利用率和系统的呑吐量，中级调度决定哪些进程被允许参与竞争处理器资源，定哪些进程被允许参与竞争处理器资源，哪些进程调至外存上去等待，在合适的情哪些进程调至外存上去等待，在合适的情况下，再重新调入内存，并将其挂在就绪况下，再重新调入内存，并将其挂在就绪队列上，以恢复对处理器资源的竞争。队列上，以恢复对处理器资源的竞争。 2022年5月24日星期二12时49分18秒计算机操作系统3.1.2 调度模式调度模式2022年5月24日星期二12时49分18秒计算机操作系统3.1.3 选择调度策略的依据选择调度策略的依据 选择调度策略时一般要考虑到以下几方面选择调度策略时一般要考虑到以下几方面的问题

5、：的问题： 1、系统设计目标系统设计目标 是决定调度策略的主要依据。批处理是决定调度策略的主要依据。批处理系统以效率为目的；实时系统保证不要丢系统以效率为目的；实时系统保证不要丢失并及时处理实时信息；而分时系统确保失并及时处理实时信息；而分时系统确保用户的请求能够及时予以响应。用户的请求能够及时予以响应。 2022年5月24日星期二12时49分18秒计算机操作系统3.1.3 选择调度策略的依据选择调度策略的依据 2 2、资源利用率、资源利用率选择调度策略时，应该考虑在实现设选择调度策略时，应该考虑在实现设计目标的前提下，尽可能地发挥各种资源计目标的前提下，尽可能地发挥各种资源的效能。的效能。2

6、022年5月24日星期二12时49分18秒计算机操作系统3.1.3 选择调度策略的依据选择调度策略的依据 3 3、均衡系统与用户的要求、均衡系统与用户的要求 系统的性能与用户要求在有些时候是系统的性能与用户要求在有些时候是冲突的，系统必须均衡并协调两者之间的冲突的，系统必须均衡并协调两者之间的关系。关系。2022年5月24日星期二12时49分18秒计算机操作系统3.1.4 作业与进程的关系作业与进程的关系 1 1、什么是作业？、什么是作业？作业是用户一次提交给计算机系统的作业是用户一次提交给计算机系统的一件具有独立性的工作，是在这一次上机一件具有独立性的工作，是在这一次上机活动中要求计算机系统

7、所做的一系列工作活动中要求计算机系统所做的一系列工作的集合，由三部分组成：源程序（或程的集合，由三部分组成：源程序（或程序）、数据、及加工步骤。序）、数据、及加工步骤。 2022年5月24日星期二12时49分18秒计算机操作系统3.1.4 作业与进程的关系作业与进程的关系 2 2、作业有四个状态、作业有四个状态 从用户提交给到完成后离开系统，作从用户提交给到完成后离开系统，作业的整个活动过程常被划分为四个阶段，业的整个活动过程常被划分为四个阶段，通常称之为四种状态：提交状态、就绪状通常称之为四种状态：提交状态、就绪状态、运行状态和完成状态。态、运行状态和完成状态。2022年5月24日星期二12

8、时49分18秒计算机操作系统3.1.4 作业与进程的关系作业与进程的关系 3 3、作业的四个状态、作业的四个状态 a提交状态：当用户将作业提交给机房提交状态：当用户将作业提交给机房或通过终端将其键入计算机，作业进入提或通过终端将其键入计算机，作业进入提交状态。交状态。b就绪状态：通过输入设备的输入，操就绪状态：通过输入设备的输入，操作系统将其存放到磁盘，作业进入就绪状作系统将其存放到磁盘，作业进入就绪状态，等待运行。态，等待运行。2022年5月24日星期二12时49分18秒计算机操作系统3.1.4 作业与进程的关系作业与进程的关系 c运行状态：在调度规则的统一调度下，运行状态：在调度规则的统一

9、调度下，某个作业调度进主存并为之建立了进程，某个作业调度进主存并为之建立了进程，投入了运行，作业便进入了运行状态。投入了运行，作业便进入了运行状态。d完成状态：当作业全部运行完毕后，完成状态：当作业全部运行完毕后，作业调度程序为其完成后期处理，作业进作业调度程序为其完成后期处理，作业进入完成状态。入完成状态。 2022年5月24日星期二12时49分18秒计算机操作系统3.1.4 作业与进程的关系作业与进程的关系 4 4、作业和进程、作业和进程 每一个作业将动态地转换成了一组运每一个作业将动态地转换成了一组运行实体行实体进程组，并由此来完成该作业进程组，并由此来完成该作业所需要完成的一系列加工步

10、骤。所需要完成的一系列加工步骤。进程组由根进程或终端进程根据需要进程组由根进程或终端进程根据需要来创建。来创建。2022年5月24日星期二12时49分18秒计算机操作系统3.1.4 作业与进程的关系作业与进程的关系 5 5、根进程与终端进程、根进程与终端进程 根进程是批处理作业形式下，作业调根进程是批处理作业形式下，作业调度程序为每一道后备作业所创建的一个度程序为每一道后备作业所创建的一个“进程进程”，称为该作业的，称为该作业的“根进程根进程”，该，该“进程进程”完成这一项作业所需进程组的创完成这一项作业所需进程组的创建工作，并最终完成该作业。建工作，并最终完成该作业。 2022年5月24日星

11、期二12时49分18秒计算机操作系统3.1.4 作业与进程的关系作业与进程的关系 5 5、根进程与终端进程、根进程与终端进程在终端交互型作业下，当用户接通终端在终端交互型作业下，当用户接通终端设备时，系统便为之建立一个进程，称之为设备时，系统便为之建立一个进程，称之为终端进程。终端进程执行命令解释程序，解终端进程。终端进程执行命令解释程序，解释执行用户交互键入的每一条命令。对于每释执行用户交互键入的每一条命令。对于每一条终端命令可以创建一个子进程去具体执一条终端命令可以创建一个子进程去具体执行，来完成的作业的一系列加工步骤。行，来完成的作业的一系列加工步骤。2022年5月24日星期二12时49

12、分18秒计算机操作系统3.1.4 作业与进程的关系作业与进程的关系 因此，进程是作业的执行状态，一因此，进程是作业的执行状态，一个作业实际上是由一组相应的进程来完个作业实际上是由一组相应的进程来完成的，当作业所对应的进程完成时，作成的，当作业所对应的进程完成时，作业便进入了完成状态，整个作业也就完业便进入了完成状态，整个作业也就完成了。成了。 2022年5月24日星期二12时49分18秒计算机操作系统3.2.1 作业调度的功能作业调度的功能 作业调度只在批处理系统中存在。因为批处理系作业调度只在批处理系统中存在。因为批处理系统的作业进入系统后，是先驻留在外存上的，因此需统的作业进入系统后，是先

13、驻留在外存上的，因此需要有作业调度，将它们分批装入内存。要有作业调度，将它们分批装入内存。而在分时系统中，为了能及时响应，用户通过键而在分时系统中，为了能及时响应，用户通过键盘输入的命令或数据等，都是直接送入内存，因而无盘输入的命令或数据等，都是直接送入内存，因而无需配置作业调度。需配置作业调度。类似地，在实时系统中，通常也不需要作业调度。类似地，在实时系统中，通常也不需要作业调度。 2022年5月24日星期二12时49分18秒计算机操作系统3.2.1 作业调度的功能作业调度的功能 1 1、记录系统中各作业的状况、记录系统中各作业的状况系统使用作业控制表系统使用作业控制表( (JCB)JCB)

14、对作业实施对作业实施管理。当作业进入后备状态时，系统为之管理。当作业进入后备状态时，系统为之建立建立JCBJCB，并记录每一个作业在各阶段所要并记录每一个作业在各阶段所要求的和已分配的资源以及该作业的状态，求的和已分配的资源以及该作业的状态，作业调度程序据此对作业进行调度和管理。作业调度程序据此对作业进行调度和管理。 2022年5月24日星期二12时49分18秒计算机操作系统3.2.1 作业调度的功能作业调度的功能 2 2、为作业做好执行前的准备工作、为作业做好执行前的准备工作作业调度程序为作业建立相应的进程，作业调度程序为作业建立相应的进程，并为这些进程分配它们所需要的系统资源，并为这些进程

15、分配它们所需要的系统资源，如内存、外存、外设等。如内存、外存、外设等。 2022年5月24日星期二12时49分18秒计算机操作系统3.2.2 作业调度的依据作业调度的依据作业调度依据的原则有两条：作业调度依据的原则有两条： 1 1接纳多少个作业接纳多少个作业 接纳多少个作业进入内存取决于多道接纳多少个作业进入内存取决于多道程序度（程序度（Degree of MultiprogrammingDegree of Multiprogramming），），即允许有多少个作业同时在内存中运行。即允许有多少个作业同时在内存中运行。而多道程序度的确定应根据系统的规模和而多道程序度的确定应根据系统的规模和运行

16、速度等参数，做适当折衷。运行速度等参数，做适当折衷。 2022年5月24日星期二12时49分18秒计算机操作系统3.2.2 作业调度的依据作业调度的依据2 2接纳哪些作业接纳哪些作业应将哪些作业从外存调入内存，将取应将哪些作业从外存调入内存，将取决于所采用的调度算法。因为系统要求的决于所采用的调度算法。因为系统要求的差异，各个系统可能采取的调度算法也各差异，各个系统可能采取的调度算法也各有其特点。有其特点。2022年5月24日星期二12时49分18秒计算机操作系统3.2.3 作业调度算法基于两个因素作业调度算法基于两个因素1 1基于作业优先级基于作业优先级考虑用户的方便性，通常根据作业的考虑用

17、户的方便性，通常根据作业的某些属性为作业规定一个调度参数某些属性为作业规定一个调度参数优优先级先级( (或称作业运行优先级或称作业运行优先级) )，作业调度程，作业调度程序则根据优先级的高低决定它们的调度顺序则根据优先级的高低决定它们的调度顺序。序。 2022年5月24日星期二12时49分18秒计算机操作系统3.2.3 作业调度算法基于两个因素作业调度算法基于两个因素 2 2基于作业对资源需求量基于作业对资源需求量考虑资源的利用率，把对资源需求量考虑资源的利用率，把对资源需求量有着互补性的作业搭配在一起进行调度。有着互补性的作业搭配在一起进行调度。比如：将短作业和长作业搭配，将内存需比如：将短

18、作业和长作业搭配，将内存需求少的作业和内存需求大的作业搭配，求少的作业和内存需求大的作业搭配，I/OI/O型作业与型作业与CPUCPU型作业搭配，等等。型作业搭配，等等。 2022年5月24日星期二12时49分18秒计算机操作系统3.2.3 作业调度的作业调度的三种常用调度算法：三种常用调度算法： 1.1.先来先服务（先来先服务（FCFSFCFS）算法算法 2. 2.最短作业优先（最短作业优先（SJFSJF）算法算法 3. 3.响应比高者优先（响应比高者优先（HRNHRN）调度算法。调度算法。 2022年5月24日星期二12时49分18秒计算机操作系统进程调度是低级调度（进程调度是低级调度（L

19、ow Level Low Level SchedulingScheduling），），又称之为短程调度又称之为短程调度（Short-Term SchedulingShort-Term Scheduling），），它决定就绪它决定就绪队列中的哪个进程将获得处理机，然后由队列中的哪个进程将获得处理机，然后由分派程序（分派程序（DispatcherDispatcher）执行把处理机分执行把处理机分配给该进程的操作。配给该进程的操作。2022年5月24日星期二12时49分18秒计算机操作系统进程调度是最基本的一种调度，不管进程调度是最基本的一种调度，不管是批处理，还是分时或实时操作系统中，是批处理，还

20、是分时或实时操作系统中，都必须配置这级调度。都必须配置这级调度。进程调度的频率很高，在分时系统中，进程调度的频率很高，在分时系统中，通常是几十毫秒就要运行一次。通常是几十毫秒就要运行一次。2022年5月24日星期二12时49分18秒计算机操作系统3.3.1 3.3.1 进程调度发生的条件进程调度发生的条件通常有以下几种可能的情况：通常有以下几种可能的情况：进程完成；进程完成；分配给进程的时间片用完；分配给进程的时间片用完；进程自身的原因如请求进程自身的原因如请求I/OI/O服务，暂时放弃服务，暂时放弃CPUCPU；在抢占式调度中，新建进程的优先级比运行进在抢占式调度中，新建进程的优先级比运行进

21、程的优先级；程的优先级；某些原语操作。某些原语操作。2022年5月24日星期二12时49分18秒计算机操作系统3.3.2 3.3.2 进程调度的功能进程调度的功能 进程调度完成以下几方面的功能进程调度完成以下几方面的功能 ： 记录进程的相关信息记录进程的相关信息进程的相关信息由进程的相关信息由PCBPCB表记录。表记录。 选择进程以分配处理机选择进程以分配处理机选择依据调度策略来进行。选择依据调度策略来进行。进行进程的上下文切换进行进程的上下文切换系统要经过进程上下文切换，才能使另一个进程系统要经过进程上下文切换，才能使另一个进程得以执行。得以执行。2022年5月24日星期二12时49分18秒

22、计算机操作系统3.3.3 3.3.3 进程上下文切换进程上下文切换 一个进程的执行是在进程的上下文中进行。当一个进程的执行是在进程的上下文中进行。当正在执行的进程由于种原因要让出处理机时，系统正在执行的进程由于种原因要让出处理机时，系统要做进程上下文切换，以使另一个进程得以执行。要做进程上下文切换，以使另一个进程得以执行。切换时，包括进程的状态、有关变量和数据结切换时，包括进程的状态、有关变量和数据结构的值、机器寄存器的值和构的值、机器寄存器的值和PCBPCB以及有关程序、数以及有关程序、数据等的上下文需要切换。据等的上下文需要切换。2022年5月24日星期二12时49分19秒计算机操作系统3

23、.3.3 3.3.3 进程上下文切换进程上下文切换 切换包括下以四个步骤：切换包括下以四个步骤：决定是否做上下文切换以及判断是否允许做上下决定是否做上下文切换以及判断是否允许做上下文切换。文切换。保存当前正在执行的进程的上下文。保存当前正在执行的进程的上下文。按照进程调度策略选择适当的就绪进程。按照进程调度策略选择适当的就绪进程。装配所选进程的上下文，将处理机的控制权交给装配所选进程的上下文，将处理机的控制权交给新选进程。新选进程。 2022年5月24日星期二12时49分19秒计算机操作系统3.3.4 进程调度有两种基本方式进程调度有两种基本方式方式：非抢占方式（方式：非抢占方式（Non-Pr

24、eemptive ModeNon-Preemptive Mode）也称非剥夺调度。这是一种较为简单的调度方也称非剥夺调度。这是一种较为简单的调度方式。在该调度方式下，当进程分配到处理机时，其式。在该调度方式下，当进程分配到处理机时，其他进程不可以抢占，只有在进程自动放弃处理机时，他进程不可以抢占，只有在进程自动放弃处理机时，才进行调度。才进行调度。2022年5月24日星期二12时49分19秒计算机操作系统3.3.4 进程调度有两种基本方式进程调度有两种基本方式方式：非抢占方式（方式：非抢占方式（Non-Preemptive Mode）优点：系统开销小；采用非抢占方式时，程序优点：系统开销小；采

25、用非抢占方式时，程序员可以在某种程度上预知进程的运行轨迹，程序设员可以在某种程度上预知进程的运行轨迹，程序设计相应简化。计相应简化。缺点：损失了系统的并发性，使系统不能根据内缺点：损失了系统的并发性，使系统不能根据内部的并发事件及时实施进程调度，难以实现要求比部的并发事件及时实施进程调度，难以实现要求比较严格的实时调度要求。较严格的实时调度要求。2022年5月24日星期二12时49分19秒计算机操作系统3.3.4 进程调度有两种基本方式进程调度有两种基本方式方式方式：抢占方式（抢占方式（Preemptive Mode）也称剥夺调度。这种调度方式，允许调度程序也称剥夺调度。这种调度方式，允许调度

26、程序根据一定的原则，去停止某个正在执行的进程，将根据一定的原则，去停止某个正在执行的进程，将已分配给该进程的处理机，重新分配给另一进程。已分配给该进程的处理机，重新分配给另一进程。 2022年5月24日星期二12时49分19秒计算机操作系统3.3.4 进程调度有两种基本方式进程调度有两种基本方式方式方式：抢占的原则有三种：抢占的原则有三种：a.时间片原则：各进程按时间片运行，当一个时间片原则：各进程按时间片运行，当一个时间片用完后，便停止该进程的执行，重新调度。时间片用完后，便停止该进程的执行，重新调度。b.优先权原则：通常是对一些重要的和紧急的优先权原则：通常是对一些重要的和紧急的作业赋予较

27、高的优先权，系统将处理机分配给优先作业赋予较高的优先权，系统将处理机分配给优先权高的进程，使之执行。权高的进程，使之执行。c.短进程优先原则：当新到达的进程比正在执短进程优先原则：当新到达的进程比正在执行的进程明显地短时，将剥夺长进程的执行，将处行的进程明显地短时，将剥夺长进程的执行，将处理机分配给短进程，使之优先执行。理机分配给短进程，使之优先执行。 2022年5月24日星期二12时49分19秒计算机操作系统3.3.4 进程调度有两种基本方式进程调度有两种基本方式方式方式：抢占方式（抢占方式（Preemptive Mode）相对于非抢占调度方式而言，抢占方式的控制比较相对于非抢占调度方式而言

28、，抢占方式的控制比较复杂，但在该方式下，系统并发性强，能够满足系复杂，但在该方式下，系统并发性强，能够满足系统的多种要求，因此适应面很广。统的多种要求，因此适应面很广。2022年5月24日星期二12时49分19秒计算机操作系统3.3.5 进程调度算法进程调度算法针对系统的不同需求，应用上述两种基本调度方式，针对系统的不同需求，应用上述两种基本调度方式，常用的进程调度算法有如下常用的进程调度算法有如下6种：种： 1. 先来先服务算法；先来先服务算法； 2. 短进程优先算法；短进程优先算法； 3. 时间片轮转算法；时间片轮转算法； 4. 优先权调度算法；优先权调度算法； 5. 多队列调度算法；多队

29、列调度算法； 6. 多级反馈队列调度算法。多级反馈队列调度算法。 2022年5月24日星期二12时49分19秒计算机操作系统3.4.1 先来先服务调度算法先来先服务调度算法先来先服务调度算法从就绪队列中，选择一个先来先服务调度算法从就绪队列中，选择一个最先进入该队列的进程，把处理机分配给它，使之最先进入该队列的进程，把处理机分配给它，使之投入运行。投入运行。该调度方式属于非抢占方式，获得处理机的进该调度方式属于非抢占方式，获得处理机的进程将一直运行，直到该进程完成或因进程本身发生程将一直运行，直到该进程完成或因进程本身发生某事件而阻塞后，才放弃处理机。某事件而阻塞后，才放弃处理机。该算法能公平

30、地使每个作业该算法能公平地使每个作业(进程进程)获得处理机。获得处理机。 2022年5月24日星期二12时49分19秒计算机操作系统3.4.2 短作业短作业(进程进程)优先调度算法优先调度算法短作业优先调度算法短作业优先调度算法(SJF)是指对短作业优先是指对短作业优先调度，即从后备队列中选择一个或若干个估计运行调度，即从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存。时间最短的作业，将它们调入内存。短进程优先调度算法短进程优先调度算法(SPF)，是指对短进程优是指对短进程优先调度，即从就绪队列中选择一个或若干个估计运先调度，即从就绪队列中选择一个或若干个估计运行时间最短的进

31、程，这它们分配处理机，使之投入行时间最短的进程，这它们分配处理机，使之投入运行。运行。该算法是一个非抢占方式的算法该算法是一个非抢占方式的算法. 2022年5月24日星期二12时49分19秒计算机操作系统3.4.3 时间片轮转调度算法时间片轮转调度算法时间片轮转法的基本原理是将处理机时间划分时间片轮转法的基本原理是将处理机时间划分成若干的时间片，以时间片为单位，进程依次轮流成若干的时间片，以时间片为单位，进程依次轮流(即按先来先服务的原则即按先来先服务的原则)使用处理机一个时间片。使用处理机一个时间片。算法多用于进程调度，以提高进程的并发性，算法多用于进程调度，以提高进程的并发性，缩短每一个进

32、程的响应时间，从而提高系统的资源缩短每一个进程的响应时间，从而提高系统的资源利用率。利用率。 2022年5月24日星期二12时49分19秒计算机操作系统3.4.3 时间片轮转调度算法时间片轮转调度算法时间片的大小是该算法中的一个重要因素。应时间片的大小是该算法中的一个重要因素。应综合考虑以下几个因素来确定：综合考虑以下几个因素来确定：系统对响应时间的要求。系统对响应时间的要求。就绪队列中进程的数目。就绪队列中进程的数目。系统的处理能力系统的处理能力 2022年5月24日星期二12时49分19秒计算机操作系统3.4.4 优先权调度算法优先权调度算法优先权调度算法的基本原理优先权调度算法的基本原理

33、使用该算法前，系统将根据某些因素赋予每一个使用该算法前，系统将根据某些因素赋予每一个作业或进程一个对应的优先权，当用于作业调度时，作业或进程一个对应的优先权，当用于作业调度时，从后备队列中选择若干个优先权最高的作业调入内存；从后备队列中选择若干个优先权最高的作业调入内存；当用于进程调度时，则把处理机分配给就绪队列中优当用于进程调度时，则把处理机分配给就绪队列中优先权最高的进程。先权最高的进程。优先权在调度过程中所起的作用与系统对进程调优先权在调度过程中所起的作用与系统对进程调度采用非抢占式调度策略还是抢占式调度策略有关。度采用非抢占式调度策略还是抢占式调度策略有关。 2022年5月24日星期二

34、12时49分19秒计算机操作系统3.4.4 优先权调度算法优先权调度算法 优先权调度算法的基本原理优先权调度算法的基本原理在非抢占式优先权策略下，系统一旦把处理机在非抢占式优先权策略下，系统一旦把处理机分配某一高优先权的进程后，该进程对处理机的占分配某一高优先权的进程后，该进程对处理机的占有不会受新进程的高优先级的影响，该进程将一直有不会受新进程的高优先级的影响，该进程将一直执行下去，直到完成，或因发生某事件而进程自身执行下去，直到完成，或因发生某事件而进程自身阻塞，使该进程放弃处理机。而高优先级的新进程阻塞，使该进程放弃处理机。而高优先级的新进程只能等待正在运行的进程自动放弃处理机后，才能只

35、能等待正在运行的进程自动放弃处理机后，才能得到调度。得到调度。 2022年5月24日星期二12时49分19秒计算机操作系统3.4.4 优先权调度算法优先权调度算法 优先权调度算法的基本原理优先权调度算法的基本原理而在抢占式优先权调度策略下，系统同样是把而在抢占式优先权调度策略下，系统同样是把处理机分配给优先权最高的进程，使之执行。但一处理机分配给优先权最高的进程，使之执行。但一旦出现了另一个优先权更高的进程时，进程调度程旦出现了另一个优先权更高的进程时，进程调度程序就停止原最高优先权进程的执行序就停止原最高优先权进程的执行(而不会等待该而不会等待该进程自动放弃处理机进程自动放弃处理机)，而将处

36、理机分配给新出现，而将处理机分配给新出现的优先权最高的进程。的优先权最高的进程。2022年5月24日星期二12时49分19秒计算机操作系统3.4.4 优先权调度算法优先权调度算法优先权的类型优先权的类型优先权值是该调度算法的重要依据。优先权涉优先权值是该调度算法的重要依据。优先权涉及的因素比较多，优先权也依据这些因素分为两大及的因素比较多，优先权也依据这些因素分为两大类型：类型：a.a.静态优先权：创建进程时确定的，与运行无关。静态优先权：创建进程时确定的，与运行无关。b.b.动态优先权：动态优先权：创建进程时所赋予的优先权，可创建进程时所赋予的优先权，可以随进程的推进而改变。以随进程的推进而

37、改变。2022年5月24日星期二12时49分19秒计算机操作系统3.4.4 优先权调度算法优先权调度算法优先权的类型优先权的类型a.a.静态优先权静态优先权依赖于以下几个方面：依赖于以下几个方面：进程类型进程类型进程对资源的需求进程对资源的需求根据用户要求根据用户要求静态优先权法简单易行、系统开销小，但不够精静态优先权法简单易行、系统开销小，但不够精确，很有可能出现优先权低的作业确，很有可能出现优先权低的作业( (进程进程) )，得不到，得不到合适的调度的情况。合适的调度的情况。2022年5月24日星期二12时49分19秒计算机操作系统3.4.4 优先权调度算法优先权调度算法优先权的类型优先权

38、的类型b.b.动态优先权：动态优先权：除了包含静态优先权所包含的内容外，还可以除了包含静态优先权所包含的内容外，还可以根据根据系统的实际状况合理地调整进程的调度。系统的实际状况合理地调整进程的调度。如，为防止长作业长等待，我们可以规定，在就绪如，为防止长作业长等待，我们可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以队列中的进程，随其等待时间的增长，其优先权以速率速率增加；或为了防止一个长作业长期地垄断处增加；或为了防止一个长作业长期地垄断处理机，可以规定正在执行的进程，其优先权以速率理机，可以规定正在执行的进程，其优先权以速率下降，使其他作业有可能抢占处理机。下降，使其他作业有可

39、能抢占处理机。2022年5月24日星期二12时49分19秒计算机操作系统3.4.5 高响应比优先高响应比优先调度算法调度算法此算法的优先权定义如下：此算法的优先权定义如下：优先权优先权( (等待时间要求服务时间等待时间要求服务时间)/)/要求服务时间要求服务时间该优先权的分子是等待时间加上要求服务时间，该优先权的分子是等待时间加上要求服务时间，即是系统对该作业的响应时间，而响应时间与服务即是系统对该作业的响应时间，而响应时间与服务时间的比值称之为响应比，故该优先权又相当于响时间的比值称之为响应比，故该优先权又相当于响应比。应比。 2022年5月24日星期二12时49分19秒计算机操作系统3.4

40、.5 高响应比优先高响应比优先调度算法调度算法该算法将优先调度高响应比的进程，因此，从该算法将优先调度高响应比的进程，因此，从响应比计算可以看出：响应比计算可以看出：如果作业的等待时间相同，该算法有利于短作如果作业的等待时间相同，该算法有利于短作业，保持了短作业优先的特点；业，保持了短作业优先的特点；当要求服务的时间相同时，则先来先服务，满当要求服务的时间相同时，则先来先服务，满足了用户的分时要求；足了用户的分时要求；对于长作业，随着等待时间增加，其优先权便对于长作业，随着等待时间增加，其优先权便可升到很高，从而也可获得处理机，避免了长作业可升到很高，从而也可获得处理机，避免了长作业长时间得不

41、到服务的现象。长时间得不到服务的现象。 2022年5月24日星期二12时49分19秒计算机操作系统3.4.6 多级队列多级队列调度算法调度算法在多级队列调度下，就绪队列被分为若干个独在多级队列调度下，就绪队列被分为若干个独立子队列。立子队列。作业则根据其性质或类型，固定地分属于一个作业则根据其性质或类型，固定地分属于一个队列。队列。多级队列调度包括队列间调度和队列内调度两多级队列调度包括队列间调度和队列内调度两部分内容。部分内容。2022年5月24日星期二12时49分19秒计算机操作系统3.4.6 多级队列多级队列调度算法调度算法队列之间的关系可以采取多种方式来处理。队列之间的关系可以采取多种

42、方式来处理。应用较多的一种方式是规定好每个队列的优先应用较多的一种方式是规定好每个队列的优先权，优先权高的队列优先获得调度。如在具有前、权，优先权高的队列优先获得调度。如在具有前、后台队列的系统中，是优先调度前台队列中的进程后台队列的系统中，是优先调度前台队列中的进程执行；仅当前台队列中已无可运行的进程时，方才执行；仅当前台队列中已无可运行的进程时，方才调度后台队列中的进程运行。另一种处理各队列间调度后台队列中的进程运行。另一种处理各队列间关系的方式是为各队列分配一定的占用关系的方式是为各队列分配一定的占用CPUCPU的时间的时间比例。比如，可为前台队列分配比例。比如，可为前台队列分配8080

43、的的CPUCPU时间，时间，给后台队列给后台队列2020的的CPUCPU时间。时间。 2022年5月24日星期二12时49分19秒计算机操作系统3.4.6 多级队列多级队列调度算法调度算法队列之间的关系的另一种处理方式是：为各队队列之间的关系的另一种处理方式是：为各队列分配一定的占用列分配一定的占用CPUCPU的时间比例。比如，可为前的时间比例。比如，可为前台队列分配台队列分配8080的的CPUCPU时间，给后台队列时间，给后台队列2020的的CPUCPU时间。时间。 2022年5月24日星期二12时49分19秒计算机操作系统3.4.6 多级反馈队列多级反馈队列调度算法调度算法在多级反馈队列调

44、度下，就绪队列也是被分为在多级反馈队列调度下，就绪队列也是被分为若干个独立子队列若干个独立子队列。调度也分成队列间调度和队列。调度也分成队列间调度和队列内调度两部分。内调度两部分。但进程不是根据其性质或类型固定地分属于一但进程不是根据其性质或类型固定地分属于一个队列，而是根据其使用个队列，而是根据其使用CPUCPU时间的长短来动态地时间的长短来动态地决定作业属于那级队列。决定作业属于那级队列。2022年5月24日星期二12时49分19秒计算机操作系统3.4.6 多级反馈队列多级反馈队列调度算法调度算法调度实施过程如下：调度实施过程如下：1.就绪队列分为若干个独立子队列就绪队列分为若干个独立子队

45、列，各个队列，各个队列赋予不同的优先权赋予不同的优先权。第一个队列的优先权最高，第第一个队列的优先权最高，第二队列次之，其余队列的优先权逐个降低。二队列次之，其余队列的优先权逐个降低。 2.2.其次，赋予各个队列中进程执行时间片大小其次，赋予各个队列中进程执行时间片大小也各不相同，在优先权愈高的队列中，每个进程的也各不相同，在优先权愈高的队列中，每个进程的执行时间片就规定得愈小，而优先权低的队列会分执行时间片就规定得愈小，而优先权低的队列会分配成倍于高一级优先级的队列的时间片。配成倍于高一级优先级的队列的时间片。 2022年5月24日星期二12时49分19秒计算机操作系统3.4.6 多级反馈队

46、列多级反馈队列调度算法调度算法3.当一个新进程进入内存后，首先将它放入第当一个新进程进入内存后，首先将它放入第一队列的末尾，按一队列的末尾，按FCFS原则排队等待调度。当轮原则排队等待调度。当轮到该进程执行时，如能在该时间片内完成，便可准到该进程执行时，如能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样调度程序便将该进程转入第二队列的末尾，再同样地按照地按照FCFS原则等待调度执行；如果它在第二队原则等待调度执行；如果它在第二队列中运行一个时间片仍未完成，再依法将它输入第列中运行一

47、个时间片仍未完成，再依法将它输入第三队列三队列依此规律，直至进程全部完成。依此规律，直至进程全部完成。 2022年5月24日星期二12时49分19秒计算机操作系统3.4.6 多级反馈队列多级反馈队列调度算法调度算法4. 仅当第一队列空闲时，调度程序才调度第二仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第（队列中的进程运行；仅当第（1i-1）队列为空时，队列为空时，才调度第才调度第i队列的进程运行。如果处理机正在运行队列的进程运行。如果处理机正在运行第第i队列的进程，而此时又有新的进程进入优先权队列的进程，而此时又有新的进程进入优先权较高的任一队列（较高的任一队列（1i-1队列）

48、，则此时新的进程队列），则此时新的进程将抢占处理机，即调度程序将处理机重新分配给新将抢占处理机，即调度程序将处理机重新分配给新进入进入1i-1队列的进程，并把被抢先的进程投入原队列的进程，并把被抢先的进程投入原队列的末尾。队列的末尾。 2022年5月24日星期二12时49分19秒计算机操作系统3.5.1 先来先服务先来先服务(FCFS)先来先服务算法只是简单地按照进程或作业到先来先服务算法只是简单地按照进程或作业到达的先后次序来调度。达的先后次序来调度。例如：一组进程的例如：一组进程的FCFS调度结果如下表调度结果如下表 2022年5月24日星期二12时49分19秒计算机操作系统3.5.1 先

49、来先服务先来先服务(FCFS)分析该调度实例，得到如下相关参数：分析该调度实例，得到如下相关参数：从上表可以看出：优先到达的作业最先得到调度，从上表可以看出：优先到达的作业最先得到调度，有着最优的带权响应时间；但其后到的长作业有着最优的带权响应时间；但其后到的长作业D也也有较优的带权周转时间，仅为有较优的带权周转时间，仅为1.99。带权周转时间。带权周转时间最长的是后到的短作业最长的是后到的短作业C，高达高达100。 2022年5月24日星期二12时49分19秒计算机操作系统3.5.1 先来先服务先来先服务(FCFS)因此，因此，FCFS算法比较有利于优先到达的作业算法比较有利于优先到达的作业

50、和长作业，而不利于短作业。和长作业，而不利于短作业。所以，对于所以，对于CPU繁忙型的作业，由于它需要大繁忙型的作业，由于它需要大量的量的CPU时间进行计算，而很少请求时间进行计算，而很少请求I/O，先来先先来先服务型调度将获得较好的效率。但对于服务型调度将获得较好的效率。但对于I/O繁忙型繁忙型的作业的作业(进程进程)，需频繁地请求，需频繁地请求I/O，而每次而每次I/O的操的操作时间却又很短，此时先来先服务型调度产生的效作时间却又很短，此时先来先服务型调度产生的效果将难以接受。果将难以接受。 2022年5月24日星期二12时49分19秒计算机操作系统3.5.2 短作业短作业( (进程进程)

51、 )优先调度优先调度( (SJF/SPF) )该算法以作业该算法以作业( (进程进程) )所需要时间的长短作为调所需要时间的长短作为调度的唯一标准，它较好地照顾到了实际上在作业度的唯一标准，它较好地照顾到了实际上在作业( (进程进程) )中占很大比例的短作业中占很大比例的短作业( (进程进程) )，使它们能比，使它们能比长作业长作业( (进程进程) )优先执行。优先执行。2022年5月24日星期二12时49分19秒计算机操作系统3.5.2 短作业短作业( (进程进程) )优先调度优先调度( (SJF/SPF) )该调度算法使短作业该调度算法使短作业( (进程进程) )得到了很好的调度，得到了很

52、好的调度，但存在着以下几方面的问题：但存在着以下几方面的问题：该算法对长作业非常不利；该算法对长作业非常不利；该算法完全未考虑作业该算法完全未考虑作业( (进程进程) )的紧迫程度，因而的紧迫程度，因而不能保证紧迫性作业不能保证紧迫性作业( (进程进程) )会得到及时处理；会得到及时处理；作业作业( (进程进程) )的长短是根据用户所提供的估计执行的长短是根据用户所提供的估计执行时间而定，存在着一定的不合理。时间而定，存在着一定的不合理。2022年5月24日星期二12时49分19秒计算机操作系统3.5.3 时间片轮转时间片轮转 该调度算法中，系统将运行时间进行划分成时该调度算法中，系统将运行时

53、间进行划分成时间片，各个任务或进程之间采取先来先服务的原则间片，各个任务或进程之间采取先来先服务的原则进行调度，轮流分配一个时间片。进行调度，轮流分配一个时间片。时间片划分后的轮转使得短任务得到了较快的时间片划分后的轮转使得短任务得到了较快的响应，同时先来先服务的原则又使各个任务或进程响应，同时先来先服务的原则又使各个任务或进程获得处理机的机会非常均等，因此这一算法较之前获得处理机的机会非常均等，因此这一算法较之前两种算法在调度效果上均有一些改善。两种算法在调度效果上均有一些改善。 2022年5月24日星期二12时49分19秒计算机操作系统3.5.3 时间片轮转时间片轮转 该算法的调度效果依赖

54、于时间片的合理划分，该算法的调度效果依赖于时间片的合理划分，如果时间片太大，每一个作业或进程只需要一个时如果时间片太大，每一个作业或进程只需要一个时间片便可以完成，那么这种形式的时间片轮转则等间片便可以完成，那么这种形式的时间片轮转则等同于先来先服务调度法；时间片如果划分得太细，同于先来先服务调度法；时间片如果划分得太细，则系统性能将在调度上严重损耗。则系统性能将在调度上严重损耗。 2022年5月24日星期二12时49分19秒计算机操作系统3.5.4 三种调度算法的调度结果比较三种调度算法的调度结果比较2022年5月24日星期二12时49分19秒计算机操作系统3.5.4 三种调度算法的调度结果

55、比较三种调度算法的调度结果比较从上表中看到：从上表中看到：长作业在长作业在FCSFFCSF中有着较优的参数，在三种调度方式中最中有着较优的参数，在三种调度方式中最优。优。SJ(P)SJ(P)下平均周转时间和带权平均周转时间均较优，因此下平均周转时间和带权平均周转时间均较优，因此系统效率较优，将有效地降低作业的平均等待时间，提高系统效率较优，将有效地降低作业的平均等待时间，提高系统的呑吐量。而短作业系统的呑吐量。而短作业D D的带权周转时间从的带权周转时间从5.55.5下降到下降到1.51.5，长作业长作业( (进程进程C)C)的带权周转时间的带权周转时间从从FCFSFCFS算法下的算法下的2.

56、02.0增加到增加到了了3.23.2，也就是说，短作业的优势非常明显，长作业有可能，也就是说，短作业的优势非常明显，长作业有可能得不到合适的调度。得不到合适的调度。2022年5月24日星期二12时49分19秒计算机操作系统3.5.4 三种调度算法的调度结果比较三种调度算法的调度结果比较RRRR方式下，表中数据显示，在该形式下的各个作方式下，表中数据显示，在该形式下的各个作业的带权周转时间比较均衡，先来后到的差别被消业的带权周转时间比较均衡，先来后到的差别被消除，充分体现了分时系统的需要。时间片的大小对除，充分体现了分时系统的需要。时间片的大小对效率参数起着非常大的影响作用，从表中看到，对效率参

57、数起着非常大的影响作用，从表中看到，对于某一组作业于某一组作业( (进程进程) )，当时间片足够大时，它，当时间片足够大时，它与与FCFSFCFS调度算法有着完全相同的调度效果。调度算法有着完全相同的调度效果。2022年5月24日星期二12时49分19秒计算机操作系统3.5.5 优先权调度算法优先权调度算法 优先权调度法加入了一个优先权参数，该参数的主观优先权调度法加入了一个优先权参数，该参数的主观可调性为操作者控制系统的调度性能提供了方便，对于紧可调性为操作者控制系统的调度性能提供了方便，对于紧急作业急作业(进程进程)，可以人为赋予高优先权，用抢占式优先调度，可以人为赋予高优先权，用抢占式优

58、先调度保证其实时性；而动态优先权法能够运行过程中根据系统保证其实时性；而动态优先权法能够运行过程中根据系统的状况及时调整调度，因而，长短作业的状况及时调整调度，因而，长短作业(进程进程)得到了很好地得到了很好地协调，既能避免短作业协调，既能避免短作业(进程进程)的长时间等待，又能使长作业的长时间等待，又能使长作业(进程进程)得到适时的调度，兼得了得到适时的调度，兼得了FCFS和和SJF/SPF的优点。的优点。 2022年5月24日星期二12时49分20秒计算机操作系统3.5.6 高响应比优先调度算法高响应比优先调度算法 高响应比优先调度算法也是一种优先权调度高响应比优先调度算法也是一种优先权调

59、度算法。在这一算法是在短作业优先的基础上，对等算法。在这一算法是在短作业优先的基础上，对等待时间长的作业动态地赋予它不断增长的优先级。待时间长的作业动态地赋予它不断增长的优先级。这种算法保留了短作业优先算法的优点，并通过优这种算法保留了短作业优先算法的优点，并通过优先级参数的动态修改，避免了长作业的长等待。先级参数的动态修改，避免了长作业的长等待。 2022年5月24日星期二12时49分20秒计算机操作系统3.5.7 多级队列调度算法多级队列调度算法 多级队列调度对进程施行分级管理，同时也多级队列调度对进程施行分级管理，同时也对队列和队列内的进程进行分级调度。这种分而治对队列和队列内的进程进行

60、分级调度。这种分而治之的调度策略使得不同类型的进程能够得到更有效之的调度策略使得不同类型的进程能够得到更有效的管理，使得系统对进程的管理更为合理，采用此的管理，使得系统对进程的管理更为合理，采用此算法的系统具有更强的适应能力。算法的系统具有更强的适应能力。2022年5月24日星期二12时49分20秒计算机操作系统3.5.8 多级反馈队列调度算法多级反馈队列调度算法多级队列调度对进程施行分级管理，同时也多级队列调度对进程施行分级管理，同时也对队列和队列内的进程进行分级调度。这种分而治对队列和队列内的进程进行分级调度。这种分而治之的调度策略使得不同类型的进程能够得到更有效之的调度策略使得不同类型的