当前位置：文档之家 › 第6章 死锁(完整)

第6章 死锁(完整)

  • 格式：pdf
  • 大小：2.42 MB
  • 文档页数：30

下载文档原格式

  / 30

合集下载

《操作系统》习题集：第6章 死锁

《操作系统》习题集：第6章 死锁

第6章死锁-习题集一、选择题1.在操作系统中，死锁出现是指（）。

【＊，★，联考】A. 计算机系统发生重大故障B. 资源个数远远小于进程数C. 若干进程因竞争资源而无限等待其他进程释放已占有的资源D. 进程同时申请的资源数超过资源总数2.在（）的情况下，系统出现死锁。

【＊，联考】A. 计算机系统发生了重大故障B. 有多个封锁的进程同时存在C. 若干进程因竞争资源而无休止地相互等待他方释放已占有的资源D. 资源数远远小于进程数或进程同时申请的资源数远远超过资源总数3.当出现（）情况下，系统可能出现死锁。

【＊，联考】A. 进程释放资源B. 一个进程进入死循环C. 多个进程竞争资源出现了循环等待D. 多个进程竞争共享型设备4.为多道程序提供的可共享资源不足时，可能出现死锁。

但是，不适当的（）也可能产生死锁。

【＊＊，联考】A. 进程优先级B. 资源线性分配C. 进程推进顺序D. 分配队列优先权5.采用资源剥夺法可以解除死锁，还可以采用（）方法解除死锁。

【＊，★，联考】A. 执行并行操作B. 撤销进程C. 拒绝分配新资源D. 修改信号量6.死锁产生的原因之一是（）。

【＊，联考】A. 系统中没有采用SPOOLing技术B. 使用的P、V操作过多C. 有共享资源存在D. 资源分配不当7.产生死锁的4个必要条件是：互斥、（）、循环等待和不剥夺。

【＊，联考，？】A. 请求与阻塞B. 请求与保持C. 请求与释放D. 释放与阻塞8.一个进程在获得资源后，只能在使用完资源后由自己释放，这属于死锁必要条件的（）。

【＊，联考】A. 互斥条件B. 请求和释放条件C. 不剥夺条件D. 环路等待条件9.死锁的预防是根据（）而采取措施实现的。

【＊，★，联考】A. 配置足够的系统资源B. 使进程的推进顺序合理C. 破坏死锁的四个必要条件之一D. 防止系统进入不安全状态10.资源的有序分配策略可以破坏死锁的（）条件。

【＊＊，★，联考】A. 互斥B. 请求和保持C. 不剥夺D. 循环等待11.发生死锁的必要条件有4个，要防止死锁的发生，可以通过破坏这4个必要条件之一来实现，但破坏（）条件是不太实际的。

第六章死锁

第六章死锁
• 环境:某些资源互斥地使用。 • 原因:(1)系统资源不足；
(2)进程推进的顺序不合适。
6.1死锁问题的提出
6.2 死锁的必要条件
• 资源的概念 – 分配方式: “可抢占”资源, “不可抢占”资源 – 使用方式: “共享”资源, “独占”资源 – 使用期限: 永久资源, 临时资源 – 资源的共同性质:一个进程由于请求一个资 源而未被满足,从而该进程被阻塞.
• 预先静态分配法(破坏部分分配条件) 作业调度时,仅当系统满足作业运行时所需的 全部资源时,才把该作业调入内存运行.在作 业运行前一次性将其所需的全部资源分配给 它,于是在作业运行过程中不再会提出新的资 源请求.
6.3 死锁的预防
• 有序资源使用法: (破坏循环等待条件) 策略: 把系统中的全部资源分别分给一个
已占 还申
P
5
Q
2
3 或5 3或4 4
1
21 21
R
3
6
36 45
然而将2个资源分给Q (只需一个)则
P44 Q 3 0 Q可运行结
束、释放
R27
P44
系统资源回 收为4个
R27
此后可将4个资源分组P…
即
QPR
银行家算法
由此可见，按银行家算法来分配资源是不会产生 死锁的。因为按该算法分配资源时，每次分配后总存 在一个进程，如果让它独立单独运行下去，必然可获 得它所需的全部资源，也就是说它能结束。而它结束 后可以归还这类资源来满足其它申请者的需要。这也 说明了存在一个合理的系统状态序列，可确保系统不 会进入死锁状态的路径。
有若干种资源中的某一种,同时每个进程还要求 (链上)下一进程所占有的资源.
6.3防止死锁发生(破坏条件之一)

