死锁

操作系统名词

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

死锁的规范定义：集合中的每一个进程都在等待只能由本集合中的其他进程才能引发的事件，那么该组进程是死锁的。

一种情形，此时执行程序中两个或多个进程发生永久堵塞（等待），每个进程都在等待被其他进程占用并堵塞了的资源。例如，如果进程A锁住了记录1并等待记录2，而进程B锁住了记录2并等待记录1，这样两个进程就发生了死锁现象。

计算机系统中，如果系统的资源分配策略不当，更常见的可能是程序员写的程序有错误等，则会导致进程因竞争资源不当而产生死锁的现象。

在两个或多个任务中，如果每个任务锁定了其他任务试图锁定的资源，此时会造成这些任务永久阻塞，从而出现死锁。例如：事务A 获取了行 1 的共享锁。事务 B 获取了行 2 的共享锁。

排他锁，等待事务 B 完成并释放其对行 2 持有的共享锁之前被阻塞。

排他锁，等待事务 A 完成并释放其对行 1 持有的共享锁之前被阻塞。

事务 B 完成之后事务 A 才能完成，但是事务 B 由事务 A 阻塞。该条件也称为循环依赖关系：事务 A 依赖于事务 B，事务 B 通过对事务 A 的依赖关系关闭循环。

除非某个外部进程断开死锁，否则死锁中的两个事务都将无限期等待下去。Microsoft SQL Server 数据库引擎死锁监视器定期检查陷入死锁的任务。如果监视器检测到循环依赖关系，将选择其中一个任务作为牺牲品，然后终止其事务并提示错误。这样，其他任务就可以完成其事务。对于事务以错误终止的应用程序，它还可以重试该事务，但通常要等到与它一起陷入死锁的其他事务完成后执行。

在应用程序中使用特定编码约定可以减少应用程序导致死锁的机会。有关详细信息，请参阅将死锁减至最少。

死锁经常与正常阻塞混淆。事务请求被其他事务锁定的资源的锁时，发出请求的事务一直等到该锁被释放。默认情况下，除非设置了 LOCK_TIMEOUT，否则 SQL Server 事务不会超时。因为发出请求的事务未执行任何操作来阻塞拥有锁的事务，所以该事务是被阻塞，而不是陷入了死锁。最后，拥有锁的事务将完成并释放锁，然后发出请求底事务将获取锁并继续执行。

不只是关系数据库管理系统，任何多进程系统上都会发生死锁，并且对于数据库对象的锁之外的资源也会发生死锁。例如，多进程操作系统中的一个进程要获取一个或多个资源（例如，内存块）。如果要获取的资源当前为另一进程所拥有，则第一个进程可能必须等待拥有进程释放目标资源。这就是说，对于该特定资源，等待进程依赖于拥有进程。在数据库引擎实例中，当获取非数据库资源（例如，内存或进程）时，会话会死锁。

在示例中，对于 Part表锁资源，事务 T1 依赖于事务 T2。同样，对于 Supplier表锁资源，事务 T2 依赖于事务 T1。因为这些依赖关系形成了一个循环，所以在事务 T1 和事务 T2 之间存在死锁。

当表进行了分区并且 ALTER TABLE 的 LOCK_ESCALATION 设置设为 AUTO 时也会发生死锁。当 LOCK_ESCALATION 设为 AUTO 时，通过允许数据库引擎在 HoBT 级别而不是 TABLE 级别锁定表分区会增加并发情况。但是，当单独的事务在某个表中持有分区锁并希望在其他事务分区上的某处持有锁时，会导致发生死锁。通过将 LOCK_ESCALATION 设为 TABLE 可以避免这种类型的死锁，但此设置会因强制某个分区的大量更新以等待某个表锁而减少并发情况。

产生条件

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

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

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

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

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

产生原因

竞争资源引起进程死锁

当系统中供多个进程共享的资源如打印机、公用队列的等，其数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。

可剥夺资源和不可剥夺资源

系统中的资源可以分为两类，一类是可剥夺资源，是指某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺。例如，优先权高的进程可以剥夺优先权低的进程的处理机。又如，内存区可由存储器管理程序，把一个进程从一个存储区移到另一个存储区，此即剥夺了该进程原来占有的存储区，甚至可将一进程从内存调到外存上，可见，CPU和主存均属于可剥夺性资源。另一类资源是不可剥夺资源，当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等。

竞争不可剥夺资源

在系统中所配置的不可剥夺资源，由于它们的数量不能满足诸进程运行的需要，会使进程在运行过程中，因争夺这些资源而陷于僵局。例如，系统中只有一台打印机R1和一台磁带机R2，可供进程P1和P2共享。假定PI已占用了打印机R1，P2已占用了磁带机R2，若P2继续要求打印机R1，P2将阻塞；P1若又要求磁带机，P1也将阻塞。于是，在P1和P2之间就形成了僵局，两个进程都在等待对方释放自己所需要的资源，但是它们又都因不能继续获得自己所需要的资源而不能继续推进，从而也不能释放自己所占有的资源，以致进入死锁状态。

