It计算机课件 操作系统第三章

操作系统

第三章处理机调度与死锁

3-1处理机调度的基本概念

3・2调度算法

3.3实时调度

3・4多处理机系统中的调度

3・5产生死锁的原因和必要条件

3・6预防死锁的方法

3・7死锁的检测与解除

3.1处理机调度的基本概念

■处理机管理的工作是对CPU资源进行

合理的分配使用，以提高处理机利用

率，并使各用户公平地得到处理机资

源。分配处理机的任务是由处理机调

度程序完成的。

处理机管理

一个作业被提交后，必须经过处

理机调度后得到处理机的使用权后才能

开始执行。

对批处理作业，要经历“作业调

度”（高级调度）和“进程调度”（低

级调度）后才能获得处理机；对终端型

作业，要进程调度后才能获得获得处理

机并执行。

限理机管理

作业调度的功能

I■作业调度的主要任务是完成作业从后

*备状态到执行状态和从执行状态到完

1成状态的转变。

-作业调度功能：

■1.记录已进入系统的各作业的情况

(JCB,JobControlBlock)；

■2.按一定的调度算法，从后备作业中

选择一个或几个作业进入系统内存；

■3.为被选中的作业创建进程，并且为

其申请系统资源；

■4.作业结束后作善后处理工作。〔处理机管理

作业控制块(JCB,JobControlBlock)

作业名每个作业进入系

估计运行时间

最迅总成时间统时由系统为其

资哪要求要求的内存量建立一个作业控

要求外设的类型及台数制块

要求文件量和输出量JCB(Job

进入系统的时间ControlBlock),

开始运行的时间它是存放作业控

资源使用情况已运行的时间

内存地址制和管理信息的

外设台号数据结构，主要

类型控制方式

作业类型信息见左图。

优先级

状态处理机管理

出

备作业队列空

是分配资源

按调度算法从作

业中选出一作业调用进程管理程序建

I立进程，进入就绪队列

调用存储、设备管理

程序，审核资源要求

放弃该否一进程调度

作业贲源要求能满足?

作业调度和进程调度的过程

\局级、/H

组3M乱展逋度或长程调度;

又称步

1高绘又称为中程调度，目的是为了、

提高内存利用率和系统吞吐量。

2低i

将暂吐不能运行的进程调

3中级调

非抢占式：适用于批处理系统

抢占式：时间片原则，优先权)

原则，短作业优先/

机管理

二调度队列模型

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

分时系统正在执行的进程可能出现完成、

用完时间片或阻塞三种情况。

时间片完

■具有高级和低级调度的调度队列模型

I该模型具有两级调度，并根据阻塞事件设置

多个阻塞队列

■同时具有三级调度的调度队列模型

三、选择L作业的周转时间:

包括

■1—Ti=tci-tsi

带权周转时间：平均带权周转时间：

_tj

Wi——-w=^Ewi

Lr

苗作业实际运行时间

3、截止丽的保证

4、优先权准则处理机管理

面向系统的准则

工、系统吞吐量高

2、处理机利用率好

3、各类资源的平衡利用

处理机管理

32调度算法

*调度算法是指根据系统的资源分配

策略所规定的资源分配算法。

对于不同的系统和系统目标通常

采用不同的调度算法。这些算法有的适

用于作业调度，有的适用于进程调度，

有的两者都适用。

处理机管理

、先来先服务和短作业(进程)优先调度算法

先来先服务调度算法(FCFS)

作业来到的先后次序进行调度的换句话

说，调度程序每次选择的作业是等待时间最

久的，而不管作业的运行时间的长短。

每次调度都是从后备作业队列中，选

择一个或多个最先进入该队列的作业将其调

入内存，分配资源，创建进程，并进入就绪

队列。

特点：优点是实现简单效率较低，有利王£

作业，CPU繁忙型作业：处理机管理

进程到达服务开始执完成周转带权周

名时间时间行时间时间时间转时间

A010111

B110011011001

C21101102100100

D31001022021991.99

周转时间=完成时间■提交时间，带权周转时间二周

转时间/服务时间

■短作业（进程）优先调度算法（SJF）

短作业（进程）优先调度算法是从就绪队

列中选出估计运行时间最短的进程，将处理机

分配给它，使其执行到完成，或发生某事件而

被阻塞放弃处理机，再重新调度。

算法缺点：

1、对长作业不利；

2、未考虑作业的紧迫程度；

3、算法有可能做不到短作业优先调颐理机/

进程名ABCDE平均

情况

