计算机操作系统 第三章

第三章处理机调度与死锁

hedulingand

处理机是最重要的计算机资源，提高处理

机的利用率及改善系统性能，在很大程度上也

决于处理机调度性能的好坏，因而，处理机调

度成为操作系统设计的中心问题之一。

本章主要内容

/处理机调度的基本概念

/调度算法

/实时系统中的调度

/多处理机系统

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

曹死锁的预防和避免

■死锁的检测和解除

2

作业的概念

■作业（job）：由用户提交给系统处理的一个计算

任务，称为作业。它包括用户程序、数据，以及

对程序运行进行控制和处理的有关信息。一般，

可把作业分成批处理型作业和终端型作业两类。

■作业从进入系统到运行结束，一般要经历进入、

收容、运行、完成四个阶段。相应地，我们说此

作业处于进入、后备、执行、完成四个不同的状

0

3

作业的状态

■进入状态即提交状态，作业从输入设备进入输入

井°

■后备状态操作员把作业输入到直接存取的后援存

取器后，为进入系统的作业建立作业控制块，并

把它加入到后备作业队列中，等候作业调度程序

调度。这一过程也称为作业注册。

■运行状态作业被作业调度程序选中，且分配了必

要的资源，建立一组相应的进程后，该作业就进

入了运行状态。它分为三种状态：即就绪状态、

执行状态、阻塞状态。

■完成状态当作业正常运行结束或因发生错误而终

J止时，作业进入完成阶段。

g

i5

§3.1处理机调度的基本概念

Thebasicconceptsofprocessorscheduling

一、处理机调度的层次

6

一个作业从提交开始，往往要经历三级调度：高级调度、

低级调度、中级调度。

1IWJ级调度(HighLevelScheduling)：作业调度/长程调度/接纳调度。

□按一定调度算法，外存后备队列中选择作业调入内存，

创建PCB等，插入就绪队列。

O一般用于批处理系统，分/实时系统一般直接入内存，无

此环节。

・调度特性：

*接纳作业数：取决于多道程序度。

作业多一影响服务质量(周转时间长)；

作业少—资源利用率和系统吞吐量低。

接纳策略：即采用何种调度算法。

7

2低级调度(LowLevelScheduling)：进程调度/短程调度

■在多道程环境下，进程数目往往多于处理机数目,

致使它们争用处理机。这就要求系统能按某种算

法，动态地把处理机分配给就绪队列中的一个进

程，使之执行。分配处理机的任务是由进程调度

程序完成的。它是操作系统设计的中心问题之一。

■低级调度就是按某种原则，决定就绪队列中的某

个进程获得处理机，由分派程序(Dispatcher)

实施处理机分派。

8

进程调度要解决的问题

WHAT：按什么原则分配CPU

—进程调度算法

WHEN：何时分配CPU

—进程调度的时机

HOW：如何分配CPU

—CPU调度过程（进程的上下文切换）

9

■进程调度可有两种方式：非抢占方式、抢占方式。

1)非抢占方式(Non-PreemptiveMode)

优点：实现简单，系统开销小。

缺点：不能满足紧急任务的要求。

2)抢占方式(PreemptiveMode)

抢占原则：

(1)时间片原则(time-sliceprinciple)；

(2)优先权原贝ij[priorityprinciple)；

(3)短进程优先原贝1"shortestjobfirstprinciple)；

■3中级调度(Intermediate-LevelScheduling)：中程调度

□对象：

■外存中因暂时不能运行而被挂起的进程

□动作：

■将外存挂起的进程激活，调入内存，进入就绪队列

口目的：

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

♦:♦三种调度运行频率：低＞中＞高

。进程调度在操作系统中必不可少

11

二、调度队列模型

每一种调度都涉及到进程队列。根据具有的调度类型,

形成三种类型的调度队列模型。

1只有进程调度的调度队列模型（如分时系统）

分时系统中，用户键入的命令和数据，直接送入内存。

由OS为命令建立一个进程，并将它排在就绪队列的末尾，然

后按时间片轮转方式运行。