第5章操作系统习题(死锁)

第5章操作系统习题(死锁)

一、选择题1、在为多道程序所提供的可共享的系统资源不足时，可能出现死锁。

但是，不适当的也可能产生死锁。

A、进程优先权B、资源的线性分配C、进程推进顺序D、分配队列优先权2、采用资源剥夺法可解除死锁，还可以采用方法解除死锁。

A、执行并行操作B、撤消进程C、拒绝分配资源D、修改信号量3、产生死锁的四个必要条件是：互斥、、环路条件与不剥夺。

A、请求与阻塞B、请求与保持C、请求与释放D、释放与阻塞4、在分时操作系统中，进程调度经常采用算法。

A、先来先服务B、最高优先权C、时间片轮转D、随机5、资源的按序分配策略可以破坏条件。

A、互斥使用资源B、占有且等待资源C、非抢夺资源D、循环等待资源6、在的情况下，系统出现死锁。

A、计算机系统发生了重大故障。

B、有多个封锁的进程同进存在。

C、若干进程因竞争资源而无休止地相互等待他方释放已占有的资源。

D、资源数目大大小于进程数或进程同时申请的资源数大大超过资源总数。

7、优先权是在创建进程时确定的，确定之后在整个进程运行期间不再改变。

A、先来先服务B、静态C、动态D、短作业8、当进程数大于资源数时，进程竞争资源会产生死锁。

A、一定B、不一定9、检测出发生死锁时，可以通过撤消一个进程解除死锁。

上述描述是。

A、正确的B、错误的10、在下列解决死锁的方法中，属于死锁预防策略的是。

A、银行家算法B、资源有序分配方法C、死锁检测法D、资源分配图化简法12、以下叙述中正确的是。

A、调度原语主要是按照一定的算法，从阻塞队列中选择一个进程，将处理机分配给它。

B、预防死锁的发生可以通过破坏产生死锁的四个必要条件之一来实现，但破坏互斥条件的可能性不大。

C、进程进入临界区时要执行开锁原语。

D、既考虑作业等待时间，又考虑作业执行时间的调度算法是先来先服务算法。

二、填空题1、进程的调度方式有两种，一种是，另一种是。

2、死锁是指在系统中的多个无限期地等待永远不会发生的条件。

3、一种最常用的进程调度算法是把处理机分配给具有最高优先权的进程。

计算机操作系统(第四版)1-8章-课后答案(全)

计算机操作系统(第四版)1-8章-课后答案(全)

计算机操作系统(第四版)1-8章-课后答案(全)第四版计算机操作系统课后答案第一章1. 操作系统的定义操作系统是一种软件，它管理着计算机系统的硬件和软件资源，并为用户和应用程序提供接口，以方便他们的使用。

2. 操作系统的功能操作系统具有以下功能：- 进程管理：负责创建、执行和终止进程，并管理它们的资源分配。

- 存储管理：管理计算机系统的内存资源，包括内存分配、虚拟内存和页面置换等。

- 文件系统管理：管理计算机系统中的文件和文件夹，包括文件的存储、读写和保护等。

- 设备管理：负责管理计算机系统中的各种设备，如打印机、键盘和鼠标等。

- 用户接口：提供用户与计算机系统进行交互的接口，如命令行界面和图形用户界面。

3. 操作系统的类型操作系统可以分为以下类型：- 批处理操作系统：按照一系列预先定义的指令集来运行任务。

- 分时操作系统：多个用户可以同时使用计算机系统。

- 实时操作系统：对任务的响应时间要求非常高，用于控制系统和嵌入式系统。

- 网络操作系统：支持多台计算机之间的通信和资源共享。

- 分布式操作系统：在多台计算机上分布式地管理和调度任务。

第二章1. 进程与线程的区别进程是计算机系统中正在运行的程序实例，而线程是进程内的一个执行单元。

进程拥有独立的地址空间和资源，而线程共享进程的地址空间和资源。

多个线程可以在同一进程内并发执行，从而提高系统的效率和资源利用率。

2. 进程的状态转换进程可以处于以下状态：- 创建状态：进程正在被创建。

- 就绪状态：进程准备好执行，等待分配CPU资源。

- 运行状态：进程占用CPU资源执行。

- 阻塞状态：进程等待某种事件发生。

- 终止状态：进程完成执行或被终止。