到达时间01234

调度算屋、

服务时间43524

完成时间47121418

FCFS周转时间461011149

带权周转时间1225.53.52.8

完成时间4918613

SJF周转时间4816398

带权周转时间12.673.11.52.252.1

■先来先服务和短作业优先算法都有

其片面性;先来先服务调度算法只

考虑作业的等待时间，而忽视了作

业的运行时间，短作业优先算法则

相反，只考虑了作业的运行时间，

而忽视了作业的等待时间。

二，高优先权(FPF)优先调度算法

“最高优先权作业调度算法,是从后备队

列中选援若干个优先权最高的作业，并装入

内在运行；

最高优先权进程调度算法，是把处理机

分配给就绪队列中优先权最高的进程，此时

可将该算法分成如下两种：

1、非抢占式优先权算法

2、抢占式优先权调度算法处理机管理

1、非抢占式优先权算法

装统一旦将处埋机（CPU）分配给运行队

列中优先权最高的进程后，该进程便一直

执行下去，直至完成或因发生某事件使该

进程放弃处理机时，系统方可将处理机分

配给另一个优先权高的进程。这种调度算

法主要用于批处理系统中，也可用于某些

对实时性要求不严的实时系统中。Li、

:处理机管理

2、抢占式优先权调度算法又称可剥夺调度

■*算法的本质就是系统中当前运行的进程永

远是可运行进程中优先权最高的那个。

-在这种方式下，系统同样是把处理机分配给

优先权最高的进程，使之执行。但是只要一

出现了另一个优先权更高的进程时，调度程

序就暂停原最高优先权进程的执行，而将处

理机分配给新出现的优先权最高的进%

剥夺当前进程的运行。「处理机管理

1因此，在采用这种调度算法时,每当出

I现一新的可运行进程,就将它和当前运

行进程进行优先权比较，如果高于当前

进程，将触发进程调度。

-这种方式的优先权调度算法，能更好的

满足紧迫进程的要求，故而常用于要求

比较严格的实时系统中，以及对性能要

求较高的批处理和分时系统中。厂i'

（处理机管理

优先权类型：

静态优先权：进程在创建时确定，在进程

的整个运行期间保持不变；

确定进程优先权的三个依据：进程类型、

进程对资源的要求、用户要求

优缺点：简单易行，系统开销小；不够精

确，有可能出现优先权低的作业长期没有被调

度O

动态优先权：在创建进程时所赋予的优先

权可以随进程的推进或随其等待时间的增加而

改变，以便获得更好的调度性能。

高响应比优先调度算法：即动态改变

作业的优先权，使作业的优先级随等待时

间的增长而以速度C提高，则长作业在

等待一定的时间后就会有机会得到处理机。

优先权变化规律可描述为：

等待时间+要求服务时间

优先权

要求服务时间

d等待时间+要求服务时间响应时间

响应比R=------------------------------=-------------

'要求服务时间要求服务时间

(1)如果作业的等待时间相同，则要求服

务的时间愈短，其优先权愈高，因而该算法有

(2)当要求服务的时间相同时，作业的优先权

决定于其等待时间，等待时间愈长，其优先权

愈高，因而它实现的是先来先服务。

(3)对于长作业，作业的优先级可以随等

待时间的增加而提高，当其等待时间足够长时，

其优先级便可升到很高，从而也可获彳I处理心

:处理机管理

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

［时间片轮转法

*~具体实现:

每次调度时，把CPU分配给队首进程，

并令其执行一个时间片。

当时间片用完后，由计时器发出中断

请求，调度程序便终止该进程的执行，并将

其放在就绪队列末尾。

然后，再把处理机分配给就绪队列甲f

新的队首进程。塞理机管理

■多级反馈队列调度算法

上施过程：

iH设置多个就绪队列T时为各个队列赋予不

同的优先级。第一个队列的优先级最高，第

二个队列次之，其余各队列的优先权逐个降

低。该算法赋予各队列中进程执行时间片的

大小也不同。优先权越高，执行的时间片就

越短。例如，第二个队列的时间片要比第一

个队列的时间片长一倍，……，第弁1个队

列的时间片要比第i个队列的时间片长二Z

处理机管理

2、当一个新进程进入内存后，首先

放入第一队列的末尾，按FCFS原则排队等待

调度。当轮到该进程执行时，若在时间片内

执行完，则准备撤出系统。否则便将该进程

转入第二队列的末尾，再同样按FCFS原则等

待调度执行……

当长作业（进程）从第一队列依次降

