第三章计算机操作系统

第三章处理机调度与死锁

■处理机调度的层次

■调度队列模型与调度准则

■调度算法

■实时调度

■产生死锁的原因和必要条件

■预防死锁的方法

■死锁的检测和解除

3.1处理机调度的层次

■高级调度

・低级调度

■中级调度

调度和进程状态转换

■、高级调度（作业调度）

」按某种原则挑选作业投入运行

」为作业创建进程

」为选中作业分配资源

作业：用户要求计算机所做的一个相对独立

的任务。

作业步：一个作业可划分成若干部分，

每个部分称为一个作业步。

典型的作业控制过程：“编译，"连接装配，“运行

进程：OS将一个作业步划分为若干作业步任务。

典型的作业步

源程序

▼

编译连接装配

作业控制块(JCB：JobControlBlock)

作业控制块是批处理作业存在的标志

其中保存有系统对于作业进行管理所需要

的全部信息

:、中级调度

」作用，短期调整系统负荷，以平顺系统

」方式,〃挂起，〃激活物

三、低级调度（进程调度）

」按某种原则将处理机分配给就绪进程

」低级调度属操作系统内核，执行频率很高

3.2调度队列的模型和调度准则

■调度队列模型

■选择调度方式和调度算法的若干准则

4、调度队列模型

时间片完

交互用户

事

件

出

现

仅有进程调度的调度队列模型

具有高、低两级调度的调度队列模型

具有三级调度的调度队列模型

作业调度时间片完

后备队列

批量作业TTTTTT进程完成

交互型作业

阻塞，挂起队列

事

件

出挂起

现

阻塞队列

等待事件

—、选择调度方式和调度算法的若干准则

面向用户面向系统

周转时间吞吐量

与性能相关响应时间CPU使用率

最后期限

可预测性公平

其他强制优先级

平衡资源

3.3调度算法

■先来先服务

■短进程优先

■高优先权优先

■基于时间片的轮转调度算法

J调度算法决策模式

非抢占式一只能由进程主动释放CPU

抢占式一OS可以强制获得CPU

衡量调度算法性能的主要参数

平均周转时间：

进程k的周转时间Tk=完成时间-提交时间

平均周转时间T=ZTk/进程数

3.3.1先来先服务和短进程优先调度算法

一、先来先服务

其原则按照进程进入就绪队列先后次序来选择。

FCFS是一种非抢占式算法

例题

进程到达时间运行时间优先权

1032

2265

3443

4656

5821

进程1进程2进程3进程4进程5

039131820

平均周转时间

T=l/5(3+7+9+12+12)=8.60

二、短进程优先调度

■根据PCB估算运行时间，选取运行时间

最短的进程作为调度对象

■短进程优先调度是非抢占式算法

■缺点：会使长进程饥饿。

例题

进程到达时间运行时间优先数

1032

2265

3443

4656

5821

进程1进程2进程5进程3进程4

039111520

T=l/5(3+7+11+14+3)=7.60

可抢占短进程优先调度

」基本思想:从运行到完成所需时间最短

的进程优先得到处理

例题

进程到达时间运行时间优先数

1032

2265

3443

4656

5821

进程1进程2进程3进程5进程2进程4

0348101520

T=l/5(3+13+4+14+2)=7.20

3.3.2高优先权优先调度算法

•非抢占式优先权算法

•抢占式优先权调度算法

•高响应比优先调度算法

例题

进程到达时间运行时间优先数

1032

2265

3443

4656

5821

非抢占式优先权调度

进程1进程2进程4进程31进程5

039141820

T=l/5(3+7+14+8+12)=818

例题

进程到达时间运行时间优先数

1032

2265

3443

4656

5821

抢占式优先权调度

进程11进程21进程4|进程2|进程3|进程11进程引

0261113171820

T=l/5(18+11+13+5+12)=11.8

高响应比优先调度

等待时间+运行时间

响应比二

运行时间

■特点：是先来先服务调度和短进程优先

