操作系统第3章处理器管理

第三章处理器管理

要求：

♦:♦掌握作业调度、进程调度的功能。

♦:♦掌握常用调度算法的基本思想，会评价

其性能（如用平均周转时间和平均等待

时间）。

处理器管理的任务

所谓进程的运行，就是给进程分配处理

器，也就是将进程调度到处理器上执行程序。

在进程管理中，负责进程运行的部分称

为进程调度，或CPU调度或处理器管理。

从进程的角度来看，它关心如下问题：

1、进程被创建以后，何时能够开始运行?

也就是说何时能够获得处理器？

2、获得处理器后，能运行多久？何时会

失去处理器？以何种方式失去？（自愿放

弃或被抢占）

3、在失去处理器时，应保存什么信息？

谁来保存？

4、在多个进程竞争处理器的情况下，

需要满足什么条件才可以再次获得处理

器？谁来作这种裁决？是否公平？

5、当再次获得处理器时，如何继续上

次的工作？

CPU是一种资源。从资源管理的角度来看，关心的

问题如下：

1、按照何种策略，根据什么条件，选择下一个应

该获得处理器的进程。

2、如何实现进程的切换？包括：

■如何将处理器的现场信息保存在当前进程的PCB

中？

■如何根据新选中进程的PCB恢复处理器的现场？

3、如何回收处理器资源？即如何再次获得处理器

的控制权？

处理器管理的任务

回答进程所关心问题的程序叫进程调度。

回答资源管理所关心问题的程序CPU调度。

操作系统是一个资源管理者，包括处理器

资源。因此，操作系统的设计者关心的是CPU调

度，它要解决的问题是：进程选择算法、进程

切换方法、处理器回收方法。

从资源管理的角度来看，所谓处理器管理

就是对处理器资源的分配和回收。

处理器资源只能分配给进程。

从进程管理的角度来看，所谓处理器管理

就是在所有就绪的进程中，找一个最值得运

行的进程，让它占用处理器。

现实社会中，这类工作称为调度。所以处

理器管理又叫CPU调度，或进程调度。

3.1作业调度

在早期批处理时代，调度是以作业为单

位的。因此，那时的处理器管理又称为作业

倜度。

作业调度的任务是：从处于后备状态的

作业中选择一个作业，为其分配资源，让它

进入主机运行。

此时的作业调度程序非常简单，运行频

率也很低，不存在作业切换，也不用担心处

理器资源的回收问题。

为了提高处理器的利用率，人们提出了

多道程序的概念，允许在系统中同时存在

多个作业。

这时作业调度的任务是：从处于后备

状态的作业中选择一个或一批作业，让它

（它们）进入主机，为它们创建进程，准

备运行。

多道批处理系统中，作业调度的主

要工作是选择作业、创建进程。

为了充分发挥资源的作用，应合理

搭配作业，并控制系统中作业的数量。

3.1作业调度

进入主机的作业并不一定能够立刻运行,

还需要另外一个调度程序为它们分配CPU,这

就是CPU调度。

作业调度又称为高级调度、宏调度、长

调度等，它选择的作业具有了获得处理器的

资格。

CPU调度又称为低级调度、微调度、短调

度等，它选择能够立刻投入运行的进程，并

将处理器分配给它。

两者的关系如下图:

时间片用完

备

后

业

作

列

队

等待

队列

作业调度与CPU调度的关系

作业调度与进程调度的关系

1）功能不同

2）执行频率不同

作业调度执行的次数很少，进程调

度执行频繁。

作业的概念主要用于批处理系统，这

类系统的设计目标是最大限度地发挥各种

资源的利用率和保持系统内各种活动的充

分并行。

批处理系统既需要作业调度，也需要

进程调度程序。

分时系统中，用户与系统直接交互,

通过键盘、鼠标等直接创建和启动进程,

不再需要作业调度。

类似地，实时系统也不需要作业调

度。

3.2进程调度

