当前位置：文档之家 › 第三章第八节--死锁

第三章第八节--死锁

  • 格式：ppt
  • 大小：4.36 MB
  • 文档页数：62

下载文档原格式

  / 62

合集下载

chapter3处理机调度与死锁

chapter3处理机调度与死锁


1.先进先出(FIFO)算法
• FCFS有利于长作业，而不利于短作业。
– 该算法短作业C的带权周转时间为100，这是无法容忍的， 而长作业D的带权周转时间仅为1.99。
• 所以，FCFS有利于CPU繁忙型作业（如科学计算）， 而不利于I/O繁忙型作业。目前大多数的事务处理都 属于I/O繁忙型作业
2.短作业(进程)优先调度算法
图 3-7 A和B任务每次必须完成的时间
在刚开始时(t1=0)，A1必须在20ms时完成，而它本身运 行又需 10 ms，可算出A1的松弛度为10ms；B1必须在50ms 时完成， 而它本身运行就需25 ms，可算出B1的松弛度为25 ms，故调度程序应先调度A1执行。在t2=10 ms时，A2的松弛 度可按下式算出： A2的松弛度=必须完成时间-其本身的运行时间-当前时间 =40 ms-10 ms-10 ms=20 ms 类似地，可算出B1的松弛度为15ms，调度程序应选择 B1运行。t3=30 ms时，A2的松弛度已减为0，B1的松弛度为 15 ms，于是调度程序应抢占B1的处理机而调度A2运行…….
2.进程调度的任务
进程调度的任务是控制协 调进程对CPU的竞争,即按一定 的调度算法从就绪队列中选中 一个进程，把CPU的使用权交 给被选中的进程
3.确定法的原则
• 具有公平性 • 资源利用率高（特别是CPU利用 率） • 在交互式系统情况下要追求响应 时间（越短越好） • 在批处理系统情况下要追求系统 吞吐量
3.最高优先权优先调度算法
• 动态优先数法：在进程创建时创立一个优 先数，但在其生命周期内优先权可以随进 程的推进或随其等待时间的增加而改变的， 以便获得更好的调度性能。
4.高响应比优先调度算法
优先权的变化规律可描述为：
第三章 处理机调度与死锁PPT课件

第三章 处理机调度与死锁PPT课件

第三章 处理机调度与死锁
3.1 处理机调度的层次 3.2 调度队列模型和调度准则 3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除
1
第一部分
整体概述
THE FIRST PART OF THE OVERALL OVERVIEW, PLEASE SUMMARIZE THE CONTENT
✓ 当一个进程运行完毕，或由于某种错误而终止运行 ✓ 当一个进程在运行中处于等待状态（等待I/O） ✓ 在进程通信中，执行中的进程执行了某种原语操作
（P操作，阻塞原语，唤醒原语） ✓ 分时系统中时间片到 ✓ 当有一个优先级更高的进程就绪
1) 非抢占方式(Non-preemptive Mode)
2) 抢占方式(Preemptive Mode)
2
3.1 处理机调度的层次
处理机三级调度
1.高级调度――作业调度
在批处理系统中，作业是先驻留在外存的输入井上 的，因此需要有作业调度。然而在分时系统中，通过键 盘输入的命令和数据直接进入内存，无需作业调度。 2.低级调度――进程调度
进程调度决定就绪队列中哪个进程将获得处理机， 然后由分派程序执行把处理机分配给该进程的操作。进 程调度是最基本的调度，任何操作系统都有进程调度。 3.中级调度——对换
作业 调度 后备队列
时间片完 就绪队列
进程调度 进程完成 CPU
事件1出现
等待事件1
事件2出现
等待事件2
… … … …
事件n出现
等待事件 n
具有高、低两级调度的调度队列模型
15
3.同时具有三级调度的调度队列模型
作业调度
时间片完
第3章-处理机调度与死锁

第3章-处理机调度与死锁

