操作系统学习(七)—— 死锁

死锁的定义

进程之间互相等待资源又都不能向前推进的情况,即造成进程相互死等的局面。即每个进程“抓住”一些为其他进程所等待的资源不放。其结果是谁也得不到它所申请的全部资源,导致这些进程都无法继续运行。

产生死锁的原因

  • 根本原因:系统能够提供的资源个数比请求该资源的进程数要少。
  • 死锁是在并发进程在竞争资源的过程中产生的。

死锁产生的必要条件:

  • 互斥:多进程共享的资源具有互斥特性,一次只能由一个进程使用。如果另一个进程申请资源,那么申请进程必须等待,直到该资源被释放。
  • 不剥夺:进程所获得资源在未使用完毕之前,不能被强行夺走,只能由进程自己释放。
  • 占有并等待(部分分配):进程每次申请它所需要的一部分资源,在等待新资源的同时,进程继续占用已分配到的资源。
  • 环路条件(循环等待):有一种循环链,链中每一个进程已获得的资源同时被链中下一个进程所请求。

死锁的预防(静态策略)

上面说了死锁产生的必要条件,那么只要打破其中一个,死锁就不会发生。

  • 打破互斥条件。即允许进程同时访问某些资源。但是,有的资源是不允许被同时访问的,像打印机等等,这是由资源本身的属性所决定的。所以,这种办法并无实用价值。
  • 打破不可抢占条件。即允许进程强行从占有者那里夺取某些资源。就是说,当一个进程已占有了某些资源,它又申请新的资源,但不能立即被满足时,它必须释放所占有的全部资源,以后再重新申请。它所释放的资源可以分配给其它进程。这就相当于该进程占有的资源被隐蔽地强占了。这种预防死锁的方法实现起来困难,会降低系统性能。
  • 打破占有且申请条件。可以实行资源预先分配策略。即进程在运行前一次性地向系统申请它所需要的全部资源。如果某个进程所需的全部资源得不到满足,则不分配任何资源,此进程暂不运行。只有当系统能够满足当前进程的全部资源需求时,才一次性地将所申请的资源全部分配给该进程。由于运行的进程已占有了它所需的全部资源,所以不会发生占有资源又申请资源的现象,因此不会发生死锁。但是,这种策略也有如下缺点:
    1)在许多情况下,一个进程在执行之前不可能知道它所需要的全部资源。这是由于进程在执行时是动态的,不可预测的;
    2)资源利用率低。无论所分资源何时用到,一个进程只有在占有所需的全部资源后才能执行。即使有些资源最后才被该进程用到一次,但该进程在生存期间却一直占有它们,造成长期占着不用的状况。这显然是一种极大的资源浪费;
    3)降低了进程的并发性。因为资源有限,又加上存在浪费,能分配到所需全部资源的进程个数就必然少了。
  • 打破循环等待条件,实行资源有序分配策略。采用这种策略,即把资源事先分类编号,按号分配,使进程在申请,占用资源时不会形成环路。所有进程对资源的请求必须严格按资源序号递增的顺序提出。进程占用了小号资源,才能申请大号资源,就不会产生环路,从而预防了死锁。这种策略与前面的策略相比,资源的利用率和系统吞吐量都有很大提高,但是也存在以下缺点:
    (1)限制了进程对资源的请求,同时给系统中所有资源合理编号也是件困难事,并增加了系统开销;
    (2)为了遵循按编号申请的次序,暂不使用的资源也需要提前申请,从而增加了进程对资源的占用时间。

银行家算法(死锁的动态策略)

1)安全序列
我们首先引入安全序列的定义:所谓系统是安全的,是指系统中的所有进程能够按照某一种次序分配资源,并且依次地运行完毕,这种进程序列{P1,P2,...,Pn}就是安全序列。如果存在这样一个安全序列,则系统是安全的;如果系统不存在这样一个安全序列,则系统是不安全的。
安全序列{P1,P2,...,Pn}是这样组成的:若对于每一个进程Pi,它需要的附加资源可以被系统中当前可用资源加上所有进程Pj当前占有资源之和所满足,则{P1,P2,...,Pn}为一个安全序列,这时系统处于安全状态,不会进入死锁状态。  
虽然存在安全序列时一定不会有死锁发生,但是系统进入不安全状态(四个死锁的必要条件同时发生)也未必会产生死锁。当然,产生死锁后,系统一定处于不安全状态。
这是一个著名的避免死锁的算法,是由Dijstra首先提出来并加以解决的。