进程调度是玩魔术的程序，它让处理器在各个进程之间飞

快地轮转，从而给每个进程都造成一个假象，认为自己在独占

实际的CPU

e工幡/，3.2进程调度

进程调度要解决的问题是：进程选择算法、进

程切换方法、处理器回收方法。首先考虑处理器的

回收问题。

在下面几种情况下，操作系统会再次获得CPU

的控制权。

1、进程请求操作系统服务

2、进程终止,中断

3、进程运行出错

4、外部中断>

操作系统在获得处理器控制器权后，首先

完成相应的中断处理，而后根据情况决定：

(1)把处理器的控制权还给被中断的进程。

(2)产生一次调度，将处理器的控制权交

给另一个进程。

即使进程不作系统调用、不产生异常操作,

即使所有的外部设备都不产生中断，因为有时

钟的存在，操作系统也会周期性地回收到处理

器的控制权。

再考虑进程的切换问题。

所谓进程的切换就是处理器现场的切换。

就是将处理器当前的现场保存起来，而后用

另一个进程的信息重新设置处理器的现场。

切换在调度程序中完成。

不同处理器提供了不同的进程切换机

制，包括需要保存的内容及切换的方法。

如InteI处理器需要保存的内容大致是

TSS（任务状态段），切换的方法包括：

1、直接caII或jmp一个TSS。

2、切换系统堆栈，而后通过指令正常返回

剩下的问题是：如何选择下一个运行

的进程？

进程选择算法的好坏直接影响到处理

器管理的好坏，进程管理的好坏，甚至一

个操作系统的好坏，因此，需要很仔细地

选择、设计进程选择算法。

在选择、设计具体的调度算法之前，先确

定调度的时机。

下列情况会触发进程调度：

1、正在运行的进程需要等待某些资源或

某个事件，国而自原放弃CPU。

2、正在运行的进程用完了自己的时间片。

3、系统中发生了某个事件（I/O、同步信

号等），使得某个正在等待的进程变成

就绪或有新创建进程，而且其优先级高

于当前进程。

4、当前进程终止。

第1和第4是进程本身自愿放弃处理器的

控制权，属于非抢占式调度

(nonpreemptive)。

第2和第3是抢占式调度(preemptive)

因为当前进程的CPU是被强行收回的，并非

出于进程的自愿。

非抢占式调度比较容易设计，它不需

要考虑太多的保护。

而抢占式调度却要考虑各种数据结构

的保护问题，考虑资源的互斥即死锁问题,

所以抢占式调度的设计更加困难。

但抢占式调度会改善系统的响应能力,

使系统反应速度更快。

如果整个操作系统内核都不允许抢占，

那么该系统称为非抢占式操作系统。

Linux2.6之前的版本是非抢占式的，它

的抢占只发生在由内核切换回用户空间之前。

如果当前进程的时间片用完，或刚就绪进程

的优先级较高，当前进程只是收到一个标志

(need_resched)。

即使内核允许抢占，抢占的动作也会被

推迟到中断处理完成之后。如Linux2.6版、

Windows2000等。

3.3性能评价标准

确定调度策略时考虑的主要因素：

1、应保证实现系统的设计目标。

2、公平对待所有作业或进程。

3、均衡使用资源，尽量使系统中各种资

源都同时得到利用。

4、兼顾响应时间和资源利用率。

5、基于相对优先级，但避免无限延期。

6、系统开销不应太大。

算法的评价标准

可以将评价标准分为面向用户的和面向系

统的。

1、面向用户的评价标准

(1)响应时间。从用户提交请求到收到

第一个应答所需要的时间。

响应时间=进程等待运行的时间+产生第一个

输出的时间。

(2)周转时间。从进程创建到终止之间

的时间间隔，包括进程实际的运行时间、等

待资源的时间、等待调度的时间等。

好的调度算法应尽量减少进程等待调度

的时间，从而减少其周转时间。

(3)死线(DeadIine)。一个进程最后

完成的期限。如果允许进程声明自己的死线,

