避免死锁的算法

1. 避免死锁算法和死锁检测算法的区别

死锁的条件互斥条件（Mutual exclusion）：资源不能被共享，只能由一个进程使用。请求与保持条件（Hold and wait）：已经得到资源的进程可以再次申请新的资源。非剥夺条件（No pre-emption）：已经分配的资源不能从相应的进程中被强制地剥夺。循环等待条件（Circular wait）：系统中若干进程组成环路，改环路中每个进程都在等待相邻进程正占用的资源。处理死锁的策略1.忽略该问题。例如鸵鸟算法，该算法可以应用在极少发生死锁的的情况下。为什么叫鸵鸟算法呢，因为传说中鸵鸟看到危险就把头埋在地底下，可能鸵鸟觉得看不到危险也就没危险了吧。跟掩耳盗铃有点像。2.检测死锁并且恢复。3.仔细地对资源进行动态分配，以避免死锁。4.通过破除死锁四个必要条件之一，来防止死锁产生。

2. 死锁及死锁的处理策略

  死锁是指两个或两个以上的进程因竞争资源而造成的一种互相等待的现象，若无外力作用，这些进程都将无法向前推进。

  饥饿：由于长期得不到想要的资源而导致进程无法向前推进的现象。如在进程调度算法中的短进程优先算法中，若有源源不断的短进程到来，则长进程一直得不到处理机，从而发生了长进程饥饿。
  死循环：某进程执行的过程中一直跳不出某种循环的现象。死循环可能是因为程序bug或者程序员有意为之。

  (1) 互斥条件。 只有对必须互斥使用的资源争抢（如打印机设备）才能导致死锁。
  (2) 不剥夺条件。 进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。如果进程可以抢夺其他进程持有自己需要的资源的话，也就不会产生死锁了，需要资源直接抢就行了。
  (3) 请求和保持条件。 进程已经保持了至少一个资源，但是又提出了新的资源需求，而该资源又被其他进程占有，此时请求进程被阻塞，但是又对自己持有的资源保持不放。也是很简单的道理，如果一个进程请求的资源被阻塞，就释放了自己持有的资源，其他进程就可以获取它释放的资源，也就不会发生相互等待而导致死锁了。
  (4) 循环等待条件。 存在一种进程资源的循环等待链，链中的每一个进程已经获得的资源同时被下一个进程所请求。

  (1) 对系统资源的争抢。各进程对不可剥夺资源的竞争可能会引起死锁。
  (2) 进程推进顺序非法。如果请求资源的顺序不当也会导致死锁，如上面的图，双方请求的资源被对方占有而导致死锁。
  (3) 信号量的使用不当。并发执行进程时，如果信号量使用的顺序不当也会到导致死锁。
  总之，对不可剥夺的资源的不合理分配，可能导致死锁。

  (1) 预防死锁。 破坏死锁产生的四个必要条件中的一个或几个。
  (2) 避免死锁。 用某种方法防止系统进入安全状态，从而避免死锁（银行家算法）。
  (3) 死锁的检测和解除。 允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后才去某种措施解除死锁。

  如果把只能互斥使用的资源改造成允许共享使用，则系统不会进入死锁状态。如 SPOOLing技术 。操作系统可以采用SPOOLing技术吧独占设备在逻辑上改造成共享设备。 它由专门负责 I/O 的常驻内存进程以及输入、输出井组成。 比如，用SPOOLing技术将打印机改造为共享设备...

  缺点：并不是所有的资源都可以改造成共享使用的资源。并且为了系统安全，有时候还需要保护这种互斥性。

  方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时重新申请。
  方案二：申请的资源被其他进程占用时，借助操作系统的协助，剥夺进程资源，至于剥夺哪个进程资源可以根据优先级考虑。
  缺点：实现复杂。暂时请求不到某个资源，之前获取的资源就需要释放，以后重新申请，如果一直这样可能会导致饥饿。

  可以采用 静态分配方法 ，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足之前，不让它运行。一旦运行，这些资源在运行期间一直归它所有，该进程就不会再请求别的任何资源。
  缺点：如果有些资源只需要用很短的时间，因此如果进程运行时间长，在运行期间都会保持持有所有资源，就会造成资源浪费， 资源利用率低。 此外，该策略可能导致某些进程饥饿。如下，如果C类进程需要资源1和资源2，如果有大量的A或B类进程，就会导致C类进程一直不能一次获取全部需要的资源，导致饥饿。

  可采用 顺序资源分配法。 首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源一次申请完。
  原理：一个进程只要已占有我号的资源时，才有资格申请更大号编号的资源。按照这样的规则，已持有大编号的资源就不会逆向回来申请我号的资源，从而就不会产生循环等待的现象。
  缺点：
  (1) 实现复杂。
  (2) 不方便增加新的设备，因为要重新分配所有编号。
  (3) 进程实际使用资源的顺序可能和资源编号递增顺序不一致，会导致资源浪费。例如打印机设备编号2，输出设备编号为1，那么一个进程请求打印机设备前，必须先请求输出设备，而输出设备在请求打印机设备这一段时间内根本没有发挥作用，其他进程也不能访问，造成资源浪费。

  假如你是一个成功的银行家，手里有100个小目标资金....现在有三家公司A、B、C分别向从你贷款

  然而，有个规则，如果借给企业的钱达不到企业提出的最大需求，那么钱可能就一去不复返了.....
  刚开始，三家公司分别从你这里借了20、10、30亿.......

  此时，手里还要40亿，此时B表示还要借20亿，那么你需要考虑可以借吗？
  如果给B借了20亿.....此时手里还要有20亿。

  之后看手里剩下的钱能不能周转过来，现在可以将剩下的20亿借给C，C就达到了最大需求，之后C还钱50亿，然后借给A，A达到最大需求，最后A还70亿，最后A........还好借给B20亿后，可以通过 C->A->B 这个顺序周转，所以这20亿可以借。
  现在看另一种情况，回到最初状态，现在手里还有40亿

  对于上面的第一种借给B20亿是安全的，因为会存在C->A->B这样的周转路径（安全序列），不会血本无归。
   安全序列：如果系统按照这种序列分配资源，则每个进程都能顺利完成。 只要能找出一个安全序列，系统就是 安全的 。一个系统的 安全序列可能有多个 。
  如果分配了资源之后，系统中找不到任何一个安全序列，系统进入了 不安全状态 ，这就意味着之后可能所有的进程都无法顺序执行下去。当然，如果有进程提前归还了一些资源（如对上面的第二中情况，如果B提前还10亿，那么就可以周转了....），那系统也可能 重新回到安全状态 ，不过在分配资源之前总是考虑最坏情况 。
  如果系统处于 安全状态 ，就 一定不会发生死锁 。如果系统进入了不安全状态未必一定发生死锁，但是发生了死锁一定是在不安全状态。

   银行家算法 核心思想： 在进程提出资源请求时，先预先判断此次分配是否会导致系统进入不安全状态，如果进入不安全状态，就暂时不答应这次请求，让该进程先阻塞。
  银行家算法步骤：

  如果系统中既不采取预防死锁的措施，也不采取避免死锁的措施，系统就很可能发生死锁。在这种情况下，系统应当提供两个算法：
  (1) 死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁。
  (2) 死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来。

  系统死锁可利用 资源分配图 来描述。

  上图可以看到，R1类资源的资源数已经全部分配完了，R2类资源还有一个资源。P1进程向R2类资源请求一个资源，P2进程向R1类资源请求一个资源。
  如果系统中剩余可用的资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利的执行下去。如果这个进程执行结束了把资源归还给系统，就可能使某些正在等待的资源的进程重新被激活，并顺利的执行下去。相应的，这些被激活的进程执行完后又会归还一些资源，这样可能又会激活另外一些阻塞的进程...

  按照上面的过程分析，最终 能消除所有边 ，就称这个图是 可完全简化的 。此时一定 没有发生死锁 （相当于找到一个安全序列）。如果最终 不能消除所有边 ，那么此时就是 发生死锁了。
   最终还连着边的进程就是处于死锁状态的进程。
  检测死锁的算法：

   死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁。
  下图是一个系统死锁的图：

  即使P3释放了资源，P1和P2进程都不满足继续运行的条件，所以此时P1和P2就是死锁进程。

  解除死锁的方法有：
  (1) 资源剥夺法。 挂起（暂时放在外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他进程，但是应防止被挂起长时间导致饥饿。
  (2) 撤销进程法。 强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这中方法实现简单，但是也是有代价的，如果有些已经运行了很长时间了，离成功只有一步之遥了，此时撤销导致功亏一篑，还需要从头再来....
  (3) 进程回退法。 让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。

  那么对哪些进程动手呢？可以考虑优先对以下的进程处理：
  (1) 优先级低的进程。
  (2) 执行时间段的进程。
  (3) 距离运行结束剩余时间长的进程。
  (4) 使用资源多的进程。
  (5) 批处理式而不是交互式的进程。

