操作系统第五篇【死锁】

死锁的概念

死锁(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 条评论
登录 后参与评论

相关文章

来自专栏Pythonista

macos修改vmware Fusion的NAT网络

1.点击vmware Fusion > 偏好设置 > ( command + , )网络

572
来自专栏Golang语言社区

【译】用Go实现一个静态博客生成器

静态站点生成器是一种工具,给一些输入(例如,markdown),使用HTML,CSS和JavaScript生成完全静态的网站。 为什么这很酷?一般来说,搭建一个...

5254
来自专栏机器学习算法原理与实践

scikit-learn 和pandas 基于windows单机机器学习环境的搭建

    很多朋友想学习机器学习,却苦于环境的搭建,这里给出windows上scikit-learn研究开发环境的搭建步骤。

662
来自专栏ericzli

Jetson TX1上安装Tensorflow Serving遇到的问题总结

本文的目的是分享在TX1上安装Tensorflow Serving时遇到的主要问题,避免重复踩坑。

2203
来自专栏机器之心

分布式TensorFlow入坑指南:从实例到代码带你玩转多机器深度学习

44210
来自专栏Snova云数仓

gpexpand分析

具体包括不限于以下内容: 创建用户名,设置环境变量,创建数据目录,安装greenplum软件包,解压目录路径。

3.3K6
来自专栏Small Code

【TensorFlow | 升级】TensorFlow 1.0 发布

NOW 首届 TensorFlow 开发者大会(TensorFlow Dev Summit)已于美国时间昨日召开,YouTube 还进行了直播。更重要的是,Te...

19710
来自专栏Python中文社区

Django 博客教程(三):创建应用和编写数据库模型

專 欄 ❈追梦人物,Python中文社区专栏作者。电子科技大学计算机学院研究生,从事大数据分析研究方向。主要使用 Python 语言进行相关数据的分析,熟练使...

1899
来自专栏非典型程序猿

你不知道的gRPC反向代理

可用性、可靠性和扩展性是衡量后台服务的基本标准,HTTP反向代理,是任何一个提供大型Web服务后台所必备的,用以提高服务的这些基础参数,且通过支持到负载均衡而进...

7748
来自专栏机器之心

资源 | Parris:机器学习算法自动化训练工具

3349

扫码关注云+社区