调度的折中。但每次调度都需要计算进

程响应比，系统开销较大。属于非抢占决

策模式

例题

进程到达时间运行时间优先数

1032

2265

3443

4656

5821

进程1进程2进程3进程5进程4

039131520

T=l/5(3+7+9+14+7)=8.00

3.3.3基于时间片的轮转调度算法

■时间片轮转法

■多级反馈队列调度

一、时间片轮转法

把CPU的时间分割成时间片，处于就绪

状态的进程轮流获得时间片。

时间片轮转调度算法是抢占算法。

其调度算法的性能取决于时间片Q。

例题

进程到达时间运行时间优先数

1032

2265

3443

4656

5821

Q=4（时间片为4）

进程1进程2进程3进程4进程2进程5进程4

0371115171920

T=l/5(3+15+7+14+11)=10.00

、多级反馈队列调度

RQO

RQ1

FOi

调度过程

」系统中有多个就绪队列

」各级就绪队列具有不同的时间片

」优先级最高的第一级队列的时间片最小，隙着

队列的级别增加，时间片成倍增加。

」各级队列均按FCFS原则排队

」当一个新进程就绪后排在第一级队列末尾

」若当前运行进程使用完时间片后运行任务尚未

完成，则该进程被排在下一级就绪队列的末尾

」当第一级队列为空后，OS从第二级就绪队列

调度进程

例题

进程到达时间服务时间优先数

1032

2265

3443

4656

5821

Q=2**N（每级反馈队列每一级时间片以2幕次方递增）

P41

P2P3P5P1P2P3P4

024681011151720

T=10.6

■多级反馈队列算法是时间片轮转算法和优

先级算法的综合和发展。

■不必估计进程的执行时间

■属Id抢占决策模式

3.4实时调度

・实现实时调度的基本条件

•实时调度算法的分类

•常用的几种实时调度算法

一、实现实时调度的基本条件

」提供必要的信息

〉就绪时间，开始/完成截止时间，处理时间

资源要求，优先级

」系统处理能力强

Sum（处理时间凋期）v=l

」采用抢占式调度机制

」具有快速切换机制

快速响应外部中断

快速分派任务

假定系统中有帆个周期性的实时任务，它们的

处理时间可表示为G，周期时间表示为尸〃则

必须满足下面的限制条件：

其中N为处理机个数

例

■一个实时系统中有下面四个周期性出现

的进程：

P1:需要20毫秒，每40毫秒出现一次

P2:需要60毫秒，每500毫秒出现一次

P3:需要5毫秒，每20毫秒出现一次

P4:需要15毫秒，每100毫秒出现一次

问该系统在单CPU上是否可调度，为什么?

P3|Pl|P31PliP4|P31Pl|P31P21P41P21P3|Pl曲加1|P2

520406080100120

:、调度算法分类

■非抢占式调度算法

♦轮转调度

♦优先调度

■抢占式调度算法

♦基于时钟中断

♦立即抢占

非抢占式轮转调度

］实时进程到达

|放在就绪队列尾

P1P2Pnp

非抢占式优先权调度

实时进程到达

II放在就绪队列头

P1P

基于时钟中断的抢占式调度

实时进程到达

33剥夺点（时钟中断到来时）

PIP

立即抢占的优先权调度

实时进程到达

33立即剥夺

PIp

三、常用的几种实时调度算法

•最早截止时间优先

・最低松弛度优先

最早截止时间优先调度（非抢占式）

1

开始截止时间1J

任务执行.1・3

tttt

任务到达1I乙J1。叶4

最早截止时间优先调度（抢占式）

A的周期20ms,B2

处理时间10ms

B的周扇50ms,

处理时间25ms

到达时间、执行时间

和最后期限

O102030405060708090100时间"ms

固定优先级调度AlBlA2BlA3B2A4B2A5B2

（A有较高优先级）―f一||I一|一

AlA2B1A3A4A5,B2

（错过）

固定优先级调度B]|A2|A3___B2__A5|_______