到第n队列后，在第n队列中便采取按时间片

轮转的方式运行。

3、仅当第一队列空闲时，调度程序才调

度第二队列的进程，仅当第1—(i・l)队

列均为空时，才调度第i队列中的进程运

行。如果处理机正在第i队列中为某进程

服务时，又有新进程进入优先权较高的

队歹U(第1中的任何一个队列)，则

此时新进程将抢占正在运行进程的处理

机，即由调度程序把正在运行的进程放

回到第i队列的末尾，把处理机分配给新

到的高优先权进程。

SI

S3

图3.3多级反馈队列调度算法

处理机管理

■多级反馈队列调度算法的性能

具有较好的性能，能较好的满足各种

类型用户的要求。

终端型作业用户;

短批处理作业用户;

长批处理作业用户;

处理机管理

3,3实时调度

在实时系统中，存在着若干个实时进

程或任务，它们用来反应或控制某个外部

事件，并且带有紧迫性。所以对实时系统

中的调度提出了某些特定的要求。

处理机管理

.、实时调度的基本条件

1.提供必要的信息

(1)就绪时间。

⑵开始截止时间和完成截止时间。

⑶处理时间。

(4)资源要求。

⑸优先级。

鼠理机管理

2.系统处理能力

.在单处理机情况下，必须满足下列条件:

mC.

2—*L<1

i.=piP；

系统才是可调度的。

其中m为系统中周期性的硬实时任务个数，

Ci为处理时间，Pi为周期时间（m个任务执

行一次所用的时间）/藕、

（处理机管理

若系统中有6个硬实时任务，它们的周期时间

:50ms,而每次的处理时间为10ms,则

:算出，此时是不能满足上式的,因而系

S:不可调度的

解决的方法是提高系统的处理能力，其途

径有二：其一仍是采用单处理机系统，但须

增强其处理能力，以显著地减少对每一个任

务的处理时间；其二是采用多处理机系统。

假定系统中的处理机数为N,则应将上述的限

制条件改为：盟Q

y—L<TV

乙p处理机管理

i=lri

3.采用抢占式调度机制

—当一个优先权更高的任务到达时，允许

,当前任务暂时挂起，而令高优先权任务立

即投入运行，这样便可满足该硬实时任务对

截止时间的要求。但这种调度机制比较复杂。

对于一些小的实时系统，如果能预知任

务的开始截止时间，则对实时任务的调度可

采用非抢占调度机制，以简化调度性

任务调度时所花费的系统开销。'处理机管理

但在设计这种调度机制时,应使所有的

实时任务都比较小，并在执行完关键性

程序和临界区后，能及时地将自己阻塞

起来，以便释放出处理机，供调度程序

去调度那种开始截止时间即将到达的任

务。

限理机管理

4.具有快速切换机制

J普机制应具有如下两方面的能力：

.1）对外部中断的快速响应能力。为使在紧迫

的外部事件请求中断时系统能及时响应，要求系

统具有快速硬件中断机构，还应使禁止中断的时

间间隔尽量短，以免耽误时机（其它紧迫任务）。

（2）快速的任务分派能力。在完成任务调度后,

便应进行任务切换。为了提高分派程序进行任务

切换时的速度，应使系统中的每个运行叫熊单但

适当的小，以减少任务切换的时间开销。（处理机管理

二、实时调度算法的分类

-按实时任务性质的不同，可分为：硬实

时调度算法和软实时调度算法;

-按调度方式的不同，可分为：非抢占调

度算法和抢占调度算法；

-按调度时间的不同，可分为：静态调度

算法和动态调度算法；

■在多处理机环境下，调度算法可分为：

集中式调度算法和分布式调度算义—

鼠理机管理

茸调度方式的不同对调度算法进行分类：

并抢占式调度算法，可分为:

鼻£抢占式轮转调度算法:这是一种常用于分

时系统的调度算法，它只能适用于一般实时

信息处理系统，而不能用于实时要求严格的

实时控制系统。

非抢占式优先调度算法：常用于多道批处理

系统的调度算法，也可用于实时要求不太严

格的实时控制系统

鼠理机管理

-抢占式调度算法，可分为:

基于时钟中断的抢占式优先权调度算法：

用于大多数的实时系统中。

立即抢占的优先权调度算法：

这种算法适用于实时要求比较严格的实时

控制系统。

限理机管理

实时进程要求调度调度实时进程运行实时进程请求调度时钟中断到来时

进程1进程2进程“实时进程当前进程实时进程