S2 就绪队列 2
S3 就绪队列 3
就绪队列 n
(时 间片 ： S1＜S2＜S3)
20
第三章 调度与死锁
最短剩余时间
21
第三章 调度与死锁
3.3.2 高优先权优先调度算法
适合于作业调 度和进程调度
1. 优先权调度算法旳类型 1)非抢占式优先权算法（用于批处理、要求不严旳实时）
系统一旦把处理机分配给就绪队列中优先权最高旳进 程后，该进程便一直执行下去，直至完毕；或因发生某事 件使该进程放弃处理机时，系统方可再将处理机重新分配 给另一优先权最高旳进程。
1 1.17
2.25
18 12 2.4
20 12 6
8. 60 2.56
• 完 周转 带权周转 毕 时间 时间
3时 3
1
9间 7
1.17
15 11 2.75
20 14 2.8
11 3
1.5
7.60 1.84
例1 FCFS和SJF调度算法旳性能比 较
第三章 调度与死锁
例2. FCFS和SJF调度算法旳性能比较
31
第三章 调度与死锁
(2) 时间片大小旳拟定
退化成
• 时间片太大
FCFS算法
• 时间片过小切换开销大。
时间片大小拟定要考虑旳原因： (1) 系统对响应时间旳要求。（顾客数一定时，成正比）
(2)就绪队列中旳进程数目。（确保响应时间，成反比）
(3)系统旳处理能力。（确保顾客键入旳命令能在一种时 间片内处理完毕）
优点:简朴、系统开销小，合用于大多数批处理系统环境。 缺陷：难以满足紧急任务旳要求——立即执行，在要求比较 严格旳实时系统中，不宜采用这种调度方式。
3
第三章 调度与死锁
计算机操作系统第三章处理机调度与死锁 ppt课件

计算机操作系统第三章处理机调度与死锁 ppt课件


2决定接纳哪些作业
选用何种调度算法：先来先服务、 短作业优先、基于作业优先级、响 应比高者优先。
PPT课件
6
注意
批处理系统中，作业是首先进入外存， 然后经由作业调度分批进入内存；
分时系统及实时系统中，由于对响应 时间有要求，因此用户输入的命令和数据 等是直接进入内存的，无须配置作业调度 机制。
PPT课件
PPT课件
14
同时具有三级调度的调度队列模型
作业 调度
后备队列
中级 调度
时间片完 就绪队列 就绪、挂起队列
进程调度
进程完成
CPU
挂起
事件出现
事件发生
阻塞、挂起队列 阻塞队列
挂起 等待事件
具有高、低、中三级调度的调度队列模型
PPT课件
15
选择调度方式和调度算法的若干准则
• 面向用户的准则
– 周转时间短（批处理） – 响应时间快（分时） – 截止时间保证（实时） – 优先权准则（all）
4
2 作业控制块
多道批处理系统中，为每个作业配备一个作业 控制块（JCB），它是作业在系统中存在的标志。
作业运行期间，系Biblioteka 按照JCB中的信息对作业进行 控制。
JCB中保存了系统对作业进行管理和调度所需 的全部信息。例如：作业标识、用户名称、用户帐 户、作业类型、作业状态、调度信息、资源需求、 进入系统时间、开始处理时间、作业完成时间、作 业退出时间、资源使用情况等。
第三章 处理机调度与死锁
要解决的三个问题：
WHAT：按什么原则分配CPU？ —进程调度算法
WHEN：何时分配CPU？ —进程调度的时机
HOW： 如何分配CPU？ —CPU调度过程（进程的上下文切换）
操作系统 第3章死锁

操作系统 第3章死锁


北京林业大学信息学院
R
R
P1
P2 (a)
P3
P4
பைடு நூலகம்
P1
P2 (b)
P3
存储器共享的死锁
北京林业大学信息学院
死锁的例子（3）
对临时性资源使用不加限制引起死锁
资源的类型： 永久性资源：可供进程逐次再使用的资源； 临时性资源(消耗性资源)：由一进程产生而被另一进 程消耗掉，只能使用短暂的时间。
产生和发送
北京林业大学信息学院
死锁模型

a占有，b请求，c死锁
北京林业大学信息学院
死锁检测

发现环，每种类型一个资源的情况
北京林业大学信息学院
死锁检测

每种类型多个资源的情况（资源公式）
北京林业大学信息学院
死锁检测


标记的方式，起初进程都没有标记 死锁检测算法：