3. 进程调度算法操作系统使用进程调度算法来决定哪个进程应该被执行。

常见的调度算法有：- 先来先服务（FCFS）调度算法：按照进程到达的顺序进行调度。

- 最短作业优先（SJF）调度算法：选择运行时间最短的进程进行调度。

操作系统复习题 (4)

操作系统复习题 (4)

第一章引论（１０、１３、２１无答案）2、什么是多道程序设计？14、陷阱和中断的主要差别是什么？20、有一文件，其文件描述符是fd，内含下列字节序列：3，1，4，5，9，2，6，5，3，5。

做如下系统调用：lseek(fd,3,SEEK_SET);read(fd,&buffer,4);其中lseek调用寻找文件中的字节3。

在操作完成之后，buffer中的内容是什么？21、块特殊文件和字符特殊文件的基本差别是什么？26、下面是单位转换的练习：a）一微年是多少秒？b）微年常称为micron，那么gigamicron是多长？c）1TB存储器中有多少字节？d）地球的质量是6000yottagram，换算成kilogram是多少？第二章进程与线程（５、１４无答案）1、图2-2中给出了三个进程状态。

理论上，三个状态可以有六种转换，每个状态两个。

但是，图中只给出了四种转换。

有没有可能发生其他两种转换中的一个或两个？11、在本习题中，要求对使用单线程文件服务器和多线程文件服务器读取文件进行比较。

假设所需要的数据都在块高速缓存中，花费15ms获得工作请求，分派工作，并进行处理其余必要工作。

如果在三分之一时间时，需要一个磁盘操作，要另外花费75ms，此时该线程进入休眠。

在单线程情形下服务器可以处理每秒钟多少个请求？如果是多线程呢？20、两个进程在一个共享储存器多处理机（即两个CPUI）上运行，当它们要共享一个公共内存时，图2-20所示的采用变量turn的忙等待解决方案还有效吗？30、假设有一个使用信箱的消息传递系统，当向满信箱发送信息或从空信箱接收信息时，进程都不会阻塞，相反，会得到一个错误代码。

进程响应错误代码的处理方法为一遍一遍地重试，直到成功为止。

这种方式会导致竞争条件吗？40、有5个批处理作业A到E，它们几乎同时到达一个计算中心。

估计它们运行时间分别为10，6，2，4和8分钟，其优先级（由外部设定）分别为3，5，2，1和4，其中5为最高优先级。

操作系统概论 第6章 并发进程 课件

操作系统概论 第6章 并发进程 课件

进程的交互：竞争与协作

并发进程之间的竞争关系
共享资源
进程的互斥

并发进程之间的协作关系
进程的相互合作
进程的同步
进程的交互：竞争与协作
第一种是竞争关系
资源竞争的两个控制问题：
一个是死锁(Deadlock)问题
一个是饥饿(Starvation) 问题
既要解决饥饿问题，又要解决死锁问题
CPU利用率= 40/80 = 50%
DEV1利用率=18.75%
DEV2利用率= 31.25%
程序并发执行

在并发环境下
CPU利用率=89% DEV1并发环境下利用=33% DEV2并发环境下利用=66%
并行和并发



在单CPU系统中，系统调度在某一时刻只能让一个 线程(进程)运行，虽然这种调度机制有多种形式(大 多数是时间片轮巡为主)，但无论如何，要通过不断 切换需要运行的线程让其运行的方式就叫并发 (concurrent)。 而在多CPU系统中，可以让两个以上的线程(进程) 同时运行，这种可以同时让两个以上线程同时运行 的方式叫做并行(parallel) 多道程序设计和并发的关系
程被置成等待信号量s的状态 */
end; procedure V(var s:semaphore); begin s := s + 1; /* 把信号量加1 */ if s <= 0 then R(s); /* 若信号量小于等于0，则释放
一个等待信号量s的进程 */
end;
p、v操作
(1) p操作 对信号量s的 p操作记为 p(s)。p(s)是一个不可分割的原语 操作，即取信号灯值减1，若相减结果为负，则调用p(s)的进程 被阻，并插入到该信号量的等待队列中，否则可以继续执行

《操作系统》习题集：第6章死锁

《操作系统》习题集：第6章死锁第6章死锁-习题集⼀、选择题1.在操作系统中，死锁出现是指（）。