那么好的调度算法应尽可能的满足各进程的

死线要求，并支持尽可能多的进程。

(4)可预言性(PredictabiIity)。同

一个程序(作业)的每次运行应该花费大致

相同的时间和代价，不管系统的负载情况如

何。

e工幡/，

2、面向系统的评价标准

(1)吞吐量。单位时间内完成的任务

(进程)数量。

从系统角度来看，处理器调度的目的是

最大化处理器的利用率。

吞吐量取决于每个进程的运行长度，但

它也受调度算法的影响。

e工幡/，

(2)处理器利用率。百分比，表示处理

器有多忙。

对于大型计算机系统，这是一个重要指

标，但对PC机、实时系统等来说，并不太重

要。

(3)就绪等待时间。进程在就绪队列中

的等待时间。

调度算法不真正影响进程的执行时间或

I/O操作的时间，它仅影响进程在就绪队列中

的等待时间。

(4)公平。公平对待各个进程，不会

出现饿死现象。

(5)优先级。高优先级的进程应该受

到照顾。

(6)均衡利用资源。保证系统中的资

源都处于忙状态。不太使用紧缺资源的进

程应该受到重视，从而平衡资源的使用。

3.4常用的调度算法

下面列举几种常用的调度算法(主要是进

程选择算法)。

一、先来先服务(FCFS)

数据结构：一个单就绪队列，新就绪的进

程被加入到就绪队列的队尾。

选择算法：就绪队列的队头就是下一个要

运行的进程。

例：有三个进程PI、P2、P3,它们顺序

排在就绪队列中。各进程下一次的运行时间分

别为24、3、3o

FCFS调度的执行顺序如下：

PlP2P3

0242730

各进程的就绪等待时间为：0、24、27o

平均等待时间为：（0+24+27）/3=

17o

3.4常用的调度算法

FCFS算法偏爱长进程，因为平均来说，

长进程的等待时间较少，而短进程的等待时

间较长。或者说，短进程得到的服务要比长

进程差。

如上例，各进程得到的服务时间与等待

时间的比(满意度)分别是：8、0.125、

0.11(3/27)o

3.4常用的调度算法

另外，FCFS算法偏爱处理器繁忙型进

程。与I/O繁忙型进程相比，处理器繁忙

型进程会占用更长的时间，它得到的服务

要优于I/O繁忙型进程。

如I/O繁忙型进程通常在等待I/O,此

时处理器繁忙型进程会占用CPU。当I/O繁

忙型进程就绪时，通常还要等待处理器繁

忙型进程。

3.4常用的调度算法

换一种调度方式:

P2P3P1

03630

各进程的就绪等待时间为：0、3、6o

平均等待时间为：(0+3+6)/3=3o

此时，各进程得到的服务时间与等待时间的

比为：8、1、4,要优于FCFS算法。

回顾

处理机管理

作业调度

从后备队列中选择一批作业，创建进程,

准备运行。

进程调度

从就绪进程中选择一个，将处理器分配

给它。

回顾

常用调度算法：

1、先来先服务(FCFS)

2、短进程优先(SPN)

3、轮转法(RR)

4、可变时间片轮转

5、优先级算法

6、多级队列法

7、多级反馈队列法

3.4常用的调度算法

二、短进程优先（SPN）

数据结构：单就绪队列。

算法思想：选择就绪队列中下一次运

行时间最短的进程。

3.4常用的调度算法

如有4个就绪进程Pl、P2、P3、P4,

其预计运行时间是6、3、8、7,贝IJSPN算法

的调度顺序如下：

P2PlP4P3

0391624

3.4常用的调度算法

优点：平均等待时间最短，周转时间最短。

通常I/O繁忙型进程的运行时间都很短，

这类进程又需要尽快得到服务，使用SPN算法

可以缩短系统的响应时间，改善服务质量。

缺点：如果就绪队列中持续出现短进程，

可能会饿死长进程。