竞争临时资源

上面所说的打印机资源属于可顺序重复使用型资源，称为永久资源。还有一种所谓的临时资源，这是指由一个进程产生，被另一个进程使用，短时间后便无用的资源，故也称为消耗性资源，如硬件中断、信号、消息、缓冲区内的消息等，它也可能引起死锁。例如，SI，S2，S3是临时性资源，进程P1产生消息S1，又要求从P3接收消息S3；进程P3产生消息S3，又要求从进程P2处接收消息S2；进程P2产生消息S2，又要求从P1处接收产生的消息S1。如果消息通信按如下顺序进行：

P1: ···Relese（S1）；Request（S3）； ···

P2: ···Relese（S2）；Request（S1）； ···

P3: ···Relese（S3）；Request（S2）； ···

并不可能发生死锁。但若改成下述的运行顺序：

P1: ···Request（S3）；Relese（S1）；···

P2: ···Request（S1）；Relese（S2）； ···

P3: ···Request（S2）；Relese（S3）； ···

则可能发生死锁。

2.进程推进顺序不当引起死锁

由于进程在运行中具有异步性特征，这可能使P1和P2两个进程按下述两种顺序向前推进。

1）进程推进顺序合法

当进程P1和P2并发执行时，如果按照下述顺序推进：P1：Request（R1）； P1：Request（R2）； P1: Relese（R1）；P1: Relese（R2）； P2：Request（R2）； P2：Request（R1）； P2: Relese（R2）；P2: Relese（R1）；这两个进程便可顺利完成，这种不会引起进程死锁的推进顺序是合法的。

2）进程推进顺序非法

若P1保持了资源R1,P2保持了资源R2，系统处于不安全状态，因为这两个进程再向前推进，便可能发生死锁。例如，当P1运行到P1：Request（R2）时，将因R2已被P2占用而阻塞；当P2运行到P2：Request（R1）时，也将因R1已被P1占用而阻塞，于是发生进程死锁。

预防

理解了死锁的原因，尤其是产生死锁的四个必要条件，就可以最大可能地避免、预防和解除死锁。只要打破四个必要条件之一就能有效预防死锁的发生：打破互斥条件：改造独占性资源为虚拟资源，大部分资源已无法改造。打破不可抢占条件：当一进程占有一独占性资源后又申请一独占性资源而无法满足，则退出原占有的资源。打破占有且申请条件：采用资源预先分配策略，即进程运行前申请全部资源，满足则运行，不然就等待，这样就不会占有且申请。打破循环等待条件：实现资源有序分配策略，对所有设备实现分类编号，所有进程只能采用按序号递增的形式申请资源。

所以，在系统设计、进程调度等方面注意如何不让这四个必要条件成立，如何确定资源的合理分配算法，避免进程永久占据系统资源。此外，也要防止进程在处于等待状态的情况下占用资源,在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。因此，对资源的分配要给予合理的规划。

下面几种方法可用以避免重装死锁的发生：

①允许目的节点将不完整的报文递交给目的端系统；

②一个不能完整重装的报文能被检测出来，并要求发送该报文的源端系统重新传送；

③为每个节点配备一个后备缓冲空间，用以暂存不完整的报文。

①、②两种方法不能很满意地解决重装死锁，因为它们使端系统中的协议复杂化了。一般的设计中，网络层应该对端系统透明，也即端系统不该考虑诸如报文拆、装之类的事。③方法虽然不涉及端系统,但使每个节点增加了开销。

有序资源分配法

这种算法资源按某种规则系统中的所有资源统一编号（例如打印机为1、磁带机为2、磁盘为3、等等），申请时必须以上升的次序。系统要求申请进程：

1、对它所必须使用的而且属于同一类的所有资源，必须一次申请完；

2、在申请不同类资源时，必须按各类设备的编号依次申请。例如：进程PA，使用资源的顺序是R1，R2；进程PB，使用资源的顺序是R2，R1；若采用动态分配有可能形成环路条件，造成死锁。

采用有序资源分配法：R1的编号为1，R2的编号为2；

PA：申请次序应是：R1，R2

PB：申请次序应是：R1，R2

这样就破坏了环路条件，避免了死锁的发生

银行家算法

避免死锁算法中最有代表性的算法是Dijkstra E.W 于1965年提出的银行家算法：

银行家算法是避免死锁的一种重要方法，防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。通过这个算法可以用来解决生活中的实际问题，如银行贷款等。

程序实现思路银行家算法顾名思义是来源于银行的借贷业务，一定数量的本金要应多个客户的借贷周转，为了防止银行家资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内归还资源，以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源，则进程都无法继续执行下去的死锁现象。

