死锁

简介

死锁是指两个或者两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信造成的一种阻塞现象，如果没有外力的作用，这些进程无法进行继续的工作，此时称系统产生了死锁，这些永远在互相等待的进程被称为死锁进程。

必要条件

• 互斥：每个资源要么已经分配给了一个进程要么是可用的
• 占有和等待：已经得到某种资源的进程可以继续请求其他资源
• 不可抢占：已经分配给某个进程的资源不能够被强制的剥夺，仅能等待拥有该资源的进程主动释放资源
• 环路等待：由两个或两个以上的进程形成一个环路，环路中每个进程都在等待下一个进程所拥有的资源

处理方法

针对死锁我们可以从多个方面来避免系统因死锁而收到影响。

鸵鸟策略

首先我们可以完全不管，因此如果死锁发生的概率很低或者即使发生了死锁也不会对用户带来多大的影响则可以直接忽略它，从而获得更高的性能。

死锁检测与死锁恢复

这种方法并不会避免死锁的发生，而是不断检测死锁，当发现系统进入死锁状态后采取一定措施进行恢复。死锁的检测可以大致分为两类，第一种是每种类型仅有一个资源的死锁检测，这种情况下可以构造出进程对资源的占有和请求的一张有向图，如果在这张有向图中检测出了环则证明发生了死锁。第二种是利用资源分配表，构造出如下数据表项：E向量(资源总量)，A向量(资源剩余量)，C矩阵(每个进程拥有的资源数)，R矩阵(每个进程请求的资源数量)，算法的流程可以描述为：1)寻找一个尚未标记为可完成的进程，且其请求的资源数小于A，2)找到进程后将C矩阵的第i行加到A中，并标记进程为已完成，继续1，3)如果没有找到可以完成运行的进程则终止。

如果检测到死锁发生后则需要进行死锁恢复，在进行恢复时可以利用抢占进行恢复；利用回滚恢复；通过杀死进程进行恢复。

死锁预防

这种方法希望能够在死锁发生前通过破坏死锁的必要条件来避免死锁的发生。其根据死锁的必要条件分为四种，1)破坏互斥条件，例如假脱机打印技术，让多个进程均允许请求打印机，2)破坏占有和等待条件，例如要求所有进程在运行前必须请求所有的资源，3)破坏不可抢占条件，4)破坏环路等待条件，例如给资源编号，进程仅能允许按照编号顺序来请求资源。

死锁避免

死锁避免发生在进程运行时，系统保证所有进程运行在安全状态，所谓安全状态表示即使所有进程突然最大程度的请求资源，系统也可以以一定的顺序调度进程，让所有进程均能够运行完成。死锁避免可以使用银行家算法，每次进行资源分配时均检查如果进行该次资源分配不会导致系统进入不安全状态则进行该资源的分配，否则则拒绝分配资源。当然需要注意的是系统进入不安全状态并不一定表示系统会出现死锁。