寻找一个没有被标记的进程P，对于他而言 R向量的第i行，小于等于A。 如果找到这样一个进程，那么将C向量的第i 行全部加到A中，标记改进程，并转到步骤 1. 如果没有这样的进程则算法终止
Pa
S资源表示消息或信件 对信件的接收和发送不加限制
请求接收
Sc
Pc Sb
Sa
Pb
cobegin Pa; Pb; Pc; coend
北京林业大学信息学院
1、死锁概念
如果在一个进程集合中的每个进程都在等待 只能由该集合中的其他一个进程才能引发的事 件，则称这一组进程或系统此时发生了死锁。
一组进程中，每个进程都在无限等待被该 组进程中另一个进程所占有的永远不会释放的 资源，这种现象称系统处于死锁状态，简称死 锁。处于死锁状态的进程就称为死锁进程.
《操作系统》第三章 - 死 锁

《操作系统》第三章 - 死 锁


令n表示系统中进程的数目，m表示资源分类数。
可以把矩阵Allocation和Need中的每一行当做一个 向量，并分别写成Allocationi和Needi。Allocationi表 示当前分给进程pi的资源。
1．资源分配算法 • 令Requesti表示进程pi的申请向量。Requesti[j]= k，表示进 程pi需要申请k个rj类资源。当进程pi申请资源时，就执行下列 动作： ① 若Requesti＞Needi，表示出错， ② 如果Requesti＞Available，则pi等待。 ③ 假设系统把申请的资源分给进程pi，则应对有关数据结构进 行修改： Available：= Available – Requesti Allocationi：= Allocationi + Requesti Needi：= Needi – Requesti ④ 系统执行安全性算法，查看此时系统状态是否安全。如果是 安全的，就实际分配资源，满足进程pi 的此次申请；否则， 若新状态是不安全的，则pi等待，对所申请资源暂不予分配， 并且把资源分配状态恢复成③之前的情况。
第3章 死
内容提要： 3.1 3.2 3.3 3.4 3.5 3.6
锁
资 源 死锁概念 死锁的预防 死锁的避免 死锁的检测和恢复 处理死锁的综合方式
3.1 资
源
3.1.1 资源使用模式
1．申请 2．使用 3．释放
3.1.2 可剥夺资源与不可剥夺资源
1．可剥夺资源 • 另外进程可以从拥有它的进程那里把它剥 夺过去为己所用，并且不会产生任何不良 影响。例如，内存就是可剥夺资源。 2．不可剥夺资源 • 不能从当前占有它的进程那里强行抢占的 资源，必须由拥有者自动释放，否则会引 起相关计算的失效。
第三章 处理机调度与死锁

第三章 处理机调度与死锁


(1)给出FCFS , SJF下的作业执行次序 (2)给出FCFS , SJF下的作业平均周转时间和带权平均 周转时间
22
作业 JOB1 JOB2 JOB3 JOB4
进入时间 8:00 8:50 9:00 9:50
估计运行时间 （分钟） 120 50 10 20
SJF 完成时 刻 10:00 11:20 10:10 10:30
8.00 8.00 10.00 10.30 10.50 10.00 10.60 10.10
10.00 10.00 10.50 10.80 10.60 10.10 10.80 10.30
2.00 2.00 2.00 2.30 1.60 1.10 1.30 0.80
1 1 4 4.6 16 11 6.5 4
10.00 10.60 10.10 10.80
2.00 2.10 1.10 1.30
1 4.2 11 6.5
1 3 2 4
高响应比优先调度算法
平均周转时间 平均带权周转时间 t = 1.625 w =5.675
30
3. 高响应比优先调度算法
(1) 如果作业的等待时间相同，则要求服务的时间 愈短，其优先权愈高，因而该算法有利于短作业。 (2) 当要求服务的时间相同时，作业的优先权决定 于其等待时间，等待时间愈长，其优先权愈高，因而它 实现的是先来先服务。 (3) 对于长作业，作业的优先级可以随等待时间的 增加而提高，当其等待时间足够长时，其优先级便可升 到很高， 从而也可获得处理机。 缺点：每次调度前都要计算响应比，增加了系统开销。 31
FCFS 完成时 刻 10:00 10:50 11:00 11:20
23
FCFS : T= ( 120+120+120+90 ) / 4 = 112.5 SJF: T=（120+150+70+40）/4 = 95 FCFS： W=（120/120 + 120/50 +120/10 +90/20）/4=4.975 SJF: W=（120/120 + 150/50 + 70/10 +40/20） /4=3.25
计算机操作系统 处理机调度与死锁