3■-———二——--------.，■调度时间，

------调度时间--------------5

⑹基于时钟中断抢占的优先权抢占调度

⑷非抢占轮转调度

实时进程请求调度当前进程运行完成

1实畔程请求调度1实时进程枪占当前

11

i[进程，并立即执行

1[______

当前进程实时进程当前进程实时进程

<-----调度时间——>，-调度时间-►

①）非抢占优先权调度M）立即抢占的优先MSr------

图3.4实时进程调度理机管理

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

匀章早截止时间优先算法即EDF(EarIiest

♦eadlineFirst)算法

截止时间愈早，其优先级愈高。

该算法要求系统中保持一个实时任务就

绪队列，该队列按各任务截止时间的早晚排

序，具有最早截止时间的任务排在队首。调

度时，总选择队首的第一个任务，分配处理

机，并运行。，一^

%理机管理

342

八44八

开始截止时间排序

任务执行1342

任务到达

1234

系统首先调度任务1执行，在任务工执行期间,

任务2、3先后到达，由于任务3的截止时间早于

任务2的，故系统在任务1后将调度任务3执行。

■最低松弛度优先算法即LLF(LeastLaxity

First)算法

艮据任务的紧急程度，来确定任务的优

昙级。紧急程度愈高,所赋予的优先级愈高

算法实现时，要求系统中有一个按松弛

度排序的实时任务就绪队列，松弛度最低的任

务排在队列最前面，调度时总是选择就绪队列

中的队首任务执行。

任务A的松弛度=必须完成时间-本身运行时间-当前时间

该算法主要可用于抢占式任务。flbaWS

■例如，一个任务在200ms时必须完成，

FT它本身所需的运行时间就有100ms,

因此，调度程序必须在100ms之前调度

执行，该任务的紧急程度（松弛程度）为

100mSo又如，另一任务在400ms时

必须完成，它本身需要运行150ms,

则其松弛程度为250mso

处理机管理

例题：假如在一个实时系统中，有两个周

期性实时任务A和B,任务A要求每20

ms执行一次，执行时间为10ms；任

务B只要求每50ms执行一次，执行时间

为25mSo

处理机管理

图3.5A和B任务每次必须完成的时间

处理机管理

在刚开始时。1=0),Al必须在20ms时完成,

去它本身运行又需10ms,可算出A1的松弛

同/10ms；Bi必须在501ns时完成,而它本

身运行就需25ms,可算出Bi的松弛度为25

ms,故调度程序应先调度A1执行。在，2=10

ms时，A2的松弛度可按下式算出：

A2的松弛度=必须完成时间■其本身的运

行时间-当前时间=40ms-10ms-10ms=20ms

(处理机管理

类似地，可算出B1的松弛度为15ms,故调

度程序应选择B1运行。在，3=30ms时，A2的松

弱隙已减为0(即4010-30),而B1的松弛度为15

ms(即50・5・30),于是调度程序应抢占的处理

机而调度A2运行。在t4=40ms时，A3的松弛度

为10ms(BP60-10-40),而的松弛度仅为5ms(

即50-5-40),故又应重新调度Bi执行。在ts=45

ms时，Bi执行完成，而此时A3的松弛度已减为

5ms(即60-10-45),而B2的松弛度为30ms(即

100-25-45),于是又应调度A3执行。丁女锦

J处理机官理

产6=55ms时,任务A尚未进入第4周期,

施任务B已进入第2周期,故再调度B2执

行。在t7=70ms时，A4的松弛度已减

至0ms(即80-10-70),而B2的松弛度

为20nls(即100-10-70),故此时调度

又应抢占B2的处理机而调度A4执行。

图3-9利用ELLF算法进行调度的情况

处理机管理

3.4多处理机系统中的调度

提高计算机系统的两种途径:

・、提高构成计算机的元器件的运行速度；

.、改进计算机系统的体系结构，特别是在系统

中引入多个处理器或多台计算机，以实现对信

息的高度并行处理，达到提高系统吞吐量和可

靠性的目的。

处理机管理

一、什么是多处理机系统

概念：是一个具有两个或多个处理机并能相互

进行通信以协同一个大的给定问题求解的计算

机系统。

特点：1）有两个或多个处理机

2）共享主存或高速通信网络

3）共享输入输出子系统

4）有单一完整的操作系统

5）各级硬件和软件相互作用

主要功能：

•进程分配

更好的利用多机硬件

资源在处理机之间的分配

改善程序的响应时间

更好地处理处理机的负载平衡

处理机间的协调和同步

因处理机故障引起的系统重组

处理机管理

]■广义上说，使用多处理机协调工作,来完

疆户所要求任务的计算机系统,这包括了并

行处理系统，也包括了分布式系统，以及在同

一计算机系统里共享内存的多处理机系统。

广义的计算机系统的一个共同的特点是有

n个处理器(n>l),能做到真正的并行处理，也就

是能同时执行n条指令.

处理机管理

二多处理器系统的类型

密耦合MPS和松弛耦合MPS(MultiProcessor

System

系统中包含的在处,在

系统中有多个类型的处理器单元〕

其功能和结构各不相同，其中有一4

主处理器，有多个从处理器。

管理

三、进程,

对称

多采用主一从式OS,即OS的核心部

分驻留在一台主机上，从机上是用户'

程序，进程调度由主机执行。当一台从机

空闲时，便向主机发送信号，等待主机/

为其分配进程。

池一个空

/处理器上。所以一个进程

静态分配?

的运行，可能被随机地分配?

动态分配q

当时是空闲的某一处理矍（

非对称MPS加

管理

四、进程(线程)调度方式

■自调度(Self-Scheduling)方式

自调度机制

自调

1、瓶颈问题；多处理器只能互

访问该队列2、低效性；一旦阻塞因

更换处理机就要频繁的拷贝数据

3、线程切换频繁

管理

T成组调度(GangScheduling)方式

注也人出锂出的

土调…度方法：将一个进程中的一

组线程分配到一组处理器上去。

在成组调度时，如何为应用程序分配处理器时间?

1)面向所有应用程序平均分配处理器时间

2)面向所有线程平均分配处理器时间