该模型如图3・1所示。

12

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

时间片完/被中断

交互用户

□□□□□结束

就绪队列

进程调度

唤醒阻塞

阻塞队列

13

2有作业和进程调度的调度队列模型（批处理系统）

时间片完/被中断

结束

口|「1口|口|/CPU

后备队列

作业调度进程调度

唤醒阻塞

阻塞队列2

阻塞队列

114

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

当在OS中引入中级调度后，我们可把进程的就绪状态分

为内存就绪状态（表示进程在内存中就绪）、外存就绪状态。

也可把阻塞状态进一步分成内存阻塞和外存阻塞状态。

在调出操作的作用下，可使内存就绪转变为外存就绪、

内存阻塞转变为外存阻塞；

在中级调度的作用下，可使外存就绪转变为内存就绪。

15

作业调度

时间片完

批量作业后备队列

交互型作业

事

件

出

现

图3-3具有三级调度时的调度队列模型

16

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

Somecriteriaforchoosingschedulingwayandalgorithm

一般和OS的类型和目标有关

1面向用户的准则（User-orientedcriterion）

（注重满足用户需求）

1）周转时间短（shortturnaroundtime）针对批处理系统

周转时间（从作业提交系统到完成为止）包括：

□驻外存等待作业调度的时间；

□驻内存等待进程调度的时间；

□执行时间；

□阻塞时间。

一后三步可能有多次。

17

计算机系统要求的是平均周转时间最短。

平均周转时间(meanturnaroundtime)为：

1〃

7一0覃

平均带权周转时间：作业的周转时间T与系统为它提供

的实际服务时间Ts之比。

1」.T

带权周转时间越小越好。

18

2）响应时间快（quickresponsetime）（针对分时系统）

响应时间指从用户通过键盘提交一个请求开始，直至系统

首次产生响应（屏幕显示结果）为止的时间。包括：

。输入传送到CPU的时间；

。处理的时间；

。结果回送到显示器的时间。

3）截止时间的保证（guaranteeddeadline）（针对实时系统）

调度算法应保证实时任务必须开始执行的最迟时间和必须

完成的最迟时间。

4）优先权原则（priorityprinciple）（适用于各种OS）

进程调度中，往往还须选择抢占调度方式，才能保证紧急

业得到及时处理。

19

2面向系统的准则(System-orientedcriterion)

1)系统吞吐量高(highsystemthroughput)(对批处理OS)

-与批处理作业的平均长度有密切关系。

2)处理机利用率好(goodprocessorutilization)(主要对大、

中型机多用户系统一由于CPU价格昂贵)

3)各类资源平衡利用(balanceduseofvariousresource)

调度算法最优准四

最大的CPU利用率最短的等待时间

♦最大的吞吐量最短的响应时间

♦最短的周转时间最公平

20

§3.2调度算法SchedulingAlgorithm）

调度实质是一种资源分配。（如作业调度可看成是内存的

分配、进程调度看成是CPU的分配）

调度算法：由系统资源分配策略所规定的资源分配算法。

一、先来先服务和短作业（进程）优先调度算法（First-Come-

First-ServedandShortestJobFirstschedulingalgorithm）

1、先来先服务（FCFS）调度算法

思想：每次调度总是选择最先进入队列的作业（进程）。

同时适用于作业调度和进程调度。

FCFS应用于进程调度是一种非抢占的调度算法。他一

手点：简单，有利于长作业（进程）即CPU繁忙性作业。

21

开始执带权周

进程名到达时间服务时间完成时间周转时间

行时间转时间

A010111

B.1■1001101'1001

C21：101102.100100'

3)

D:100，102202’1991.99

22

2、短作业（进程）优先调度算法（SJF、SPF）

（ShortestJobFirstschedulingalgorithm）

思想：从队列中选择估计运行时间最短的作业（进程），对它执行

调度。

同时适用于作业调度和进程调度。

该算法有利于短作业（进程），可提高系统的吞吐量、降

低作业平均等待时间。

例：

缺点：1）不利于长作业，“饥饿”；