计算机操作系统 处理机调度与死锁


2. 多级反馈队列调度算法
多个就绪队列，各个队列赋予不同的优先级。 第一个队列的优先级最 高，第二个队列次之，其余各队列的优先权逐个降低。
各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列 中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时 间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要 比第i个队列的时间片长一倍。
程序等。
进程的执行是在其上下文中执行。当正在执行的进程由于某种原因要让出处 理机时，系统要做进程上下文切换，以使另一个进程得以执行。
当进行上下文切换时，系统要: • 首先检查是否允许做上下文切换(优先级 ); • 保留被切换进程的当前信息(现场)，以便返回该进程时，从断点恢复该进
程的执行。
系统保留了CPU现场之后，调度程序选择一个新的处于就绪状态的进程，并 装配(布置)该进程的上下文(现场) ，使CPU的控制权转换到被选中进程中。
进程上下文切换 进程上下文由正文段、数据段、硬件寄存器的内容以及有关数 据结构等组成。 硬件寄存器主要包括存放CPU将要执行的下条指令虚拟地址的 程序计数器PC。 指出机器与进程相关联的硬件状态的处理机状态寄存器PS。 存放过程调用（或系统调用）时所传递参数的通用寄存器R以及 堆栈指针寄存器S等。
作业调度
交换调度
进程调度
线程调度 作业调度
3.1 处理机调度的基本概念
3.1.1 高级、中级和低级调度
1. 高级调度(High Scheduling) ，即作业调度 在每次执行作业调度时，须做出以下两个决定
1) 接纳多少个作业
2) 接纳哪些作业
调度目标： (1) 对所有作业应该是公平合理的； (2) 应使设备有高的利用率； (3) 单位时间内执行尽可能多的作业； (4) 有快的响应时间。
第三章 处理机调度与死锁

第三章 处理机调度与死锁


(2) 进程对资源的需求。对资源需求少的进程应赋予较
高优先权。
(3) 用户要求。
第三章 处理机调度与死锁
2) 动态优先权
•在创建进程时所赋予的优先权，可以随进程的推进或随其等
待时间的增加而改变，以便获得更好的调度性能。 •在就绪队列中的进程，随其等待时间的增长，其优先权以速 率a提高。 •当采用抢占式优先权调度算法时，如果再规定当前进程的优 先权以速率b下降，则可防止一个长作业长期地垄断处理机。
第三章 处理机调度与死锁
第三章 处理机调度与死锁
第三章 处理机调度与死锁
• 为提高处理机利用率、改善系统性能 （吞吐量、周转时间和响应时间）需对 处理机进行合理分配调度 • 处理机调度的目的：分配处理机
第三章 处理机调度与死锁
3.1 处理机调度的层次
– 高级、中级和低级调度 – 每一级调度，采用不同的调度方式和调 度算法
试给出在下面两种调度算法下，作业的执行顺序、平均周 转时间和带权周转时间。
（1）先来先服务FCFS调度算法；
（2）短作业优先SJF调度算法。
第三章 处理机调度与死锁
（1）采用FCFS调度算法时，作业的执行顺序是作业1、作
业2、作业3。由此可得到运行表见下。
平均周转时间为： T=(∑Ti)/3=[2+2.83+2.83]/3=2.55h 带权平均周转时间： W=[∑(Ti/Tir)]/3=（2/2+2.83/1+2.83/0.25）/3=5.05h
1 n 可把平均周转时间描述为： T Ti n i 1
第三章 处理机调度与死锁
作业的周转时间T与系统为它提供服务的时间TS 之比，即
W=T/TS，称为带权周转时间，而平均带权周转时间则可表 示为:
计算机操作系统(第四版)第三章死锁

计算机操作系统(第四版)第三章死锁


