死锁及银行家算法

哲学家就餐问题中的死锁

描述：在一张圆桌上，有n个哲学家，n支筷子，他们的生活方式只是交替地进行思考和进餐，饥饿时便试图取其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐，进餐完毕，放下筷子又继续思考
若n位哲学家都各自获取了一只筷子，此时所有哲学家都想获取第二只筷子去吃饭，但是共享资源n只筷子已经都被n位哲学家握在手里了，彼此想要的筷子都在其他哲学家手中，又没有机制能让任何哲学家放弃握在手中的筷子，从而照成了所有哲学家都在等待其他人手中资源的死锁问题

计算机中死锁的产生

计算机中的资源通常分为两类：一类叫可重用资源，一类叫可消耗资源
可重用资源
一次只能供给一个进程安全的使用，并不会因为使用而耗尽。当一个进程使用完后，该资源就被归还。然后可以再供给其他进程或线程使用。例如内存，外设，处理器等资源
可消耗资源
指可以被创建和销毁的资源。例如在生产者消费者模型中，生产者生产产品创建了资源，消费者取走产品从而销毁了资源。常见的有：信号，消息等资源

竞争可重用资源产生死锁
例如现在内存大小共有4G。进程1总共需要3G，进程2总共需要3.5G。进程1首先申请了2G内存，进程2首先申请了1.5G内存，此时内存总量还剩余0.5G
当进程1想要在申请剩余的1G时，内存资源不够了。进程2想要在申请2G时，内存当然也不够了。此时，进程1希望进程2释放它所拥有的1.5G内存。进程2希望进程1释放它所拥有的2G内存。双方都占着自己所拥有的资源等待着对方释放资源，此时二者便陷入了死锁状态

竞争可消耗资源产生死锁
进程1和进程2之间通过消息进行通信。
1 进程1发送消息m1给进程2
2 进程2发送消息m2给进程1
3 进程1接收消息m2
4 进程2接收消息m1
如果按上述的1234顺序执行，二者之间便可以进行正常通信。但是如果执行顺序为：3412，此时二者都会发生阻塞而造成死锁

当一组进程中中的各进程都在等待某个事件发生（通常是等待资源的释放）但能够触发该事件的进程正处于阻塞中。此时，这组进程就发生了死锁

死锁产生的四个必要条件
当以下四个条件均满足时，才会产生死锁。只要有一个不满足。就不会产生：
互斥条件：各进程对某一资源必须是互斥的访问，当一个进程在访问时，请他进程只能等待
请求和保持条件：指进程已经拥有了一个资源，还要在申请另一个资源
不可抢占条件：资源在只能被申请它的进程使用完后自动释放，请他进程不能抢占
循环等待条件：如进程1等待进程2所拥有的资源，进程2等待进程3所拥有的资源，进程3等待进程1所拥有的资源

避免死锁

破坏死锁的四个必要条件、加锁顺序一致、避免锁未释放的场景、资源一次性分配

银行家算法

设requesti是进程Pi的请求量，如果requesti[j]=k,表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查

1. 如果requesti[j]>need[I,j]则出错，因为进程所需要的资源数已经超过它需要的最大值
2. 如果requesi[j]>available[j]表示尚无足够的资源，Pi须等待
3. 系统试探着把资源分配给进程Pi，并修改available、allocation、need的数值
4. 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，已完成本次资源的分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待

检测当前状态是否安全：
设置变量work：表示系统可提供给进程继续运行的剩余资源数。初始时，work=Available
设置变量finash：表示系统是否有足够的资源分配给某进程。如果有finash为true，如果没有为false，初始时，假设finash[i]为false

1. 如果从进程集合中找到一个进程满足：finash[i]=false且Need[i,j]<work[j]，则继续往下执行，若无则，跳转3
2. 当进程i获取资源后，顺利执行，并释放资源：work[j]=work[j]+Allocation[i,j]；finash[i] = true；继续回到1执行
3. 当该进程组中所有进程的finash均变为true后，说明该系统处于安全状态。否则，为不安全状态

