操作系统第五篇【死锁】

死锁的概念

死锁(Deadlock),这里指的是进程死锁。它是操作系统或软件运行的一种状态:在多任务系统下,当一个或多个进程等待系统资源,而资源又被进程本身或其他进程占用时,就形成了死锁。

所谓死锁,是指多个进程循环等待它方占有的资源而无限期地僵持下去的局面。 计算机系统产生死锁的根本原因就是资源有限且进程间推进顺序不当

出现死锁的条件

  • 互斥条件
    • 即某个资源在一段时间内只能由一个进程占有,不能同时被两个或两个以上的进程占有。
  • 不剥夺条件
    • 进程所获得的资源在未使用完毕之前,资源申请者不能强行地从资源占有者手中夺取资源,而只能由该资源的占有者进程自行释放。
  • 请求和保持条件
    • 进程至少已经占有一个资源,但又申请新的资源;由于该资源已被另外进程占有,此时该进程阻塞;但是,它在等待新资源之时,仍继续占用已占有的资源。
  • 环路条件

这里写图片描述

处理死锁

  • 死锁预防、死锁避免
  • 死锁检测、死锁恢复

死锁预防

死锁的预防是保证系统不进入死锁状态的一种策略。 它的基本思想是要求进程申请资源时遵循某种协议,从而打破产生死锁的四个必要条件中的一个或几个,保证系统不会进入死锁状态。

  • 破坏“请求和保持”条件
    • 即允许进程同时访问某些资源。
    • 但是,有的资源是不允许被同时访问的,像打印机等等,这是由资源本身的属性所决定的。
    • 所以,这种办法并无实用价值。
  • 破坏“不剥夺”条件
    • 即允许进程强行从占有者那里夺取某些资源
  • 破坏“环路等待”条件
    • 可以实行资源预先分配策略

死锁的避免

死锁的避免指在系统运行过程中,对进程发出的每一个系统能够满足的资源申请进行动态检查,并根据检查结果决定是否分配资源,若分配后系统可能发生死锁,则不予分配,否则予以分配。 在分配资源时判断是否会出现死锁,如不会死锁,则分配资源。

死锁的检测和恢复

保存资源的请求和分配信息,利用某种算法对这些信息加以检查,以判断是否存在死锁。 死锁检测算法主要是检查是否有循环等待

死锁检测算法是当进程进行资源请求时检查并发进程组是否构成资源的请求和占用环路。如果不存在这一环路,则系统中一定没有死锁。检测方法有进程-资源有向图和死锁定理

一旦发生死锁,就利用资源剥夺法或进程撤销法解除死锁。

  • 1)撤消陷于死锁的全部进程;
  • 2)逐个撤消陷于死锁的进程,直到死锁不存在;
  • 3)从陷于死锁的进程中逐个强迫放弃所占用的资源,直至死锁消失;
  • 4)从另外的进程那里强行剥夺足够数量的资源分配给死锁进程,以解除死锁状态。

鸵鸟算法

最简单的方法,就是忽略死锁。 据说(尽管很多人认为不可能)鸵鸟遇到无法避免的危险时就把头埋在沙子里,对出现的危险不管不顾。 操作系统处理死锁的一种策略是不预防、不避免,对可能出现的死锁采取放任的态度,称作鸵鸟算法

当出现死锁的概率很小,并且出现之后处理死锁会花费很大的代价时,执行死锁避免的开销很大,还不如不做处理。因此,鸵鸟算法是平衡性能和复杂性的一种方法。

….啥都不处理也能叫做成一个算法….

银行家算法

银行家算法是一种最有代表性的避免死锁的算法。又被称为“资源分配拒绝”法。

  • 一、安全状态
    • 所谓系统是安全的,是指系统中的所有进程能够按照某一种次序分配资源,并且依次地运行完毕,这种进程序列{ P1 ,P2 …Pn}就是安全序列。
    • 如果存在这样一个安全序列,则系统是安全的。
  • 二、由安全状态向不安全状态的转换
    • 对于处于安全状态的系统,当某进程请求某些资源后,系统不再安全,也就是说,不存在一个安全序列,那么,此时系统处于不安全状态。