23
例题：假定系统中有五个进程{P0、P1、P2、 P3、P4}和三种类型的资源{A，B，C}，每一 种资源的数量分别为10、5、7，在T0时刻的 资源分配情况如图
资源情况 进程
Max Need Allocation A B C A B C A B C
Available A B C
P0
7
3 9 2 4
16
3. 防止“环路等待”条件的出现(层次分配策略)
这种方法的基本思想是：资源被分成多个层次,一个进程 得到某一层的一个资源后,它只能再申请较高一层的资源;当一 个进程要释放某层的一个资源时,必须先释放所占用的较高层 的资源;当一个进程获得了某一层的一个资源后,它想再申请该 层中的另一个资源,就必须先释放该层中的已占用资源.
根据使用方式：共享资源和独享资源(即非临界资源与临界资源) 。
根据使用期限: 永久资源和临时性资源。
3
CPU、主存、硬盘，该类资源可为几个进程 共同使用（可抢占）
资源 打印机，读卡机，磁带机，可为某个进程独 享（不可抢占）
根据使用方式：共享资源和独享资源。 根据使用期限；永久资源和临时性资源。
可重复使用的资源,如：内存、 外部设备、数据文件、表格等
6
我们先来看一个申请不同类型资源的死锁例子： 假定有两个进程Pl和P2，设F和T都是可重用资源。于是 Pl和P2可有如下形式：
图 简单的死锁例子
7
三、产生死锁的原因
1 竞争资源 当系统中供多个进程所共享的资源，不足 以同时满足它们的需要时，引起它们对资源的竞争 而产生死锁； 答：不可能。因为死锁产生的原因有两点：系统资源不足或推进 2 进程推进的顺序不当 进程在运行过程中，请求和 顺序不当，在本题中，进程所需的最大资源数为 60，而系统共有 释放资源的顺序不当，导致进程的死锁。 该类资源 65个，其资源数已足够系统内各进程使用。 例题： 一个OS有20个进程，竞争使用65个同类资源， 申请方式是逐个进行的，一旦某个进程获得它所需 要的全部资源，则立即归还所有资源。每个进程最 多使用三个资源。若仅考虑这类资源，该系统有无 可能产生死锁，为什么？
第3章 死锁

第3章 死锁

9
3.关于死锁的一些结论 • 参与死锁的进程最少是两个； • 参与死锁的进程至少有两个已经占有资源； • 参与死锁的所有进程都在等待资源； • 参与死锁的进程是当前系统中所有进程的子 集； 注：如果死锁发生，会浪费大量系统资源，甚 至导致系统崩溃。
4.永久性资源和临时性资源 永久性资源：可以被多个进程多次使用（可 再用资源）： 可抢占资源 不可抢占资源 临时性资源：只可使用一次的资源；如信号 量,中断信号，同步信号等（可消耗性资源） “申请--分配--使用--释放”模式
22
1)资源一次性分配； 在作业调度时，为选中的作业分配它所需要 的所有资源。当这些资源分配给该作业后，在其 整个运行期间为它独占(静态分配)。 讨论： (1)这种方法破坏了死锁的必要条件中的哪一条？ (破坏请求和保持条件) (2)这种方法的资源利用率高不高？为什么？ 问题： • 降低了设备的利用率 (只用很短的时间，或根本用不到) • 造成不必要的等待 • 用户提不出所需的全部资源 ★
2) 安全状态之例
我们通过一个例子来说明安全性。假定系统中有三
个进程P1 、 P2 和P3 ，共有12台磁带机。进程P1 总共要
求10台磁带机，P2和P3分别要求4台和9台。假设在T0时
刻，进程P1 、P2 和P3 已分别获得5台、2台和2台磁带机，
尚有3台空闲未分配，如下表所示：
进程
最大需求
已分配
2.银行家算法 基本思想：当系统现有的资源可保证申请进程 完成时，才进行分配。否则，申请进程等待。
系统现有的资源 Pi： 进程占有的资源 进程还需要的资源
不
进
行
分
配
系统现有的资源 Pj： 进程占有的资源 ★ 进程还需要的资源
进

计算机操作系统(第四版)第3章 处理机调度与死锁

