死锁的定义
进程之间互相等待资源又都不能向前推进的情况,即造成进程相互死等的局面。即每个进程“抓住”一些为其他进程所等待的资源不放。其结果是谁也得不到它所申请的全部资源,导致这些进程都无法继续运行。
产生死锁的原因
- 根本原因:系统能够提供的资源个数比请求该资源的进程数要少。
- 死锁是在并发进程在竞争资源的过程中产生的。
死锁产生的必要条件:
- 互斥:多进程共享的资源具有互斥特性,一次只能由一个进程使用。如果另一个进程申请资源,那么申请进程必须等待,直到该资源被释放。
- 不剥夺:进程所获得资源在未使用完毕之前,不能被强行夺走,只能由进程自己释放。
- 占有并等待(部分分配):进程每次申请它所需要的一部分资源,在等待新资源的同时,进程继续占用已分配到的资源。
- 环路条件(循环等待):有一种循环链,链中每一个进程已获得的资源同时被链中下一个进程所请求。
死锁的预防(静态策略)
上面说了死锁产生的必要条件,那么只要打破其中一个,死锁就不会发生。
- 打破互斥条件。即允许进程同时访问某些资源。但是,有的资源是不允许被同时访问的,像打印机等等,这是由资源本身的属性所决定的。所以,这种办法并无实用价值。
- 打破不可抢占条件。即允许进程强行从占有者那里夺取某些资源。就是说,当一个进程已占有了某些资源,它又申请新的资源,但不能立即被满足时,它必须释放所占有的全部资源,以后再重新申请。它所释放的资源可以分配给其它进程。这就相当于该进程占有的资源被隐蔽地强占了。这种预防死锁的方法实现起来困难,会降低系统性能。
- 打破占有且申请条件。可以实行资源预先分配策略。即进程在运行前一次性地向系统申请它所需要的全部资源。如果某个进程所需的全部资源得不到满足,则不分配任何资源,此进程暂不运行。只有当系统能够满足当前进程的全部资源需求时,才一次性地将所申请的资源全部分配给该进程。由于运行的进程已占有了它所需的全部资源,所以不会发生占有资源又申请资源的现象,因此不会发生死锁。但是,这种策略也有如下缺点:
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个资金单位。某一时刻的状态如图所示。
解答:
1)选取客户C2,银行家手上资源大于C2请求的资源,C2借款完毕,返还3个资源。
2)选取客户C3,银行家手上资源等于C3请求的资源,C3借款完毕,返还4个资源。
3)选取客户C1,银行家手上资源大于C1请求的资源,C1借款完毕,返还9个资源。
最后返还10个资源,银行家保本。
综上所述,银行家算法是从当前状态出发,逐个按安全序列检查各客户谁能完成其工作,然后假定其完成工作且归还全部贷款,再进而检查下一个能完成工作的客户,......。如果所有客户都能完成工作,则找到一个安全序列,银行家才是安全的。
银行家算法允许死锁必要条件中的:
1)互斥条件(资源被一个人申请其他人无法申请)
2)占有且申请条件(进程占有一部分资源,完成之前继续占有并申请资源)
3)不可抢占条件(占有资源后不能强制解除,只能自己完成后释放)
这样,它与预防死锁的几种方法相比较,限制条件少了,资源利用程度提高了。
死锁的恢复
2.死锁的恢复
一旦在死锁检测时发现了死锁,就要消除死锁,使系统从死锁状态中恢复过来。
最简单,最常用的方法就是进行系统的重新启动,不过这种方法代价很大,它意味着在这之前所有的进程已经完成的计算工作都将付之东流,包括参与死锁的那些进程,以及未参与死锁的进程。
撤消进程,剥夺资源。终止参与死锁的进程,收回它们占有的资源,从而解除死锁。这时又分两种情况:一次性撤消参与死锁的全部进程,剥夺全部资源;或者逐步撤消参与死锁的进程,逐步收回死锁进程占有的资源。一般来说,选择逐步撤消的进程时要按照一定的原则进行,目的是撤消那些代价最小的进程,比如按进程的优先级确定进程的代价;考虑进程运行时的代价和与此进程相关的外部作业的代价等因素。
此外,还有进程回退策略,即让参与死锁的进程回退到没有发生死锁前某一点处,并由此点处继续执行,以求再次执行时不再发生死锁。虽然这是个较理想的办法,但是操作起来系统开销极大,要有堆栈这样的机构记录进程的每一步变化,以便今后的回退,有时这是无法做到的。