e工幡/，3.4常用的调度算法

问题：当一个进程正在运行时，如果一

个新的进程进入就绪队列，而且它的估算时

间比当前进程的剩余时间还要短，应该如何

处理？

1、抢占。立刻调度，将处理器交给新

就绪的进程。

2、非抢占。当前进程继续运行，直到

完成其预计工作，而后再调度。

3.4常用的调度算法

SPN算法又分为抢占式SPN和非抢占

式SPN。

抢占式SPN有时又叫最短剩余时间

优先(ShortestRemainingTime

First)o

3.4常用的调度算法

例：四个进程P1、P2、P3、P4,其到达就

绪队列的时间和期望的运行时间如下：

进程到达时间期望运行时间

P108

P214

P329

P435

非抢占式SPN：

PlP2P4P3

抢占式SPN：

PlP2P4PlP3

3.4常用的调度算法

三、轮转法(RR)

轮转法(RoundRobin)是加了时间片限

制的FCFS算法。

数据结构与FCFS相同：单就绪队列。

基本思想：调度程序从就绪队列中的第一

个进程开始，轮流把CPU分配给队列中的每个

进程，每个进程每次可以运行一个时间片。

3.4常用的调度算法

在三种情况下，当前进程会让出CPU：

1、当前进程在未用完时间片之前就已完成

工作。

2、当前进程在未用完时间片之前就已进入

等待状态。

3、当前进程用完了时间片，仍未完成工作,

它的CPU被剥夺。

轮转法是抢占式的算法。

e工幡/，3.4常用的调度算法

例：有三个进程PI、P2、P3,它们顺序排在

就绪队列中。各进程下一次的运行时间分别为24、

3、3o

假定时间片是4,贝URR调度的执行顺序如下：

PlP2P3PlPlPlPlPl

047101418222630

各进程的就绪等待时间是（10-4）、4、7o

平均就绪等待时间为：（6+4+7）/3=

5.666o

3.4常用的调度算法

主要设计问题：如何确定时间片的长度？

时间片越长，CPU的轮转就越慢，新就绪

进程的等待时间就越长。如果时间片无限长，

轮转法就退变成了FCFS。

时间片过短，会导致调度次数的增加，从

而增加系统开销。另外，过短的时间片会将短

进程的处理分割成几部分，会延长其周转时间。

3.4常用的调度算法

桌面系统的时间片应短，保证短的响应

时间；服务器系统的时间片应长，减少额

外开销。

Linux的时间片是210ms,2.6改为21ms。

Windows的时间片是20ms（桌面）、

120ms（服务器）o

时间片的长度应稍大于一次典型交互

的时间。

3.4常用的调度算法

时间片的长短由以下因素决定：

(1)系统的响应时间。进程数目一定

时，与响应时间成正比。

(2)就绪队列的长度。响应时间一定

时，与就绪进程数目成反比。

3.4常用的调度算法

(3)进程的切换时间。若进程切换时间

为t,时间片为q,贝h/q应不大于某一数值,

如1/10。即相对于进程的转换时间，时间

片不能太短。

(4)CPU运行速度。CPU速度快则时间片

可以短。

3.4常用的调度算法

需求：I/O繁忙型进程（如交互式程序）

的大部分时间都在等待I/O,需要的处理器时

间较少。但一旦其I/O操作完成，就希望能立

刻投入运行，否则会给用户造成系统反映迟钝

的感觉。

轮转法的问题：将就绪的I/O进程加入到

就绪队列的队尾，无法立刻投入运行。

e工幡/，3.4常用的调度算法

改进方法一：增加一个辅助队列，将

刚就绪的I/O进程加入到此队列中。调度程

序先从辅助队列中选择进程，只有当辅助

队列空时，才从就绪队列中选择进程。

改进方法二：将刚就绪的I/O进程加入

到就绪队列的队头。

3.4常用的调度算法

I/O

兀

成

I/O队列n

3.4常用的调度算法

四、可变时间片轮转法

