《操作系统》课程教学资源（PPT课件）第3章 处理机调度与死锁

第三章处理机调度与死锁在多道批处理系统还是分时系统中：X用户数与处理机数的关系？X处理用户进程外，操作系统还要使用CPU如果竞争处理机？怎样充分利用？谁管理处理机的使用?

第三章 处理机调度与死锁 在多道批处理系统还是分时系统中： ❖ 用户数与处理机数的关系？ ❖ 处理用户进程外，操作系统还要使用CPU 如果竞争处理机？怎样充分利用？谁管理处理机的使 用？

要解决的问题WHAT：按什么原则分配CPU一进程调度算法WHEN：何时分配CPU一进程调度的时机HOW：如何分配CPU一CPU调度过程（进程的上下文切换）

要解决的问题 WHAT：按什么原则分配CPU —进程调度算法 WHEN：何时分配CPU —进程调度的时机 HOW： 如何分配CPU —CPU调度过程（进程的上下文切换）

3.1进程调度概述3.1.1进程调度的功能进程调度的任务是控制协调进程对CPU的竞争即按照一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。进程调度是通过进程调度程序来完成的。进程调度程序的主要功能可描述如下：1.记录系统中各进程的执行状况将进程的状态变化及资源需求情况及时地记录到PCB中。通过PCB变化来准确地掌握系统中所有进程的执行情况和状态特征

进程调度的任务是控制协调进程对CPU的竞争即 按照一定的调度算法从就绪队列中选中一个进程，把 CPU的使用权交给被选中的进程。进程调度是通过进 程调度程序来完成的。进程调度程序的主要功能可描 述如下： 1. 记录系统中各进程的执行状况 将进程的状态变化及资源需求情况及时地记录到PCB 中。通过PCB变化来准确地掌握系统中所有进程的执 行情况和状态特征。 3.1 进程调度概述 3.1.1 进程调度的功能

2.选择进程真正占有CPU这是进程调度的实质。即按照系统规定的调度策略从就绪队列中选择一个进程占有CPU执行。进程调度依据的算法是与系统的设计自标相一致。3.进行进程上下文的切换当进程调度选中一个进程占有CPU时，进程调度程序要做的主要工作则是进行进程上下文切换：将正在执行进程的上下文保留在该进程的PCB中，以便以后该进程恢复执行。将刚选中进程的运行现场恢复起来，并将CPU的控制权交给被选中进程，使其执行

2. 选择进程真正占有CPU 这是进程调度的实质。即按照系统规定的调度策略 从就绪队列中选择一个进程占有CPU执行。进程调度 依据的算法是与系统的设计目标相一致。 3. 进行进程上下文的切换 当进程调度选中一个进程占有CPU时，进程调度 程序要做的主要工作则是进行进程上下文切换：将正 在执行进程的上下文保留在该进程的PCB中，以便以 后该进程恢复执行。将刚选中进程的运行现场恢复起 来，并将CPU的控制权交给被选中进程，使其执行

3.1.2.进程调度的方式和调度时机1.进程调度方式（(1）非剥夺方式(Nonpreemptivemode)在非剥夺方式下，调度程序一旦把CPU分配给某一进程后便让它一直运行下去，直到进程完成或发生某事件而不能运行时，才将CPU分给其它进程这种调度方式通常用在批处理系统中。它的主要优点是简单、系统开销小(2)剥夺方式(Preemptivemode)与非剥夺方式不同，这种方式规定，当一个进程正在执行时，系统可以基于某种策略剥夺CPU给其它进程。剥夺的情况有：优先级策略和时间片策略。显然这种调度方式通常用在分时系统和实时系统中，以便及时响应各进程的请求

1. 进程调度方式 (1)非剥夺方式(Non preemptive mode) 在非剥夺方式下, 调度程序一旦把CPU分配给某 一进程后便让它一直运行下去, 直到进程完成或发生 某事件而不能运行时，才将CPU分给其它进程。 这种调度方式通常用在批处理系统中。它的主要 优点是简单、系统开销小。 (2)剥夺方式(Preemptive mode) 与非剥夺方式不同，这种方式规定，当一个进程 正在执行时，系统可以基于某种策略剥夺CPU给其它 进程。剥夺的情况有：优先级策略和时间片策略。显 然这种调度方式通常用在分时系统和实时系统中，以 便及时响应各进程的请求。 3.1.2.进程调度的方式和调度时机

2.进程调度的时机 所谓进程调度的时机，是指什么情况下引起进程 调度程序工作。进程调度的时机是与进程调度的方式 有关的。进程调度的时机如下： 1)正在执行的进程正确完成，或由于某种错误而终 止运行（陷阱或中断）； 2)执行中的进程提出/O请求，等待I/O完成时； 3)在分时系统中，按照时间片轮转，分给进程的时 间片用完时； 4)按照优先级调度时，有更高优先级进程变为就绪 时剥夺方式)： 5)在进程通讯中，执行中的进程执行了某种原语操 作，如P操作、阻塞原语和唤醒原语时，都可能引 起进程调度

