死锁相关问题

标签：抢占 lock 问题死锁线程进程相关资源

什么是死锁

死锁是指两个(或多个)线程相互等待对方数据的过程，死锁的产生会导致程序卡死，不解锁程序将永远无法进行下去。

资源

大部分的死锁都和资源有关，在进程对设备、文件具有独占性（排他性）时会产生死锁。把这类需要排他性使用的对象称为资(resource)。资源主要分为可抢占资源和不可抢占资源

可抢占资源和不可抢占资源

资源主要有可抢占资源和不可抢占资源。

可抢占资源(preemptable resource) 可以从拥有它的进程中抢占而不会造成其他影响，内存就是一种可抢占性资源，任何进程都能够抢先获得内存的使用权。
不可抢占资源(nonpreemtable resource) 指的是除非引起错误或者异常，否则进程无法抢占指定资源，这种不可抢占的资源比如有光盘，在进程执行调度的过程中，其他进程是不能得到该资源的。

死锁与不可抢占资源有关，虽然抢占式资源也会造成死锁，不过这种情况的解决办法通常是在进程之间重新分配资源来化解

死锁的原因

举个例子：
前提条件：两个线程A和B，两个数据1和2。
步骤：线程A在执行过程中，首先对资源1加锁，然后再去给资源2加锁，但是由于线程的切换，导致线程A没能给资源2加锁。线程切换到B后，线程B先对资源2加锁，然后再去给资源1加锁，由于资源1已经被线程A加锁，因此线程B无法加锁成功，当线程切换为A时，A也无法成功对资源2加锁，由此就造成了线程AB双方相互对一个已加锁资源的等待，死锁产生。

理论上，死锁产生有以下四个必要条件，缺一不可：

1 互斥条件

进程对所需求的资源具有排他性，若有其他进程请求该资源，请求进程只能等待

2 不剥夺条件

又称不可抢占，已获资源只能由进程自愿释放，不允许被其他进程剥夺

3 请求和保持条件

进程在请求资源得不到满足而等待时，不释放已占有资源

4 循环等待条件

又称环路条件，存在循环等待链，其中，每个进程都在等待链中等待下一个进程所持有的资源，造成这组进程处于永远等待状态

死锁举例：

#include <iostream>
#include <thread>
#include <mutex>
using namespace std;
 
mutex mt1;
mutex mt2;
void thread1()
{
    cout << "thread1 begin" << endl;
    lock_guard<mutex> guard1(mt1);
    this_thread::sleep_for(chrono::seconds(1));
    lock_guard<mutex> guard2(mt2);
    cout << "hello thread1" << endl;
}
void thread2()
{
    cout << "thread2 begin" << endl;
    lock_guard<mutex> guard1(mt2);
    this_thread::sleep_for(chrono::seconds(1));
    lock_guard<mutex> guard2(mt1);
    cout << "hello thread2" << endl;
}
 
int main()
{
    thread t1(thread1);
    thread t2(thread2);
    t1.join();
    t2.join();
    cout << "thread end" << endl;
    return 0;
}

因为程序运行的是非常快的，所以为了产生死锁现象，我们各自休眠了1秒。

运行以上程序可以发现，程序在输出完“thread1 beginthread2 begin”后，就卡在那里，程序运行可能发生了以下这种情况：

thread1	thread2
mt1.lock()	mt2.lock()
//死锁	//死锁
mt2.lock()	mt1.lock()

thread1中的mt2在等待thread2中的mt2释放锁，而thread2中的mt1在等待thread1中的mt1释放锁，互相等待对方释放锁，进而产生了死锁。

死锁的解决方案

保证上锁的顺序一致
比如像上面thread1和thread2线程，我们每次都先锁mt1，在锁mt2，就不会发生死锁现象
给锁定义一个层次的属性，每次按层次由高到低的顺序上锁，这个原理也是每次都先锁同一个锁

C++标准库中提供了std::lock()函数，能够保证将多个互斥锁同时上锁。

std::lock(mt1, mt2);

那么既然在最前面就已经上锁了，后面就不需要上锁了，而C++标准库并没有提供std::unlock()的用法，所以还是需要用到lock_guard，但是需要修改一点。加个std::adopt_lock就可以了。

lock_guard<mutex> guard1(mt1, adopt_lock);
lock_guard<mutex> guard2(mt2, adopt_lock);

这个表示构造函数的时候不要给我上锁，到析构的时候你要记得给我解锁。

处理方法

主要有以下四种方法：

鸵鸟策略
死锁检测与死锁恢复
死锁预防
死锁避免

鸵鸟策略

把头埋在沙子里，假装根本没发生问题。
因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。
当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。
大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

死锁检测与死锁恢复

不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。

死锁检测

1、每种类型一个资源的死锁检测

上图为资源分配图，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。

图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此会发生死锁。

每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。

2、每种类型多个资源的死锁检测

上图中，有三个进程四个资源，每个数据代表的含义如下：

E 向量：资源总量
A 向量：资源剩余量
C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量
R 矩阵：每个进程请求的资源数量