[背景知识]
一个银行家如何将一定数目的资金安全地借给若干个客户,使这些客户既能借到钱完成要干的事,同时银行家又能收回全部资金而不至于破产,这就是银行家问题。这个问题同操作系统中资源分配问题十分相似:银行家就像一个操作系统,客户就像运行的进程,银行家的资金就是系统的资源。

[问题的描述]
一个银行家拥有一定数量的资金,有若干个客户要贷款。每个客户须在一开始就声明他所需贷款的总额。若该客户贷款总额不超过银行家的资金总数,银行家可以接收客户的要求。客户贷款是以每次一个资金单位(如1万RMB等)的方式进行的,客户在借满所需的全部单位款额之前可能会等待,但银行家须保证这种等待是有限的,可完成的。

例如:有三个客户C1,C2,C3,向银行家借款,该银行家的资金总额为10个资金单位,其中C1客户要借9各资金单位,C2客户要借3个资金单位,C3客户要借8个资金单位,总计20个资金单位。某一时刻的状态如图所示。

银行家算法实例.png

解答
1)选取客户C2,银行家手上资源大于C2请求的资源,C2借款完毕,返还3个资源。
2)选取客户C3,银行家手上资源等于C3请求的资源,C3借款完毕,返还4个资源。
3)选取客户C1,银行家手上资源大于C1请求的资源,C1借款完毕,返还9个资源。
最后返还10个资源,银行家保本。

综上所述,银行家算法是从当前状态出发,逐个按安全序列检查各客户谁能完成其工作,然后假定其完成工作且归还全部贷款,再进而检查下一个能完成工作的客户,......。如果所有客户都能完成工作,则找到一个安全序列,银行家才是安全的。

银行家算法允许死锁必要条件中的:
1)互斥条件(资源被一个人申请其他人无法申请)
2)占有且申请条件(进程占有一部分资源,完成之前继续占有并申请资源)
3)不可抢占条件(占有资源后不能强制解除,只能自己完成后释放)
这样,它与预防死锁的几种方法相比较,限制条件少了,资源利用程度提高了。

死锁的恢复

2.死锁的恢复

一旦在死锁检测时发现了死锁,就要消除死锁,使系统从死锁状态中恢复过来。

  • 最简单,最常用的方法就是进行系统的重新启动,不过这种方法代价很大,它意味着在这之前所有的进程已经完成的计算工作都将付之东流,包括参与死锁的那些进程,以及未参与死锁的进程。

  • 撤消进程,剥夺资源。终止参与死锁的进程,收回它们占有的资源,从而解除死锁。这时又分两种情况:一次性撤消参与死锁的全部进程,剥夺全部资源;或者逐步撤消参与死锁的进程,逐步收回死锁进程占有的资源。一般来说,选择逐步撤消的进程时要按照一定的原则进行,目的是撤消那些代价最小的进程,比如按进程的优先级确定进程的代价;考虑进程运行时的代价和与此进程相关的外部作业的代价等因素。

  • 此外,还有进程回退策略,即让参与死锁的进程回退到没有发生死锁前某一点处,并由此点处继续执行,以求再次执行时不再发生死锁。虽然这是个较理想的办法,但是操作起来系统开销极大,要有堆栈这样的机构记录进程的每一步变化,以便今后的回退,有时这是无法做到的。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,378评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,356评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,702评论 0 342
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,259评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,263评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,036评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,349评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,979评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,469评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,938评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,059评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,703评论 4 323
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,257评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,262评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,485评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,501评论 2 354
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,792评论 2 345

推荐阅读更多精彩内容

  • 1、竞态条件: 定义:竞态条件指的是一种特殊的情况,在这种情况下各个执行单元以一种没有逻辑的顺序执行动作,从而导致...
    Hughman阅读 1,283评论 0 7
  • 一、死锁的基本概念 1.1 死锁的定义 一组进程中,每个进程都无限等待被该组进程中另一进程所占用的资源,因而永远无...
    yjaal阅读 1,464评论 0 6
  • word直接复制来了,格式就不改了。至于这门课怎么复习,只要平时实验都认真完成、报告认真写,平时分都很高;考试的话...
    Jozhn阅读 4,520评论 0 8
  • 一、什么是死锁 所谓死锁,是指多个进程循环等待它方占有的资源而无限期地僵持下去的局面。 二、产生死锁的必要条件 互...
    Q南南南Q阅读 756评论 0 0
  • 一只黑袜子拒绝和另外一只黑袜子在一起,因为它们的纹路不一样。
    單SHAN阅读 238评论 3 2