调整的方法是：在每一轮周期开始时，根据就绪

队列中进程的数目计算出这一轮的时间片，并开始轮

转。

在轮转开始之后，新就绪的进程不允许加入就绪

队列，因而也不参加轮转。

轮转一周以后，新就绪进程加入队列，再根据就

绪队列中进程的数目重新计算时间片，开始下一轮轮

转。对长进程，可以适当增加其时间片的长度。

3.4常用的调度算法

五、优先级

基本思想：根据进程的紧急程度给进程

指定优先级，如给希望尽快得到CPU服务的

进程以较高的优先级。指定进程的优先级后,

可以根据优先级选择进程。

3.4常用的调度算法

选择方法：选择优先级最高的就绪进

程；如有多个优先级最高的进程，则选最

早到达者(FCFS)o

数据结构：单就绪队列，也可以采用

多就绪队列。

新就绪的进程加入到队尾。

调度程序遍历就绪队列，选择遇到的

第一个具有最高优先级的进程。

3.4常用的调度算法

优先级调度的关键是：如何确定进程的优

先级？

确定优先级的方法有两种：静态和动态。

工、静态。在进程创建时确定其优先级，

一旦确定就不再改变。

静态优先级难以反映进程动态的变化。

e工幡/，3.4常用的调度算法

静态优先级分内部定义和外部指定。

内部定义：利用某些可度量的量一次

性地计算进程的优先级。如预计的进程运

行时间、需要的内存量、工/O操作的次数

等。

外部指定：按OS以外的标准设置，如

由用户指定。

3.4常用的调度算法

2、动态。在进程运行过程中，根据某些条件的

变化动态地调整进程的优先级。

调整优先级的条件包括：进程已运行的时间、已

等待的时间、预计的执行时间、进程的重要程度等。

如指定进程的优先级是它预计的运行时间的倒数,

则优先级调度就是SPN。

如指定进程的优先级是它在就绪队列中的等待时

间，则优先级调度就是FCFS。

3.4常用的调度算法

优先级调度算法可以是抢占的，也可以是

非抢占的。

抢占：在进程进入就绪队列时，与当前进

程比较优先级。如果新就绪进程的优先级高于

当前进程，则触发调度，抢占当前进程的处理

珀奥tro

基于优先级的抢占式调度可以保证尽快地

运行高优先级进程，缩短其响应时间。

3.4常用的调度算法

非抢占：在进程进入就绪队列时，不

比较其优先级。不管新就绪进程的优先级

是否高于当前进程，都不触发调度，而是

静静地等待。

非抢占式调度实现简单，但会出现优

先级倒挂现象。

e工幡/，3.4常用的调度算法

优先级调度的问题：可能会出现低优先级进程饿

死的现象。

解决办法一：按照进程的年龄（在就绪队列中等

待的时间）调整其优先级，即随着进程年龄的增大，

逐步调高它的优先级，从而获得运行机会。

解决办法二：当进程在就绪队列中等待足够长后,

跃迁其优先级，让它运行，而后再将其优先级降低到

原来的水平。

3.4常用的调度算法

例：Windows的线程有两个优先级：

BasePriority和CurrentPriority,其中

BasePriority是从进程中继承来的，但可

以通过系统调用修改；CurrentPriority

是动态变化的，从工到工5。

3.4常用的调度算法

Windows的线程调度程序采用多级就绪队列。

Windows提供了32个优先级，因而有32个就绪队列。

其中0到15用于普通线程，16到31用于实时进程。

在下列情况下，线程的优先级会跃迁：

等待的I/。操作完成、等待的事件（如信号量）发

生、前台线程就绪、GUI线程被唤醒、线程过分饥

饿。

3.4常用的调度算法

六、多级队列法

系统中的进程对调度的要求是不一样的O

如在前台运行的进程通常是交互式的，需要短的

响应时间；而在后台运行的进程通常是服务器进程，

需要短的周转时间。所以，前台进程的轮转应快，时