2）未考虑作业（进程）的紧迫程度；

3）长、短只能是一个估算的时间，不一定确切。

23

“饥饿”状态

■在预计时间内，某个或某些进程永远得不到完成工作的

机会，因为他们所需的资源总是被别的进程占有或抢占。

这种状况称作“饥饿”或者“饿死”

(Starvation)o

■饥饿不同于死锁，但与死锁相近。死锁进程必定处

于阻塞状态，饥饿进程不一定被阻塞，可以在就绪

状态。

■利用先来先服务的资源分配策略可以避免饥饿现象。

24

二、高优先权优先调度算法(Priorityschedulingalgorithm)

1、优先权调度算法的类型

口优先权调度算法是为了照顾紧迫性作业(进程)。

□可用于作业调度和进程调度。

□根据按优先权调度时是否允许抢占，可分为两种：

1)非抢占式(Nonnpreemptive)优先权算法

主要用于批处理或要求不高的实时系统中。

2)抢占式优先权调度算法

■当就绪队列中有新进程出现时，应比较新进程和正运行进

程的优先权。若小于、等于，则继续运行，否则，重新调

度、切换。

125

非抢占式优先权算法一例

EG：进程到达时间服务时间优先权

Pi0.073

2.042

P2

P34.014

P45.041

■Gantt图

07111516

平均周转时间=((7・0)+(15・2)+(16・4)+(11・5))/4=8.5

26

抢占式优先权算法一例

EG：进程到达时间服务时间优先权

Pi0.073

2.042

P2

P34.014

P45.041

■Gantt图

Pi

PPP2P3

2|4,

0259101516

平均周转时间=((15-0)+(10-2)+(16-4)+(9-5))/4=9.75

27

练习

5个进程Pi，P2,P3,P4,P5,见表，规定进程优先数越小，优先级越

高，试描述在采用下述调度算法时各个进程运行过程，并计算采用每

种算法时进程平均周转时间。假设忽略进程的调度时间。

1）先来先服务调度算法；2）短进程优先调度算法；

3）非剥夺式优先级调度算法；4）剥夺式优先级调度算法。

进程创建时刻ms运行时间ms优先数

P]035

263

p2

P3441

P4654

P5822

28

2优先权的类型(Thetypeofpriority)：

有两种类型的优先权一静态优先权和动态优先权。

1)静态优先权(staticpriority)：优先权在创建进程时就确

定好，且在进程的整个运行期间保持不变。

优先权常用某范围内的整数表示，又称优先数。UNIX系

统中，整数值越小，优先级越高。又如：

确定进程优先数的依据：

♦进程类型：通常系统进程的优先权高于用户进程；

♦对资源的需求：需求越少，优先权越高；

♦用户要求：紧迫程度、交费多少等。

优点：简单。

缺点：出现“饥饿”现象。

29

2）动态优先权（dynamicpriority）：优先权在创建进程时规定,

但可以随着进程的运行而改变。

3高响应比优先调度算法（HighestResponseRatioFirst

Schedulingalgorithm）

对每一个作业（进程）计算一个优先数，称为响应比。挑

选响应比高的进行调度。（短作业与优先权调度的组合）

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

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

K---------------------------------

夕一要求服务时间—要求服务时间

例如

30

■如等待时间相同，则要求服务时间愈短，优先权愈高一SPF。

■如要求服务时间相同，优先权决定于等待时间一FCFS。

■长作业，等待一定时间后，则响应比增加，利于调度。

，每次调度，计算响应比，增大了系统开销。

31

三、基于时间片轮转调度算法(只应用于进程调度)Round-

robinschedulingalgorithmbasedontime-slice

1时间片轮转法(time-sliceRound-robinmethod)

1)思想：和分时系统类似。翳所有的就绪进程按先来先服务的

原则排成队列，每次调度队首进程，执行一个时间片后，将

其排入队尾，再重新调度。例如：

2)时间片大小的确定(Determinationoftime-slicesize)

口q过长large—＞退化为FCFS算法，进程在一个时间片内

都执行完，响应时间长。

