清华大学计算机系列教材：《计算机操作系统教程》（第2版）第4章 处理机调度

清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS 第4章处理机调度 41分级调度 4.2作业调度 43进程调度 44调度算法 4.5算法评价 46实时系统调度方法 本章小结 习题

第4章 处理机调度 4.1 分级调度 4.2 作业调度 4.3 进程调度 4.4 调度算法 4.5 算法评价 4.6 实时系统调度方法 本章小结 习题

清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS CPU是计算机系统中一个十分重要的资源。在早期 的计算机系统中,对它的管理是十分简单的。随着 多道程序设计技术和各种不同类型的操作系统的出 现,各种不同的CPU管理方法得到启用。不同的 CPU管理方法将为用户提供不同性能的操作系统。 例如:在多道批处理系统中,为了提高处理机的效 率和增加作业吞吐率,当调度一批作业组织多道运 行时,要尽可能使作业搭配合理。这样,就能使系 统中的各种资源可充分利用。但由于是批处理,在 用户看来,这是一台没有交互、速度较慢的处理机。 在分时系统中,在调度作业执行时要首先考虑每个 用户作业得到处理机的均等性。这样,系统资源的 利用率就不如批处理系统。由此可以看到,根据操 作系统的要求不同,处理机管理的策略是不同的

CPU是计算机系统中一个十分重要的资源。在早期 的计算机系统中，对它的管理是十分简单的。随着 多道程序设计技术和各种不同类型的操作系统的出 现，各种不同的CPU管理方法得到启用。不同的 CPU管理方法将为用户提供不同性能的操作系统。 例如：在多道批处理系统中，为了提高处理机的效 率和增加作业吞吐率，当调度一批作业组织多道运 行时，要尽可能使作业搭配合理。这样，就能使系 统中的各种资源可充分利用。但由于是批处理，在 用户看来，这是一台没有交互、速度较慢的处理机。 在分时系统中，在调度作业执行时要首先考虑每个 用户作业得到处理机的均等性。这样，系统资源的 利用率就不如批处理系统。由此可以看到，根据操 作系统的要求不同，处理机管理的策略是不同的

清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS 衡量调度策略的最常用的几个指标是:周转时间、 吞吐率、响应时间以及设备利用率等。周转时间是 指将一个作业提交给计算机系统后到该作业的结果 返回给用户所需要的时间。吞吐率是指在给定的时 间内,一个计算机系统所完成的总工作量。响应时 间则是指从用户向计算机发出一个命令到计算机把 相应的执行结果返回给用户所需要的时间。设备利 用率主要指输入输出设备的使用情况 本章将以CPU管理为核心,讨论管理、控制用户进 程执行的方法。主要包括: (1)作业与进程的关系;(2)作业调度策略与算法;(3) 进程调度策略与算法;(4)几种调度策略的评价 另外,还介绍实时调度系统

衡量调度策略的最常用的几个指标是：周转时间、 吞吐率、响应时间以及设备利用率等。周转时间是 指将一个作业提交给计算机系统后到该作业的结果 返回给用户所需要的时间。吞吐率是指在给定的时 间内，一个计算机系统所完成的总工作量。响应时 间则是指从用户向计算机发出一个命令到计算机把 相应的执行结果返回给用户所需要的时间。设备利 用率主要指输入输出设备的使用情况。 本章将以CPU 管理为核心，讨论管理、控制用户进 程执行的方法。主要包括： (1) 作业与进程的关系；(2) 作业调度策略与算法；(3) 进程调度策略与算法；(4) 几种调度策略的评价。 另外，还介绍实时调度系统

清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS 41分级调度 411作业的状态及其转换 在第2章中,介绍了用户如何利用操作系统提供的手 段与工具去组织和控制自己的作业运行。但是, 个作业从用户提交开始到真正占有处理机而被执行, 则要由系统经过多级调度才能实现(在有些系统, 例如分时系统中,也可以由单级调度实现),下面 以批处理系统为例看一个作业处理的大致过程。 如图41所示,一个作业从提交给计算机系统到执行 结束退出系统,一般都要经历提交、收容、执行和 完成等4个状态

4.1 分 级 调 度 4.1.1 作业的状态及其转换 在第2章中，介绍了用户如何利用操作系统提供的手 段与工具去组织和控制自己的作业运行。但是，一 个作业从用户提交开始到真正占有处理机而被执行， 则要由系统经过多级调度才能实现（在有些系统， 例如分时系统中，也可以由单级调度实现），下面 以批处理系统为例看一个作业处理的大致过程。 如图4.1 所示，一个作业从提交给计算机系统到执行 结束退出系统，一般都要经历提交、收容、执行和 完成等4个状态

清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS 外存 就绪 等待 交换调度 提交 收容 状态 状态 输入管理系统 就绪 等待 完成 状态 执行 线程调度 内存 进程调度 作业调度 图41作业的状态及其转换

图4.1 作业的状态及其转换

清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS 个作业在其处于从输入设备进入外部存储设备的 过程称为提交状态。处于提交状态的作业,因其信 息尚未全部进入系统,所以不能被调度程序选取。 收容状态也称为后备状态。输入管理系统不断地将 作业输入到外存中对应部分(或称输入井,即专门 用来存放待处理作业信息的一组外存分区)。若 个作业的全部信息已全部被输入进输入井,那么, 在它还未被调度去执行之前,该作业处于收容状态

一个作业在其处于从输入设备进入外部存储设备的 过程称为提交状态。处于提交状态的作业，因其信 息尚未全部进入系统，所以不能被调度程序选取。 收容状态也称为后备状态。输入管理系统不断地将 作业输入到外存中对应部分（或称输入井，即专门 用来存放待处理作业信息的一组外存分区）。若一 个作业的全部信息已全部被输入进输入井，那么， 在它还未被调度去执行之前，该作业处于收容状态