3. 解决死锁的4种基本方法（值得收藏）

解决死锁的4种基本方法（文末有惊喜）

1、预防死锁：通过设置一些限制条件，去破坏产生死锁的必要条件

2、避免死锁：在资源分配过程中，使用某种方法避免系统进入不安全的状态，从而避免发生死锁

3、检测死锁：允许死锁的发生，但是通过系统的检测之后，采取一些措施，将死锁清除掉

4、解除死锁：该方法与检测死锁配合使用

死锁介绍

死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

产生条件

虽然进程在运行过程中，可能发生死锁，但死锁的发生也必须具备一定的条件，死锁的发生必须具备以下四个必要条件。

1）互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。

2）请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。

3）不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

4）环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。

小关注来一波，我为你们准备了最新java学习资料文档以及高清视频教程，有需要的小伙伴扫一扫更直接

4. 计算机死锁是什么意思

所谓死锁<DeadLock>:
是指两个或两个以上的进程在执行过程中,因争夺资源而造成的一种互相等待的现象,若无外力作用,它们都将无法推进下去.此时称系统处于死锁状态或系统产生了死锁,这些永远在互相等竺的进程称为死锁进程.
由于资源占用是互斥的，当某个进程提出申请资源后，使得有关进程在无外力协助下，永远分配不到必需的资源而无法继续运行，这就产生了一种特殊现象死锁。
一种情形，此时执行程序中两个或多个线程发生永久堵塞（等待），每个线程都在等待被其他线程占用并堵塞了的资源。例如，如果线程A锁住了记录1并等待记录2，而线程B锁住了记录2并等待记录1，这样两个线程就发生了死锁现象。
计算机系统中,如果系统的资源分配策略不当，更常见的可能是程序员写的程序有错误等，则会导致进程因竞争资源不当而产生死锁的现象。
理解了死锁的原因，尤其是产生死锁的四个必要条件，就可以最大可能地避免、预防和解除死锁。所以，在系统设计、进程调度等方面注意如何不让这四个必要条件成立，如何确定资源的合理分配算法，避免进程永久占据系统资源。此外，也要防止进程在处于等待状态的情况下占用资源,在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配
。因此，对资源的分配要给予合理的规划。
一、有序资源分配法
这种算法资源按某种规则系统中的所有资源统一编号（例如打印机为1、磁带机为2、磁盘为3、等等），申请时必须以上升的次序。系统要求申请进程：
1、对它所必须使用的而且属于同一类的所有资源，必须一次申请完；
2、在申请不同类资源时，必须按各类设备的编号依次申请。例如：进程PA，使用资源的顺序是R1，R2；
进程PB，使用资源的顺序是R1，R2；若采用动态分配有可能形成环路条件，造成死锁。
采用有序资源分配法：R1的编号为1，R2的编号为2；
PA：申请次序应是：R1，R2
PB：申请次序应是：R1，R2
这样就破坏了环路条件，避免了死锁的发生
二、银行算法
避免死锁算法中最有代表性的算法是Dijkstra
E.W
于1968年提出的银行家算法：
该算法需要检查申请者对资源的最大需求量，如果系统现存的各类资源可以满足申请者的请求，就满足申请者的请求。
这样申请者就可很快完成其计算，然后释放它占用的资源，从而保证了系统中的所有进程都能完成，所以可避免死锁的发生。

