第三章 处理机调度

1、第三章 处理机调度 第三章第三章 处理机调度处理机调度 1 调度级别调度级别 2 调度的功能、时机及方式调度的功能、时机及方式 3 调度原则与评估标准调度原则与评估标准 4 调度算法调度算法 5 调度的实现调度的实现 第三章 处理机调度 调调 度度 级级 别别 .高级调度高级调度 即作业调度。它决定允许哪些作业可参与竞争和 其它系统资源，从状态观点，就是将一个或一批作业从后备 状 态 变 为 运 行 状 态 。 一 个 作 业 一 旦 被 高 级 调度选中，便可获得所需要的基本内存和设备资源，并被装 入内存，此后就以进程形式参与并发运行，与其它进程竞争 。换言之，高级调度决定给哪个作业分配一台

2、虚拟处 理机，获得虚拟处理机的作业将在该虚拟处理机上顺序执行。 从这个意义上说，高级调度进行的是虚拟处理机的分配，即 的宏观调度，故高级调度亦称宏观调度。 第三章 处理机调度 中级调度中级调度 中级调度决定哪些进程可参与竞争，从状态观 点，就是将进程从活动态变为静止的挂起态，或者将进程 从挂起态变为就绪态或等待态。这主要是为了短期调整系 统负荷，以缓和内存使用紧张的矛盾。中级调度的实质是 执行“挂起”和“激活”操作；挂起一个进程是把该进程 的实体（程序和数据）从内存迁移到外存的专门区域，称 为交换区，并释放该进程占用的用户内存区，这称为“换 出”；反之，激活一个进程是把该进程的实体从外存交换

3、区迁移到内存，这称为“换进”。故中级调度也常称为进 程交换，通常仅用于分时系统。 第三章 处理机调度 低级调度低级调度 即进程调度。它决定哪个进程可获得物理， 从状态观点，就是将某个进程从就绪态变为执行态。被 低级调度选中的进程将实际获得，并可立即在物 理上执行它的程序。因此，低级调度是处理机三 级调度中的终结调度，亦称的微观调度。 第三章 处理机调度 图- 处理机的三级调度 第三章 处理机调度 调度的功能、时机及方式调度的功能、时机及方式 . 作业调度的功能与时机作业调度的功能与时机 （）按照某种调度算法（即调度策略），根据系统资 源的当前使用情况和后备作业对资源的需求，挑选一个或 多个后备

4、作业投入运行； （）为选中的作业分配基本的内存和设备资源，这通 过调用内存分配程序和设备分配程序来完成； （）为选中的作业建立进程，将进程实体装入内存， 这通过调用建立进程原语来实现。 第三章 处理机调度 一般来说，在下列情况下将启动作业调度： （）设为系统支持的在主机上运行的最大作业数（也 称道数），为在主机上运行的当前作业数。如果， 且存在后备作业，则启动作业调度； （）当一作业运行终止而被撤销后，如果存在后备作业， 则立即启动作业调度崐； （）在分时系统中，当一用户在某终端上通过交互会话 被核准其注册的登录作业名及其口令后，立即启动作业调度。 第三章 处理机调度 . 进程调度的功能与时机

5、进程调度的功能与时机 启动进程调度的时机可归结为： （）现行进程执行完它的当前时值时，这包括 现行进程执行完毕而终止或现行进程因等待某个事件而 自行阻塞，此时需要将分配给一个新的就绪进程； （）在采用剥夺调度方式的系统中，当发生了某种 剥夺事件，例如，当发生了时间片中断或有比现行进程 具有更高优先级的进程进入了就绪队列时，此时系统要 回收现行进程占用的并进行重新调度。 第三章 处理机调度 . 调度方式调度方式 一进程在上的一次连续执行过程称为该进程的一个周 期。一个周期由进程自我终止。当进程需等待某个事件而进入等 待态时，便终止了它的当前周期。待等待事件发生后，进程将开 始下一个周期。进程执行