□q过短small一〉用户的一次请求需要多个时间片才能处

理完，上下文切换次数增加，响应时间长。

根据系统的处理能力，应让用户键入的常用命令在一个时间片内

I完。时间片的大小从几ms到几百ms,通常可让用户的

6〜80%的作业在一个时间片内完成。32

现有5个进程，需要运行的时间分别为(4,3,4,2,4),那么在

时间片q=l和q=4的情况下，诸进程的运行情况如下图所示:

33

2多级反馈队列调度算法(multi-levelfeedbackqueue

schedulingalgorithm)

口基本思想：

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

度算法的综合和发展，动态调整进程优先级和时间片大小

,是目前公认的一种较好的进程调度算法。

设置多个就绪队列；

□各队列优先级不一样；

分配的时间片也不同，高优先权队列进程时间片较小。

34

Thestepsofmulti-levelfeedbackqueueschedulingalgorithm

(1)在选取进程时，短时间片

选取高优先权队列里的

进程。优先级调度按

照FCFS分配给相应的时

间片。时间片轮转

(2)进程使用完时间片后,

进入低一级优先权队列，

动态优先权、不等时间片

队列n按RR算法调度执行。

长时间片

(3)当高优先权队列里没

有进程时，才调度低优先

权队列进程。

进程创建后进入最高优先权队列，抢占低优先权进程

35

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

Theperformanceofmulti-levelfeedbackqueue

多级反馈队列调度算法具有较好的性能，能较好地满足各种类型用户

的需要：

■对于终端型作业用户：一般终端型作业较小，通常可在第一队列中的一

个时间片内完成，有较好的响应时间。

■对短批处理作业用户：批处理作业一开始也是送入第一队列，或一个时

间片完成，或进入第二、第三队列，在某个时间片完成，仍然有较短的响

应时间。

■对长批处理作业用户：依次在各队列中运行，直到最后一个队列。而最

后一个队列常用时间片轮转法，也可以较及时的得到处理。

36

几种常见调度算法的比较

FCFSRRSJFHRRFMFQ

选择依捌Max[w]常量Min[s]Max[(w+s)/s]

非抢占非抢占

调度方式非抢占抢占抢占

抢占抢占

时间片小，

吞吐量不突出高高不突出

可能变低

短进程提供

短进程（作业）

响应时间不突出良好的响应较好不突出

响应时间好

时间

开销最小低可能高可能高可能高

不利于短不利于长作可能偏爱I/O

对进程作用公平对待良好的均衡

作业业（进程）繁忙型作业

“饥饿”问题无无可能无可能

37

四、彩票调度算法(lotteryschedulingalgorithm)

基本思想：为进程发放针对系统各种资源(如CPU

时间)的彩票。当调度程序需作出决策时，随机选择一

张彩票，持有该彩票的进程将获得系统资源。

如CPU调度，系统可每秒种抽50次彩票，每次的中

奖者获得20ms的运行时间。

对于重要的进程，可被给予更多的额外彩票，以增

加其中奖机会。

38

§3.3实时系统中的调度

Real-timeScheduling

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

implementreal-timescheduling)

实时调度必须满足实时任务对截止时间的要求，因此实时

系统必须：

1提供必要的调度信息：

就绪时间(readytime);

开始和完成截止时间(beginandenddeadline);

处理时间(processingtime);

资源要求(resourcerequirement);

——,优先级(priority)。

39

2.系统处理能力(Strongsystemprocessingability)

口采用单处理机系统，但须增强其处理能力，以显著地减

少对每一个任务的处理时间；

□是采用多处理机系统。

3.米川抢占式调度方式(Takepreemptiveschedulingmechanism)

4.具有快速切；(quickswitchingmechanism)

e对外部中断的快速响应能力。

e快速的任务分派能力。

40

二、实时调度算法(real-timeschedulingAlgorithm)

1、非抢占式调度算法

时间片轮转调度算法：响应时间以秒为级别，只适合于

一般实时信息处理系统

口非抢占优先权调度算法：响应时间可做到以秒或百毫秒

