死锁（Deadlock）：指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，这些进程都将永远不能再向前推进。

对资源不加限制地分配可能导致进程间由于竞争资源而相互制约以至于无法继续运行的局面，人们把这种局面称为死锁 (deadlock)。

可重用性资源和可消耗性资源

➢ 可重用性资源：一次只能分配给一个进程，不允许多个进程共享，遵循：

➢ 请求资源 - 使用资源 - 释放资源 （大部分资源）。

➢ 可消耗性资源：由进程动态创建和消耗 （进程间通信的消息）。

可抢占性和不可抢占性资源

➢ 可抢占性资源：某进程在获得这类资源后，该资源可以再被其他进程或系统抢占，CPU（处理机）和主存区。

➢ 不可抢占资源：当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，打印机、磁带机。

竞争不可抢占性资源引起死锁

➢ 系统中的不可抢占性资源，由于它们的数量不能满足诸进程运行的需要，会使进程在运行过程中，因争夺这些资源而陷入僵局

竞争可消耗性资源引起死锁

➢ 临时性资源，是指由一个进程产生，被另一个进程使用一短暂时间后便无用的资源，故也称之为消耗性资源，它也可能引起死锁

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

➢ 进程推进顺序合法

➢ 进程推进顺序非法

死锁：一组等待的进程，其中每一个进程都持有资源，并且等待着由这个组中其他进程所持有的资源

 

资源分配图组成

 

无死锁的资源分配图

 

有死锁的资源分配图

 

如果图没有环，那么不会有死锁。

如果图有环，那么：

➢ 如果每一种资源类型只有一个实例，那么死锁发生；

➢ 如果一种资源类型有多个实例，那么可能死锁

在资源分配图中，找出一个既不阻塞又非独立的进程结点pi。

p1释放资源后，便可使p2获得资源而继续运行，直到p2完成后又释放出它所占有的全部资源；

在进行一系列的简化后，若能消去图中所有的边，使所有进程都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的

 

预防死锁

破坏死锁的四个必要条件中的一个或几个

互斥：互斥条件是共享资源必须的，不仅不能改变，还应加以保证

请求和保持：必须保证进程申请资源的时候没有占有其他资源

➢ 要求进程在执行前一次性申请全部的资源，只有没有占有资源时才可以分配资源

➢ 资源利用率低，可能出现饥饿

非抢占：

➢ 如果一个进程的申请没有实现，它要释放所有占有的资源；

➢ 先占的资源放入进程等待资源列表中；

➢ 进程在重新得到旧的资源的时候可以重新开始。

循环等待：对所有的资源类型排序进行线性排序，并赋予不同的序号，要求进程按照递增顺序申请资源。

➢ 如何规定每种资源的序号是十分重要的；

➢ 限制新类型设备的增加；

➢ 作业使用资源的顺序与系统规定的顺序不同；

➢ 限制用户简单、自主的编程。

当进程申请一个有效的资源的时候，系统必须确定分配后是安全的。

➢ 如果存在一个安全序列，则系统处于安全态。

进程序列<P1, P2, …, Pn>是安全的，如果每一个进程Pi所申请的可以被满足的资源数加上其他进程所持有的该资源数小于系统总数。

银行家算法

 

银行家算法的数据结构

n为进程的数目，m为资源类型的数目

Available: 长度为 m的向量。 如果available[j]=k,那么资源Rj有k个实例有效

Max: n x m 矩阵。 如果Max[i,j]=k,那么进程Pi可以最多请求资源Rj的k个实例

Allocation: n x m 矩阵。 如果Allocation[i,j]=k,那么进程Pj当前分配了k个资源Rj的实例

Need: n x m 矩阵。如果Need[i,j]=k,那么进程Pj还需要k个资源Rj的实例

Need [i,j] = Max[i,j] – Allocation [i,j]

常用解除死锁的两种方法：

抢占资源。从一个或多个进程中抢占足够数量的资源给死锁进程，以解除死锁状态

终止或撤消进程。终止系统中一个或多个死锁进程，直到打破循环环路，使死锁状态消除为止。

➢终止所有死锁进程（最简单方法）

➢逐个终止进程（稍温和方法）