第四课 调度和 死锁
(Scheduling and Deadlock )
教学目的：
在多道程序系统中，一个作业从提交到执行完成，
要经历多级调度，调度的好坏要影响系统的运行性
能，因此调度是多道系统的关键。为了改善系统 资
源 的利用率和提高系统处理能力，多道程序系统中
采用多个进程的并发执行，但它也可能发生死锁的
危险，研究死锁的原因和产生条件，采用预防死锁、
避免死锁、检测死锁和解除死锁等多种方法防止死
锁是多道程序系统重要的研究课题。
教学要求：
?熟悉 处理机三级调度 概念和 处理机调度模型,掌
握作业的状态和作业 调度的功能。
掌握进程调度的方式和功能,熟悉 调度方式和
算法的选择准则,掌握七种 调度算法及适合范围。
?掌握 死锁的定义和产生死锁的原因,掌握 死锁的
四个必要条件； 熟悉 预防死锁的方法，熟练掌握
银行家算法及其在死锁避免中的应用；掌握资源
分配图的简化及其死锁定理,熟悉 解除死锁的方
法。
（一） 调度 (Scheduling)
（ 1）处理机三级调度
1。高级 (Long-term)调度 ―― 作业调度
作业调度用于决定把外存输入井上处于作业后备队列上的哪
些作业调入内存，并为它们创建进程、分配必要的资源，然
后再将新创建的进程排在就绪队列上，准备执行。在批处理
系统中，作业是先驻留在外存的输入井上的，因此需要有作
业调度。然而在分时系统中，通过键盘输入的命令和数据直
接进入内存，无需作业调度。
2。低级 (Short-term)调度 ―― 进程调度
进程调度决定就绪队列中哪个进程将获得处理机，然后由分
派程序执行把处理机分配给该进程的操作。进程调度是最基
本的调度，任何操作系统都有进程调度。
处理机三级调度 -1
3。中级 (Medium-term)调度 —— 对换
引入中级调度的目的是为了提高主存利用率和系统
吞吐量。由于在进程并发执行过程中，为了充分发
挥内存的效能，需将那些暂时不能运行的进程从内
存调到外存盘交换区去等待，而将那些在盘交换区
的等待事件已经发生急需调度运行的进程从盘交换
区调入内存。在 UNIX系统中中级调度就是存储管理
中的对换，采用虚拟存储技术的分时系统往往设立
中级调度。
图：处理机三级调度
外存 (盘 )交换区
作业
后备
状态
作业
提交
状态 作业 完成状态
终止 作业
就绪
态
阻塞
态
中级调度
主存
进程调度 运行态
就绪
态
阻塞
态
作业调度 作业运行状态
外存
Scheduling in Batch Systems
Three level scheduling
（ 2）作业调度
1。作业的状态
作业从进入到运行结束，一般需要经历, 提交,,, 后备,,
,运行, 和, 完成, 四个阶段。
?提交状态
一个作业被提交给机房后正在通过 SPOOLing系统进行输入
或用户通过终端向计算机中键入其作业时所处于的状态为提
交状态。
?后备状态
作业已经过 SPOOLing系统输入到磁盘输入井，等待调入内
存运行，此时作业处于后备状态。为了管理和调度作业，为
每个作业设置一个作业控制块（ JCB）。 作业控制块记录了作
业类型和资源要求等有关信息。作业控制块按作业类型组成
一个或多个后备作业队列。
作业调度 -1
?运行状态
一个在后备作业队列的作业被作业调度程序选中
后，分配必要的资源，建立一组相应的进程后，调
入内存，该作业就进入运行状态。进程各状态（进
程运行态、内存进程就绪态、内存阻塞态、外存进
程就绪态、外存进程阻塞态等）都对应作业运行状
态。
?完成状态
当进程正常运行结束或因发生错误而终止时，作
业进入完成状态。终止作业程序将负责善后处理。
作业调度 -2
2。作业状态的转换
?作业调度
作业调度程序按一定算法从后备作业队列中选
一个满足资源要求的作业，分配它所要求的资源，
建立一组相应的进程，设置该进程状态为就绪态，
并将该进程插入内存就绪队列，参加 CPU争夺。
?终止作业
当进程正常运行结束或因发生错误终止时，调
用终止作业程序，它负责将输出文件缓冲输出到
输出井，并调用 SPOOLing系统输出进程将作业输
出文件在打印机输出。同时回收作业所使用内、
外存,I/O设备等各种资源，最后调用记帐程序
结清作业费用。
（ 3） 处理机调度模型
1。仅有进程调度的调度队列模型
在分时系统中通常仅设置了进程调度。此时系统有一个就
绪队列，每个进程运行一个时间片，进程运行一个时间片后
如未完成，则被放在就绪队列末尾。如进程运行中因等待某
事件（例如申请 I/O而等待 I/O完成），则需排入阻塞队列，
系统因阻塞的原因不同可设几个阻塞队列。
2。有进程调度和中级调度队列模型
在具有虚拟存储器技术的分时系统中（例如 UNIX系统等），
一般采用具有进程调度和中级调度的调度模型。在该模型中
比第一种模型增加了中级调度，则相对于上模型也增加了外
存进程就绪队列和外存进程阻塞队列。中级调度时或从内存
就绪队列调到外存的就绪队列，或从内存阻塞队列调到外存
阻塞队列，或从外存进程就绪队列调到内存就绪队列。
处理机调度模型 -1
3。具有高级调度和低级调度的调度队列模型
在多道批处理系统中，一般处理机管理设置作
业和进程两级调度。它比第一个模型增加了高级
调度。模型增加了在磁盘的作业后备队列，作业
调度的任务是从作业后备队列中选一个作业为它
创建至少一个进程，并分配资源，将它排入内存
进程就绪队列末尾。
4。同时具有三级调度的调度队列模型
在通用系统的多模式 OS中，一般采用具有三级
调度的调度队列模型，由于多模式 OS同时支持批
处理、分时和实时处理，所以它必须具有以上模
型，具有三级调度的调度队列模型是第二、三两
模型的综合，见图所示。
图,具有三级调度队形模型
中级
调度
调出
CP
U
交互型作业
分时间片完
等
待
事
件
完成
内存进程就绪队列
外存进程就绪队列
外存进程阻塞队列
内存进程阻塞队列
事
件
发
生
作业调度
后备作业队列
批量
作业 中级调度
调入
中级
调度
调出
磁盘
（ 4）进程调度
1。进程调度的方式
?非抢占方式
采用这种调度方式时，一旦把处理机分配给某进
程后，便让进程一直执行，直到该进程完成或发生
某事件而被阻塞时，才把处理机分配给其它进程，
决不允许某进程抢占已经分配出去的处理机。
这种调度方式的优点是实现简单、系统开销小，
适用于大多数批处理系统环境。缺点是难以满足紧
急任务的要求，不适用于实时、分时系统要求。
进程调度 -1
?抢占方式（ Preemptive mode）
这种调度方式，允许进程调度程序根据某个原则，去仃
止某个正在执行的进程，将已分配给进程的处理机，重
新分配给另一个进程。抢占的原则有：
?时间片原则。各进程按时间片运行，当一个时间片用完
后，便仃止该进程的执行而重新进行调度。这个原则适
用于分时系统。
?优先权原则。通常是对一些重要的和紧急的进程赋予较
高的优先权。当这种进程进入就绪队列时，例如由阻塞
态转换为就绪态，或从静止就绪态转为活动就绪态时，
或新创建进入就绪态的进程进入就绪队列时，如果其优
先权比正在执行的进程优先权高，便仃止正在执行的进
程，将处理机分配给优先权高的进程，使之执行。
2.调度的 时机
?在 UNIX系统中，为了减少操作系统设计的复杂性和提高
系统执行效率，对操作系统程序采用了伪异步执行方式。
也就是说，设计人员认为在系统程序执行期间不会发生
调度或发生调度的时间是可预知的，然而，由于调度程
序 swtch又是进程 0的一部分，也就是说是系统程序，这
又要求调度必须在核心态下完成。怎样把这二者统一起
来呢？显然，采用系统调用的方式向用户开放进程调度
是不可取的，这一是导致系统无法控制，二是可能造成
系统瘫痪和很多意想不到的问题出现。 UNIX的设计者们
采用了当处理机在执行完核心程序之后向用户态转换之
前的瞬间，检查各就绪进程的优先级进行调度的方法。
由用户态转而执行核心程序的可能性很多,例如中断处理
和陷阱处理，系统调用等。
3.进程调度的功能
?记录系统中所有进程的执行情况
进程管理模块在各进程的 PCB表中记录系统各
进程的执行情况和状态特征，并将各 PCB表根据
进程状态特征和资源要求排成相应的队列，并进
行动态队列转换。
?选择占有处理机进程
进程调度的主要功能是按照一定的策略（由它
决定的调度算法），选择一个处于就绪态的进程，
使其获得处理机执行。
?进行进程上下文切换
进程上下文实际上是进程执行活动全过程的静
态描述，一个进程的执行是在进程上下文中执行。
当正在执行的进程由于某种原因要让出处理机时，
系统要做上下文切换，以使另一个进程得以执行。
(5)调度方式和算法的选择准则 (Criteria)
1.面向用户 (User-oriented)的准则和评价
周转时间 (Turnaround Time)短,
它是评价批处理系统的重要性能指标。作业周转时间 Ti是
指从作业提交给系统开始，到作业完成为止的这段时间间
隔。
平均周转时间 T = 1/n×
平均带权周转时间 W = 1/n×
一个作业的带权周转时间 Wi=Ti/Tsi（ 作业的周转时间 Ti/
实际服务时间 Tsi）
响应时间 (Response Time)快
响应时间是评价分时系统的性能指标。响应时间是从用
户通过键盘提交一个请求开始，直至系统首次产生响应为
止的时间。
][
1
?
?
n
i
Ti
]/[
1
?
?
n
i
Ts iTi
调度方式和算法的选择准则 -1
?截止时间 (Deadline)的保证
它是用来评价实时系统的重要指标，截止时间是某任务必
须执行的最迟时间，或完成的最迟时间。
优先权 (Enforcing Priorities)准则
在选择批处理、分时和实时系统的调度算法时，都可引用
优先权准则，以便让那些紧急的作业（或事件），得到及时
的处理。在要求较严格的场合，往往还需选择抢占调度方式，
才能保证紧急作业得到及时的处理。
2。 面向系统 (System-oriented)的准则
达到系统设计目标
系统的设计目标是选择算法的主要依据。例如批处理系统
所追求的是充分发挥和提高计算机的效率，分时系统则侧重
于保护用户的请求及时给予响应，实时系统所关心的是不要
丢失实时信息并给予处理。
调度方式和算法的选择准则 -2
?系统吞吐量 (throughput)大
这是用来评价批处理系统的重要指标。系统吞吐
量是单位时间内完成的作业数，它与批处理作业的
平均长度具有密切关系。
处理机利用率 (Processor Utilization)高
对于大中型多用户系统，由于 CPU价格十分昂贵，
所以处理机利用率成为衡量大、中型系统性能的十
分重要指标，但对单用户微机或某些实时系统，该
准则就不那么重要。
各类资源的平衡利用 (Balancing Resources)
在大中型系统中，有效地利用各类资源（包括
CPU,外存,I/O设备等）也是一个重要指标，对于
微型机和某些实时系统，该准则也不重要。
（ 6）作业／进程调度算法
1。先来先服务 First-Come-First-Served （ FCFS）（ 作业／
进程）调度算法
FCFS是一种最简单的调度算法，可用于作业或进程调度。
此算法的原则是按照作业到达后备作业队列（或进程进入就
绪队列）的先后次序来选择作业（或进程）。 FCFS算法属于
非抢占方式，一旦一个进程占有处理机，它就一直运行下去，
直到该进程完成或者因等待某事件而不能继续运行时才释放
处理机。 FCFS算法易于实现，表面上很公平。
2。短作业／进程优先 (SJF/Shortest Process Next)调度算
法
这种调度算法主要用于作业调度，它从作业后备队列中挑
选所需运行时间（估计值）最短的作业进入主存运行。这一
算法有利于短作业，对长作业不利。采用 SJF有利于系统减
少平均周转时间和平均带权周转时间。
3。时间片轮转 Round-Robin（ RR） 调度算法
它用于进程调度，是分时系统采用的主要调度算法。
进程调度程序总是选择就绪队列中第一个进程，允
许其占有处理机一个时间片的时间。当执行的时间
片用完时，调度程序便仃止该进程的执行，并将它
送就绪队列的末尾，等待分配下一时间片再执行。
然后把处理机分配给就绪队列中新的队首进程，同
时也让它执行一个时间片。这样就可以保证就绪队
列中的所有进程，在一给定的时间内，均能获得一
时间片处理机执行时间。
在 RR算法中，时间片的大小对系统性能有很大的影
响。
4。高响应比优先 Highest Response
Ratio Next (HRRN)(作业 )调度算法
按照高响应比优先的原则，在每次选择作业投入运
行时，先计算此时后备作业队列中每个作业的响应比
RP然后选择其值最大的作业投入运行。
RP值定义为：
RP＝ （已等待时间＋要求运行时间）／要求运行时间
＝ 1＋ 已等待时间／要求运行时间。
已等待时间 =调度时间 -到达时间,
HRN算法实际上是 FCFS算法和 STF算法的折衷, HRN算
法是非抢占方式调度。
作业／进程调度算法 -3
例：假定在一个处理机上执行以下五个作业：
作业号 A B C D E
到达时间 0 1 2 3 4
运行时间 4 3 5 2 4
分别采用 FCFS,SJF,RR（ 时间片＝ 1） 和 HRN(响应比高者优先 )
四种调度算法时, 试做,（ 1） 画出调度图；
（ 2） 计算每个作业的周转时间和带权周转时间 ；
（ 3）计算平均周转时间和平均带权周转时间。
调度图：
T 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
FCFS A A A A B B B C C C C C D D E E E E
SJF A A A A D D B B B E E E E C C C C C
RR1 A B C D E A B C D E A B C E A C E C
HRN A A A A B B B D D C C C C C E E E E
例解：
作业号
A B C D E 平均
到达时间
0 1 2 3 4
运行时间
4 3 5 2 4
完成时间
4 ① 7 ② 12 ③ 14 ④ 18 ⑤
周转时间
4 6 10 11 14 9
F C F S
带权周转
时间
1 2 2 5,5 3,5 2,8
完成时间
4 ① 9 ③ 18 ⑤ 6 ② 13 ④
周转时间
4 8 16 3 9 8
SJF
带权周转
时间
2 2,6 7 3,1 1,5 2,2 5 2,1
例解 -1
作业号
A B C D E 平均
到达时间
0 1 2 3 4
运行时间
4 3 5 2 4
完成时间
15 ③ 12 ② 18 ⑤ 9 ① 17 ④
周转时间
15 11 16 6 13 1 2,4
RR
带权周转
时间
3, 7 5 3,6 7 3,2 3 3,2 5 3,3 7
完成时间
4 ① 7 ② 14 ④ 9 ③ 18 ⑤
周转时间
4 6 12 6 14 8,4
H R R N
带权周转
时间
1 2 2,4 3 3,5 2,3 8
例解 -2 RR（ 时间片＝ 1）解 2
到达 |A B C D E
作业 |↓ ↓ ↓ ↓ ↓
时间 |0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
18
调度 ||-A-|-B-|-A-|-C-|-B-|-D-|-A-|-E-|-C-|-B-|-D-|-A-|-E-|-C-|-E-|-C-|-E-|-C-
|
就 |A B A C B D A E C B D A E C E C E C
绪 | A C B D A E C B D A E C E C E C
队 | B D A E C B D A E C
列 | A E C B D A E C
| C B D A E C
进 程 A B C D E 平均
到达时间 0 1 2 3 4
运行时间 4 3 5 2 4
RR 完成时间
周转时间
1 2
1 2
1 0
9
1 8
1 6
1 1
8
1 7
1 3 1 1, 6
例解 -3
?高响应比优先 (HRRN)(作业 )调度算法计算：
T=0,只有作业 A已到达，调度作业 A运行 。
T=4,作业 A完成，作业 B,C,D,E已到达，计算作业
B,C,D,E响应比 RP分别为,1+3/3,1+2/5、
1+1/2,1+0/4，作业 B响应比最大调度运行。
T=7,作业 B完成，作业 C,D,E已到达，计算作业 C、
D,E响应比 RP分别为,1+5/5,1+4/2,1+3/4，作
业 D响应比最大调度运行。
T=9,作业 D完成，作业 C,E已到达，计算作业 C,E响
应比 RP分别为,1+7/5,1+5/4，作业 C响应比最大
调度运行。
T=14,作业 C完成，只有作业 E未完成，调度作业 E运
行 。
5.优先权 (Priority)调度算法
按照进程的优先权大小来调度，使高优先权进程得
到优先处理的调度策略称为优先权调度算法。进程
的优先权的设置可以是静态的，也可以是动态的。
?静态优先权 在进程创建时确定，且的在整个生命期
中保持不变。确定进程优先权的依据有：
进程类型，通常系统进程（例如对换进程）的优先
权高于一般用户态进程的优先权；
进程对资源的需求，如进程执行时间及内存需要省
的进程应赋予较高的优先权；
根据用户要求，由用户的紧迫程度及用户所付费用
的多少来确定进程的优先权。
? 动态优先权 是指在创建进程时所赋予的优先权，可
以随进程的推进而改变，以便获得更好的调度性能。
改变优先权的因数，随系统不同而不同，最常考虑
的因素的进程的等待时间，已使用处理机的时间，
或者资源使用情况等。
作业／进程调度算法 -5
在 UNIX系统 V中处于核心态和用户态的优先权不同。
进程处于核心态的优先权高，处于核心态的进程优先权
又分二类，一类是因等待磁盘 I/O,等待缓冲器等不可
中断优先权最高，而另一类因等待 TTY输入输出等可中
断优先权其次。处于用户态的优先权相对较低，用户态
优先权又分为 n+1级优先权。优先数为 0级的优先权最高，
优先数为 n级的优先权最低。
用户态优先权是可变的，它随着占用 CPU时间的增加
而降低。核心每隔 1秒钟便按下述公式对各进程重新计
算其用户优先数（优先数与优先权成反比关系）。
优先数＝最近使用 CPU的时间／ 2＋基本用户优先数。
线性优先级调度算法（ SRR,Selfish Round Robin）
?本算法是优先级算法的一个实例，它通过进程优先
级的递增来改进长执行时间进程的周转时间特征。
?就绪进程队列分成两个：
?新创建进程队列：按 FCFS方式排成；进程优先
级按速率 a增加；
?享受服务队列：已得到过时间片服务的进程按
FCFS方式排成；进程优先级按速率 b增加；
?新创建进程等待时间的确定：当新创建进程优先级
与享受服务队列中最后一个进程优先级相同时，转
入享受服务队列；
a
b
Time
Priority
SRR算法的优先级变化
6．多级队列调度算法
多队列调度是根据作业的性质和类型的不同，将
就绪队列再分为若干个子队列，所有的作业（或进
程）按其性质排入相应的队列中，而不同的就绪队
列采用不同的调度算法。
例如前后台系统可以建立两个就绪队列，批处理
作业所建立进程进入后台就绪队列；交互型作业所
建立的进程进入前台就绪队列。前台采用时间片轮
转算法，进程按 FCFS等策略排序，后台采用优先权
高优先的调度算法或者短作业优先的调度算法。
作业／进程调度算法 -6
对多级就绪队列调度策略有两种，一种是各就绪队
列按进程性质赋予不同的优先权，优先权高的就绪队
列的进程优先被调度，例如上例中前台就绪队列的优
先权比后台就绪队列的优先权高，所以前台队列中的
进程优先被调度。而只有当 较高 优先权的就绪队列空
时，方才调度 较低 优先权的就绪队列进程 执行, 如果
进程执行时有新进程进入较高优先级的队列，则抢先
执行新进程，并把被抢先的进程投入原队列的末尾。
在上例中只有前台队列空时，才调度后台就绪队列。
这样，只有较高优先权的就绪队列都空时才调度最低
优先权就绪队列的进程。
另一种调度就绪队列的方式是为每个队列分配一定
的占用 CPU时间的比例。如在上例中为前台队列分配
80％的 CPU时间，给后台队列分配 20％的 CPU时间。
Multilevel Queue Scheduling
7。多级反馈 (Feedback)队列调度算法
前面介绍的各种用作进程调度的算法，都有在一定的
局限性，如短进程优先算法仅照顾了短进程而怠慢了
长进程。况且对进程运行的长短，往往难以正确估计，
所以短进程优先的调度算法无法正确使用。而多级反
馈队列调度算法，则不必事先知道各种进程所需的执
行时间，仍能基本满足短进程优先和 I/O频繁的进程
优先的需要，因而是目前公认的较好的一种进程调度
算法。在 UNIX系统,WindowsNT,OS/2中都采用了类
似的调度算法。
WindowsNT采用可抢占动态优先级多级就绪队列调
度算法。 NT执行体支持 32级优先级，并将它们分成两
类，实时优先级（ 16－ 31）和可变优先级（ 1－ 15），
0级为系统保留。每个优先级一个就绪队列，高序号
队列为高优先级，调度程序从高优先级的队列开始往
下找，如高优先级队列为空时才再往下找，直至找到
一个线程。
作业／进程调度算法 -8
各个就绪队列中进程执行时间片的大小也各不相
同，在优先级越高的队列中，每个进程的执行时
间片就规定得越小。
?当一个线程执行完一个完整的时间段后被中断抢
占处理器，而被抢占的线程优先级降低一级而进
入下级就绪队列，如此继续，直至降到线程的基
本优先级。而一个线程从阻塞态变为就绪态时要
提高优先级，提高的幅度与等待的事件有关。如
等待键盘输入所提高的幅度要大于等待磁盘 I/O。
在 NT中，交互式线程处于高优先级,I/O型线程
处于中间优先级，计算型线程处于低优先级，系
统还设置一个空闲线程，其优先级为 0，是优先
级最低的线程，只要处理空闲，就执行该线程。
线程优先级
返回
16 个 实时 线程优先级
15 个 可变 线程 优先级
1 个 系统 线 程 优先级
( 零页线程)
实时 优先级
范围16 -31
实时 优先级
的相对实时
可变 优先级
范围1 -15
可变 优先级
的相对 实时
实时 优先级
的相对 空闲
可变 优先级
的相对 空闲
实时
空闲
中下
中级
中上
高级
仅用于零页线程(Wi n32 应用不能使用)
图,多级反馈队列
就绪队列 1 时间片 S1 时间片完
时间片完
就绪队列 2 时间片 S2>S1
运行
运行
运行
就绪队列 n 时间片 Sn>Sn-1
完成
完成
完成
时间片完
阻塞队列 i
阻塞
阻塞
阻塞
事件发生
时间配额用完
线程
优先级
运行状态 就绪状态
线程完整用完一个规定的时间片值时，重新赋予新时
间片值，优先级降一级（不低于基本优先级），放在
相应优先级就绪队列的尾部；
时间
运行
基本
优先级
线程
优先级
等待 运行 运行
等待结束
时的优先
级提升
时间
配额
基本 优先级
的时 间片轮转
时间配额用完 时
的优先级降低
被抢先
( 时间配额用完前)线程优先级提升
返回
线程由于调用等待函数而阻塞时，减少一个时间片
，并依据等待事件类型提高优先级；如等待键盘事
件比等待磁盘事件的提高幅度大。
?在下列 5种情况下,Windows 2000会提升线程的当前
优先级：
?I/O操作完成
?信号量或事件等待结束
?前台进程中的线程完成一个等待操作
?由于窗口活动而唤醒图形用户接口线程
?线程处于就绪状态超过一定时间，但没能进入运行状态 (处
理机饥饿 )
?线程优先级提升的目的是改进系统吞吐量、响应时间
等整体特征，解决线程调度策略中潜在的不公正性。
但它也不是完美的，它并不会使所有应用都受益。
?Windows 2000永远不会提升实时优先级范围内 (16至
31)的线程优先级。
（二） 进程死锁
（ 1）死锁的原因和条件
1。死锁的原因
?竞争资源引起死锁
在多道程序系统，多个进程共享系统的资源。系统资源分为
二类，一类是不可抢占的资源，如打印机、磁带机等。当系
统把这类资源分配给某进程后，再不能强行收回，只能在进
程用完后自动释放。另一类是可抢占的资源，如 CPU,内存等。
由于系统拥有的不可抢占的资源有限，多个进程共享竞争不
可抢占的资源就可能引起死锁。
?进程推进顺序不当引起死锁
在多道程序系统中，并发执行的进程推进序列不可予测，
有些推进顺序，进程可以顺利完成，这些推进顺序是合法的；
而有的推进顺序会引起进程无限期地等待永远不会发生的条
件而不能向前推进，造成了死锁。
死锁的原因和条件 -1
?进程推进顺序不当引起死锁例：
进程 P和 Q并发执行，进程 P和 Q程序如下：
Process P Process Q
..,.
Get A Get B
..,.
Get B Get A
..,.
Release A Release B
..,.
Release B Release A
..,.
进程 P和 Q按路径 1,2,5,6推进顺序合法，按 3,4推进顺
序非法，见下图：
进程推进顺序不当引起死锁例：
Progress
of Q
Release
A
Release
B
Get A
Get B
Get A Get B Release A
Release B
Progress
of P
A
Required B Required
A
Required
B
Required
deadlock
inevitable
1 2
3
4
5
6
P and Q
want B
P and Q
want A
死锁的原因和条件 -1
2。产生死锁的必要条件（ Conditions for Deadlock ）
?互斥（ Mutual exclusion ）条件：一个资源一次只能被
一个进程所使用，即是排它性使用。
?不可抢占（ No preemption ）条件：一个资源仅能被占
有它的进程所释放，而不能被别的进程强占。
?请求和保持（ Hold-and-wait ）条件：进程已经保持了
至少一个资源，但又提出了新的资源要求，而该资源又已被
其它进程占有，此时请求进程阻塞，但又对已经获得的其它
资源保持不放。
?环路等待（ Circular wait ）条件：当每类资源只有一个
时，在发生死锁时，必然存在一个进程 -资源的环形链。如
一系统状态的资源分配图所示,P1正在等待一个 P2 占用的
资源 R2,P2正在等待一个 P1占用的资源 R1。
死锁的原因和条件 -2
? 资源分配图由结点和边组成。结点有二类，一类是进程结
点，用园圈表示；另一类是资源结点，用小方框表示一类资
源，用方框中的小圈表示资源数。边也有二类，一类是分配
边，它由资源结点指向进程结点，另一类是申请边，它由进
程结点指向资源结点。
返回
○ R1
R2 ○
P1 P2
死锁的原因和条件 -3
3。处理 死锁的基本方法
A.死锁的预防
静态方法：在进程执行前采取的措施，通过
设置某些限制条件，去破坏产生死锁的四个必
要条件之一，防止发生死锁。
B.死锁的避免
动态的方法：在进 程 执行过程中采取的措
施，不需事先采取限制措施破坏产生死锁的必
要条件，而是在进程申请资源时用某种方法去
防止系统进入不安全状态，从而避免发生死锁。
死锁的原因和条件 -4
C.死锁的检测和解除
这种方法预先并不采用任何限制措施，允许系统
在运行过程中发生死锁，但可通过系统设置的检测
机构及时检测死锁的发生，如检测到死锁，则采用
撤消进程等死锁解除方法使系统 恢复 正常工作。
D.驼鸟算法 (The Ostrich Algorithm)
自称没有 死锁问题, 理由是死锁极少发生和预防的成
本太高 。 如发生死锁采用重启动和人工 恢复方法 。
这是方便和正确的折中 方法 。 大部分的操作系统包
括 UNIX and Windows 采用这种方法 。
（ 2）死锁的预防 (Deadlock Prevention)
预防死锁的方法是破坏四个产生死锁的必要条件之一。
1。破坏互斥条件
互斥使用是资源本身特征所决定的。使用硬软件
结合可改变资源本身特性，例如采用 SPOOLing技术
可将, 独享, 打印机改变为, 共享, 的打印机。
2。破坏不可抢占条件
抢占式调度法主要用于处理机和存贮器资源调度，
它们的状态容易保存和恢复。但此法对外部设备和
私存数据不宜使用。
死锁的预防 -1
3。破坏请求和保持条件
系统可采用资源静态予分配方式来破坏请求保持
条件。系统要求所有进程一次性地申请在整个运行
过程中全部资源，若系统有足够资源满足给进程，
则在运行前，一次性将其所需要的所有资源分配给
该进程。这样该进程在整个运行期间，便不再提出
资源要求，从而摒弃了请求条件。这种预防死锁的
方法，优点是简单、易予实现且很安全，但其资源
利用率很低，进程也延迟运行。
4。破坏循环等待条件
? 有序资源使用法
该方法将所有的资源按类型进行线性排队，并赋
予不同的序号。例如令输入机的序号为 1，打印机序
号为 2，磁盘机序号为 3等。
死锁的预防 -2
所有进程对资源的请求必须严格按资源序号递增的次序提出。
这样在所形成的资源分配图中不可能再出现环路，因而摒弃
了, 环路等待, 条件，在采用这种策略时总有一个进程占据
了较高序号的资源，它继续请求的资源必然是空闲的，因而
进程可以一直向前推进。这种预防死锁的策略可以提高资源
利用率，但在进程使用各类资源的顺序与系统规定的顺序不
同时会造成资源浪费的情况。
?资源按级分配法
该方法是把资源递增排序成若干等级（如 L1,L2……,Lm），
其中每级可包含几类资源，要求每个进程在获得了 Lj级中资
源之后,它才能申请更高级的 LK（ LK＞ Lj） 级中的资源；如
果它还需申请比 LK级低的 LI级（ LI<LK） 资源，则必须先释放
所有大于 LI级的资源。该方法是 Haveder 1968年在设计 IBM／
360 OS时提出的，资源共分三级，第一级数据集或文件，第
二级主存，第三级 I/O设备。
(3)死锁的避免 (Deadlock Avoidance)
该方法允许进程动态地申请资源，系统在进行资源分配之
前，先计算资源分配的安全性。若此次分配不会导致系统
从安全状态向不安全状态转换，便可将资源分配给进程；
否则不分配资源，进程必须阻塞等待。从而避免发生死锁。
1.系统的安全状态
安全状态是指系统的一种状态，在此状态开始系统能按某
种顺序（例如 P1,P2…… Pn） 来为各个进程分配其所需资源，
直至最大需求，使每个进程都可顺序地一个个地完成。这
个序列（ P1,P2……,Pn） 称为安全序列。若系统此状态不
存在一个安全序列，则称系统处于不安全状态。
?例：假如系统中有 P1,P2和 P3三个进程和 12台磁带机。各进
程最大需求和 T0时刻分配状态如下：
?进程 最大需求 已分配 还需请求 可用
P1 10 5 5 3
P2 4 2 2
P3 9 2 7
死锁的避免 -1
?分析 T0状态，可以找到一个安全序列（ P2,P1,P3）,即系统
按此进程序列分配资源，每个进程都可顺利完成，其步骤如
下：
先将可用的 3台磁带机中 2台分配给 P2,P2满足了最大的资源需
求，在有限时间内运行完毕，释放它占有的全部资源，使可
用资源数量增至 5台。再将可用的 5 台磁带机分配给 P1,最后
将可用 10台中 7台磁带机分配给 P3。
这样三进程可按照（ P2,P1,P3） 序列顺序地一个个执行完成，
则（ P2,P1,P3） 序列是安全序列,T0时刻状态也是安全状态。
2。由安全状态向不安全状态的转换
如果在 T0 状态不按安全序列进行分配，可能会导致系统进入
一个不安全状态，例如在 T0状态下 P3中申请 1台磁带机。如系
统实施此次分配使系统状态由 T0变为 T1状态，分析 T1状态安全
情况。
死锁的避免 -2
T1时刻状态：
进程 最大需求 已分配 还需请求 可用 可用
分配资源前 释放 资源 后
P1 10 5 5 > 4
P2 4 2 2 =< 2 4
P3 9 3 6 > 4
因为找不到一个安全序列使所有进程顺序地一个个地运
行完毕，所以 T1状态是不安全状态，由于实施分配给 1台
磁带机给 P3的操作会引起系统状态由安全状态 T0向不安全
状态下的转换，所以为了避免死锁，上述的分配只是安
全检测，检测后判定这样的申请不能满足,P3为申请 1台
磁带机而必须阻塞等待。
3.利用银行家算法避免死锁
最具代表的避免死锁算法是 Dijkstra的银行家算法，这是
由于该算法用于银行系统现金贷款的发放而得名。
?银行家算法的数据结构
? 可用资源向量 Available [m]
m为系统中资源种类数,Available[j]=k表示系统中第 j
类资源数为 k个。
? 最大需求矩阵 Max[n,m]
n为系统中进程数,Max[i,j]=k表示进程 i对 j类资源的最
大需求数为中 k。
? 分配矩阵 Allocation[n,m]
它定义了系统中每一类资源当前已分配给每一进程资源
数,Allocation[i,j]=k表示进程 i已分得 j类资源的数
目为 k个。
利用银行家算法避免死锁 -1
? 需求矩阵 Need[n,m]
它表示每个进程尚需的各类资源数,Need[i,j]=k 表示进程
i还需要 j类资源 k个。 Need[i,j]=Max[i,j]-Allocation[i,j]
?银行家算法
?假设在进程并发执行时进程 i提出请求 j类资源 k个后，表示
为 Requesti[j]=k。 系统按下述步骤进行安全检查：
如果 Requesti≤Need i则继续以下检查，否则显示需求申请超
出最大需求值的错误。
如果 Requesti≤Available 则继续以下检查，否则显示系统无
足够资源,Pi阻塞等待。
系统试探把要求的资源分配给进程 i并修改有关数据结构的值：
Available = Available-Requesti ；
Allocationi =Allocationi+Requesti ；
Needi=Needi-Requesti ；
利用银行家算法避免死锁 -2
系统执行安全性算法，检查此次资源分配后，系统
是否处于安全状态，若安全，才正式将资源分配给
进程 i,以完成本次分配；否则将试探分配作废，恢
复原来的资源分配状态，让进程 Pi等待。
③安全性算法
安全性算法执行步骤如下：
A.初始化设置工作向量 Work[m]表示系统可提供的各类
资源数目，用以保护原数据结构有关值。 Work =
Available,设置完成标志向量 Finish[n]。
Finish[i] = false 表示 i进程尚末完成，如值为
true则表示进程 i已完成。
利用银行家算法避免死锁 -3
B.从进程集合 n中找到一个能满足下述二个条件,
Finish[i] = false和 Necdi≤Work, 如找到则执
行步骤 C,如找不到同时满足以上二条件的进程
则执行步骤 D。
C.当进程 i获得资源后可顺利执行直到完成，并释
放出分配给它的资源，表示如下：
work = work+Allocationi ；
Finish[i]=true ； 转执行步骤 B。
D.如果所有的 Finish[i]＝ ture,则表示系统处于
安全状态，否则系统处于不安全状态。
?银行家算法 例：
假定系统中有五个进程 {P0,P1,P2,P3,P4}和三种类型资源
{A,B,C},每一种资源的数量分别为 10,5,7。各进程的
最大需求,T0时刻资源分配情况如下 所示。
Max Allocation Need
Available
A B C A B C A B C A B C
P0 7 5 3 0 1 0 7 4 3 3 3 2
P1 3 2 2 2 0 0 1 2 2
P2 9 0 2 3 0 2 6 0 0
P3 2 2 2 2 1 1 0 1 1
P4 4 3 3 0 0 2 4 3 1
试问,① T0时刻是否安全？
② P1请求资源 Request1(1,0,2)是否允许？
③ P4请求资源 Request4(3,3,0)是否允许？
银行家算法 例 -1
?T0时刻是否安全？
从表中可找出一个序列 (P1, P3,P4, P2, P0） 使各进程 顺序
地一个个地执行 完成 。
Max Allocation Need Available Available
(分配资源前 ) (释放 资源 后）
A B C A B C A B C A B C A B C
P0 7 5 3 0 1 0 7 4 3 =< 10 4 7 ⑤ 10 5 7
P1 3 2 2 2 0 0 1 2 2 =< 3 3 2 ① 5 3 2
P2 9 0 2 3 0 2 6 0 0 =< 7 4 5 ④ 10 4 7
P3 2 2 2 2 1 1 0 1 1 =< 5 3 2 ② 7 4 3
P4 4 3 3 0 0 2 4 3 1 =< 7 4 3 ③ 7 4 5
安全序列为 {P1,P3,P4,P2,P0},T0时刻系统是安全的。
?P1请求资源 Request1(1,0,2)可否允许？
银行家算法 例 -2
Request1(1,0,2)≤Need 1(1,2,2),P1请求在最大需求
范围内。
Request1(1,0,2)≤ Available(3,3,2), 可用资源可
满足 P1请求需要。
试探把要求的资源分配给进程 P1并修改有关数据结构
的数值：
Available = Available(3,3,2)－
Request1(1,0,2)=Available(2,3,0)；
Need1 = Need1(1,2,2)－ Request1(1,0,2)=
Need1(0,2,0)；
Allocation1 =Allocation1(2,0,0)+Request1(1,0,2)
=Allocation1(3,0,2)；
利用安全性算法检查试探将资源分配后状态的安全性
如下：
银行家算法 例 -3
Max Allocation Need Available Available
(分配资源前 ) (释放 资源 后）
A B C A B C A B C A B C A B C
P0 7 5 3 0 1 0 7 4 3 =< 10 4 7 ⑤ 10 5 7
P1 3 2 2 3 0 2 0 2 0 =< 2 3 0 ① 5 3 2
P2 9 0 2 3 0 2 6 0 0 =< 7 4 5 ④ 10 4 7
P3 2 2 2 2 1 1 0 1 1 =< 5 3 2 ② 7 4 3
P4 4 3 3 0 0 2 4 3 1 =< 7 4 3 ③ 7 4 5
因为先分配资源给 P1进程符合按安全序列 {P1,P3,P4,P2,P0}
分配资源，所以试探将资源分配给进程 P1后的状态是安全的，
可将资源分配给进程 P1。
?P4请求资源 Request4(3,3,0)是否允许？
Request4(3,3,0)≤Need 4(4,3,1),P4请求在最大需求范围内。
Request4(3,3,0)≤Available(2,3,0) 不成立，即可用资源暂不
能满足 P4请求资源需要,P4阻塞等待。
（ 4）死锁的检测 (Deadlock Detection)
死锁的避免算法增加了系统的开销，死锁的检测采用资源分配
图的简化判断是否发生了不安全状态。如发现系统处于不安
全状态时，即执行死锁解除的策略，采用此法开销相对减少。
1。资源分配图的简化：
系统处于某 S状态时可用资源分配图表示，可用资源分配图
简化来判断系统是否处于死锁状态。资源分配图简化的方法
如下：在资源分配图中找一个既不阻塞又非孤立的进程结点
PI（ 如某进程既无已分配的资源也不需申请资源，即既无分
配边又无申请边，则该进程结点是孤立结点），让它获得所
需资源而继续运行直至完毕，再释放它拥有的所有的资源，
这相当于取消 PI的分配边和请求边，使它成为孤立结点。
经过以上简化，如所有的进程结点都是孤立结点则称资源分
配图是可完全简化的。若不能通过任何过程使该图完全简化，
则该图是不可完全简化的。资源分配图简化如 下图,
资源分配图的简化例,
P1
。。。。 。
P1
P2
。 。
。
P1
P2
。。
。。
。
P2
。。
R1 R2
R1 R
2
R2R1
死锁的检测 -1
2。死锁定理：
S为死锁状态的充分条件是：尚且仅当 S状态的
资源分配图是不可完全简化的，该充分条件称为
死锁定理。
3。死锁检测的数据和算法类似于银行家算法。
（ 5）死锁的解除
?当检测死锁的软件判别死锁存在时，就要解除死锁，
使系统从死锁中恢复。
?第一种是强制性地从系统中撤消一个或多个死锁的
进程以断开循环等待链，并收回分配给终止进程的
全部资源供剩下的进程使用。借助于撤消进程来解
除死锁可以使用两种方法。一种是撤消全部的死锁
进程，这显然会断开死锁环路，但代价太大。另一
种方法是逐个撤消死锁的进程直至死锁环路消除。
这里存在一个按照什么原则进行逐个撤消进程的问
题。目前较实用而又简便的方法是撤消那些代价最
小的进程。所谓影响一个进程的撤消代价因素有该
进程的优先权，该进程运行到今的运行代价（包括
CPU时间，使用资源的种类和时间等）、与相关的
作业类型和外部代价等。
死锁的解除 -1
?死锁恢复的另一种办法是使用一个有效的挂起和
解除机构来挂起一些死锁的进程，其实质是从被
挂起的进程那里抢占资源以解除死锁，许多学者
认为在此领域的研究工作比起其它死锁恢复的办
法更为重要。例如一个系统提供了检查点和重新
启动的便利的话，我们可以暂时仃止一个系统，
而后从各进程的最近的检查点（系统保留了检查
点的状态）逐次地重新启动。这既可以从死锁中
恢复，又使进程损失最小（从检查点以后的损
失）。但许多系统还没有此功能，在 IBM4300系
列等机器上提供了此类功能。
处理死锁的综合方式
?内部 资源 — PCB
死锁预防 — 使用 资源定序,破坏 循环等待。
?主 存储器 ---用户态存储空间
死锁预防 — 使用抢占, 破坏 非抢占。
?可交换 空间
死锁预防 ---使用预先 全分配,破坏 占有并等待。
?作业资源 ---设备,文件
死锁 避免 ---
?特殊资源
死锁检测、死锁恢复
解决死锁问题的综合方法
?资源归类,将各种资源归入若干个不同的资源类
(resource group)中，如：外存交换区空间，进程
资源（可分配的设备，如磁带机，文件），主存空
间，内部资源（如 I/O通道）
?资源排序,在不同资源类之间规定次序，对不同资
源类中的资源采用线性按序申请的方法
?针对性优化,对同一资源类中的资源，采用适当的
方法。如：
?进程资源－－避免，
?外存交换区空间，主存，内部资源－－预防
习题
1,在操作系统中处理机管理由作业管理和进程管理两部分组成,
作业管理把作业流分成提交, 后备, 运行, 完成四个状态,
进程管理把进程分成就绪, 执行, 阻塞三个基本状态 。 作业
由后备状态到运行状态由﹎﹎ B﹎﹎ 完成, 进程由就绪状态到
执行状态由﹎﹎ C﹎﹎, 用户进程的祖先进程由﹎﹎ E﹎﹎ 建
立的 。
A,B,C,D,E,(1)作业调度程序； (2)进程调度程序； (3)存
储管理程序； (4)输入输出程序； (5)假脱机 （ SPOOLing） 处
理程序； (6)交通程序； (7)设备管理程序 。
2,操作系统的主要性能参数：﹎﹎ A﹎﹎ 指的是单位时间内系
统处理的作业量 。 ﹎﹎ B﹎﹎ 指的是从作业或命令的输入到其
结束的间隔时间, 在分析性能时常用其倒数 。 ﹎﹎ C﹎﹎ 指的
是在一个给定的时间内, 系统的一个指定成份被使用的时间
比例 。
A,B,C,(1)周转时间； (2)处理时间； (3)消逝时间； (4)利
用率； (5)生产率； (6)吞吐量 。
习题 -1
3,在所学的调度算法中, 对所有进程和作业都是公平合理的调
度算法是﹎﹎ A﹎﹎； 最有利于提高系统吞吐量的作业调度算
法是﹎﹎ B﹎﹎； 能兼顾作业等待时间和作业执行时间调度算
法是﹎﹎ C﹎﹎； 最有利于提高资源的使用率, 能使短作业,
长作业及交互作业用户都比较满意的调度算法是﹎﹎ D﹎﹎；
为实现人机交互作用应采用调度算法是﹎﹎ E﹎﹎； 能对紧急
作业进行及时处理的调度算法是﹎﹎ F﹎﹎ 。
A,B,C,D,(1)FCFS调度算法； (2)短作业优先调度算法； (3)
时间片轮转法； (4)多级反馈队列调度算法； (5) 高响应比优
先算法； (6)基于优先权的剥夺调度算法 。
4.假定在一个处理机上执行以下五个作业，
作 业 号 1 2 3 4 5
到 达 时 间 0 2 4 6 8
运 行 时 间 3 6 4 5 2
当分别采用 FCFS,SJF(短作业优先 )和 HRRN（ 响应比高者优先）
三种调度算法时，试问,
习题 -2
⑴ 三种调度算法调度次序为﹎﹎ A﹎﹎, ﹎﹎ B﹎﹎ 和﹎﹎ C﹎﹎；
⑵ 采用 FCFS调度算法时 1--5号作业的周转时间为﹎﹎ D1﹎﹎,
﹎﹎ E1﹎﹎, ﹎﹎ F1﹎﹎, ﹎﹎ G1﹎﹎ 和﹎﹎ H1﹎﹎； 采用
SJF调度算法时 1--5号作业的周转时间为﹎﹎ D2﹎﹎, ﹎﹎ E2
﹎﹎, ﹎﹎ F2﹎﹎, ﹎﹎ G2﹎﹎ 和﹎﹎ H2﹎﹎； 采用 HRRN调
度算法时 1--5号作业的周转时间为﹎﹎ D3﹎﹎, ﹎﹎ E3﹎﹎,
﹎﹎ F3﹎﹎, ﹎﹎ G3﹎﹎ 和﹎﹎ H3﹎﹎；
⑶ 三种调度算法的平均周转时间为﹎﹎ I﹎﹎, ﹎﹎ J﹎﹎ 和﹎
﹎ K﹎﹎ 。
A,B,C,(1)1 2 3 4 5 ; (2)5 1 3 4 2 ; (3)1 5 3 4 2 ;
(4)1 2 5 3 4 ; (5)1 2 3 5 4 ;
D1---H1, D2---H2,D3---H3,(1)1 (2)2 (3)3 (4)4 (5)5
(6)6 (7)7 (8)8 (9)9 (10)10 (11)11 (12)12
(13)13 (14)14 (15)15 (16)16 (17)17 (18)18
(19)19 (20)20
I,J,K,(1)7.0 (2)7.6 (3)8.0 (4)8.6 (5)9.0 (6)9.6
(7)10.0 (8)11.0
习题 -3
5,产生死锁的基本原因是﹎﹎ A﹎﹎ 和﹎﹎ B﹎﹎, 产生死锁的
四个必要条件是互斥条件﹎﹎ C﹎﹎, 不剥夺条件和﹎﹎ D﹎
﹎ 。
A,(1)资源分配不当； (2)系统资源不足； (3)作业调度不当；
(4)资源的独占性 。
B,(1)进程推进顺序非法； (2)进程调度不当； (3)系统中进程
太多； (4)CPU运行太快 。
C,(1)请求和阻塞条件； (2)请求和释放条件； (3)请求和保持
条件； (4)释放和阻塞条 件； (5)释放和请求条件 。
D,(1)线性增长条件； (2)环路条件； (3)无序释放条件； (4)
有序请求条件； (5) 无序请求条件 。
习题 -4
6,预防死锁的论述中，﹎﹎ A﹎﹎ 条是正确的论述。
(1)由于产生死锁的基本原因是系统资源不足，因而预防死锁的
有效方法，是根据系统规模，配置足够的系统资源。
(2)由于产生死锁的另一种基本原因是进程推进顺序不当，因而
预防死锁的有效方法，是使进程的推进顺序合法。
(3)因为只要系统不进入不安全状态，便不会产生死锁，故预防
死锁的有效方法，是防止系统进入不安全状态。
(4)可以通过破坏产生死锁的四个必要条件之一或其中几个的方
法，来预防发生死锁。
习题 -5
7,试描述避免死锁的银行家算法, 若系统运行中出现下述资源
分配情况
进程 ALLOCATION NEED AVAILABLE
A B C D A B C D A B C D
P0 0 0 3 2 0 0 1 2 1 6 2 2
P1 1 0 0 0 1 7 5 0
P2 1 3 5 4 2 3 5 6
P3 0 3 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6
该系统是安全,安全序列为﹎﹎ A﹎﹎, ﹎﹎ B﹎﹎, ﹎﹎ C﹎﹎,
﹎﹎ D﹎﹎, ﹎﹎ E﹎﹎ 。
如果进程 P2此时提出资源申请 （ 1,2,2,2）, 系统﹎﹎ F﹎
﹎ 将资源分配给它 。
A---E,(1)P0 (2)P1 (3)P2 (4)P3 (5)P4
B,(1) 能 (2) 不能
8,试述死锁产生的原因和必要条件及解决死锁的方法 。
习题 -6
9,在一个多道程序系统中,作业从提交给系统到运行结束退
出系统,通常要经历哪几个阶段和哪些状态？ 你能说出这些
状态转变的原因吗？ 由哪些程序来负责这些状态之间的转
换 。
10,试述 Windows NT进程调度算法。
(Scheduling and Deadlock )
教学目的：
在多道程序系统中，一个作业从提交到执行完成，
要经历多级调度，调度的好坏要影响系统的运行性
能，因此调度是多道系统的关键。为了改善系统 资
源 的利用率和提高系统处理能力，多道程序系统中
采用多个进程的并发执行，但它也可能发生死锁的
危险，研究死锁的原因和产生条件，采用预防死锁、
避免死锁、检测死锁和解除死锁等多种方法防止死
锁是多道程序系统重要的研究课题。
教学要求：
?熟悉 处理机三级调度 概念和 处理机调度模型,掌
握作业的状态和作业 调度的功能。
掌握进程调度的方式和功能,熟悉 调度方式和
算法的选择准则,掌握七种 调度算法及适合范围。
?掌握 死锁的定义和产生死锁的原因,掌握 死锁的
四个必要条件； 熟悉 预防死锁的方法，熟练掌握
银行家算法及其在死锁避免中的应用；掌握资源
分配图的简化及其死锁定理,熟悉 解除死锁的方
法。
（一） 调度 (Scheduling)
（ 1）处理机三级调度
1。高级 (Long-term)调度 ―― 作业调度
作业调度用于决定把外存输入井上处于作业后备队列上的哪
些作业调入内存，并为它们创建进程、分配必要的资源，然
后再将新创建的进程排在就绪队列上，准备执行。在批处理
系统中，作业是先驻留在外存的输入井上的，因此需要有作
业调度。然而在分时系统中，通过键盘输入的命令和数据直
接进入内存，无需作业调度。
2。低级 (Short-term)调度 ―― 进程调度
进程调度决定就绪队列中哪个进程将获得处理机，然后由分
派程序执行把处理机分配给该进程的操作。进程调度是最基
本的调度，任何操作系统都有进程调度。
处理机三级调度 -1
3。中级 (Medium-term)调度 —— 对换
引入中级调度的目的是为了提高主存利用率和系统
吞吐量。由于在进程并发执行过程中，为了充分发
挥内存的效能，需将那些暂时不能运行的进程从内
存调到外存盘交换区去等待，而将那些在盘交换区
的等待事件已经发生急需调度运行的进程从盘交换
区调入内存。在 UNIX系统中中级调度就是存储管理
中的对换，采用虚拟存储技术的分时系统往往设立
中级调度。
图：处理机三级调度
外存 (盘 )交换区
作业
后备
状态
作业
提交
状态 作业 完成状态
终止 作业
就绪
态
阻塞
态
中级调度
主存
进程调度 运行态
就绪
态
阻塞
态
作业调度 作业运行状态
外存
Scheduling in Batch Systems
Three level scheduling
（ 2）作业调度
1。作业的状态
作业从进入到运行结束，一般需要经历, 提交,,, 后备,,
,运行, 和, 完成, 四个阶段。
?提交状态
一个作业被提交给机房后正在通过 SPOOLing系统进行输入
或用户通过终端向计算机中键入其作业时所处于的状态为提
交状态。
?后备状态
作业已经过 SPOOLing系统输入到磁盘输入井，等待调入内
存运行，此时作业处于后备状态。为了管理和调度作业，为
每个作业设置一个作业控制块（ JCB）。 作业控制块记录了作
业类型和资源要求等有关信息。作业控制块按作业类型组成
一个或多个后备作业队列。
作业调度 -1
?运行状态
一个在后备作业队列的作业被作业调度程序选中
后，分配必要的资源，建立一组相应的进程后，调
入内存，该作业就进入运行状态。进程各状态（进
程运行态、内存进程就绪态、内存阻塞态、外存进
程就绪态、外存进程阻塞态等）都对应作业运行状
态。
?完成状态
当进程正常运行结束或因发生错误而终止时，作
业进入完成状态。终止作业程序将负责善后处理。
作业调度 -2
2。作业状态的转换
?作业调度
作业调度程序按一定算法从后备作业队列中选
一个满足资源要求的作业，分配它所要求的资源，
建立一组相应的进程，设置该进程状态为就绪态，
并将该进程插入内存就绪队列，参加 CPU争夺。
?终止作业
当进程正常运行结束或因发生错误终止时，调
用终止作业程序，它负责将输出文件缓冲输出到
输出井，并调用 SPOOLing系统输出进程将作业输
出文件在打印机输出。同时回收作业所使用内、
外存,I/O设备等各种资源，最后调用记帐程序
结清作业费用。
（ 3） 处理机调度模型
1。仅有进程调度的调度队列模型
在分时系统中通常仅设置了进程调度。此时系统有一个就
绪队列，每个进程运行一个时间片，进程运行一个时间片后
如未完成，则被放在就绪队列末尾。如进程运行中因等待某
事件（例如申请 I/O而等待 I/O完成），则需排入阻塞队列，
系统因阻塞的原因不同可设几个阻塞队列。
2。有进程调度和中级调度队列模型
在具有虚拟存储器技术的分时系统中（例如 UNIX系统等），
一般采用具有进程调度和中级调度的调度模型。在该模型中
比第一种模型增加了中级调度，则相对于上模型也增加了外
存进程就绪队列和外存进程阻塞队列。中级调度时或从内存
就绪队列调到外存的就绪队列，或从内存阻塞队列调到外存
阻塞队列，或从外存进程就绪队列调到内存就绪队列。
处理机调度模型 -1
3。具有高级调度和低级调度的调度队列模型
在多道批处理系统中，一般处理机管理设置作
业和进程两级调度。它比第一个模型增加了高级
调度。模型增加了在磁盘的作业后备队列，作业
调度的任务是从作业后备队列中选一个作业为它
创建至少一个进程，并分配资源，将它排入内存
进程就绪队列末尾。
4。同时具有三级调度的调度队列模型
在通用系统的多模式 OS中，一般采用具有三级
调度的调度队列模型，由于多模式 OS同时支持批
处理、分时和实时处理，所以它必须具有以上模
型，具有三级调度的调度队列模型是第二、三两
模型的综合，见图所示。
图,具有三级调度队形模型
中级
调度
调出
CP
U
交互型作业
分时间片完
等
待
事
件
完成
内存进程就绪队列
外存进程就绪队列
外存进程阻塞队列
内存进程阻塞队列
事
件
发
生
作业调度
后备作业队列
批量
作业 中级调度
调入
中级
调度
调出
磁盘
（ 4）进程调度
1。进程调度的方式
?非抢占方式
采用这种调度方式时，一旦把处理机分配给某进
程后，便让进程一直执行，直到该进程完成或发生
某事件而被阻塞时，才把处理机分配给其它进程，
决不允许某进程抢占已经分配出去的处理机。
这种调度方式的优点是实现简单、系统开销小，
适用于大多数批处理系统环境。缺点是难以满足紧
急任务的要求，不适用于实时、分时系统要求。
进程调度 -1
?抢占方式（ Preemptive mode）
这种调度方式，允许进程调度程序根据某个原则，去仃
止某个正在执行的进程，将已分配给进程的处理机，重
新分配给另一个进程。抢占的原则有：
?时间片原则。各进程按时间片运行，当一个时间片用完
后，便仃止该进程的执行而重新进行调度。这个原则适
用于分时系统。
?优先权原则。通常是对一些重要的和紧急的进程赋予较
高的优先权。当这种进程进入就绪队列时，例如由阻塞
态转换为就绪态，或从静止就绪态转为活动就绪态时，
或新创建进入就绪态的进程进入就绪队列时，如果其优
先权比正在执行的进程优先权高，便仃止正在执行的进
程，将处理机分配给优先权高的进程，使之执行。
2.调度的 时机
?在 UNIX系统中，为了减少操作系统设计的复杂性和提高
系统执行效率，对操作系统程序采用了伪异步执行方式。
也就是说，设计人员认为在系统程序执行期间不会发生
调度或发生调度的时间是可预知的，然而，由于调度程
序 swtch又是进程 0的一部分，也就是说是系统程序，这
又要求调度必须在核心态下完成。怎样把这二者统一起
来呢？显然，采用系统调用的方式向用户开放进程调度
是不可取的，这一是导致系统无法控制，二是可能造成
系统瘫痪和很多意想不到的问题出现。 UNIX的设计者们
采用了当处理机在执行完核心程序之后向用户态转换之
前的瞬间，检查各就绪进程的优先级进行调度的方法。
由用户态转而执行核心程序的可能性很多,例如中断处理
和陷阱处理，系统调用等。
3.进程调度的功能
?记录系统中所有进程的执行情况
进程管理模块在各进程的 PCB表中记录系统各
进程的执行情况和状态特征，并将各 PCB表根据
进程状态特征和资源要求排成相应的队列，并进
行动态队列转换。
?选择占有处理机进程
进程调度的主要功能是按照一定的策略（由它
决定的调度算法），选择一个处于就绪态的进程，
使其获得处理机执行。
?进行进程上下文切换
进程上下文实际上是进程执行活动全过程的静
态描述，一个进程的执行是在进程上下文中执行。
当正在执行的进程由于某种原因要让出处理机时，
系统要做上下文切换，以使另一个进程得以执行。
(5)调度方式和算法的选择准则 (Criteria)
1.面向用户 (User-oriented)的准则和评价
周转时间 (Turnaround Time)短,
它是评价批处理系统的重要性能指标。作业周转时间 Ti是
指从作业提交给系统开始，到作业完成为止的这段时间间
隔。
平均周转时间 T = 1/n×
平均带权周转时间 W = 1/n×
一个作业的带权周转时间 Wi=Ti/Tsi（ 作业的周转时间 Ti/
实际服务时间 Tsi）
响应时间 (Response Time)快
响应时间是评价分时系统的性能指标。响应时间是从用
户通过键盘提交一个请求开始，直至系统首次产生响应为
止的时间。
][
1
?
?
n
i
Ti
]/[
1
?
?
n
i
Ts iTi
调度方式和算法的选择准则 -1
?截止时间 (Deadline)的保证
它是用来评价实时系统的重要指标，截止时间是某任务必
须执行的最迟时间，或完成的最迟时间。
优先权 (Enforcing Priorities)准则
在选择批处理、分时和实时系统的调度算法时，都可引用
优先权准则，以便让那些紧急的作业（或事件），得到及时
的处理。在要求较严格的场合，往往还需选择抢占调度方式，
才能保证紧急作业得到及时的处理。
2。 面向系统 (System-oriented)的准则
达到系统设计目标
系统的设计目标是选择算法的主要依据。例如批处理系统
所追求的是充分发挥和提高计算机的效率，分时系统则侧重
于保护用户的请求及时给予响应，实时系统所关心的是不要
丢失实时信息并给予处理。
调度方式和算法的选择准则 -2
?系统吞吐量 (throughput)大
这是用来评价批处理系统的重要指标。系统吞吐
量是单位时间内完成的作业数，它与批处理作业的
平均长度具有密切关系。
处理机利用率 (Processor Utilization)高
对于大中型多用户系统，由于 CPU价格十分昂贵，
所以处理机利用率成为衡量大、中型系统性能的十
分重要指标，但对单用户微机或某些实时系统，该
准则就不那么重要。
各类资源的平衡利用 (Balancing Resources)
在大中型系统中，有效地利用各类资源（包括
CPU,外存,I/O设备等）也是一个重要指标，对于
微型机和某些实时系统，该准则也不重要。
（ 6）作业／进程调度算法
1。先来先服务 First-Come-First-Served （ FCFS）（ 作业／
进程）调度算法
FCFS是一种最简单的调度算法，可用于作业或进程调度。
此算法的原则是按照作业到达后备作业队列（或进程进入就
绪队列）的先后次序来选择作业（或进程）。 FCFS算法属于
非抢占方式，一旦一个进程占有处理机，它就一直运行下去，
直到该进程完成或者因等待某事件而不能继续运行时才释放
处理机。 FCFS算法易于实现，表面上很公平。
2。短作业／进程优先 (SJF/Shortest Process Next)调度算
法
这种调度算法主要用于作业调度，它从作业后备队列中挑
选所需运行时间（估计值）最短的作业进入主存运行。这一
算法有利于短作业，对长作业不利。采用 SJF有利于系统减
少平均周转时间和平均带权周转时间。
3。时间片轮转 Round-Robin（ RR） 调度算法
它用于进程调度，是分时系统采用的主要调度算法。
进程调度程序总是选择就绪队列中第一个进程，允
许其占有处理机一个时间片的时间。当执行的时间
片用完时，调度程序便仃止该进程的执行，并将它
送就绪队列的末尾，等待分配下一时间片再执行。
然后把处理机分配给就绪队列中新的队首进程，同
时也让它执行一个时间片。这样就可以保证就绪队
列中的所有进程，在一给定的时间内，均能获得一
时间片处理机执行时间。
在 RR算法中，时间片的大小对系统性能有很大的影
响。
4。高响应比优先 Highest Response
Ratio Next (HRRN)(作业 )调度算法
按照高响应比优先的原则，在每次选择作业投入运
行时，先计算此时后备作业队列中每个作业的响应比
RP然后选择其值最大的作业投入运行。
RP值定义为：
RP＝ （已等待时间＋要求运行时间）／要求运行时间
＝ 1＋ 已等待时间／要求运行时间。
已等待时间 =调度时间 -到达时间,
HRN算法实际上是 FCFS算法和 STF算法的折衷, HRN算
法是非抢占方式调度。
作业／进程调度算法 -3
例：假定在一个处理机上执行以下五个作业：
作业号 A B C D E
到达时间 0 1 2 3 4
运行时间 4 3 5 2 4
分别采用 FCFS,SJF,RR（ 时间片＝ 1） 和 HRN(响应比高者优先 )
四种调度算法时, 试做,（ 1） 画出调度图；
（ 2） 计算每个作业的周转时间和带权周转时间 ；
（ 3）计算平均周转时间和平均带权周转时间。
调度图：
T 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
FCFS A A A A B B B C C C C C D D E E E E
SJF A A A A D D B B B E E E E C C C C C
RR1 A B C D E A B C D E A B C E A C E C
HRN A A A A B B B D D C C C C C E E E E
例解：
作业号
A B C D E 平均
到达时间
0 1 2 3 4
运行时间
4 3 5 2 4
完成时间
4 ① 7 ② 12 ③ 14 ④ 18 ⑤
周转时间
4 6 10 11 14 9
F C F S
带权周转
时间
1 2 2 5,5 3,5 2,8
完成时间
4 ① 9 ③ 18 ⑤ 6 ② 13 ④
周转时间
4 8 16 3 9 8
SJF
带权周转
时间
2 2,6 7 3,1 1,5 2,2 5 2,1
例解 -1
作业号
A B C D E 平均
到达时间
0 1 2 3 4
运行时间
4 3 5 2 4
完成时间
15 ③ 12 ② 18 ⑤ 9 ① 17 ④
周转时间
15 11 16 6 13 1 2,4
RR
带权周转
时间
3, 7 5 3,6 7 3,2 3 3,2 5 3,3 7
完成时间
4 ① 7 ② 14 ④ 9 ③ 18 ⑤
周转时间
4 6 12 6 14 8,4
H R R N
带权周转
时间
1 2 2,4 3 3,5 2,3 8
例解 -2 RR（ 时间片＝ 1）解 2
到达 |A B C D E
作业 |↓ ↓ ↓ ↓ ↓
时间 |0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
18
调度 ||-A-|-B-|-A-|-C-|-B-|-D-|-A-|-E-|-C-|-B-|-D-|-A-|-E-|-C-|-E-|-C-|-E-|-C-
|
就 |A B A C B D A E C B D A E C E C E C
绪 | A C B D A E C B D A E C E C E C
队 | B D A E C B D A E C
列 | A E C B D A E C
| C B D A E C
进 程 A B C D E 平均
到达时间 0 1 2 3 4
运行时间 4 3 5 2 4
RR 完成时间
周转时间
1 2
1 2
1 0
9
1 8
1 6
1 1
8
1 7
1 3 1 1, 6
例解 -3
?高响应比优先 (HRRN)(作业 )调度算法计算：
T=0,只有作业 A已到达，调度作业 A运行 。
T=4,作业 A完成，作业 B,C,D,E已到达，计算作业
B,C,D,E响应比 RP分别为,1+3/3,1+2/5、
1+1/2,1+0/4，作业 B响应比最大调度运行。
T=7,作业 B完成，作业 C,D,E已到达，计算作业 C、
D,E响应比 RP分别为,1+5/5,1+4/2,1+3/4，作
业 D响应比最大调度运行。
T=9,作业 D完成，作业 C,E已到达，计算作业 C,E响
应比 RP分别为,1+7/5,1+5/4，作业 C响应比最大
调度运行。
T=14,作业 C完成，只有作业 E未完成，调度作业 E运
行 。
5.优先权 (Priority)调度算法
按照进程的优先权大小来调度，使高优先权进程得
到优先处理的调度策略称为优先权调度算法。进程
的优先权的设置可以是静态的，也可以是动态的。
?静态优先权 在进程创建时确定，且的在整个生命期
中保持不变。确定进程优先权的依据有：
进程类型，通常系统进程（例如对换进程）的优先
权高于一般用户态进程的优先权；
进程对资源的需求，如进程执行时间及内存需要省
的进程应赋予较高的优先权；
根据用户要求，由用户的紧迫程度及用户所付费用
的多少来确定进程的优先权。
? 动态优先权 是指在创建进程时所赋予的优先权，可
以随进程的推进而改变，以便获得更好的调度性能。
改变优先权的因数，随系统不同而不同，最常考虑
的因素的进程的等待时间，已使用处理机的时间，
或者资源使用情况等。
作业／进程调度算法 -5
在 UNIX系统 V中处于核心态和用户态的优先权不同。
进程处于核心态的优先权高，处于核心态的进程优先权
又分二类，一类是因等待磁盘 I/O,等待缓冲器等不可
中断优先权最高，而另一类因等待 TTY输入输出等可中
断优先权其次。处于用户态的优先权相对较低，用户态
优先权又分为 n+1级优先权。优先数为 0级的优先权最高，
优先数为 n级的优先权最低。
用户态优先权是可变的，它随着占用 CPU时间的增加
而降低。核心每隔 1秒钟便按下述公式对各进程重新计
算其用户优先数（优先数与优先权成反比关系）。
优先数＝最近使用 CPU的时间／ 2＋基本用户优先数。
线性优先级调度算法（ SRR,Selfish Round Robin）
?本算法是优先级算法的一个实例，它通过进程优先
级的递增来改进长执行时间进程的周转时间特征。
?就绪进程队列分成两个：
?新创建进程队列：按 FCFS方式排成；进程优先
级按速率 a增加；
?享受服务队列：已得到过时间片服务的进程按
FCFS方式排成；进程优先级按速率 b增加；
?新创建进程等待时间的确定：当新创建进程优先级
与享受服务队列中最后一个进程优先级相同时，转
入享受服务队列；
a
b
Time
Priority
SRR算法的优先级变化
6．多级队列调度算法
多队列调度是根据作业的性质和类型的不同，将
就绪队列再分为若干个子队列，所有的作业（或进
程）按其性质排入相应的队列中，而不同的就绪队
列采用不同的调度算法。
例如前后台系统可以建立两个就绪队列，批处理
作业所建立进程进入后台就绪队列；交互型作业所
建立的进程进入前台就绪队列。前台采用时间片轮
转算法，进程按 FCFS等策略排序，后台采用优先权
高优先的调度算法或者短作业优先的调度算法。
作业／进程调度算法 -6
对多级就绪队列调度策略有两种，一种是各就绪队
列按进程性质赋予不同的优先权，优先权高的就绪队
列的进程优先被调度，例如上例中前台就绪队列的优
先权比后台就绪队列的优先权高，所以前台队列中的
进程优先被调度。而只有当 较高 优先权的就绪队列空
时，方才调度 较低 优先权的就绪队列进程 执行, 如果
进程执行时有新进程进入较高优先级的队列，则抢先
执行新进程，并把被抢先的进程投入原队列的末尾。
在上例中只有前台队列空时，才调度后台就绪队列。
这样，只有较高优先权的就绪队列都空时才调度最低
优先权就绪队列的进程。
另一种调度就绪队列的方式是为每个队列分配一定
的占用 CPU时间的比例。如在上例中为前台队列分配
80％的 CPU时间，给后台队列分配 20％的 CPU时间。
Multilevel Queue Scheduling
7。多级反馈 (Feedback)队列调度算法
前面介绍的各种用作进程调度的算法，都有在一定的
局限性，如短进程优先算法仅照顾了短进程而怠慢了
长进程。况且对进程运行的长短，往往难以正确估计，
所以短进程优先的调度算法无法正确使用。而多级反
馈队列调度算法，则不必事先知道各种进程所需的执
行时间，仍能基本满足短进程优先和 I/O频繁的进程
优先的需要，因而是目前公认的较好的一种进程调度
算法。在 UNIX系统,WindowsNT,OS/2中都采用了类
似的调度算法。
WindowsNT采用可抢占动态优先级多级就绪队列调
度算法。 NT执行体支持 32级优先级，并将它们分成两
类，实时优先级（ 16－ 31）和可变优先级（ 1－ 15），
0级为系统保留。每个优先级一个就绪队列，高序号
队列为高优先级，调度程序从高优先级的队列开始往
下找，如高优先级队列为空时才再往下找，直至找到
一个线程。
作业／进程调度算法 -8
各个就绪队列中进程执行时间片的大小也各不相
同，在优先级越高的队列中，每个进程的执行时
间片就规定得越小。
?当一个线程执行完一个完整的时间段后被中断抢
占处理器，而被抢占的线程优先级降低一级而进
入下级就绪队列，如此继续，直至降到线程的基
本优先级。而一个线程从阻塞态变为就绪态时要
提高优先级，提高的幅度与等待的事件有关。如
等待键盘输入所提高的幅度要大于等待磁盘 I/O。
在 NT中，交互式线程处于高优先级,I/O型线程
处于中间优先级，计算型线程处于低优先级，系
统还设置一个空闲线程，其优先级为 0，是优先
级最低的线程，只要处理空闲，就执行该线程。
线程优先级
返回
16 个 实时 线程优先级
15 个 可变 线程 优先级
1 个 系统 线 程 优先级
( 零页线程)
实时 优先级
范围16 -31
实时 优先级
的相对实时
可变 优先级
范围1 -15
可变 优先级
的相对 实时
实时 优先级
的相对 空闲
可变 优先级
的相对 空闲
实时
空闲
中下
中级
中上
高级
仅用于零页线程(Wi n32 应用不能使用)
图,多级反馈队列
就绪队列 1 时间片 S1 时间片完
时间片完
就绪队列 2 时间片 S2>S1
运行
运行
运行
就绪队列 n 时间片 Sn>Sn-1
完成
完成
完成
时间片完
阻塞队列 i
阻塞
阻塞
阻塞
事件发生
时间配额用完
线程
优先级
运行状态 就绪状态
线程完整用完一个规定的时间片值时，重新赋予新时
间片值，优先级降一级（不低于基本优先级），放在
相应优先级就绪队列的尾部；
时间
运行
基本
优先级
线程
优先级
等待 运行 运行
等待结束
时的优先
级提升
时间
配额
基本 优先级
的时 间片轮转
时间配额用完 时
的优先级降低
被抢先
( 时间配额用完前)线程优先级提升
返回
线程由于调用等待函数而阻塞时，减少一个时间片
，并依据等待事件类型提高优先级；如等待键盘事
件比等待磁盘事件的提高幅度大。
?在下列 5种情况下,Windows 2000会提升线程的当前
优先级：
?I/O操作完成
?信号量或事件等待结束
?前台进程中的线程完成一个等待操作
?由于窗口活动而唤醒图形用户接口线程
?线程处于就绪状态超过一定时间，但没能进入运行状态 (处
理机饥饿 )
?线程优先级提升的目的是改进系统吞吐量、响应时间
等整体特征，解决线程调度策略中潜在的不公正性。
但它也不是完美的，它并不会使所有应用都受益。
?Windows 2000永远不会提升实时优先级范围内 (16至
31)的线程优先级。
（二） 进程死锁
（ 1）死锁的原因和条件
1。死锁的原因
?竞争资源引起死锁
在多道程序系统，多个进程共享系统的资源。系统资源分为
二类，一类是不可抢占的资源，如打印机、磁带机等。当系
统把这类资源分配给某进程后，再不能强行收回，只能在进
程用完后自动释放。另一类是可抢占的资源，如 CPU,内存等。
由于系统拥有的不可抢占的资源有限，多个进程共享竞争不
可抢占的资源就可能引起死锁。
?进程推进顺序不当引起死锁
在多道程序系统中，并发执行的进程推进序列不可予测，
有些推进顺序，进程可以顺利完成，这些推进顺序是合法的；
而有的推进顺序会引起进程无限期地等待永远不会发生的条
件而不能向前推进，造成了死锁。
死锁的原因和条件 -1
?进程推进顺序不当引起死锁例：
进程 P和 Q并发执行，进程 P和 Q程序如下：
Process P Process Q
..,.
Get A Get B
..,.
Get B Get A
..,.
Release A Release B
..,.
Release B Release A
..,.
进程 P和 Q按路径 1,2,5,6推进顺序合法，按 3,4推进顺
序非法，见下图：
进程推进顺序不当引起死锁例：
Progress
of Q
Release
A
Release
B
Get A
Get B
Get A Get B Release A
Release B
Progress
of P
A
Required B Required
A
Required
B
Required
deadlock
inevitable
1 2
3
4
5
6
P and Q
want B
P and Q
want A
死锁的原因和条件 -1
2。产生死锁的必要条件（ Conditions for Deadlock ）
?互斥（ Mutual exclusion ）条件：一个资源一次只能被
一个进程所使用，即是排它性使用。
?不可抢占（ No preemption ）条件：一个资源仅能被占
有它的进程所释放，而不能被别的进程强占。
?请求和保持（ Hold-and-wait ）条件：进程已经保持了
至少一个资源，但又提出了新的资源要求，而该资源又已被
其它进程占有，此时请求进程阻塞，但又对已经获得的其它
资源保持不放。
?环路等待（ Circular wait ）条件：当每类资源只有一个
时，在发生死锁时，必然存在一个进程 -资源的环形链。如
一系统状态的资源分配图所示,P1正在等待一个 P2 占用的
资源 R2,P2正在等待一个 P1占用的资源 R1。
死锁的原因和条件 -2
? 资源分配图由结点和边组成。结点有二类，一类是进程结
点，用园圈表示；另一类是资源结点，用小方框表示一类资
源，用方框中的小圈表示资源数。边也有二类，一类是分配
边，它由资源结点指向进程结点，另一类是申请边，它由进
程结点指向资源结点。
返回
○ R1
R2 ○
P1 P2
死锁的原因和条件 -3
3。处理 死锁的基本方法
A.死锁的预防
静态方法：在进程执行前采取的措施，通过
设置某些限制条件，去破坏产生死锁的四个必
要条件之一，防止发生死锁。
B.死锁的避免
动态的方法：在进 程 执行过程中采取的措
施，不需事先采取限制措施破坏产生死锁的必
要条件，而是在进程申请资源时用某种方法去
防止系统进入不安全状态，从而避免发生死锁。
死锁的原因和条件 -4
C.死锁的检测和解除
这种方法预先并不采用任何限制措施，允许系统
在运行过程中发生死锁，但可通过系统设置的检测
机构及时检测死锁的发生，如检测到死锁，则采用
撤消进程等死锁解除方法使系统 恢复 正常工作。
D.驼鸟算法 (The Ostrich Algorithm)
自称没有 死锁问题, 理由是死锁极少发生和预防的成
本太高 。 如发生死锁采用重启动和人工 恢复方法 。
这是方便和正确的折中 方法 。 大部分的操作系统包
括 UNIX and Windows 采用这种方法 。
（ 2）死锁的预防 (Deadlock Prevention)
预防死锁的方法是破坏四个产生死锁的必要条件之一。
1。破坏互斥条件
互斥使用是资源本身特征所决定的。使用硬软件
结合可改变资源本身特性，例如采用 SPOOLing技术
可将, 独享, 打印机改变为, 共享, 的打印机。
2。破坏不可抢占条件
抢占式调度法主要用于处理机和存贮器资源调度，
它们的状态容易保存和恢复。但此法对外部设备和
私存数据不宜使用。
死锁的预防 -1
3。破坏请求和保持条件
系统可采用资源静态予分配方式来破坏请求保持
条件。系统要求所有进程一次性地申请在整个运行
过程中全部资源，若系统有足够资源满足给进程，
则在运行前，一次性将其所需要的所有资源分配给
该进程。这样该进程在整个运行期间，便不再提出
资源要求，从而摒弃了请求条件。这种预防死锁的
方法，优点是简单、易予实现且很安全，但其资源
利用率很低，进程也延迟运行。
4。破坏循环等待条件
? 有序资源使用法
该方法将所有的资源按类型进行线性排队，并赋
予不同的序号。例如令输入机的序号为 1，打印机序
号为 2，磁盘机序号为 3等。
死锁的预防 -2
所有进程对资源的请求必须严格按资源序号递增的次序提出。
这样在所形成的资源分配图中不可能再出现环路，因而摒弃
了, 环路等待, 条件，在采用这种策略时总有一个进程占据
了较高序号的资源，它继续请求的资源必然是空闲的，因而
进程可以一直向前推进。这种预防死锁的策略可以提高资源
利用率，但在进程使用各类资源的顺序与系统规定的顺序不
同时会造成资源浪费的情况。
?资源按级分配法
该方法是把资源递增排序成若干等级（如 L1,L2……,Lm），
其中每级可包含几类资源，要求每个进程在获得了 Lj级中资
源之后,它才能申请更高级的 LK（ LK＞ Lj） 级中的资源；如
果它还需申请比 LK级低的 LI级（ LI<LK） 资源，则必须先释放
所有大于 LI级的资源。该方法是 Haveder 1968年在设计 IBM／
360 OS时提出的，资源共分三级，第一级数据集或文件，第
二级主存，第三级 I/O设备。
(3)死锁的避免 (Deadlock Avoidance)
该方法允许进程动态地申请资源，系统在进行资源分配之
前，先计算资源分配的安全性。若此次分配不会导致系统
从安全状态向不安全状态转换，便可将资源分配给进程；
否则不分配资源，进程必须阻塞等待。从而避免发生死锁。
1.系统的安全状态
安全状态是指系统的一种状态，在此状态开始系统能按某
种顺序（例如 P1,P2…… Pn） 来为各个进程分配其所需资源，
直至最大需求，使每个进程都可顺序地一个个地完成。这
个序列（ P1,P2……,Pn） 称为安全序列。若系统此状态不
存在一个安全序列，则称系统处于不安全状态。
?例：假如系统中有 P1,P2和 P3三个进程和 12台磁带机。各进
程最大需求和 T0时刻分配状态如下：
?进程 最大需求 已分配 还需请求 可用
P1 10 5 5 3
P2 4 2 2
P3 9 2 7
死锁的避免 -1
?分析 T0状态，可以找到一个安全序列（ P2,P1,P3）,即系统
按此进程序列分配资源，每个进程都可顺利完成，其步骤如
下：
先将可用的 3台磁带机中 2台分配给 P2,P2满足了最大的资源需
求，在有限时间内运行完毕，释放它占有的全部资源，使可
用资源数量增至 5台。再将可用的 5 台磁带机分配给 P1,最后
将可用 10台中 7台磁带机分配给 P3。
这样三进程可按照（ P2,P1,P3） 序列顺序地一个个执行完成，
则（ P2,P1,P3） 序列是安全序列,T0时刻状态也是安全状态。
2。由安全状态向不安全状态的转换
如果在 T0 状态不按安全序列进行分配，可能会导致系统进入
一个不安全状态，例如在 T0状态下 P3中申请 1台磁带机。如系
统实施此次分配使系统状态由 T0变为 T1状态，分析 T1状态安全
情况。
死锁的避免 -2
T1时刻状态：
进程 最大需求 已分配 还需请求 可用 可用
分配资源前 释放 资源 后
P1 10 5 5 > 4
P2 4 2 2 =< 2 4
P3 9 3 6 > 4
因为找不到一个安全序列使所有进程顺序地一个个地运
行完毕，所以 T1状态是不安全状态，由于实施分配给 1台
磁带机给 P3的操作会引起系统状态由安全状态 T0向不安全
状态下的转换，所以为了避免死锁，上述的分配只是安
全检测，检测后判定这样的申请不能满足,P3为申请 1台
磁带机而必须阻塞等待。
3.利用银行家算法避免死锁
最具代表的避免死锁算法是 Dijkstra的银行家算法，这是
由于该算法用于银行系统现金贷款的发放而得名。
?银行家算法的数据结构
? 可用资源向量 Available [m]
m为系统中资源种类数,Available[j]=k表示系统中第 j
类资源数为 k个。
? 最大需求矩阵 Max[n,m]
n为系统中进程数,Max[i,j]=k表示进程 i对 j类资源的最
大需求数为中 k。
? 分配矩阵 Allocation[n,m]
它定义了系统中每一类资源当前已分配给每一进程资源
数,Allocation[i,j]=k表示进程 i已分得 j类资源的数
目为 k个。
利用银行家算法避免死锁 -1
? 需求矩阵 Need[n,m]
它表示每个进程尚需的各类资源数,Need[i,j]=k 表示进程
i还需要 j类资源 k个。 Need[i,j]=Max[i,j]-Allocation[i,j]
?银行家算法
?假设在进程并发执行时进程 i提出请求 j类资源 k个后，表示
为 Requesti[j]=k。 系统按下述步骤进行安全检查：
如果 Requesti≤Need i则继续以下检查，否则显示需求申请超
出最大需求值的错误。
如果 Requesti≤Available 则继续以下检查，否则显示系统无
足够资源,Pi阻塞等待。
系统试探把要求的资源分配给进程 i并修改有关数据结构的值：
Available = Available-Requesti ；
Allocationi =Allocationi+Requesti ；
Needi=Needi-Requesti ；
利用银行家算法避免死锁 -2
系统执行安全性算法，检查此次资源分配后，系统
是否处于安全状态，若安全，才正式将资源分配给
进程 i,以完成本次分配；否则将试探分配作废，恢
复原来的资源分配状态，让进程 Pi等待。
③安全性算法
安全性算法执行步骤如下：
A.初始化设置工作向量 Work[m]表示系统可提供的各类
资源数目，用以保护原数据结构有关值。 Work =
Available,设置完成标志向量 Finish[n]。
Finish[i] = false 表示 i进程尚末完成，如值为
true则表示进程 i已完成。
利用银行家算法避免死锁 -3
B.从进程集合 n中找到一个能满足下述二个条件,
Finish[i] = false和 Necdi≤Work, 如找到则执
行步骤 C,如找不到同时满足以上二条件的进程
则执行步骤 D。
C.当进程 i获得资源后可顺利执行直到完成，并释
放出分配给它的资源，表示如下：
work = work+Allocationi ；
Finish[i]=true ； 转执行步骤 B。
D.如果所有的 Finish[i]＝ ture,则表示系统处于
安全状态，否则系统处于不安全状态。
?银行家算法 例：
假定系统中有五个进程 {P0,P1,P2,P3,P4}和三种类型资源
{A,B,C},每一种资源的数量分别为 10,5,7。各进程的
最大需求,T0时刻资源分配情况如下 所示。
Max Allocation Need
Available
A B C A B C A B C A B C
P0 7 5 3 0 1 0 7 4 3 3 3 2
P1 3 2 2 2 0 0 1 2 2
P2 9 0 2 3 0 2 6 0 0
P3 2 2 2 2 1 1 0 1 1
P4 4 3 3 0 0 2 4 3 1
试问,① T0时刻是否安全？
② P1请求资源 Request1(1,0,2)是否允许？
③ P4请求资源 Request4(3,3,0)是否允许？
银行家算法 例 -1
?T0时刻是否安全？
从表中可找出一个序列 (P1, P3,P4, P2, P0） 使各进程 顺序
地一个个地执行 完成 。
Max Allocation Need Available Available
(分配资源前 ) (释放 资源 后）
A B C A B C A B C A B C A B C
P0 7 5 3 0 1 0 7 4 3 =< 10 4 7 ⑤ 10 5 7
P1 3 2 2 2 0 0 1 2 2 =< 3 3 2 ① 5 3 2
P2 9 0 2 3 0 2 6 0 0 =< 7 4 5 ④ 10 4 7
P3 2 2 2 2 1 1 0 1 1 =< 5 3 2 ② 7 4 3
P4 4 3 3 0 0 2 4 3 1 =< 7 4 3 ③ 7 4 5
安全序列为 {P1,P3,P4,P2,P0},T0时刻系统是安全的。
?P1请求资源 Request1(1,0,2)可否允许？
银行家算法 例 -2
Request1(1,0,2)≤Need 1(1,2,2),P1请求在最大需求
范围内。
Request1(1,0,2)≤ Available(3,3,2), 可用资源可
满足 P1请求需要。
试探把要求的资源分配给进程 P1并修改有关数据结构
的数值：
Available = Available(3,3,2)－
Request1(1,0,2)=Available(2,3,0)；
Need1 = Need1(1,2,2)－ Request1(1,0,2)=
Need1(0,2,0)；
Allocation1 =Allocation1(2,0,0)+Request1(1,0,2)
=Allocation1(3,0,2)；
利用安全性算法检查试探将资源分配后状态的安全性
如下：
银行家算法 例 -3
Max Allocation Need Available Available
(分配资源前 ) (释放 资源 后）
A B C A B C A B C A B C A B C
P0 7 5 3 0 1 0 7 4 3 =< 10 4 7 ⑤ 10 5 7
P1 3 2 2 3 0 2 0 2 0 =< 2 3 0 ① 5 3 2
P2 9 0 2 3 0 2 6 0 0 =< 7 4 5 ④ 10 4 7
P3 2 2 2 2 1 1 0 1 1 =< 5 3 2 ② 7 4 3
P4 4 3 3 0 0 2 4 3 1 =< 7 4 3 ③ 7 4 5
因为先分配资源给 P1进程符合按安全序列 {P1,P3,P4,P2,P0}
分配资源，所以试探将资源分配给进程 P1后的状态是安全的，
可将资源分配给进程 P1。
?P4请求资源 Request4(3,3,0)是否允许？
Request4(3,3,0)≤Need 4(4,3,1),P4请求在最大需求范围内。
Request4(3,3,0)≤Available(2,3,0) 不成立，即可用资源暂不
能满足 P4请求资源需要,P4阻塞等待。
（ 4）死锁的检测 (Deadlock Detection)
死锁的避免算法增加了系统的开销，死锁的检测采用资源分配
图的简化判断是否发生了不安全状态。如发现系统处于不安
全状态时，即执行死锁解除的策略，采用此法开销相对减少。
1。资源分配图的简化：
系统处于某 S状态时可用资源分配图表示，可用资源分配图
简化来判断系统是否处于死锁状态。资源分配图简化的方法
如下：在资源分配图中找一个既不阻塞又非孤立的进程结点
PI（ 如某进程既无已分配的资源也不需申请资源，即既无分
配边又无申请边，则该进程结点是孤立结点），让它获得所
需资源而继续运行直至完毕，再释放它拥有的所有的资源，
这相当于取消 PI的分配边和请求边，使它成为孤立结点。
经过以上简化，如所有的进程结点都是孤立结点则称资源分
配图是可完全简化的。若不能通过任何过程使该图完全简化，
则该图是不可完全简化的。资源分配图简化如 下图,
资源分配图的简化例,
P1
。。。。 。
P1
P2
。 。
。
P1
P2
。。
。。
。
P2
。。
R1 R2
R1 R
2
R2R1
死锁的检测 -1
2。死锁定理：
S为死锁状态的充分条件是：尚且仅当 S状态的
资源分配图是不可完全简化的，该充分条件称为
死锁定理。
3。死锁检测的数据和算法类似于银行家算法。
（ 5）死锁的解除
?当检测死锁的软件判别死锁存在时，就要解除死锁，
使系统从死锁中恢复。
?第一种是强制性地从系统中撤消一个或多个死锁的
进程以断开循环等待链，并收回分配给终止进程的
全部资源供剩下的进程使用。借助于撤消进程来解
除死锁可以使用两种方法。一种是撤消全部的死锁
进程，这显然会断开死锁环路，但代价太大。另一
种方法是逐个撤消死锁的进程直至死锁环路消除。
这里存在一个按照什么原则进行逐个撤消进程的问
题。目前较实用而又简便的方法是撤消那些代价最
小的进程。所谓影响一个进程的撤消代价因素有该
进程的优先权，该进程运行到今的运行代价（包括
CPU时间，使用资源的种类和时间等）、与相关的
作业类型和外部代价等。
死锁的解除 -1
?死锁恢复的另一种办法是使用一个有效的挂起和
解除机构来挂起一些死锁的进程，其实质是从被
挂起的进程那里抢占资源以解除死锁，许多学者
认为在此领域的研究工作比起其它死锁恢复的办
法更为重要。例如一个系统提供了检查点和重新
启动的便利的话，我们可以暂时仃止一个系统，
而后从各进程的最近的检查点（系统保留了检查
点的状态）逐次地重新启动。这既可以从死锁中
恢复，又使进程损失最小（从检查点以后的损
失）。但许多系统还没有此功能，在 IBM4300系
列等机器上提供了此类功能。
处理死锁的综合方式
?内部 资源 — PCB
死锁预防 — 使用 资源定序,破坏 循环等待。
?主 存储器 ---用户态存储空间
死锁预防 — 使用抢占, 破坏 非抢占。
?可交换 空间
死锁预防 ---使用预先 全分配,破坏 占有并等待。
?作业资源 ---设备,文件
死锁 避免 ---
?特殊资源
死锁检测、死锁恢复
解决死锁问题的综合方法
?资源归类,将各种资源归入若干个不同的资源类
(resource group)中，如：外存交换区空间，进程
资源（可分配的设备，如磁带机，文件），主存空
间，内部资源（如 I/O通道）
?资源排序,在不同资源类之间规定次序，对不同资
源类中的资源采用线性按序申请的方法
?针对性优化,对同一资源类中的资源，采用适当的
方法。如：
?进程资源－－避免，
?外存交换区空间，主存，内部资源－－预防
习题
1,在操作系统中处理机管理由作业管理和进程管理两部分组成,
作业管理把作业流分成提交, 后备, 运行, 完成四个状态,
进程管理把进程分成就绪, 执行, 阻塞三个基本状态 。 作业
由后备状态到运行状态由﹎﹎ B﹎﹎ 完成, 进程由就绪状态到
执行状态由﹎﹎ C﹎﹎, 用户进程的祖先进程由﹎﹎ E﹎﹎ 建
立的 。
A,B,C,D,E,(1)作业调度程序； (2)进程调度程序； (3)存
储管理程序； (4)输入输出程序； (5)假脱机 （ SPOOLing） 处
理程序； (6)交通程序； (7)设备管理程序 。
2,操作系统的主要性能参数：﹎﹎ A﹎﹎ 指的是单位时间内系
统处理的作业量 。 ﹎﹎ B﹎﹎ 指的是从作业或命令的输入到其
结束的间隔时间, 在分析性能时常用其倒数 。 ﹎﹎ C﹎﹎ 指的
是在一个给定的时间内, 系统的一个指定成份被使用的时间
比例 。
A,B,C,(1)周转时间； (2)处理时间； (3)消逝时间； (4)利
用率； (5)生产率； (6)吞吐量 。
习题 -1
3,在所学的调度算法中, 对所有进程和作业都是公平合理的调
度算法是﹎﹎ A﹎﹎； 最有利于提高系统吞吐量的作业调度算
法是﹎﹎ B﹎﹎； 能兼顾作业等待时间和作业执行时间调度算
法是﹎﹎ C﹎﹎； 最有利于提高资源的使用率, 能使短作业,
长作业及交互作业用户都比较满意的调度算法是﹎﹎ D﹎﹎；
为实现人机交互作用应采用调度算法是﹎﹎ E﹎﹎； 能对紧急
作业进行及时处理的调度算法是﹎﹎ F﹎﹎ 。
A,B,C,D,(1)FCFS调度算法； (2)短作业优先调度算法； (3)
时间片轮转法； (4)多级反馈队列调度算法； (5) 高响应比优
先算法； (6)基于优先权的剥夺调度算法 。
4.假定在一个处理机上执行以下五个作业，
作 业 号 1 2 3 4 5
到 达 时 间 0 2 4 6 8
运 行 时 间 3 6 4 5 2
当分别采用 FCFS,SJF(短作业优先 )和 HRRN（ 响应比高者优先）
三种调度算法时，试问,
习题 -2
⑴ 三种调度算法调度次序为﹎﹎ A﹎﹎, ﹎﹎ B﹎﹎ 和﹎﹎ C﹎﹎；
⑵ 采用 FCFS调度算法时 1--5号作业的周转时间为﹎﹎ D1﹎﹎,
﹎﹎ E1﹎﹎, ﹎﹎ F1﹎﹎, ﹎﹎ G1﹎﹎ 和﹎﹎ H1﹎﹎； 采用
SJF调度算法时 1--5号作业的周转时间为﹎﹎ D2﹎﹎, ﹎﹎ E2
﹎﹎, ﹎﹎ F2﹎﹎, ﹎﹎ G2﹎﹎ 和﹎﹎ H2﹎﹎； 采用 HRRN调
度算法时 1--5号作业的周转时间为﹎﹎ D3﹎﹎, ﹎﹎ E3﹎﹎,
﹎﹎ F3﹎﹎, ﹎﹎ G3﹎﹎ 和﹎﹎ H3﹎﹎；
⑶ 三种调度算法的平均周转时间为﹎﹎ I﹎﹎, ﹎﹎ J﹎﹎ 和﹎
﹎ K﹎﹎ 。
A,B,C,(1)1 2 3 4 5 ; (2)5 1 3 4 2 ; (3)1 5 3 4 2 ;
(4)1 2 5 3 4 ; (5)1 2 3 5 4 ;
D1---H1, D2---H2,D3---H3,(1)1 (2)2 (3)3 (4)4 (5)5
(6)6 (7)7 (8)8 (9)9 (10)10 (11)11 (12)12
(13)13 (14)14 (15)15 (16)16 (17)17 (18)18
(19)19 (20)20
I,J,K,(1)7.0 (2)7.6 (3)8.0 (4)8.6 (5)9.0 (6)9.6
(7)10.0 (8)11.0
习题 -3
5,产生死锁的基本原因是﹎﹎ A﹎﹎ 和﹎﹎ B﹎﹎, 产生死锁的
四个必要条件是互斥条件﹎﹎ C﹎﹎, 不剥夺条件和﹎﹎ D﹎
﹎ 。
A,(1)资源分配不当； (2)系统资源不足； (3)作业调度不当；
(4)资源的独占性 。
B,(1)进程推进顺序非法； (2)进程调度不当； (3)系统中进程
太多； (4)CPU运行太快 。
C,(1)请求和阻塞条件； (2)请求和释放条件； (3)请求和保持
条件； (4)释放和阻塞条 件； (5)释放和请求条件 。
D,(1)线性增长条件； (2)环路条件； (3)无序释放条件； (4)
有序请求条件； (5) 无序请求条件 。
习题 -4
6,预防死锁的论述中，﹎﹎ A﹎﹎ 条是正确的论述。
(1)由于产生死锁的基本原因是系统资源不足，因而预防死锁的
有效方法，是根据系统规模，配置足够的系统资源。
(2)由于产生死锁的另一种基本原因是进程推进顺序不当，因而
预防死锁的有效方法，是使进程的推进顺序合法。
(3)因为只要系统不进入不安全状态，便不会产生死锁，故预防
死锁的有效方法，是防止系统进入不安全状态。
(4)可以通过破坏产生死锁的四个必要条件之一或其中几个的方
法，来预防发生死锁。
习题 -5
7,试描述避免死锁的银行家算法, 若系统运行中出现下述资源
分配情况
进程 ALLOCATION NEED AVAILABLE
A B C D A B C D A B C D
P0 0 0 3 2 0 0 1 2 1 6 2 2
P1 1 0 0 0 1 7 5 0
P2 1 3 5 4 2 3 5 6
P3 0 3 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6
该系统是安全,安全序列为﹎﹎ A﹎﹎, ﹎﹎ B﹎﹎, ﹎﹎ C﹎﹎,
﹎﹎ D﹎﹎, ﹎﹎ E﹎﹎ 。
如果进程 P2此时提出资源申请 （ 1,2,2,2）, 系统﹎﹎ F﹎
﹎ 将资源分配给它 。
A---E,(1)P0 (2)P1 (3)P2 (4)P3 (5)P4
B,(1) 能 (2) 不能
8,试述死锁产生的原因和必要条件及解决死锁的方法 。
习题 -6
9,在一个多道程序系统中,作业从提交给系统到运行结束退
出系统,通常要经历哪几个阶段和哪些状态？ 你能说出这些
状态转变的原因吗？ 由哪些程序来负责这些状态之间的转
换 。
10,试述 Windows NT进程调度算法。