（B有较高优先级）।।।（T

AlA2BlA3A4A5,B2

（错过）（错过）

使用完成最后期限

AIBI|A2BIA3B2A4B2A5|一

最早和最后期限调度

111T\

A1A2B1/A4A5,B2

最低松弛度优先算法

选择松弛度最低的任务先运行

松弛度=完成截止时间-处理时间-当前时间

例

A1A2A3MA5

II"II

40"lQO~80

*B1B2

A的周期20ms,处理时间10ms

B的周期50ms,处理时间25ms

5570

010456080

A1-10A2-10A3-10A4-10

B1-25B1-15B1-5B2-20

3.5产生死锁的原因和必要条件

■死锁问题概述

■产生死锁的原因

■产生死锁的必要条件

■处理死锁的基本方法

3.5.1死锁问题概述

死锁是指计算机系统和进程所处的一种状态。

常定义为：在系统中的一组进程，由于竞争

系统资源或由于彼此通信而永远阻塞，我们

称这些进程处于死锁状态。

死锁的例子

ProcessPlProcessP2

GetRIGetR2

♦♦♦

•••

GetR2GetRI

♦♦♦

•♦•

releaseRIreleaseR2

♦••

♦♦•

releaseR2releaseRI

Pl

P1P2都要R1

释放R1

释放R

「e2都要区2

获得R1

获得R

获得R1获得R2释放R1释放R2P2

竞争可剥夺性资源・200k内存

进程P1进程P2

request80kbrequest70kb

kbrequest80kb

352产生死锁的原因

资源不足，竞争资源

进程间推进顺序非法

353产生死锁的必要条件

■互斥

■请求和保持

■不剥夺

■环路等待

■互斥条件:一个资源每次只能给一个进程使用

■不剥夺条件：资源只能由占有者自愿释放

■请求和保持条件:一个进程在申请新资源的同时保持

对原有资源的占有

■环路等待条件:存在一个进程等待队列

