【架构-20】死锁

什么是死锁？

死锁(Deadlock)是指两个或多个线程/进程在执行过程中,由于资源的互相占用和等待,而陷入一种互相等待的僵局,无法继续往下执行的情况。
产生死锁的四个必要条件:
（1）互斥条件(Mutual Exclusion)：至少有一个资源是非共享的,即在一个时间内只由一个线程/进程占用。
（2）占有并等待(Hold and Wait)：一个线程/进程已经占用了至少一个资源,并且在等待获取其他资源。
（3）不可剥夺(No Preemption)：资源只能被线程/进程自愿释放,不能被强制剥夺。
（4）循环等待(Circular Wait)：两个或多个线程/进程之间形成一种头尾相接的循环等待资源关系。

一个具体的死锁场景

如下:
假设有两个线程T1和T2,各自需要两个资源A和B。

（1）T1首先申请并获得了资源A,T2首先申请并获得了资源B。
（2）之后T1申请资源B,但被阻塞,因为资源B已经被T2占用。
（3）同时T2申请资源A,但也被阻塞,因为资源A已经被T1占用。
（4）此时双方都在等待对方释放资源,形成了死锁。

这种情况下,T1和T2将永远阻塞下去,无法继续执行,除非有外部干预。

因此,避免死锁的关键是要及时发现并及时打破其中的一个条件。通常可以通过合理的资源申请顺序、死锁检测和资源抢占等方式来预防和解决死锁问题。

常见的死锁场景

1. 多个线程/进程占用部分资源,又互相等待其他资源,形成循环等待。
2. 某个线程/进程获得资源后不及时释放,造成其他线程/进程无法获得所需资源。
3. 资源分配不合理,导致资源耗尽或分配不均。
4. 系统管理不善,未对资源访问顺序等进行合理控制。

如何预防死锁？

预防和避免死锁主要有以下几种常见的方法:

1. 合理的资源分配和申请顺序
   给每个线程/进程分配资源时遵循固定的顺序
   申请资源时按照固定顺序申请,防止循环等待
2. 死锁检测和解决
   动态检测系统中是否存在死锁
   一旦发现死锁,通过抢占资源或者回滚等方式打破死锁
3. 资源有限分配
   限制系统中资源的总量,防止资源耗尽
   合理分配资源,避免某些线程/进程占用太多资源
4. 破坏不可抢占条件
   允许强制从一个线程/进程中获取资源
   当资源被占用时,可以暂时将其抢占回来
5. 利用死锁避免算法
   如银行家算法等,动态检查并拒绝可能导致死锁的资源分配请求
6. 合理的线程/进程执行顺序
   按照一定的调度策略,合理安排线程/进程的执行顺序
7. 超时检测和处理
   对于长时间阻塞的线程/进程,可以主动超时中止,避免永久阻塞

总之,预防死锁需要从多个方面着手,既要从设计层面预防,又要在运行时动态监测和处理。只有采取多种措施,才能更好地避免和解决死锁问题。

银行家算法？

假设你是一家银行的银行家,你负责管理银行的资金分配。银行里有很多客户(相当于进程),每个客户都有一定的贷款需求(相当于资源需求)。

当一个新客户来申请贷款时,作为银行家你需要做以下几步:

1. 先弄清楚每个客户的最大贷款需求是多少(系统需要提前知道每个进程的最大资源需求)。
2. 你要保持一个可用资金池,记录银行当前还有多少可用的资金(相当于可用资源向量)。
3. 当新客户来申请贷款时,你要先检查能否满足他的需求,如果可以就批准贷款;如果不行,就暂时把他的申请放在等待队列里(相当于将该请求暂时保存)。
4. 你会定期检查等待队列里的申请,看看是否能安全地满足某些申请(相当于检查等待队列中的请求)。
5. 如果你能找到一个"安全序列",即按照某个顺序依次满足所有客户的贷款需求,那么说明系统处于安全状态,你可以批准贷款;否则你就拒绝贷款申请(相当于判断系统是否处于安全状态)。

这就是银行家算法的核心思想。它可以动态地检测系统是否处于安全状态,从而避免发生"死锁"(即客户永远无法获得贷款)。这种算法在操作系统、数据库等领域都有广泛应用。

银行家算法的基本思想和优点？

银行家算法(Banker’s Algorithm)是一种预防死锁的常见算法,它是由操作系统先驱E.W. Dijkstra提出的。

银行家算法的基本思想是:

1. 系统需要提前知道每个进程所需的最大资源需求。
2. 系统保持一个可用资源向量,记录当前系统中可用的各类资源数量。
3. 当进程请求资源时,系统先检查是否能满足这个请求,如果可以,则分配资源;如果不可以,则将该请求暂时保存在等待队列中。
4. 系统会周期性地检查等待队列中的请求,看是否可以安全地满足某些请求。
5. 如果系统能找到一个安全序列,即能按照这个序列依次满足所有进程的资源需求,则认为系统处于安全状态,可以分配资源。否则拒绝分配资源。

银行家算法的优点是:
（1）能够动态地检测系统是否处于安全状态,防止发生死锁。
（2）能够合理地分配资源,最大化资源利用率。
（3）相对简单易实现,可以应用于多种资源分配场景。