5. 死锁怎么解决

处理死锁的思路如下：

预防死锁：破坏四个必要条件中的一个或多个来预防死锁。

避免死锁：在资源动态分配的过程中，用某种方式防止系统进入不安全的状态。

检测死锁：运行时产生死锁，及时发现思索，将程序解脱出来。

解除死锁：发生死锁后，撤销进程，回收资源，分配给正在阻塞状态的进程。

预防死锁的办法：

破坏请求和保持条件：

1、一次性的申请所有资源。之后不在申请资源，如果不满足资源条件则得不到资源分配。

2、只获得初期资源运行，之后将运行完的资源释放，请求新的资源。

破坏不可抢占条件：当一个进程获得某种不可抢占资源，提出新的资源申请，若不能满足，则释放所有资源，以后需要，再次重新申请。

破坏循环等待条件：对资源进行排号，按照序号递增的顺序请求资源。若进程获得序号高的资源想要获取序号低的资源，就需要先释放序号高的资源。

(5)避免死锁的算法扩展阅读

形成死锁的四个必要条件：

（1） 互斥条件：一个资源每次只能被一个进程使用。

（2） 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。

（3） 不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。

（4） 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。

如果一组进程中每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程是死锁的。

举例来说：有两个进程A和B,A持有资源a等待b资源，B持有资源b等待a资源，两个进程都在等待另一个资源的同时不释放资源，就形成死锁。