2. 进程调度的时机 所谓进程调度的时机，是指什么情况下引起进程 调度程序工作。进程调度的时机是与进程调度的方式 有关的。进程调度的时机如下： 1) 正在执行的进程正确完成, 或由于某种错误而终 止运行(陷阱或中断) ； 2) 执行中的进程提出I/O请求, 等待I/O完成时; 3) 在分时系统中, 按照时间片轮转, 分给进程的时 间片用完时； 4) 按照优先级调度时, 有更高优先级进程变为就绪 时(剥夺方式)； 5) 在进程通讯中, 执行中的进程执行了某种原语操 作, 如P操作、阻塞原语和唤醒原语时, 都可能引 起进程调度

3.1.3进程调度算法评价 对于不同的系统，有不同的设计目标，采用不同 的调度算法。调度算法实质上是个策略问题 面向系统的准则： •单位时间内运行尽可能多的进程 使处理机尽可能保持“忙碌”利用率高 •使内外存，各种/0设备得以充分利用 ·系统资源均衡使用 面向用户的准则： ·周转时间短 。交互式系统的响应时间快 。截止时间保证 ·优先权准则（公平合理）

对于不同的系统, 有不同的设计目标, 采用不同 的调度算法。调度算法实质上是个策略问题 面向系统的准则： ⚫单位时间内运行尽可能多的进程 ⚫使处理机尽可能保持“忙碌”利用率高 ⚫使内外存,各种I/O设备得以充分利用 ⚫系统资源均衡使用 面向用户的准则： ⚫ 周转时间短 ⚫ 交互式系统的响应时间快 ⚫ 截止时间保证 ⚫ 优先权准则(公平合理) 3.1.3 进程调度算法评价

进程（作业）平均周转时间设某进程创建时间为Si，结束的时间为Ei它的周转时间(全过程所用时间）为Ti=Ei-Si系统为它提供的实际服务时间为Tsi则进程平均周转时间T.带权平均周转时间W为：W32uTEZT一小其中，n为被测定进程流中的进程数要设计一个理想的调度算法是一件十分困难的事在实际系统中，调度算法往往折考虑。大多数操作系统都采用比较简单的调度算法

进程(作业)平均周转时间 设某进程创建时间为Si, 结束的时间为Ei 它的周转时间(全过程所用时间)为 Ti =Ei – Si 系统为它提供的实际服务时间为Tsi 则进程平均周转时间T,带权平均周转时间W为： T＝ W= 其中，n为被测定进程流中的进程数  n i=1 n Ti 1  n i=1 Ti n 1 Tsi 要设计一个理想的调度算法是一件十分困难的事, 在实际系统中, 调度算法往往折衷考虑。 大多数操作系统都采用比较简单的调度算法

3.2进程调度算法1.先进先出进程调度算法（FIFO）（先来先服务FCFS）按照进程就绪的先后次序来调度进程优点：实现简单缺点：没考虑进程的优先级2.短作业（进程）优先调度算法（SJFSPF）选择就绪队列中估计运行时间最短的进程投入运行优点：平均周转时间，带权平均周转时间都改善缺点：对长作业非常不利不能保证紧迫性进程得到及时处理估计运行时间不准确

3.2 进程调度算法 1.先进先出进程调度算法(FIFO) (先来先服务FCFS) 按照进程就绪的先后次序来调度进程 优点:实现简单 缺点:没考虑进程的优先级 2.短作业(进程)优先调度算法(SJF SPF) 选择就绪队列中估计运行时间最短的进程投入运行 优点:平均周转时间,带权平均周转时间都改善 缺点:对长作业非常不利 不能保证紧迫性进程得到及时处理 估计运行时间不准确

3.时间片轮转调度算法(RR一RoundRobin）把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列未尾。同时系统选择另一个进程运行分时系统中常用时间片轮转法时间片选择问题：固定时间片、可变时间片（随确定时间片大小的因素：系统响应时间、就绪进程个数、CPU能力

把CPU划分成若干时间片,并且按顺序赋给就绪 队列中的每一个进程，进程轮流占有CPU，当时间 片用完时，即使进程未执行完毕，系统也剥夺该进 程的CPU，将该进程排在就绪队列末尾。同时系统 选择另一个进程运行 分时系统中常用时间片轮转法 时间片选择问题： 固定时间片、可变时间片(随) 确定时间片大小的因素： 系统响应时间、就绪进程个数、CPU能力 3.时间片轮转调度算法(RR—Round Robin)