为级别。适应于要求不高的实时控制系统。

2、抢占式调度算法

□基于时钟中断抢占的优先权调度算法：响应时间可做到

几十毫秒至几毫秒。适合大多数实时系统。

□立即抢占的优先权调度：一旦外部中断出现，只要当前

任务未处于临界区，即能被剥夺处理机，响应时间可做到

「几毫秒至100微秒。

41

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

1111

1111

,H____________VV_______________

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

卜•调度时间―

<---------------调度时间-----------------A

（c）基于时钟中断抢占的优先权抢占调度

（。）非抢占轮转调度

实时进程请求调度当前进程运行完成实时等程请求调度1实时进程枪占当前

11

11'进程，并立即执行

,V[_________

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

<-----调度时间一A--调度时间+

@）非抢占优先权调度M）立即抢占的优先权调度

图3-5实时进程调度

42

二、常用的几种实时调度算法(Severalcommonreal­

timeschedulingAlgorithm)

常用的几种实时调度算法，均基于任务的优先权，根据确

定优先级方法的不同形成了不同的实时调度算法。

1.最早截止时间优先EDF(EarliestDeadlineFirst)算法(根

据任务的开始截止时间确定优先级)

该算法即可用于抢占式调度，也可用于非抢占式调度。

1342

开始截止时间

任务执行11I3|42

-iI41一

任务到达

1234

图3-6EDF算法用于非抢占调度方式

43

2.最低松弛度优先LLF(LeastLaxityFirst)算法

该算法根据任务紧急(或松弛)的程度，确定任务优

先级。任务的紧急程度愈高，为该任务所赋予的优先级

就愈高，以使之优先执行。主要用于可抢占调度方式。

与任务的完成截止时间密切相关。

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

系统中有一个按松弛度排序的实时任务就绪队列，

松弛度最低的任务排在最前面，调度程序总是选择就绪

队列中的队首任务执行。

A]A2A3A4A5A6A7A8

020406080100120140160

0任务A每20ms执行

B2一次，执行时间为

图3・7A和B任务每次必须完成I10ms；住务B每

A2的胪，A4松弛度减至0(50ms执行一次，执2

50ms完"40ms-10msJ20(100-10-70),A4抢【行时间为25ms。

A

68

01020304050-607080

£1=0

B/20)B"5)B2(l5)B2(l0)

图3-8利用LLF算法进行调度的情况

45

§3.4多处理机中的调度

SchedulinginMulti-ProcessorSystem

/提高计算机系统性能的主要途径有两条：

♦提高构成计算机的元器件的运行速度;

♦改进计算机系统的体系结构；

/20世纪70年代开始出现的多处理器系统，可

以实现对信息的高度并行处理，提高系统吞吐

量和可靠性。

46

-、多处理器系统的类型(ThetypeofMPS)

1.根据多处理器之间的耦合程度划分

(1)紧密耦合(TightlyCoupted)MPS

通过高速总线或高速交叉开关互连多个处理器之间。它

们共享主存储器系统和I/O设备，将主存划分成若干能独立访

间的存储器模块，便于多个处理器同时对主存访问，系统中

所有资源由操作系统实施统一控制和管理。

(2)松散耦合(LooselyCoupled)MPS

通过通道或通信线路，来实现多台计算机之间的互连。

每台计算机都有自己的存储器和I/O设备，配置OS管理本地

资源和在本地运行的进程。通过通信线路与其它计算机交换

信息，以及协调它们之间的工作。

47

2,根据所用处理器的相同与否划分

(1)对称多处理器系统SMPS(Symmetric

MultiProcessorSystem)。在系统中所包含的各处

理器单元，在功能和结构上都是相同的，当前的

绝大多数MPS都属于SMP系统。

(2)非对称多处理器系统。处理单元的功能和

结构各不相同，其中只有一个主处理器，有多个

从处理器。

48

二、进程分配方式（ProcessAssignmentWay）

1.对称多处理器系统中的进程分配方式

SMP系统中，把所有处理器作为一个处理池，由调度程

序，将任一个进程分配给池中任一处理器。