6. 避免死锁的一个着名算法

避免死锁的着名算法是银行家算法。

算法有四个条件：

1、分批向银行贷款时，申请的总额不能超过一开始申请的额度；

2、申请贷款时不能超过银行现有资金数目；

3、当银行资金不能满足顾客贷款需求时，可以推迟支付，但是肯定会让顾客在需求时间内得到贷款；

4、顾客拿到贷款后必须在规定时间内归还。

7. 预防死锁的方法

1、避免一个线程同时获取多个锁。
2、避免一个线程在锁内同时占用多个资源，尽量保证每个锁只占用一个资源。
3、尝试使用定时锁，使用Lock.tryLock（timeout）来替代使用内部锁机制。
4、对于数据库锁，加锁和解锁须在一个数据库连接里，否则会出现解锁失败的情况。

8. 什么是死锁请给出预防死锁的方法(预防死锁的方法有哪些)

1、预防死锁的方法有哪些。

2、预防死锁的方法。

3、预防死锁的方法两种。

4、预防死锁的方法有哪两种。

1.避免一个线程同时获取多个锁。

2.避免一个线程在锁内同时占用多个资源，尽量保证每个锁只占用一个资源。

3.尝试使用定时锁，使用Lock.tryLock（timeout）来替代使用内部锁机制。

4.对于数据库锁，加锁和解锁须在一个数据库连接里，否则会出现解锁失败的情况。

5.产生死锁的原因主要是：因为系统资源不足。

6.进程运行推进的顺序不合适。

7.资源分配不当等。

8.如果系统资源充足，进程的资源请求都能够得到满足，死锁出现的可能性就很低，否则就会因争夺有限的资源而陷入死锁。

9.第二，进程运行推进顺序和速度不同，也可能产生死锁。

10.产生死锁的四个必要条件：互斥条件：一个资源每次只能被一个进程使用。

11.请求和保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。

12.不剥夺条件：进程已获得的资源，在末使用完之前，不能强行剥夺。

13.循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。

14.这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。

9. 解决死锁的4种基本方法

解决死锁的4种基本方法：

1、预防死锁：通过设置一些限制条件，去破坏产生死锁的必要条件。

2、避免死锁：在资源分配过程中，使用某种方法避免系统进入不安全的状态，从而避免发生死锁。

3、检测死锁：允许死锁的发生，但是通过系统的检测之后，采取一些措施，将死锁清除掉。

4、解除死锁：该方法与检测死锁配合使用。

产生条件

进程在运行过程中，可能发生死锁，但死锁的发生也必须具备一定的条件，死锁的发生必须具备以下四个必要条件。

1）互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。

2）请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。

3）不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

4）环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合｛P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。