6、完毕进入停止状态则终止了它的最后一 个周期。一个进程在其并发运行过程中通常有若干个离散的且长 短不等的周期。例如，一进程需要在上执行的总时间为 ，在 、 、 的执行点处它分别要等 待三个事件而暂停执行，即该进程有四个分别为 、 、 以及 的周期时值。当现行进程执行 完它的一个周期时，系统应及时把转交给另一个进程去执 行它的周期，这是导致进程调度的基本原因，也是实现多部件并 行和多进程并发的基本要求。 第三章 处理机调度 进程调度方式包括剥夺式与非剥夺式。在剥夺方式下， 当现行进程正在执行它的一个周期期间，系统有权 强行分割该进程的当前时值，即强行剥夺现行进程 正占用的，并把分配给另一进程，换言

7、之， 如果一个进程的一个周期可能被分割成两个或更多 个周期，则系统采用的是剥夺式调度。反之，在非 剥夺方式下，一个进程一旦获得便一直执行下去， 直到完成它的当前周期，系统才重新调度，换言之， 系统无权分割进程的任一周期。 第三章 处理机调度 调度原则与评估标准调度原则与评估标准 一般需综合考虑以下四个基本调度原则： （）尽量提高系统的吞吐量，系统吞吐量是指在单位时 间内完成的平均作业数； （）均衡利用资源，使与外设尽量都保持“忙” 状态； （）对所有的作业都应公平，任何一个作业的完成都不 能被无限延迟； （）如果支持优先级，应对优先级高的作业或进程给予 优先服务。 第三章 处理机调度 下面是几

8、项主要的评估标准： （） 平均周转时间 作业从提交时刻is到完成时 刻ic所经历的时间称为该作业的周转时间，即 icis；进程从进入就绪队列的时刻ir到执行完本次 周期的时刻ic称为该进程的周转时间i，即i icir。于是，个作业的平均周转时间或个进程 的平均周转时间为： n i i T n T 1 1 第三章 处理机调度 （） 平均带权周转时间 作业的周转时间Ti与其实 际运行时间 i之比 称为该作业的带权周转时间， 即 ，同样，进程的周转时间与其本次 周期的时值之比 称为该进程的带权周转时间。 于是，个作业或个进程的平均带权周转时间为： i T iii tTT/ i T n i i T n

9、 T 1 1 第三章 处理机调度 （）平均等待时间 进程从进入就绪队列那一时刻 ir到获得的那一时刻ip所经历的时间称为它的 等待时间i，即iipir，那么个进程的平均等待 时间为： n i i W n W 1 1 通常，用来衡量不同调度算法对同一作业流或同 一进程集的调度性能，用来衡量不同进程调度算法对 同一进程集的调度性能，而用来衡量同一调度算法对 不同作业流或不同进程集的调度性能。 第三章 处理机调度 调调 度度 算算 法法 . 先来先服务先来先服务 假定有四个作业，它们的进入、估计运行和完成时间以 及平均周转时间和平均带权周转时间如表-所示。 第三章 处理机调度 考虑三个进程、和，它们

10、的本次周期 的时值分别为 、 和 ，且以、 的次序处于就绪队列中，不妨认为它们进入就绪队列 的相对时刻均为。于是，在调度下，其执行过 程可表示如下： P1P2P3 0 21 2730 第三章 处理机调度 、和的等待时间分别为、和， 周转时间分别为、和，故它们的平均等待时 间和平均周转时间分别为： )(263/ )302721( )(163/ )27210( msT msW 算法本质上是非剥夺式的，如果可剥夺，则不 能保证原则的实施。例如，对上述三个进程，若按 时间片进行剥夺式调度，且规定时间片，则执行过程 可表示如下： P1P2P3P1P1P1 02127 306 1215 第三章 处理机调度

11、 . 最短者优先最短者优先 第三章 处理机调度 . 最高响应比者优先最高响应比者优先 HRN（Highest-Response-ratio-next)）算法是为了克服 算法和算法的缺点而提出的，是这两种算法 的一种折衷。 一个作业或进程的响应比定义为： 响应时间需运行时间 （已等待时间需运行时间）需运行时间 已等待时间需运行时间 第三章 处理机调度 调度程序开始调度时，首先计算各个后备作业或 各个就绪进程的响应比 ，然后选择值最大的作业或进 程。响应比既是需运行时间的函数，也是等待时间的函 数。由于与需运行时间成反比，故短作业或短进程可获 得较 高的响应比；另一方面，因与等待时间成正比，故 长