【＊，★，联考】A. 计算机系统发⽣重⼤故障B. 资源个数远远⼩于进程数C. 若⼲进程因竞争资源⽽⽆限等待其他进程释放已占有的资源D. 进程同时申请的资源数超过资源总数2.在（）的情况下，系统出现死锁。

【＊，联考】A. 计算机系统发⽣了重⼤故障B. 有多个封锁的进程同时存在C. 若⼲进程因竞争资源⽽⽆休⽌地相互等待他⽅释放已占有的资源D. 资源数远远⼩于进程数或进程同时申请的资源数远远超过资源总数3.当出现（）情况下，系统可能出现死锁。

【＊，联考】A. 进程释放资源B. ⼀个进程进⼊死循环C. 多个进程竞争资源出现了循环等待D. 多个进程竞争共享型设备4.为多道程序提供的可共享资源不⾜时，可能出现死锁。

但是，不适当的（）也可能产⽣死锁。

【＊＊，联考】A. 进程优先级B. 资源线性分配C. 进程推进顺序D. 分配队列优先权5.采⽤资源剥夺法可以解除死锁，还可以采⽤（）⽅法解除死锁。

【＊，★，联考】A. 执⾏并⾏操作B. 撤销进程C. 拒绝分配新资源D. 修改信号量6.死锁产⽣的原因之⼀是（）。

【＊，联考】A. 系统中没有采⽤SPOOLing技术B. 使⽤的P、V操作过多C. 有共享资源存在D. 资源分配不当7.产⽣死锁的4个必要条件是：互斥、（）、循环等待和不剥夺。

【＊，联考，？】A. 请求与阻塞B. 请求与保持C. 请求与释放D. 释放与阻塞8.⼀个进程在获得资源后，只能在使⽤完资源后由⾃⼰释放，这属于死锁必要条件的（）。

【＊，联考】A. 互斥条件B. 请求和释放条件C. 不剥夺条件D. 环路等待条件9.死锁的预防是根据（）⽽采取措施实现的。

【＊，★，联考】A. 配置⾜够的系统资源B. 使进程的推进顺序合理C. 破坏死锁的四个必要条件之⼀D. 防⽌系统进⼊不安全状态10.资源的有序分配策略可以破坏死锁的（）条件。

操作系统概念(第九版)答案

操作系统概念(第九版)答案简介《操作系统概念(第九版)答案》是一本针对《操作系统概念(第九版)》教材的答案集合。

本文档旨在提供读者对操作系统相关概念的理解和应用基础。

目录1.引论2.进程管理3.处理机调度4.进程同步5.死锁6.内存管理7.虚拟内存8.文件系统9.输入与输出10.磁盘存储管理11.安全性和保护12.分布式系统13.多媒体操作系统14.实时系统第一章引论本章的目标是介绍操作系统的概念和功能，包括定义了什么是操作系统、操作系统的历史和发展、操作系统的分类以及操作系统的基本组成部分。

问题1：操作系统是什么？答案：操作系统是一个管理计算机硬件和软件资源的软件系统。

它为用户提供一个在硬件和软件之间进行交互的接口，同时协调和控制计算机的各个组件，以实现有效和可靠的计算机操作。

问题2：操作系统的历史和发展？答案：操作系统的历史可以追溯到大约20世纪50年代，当时计算机的使用范围相对较小，操作系统也比较简单。

随着计算机技术的发展，操作系统逐渐变得复杂而且功能强大。

在20世纪60年代，随着多道程序设计的发展，操作系统开始支持同时运行多个程序。

这就导致了对资源的合理分配和进程调度的需求。

同时，操作系统的文件系统和输入输出功能也得到了改进和扩展。

在20世纪70年代，个人计算机的出现使得操作系统变得更加普及。

同时，分时操作系统和分布式操作系统的概念也开始出现。

到了20世纪80年代和90年代，图形用户界面(GUI)的引入和互联网的普及使得操作系统更加用户友好和功能丰富。

现在，操作系统已经成为计算机系统中不可或缺的一部分，为计算机用户提供各种功能和服务。

问题3：操作系统的分类有哪些？答案：操作系统可以根据不同的标准进行分类。

以下是国际上常用的操作系统分类方法：1.目标计算机系统：大型机操作系统、小型机操作系统、微型机操作系统、嵌入式系统操作系统。

2.处理方式：批处理系统、分时操作系统、实时操作系统。

3.用户数量：单用户操作系统、多用户操作系统。

计算机操作系统 第5章 死 锁