%:理机管理

»1ftSSl

ft®2MS2

MS3

W4处螂4

⑷期37.5%(b)据费15%

处理机管理

成组调度方式的主要优点：若一组相互合

作的进程或线程，能并行执行，则可有效地减

少线程（进程）阻塞情况的发生，从而减少线

程的切换，改善系统的性能。

止匕外，也相应地减少了处理器分配和调度

的频率，所以也减少了开销。

处理机管理

■专用处理器分配方式

■为进程中的每个线程都固定分配一个CPU,

直到该线程执行完成。

缺点：线程阻塞时，造成CPU的闲置。

优点：线程执行时不需切换，相应的开销

可以大大减小，推进速度更快。适用场合：

CPU数量众多的高度并行系统，单个CPU

利用率已不太重要。厂、

I处理机管理

图3・11线程数对加速比的影响

3・5产生死锁的原因和必要条件

&多道程序环境卜，我们可借助多个并发程

序并发执行，来改善系统的资源利用率，提

高系统的吞吐量，但也可能出现问题一死锁。

死锁是指多个进程在运行过程中，因争夺

资源而导致每个进程都无法执行的一种僵局。

此时若不对其干涉，则这些进程都无法向前

推进。

（处理机管理

死锁简单的定义：

密就是两个或两个以上的进程等候着一个永

般、会发生的事件时所取的一种系统状态。

教材上关于死锁的定义：

两个或两个以上并发进程，如果每个进程持有

某种资源，而又等待着别的进程释放它或它们

现在保持着的资源，否则就不能向前推进。此

时，每个进程都占用了一定的资源，但又都不

能向前推进。这种现象称为死锁。尸一-

（处理机管理

•、产生死锁的原因

广生死锁的根本原因是

1、竞争资源引起进程死锁:当系统中供多

个进程所共享的资源，不足以同时满足

他们的需要时，引起他们对资源的竞争

而引起死锁。

2、进程推进顺序不当引起死锁：进程在运

行过程中，请求和释放资源的顺序不当,

导致了进程死锁。晨理机管理

•竞争资源引起进程死锁

4^可剥夺和非剥夺性资源（（consumable

resource）：可以动态生成和消耗，一般

不限制数量。如硬件中断、信号、消息、

缓冲区内的数据。）

2）竞争非剥夺性资源（打印机，磁带机等）

3）竞争临时性资源

•死锁发生：双方都等待对方去生成资那一、

（处理机管理

-永久性资源：像打印机一样可顺序重复

，使用的资源；

.临时性资源，也称为消耗性资源，是指

由一个进程产生，被另一进程使用一短

暂时间后便无用的资源。

-由于进程具有异步性，这就可能使进程

按下述两种顺序向前推进：

-1）进程推进顺序合法；

-2）进程推进顺序非法。厂一、

:处理机管理