把一个进程需要和已占有资源的情况记录在进程控制中，假定进程控制块PCB其中“状态”有就绪态、等待态和完成态。当进程在处于等待态时，表示系统不能满足该进程当前的资源申请。“资源需求总量”表示进程在整个执行过程中总共要申请的资源量。显然，每个进程的资源需求总量不能超过系统拥有的资源总数，银行算法进行资源分配可以避免死锁。

解决方法

在系统中已经出现死锁后，应该及时检测到死锁的发生，并采取适当的措施来解除死锁。

死锁预防。

这是一种较简单和直观的事先预防的方法。方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或者几个，来预防发生死锁。预防死锁是一种较易实现的方法，已被广泛使用。但是由于所施加的限制条件往往太严格，可能会导致系统资源利用率和系统吞吐量降低。

死锁避免。

系统对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源；如果分配后系统可能发生死锁，则不予分配，否则予以分配。这是一种保证系统不进入死锁状态的动态策略。

死锁检测和解除。

先检测：这种方法并不须事先采取任何限制性措施，也不必检查系统是否已经进入不安全区，此方法允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源。检测方法包括定时检测、效率低时检测、进程等待时检测等。

然后解除死锁：采取适当措施，从系统中将已发生的死锁清除掉。

这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。死锁的检测和解除措施，有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。

排除方法

1、撤消陷于死锁的全部进程；

2、逐个撤消陷于死锁的进程，直到死锁不存在；

3、从陷于死锁的进程中逐个强迫放弃所占用的资源，直至死锁消失。

4、从另外一些进程那里强行剥夺足够数量的资源分配给死锁进程，以解除死锁状态

计算机网络的死锁

死锁是网络中最容易发生的故障之一，即使在网络负荷不很重时也会发生。死锁发生时，一组节点由于没有空闲缓冲区而无法接收和转发分组，节点之间相互等待，既不能接收分组也不能转发分组，并一直保持这一僵局，严重时甚至导致整个网络的瘫痪。此时，只能靠人工干预来重新启动网络，解除死锁。但重新启动后并未消除引起死锁的隐患，所以可能再次发生死锁。死锁是由于控制技术方面的某些缺陷所引起的，起因通常难以捉摸、难以发现，即使发现，也常常不能立即修复。因此，在各层协议中都必须考虑如何避免死锁的问题。

存储转发死锁及其防止

最常见的死锁是发生在两个节点之间的直接存储转发死锁。例如，A节点的所有缓冲区装满了等待输出到B节点的分组，而B节点的所有缓冲区也全部装满了等待输出到A节点的分组；此时，A节点不能从B节点接收分组，B节点也不能从A节点接收分组，从而造成两节点间的死锁。这种情况也可能发生在一组节点之间，例如，A节点企图向B节点发送分组、B节点企图向C节点发送分组、而C节点又企图向A节点发送分组，但此时每个节点都无空闲缓冲区用于接收分组，这种情形称做间接存储转发死锁。当一个节点处于死锁状态时，所有与之相连的链路将被完全拥塞。

一种防止存储转发死锁的方法是，每个节点设置M+1个缓冲区，并以0到M编号。M为通信子网的直径，即从任一源节点到任一目的节点间的最大链路段数。每个源节点仅当其0号缓冲区空时才能接收源端系统来的分组，而此分组仅能转发给1号缓冲区空闲的相邻节点，再由该节点将分组转发给它的2号缓冲区空闲的相邻节点……最后，该分组或者顺利到达目的节点并被递交给目的端系统，或者到了某个节点编号为M的缓冲区中再也转发不下去，此时一定发生了循环,应该将该分组丢弃。由于每个分组都是按照编号递增规则分配缓冲区，所以节点之间不会相互等待空闲缓冲区而发生死锁现象。这种方法的不足之处在于，当某节点虽然有空闲缓冲区，但正巧没有所需要的特定编号的缓冲区时，分组仍要等待，从而造成了缓冲区和链路的浪费。

缓冲区，而其它缓冲区均可用于存放中转分组。在每条输出链路的队列上分组按时间戳顺序排队。例如，节点A要将分组送到节点B，若B节点没有空闲缓冲区，但正巧有要送到A节点的分组，此时A、B节点可通过特殊的接收缓冲区交换分组；若B节点既没有空闲缓冲区，也没有要送往A节点的分组，B节点只好强行将一个出路方向大致与A节点方向相同的分组与A节点互相交换分组，但此时A节点中的分组必须比B节点中的分组具有更早的时间戳，这样才能保证子网中某个最早的分组不受阻挡地转发到目的地。由此可见，每个分组最终总会成为最早的分组，并总能被一步一步地发送到目的节点，从而避免了死锁现象的发生。

重装死锁及其防止

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省