5.2
死 锁 预 防(Deadlock Prevention) -2
所有进程对资源的请求必须严格按资源序号递增的次序提出。 这样在所形成的资源分配图中不可能再出现环路，因而摒弃 了“环路等待”条件，在采用这种策略时总有一个进程占据 了较高序号的资源，它继续请求的资源必然是空闲的，因而 进程可以一直向前推进。这种预防死锁的策略可以提高资源 利用率，但在进程使用各类资源的顺序与系统规定的顺序不 同时会造成资源浪费的情况。 • 资源按级分配法 该方法是把资源递增排序成若干等级（如L1、L2…….Lm）， 其中每级可包含几类资源，要求每个进程在获得了Lj级中资 源之后 ，它才能申请更高级的LK（LK＞Lj）级中的资源；如 果它还需申请比LK级低的LI级（LI<LK）资源，则必须先释放 所有大于LI级的资源。该方法是Haveder 1968年在设计IBM／ 360 OS时提出的，资源共分三级，第一级数据集或文件，第 二级主存，第三级I/O设备。
5.2
死 锁 预 防(Deadlock Prevention) -1
3。破坏请求和保持条件 破坏请求和保持条件 系统可采用资源静态予分配方式 资源静态予分配方式来破坏请求保持条件。系 资源静态予分配方式 统要求所有进程一次性地申请在整个运行过程中全部资源， 若系统有足够资源满足给进程，则在运行前，一次性将其所 需要的所有资源分配给该进程。这样该进程在整个运行期间， 便不再提出资源要求，从而摒弃了请求条件。这种预防死锁 的方法，优点是简单、易予实现且很安全，但其资源利用率 很低，进程也延迟运行。 4。破坏循环等待条件 破坏循环等待条件 • 有序资源使用法 该方法将所有的资源按类型进行线性排队，并赋予不同的 序号。例如令输入机的序号为1，打印机序号为2，磁盘机序 号为3等。

操作系统精髓及设计原理-第6章 并发性_死锁及饥饿

第六章习题翻译第一部分复习题６.１给出可重用资源和可消费资源的例子。

答：可重用资源：处理器，Ｉ/Ｏ通道，主存和辅存，设备以及诸如文件，数据库和信号量之类的数据结构。

可消费资源：中断，信号，消息和Ｉ/Ｏ缓冲区中的信息。

６.２可能发生死锁所必须的三个条件是什么？答：互斥，占有且等待，非抢占。

６.３产生死锁的第４个条件是什么？答：循环等待。

６.４如何防止占有且等待的条件？答：可以要求进程一次性地请求所有需要的资源，并且阻塞这个资源直到所有请求都同时满足。

６.５给出防止无抢占条件的两种方法。

答：第一种，如果占有某些资源的一个进程进行进一步资源请求被拒绝，则该进程必须释放它最初占用的资源，如果有必要，可再次请求这些资源和另外的资源。

第二种，如果一个进程请求当前被另一个进程占有的一个资源，则操作系统可以抢占另一个进程，要求它释放资源。

６.６如何防止循环等待条件？答：可以通过定义资源类型的线性顺序来预防。

如果一个进程已经分配到了Ｒ类型的资源，那么它接下来请求的资源只能是那些排在Ｒ类型之后的资源类型。

６.７死锁避免，检测和预防之间的区别是什么？答：死锁预防是通过间接地限制三种死锁必要条件的至少一个或是直接地限制循环等待的发生来避免死锁的出现。

死锁避免允许可能出现的必要条件发生，但是采取措施确保不会出现死锁的情况。

而死锁检测允许资源的自由分配，采取周期性的措施来发现并处理可能存在的死锁情况。

第二部分习题６.１写出图６.１（a）中死锁的四个条件。

解：互斥：同一时刻只有一辆车可以占有一个十字路口象限。

占有且等待：没有车可以倒退；在十字路口的每辆车都要等待直到它前面的象限是空的。

非抢占: 没有汽车被允许挤开其他车辆。

循环等待: 每辆汽车都在等待一个此时已经被其他车占领的十字路口象限。

６.２按照６.１节中对图６.２中路径的描述，给出对图６.３中６种路径的简单描述。

解：１.Q 获得 B 和Ａ, 然后释放 B 和 A. 当 P 重新开始执行的时候, 它将会能够获得两个资源。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