1）静态分配：进程从开始到完成，被固定地分配到一台处理

机上。每一台处理机有自己的专用就绪队列。

优点：进程调度简单、开销小。

缺点：整个系统中各处理机忙、闲不均。

2）动态分配：系统中仅设置一个公共就绪队列，由所有处理

机共享。某一进程可分配到任一台处理机上运行。某进程在其

生命周期中可能会在多台处理机上运行。

优点：各处理机使用平均。

缺点：调度的开销较大（如对就绪队列的使用、进程切换

学的开销等）。

49

2.非对称多处理器系统中的进程分配方式

非对称MPS,OS大多是采用E—M(Master/Slave)

式OS,即OS的核心部分驻留在主机(master)上，从机

(slave)只是执行用户程序，进程调度只由主机执行。每

当从机空闲时，请求主机为它分配进程，主机便从一

公用的就绪队列中(队首)取下一个进程分配。

优点：系统处理比较简单。

缺点：主机是系统瓶颈。

克服缺点的方法：用多台而非一台处理机来管理各

个系统。

50

二、进程（线程）调度方式（Process（thread）SchedulingWay）

1）自调度（Self6chedulingWay）：各个CPU采用一个公

共就绪队列，每个处理机都可以从队列中选择适当进程

（采用FCFS、SPF等算法）来执行。

□需要对就绪队列进行互斥访问控制。

是最常用的算法，实现时易于移植采用单处理机的调

度技术。

□优点：

1）只要有工作，就不会有空闲处理机；

2）就绪队列的组织，调度算法可延用单处理机系统中的

方法。

51

。缺点：

•瓶颈问题（公共的就绪队列形成瓶颈）；

・低效性（线程在运行中可能会更换多个处理机,

有些内容如高速缓存中的信息丢失，需多次设

置）；

•线程切换频繁（相互合作的进程的同步关系难

以保证）

52

2）成组调度（GangScheduling）:将一^个进程中的一^组

线程，分配到一组处理机上去执行。

■优点：1）合作的线（进）程能并行执行，则可减

小阻塞，从而减少切换。

2）每次调度解决一组线（进）程的处理机分配，

可减少总的调度次数。

■成组调度可有两种方式：

1）面向所有应用程序平均分配处理机

2）面向所有线程平均分配处理机

第二种方式更合理、有效

53

3)专用处理机分酉己(DedicatedProcessorAssignment):

在一个应用程序执行期间，专门为该应用程序

分配一组处理机，每一个线程一个。这组处理机供

该应用程序专用，直到应用程序完成。

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

Thereasonsandnecessaryconditionsforcreatingdeadlock

55

、死锁(deadlock)

指多个进程在运行过程中因争夺资源而造成的一种僵

局(deadly-Embrace),若无外力作用，这些进程都将无法

向前推进。

申请打印机申请扫描仪

申请扫枪必、请打印机

使用陛

释放打印机’

释放扫描仪释放扫描仪

56

关于死锁的一些结论

■参与死锁的进程最少是两个

（两个以上进程才会出现死锁）

■参与死锁的进程至少有两个已经占有资源

参与死锁的所有进程都在等待资源

■参与死锁的进程是当前系统中所有进程的子集

如果死锁发生，会浪费大量系统资源，甚至导

致系统崩溃

57

.、产生死锁的原因(Thereasonsfordeadlockgenerating)

■竞争资源(Resourcecompetition)

■进程推进顺序非法(Illegalprocessproceeding)

1、竞争资源中起死锁(Resourcecompetitioncausesprocessdeadlock)

(不可避免)

■资源分类

操作系统管理着系统内所有资源，它负责分配不同类

型的资源给进程使用，系统中的资源可从不同角度进行分

类。

58

■资源的分类

□是否可剥夺

■可剥夺资源(PreemptableResources)

可以从拥有它的进程中剥夺而不会产生任何副作用的资源。

例：存储器

■不可剥夺资源(NonpreemptableResources)

无法在不引起相关计算失败的情况下把它从主进程处剥夺的

资源。例：打印机