第三章处理机调度与死锁31处3.1处理机调度的层次和调度算法的目标32理机调3.2作业与调度算法3.3进程调度度与3.4 实时调度死锁3.5 死锁概述3.6 预防死锁3.7避免死锁383.8死锁的检测与解除3.13.1处理机调度的层次处311P85理机调 3.1.1 高级调度312度与 3.1.2 低级调度313死锁 3.1.3中级调度❑高级调度(High-Level Scheduling)又称作业调度，决定后备作业中谁调入内存运行处❑低级调度(Low-Level Scheduling)理机调又称进程调度，决定就绪队列中哪个进程获得度与CPU ；死锁❑中级调度(Intermediate-Level Scheduling)又称在虚拟存储器中引入，在内、外存对换区进行进程对换行进程对换。

高级调度(High Level Scheduling)又称作业调度或长程调度处 功能：按照一定的算法，从外存的后备队列中选取某些并为它们创建进程理机调作业调入内存，并为它们创建进程、分配资源，再将进程插入就绪队列，准备执行。

度与死锁 作业和作业步作业控制块 作业调度作业和作业步(1)作业(Job)比程序更为广的概念含：程序+数据+作业说明书处比程序更为广的概念，含：程序+数据+作业说明书根据说明书，对程序进行控制。

批处理系统中，以作业为基本单位从外存调入内存理机调作业为基本单位从外存调入内存。

(2)作业步(Job Step)，Demo run作的行过若个相独立相关联的序加步度与作业的运行经过若干个相对独立、又相互关联的顺序加工步骤，每个加工步骤称为一个作业步。

“编译”作业步，死锁例如，典型的作业可分成三个作业步：①编译作业步，②“连结装配”作业步；③“运行”作业步(3)作业流()作流若干个作业进入系统后，依次存放，形成输入的作业流；在操作系统的控制下，逐个作业进行处理，形成处理作业流。

事物都需操控指挥中心事物都需操控、指挥中心，so is the 作业处理机调度与死锁为管理和调度作业，多道批处理系统为每个作业设置个作业控制块是作业在系统中处置一个作业控制块JCB，JCB是作业在系统中存在的标志，保存系统对作业进行管理和调度所需的全部信息理机调信息。

操作系统第三章调度与死锁


§3.2 调度算法 （七）
六、多级队列调度
根据作业性质不同分为若干个就绪队列， 如：系统进程队列，交互进程队列，批处理队 列等。对各队列采用不同的调度算法。
§3.2 调度算法 （八）
七、多级反馈队列
亦称多级反馈轮转法（Round Robin with Multiple Feedback）
实现基本思想：
Block）描述。 • 线程是进程内一个可调度的实体。具有独立的程序计数
器。
TCB
主线程 输入线程 计算线程 输出线程
§3.5 线程的基本概念 （二）
CPU 状态 堆栈
程序计数器
. ..
寄存器
PCB
图1
进程标识 资源清单
. ..
TCB
线程1的TCB 线程2的TCB 线程3的TCB
主线程
创建线程 1 。。。 创建线程 n
在进程运行过程中，优先级会有不同幅度（0 –6）的提 升，使进程获得调度的可能性。 优先级提升幅度的原则：
随着进程等待时间增加，优先级提升幅度增加。 因进程类型而定；受 I/O 限制的进程提升幅度大于受 计算限制的进程。
进程优先级下降 ：当进程因为时间片到或者等待某事 件发生而释放CPU时，优先级下降。
对最短CPU运行期的估算，依赖于系统的下一个CPU周
期中，实现较困难。进程的CPU时间
n+1
tn
n的+1 估算公式： n
其中 n 为估计的第n个CPU 周期。tn 为实际值。
为控制值，0≤ ≤1，常取 0.5 该算法优于FCFS，但长进程等待时间长，估算误差较大。
§3.2 调度算法 （三）
三、 最高优先权（HPF）算法
思考题 1、各种调度算法的特点、性能如何？适宜于 哪类 OS？

16第3章(下)-死锁