进程 P1 和 P2 所请求的资源都得不到满足，只有进程 P3 可以，让 P3 执行，之后释放 P3 拥有的资源，此时 A = (2 2 2 0)。P2 可以执行，执行后释放 P2 拥有的资源，A = (4 2 2 1) 。P1 也可以执行。所有进程都可以顺利执行，没有死锁。

算法总结如下：
每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。

寻找一个没有标记的进程 Pi，它所请求的资源小于等于 A。
如果找到了这样一个进程，那么将 C 矩阵的第 i 行向量加到 A 中，标记该进程，并转回 1。
如果没有这样一个进程，算法终止。

死锁恢复

利用抢占恢复
利用回滚恢复
通过杀死进程恢复

死锁预防

在程序运行之前预防发生死锁。

破坏互斥条件
例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。
破坏请求和保持条件
一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。
破坏不剥夺条件
允许抢占资源
破坏循环请求等待
给资源统一编号，进程只能按编号顺序来请求资源。

死锁避免

在程序运行时避免发生死锁。

安全状态

图 a 的第二列 Has 表示已拥有的资源数，第三列 Max 表示总共需要的资源数，Free 表示还有可以使用的资源数。从图 a 开始出发，先让 B 拥有所需的所有资源（图 b），运行结束后释放 B，此时 Free 变为5（图 c）；接着以同样的方式运行 C 和 A，使得所有进程都能成功运行，因此可以称图 a 所示的状态时安全的。

定义：如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。安全状态的检测与死锁的检测类似，因为安全状态必须要求不能发生死锁。

下面的银行家算法与死锁检测算法非常类似，可以结合着做参考对比。

单个资源的银行家算法
一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。

上图 c 为不安全状态，因此算法会拒绝之前的请求，从而避免进入图 c 中的状态。

多个资源的银行家算法

上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。

检查一个状态是否安全的算法如下：

查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。
假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。
重复以上两步，直到所有进程都标记为终止，则状态时安全的。

如果一个状态不是安全的，需要拒绝进入这个状态。

死锁问题排查

举例：

#include <iostream>
#include <thread>
#include <mutex>

using namespace std;

mutex mtxA;
mutex mtxB;

void taskA() {
    lock_guard<mutex> lockA(mtxA);
    cout << "Thread A get Lock A!" << endl;
    this_thread::sleep_for(chrono::seconds(1));
    lock_guard<mutex> lockB(mtxB);
    cout << "Thread A get Lock A and B!" << endl;
    cout << "Thread A relese all source!" << endl;
}

void taskB() {
    lock_guard<mutex> lockB(mtxB);
    cout << "Thread B get Lock B!" << endl;
    this_thread::sleep_for(chrono::seconds(1));
    lock_guard<mutex> lockA(mtxA);
    cout << "Thread B get Lock B and A!" << endl;
    cout << "Thread B relese all source!" << endl;
}
  
int main() {

    thread t1(taskA);
    thread t2(taskB);

    t1.join();
    t2.join();
    return 0;
}

运行结果：

首先，怀疑一个程序发生了死锁，首先可以查看该进程CPU利用率、内存利用率的情况。因为如果发生了死锁（这里假设是互斥锁），进程里面发生死锁的线程会处于阻塞的状态，此时基本不占有CPU，因此CPU的利用率、内存占有率将会比较低。我们可以使用 ps aux 命令来拿到一个进程的状态：

这里可以看见有两个和deadLock相关的进程：14916、15144。后面一个是执行了grep这个命令之后产生的进程，所以第一个进程是我们想排查的进程。

然后，使用 top 命令来查看进程的CPU利用率、内存占有率：

top -Hp 14916

可以看见，这个进程里面一共存在三个线程。仔细思考，应该是对应线程t1、t2、和 main线程。它们的CPU利用率、内存都是0，很有可能发生了死锁。

此时，进程已经运行起来了。在实际的项目中，我们一般也不可能把一个进程停掉用GDB调试。因此，只能用GDB 的 attach 命令来跟踪这个进程：
首先，需要切换到root权限（本地环境为ubuntu操作系统）

sudo -i

然后：

gdb attach 14916

查看三个线程的堆栈调用情况：

thread apply all bt

下一步我们单独查看每个线程的堆栈调用情况
info threads

futex_wait函数有三个参数：private、expected和futex_word。

private参数是一个标志，用于指示futex_word参数是否是私有的。如果private为0，则futex_word是共享的；如果private为1，则futex_word是私有的。

expected参数是一个期望值，用于指定线程等待的条件。当futex_word的值等于expected时，线程将继续执行；否则，线程将被阻塞。

futex_word参数是一个指向共享变量的指针，它用于存储线程等待的条件和状态。

PS: 这里不知道为什么解析出来的futex_word = mtxB解析成了mtx

使用thread+线程索引来切换到某个线程，并使用bt来查看堆栈当前线程的堆栈调用：

对应到源代码：

至此，基本就确定了死锁的原因了。

参考：
https://zhuanlan.zhihu.com/p/349312853
https://zhuanlan.zhihu.com/p/343539779
Linux下排除死锁详细教程（基于C++11、GDB）

标签：抢占,lock,问题,死锁,线程,进程,相关,资源
From： https://www.cnblogs.com/whiteBear/p/17604777.html