口是否临时性

-永久性资源：可顺序重复使用权的资源(如打印机)

■临时性资源：由某个进程产生，被另一个进程使用一短暂时

间后便成为无用的资源。

59

•竞争非剥夺性资源：可能导致死锁。如Pl、P2都需要R1、

R2,在某一时刻资源申请、分配情况如图：

图1I/O设备共享时死锁图2进程间通信时死锁

•竞争临时性资源

■竞争临时性资源也可引起死锁。图2示出进程通信形成死锁

情况。

60

■2、进程推进顺序不当引进死锁（进程并发的异步性）

Illegalprocessproceedingcausesprocessdeadlock

无法控制进程之间的推进顺序（固有的），因

此死锁是基本特征的“副作用”；可能是进程按下

述两种顺序向前推进。

□进程推进顺序合法

□推进顺序非法

61

状态:就绪执行阻塞

62

P2Rel(R2)

P2Rel(Rl)

P2Req(Rl)

P2Req(R2)

P1Req(R1)PlReq(R2)PlRel(R1)PlRel(R2)

1、2、3三条曲线的顺序合法，4的顺序非法

图3-10进程推进顺序对死锁的影响

63

二、产生死锁的必要条件(TheNecessaryConditionof

DeadlockGenerating)Coffman条件：

在同时具备下列四个必要条件时，就会产生死锁：

1.互斥条件(MutualExclusioncondition)

指进程对所分配到的资源进行排它性使用。

2.请求和保持条件(Requestandholdcondition)

进程已经保持了至少一个资源，但又提出了新的资源

要求。当不能满足而阻塞时，保持原资源不释放。

3.不剥夺条件(Nonpreemptivecondition)

进程已获得的资源，在未使用完之前，不能被剥夺，

只能在使用完时自己释放。

4.环路等待条件(Loopwaitingcondition)

在发生死锁时，必然存在一个进程一资源的环形链。

环路中的进程形成等待链。

64

二、处理死锁的基本方法(BasicMethodsofDeadlock

Processing)

■1预防死锁(DeadlockPrevention)：设置某些条件，破坏产生

死锁的一个或几个必要条件。

□优点：实现简单；

□缺点：条件严格，降低系统资源利用率和吞吐量。

■2避免死锁(DeadlockAvoidance)：不事先采取各种限制措施

去破坏产生死锁的条件，在资源的动态分配过程中，防止系

统进入不安全状态，以避免发生死锁。

□优点：条件较弱，较高资源利用率和吞吐量。

□缺点：实现难.

65

■3检测死锁(DeadlockDetectionandRelieving)：不采取限制

措施，不检查系统是否已进入不安全区，允许发生死锁，但

可通过系统设置的检测机构及时检测出，并精确的确定与死

锁相关的进程和资源，结合相关机制，将死锁清除。

■4.解除死锁(DeadlockRelieving)：与检测配套的一种措施，

用于将进程从死锁状态下解脱出来，撤销或挂起一些进程，

以便回收一些资源。

66

§3.6死锁的预防和避免

DeadlockPreventionandAvoidance

一\死锁的预防(DeadlockPrevention)

因为第一个必要条件“互斥条件”是设备的固有属性决定

的，所以只能设法破坏另三个必要条件。

1摒弃“请求和保持”条件：

资源静态分配：进程运行前一次性满足它的全部资源请求，否

则，全部不分配。在运行过程中，进程不再请求资源。因此不

再占有某些资源去等待另外资源。

缺点：1)进程在整个生命周期一直占用资源，减低利用率;

2)进程延迟运行；

67

2摒弃“不剥夺”条件

思想：某进程申请新资源不能满足时，释放已占用的所有资源，

以后需要时再申请。意味着：进程已经占有的资源，在运行过程

中可能会暂时的释放，也可认为是被剥夺了。

缺点：造成前段工作的失效。反复地申请、释放资源使进程的执

行推迟；前后两次运行信息不连续。

3摒弃“环路等待”条件(预防死锁较有效的方法)

有序资源分配方法：所有资源按类型进行线性排队，并赋予不同

