死锁与银行家算法

死锁

死锁作为多进(线)程开发中经常遇到的问题，其通常体现为多个进程和线程同时处于阻塞状态并且在没有任何外力干扰的情况下完全无法解除这种状态的情况。我们可以通过一个著名的场景来具体地理解死锁的概念。

哲学家用餐问题

哲学家用餐问题主要模型在一个圆桌上坐着n位哲学家，而每位哲学家的间隔处均放着一只筷子，所有的哲学家均处拥有进餐和思考两种状态，其中如果希望进入用餐状态则需要同时获得左右两边的筷子。
现在假设总共有5个哲学家，对应的就是5只筷子，画成图就如下所示 这张图来自于维基百科哲学家就餐问题,故筷子变成了叉子，将就看看吧(笑)

哲学家用餐问题与死锁

现在我们要在这个问题中引入死锁的问题，我们假设所有的哲学家同时希望就餐，此时他们同时拿起了他们左侧的筷子(叉子)，由于这群哲学家都是自私自利的，他们在成功就餐之前不会放弃手上的筷子(叉子)，故接下来他们在请求自己右边的叉子的时候所有的哲学家都不会获得在他们右手的筷子(叉子)，因为右边的筷子(叉子)均被他们各自右边的哲学家取走了，所以从这个时刻开始所有的哲学家均无法就餐，由于他们都不愿意放弃手上已经获得的筷子(叉子)，所以没有人会打破这个僵局，也就是说现在发生了死锁

常规的解决方案

由于哲学家问题涉及到的请求的资源种类单一，我们可以使用在之前学到的信号量机制轻松地解决这个问题。

服务生机制

第一种方法就是引入一个服务生，当哲学家需要进餐的时候他们将不会自己拿起自己的筷子(叉子)，而是由服务生检查他两侧是否有筷子(叉子)，如果都有的时候便由服务生拿起两侧的餐具交给这位哲学家，这样实现了在请求资源之前对资源进行检查，防止出现死锁的情况。 我们可以用伪代码实现如下，我们将会对哲学家进行编号，顺时针0-4，其中0号哲学家左边的筷子视作0号筷子，右边为1号，依次递增。

let waiter: Semaphore = 1;
let fork: Vec<Semaphore> = [1; 5];

fn philosopher(code:i32){
    waiter.wait();
    let ready = false;
    if fork[left].available() and fork[right].available(){
        fork[left].wait();
        fork[right].wait();
    }
    waiter.signal();
    if ready{
        //进餐
        fork[left].signal();
        fork[right].signal():
    }else{
        //左右筷子被占用，无法就餐
    } 
}

轮流进餐机制

第二种方法便是要求每次只能由一个哲学家要求进餐，也就是说当某个哲学家宣布自己要进餐的时候其他所有人都不能对自己身边的餐具进行请求，只能由要求进餐的这位哲学家拿起自己两侧的餐具进行就餐，就餐完毕之后其他人才能再次宣布自己要就餐。

let house: Semaphore = 1;
let fork: Vec<i32> = [1; 5];

fn philosopher(code: i32){
    house.wait();
    fork[left] = 0;
    fork[right] = 0;
    //就餐
    fork[left] = 1;
    fork[right] = 1;
    house.signal();
}

死锁的概念

从上面的问题，相信读者也对死锁有了一定的概念，对于死锁来说其自身的产生实际上有四个必要条件，而后续探讨的系统性的对死锁的解决同样基于这四个必要条件进行

• 互斥条件：多个线程之间请求的资源具有互斥性
• 不可剥夺条件：线程请求的资源是不可剥夺的
• 持有请求条件：当一个线程持有一个或多个资源的同时其会去请求其他线程所占有的资源，引起阻塞
• 循环等待条件：多个线程同时发生持有等待，同时这些线程持有的资源与请求的资源可以形成一个环。

死锁的解决

预防死锁

预防死锁实际上是最低效，最暴力，但是最简单的方法，其通过分别破坏死锁的四种条件完成对死锁的预防。

• 互斥条件：其作为系统的基本特征，无法破坏
• 持有请求条件：要求进程在创建时需要申请全部的资源，如果不满足的话直接阻止进程的创建
• 不可剥夺条件：要求进程在全部资源全部申请成功后才能执行，否则将进程阻塞
• 循环等待条件：按序申请，相当于对所有资源进行编号，进程在申请资源的时候必须严格按照序号进行申请

避免死锁

避免死锁相对于预防死锁来说性能更好，其的基本流程为判断申请资源的时候是否有死锁风险，如果没有的话则授予资源，否则阻塞进程直到资源可用。

安全与不安全的划分

当系统按照一定的顺序调度进程，如\(P_1, P_2, P_3...P_n\)，对于其中任何一个进程\(P_i\)均应当满足其所请求资源的最大需求，此时则视为安全，否则视为不安全。
此时，我们就需要构建一个算法用来计算得到这样一个进程序列。同时由于系统中的进程实际上是不断地在申请和释放资源的，故实际上系统的安全和不安全其实是在反复切换的。

银行家算法

银行家算法便是一种著名的用于实现避免死锁的算法。

数据结构

• 可用的资源量：Available，长度为n的向量
• 最大需求矩阵：Max，n行m列的矩阵
• 分配矩阵：Allocation，n行m列的矩阵
• 需求矩阵：Need，n行m列的矩阵
• 资源请求向量：Request，长度为m的向量，且Request_i[j]表示i进程对j资源的需求量

其中Max = Allocation + Need

算法过程

当进程i提出了Request_i的时候，将会执行以下操作

1. 若Request_i > Need[i]，出错
2. 若Request_i > Available，进程被阻塞
3. 当上述两步均通过，则开始试分配
   1. Available -= Request_i
   2. Allocation[i] += Request_i
   3. Need[i] -= Request_i
4. 允许安全性检测算法
5. 若第4步得到了一个安全的调度序列，则视作安全，分配内存，否则撤销该次预分配

安全性检测

在这一步中我们将会引入两个向量，分别为

• work向量，长度为n，其作为Available的一个替身
• finish向量，长度为m，其用于标记各进程的满足情况，初始化为全false

接下来我们需要按照如下的方式来对finish进行迭代
1. 找到一个同时满足finish[i] = false且Need[i] < work的进程i，假定其很快就会完成他的工作并归还资源，然后进行work += Allocation[i]和finish[i] = true，若找不到，则到第3步 2. 回到第1步 3. 如果finish全部为true则说明安全，反之则为不安全

总结

对于常规条件下的死锁问题，我们还会有很多的解决方案，包括上面提到的哲学家死锁问题，同样也还有其他的解法，本文的目的只在于介绍死锁问题和银行家算法。