死锁

什么是死锁

死锁是指多个进程因竞争资源而造成的一种僵局(互相等待),若无外力作用,这些进程都将无法向前推进。例如,在某一个计算机系统中只有一台打印机和一台输入 设备,进程 P1 正占用输入设备,同时又提出使用打印机的请求,但此时打印机正被进程 P2 所占用,而 P2 在未释放打印机之前,又提出请求使用正被 P1 占用着的输入设备。这样两个进程相互无休止地等待下去,均无法继续执行,此时两个进程陷入死锁状态。

死锁产生的原因

  1. 系统资源的竞争

    系统资源的竞争导致系统资源不足,以及资源分配不当,导致死锁。

  2. 进程运行推进顺序不合适

    进程在运行过程中,请求和释放资源的顺序不当,会导致死锁。

死锁的四个必要条件

  1. 互斥条件:资源是独占的且排他使用,进程互斥使用资源,即任意时刻一个资源只能给一个进程使用,其他进程若申请一个资源,而该资源被另一进程占有时,则申请者等待直到资源被占有者释放。

  2. 不可剥夺条件:进程所获得的资源在未使用完毕之前,不被其他进程强行剥夺,而只能由获得该资源的进程资源释放。

  3. 请求和保持条件:进程每次申请它所需要的一部分资源,在申请新的资源的同时,继续占用已分配到的资源。

  4. 循环等待条件:在发生死锁时必然存在一个进程等待队列 {P1,P2,…,Pn},其中 P1 等待 P2 占有的资源,P2 等待 P3 占有的资源,…,Pn 等待 P1 占有的资源,形成一个进程等待环路,环路中每一个进程所占有的资源同时被另一个申请,也就是前一个进程占有后一个进程所深情地资源。

以上给出了导致死锁的四个必要条件,只要系统发生死锁则以上四个条件至少有一个成立。事实上循环等待的成立蕴含了前三个条件的成立,似乎没有必要列出然而考虑这些条件对死锁的预防是有利的,因为可以通过破坏四个条件中的任何一个来预防死锁的发生。

死锁预防

我们可以通过破坏死锁产生的 4 个必要条件来预防死锁,由于资源互斥是资源使用的固有特性是无法改变的。

  1. **破坏 “不可剥夺” 条件:**一个进程不能获得所需要的全部资源时便处于等待状态,等待期间他占有的资源将被隐式的释放重新加入到系统的资源列表中,可以被其他的进程使用,而等待的进程只有重新获得自己原有的资源以及新申请的资源才可以重新启动,执行。

  2. **破坏 ”请求与保持条件“:**第一种方法静态分配即每个进程在开始执行时就申请他所需要的全部资源。第二种是动态分配即每个进程在申请所需要的资源时他本身不占用系统资源。

  3. **破坏 “循环等待” 条件:**采用资源有序分配其基本思想是将系统中的所有资源顺序编号,将紧缺的,稀少的采用较大的编号,在申请资源时必须按照编号的顺序进行,一个进程只有获得较小编号的进程才能申请较大编号的进程。

死锁解除

  1. 资源剥夺法。挂起某些思索进程,并抢占它的资源,将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源时,而处于资源匮乏的状态。

  2. 进程撤销法。强制撤销一个或一部分进程并剥夺这些进程的资源。撤销的原则可以按进程的优先级和撤销进程代价的高低进行。

  3. 进程回退法。让一个或多个进程回退到足以回避死锁的地步,进程回退时资源释放资源而不是被剥夺。要求系统保持进程的历史信息,设置还原点。