的序号。进程对资源的请求必须按资源序号递增的次序提出。

如:m种资源，R1<R2<……<Rm,若Pi保持了Ri,则它只能

申请比Ri级别更高的Rj(RivRj),释放时，Rj先于Ri释放。

68

缺点：

>1）资源序号应相对稳定，限制了新设备类型的增加；

>2）进程使用资源的顺序与系统规定的顺序不一致；例如：

打印机v磁带机（系统规定）。P的过程先申请磁带机，再申请

打印机。而申请过程中P先申请到打印机，再等待磁带机，导

致打印机长期闲置。

A3）对用户增加了限制。

总之，这一做法的困难在于如何给资源类确定各方面都较

满意的序号。

69

哲学家就餐问题的死锁及处理办法

假如五个同时饥饿而各自拿起左边的筷子时，当他们

试图去拿右边筷子时，都将因无筷子可拿而无限期地等待。

对于这样的死锁问题可采取以下几种解决方法：

(1)至多只允许四个哲学家同时进餐。

(2)仅当哲学家的左、右两支筷子均可用时，才允许

他拿起筷子进餐。

(3)规定奇数号哲学家先拿起他左边的筷子，再拿起

他右边的筷子；而偶数号哲学家则相反。

请问：上述三种办法是怎样防止死锁的?

70

二、死锁的避免(DeadlockAvoidance)

避免死锁中，可把系统状态分为安全、不安全。只要

使系统处于安全状态，则可避免死锁。

安全状态(SafetyState)：系统能按某种顺序(如

<P1,P2,…，Pn>)为每个进程分配其所需资源，使每个进

程都可顺序完成，则称此时系统处于安全状态。

进程序列PLP2,…，Pn称为安全序列。

若不存在安全序列，则称系统处于不安全状态。

不安全状态有可能导致死锁，安全状态则可避免死锁。

因此，使系统不进入不安全状态则可避免死锁。

171

安全状态与不安全状态

安全状态不安全状态

死锁状态

72

银行家算法

了解死锁的实质

73

二、死锁的避免

银行家算法：

■算法描述

口银行家拥有一笔周转资金

□客户要求分期贷款，如果客户能够得到

各期贷款，就一定能够归还贷款，否则

就一定不能归还贷款

银行家应谨慎的贷款，防止出现坏帐

74

二、死锁的避免

银行家算法：

■用银行家算法避免死锁

□操作系统（银行家）

□操作系统管理的资源（周转资金）

口进程（要求贷款的客户）

75

二、死锁的避免

银行家算法：单种资源的银行家算法

4个客户每个都有一个贷款额度

已使用最大已使用最大已使用最大

名字J|名字||名字||

6

Andy06Andy16Andy1

Barbara05Barbara15Barbara25

Marvin04Marvin24Marvin24

Suzanne07Suzanne47Suzanne47

可用：10可用：2可用：1

(a)(b)⑹

76

二、死锁的避免

银行家算法：单种资源的银行家算法

■对每个请求进行检查，是否会导致不安全状态。

若是，则不满足该请求；否则便满足

■检查状态是否安全的方法是看他是否有足够的

资源满足一个距最大需求最近的客户，如此反

复下去。如果所有投资最终都被收回，则该状

态是安全的，最初的请求可以批准

77

、死锁的避免

银行家算法：单种资源的银行家算法

已使用最大已使用最大已使用最大

名字I(名字11名字

Andy06Andy16Andy16

一个状态被称为Barbara05Barbara15Barbara25

Marvin04Marvin2kMarvin24

是安全状态Suzanne07Suzanne47Suzanne47

可用：10可用：2可用：1

(a)(b)(c)

/条件是存在一个状态序列能够使所有的客户

均得到其所有的贷款。

/图示b状态是安全的，以使Marvin运行结束,

释放所有的4个单位资金。这样下去便可满足

Suzanna或Barbara的请求。

78

、死锁的避免

银行家算法：单种资源的银行家算法

已使用最大已使用最大已使用最大

名字I(名字11名字

Andy06