11.死锁的例子

）工）设备共享

进程PI、P2,共享一台打印机和一

台磁带机

时亥世工：进程P工——占用打印机

进程P2——占用磁带机

时刻t2：进程P工——又请求磁带机

进程P2——又请求打印机、

限理机管理

I/O设备共享时的死锁情况

进程之间通信时的死锁

•进程推进顺序不当引起死锁

I1）进程推进顺序合法

P2Relg)

②①

P2Rel(R2)

P2ReqtR,)0

PReq(0)

2j.®4

Reqg)P1Req(0)P1Rel(RJP1Rel(R2)

进程推进顺序对死镇的影响

）进程推进顺序非法

若并发进程P]和P2按曲线④所示的顺

序推进，它们将进入不安全区D内。此时P]

保持了资源P2保持了资源R”系统处于

不安全状态。因为，这时两进程再向前推进,

便可能发生死锁。

处理机管理

二产生死锁的必要条件

f互斥条件：任一时刻只允许一个进程使

i用资源

2.请求和保持条件：进程在请求其余资源

时，不主动释放已经占用的资源

3,非剥夺条件：进程已经占用的资源，不

会被强制剥夺

4,环路等待条件：环路中的每一条边是进

程在请求另一进程已经占有的资物一^

①理机管理

;处理死锁的基本方法

⑴预防死锁。

(2)避免死锁。

(3)检测死锁。

(4)解除死锁。

处理机管理

3・6预防死锁的方法

一预防死锁和避免死锁这两种方法，实质

上都是通过施加某些限制条件的方法，来防

止死锁的发生。

两者的主要区别是：为预防死锁所施加

的限制条件严格;为避免死锁所施加的限制条

件则较宽松，它给进程的运行提供了较宽松

的环境，有利于进程的并发执行。

限理机管理

一、预防死锁

页防死锁：通过设置某些限制条件，去破坏

■锁的四个必要条件中的一个或几个条件,

f来防止发生死锁。这是一种较易实现的方法,

被广泛应用。但由于所施加的限制条件往往

太严格，可能导致资源利用率和系统吞吐量

的降低。预防死锁的方法是使四个必要条件

中的第2、3、4个条件之一不能成立，来］

止发生死锁。11.摒弃“请求和保持”条I

2.摒弃“不剥夺”条彳

3.摒弃“环路等待”5

破坏“请求与保持条件”

-这种方法的基本思想是：每个进程在运行之

前，必须预先提出自己所要使用的全部资源,

调度程序在该进程所需要的资源未得到满足

之前，不让它们投入运行，并且当资源一旦

分配给某个进程之后，那么在该进程的整个

运行期间相应资源一直被它占有，这就破坏

了产生死锁的请求与保持条件。/一、

破坏环路条件

上座种方法的基本思想是：对系统提供的每一

卦资源，由系统设计者将它们按类型进行线

性排队，并赋予不同的序号。例如，设卡片

输入机为1,打印机为2,磁带机为3,磁盘

机为4,……o

1.对进程所必须使用的而且属于同一类的所

有资源，必须一次申请完；

2.在申请不同类资源时，必须按各类设备的

编号递增（或递减）的次序依次申请。

处理机管理

亦即，只有低编号的资源要求满足后，

才能对高编号资源提出要求；释放资源

时，应按编号递减的次序进行。由此可

以看出，对资源请求采取了这种限制之

后，所形成的进程一资源图不可能再产

生环路。

处理机管理

啜：进程PA,使用资源的顺序是RI,R2；

进程PB,使用资源的顺序是R2,R1；

若采用动态分配有可能形成环路条件，造成死

锁。

采用有序资源分配法：R1的编号为1,R2的编

号为2；

PA：申请次序应是：RLR2

PB：申请次序应是：R1,R2

这样就破坏了环路条件,避免了死锁的

发生。履理机管理

,3.资源受控动态分配

-为了避免死锁发生，操作系统必须根据

预先掌握的关于资源用法的信息控制资

源分配，使得共同进展路径的下一步不

致于进入危险区，即只要有产生死锁的

可能性，就避免把一种资源分配给一个

进程。

处理机管理

预防是采用某种策略，限制并发进程对资源的

请快，使系统在任何时刻都不满足死锁的必要

*____________

•预防死锁的两种策略：

-预先静态分配法：（针对死锁的第2个条件）

预先分配所需全部资源，保证不等待资源；

•降低了对资源的利用率，降低进程的并

发程度；

•有可能无法预先知道所需资源；