3)不可抢占 4)环路等待
第二种协议:允许进程仅当自己未占用资源时才请求资源。 在一个进程申请任何另外资源前，必须释放当前它占用的所 有的资源。 初始数据 数据排序 磁盘文件 2）释放 磁带机+磁盘文件 已排序数据 打印机 3）再申请 磁盘文件+打印机
磁带机
1）申请 磁带机+磁盘文件
4)环路等待
层次分配策略的思想 1)首先将资源分成多个层次 2)一进程得到某层次的资源后 资源R=(R1,R2,„.Rm)
Work:=Available:=[2,3,0]
资源情况 Max A，B，C 进 程 P0 P1 P2 P3 P4 7,5,3 3,2,2 9,0,2 2,2,2 4,3,3 0,1,0 3,0,2 3,0,2 2,1,1 0,0,2 7,4,3 0,2,0 6,0,0 0,1,1 4,3,1 2,3,0 10,5,7 5,3,2 10,4,7 7,4,3 7,4,5 Allocation A，B，C Need A，B，C Available A，B，C
7,5,3
3,2,2 9,0,2 2,2,2 4,3,3
0,1,0
3,0,2 3,0,2 2,1,1 0,0,2
7,4,3
0,2,0 6,0,0 0,1,1 4,3,1
2,3,0
合理性检查
1)Request4(3,3,0)<=Need(4,3,1) 2)Request1(3,3,0)>Available(2,3,0),让P4等待
Work+Alloc ation
存在安全序列：P1，P3，P4，P2，P0
满足P1请求
分配前安全序列1：P1，P3，P4，P2，P0
P4请求Request(3,3,0)
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
➢ 不安全状态一定导致死锁
24
3.安全序列 ➢ 一个进程序列{P1，…，Pn}是安全的
如果对于每一个进程Pi(1≤i≤n），它以 后尚需要的资源量不超过系统当前剩余资源量 与所有进程Pj (j < i )当前占有资源量之和， 系统处于安全状态 ➢ 安全状态一定是没有死锁发生的
25
安全状态之例
➢ 假定有3个进程P1、P2和P3，12台磁带机 ➢ 系统在T0时刻的状态如下表所示
18
3.破坏环路等待条件 ➢ 方法：将所有资源按类型线性编号
按序号递增的次序请求资源 按序号递减的次序释放资源 优点：资源利用率和系统吞吐量提高 缺点：限制了新设备类型的增加 申请的资源闲置造成浪费 限制用户简单、自主地编程
19
4.互斥条件不仅不应破坏还要保持 因为资源的互斥使用是由资源本身的属
V--结点集，分为P，R两部分 P={p1,p2,…,pn}, R={r1,r2,…,rm}
E--边的集合，其元素为有序二元组 <pi,rj>或<rj,pi>
4
➢ 资源分配图(RAG)的表示 ✓ 资源类:用方框表示 ✓ 资源实例:用方框中的黑圆点表示 ✓ 进程 :用圆圈中加进程名表示 ✓ 分配边：资源实例进程 ✓ 申请边：进程资源类
进程 P1 P2 P3
最大 需求
10 4 9
已分 配
5 2 2
可用 3
26
由安全状态向不安全状态的转换
➢ 如果不按照安全序分配资源，则系统可能会由安全 状态进入不安全状态
➢ T0时刻以后，P3又请求1台磁带机，若把剩余3台中
的1台分配给P3，则系统便进入不安全状态 ➢ 若把其余的2台分配给P2，这样，在P2完成后只能释 放出4台，既不能满足P1尚需5台的要求，也不能满足 P3尚需6台的要求，致使它们都无法推序设计
第8节 死锁
主讲教师：林韩辉
内容提要
死锁的原因和必要条件 预防死锁 发现死锁 解除死锁
2
一、死锁的基本概念
1.资源分配图
➢ 资源类和资源实例 ✓ 系统中的一类资源称为一个资源类 ✓ 每个资源类中的一个资源称为一个资源实例
3
➢ 资源分配图(RAG)的定义 RAG=（V,E）
14
处理死锁的基本方法
1.预防死锁
➢ 通过破坏产生死锁的四个必要条件的一个或几个
防止死锁的发生
➢ 施加的限制条件可能导致系统资源利用率和
系统吞吐量的降低
2.避免死锁
➢ 在资源的动态分配过程中，防止系统进入不安全
状态，从而避免死锁的发生
➢ 限制条件较弱，系统资源利用率和系统吞吐量较高，
但实现比较困难
性决定的，不能够改变资源属性就应该按照要 求使用资源
20
（二） 安全状态与不安全状态 1.死锁的避免
➢ 死锁预防策略所施加的限制条件严重地损害 了系统性能
➢ 要施加较弱的限制条件，通过避免系统进入 不安全状态来避免死锁，从而获得较满意的系 统性能
21
➢ 死锁避免的策略允许进程动态地申请资源 ➢ 资源分配前先计算资源分配的安全性： ✓ 若此次分配不会导致系统进入不安全状态，
则将资源分配给进程 否则，进程等待 ✓ 最具有代表性的死锁避免算法是银行家 算法
22
2.安全状态与不安全状态 ➢ 安全状态
指系统能按某种进程顺序来为每个进程 分配其所需资源，直至最大需求，使每个进程 都可顺序完成
➢ 不安全状态 若系统不存在一个安全序列，则称系统
处于不安全状态
23
安全状态与不安全状态
7
竞争系统资源 ➢ 系统资源类型
✓ 永久性资源（可再用资源）
可抢占资源：例 内存、CPU、磁盘 不可抢占资源：例 打印机、磁带机 ✓ 临时性资源（可消耗性资源） 只可使用一次的资源 例：信号量、中断信号、同步信号等
8
P1
R1
R2
P2
I/O设备共享时的死锁情况
P1
S3
S1
P3
P2
S2
图 3-13 进程之间通信时的死锁
4.产生死锁的必要条件
1.互斥条件
进程对占有的资源进行排他性使用
2.请求和保持条件
部分分配策略中，进程占有资源却又申请新的资源
3.不剥夺条件
对已经分配给进程的资源不可强占使用
4.环路等待条件
发生死锁时，系统的RAG必然出现环路
13
➢ 说明
✓ 发生死锁时，四个必要条件一定同时具备 ✓ 具备四个必要条件未必发生死锁 ✓ 各条件之间是有联系的
5
2.死锁的定义
➢ 指多个进程因竞争共享资源而造成的一种僵 局，若无外力作用，这些进程都将永远不能 再向前推进
➢ 即：一组进程中，每个进程都无限等待被该 组进程中另一进程所占有的资源，因而永远 无法得到的资源，这种现象称为进程死锁， 这一组进程就称为死锁进程
6
3.产生死锁的原因
竞争系统资源(系统提供的资源不能 满足每个进程的使用) ➢ 竞争永久资源 ➢ 竞争临时资源 进程的推进顺序不当（多道）
通过破坏死锁的四个必要条件之一预防死锁 1.破坏请求和保持条件(资源独占)
方法：资源一次性分配 优点：简单、安全 缺点：资源浪费严重
进程延迟运行
17
2.破坏不剥夺条件（资源受控动态分配） 方法：已保持资源的进程提出新的资源请求 而未能满足时，必须释放占有的资源 缺点：造成资源使用的不连续 造成进程的“饿死”状态 延长进程的周转时间
➢ 可导致死锁的因素（资源方面） ✓ 竞争不可抢占的永久资源 ✓ 竞争临时性资源
➢ 竞争可抢占资源不会导致死锁
进程推进顺序不当引起死锁
P2Rel(R1) P2Rel(R2) P2Req(R1)
P2Req(R2)
②
D ④
① ③
P1Req(R1)
P1Req(R2) P1Rel(R1) P1Rel(R2)
15
3.检测死锁
➢ 不采用任何限制条件，允许发生死锁 ➢ 死锁检测机构能够快速检测死锁的存在 ➢ 检测遵循死锁定理
4.解除死锁
➢ 与死锁检测相配套的一种措施 ➢ 一旦检测到死锁的存在，通过手段解除死锁 ➢ 保证系统有好的资源利用率和系统吞吐量 ➢ 实现难度比较大
16
二、 死锁的预防和避免
(一） 死锁的预防
27
例子：利用银行家算法避免死锁
1.银行家算法中的数据结构 ➢ 可用资源向量Available[m] ✓ 每一个元素代表一类可利用的资源数目 ✓ 初始值是系统中所配置的各类全部可用资源 ✓ 的数目 ✓ 其值随资源的分配和回收而动态地改变 ✓ Available[j]=K：表示有Rj类资源K个