{Pi'P?’Pn},

其中Pl等待P2占有的资源，P2等待P3占有

的资源，…，Pn等待Pi占有的资源，形

成一个进程等待环路

3.5.4处理死锁的基本方法

■预防死锁

■避免死锁

■检测死锁

■解除死锁

3.6预防死锁的方法

■预防死锁

■系统安全状态

■利用银行家算法避免死锁

3.6.1预防死锁

」在系统设计时确定资源分配算法，保证

不发生死锁。具体的做法是破坏产生死

锁的四个条件之一

，预防死锁是一种较可取的方法，但资源

的利用率较低◎

1、破坏互斥条件

互斥是正确使用非共享资源的唯一手段。

故不能通过取消互斥来预防死锁。

2、破坏不剥夺条件

适用于状态容易保护，稍后又容易恢复的

资源。如CPU,内存。

3、破坏请求和保持条件

」采用预先静态分配法：每个进程执行前,

一次分配其所有资源

」允许进程仅当自己未占有资源时才申请

资源。

4、破坏环路等待条件

■有序资源分配

为使“循环等待”条件不满足，我们把所有

资源按类型进行排队，并赋予不同的编号。

每人、井产/申请按序号递增次序进行

1'释放按序号递减次序进行

优点：较前几种，改善资源的利用率。

缺点：进程实际需求和资源顺序不一致

会造成资源浪费。

例如:1,2,3,…，10

PP2

••P3.......P10

申

请

申

1H清1

申

申

请32

H清

申

申

请95

H清

-:・

3.6.2系统安全状态

■安全状态：指系统能按某种进程顺序如

<P1,P2…PN>为每个进程分配资源直至

满足其最大需求，使每个进程顺利完成。

■不安全状态：在系统中不存在这样的序列。

安全状态举例

C初值为10

安全状态

不安全状态

由安全状态向不安全状态的转换

安全状态不安全状态

死锁状态

363利用银行家算法避免死锁

一、死锁避免定义

在系统运行过程中，对进程发出的每一个

系统能够满足的资源申请进行动态检查，

井根据检查结果决定是否分配资源，若分

配后系统可能发生死锁，则不予分配，否

则予以分配

・•银行家算法

假定某银行家有一笔资金可供一批顾客借用,

并假定：

」每个顾客预知他的最大借款总额，且不超过银行

家拥有的可用资金总和。

」每次借款以一万元为单位。

」每当顾客提出借款请求，银行家可立即给予，或

让顾客等一段时间。

」只有当顾客达到他的预定最大借款额时，他才在

有限时间依次归还。

银行家算法数据结构

■Available：一个长度为m的向量，表示每类资源的

可用数目。如果Available[j]=k,表明Rj类资源有k

个。

■Max：一个mXn矩阵，定义每个进程的最大资源需

求数，如果Max[i,j]=k,表示进程i需要Rj类资源有k

个。

■Allocation：一个mXn矩阵，定义当前分配给每个

进程每类资源的数目。如果Allocation[i,j]=k,则表

示进程I获得：Rj类资源有k个

■Need：一个mXn矩阵，表示每个进程还需多少资

源。如果Need[i,j]=k,表示进程I还需要Rj类资源

有k个。表示进程I需要Rj类资源有k个

银行家算法

设：Request1是进程Pi的请求向量

当Pi发出资源请求后，系统按如下步骤进行检查:

1＞如果Requesti^Needi则goto2,否则认为出错。

2、如果Reqllesti«Avai加ble贝!|goto39否则表示

足够资源，Pi等待。

3、系统进行试探分配，并求该相应数据结构数据

Available：=Available-Requesti

Allocationi：=Allocatioiii+Requesti

Needi：=Needi-Requesti

4、系统执行安全性算法：安全，把资源分配给Pi,

否则，Pi等待。

安全性算法

1、设Work和Finish是长度分别为m,n的向量

初始值Work：=Available>Finishi：=False（所有）

2、从进程集合中找到一个能满足下列条件的进程

a.Finishi=False

b.Needi<Work如找到goto3,否则goto4

3、当进程Pi获得资源后，顺利执行，直至完成，并释

放分配给它的资源。Work：=Work+Allocationi

Finishi：=Truegoto2

4、如果所有进程的Finishi=True则表示系统安全，否则

为不安全。

例

假定系统中五个进程{P0…P4}和三种资源

{A,B,C},资源数量分别为10,5,7,在

T0时刻的资源分配情况如下表。

MaxAllocationNeedAvailable

P07,5,30,1,07,4,33,3,2

PI3,2,22,0,0b2,2

P29,0,23,0,26,0,0

P32,2,22,1,10,1,1

P44,3,30,0,24,3,1

、TO时刻安全性

WorkNeedAllocationWork+AllocationFinish

Pl332122200532T

P3532011211743T

P4743431002745T

P27456003021047T

P010477430101057T

TO状态是安全

2、Pl请求资源

Pl请求向量Request1(1,0,2)

系统按银行家算法进行检查：

■Request1(1,0,2)<Needl(1,2,2)

■Request1(1,0,2)<Available(3,3,2)

■系统先假定为Pl分配资源，并求该数据结构的值

Available=Available-Request1=(2,3,0)

Allocation1二Allocation1+Request1=(3,0,2)

Needl=Need1-Request1：=(0,2,0)

■系统调用安全性算法，检查其安全性

WorkNeedAllocationWork+AllocationFinish

Pl230020302532T

P3532011211743T

P4743431002745T

P0745743010755T

P27556003021057T

状态是安全，Pl的请求能满足

3、P4请求资源

P4请求向量Request4(3,3,0)

系统按银行家算法进行检查：

■Request4(3,3,0)<Need4(4,3,1)

■Request4(3,3,0)<Available(2,3,0)

让P4等待

4、P0请求资源

PO请求向量Requesto（0,2,0）

系统按银行家算法进行检查:

」RequestO（0>2》0）<NeedO（7》4》3）

JRequestO（0>2》0）<Available