限理机管理

-有序资源使用法：（针对死锁的第4个

条件）把资源分类按顺序排列，保证

不形成环路；

•限制进程对资源的请求；

•资源的排序占用系统开销；

处理机管理

二、系统安全状态

1.安全状态_

避免死锁：并不需事先采取各种限制

措施去破坏产生死锁的必要条件，而

是在资源的动态分配过程中，用某种

方法防止系统进入不安全状态，从而

避免发生死锁。

处理机管理

所谓安全状态，是指系统能按某种进程

顺序(Pl,P,…，Pn)(称〈Pl,P"…，Pn>序

列为安全序列)，来为每个进程p分配其所需

资源，直至满足每个进程对资源的最大需求，

使每个进程都可顺利地完成。

如果系统无法找到这样一个安全序列，

则称系统处于不安全状态。【处理机管理

I2.安全状态之例

*假定系统中有三个进程Pl、P2和P3,共有

12台磁带机。假设在1时刻，如下表所示：

进程最大需求已分配可用

Pi1053

42

p2

P392

处理机管理

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

如果不按照安全序列分配资源，则系

统可能会由安全状态进入不安全状态。

■1.银行家算法(Dijkstra,1965)

问题

■一个银行家把他的固定资金（capital）

贷给若干顾客。只要不出现一个顾客借

走所有资金后还不够的情况，银行家的

资金应是安全的。银行家需一个算法保

证借出去的资金在有限时间内可收回。

限理机管理

我们可以把操作系统看作是银行家，

操作系统管理的资源相当于银行家管理的

资金，进程向操作系统请求分配资源相当

于用户向银行家贷款。操作系统按照银行

家制定的规则为进程分配资源，当进程首

次申请资源时，要测试该进程对资源的最

大需求量，如果系统现存的资源可以满足

它的最大需求量则按当前的申请量分配资

源，否则就推迟分配。：处理机管理

进程在执行中继续申请资源时，先测试

该进程已占用的资源数与本次申请的资

源数之和是否超过了该进程对资源的最

大需求量。若超过则拒绝分配资源，若

没有超过则再测试系统现存的资源能否

满足该进程尚需的最大资源量，若能满

足则按当前的申请量分配资源，否则也

要推迟分配。厂一、

（处理机管理

2.银行家算法

点段定贷款分成若干次进行；并且客户在第一

融借款时,能说明他的最大借款额。

•具体算法：

一客户的借款操作依次顺序进行，直到全部

操作完成；

-银行家对当前客户的借款操作进行判断，

以确定其安全性（能否支持客户借款，直

到全部归还）；

-安全时，贷款；否则，暂不贷款。^^）1^^

3.银行家算法的特点

•允许互斥、部分分配和不可抢占，可提高

资源利用率；

•要求事先说明最大资源要求，在现实中很

困难；

处理机管理

4.解决死锁问题的综合方法

g资源归类：将各种资源归入若干个不同的资

源类（resourcegroup）中，如：外存交换区

空间，进程资源（可分配的设备，如磁带机,

文件），主存空间，内部资源（如I/O通道）

•资源排序：在不同资源类之间规定次序，对

不同资源类中的资源采用线性按序申请的方

法

限理机管理

•针对性优化：可对同一资源类中的资

源进行针对性处理，采用不同的适当

方法。例如，使用避免方法处理外设

资源分配，而对存储资源则采用预防

方法。

处理机管理

三、利用银行家算法避免死锁

1.1.银行家算法中的数据结构

(1)可利用资源向量Available

是个含有用个元素的数组，其中的每一个元

素代表一类可利用的资源数目。如果Available

：j]=K,则表示系统中现有Rj类资源或个。

处理机管理

(2)最大需求矩阵Max

这是一个〃义阳的矩阵，它定义了系统中

〃个进程中的每一个进程对冽类资源的最大

需求。如果Max[i,j]=K,则表示进程i需

要R1类资源的最大数目为K。

处理机管理

(3)分配矩阵Allocation

这也是一个〃义切的矩阵，它定义了系统

中每一类资源当前已分配给每一进程的资源数。

如果Allocation[ij]=K,则表示进程i当前

已分得勺类资源的数目为《

处理机管理

(4)需求矩阵Need。

这也是一个〃X/M的矩阵，用以表示每一

个进程尚需的各类资源数。如果Need[i,j]

=K,则表示进程i还需要Rj类资源K个，方能

完成其任务。