12、作业或长进程随着其等待时间的增长，也可获得较高的 响应比。这就是说，算法既优待了短作业或短进程， 又照顾了先来者。 第三章 处理机调度 第三章 处理机调度 . 轮转法轮转法 （ ）算法是一种剥夺式的 进程调度算法，它依据公平服务的原则，将时间划 分成一个个的时间片（记为S），并以为单位，轮转地为 各个就绪进程一次分配一个时间片。 以前述的三个进程为例，考察算法的执行情况及其 调度性能。设 ，则有： P1 P2P3P1P2P1P1P1P1 04811 151721 25 2930 第三章 处理机调度 进程首先执行一个时间片并被剥夺，其周期 所剩余的 放到以后执行；执行一个时间片后也 被剥夺；的时

13、值为 ，不足一个时间片。第 二轮开始，又由先执行一个时间片后被剥夺； 这次 只执行 。至此，和的周期已先后完成， 故随后连续个时间片都分给了，直至完成，在最 后一个时间片里，只执行了 。容易算出，该例的 平均等待时间和平均周转时间分别为： )(33.193/ )111730( )(43/ )840( msT msW 第三章 处理机调度 N RT S 其中，为系统的响应时间上限，为系统中的进 程数目上限。例如，设 ，则 0.1 。 第三章 处理机调度 . 最高优先级法最高优先级法 优先级通常是用一个整型数来表示，称为优先数。对于 不同的系统，既可以用较大的数也可以用较小的数来表示较 高的优先级，

14、这并无统一的规定。例如，中的优先 数的取值范围为，且规定优先数愈小其 表示的优先级愈高。 优先级的设置分为静态和动态两种方式： （）静态设置方式 （）动态设置方式 第三章 处理机调度 设有五个就绪进程，它们各自的本次周期的长度、 初始优先数及进入就绪队列的相对时刻如下所示： 第三章 处理机调度 在非剥夺的静态设置方式下，执行情况如下： P2P1P5P3P4 0 436 526062 在进程执行完时，已进入就绪队列，因其优先级较高， 故先于和之前执行。可算得这些进程的平均等待时间 、平均周转时间以 及平均带权周转时间分别为： )(575. 8)(96.39)(2 .27msTmsTmsW 第三章

15、 处理机调度 . 多级反馈队列多级反馈队列 多级反馈队列就是综合了、和的 一 种进程调度算法，其基本思想如下： （）系统按优先级别设置个就绪进程队列，第一级队 列的优先级最高，以下逐级降低，第级队列的优先级最低； （）每个就绪队列对应有一个时间片Si（i，2, ， n），且有，一般有2Si； （）除对第级队列按调度外，对其余各级队列均 按调度； 第三章 处理机调度 （）系统每次总是调度级别较高的队列中的进程，仅 当该队列为空时，才去 调度下一级队列中的进程； （）当现行进程正在执行它的周期时，如果发 生了时间片中断或有进 程进入更高级的就绪队列时将引起 剥夺，对前一种情况，现行进程将进入下一 级队列，对后 一种情况，现行进程则进入本级队列末尾。当一进程被唤 醒时，它进入的是原先离开的那个队列，即与其当前优先 级对应的就绪队列。可见，一个进程的