3. ◦
避免死锁
在资源的动态分配过程中，用 某种方法防止系统进入不安全 的状态，从而避免死锁。如一 次分配所有资源。 银行家算法(banker’s algorithm)
◦
◦
4. ◦
死锁避免(deadlock Avoidance)
2.
让它发生，找到并解决之
◦ 通过系统的检测机构及时 地检测出死锁，然后采取 某种措施解除死锁。 检测及解除死锁(deadlock detection and Recovery)
第6章 死锁 （北理珠本末终始）
示例：死锁的产生与避免(之四)
三.多道执行：
拒绝B的请求并挂起。无死锁 A B C A B C A B C
1.A请求：R 2.B请求：S 拒绝并挂起 2.C请求：T 3.A请求：S 4.C请求：R
R
ห้องสมุดไป่ตู้
S (1)
T
R
S (2)
T
R
S （3）
T
A
B
C
A
B
C
A
B
C
R 5.A释放：R 6.A释放：S
P2>=A?
否
P1 P2 P3
当前请求矩阵 R 磁带机 绘图仪 扫描仪 2 0 0 1 0 1 2 1 0 计算方法：总需要-C
CD-ROM 1 0 0
P3>=A?
是
引自《现代操作系统》(原书第3版)P251,制作北理珠本末终始,2011-11-29
第6章 死锁 （北理珠本末终始）
死锁避免：银行家算法
0 0 1 0 ◦ C= 2 0 0 1 0 1 2 0
◦ 进程3占有：
需要2磁带机2绘图仪2扫描仪

4类资源：
◦ ◦ ◦ ◦ ◦ 磁带机：4 绘图仪：2 扫描仪：3 CD-ROM：1 用E向量表示(现有资源)
existing resource vector E=（4 2 3 1）
如低优先级的进程等待被高优先级的进程长久占据的资源


死锁进程处于等待状态，饿死不然 死锁可以检测，饿死不然 死锁⇒饥饿（反之不行）
◦ 饥饿可以终止（但不是必须的） ◦ 死锁除非外部干预否则不能终止
第6章 死锁 （北理珠本末终始）
第6章 死锁 （北理珠本末终始）
第6章 死锁 （北理珠本末终始）

数据库系统中，为了避免竞争，对若干记录加锁
◦ 进程A：对记录R1加锁 ◦ 进程B：对记录R2加锁 ◦ 此时，两个进程试图把对方的记录加锁。

死锁方面的大多数研究工作工作在1980年以前就完成了
第6章 死锁 （北理珠本末终始）
哲学家就餐问题
面条
面条
面条
面条
面条
第6章 死锁 （北理珠本末终始）
资源(resource)
◦ 设置空表L，随机选取结 点。 ◦ 以R出发搜索
L={ }L={R}L={R,A} L={R,A,S}
L={B,T,E,V,G,U}L={B,T,E,V,G,U,D} L={B,T,E,V,G,U,D,T}，发现回路，结 束！
◦ 以B出发搜索
L={ }L={B}L={B,T} L={B,T,E}L={B,T,E,V} L={B,T,E,V}L={B,T,E,V,G}
◦ 死锁与不可抢占资源有关，有关可抢占资源的潜在死锁通常可以通过在进 程之间重新分配资源面化解。 ◦ 不可抢占资源在完成之前难以释放，如正在刻录的CD盘。
使用资源的事件
◦ 请求资源（malloc，open，request等系统调用） ◦ 使用资源
◦ 释放资源（free，close等）
第6章 死锁 （北理珠本末终始）
第6章 死锁 （北理珠本末终始）
死锁检测：每个类型多个资源

3个进程
◦ 进程1
需要2磁带机1扫描1CDROM
◦ 用A向量表示(可用资源)
available resource vector A=(2 1 0 0)
◦ 进程2占有：
需要3磁带机1扫描仪 1CDROM

C代表当前分配矩阵
◦ current allocation matrix
4.

环路等待条件
死锁发生时，系统中一定有由两个或两个以上的进程组成一条环路， 该环路中的每个进程都在等待着下一个进程所占有的资源

Conditions for Resource Deadlocks
1. 2. 3. 4. Mutual exclusion condition Hold and wait condition. No preemption condition. Circular wait condition.
第6章 死锁 （北理珠本末终始）
死锁与四个必要条件
死锁发生时四个条件必须同时满足 如果其中任何一个不满足，死锁就不会发 生 预防死锁：破坏上述任何一个条件

第6章 死锁 （北理珠本末终始）
加州伯克利分校“操作系统与系 统编程”公开课
第6章 死锁 （北理珠本末终始）
第6章 死锁 （北理珠本末终始）