class Banker {
public:
    Banker(const std::vector<int>& available
           , const std::vector<std::vector<int>>& max
           , const std::vector<std::vector<int>>& allocation)
        : _processNum(max.size())
        , _resouceNum(max[0].size())
        , _available(available)
        , _max(max)
        , _allocation(allocation)
        , _need(_processNum, std::vector<int>(_resouceNum, 0)) {
        // 计算出需要的资源数
        for (int i = 0; i < _processNum; ++i) {
            for (int j = 0; j < _resouceNum; ++j) {
                _need[i][j] = _max[i][j] - _allocation[i][j];
            }
        }
    }

    // 输出安全序列
    void PrintSecurity() {
        std::cout << "安全序列为：" << std::endl;
        for (auto& i : _security) {
            std::cout << i << std::endl;
        }
    }

    // 判断请求算法
    bool CheckRequest(int id, const std::vector<int>& request) {
        // 检查资源请求是否合理
        for (int i = 0; i < _resouceNum; ++i) {
            // 请求资源数超过进程需求最大值
            if (request[i] > _need[id][i]) {
                std::cerr << "请求资源数超过进程需求最大值" << std::endl;
                return false;
            }

            // 尚无足够资源
            if (request[i] > _available[i]) {
                std::cerr << "尚无足够资源，进程等待" << std::endl;
                return false;
            }
        }

        // 尝试分配资源给进程，检测此次分配后系统是否处于安全状态
        for (int i = 0; i < _resouceNum; ++i) {
            _available[i] -= request[i];
            _allocation[id][i] += request[i];
            _need[id][i] -= request[i];
        }

        // 检查分配后系统是否安全
        if (_checkSafe()) {
            // 分配后系统安全，正式分配
            std::cerr << "进程：" << id << "分配资源成功" << std::endl;
            return true;
        } else {
            // 分配后不安全，分配失效，资源恢复
            std::cerr << "本次资源分配后系统不安全，分配失败" << std::endl;
            for (int i = 0; i < _resouceNum; i++) {
                _available[i] += request[i];
                _allocation[id][i] -= request[i];
                _need[id][i] += request[i];
            }
            return false;
        }
    }
private:
    // 检测安全性
    bool _checkSafe() {
        std::vector<int> work(_available);            // 系统可提供进程所需的资源数
        std::vector<bool> finish(_processNum, false); // 系统是否有足够资源给某进程

        while (1) {
            int i;
            for (i = 0; i < _processNum; ++i) {
                // 如果这个进程已经执行过，则跳过
                if (finish[i] == true) {
                    continue;
                }
                // 标志当前进程分配资源后是否安全
                bool flag = true;
                for (int j = 0; j < _resouceNum; j++) {
                    // 如果某一项资源不够分配，则说明当前进程不能执行，继续判断后面的
                    if (_need[i][j] > work[j]) {
                        flag = false;
                        break;
                    }
                }
                if (flag == true) {
                    // 加入安全序列中
                    _security.push_back(i);
                    // 调用进程运行，并且释放进程所占资源
                    for (int j = 0; j < _resouceNum; j++) {
                        work[j] += _allocation[i][j];
                        finish[i] = true;
                    }
                    // break进入下一轮查找安全进程，从头开始判断
                    break;
                }
            }
            if (i == _processNum) {
                // 有两种可能，若finish全为true则系统处于安全状态，否则系统处于不安全状态
                for (int j = 0; j < _processNum; ++j) {
                    if (finish[j] == false) {
                        std::cerr << "系统处于不安全状态" << std::endl;
                        return false;
                    }
                }
                // 系统处于安全状态
                return true;
            }
        }
    }
    std::vector<int> _security; // 安全序列
    int _processNum;	        // 进程数
    int _resouceNum;	        // 资源数
    // 可利用资源向量，_available[j]=K，表示j类资源剩余K个
    std::vector<int> _available;
    // 最大需求矩阵，_max[i,j]=K，表示进程i最大需求j类资源K个
    std::vector<std::vector<int>> _max;
    // 已分配矩阵，_allocation[i,j]=K，表示进程i已经被分配了j类资源K个
    std::vector<std::vector<int>> _allocation;
    // 需求矩阵，_need[i,j]=K，表示进程i还需要j类资源K个
    std::vector<std::vector<int>> _need;
};