死锁

死锁，即进程间的资源竞争陷入了一个循环等待的链，等待其他进程的资源但是自身占用了一定的资源。当进程链形成有向环且进程都等待时，系统处于死锁。

死锁产生的原因

系统资源的竞争 -- 系统资源分配不足但不可剥夺时才会出现死锁
进程推进顺序非法 -- 系统资源充足但是进程的资源申请与释放的顺序不合法，为此我们需要通过安全性检测与银行家算法得到合法的执行顺序。

死锁产生的必要条件

互斥访问 -- 资源只能一个进程访问，否则不会产生资源竞争。
不可剥夺条件
请求并保持条件 -- 如果进程申请资源不足，并不会释放当前拥有的资源而是保持占用。
循环等待

死锁的预防

死锁的预防即通过硬件手段扼杀死锁的产生，针对死锁产生的四个必要条件破坏。

破坏互斥条件 -- 基本不可行，对于类似于打印机的设备无法实现并行访问
破坏不可剥夺条件 -- 资源可抢夺，可能导致任务执行混乱，通常也不可行
破坏请求并保持条件 -- 进程不能在拥有不可剥夺资源时申请新资源。
- 静态资源分配：进程运行前一次性分配所有资源，资源不足则不执行。静态资源分配可能造成系统资源浪费与饥饿现象
- 动态申请并释放：进程可以申请资源，但是使用完拥有的资源释放后才能申请新资源
破坏循环等待条件 -- 基于编号分配资源，从而避免自然产生死锁环。

死锁避免

死锁避免是通过软件方式对当前执行状态下的进程序列进行安全性检验。

安全性检查

系统安全性检查是对于某个进程组，进程序列 $(P_1,\cdots ,P_n)$ 的执行是否不会发生死锁。如果在某个初始分配条件下的任何进程序列都是安全序列，则系统是安全的；反之，如果系统不安全，其不一定会陷入死锁，因为系统不一定会选择不安全序列执行。

#include <vector>
#include <stdexcept>

int num = 3;  // 3个进程
int resource = 2; // 2个互斥资源

std::vector<std::vector<int>> max(num,std::vector<int>(resource));
std::vector<std::vector<int>> allocate(num,std::vector<int>(resource));

std::vector<bool> finish(num,false);
std::vector<int> work(resource);   // 当前可用资源

for (int i = 0; i < num; i++){     // 顺序执行example， 检测P0-P1-P2序列
    std::vector<int> need(resource);
    int sign = 0;
    for (int j = 0; j < resource; j++){
        need[j] = max[i][j] - allocate[i][j];
        if (need[j] <= work[j]){
            sign ++;
        }
    }    
    if (sign == resource){
        finish[i] = true;
        for (int k = 0; k < resource; k++){
            work[k] += allocate[i][k];
        }
    }
    else{
        throw std::runtime_error("Unsafe process seq");
    }
}

银行家算法

银行家算法不需要遍历所有的安全序列。对于当前资源足够执行的进程，将试探性分配资源再通过安全性检查检测系统是否为安全状态，安全则正式分配，否则撤销分配。

死锁检测

死锁检测是在进程执行中，判断当前是否处于死锁状态，只根据当前的资源分配情况判断，而不进行进程的安全性检验与未来运行的预测。

通常通过资源分配图进行简化与判断。有向边从进程指向资源表示进程申请资源；从资源指向进程表示进程已经分配的资源。

简化：如果资源类中存在数量足够的资源，则将请求有向边反向；入股进程结点只有入度，则该进程资源分配足够，执行完成就可以删除相应入边并释放资源。

如果简化进程资源分配图仍然存在有向边，则系统处于死锁状态。基于此，可以归纳出

死锁定理：系统死锁当且仅当资源分配图不可完全简化

死锁解除

通过操作系统进行死锁状态的解除

资源剥夺 -- 挂起死锁进程并释放资源，分配给其他进程。可能存在进程长时间挂起而饥饿的现象
撤销进程 -- 终止死锁进程并回收资源。
进程回退 -- 回到未死锁状态并进行安全序列的执行。

死锁