清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS 作业调度程序从后备作业中选取若干个作业到内存 投入运行。它为被选中作业建立进程并分配必要的 资源,这时,这些被选中的作业处于执行状态。从 宏观上看,这些作业正处在执行过程中,但从微观 上看,在某一时刻,由于处理机总数少于并发执行 的进程数,因此,不是所有被选中作业都占有处理 机,其中的大部分处于等待资源或就绪状态中。那 么,究竞哪个作业的哪个进程能获得处理机而真正 在执行,要依靠进程调度来决定。 当作业运行完毕,但它所占用的资源尚未全部被系 统回收时,该作业处于完成状态。在这种状态下, 系统需做诸如打印结果、回收资源等类的善后处理 工作

作业调度程序从后备作业中选取若干个作业到内存 投入运行。它为被选中作业建立进程并分配必要的 资源，这时，这些被选中的作业处于执行状态。从 宏观上看，这些作业正处在执行过程中，但从微观 上看，在某一时刻，由于处理机总数少于并发执行 的进程数，因此，不是所有被选中作业都占有处理 机，其中的大部分处于等待资源或就绪状态中。那 么，究竟哪个作业的哪个进程能获得处理机而真正 在执行，要依靠进程调度来决定。 当作业运行完毕，但它所占用的资源尚未全部被系 统回收时，该作业处于完成状态。在这种状态下， 系统需做诸如打印结果、回收资源等类的善后处理 工作

清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS 412调度的层次 处理机调度问题实际上也是处理机的分配问题。显 然,只有那些参与竞争处理机所必需的资源都已得 到满足的进程才能享有竞争处理机的资格。这时, 它们处于内存就绪状态。这些必需的资源包括内存 外设及有关数据结构等。从而,在进程有资格竞争 处理机之前,作业调度程序必须先调用存储管理 外设管理程序,并按一定的选择顺序和策略从输入 井中选择出几个处于后备状态的作业,为它们分配 内存等资源和创建进程,使它们获得竞争处理机的 资格

4.1.2 调度的层次 处理机调度问题实际上也是处理机的分配问题。显 然，只有那些参与竞争处理机所必需的资源都已得 到满足的进程才能享有竞争处理机的资格。这时， 它们处于内存就绪状态。这些必需的资源包括内存、 外设及有关数据结构等。从而，在进程有资格竞争 处理机之前，作业调度程序必须先调用存储管理、 外设管理程序，并按一定的选择顺序和策略从输入 井中选择出几个处于后备状态的作业，为它们分配 内存等资源和创建进程，使它们获得竞争处理机的 资格

清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS 另外,由于处于执行状态下的作业一般包含有多个 进程,而在单机系统中,每一时刻只能有一个进程 占有处理机。那么,其他进程就只能处于准备抢占 处理机的就绪状态或等待得到某种新资源的等待状 态。为了提高资源的利用率,在有些操作系统中把 部分在内存中处于就绪状态或等待状态而在短时 期内又得不到执行的进程、作业换出内存,以让其 他作业的进程竞争处理机。这样,在外存中,除了 处于后备状态的作业外,还存在有处于就绪状态而 等待得到内存的作业。这就需要有一定的方法和策 略为这部分作业分配空间。 般来说,处理机调度可以分为4级:

另外，由于处于执行状态下的作业一般包含有多个 进程，而在单机系统中，每一时刻只能有一个进程 占有处理机。那么，其他进程就只能处于准备抢占 处理机的就绪状态或等待得到某种新资源的等待状 态。为了提高资源的利用率，在有些操作系统中把 一部分在内存中处于就绪状态或等待状态而在短时 期内又得不到执行的进程、作业换出内存，以让其 他作业的进程竞争处理机。这样，在外存中，除了 处于后备状态的作业外，还存在有处于就绪状态而 等待得到内存的作业。这就需要有一定的方法和策 略为这部分作业分配空间。 一般来说，处理机调度可以分为4级：

清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS (1)作业调度:又称宏观调度,或高级调度。其主要 任务是按一定的原则对外存输入井上的大量后备作 业进行选择,给选出的作业分配内存、输入输出设 备等必要的资源,并建立相应的进程,以使该作业 的进程获得竞争处理机的权利。另外,当该作业执 行完毕时,还负责回收系统资源 (2)交换调度:又称中级调度。其主要任务是按照给 定的原则和策略,将处于外存交换区中的就绪状态 或就绪等待状态的进程调入内存,或把处于内存就 绪状态或内存等待状态的进程交换到外存交换区。 交换调度主要涉及到内存管理与扩充。 (3)进程调度:又称微观调度或低级调度。其主要任 务是按照某种策略和方法选取一个处于就绪状态的 进程占用处理机。在确定了占用处理机的进程后

(1) 作业调度：又称宏观调度，或高级调度。其主要 任务是按一定的原则对外存输入井上的大量后备作 业进行选择，给选出的作业分配内存、输入输出设 备等必要的资源，并建立相应的进程，以使该作业 的进程获得竞争处理机的权利。另外，当该作业执 行完毕时，还负责回收系统资源。 (2) 交换调度：又称中级调度。其主要任务是按照给 定的原则和策略，将处于外存交换区中的就绪状态 或就绪等待状态的进程调入内存，或把处于内存就 绪状态或内存等待状态的进程交换到外存交换区。 交换调度主要涉及到内存管理与扩充。 (3) 进程调度：又称微观调度或低级调度。其主要任 务是按照某种策略和方法选取一个处于就绪状态的 进程占用处理机。在确定了占用处理机的进程后