深入浅出理解死锁（以吃鸡游戏为例）

太过爱你忘了你带给我的痛 2022-05-13 03:46 253阅读 0赞

*  定义
 *  死锁条件
 *  死锁解决和预防
    
     *  避免互斥条件
     *  避免占有且等待
     *  避免不可抢占
     *  避免循环等待
 *  银行家算法
    
     *  算法背景
     *  算法原理

文章转载自微信公众号：漫话编程

# 定义 #

死锁（英语：Deadlock），计算机科学名词。当两个以上的运算单元，双方都在等待对方停止运行，以获取系统资源，但是没有一方提前退出时，就称为死锁。

举一个简单的例子就很容易理解什么是死锁了。

我和女朋友一起玩绝地求生，我捡到了一把98K，女朋友捡到了一个八倍镜。我手里有98K，想要女朋友包里的八倍镜。女朋友包里有八倍镜，想要我手里的98K。如果我不把98K给女朋友，女朋友也不把八倍镜给我。那我们两个之间就出现了死锁。（我们假设这个游戏中只有一把98K和一个八倍镜。并且我和女朋友都不会打死对方并抢夺装备）

# 死锁条件 #

在吃鸡游戏中，出现死锁的前提是满足了以下几个条件的：

1、互斥条件：一把98K只能同时被一个人捡起来，无法被多个人同时捡起来。八倍镜也一样。

2、占有且等待：持有98K的人希望拿到八倍镜，并且不愿意放弃手里的98K。持有八倍镜的人也一样。

3、不可强行占有：持有98K和八倍镜的人不会从对方手里直接把东西抢过来。

4、循环等待条件：两个人分别持有98K和八倍镜，并且需要同时拥有98K和八倍镜才能大杀四方。

以上就是死锁的四个条件。映射到计算机系统中，分别对应着：

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

2、占有且等待：一个进程因请求资源而阻塞时，对已获得的资源保持不放。

3、不可强行占有：进程已获得的资源，在末使用完之前，不能强行剥夺。

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

这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立。

# 死锁解决和预防 #

前面提到过死锁的四个必要条件，也就是说，只有在这四个条件同时满足的时候才会出现死锁。

那么，想要解决死锁，就想办法破坏四个条件中的任意一个就可以了。

比如吃鸡游戏，如果发生了死锁的话，比较简单的方式就是其中一个放弃装备，让另外一个人捡起来就可以了（破坏占有且等待条件）。或者就是其中一个人把另外一个人打死，然后舔他的包（破坏不可强行占有条件）。

所以，对于计算机系统中的死锁，预防方式就是避免以上四个条件同时出现。共有以下四个大类：

## 避免互斥条件 ##

允许进程同时访问某些资源。但是，有的资源是不允许被同时访问的，这是由资源本身的属性所决定的。所以，这种办法并无实用价值。

## 避免占有且等待 ##

为预防占有且等待条件，可以要求进程一次性的请求所有需要的资源，并且阻塞这个进程直到所有请求都同时满足。这个方法比较低效。

还有一种方式，就是如果占有某些资源的一个进程进行进一步资源请求时被拒绝，则该进程立刻释放它最初占有的资源。

## 避免不可抢占 ##

如果一个进程请求当前被另一个进程占有的一个资源，则操作系统可以抢占另外一个进程，要求它释放资源。

## 避免循环等待 ##

实行资源有序分配策略。如果一个进程已经分配了R类资源，那么接下来请求的资源只能是那些排在R类型之后的资源类型。

# 银行家算法 #

银行家算法（Banker’s Algorithm）是一个避免死锁的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。

## 算法背景 ##

在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。

## 算法原理 ##

我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。  
为保证资金的安全，银行家规定：

> (1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；
> 
> (2) 顾客可以分期贷款，但贷款的总数不能超过最大需求量；
> 
> (3) 当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；
> 
> (4) 当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金.

操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。