间片应短；而后台进程的轮转可慢，时间片应长。

因此，应根据进程的实际情况将其分组，每组进

程采用适当的调度算法。

3.4常用的调度算法

基本思想：

1、提供几个就绪队列，每个队列有自己

独立的调度算法。

2、根据进程的某些特性，如类型、优先

级等，永久性地把进程链入某一队列。

3、整个系统（队列之间）采用另外的调

度算法，如固定优先级的抢占式调度或

规定各个队列占用CPU的比例。

3.4常用的调度算法

高优先级轮转

------»系统进程-----

---------1交互进程-----

低优先级程FCFS

3.4常用的调度算法

七、多级反馈队列法

基本思想：给刚就绪的进程以最高的优先

级，让它尽快投入运行；在进程的运行过程中

不断地降低其优先级，即进程运行时间越长，

它的优先级就越低。

提供多个就绪队列。每个就绪队列的时间片

长度不同，采用的调度算法也可不同。

第一级队列（高）

RR终止

>

第二级队列

RR终止

第N级队列（低）FCFS

，处理器»终止

3.4常用的调度算法

将就绪队列分为N个，每个就绪队列一个优先级。

给每个就绪队列分配不同的时间片。队列的优先

级越高，时间越短；优先级越低，时间片越长。

最低优先级队列采用FCFS调度算法，其它队列采

用时间片轮转调度算法。

第一次就绪的进程进入第一级队列（优先级最

高）；等待进程被唤醒后，进入原来的就绪队列。

系统从第一级队列开始调度，当第一级为空时，

转向第二个队列，依次类推。

运行进程用完一个时间片后，进入下一级就绪队

列。

高优先级进程就绪时，可以抢占CPU,被抢占的

进程回到原就绪队列的队尾。

3.4常用的调度算法

多级反馈队列法特点：

允许进程在各队列之间移动。

比较照顾新的、小的进程，小进程能尽快得到处

理器。

进程等待的时间不计算在内，因此等待工/O操作

的进程不会被降级。

长进程的优先级会被逐渐降低，因而获得处理器

的机会会减少。但长进程的时间片被延长，它每次获

得处理器后，可以运行更长的时间。

进程之间允许抢占，所以短进程的响应时间不会

太长。

3.5多处理器调度

多处理器系统的调度有自己独特的要求。

有多种形式的多处理器系统，如：

工、松散耦合的多处理器。每个处理器都有自己

的内存、I/O通道等。

2、主从形式的多处理器。处理器有分工，如

工/O处理器等，处理器之间有主从关系。

3、紧密耦合的多处理器。各处理器共享同一个

物理内存，由一个操作系统集中控制。

考虑第三种形式的多处理器系统。

e工幡/，3.5多处理器调度

多处理器调度时需要考虑如下问题：

1、如何为进程指派处理器？

2、是否允许在单处理器上运行多道程序?

3、如何调度和切换进程？

3.5多处理器调度

把处理器看成处理器池。

如何指派处理器？

(1)静态。在进程创建时为其指派处理

器，此后该进程就在指派的处理器上运行。

(2)动态。进程可以在任意一个空闲的

处理器上运行。

3.5多处理器调度

谁来指派处理器？

(1)主从。操作系统运行在一台处理器上,

它负责处理器的指派。简单。

(2)同等。操作系统运行在所有处理器上,

每个处理器自己选择进程。复杂。

3.5多处理器调度

是否允许多道程序？

(1)如果进程之间的关系松散，允许在单处理器

上运行多道程序会提高处理器的利用率。

(2)如果进程之间的关系很密切(有大量的交

互)，如只有当它们同时运行时才能获得最佳的性能,

此时，允许在单处理器上运行多道程序反而会降低应

用程序的性能。

在这种情况下，较好的方法是不支持多道程序。

浪费部分处理器资源以获得较高的性能。

3.5多处理器调度

如何选择下一个运行的进程？

(1)所有处理器共用