R代表请求矩阵
◦ request matrix ◦ 需要额外的资源
2 0 0 1 1 0 1 0 ◦ R= 2 1 0 0
第6章 死锁 （北理珠本末终始）
总的资源（ E 是现有资源向量） 磁带机 绘图仪 扫描仪 CD-ROM E= 4 2 3 1
E-C列之和
当前进程占有资源（ C 是当前分配矩阵） 磁带机 绘图仪 扫描仪 CD-ROM P1 0 0 1 0 P2 2 0 0 1 P3 0 1 2 0
P1和P2均可 执行，无死 锁
当前可用资源（ A 是可用资源向量） A= 2 1 0 0 计算方式：A=E-C的列之和
A=
磁带机 绘图仪 2 2
扫描仪 2
CD-ROM 0
P1 P2 P3
进程总需要资源 磁带机 绘图仪 扫描仪 2 0 1 3 0 1 2 2 2
CD-ROM 1 1 0
总需要-C
将C的第3行 加到A中 否 P1>=A? P3继续并释 放资源
S （4）
T
R
S （5）
T
R
S （6）
T
7.B请求：S
制作：本末终始；日期：2011-11北理珠
第6章 死锁 （北理珠本末终始）
第6章 死锁 （北理珠本末终始）
处理死锁的策略
1.
忽略该问题
◦ ◦ ◦ ◦ 也许如果你忽略它，它也 会忽略你 如平均每5年出现一次死 锁。数学家不能接受。 免除了消除死除的代价。 鸵鸟算法（The Ostrich Algorithm）
第6章 死锁 （北理珠本末终始）
死锁(DEADLOCK)与饥饿(STARVATION)

死锁
◦ 在多道程序系统中，一组进程中的每一个进程无限期等待被该组 进程中的另一个进程所占有且永远不会释放的资源。

饥饿
◦ 是指系统不能保证某个进程的等待时间上界(deadline)，从而使该 进程长时间等待，当等待时间给进程推进和响应带来明显影响时 ，称发生了进程饥饿。当饥饿到一定程度的进程所赋予的任务即 使完成也不再具有实际意义时称该进程被饿死。 ◦ 进程或线程的等待时间不确定

第6章 死锁 （北理珠本末终始）
资源死锁的条件

Coffman等人(1971)总结产生(资源)死锁的四个必要条件
1.

互斥条件。
每个资源要么已经分配给了一个进程，要么就是可用的
2.

占有和等待条件（部分已分配条件）
已经得到了某个资源的进程可以再请求新的资源
3.

不可抢占条件（非剥夺条件）
已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的 进程显示地释放
银行家拥有的资金数：10个单位
第6章 死锁 （北理珠本末终始）
无死锁
有可能出现死锁
示例：两种编码
（AST，P246）
第6章 死锁 （北理珠本末终始）
死锁的定义
如果一个进程集合中的每个进程都在等 待只能由该进程集合中的其他进程才能 引发的事件，那么，该进程集合就是死 锁的。 A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause
资源分配图

Holt(1972)用有向图建立四个死锁必要条件的模型 说明
◦ 两类节点：“圆形”表示进程；“方形”表示资源 ◦ “方形”“圆形”：资源已被进程占有 ◦ “圆形”“方形”：进程申请资源，被阻塞，等待资源状态 ◦ 图(a)：资源“R”被进程A占有 ◦ 图(b)：进程“B”申请资源“S” ◦ 图(c)：死锁
操作系统
北京理工大学珠海学院 计算机学院 龚友明
死锁(DEADLOCK)示例
引自《操作系统联考辅导教程》P133；《现代操作系统》P244

某计算机系统中只有一台打印机和一台输入设备，
◦ 进程P1：占用输入设备 ◦ 进程P2：占用打印机 ◦ 此时，P1申请“打印机”，P2申请“输入设备”，而占用的设备两者都 没放弃。 ◦ 结果，P1与P2无休止等待下去，无法继续执行，陷入“死锁”状态
◦ 在桥上变空之前不允许汽车上桥 ◦ 如果两车相遇，让其中一辆车倒退 ◦ 桥上加一个车道
第6章 死锁 （北理珠本末终始）
处理死锁的方法

鸵鸟算法
◦ 忽略死锁，即不处理。如平均每5年出现一次死锁 。免除了消除死除的代价。

预防死锁