为了实现银行家算法,在系统中必须设置这样四个数据结构,分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配,以及所有进程还需要多少资源的情况。

  •  (1) 可利用资源向量Available。
  • (2) 最大需求矩阵Max。 
  • (3) 分配矩阵Allocation。  
  • (4) 需求矩阵Need。

设Requesti是进程Pi的请求向量,如果Request i[j]=K,表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后,系统按下述步骤进行检查: (1) 如果Request i[j]≤Need[i, j],便转向步骤(2); 否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。 2) 如果Request i[j]≤Available[j],便转向步骤(3); 否则,表示尚无足够资源,Pi须等待。 (3) 系统试探着把资源分配给进程Pi,并修改下面数据结构中的数值: Available[j] = Available[j] - Request i[j]; Allocation[i, j] = Allocation[i, j] + Request i[j]; Need[i, j] = Need[i, j] - Request i[j]; (4) 系统执行安全性算法,检查此次资源分配后系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待

这里写图片描述

原文发布于微信公众号 - Java3y(java3y)

原文发表时间:2018-04-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏windealli

同步异步与阻塞非阻塞

标题有点简单粗暴,直接用了本文要介绍的几个概念。本来想取个高大上一点的标题,但是感觉主题不那么明了。

41923
来自专栏腾讯Bugly的专栏

《手Q Android线程死锁监控与自动化分析实践》

一、问题背景 手Q每个版本上线以后研发同学都会收到各种问题反馈。在跟进手Q内部用户反馈的问题时,发现多例问题,其表象和原因如下: 1、问题表象:“未读不消失”、...

3209
来自专栏Java Edge

Java Fork Join 框架Doug Lea 关于Java 7引入的他写的Fork/Join框架的论文0. 摘要1. 简介2. 设计3. 实现

2728
来自专栏Pythonista

python多线程与线程

考虑一个场景:浏览器,网易云音乐以及notepad++ 三个软件只能顺序执行是怎样一种场景呢?另外,假如有两个程序A和B,程序A在执行到一半的过程中,需要读取大...

1092
来自专栏移动端开发

AVFoundation 框架初探究(二)

接着第一篇总结 ----       系列第一篇地址:AVFoundation 框架初探究(一)       在第一篇的文章中,我们总结了主要有下面几个点的知识...

3514
来自专栏逸鹏说道

C#线程篇---Windows调度线程准则(3)

Windows本身就是一个抢占式操作系统,它的实现,必定有某种算法在里面,比如什么时候调度哪些线程,需要花费多长时间等问题。 我们时时在用Windows,作为程...

3144
来自专栏阿杜的世界

2月工作小结

只要有任务做,就可以快速进步,最近接手的一个任务是对各类业务数据进行定时统计,数据量比较庞大,要求短时间内出统计结果。完成任务的过程中,学习到如下知识:

462
来自专栏开发 & 算法杂谈

基于Lockset的数据竞争检测方法汇总(四)

     今天讲的这篇文论中提到的Lockset方法同样也是和Happens-Before结合来进行动态数据竞争检测,这篇论文中使用的Happens-Befor...

1264
来自专栏JackeyGao的博客

Python 高级并发2

根据编程逻辑一般需要计算密集和I/O操作密集的时候选择并发提高程序效率, Python 由于GIL的限制,密集性运算需要使用多核心CPU时候, 这时候多线程显得...

521
来自专栏阮一峰的网络日志

进程与线程的一个简单解释

进程(process)和线程(thread)是操作系统的基本概念,但是它们比较抽象,不容易掌握。 最近,我读到一篇材料,发现有一个很好的类比,可以把它们解释地清...

2916

扫码关注云+社区