Need[ij]=Max[ij]-Allocation[ij_

处理机管理

2、银行家算法

设Requestj是进程匕的请求向量，如果

Request[j]=K,表示进程居需要A个%类型的

资源。当匕发出资源请求后，系统按下述步骤进

行检查：

(1)如果Request[j]《Need[i,j],便转向

步骤2；否则认为出错，因为它所需要的资源数

已超过它所宣布的最大值。

(2)如果Request[j]^Available[j],便

转向步骤(3)；否则，表示尚无足够资源，匕须

等待。

（3）系统试探着把资源分配给进程并修

改下面数据结构中的数值：

Available[j]:=Available[j]

-Requestj[j]；

Allocation[ijl:=AllocationLbjl

+Requesti[j]；

Need[ij]:=Need[ij]-Requestj[jl；

(4)系统执行安全性算法，检查此次资

源分配后，系统是否处于安全状态。若安全,

才正式将资源分配给进程匕，以完成本次分

配；否则，将本次的试探分配作废，恢复

原来的资源分配状态，让进程匕等待。

3.安全性算法

JJ1）设置两个向量：

©工作向量Work:它表示系统可提供给

进程继续运行所需的各类资源数目，它含有m

个元素，在执行安全算法开始时，

Work:=Available;

②工作向量Finish:它表示系统是否有足

够的资源分配给进程，使之运行完成。开始时

先做Finish[i]:=false;当有足够资蹲分配绐＜

进程时，再令Finish[i]:=trueo/理机管理

(2)从进程集合中找到一个能满足下述条

件的进程：

DFinish[i]=false;

②Need[ij]<Work[j]；若找到,

执行步骤(3),否则，执行步骤(4)。

(3)当进程Pi获得资源后,可顺利执

行，直至完成，并释放出分配给它的资

源，故应执行：

・Work[j]：=Work[j]

+Allocation[ij];

■Finish[i]：=true;

■gotostep2;

处理机管理

(4)如果所有进程的Finish[i]=true都满

足，则表示系统处于安全状态；否则，系

统处于不安全状态。

处理机管理

3、银行家算法的优缺点

T优点：使用银行家算法来分配资源是不会

%产生死锁的。因为该算法保证了每次分配

・都不会使系统进入不安全状态。

■缺点

-(1)要求系统中每类资源的数量不变，

用户的数目也保持不变，但一些系统中做

不到。

■(2)本算法还要求每个进程必须事先

说明它们的最大资源需求量。

■(3)算法的实现本身也要增加厂些系、

统开销。芈理机官理

4、银行家算法一举例

各种资源的数量分别为10、5、7,在丁。时刻

的资源分配情况如图所示。

源楮MaxAllocationNeedAvailable

进程ABCABCABC：ABC

P。753010743332

(230)

■?14322：200122

(302)(020)

302600

p2902

Pa转222211011

H433002431，

To时刻的资源分配表

(1)r时刻的安全性:

、\资源椿

Work,NeedAllocationWork+AllocationFinish

ABCABCABC*ABC

P.332122200532true

Oil211J743true

1p3532

Rj743431002745true

745600302:1047true

P2.

true

P01041743010,41057

(2)以请求资源：以发出请求向量

RequestjCl,0,2),系统按银行家算法进行

检查：

①Requesti(l,0,2)WNeedi(l,2,2)

2)Request]。，0,2)WAvailable](3,3,2)

③系统先假定可为Pi分配资源，并修改

Available,Allocation］和Need1向量，由此形成的

资源变化情况如图3-15中的圆括号所示。

④再利用安全性算法检查此时系统是否

安全。

Work]Need,AllocationWorkfAllocationFinish

ABCABCABC:ABC

P1230020302532true

耳■532011211743true

匕743431002745true

Po745743010755true

P27556003021057true

处理机管理

Pl申请资源时的安全性检查

(3)请求资源：发出请求向量Request's,

3,0),系统按银行家算法进行检查:

①Request4(3,3,0)<Need4(4,3,1);

②Request#,3,0)<Available。，3,0),让

P4等待。

处理机管理

(4)P0请求资源:P0发出请求向量Requsto(O,2

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

①Requesto(O,2,0)<Need0(7,4,3);

②Request。®2,0)<Available(2,3,0);

③系统暂时先假定可为Po分配资源，并修

改有关数据，如下图所示。

(5)进行安全性检查：可用资源AvailableQ,

1,0)不能满足任何进程的要求，所以系统进入不

安全状态，此时系统不分配资源。

艰情AllocationNeedAvailable

进程7^

ABC?ABC.ABC