1 死锁的概念

死锁，是指多个线程或者进程在运行过程中因争夺资源而造成的一种僵局，当进程或者线程
处于这种僵持状态，若无外力作用，它们将无法再向前推进。如下图所示，线程 A 想获取线
程 B 的锁，线程 B 想获取线程 C 的锁，线程 C 想获取线程 A 的锁，从而构建了一个资源获取环。

怎么理解一个线程想获取另一个线程的锁呢？
先定义锁，把pthread_mutex_t 理解为锁（实际是一种线程同步机制）
pthread_mutex_t r1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t r2 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t r3 = PTHREAD_MUTEX_INITIALIZER;
获取锁 pthread_mutex_lock(ra) pthread_mutex_lock(rb) pthread_mutex_lock(rc)
只有当 r1 r2 r3 被释放了，也就是调用 pthread_mutex_unlock(ra), ... 之后，相应的锁r1, r2, r3 才能被其它线程所获得，即pthread_mutex_lock，否则pthread_mutex_lock不成功，线程阻塞

用一段代码来演示这种死锁

pthread_mutex_t r1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t r2 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t r3 = PTHREAD_MUTEX_INITIALIZER;

void *t1_cb(void *arg) {
   
   

    pthread_mutex_lock(&r1);
    sleep(1);
    pthread_mutex_lock(&r2);    
    pthread_mutex_unlock(&r2);
    pthread_mutex_unlock(&r1);
}

void *t2_cb(void *arg) {
   
   
    pthread_mutex_lock(&r2);
    sleep(1);
    pthread_mutex_lock(&r1);
    pthread_mutex_unlock(&r1);
    pthread_mutex_unlock(&r2);
}

void *t3_cb(void *arg) {
   
   
    pthread_mutex_lock(&r3);
    sleep(1);
    pthread_mutex_lock(&r1);

    pthread_mutex_unlock(&r1);
    pthread_mutex_unlock(&r3);

}

// deadlock
// 
int main() {
   
   

    pthread_t t1, t2, t3;

    pthread_create(&t1, NULL, t1_cb, NULL);
    pthread_create(&t2, NULL, t2_cb, NULL);
    pthread_create(&t3, NULL, t3_cb, NULL);

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    pthread_join(t3, NULL);
    printf("complete\n");

}

程序将会 打印信息 “complete” ，不会退出，死锁。

为什么？

r1, r2, r3 都是互斥锁，同时只能被一个线程拥有（持有）（lock）一次
t1 持有r1 等 r2 unlock , t1 才会unlock r1
t2 持有r2 等 r3 unlock , t2 才会unlock r2
t3 持有r3 等 r1 unlock , t3 才会unlock r3

就这样，t1,t2,t3都等不到任何unlock，僵持住了，死锁

2 检测死锁

t1 持有r1 等 r2 unlock , t1 才会unlock r1
t2 持有r2 等 r3 unlock , t2 才会unlock r2
t3 持有r3 等 r1 unlock , t3 才会unlock r3
简化一下：
t1 等 r2 ，记作 t1-->r2
t2 等 r3 ，记作 t2-->r3
t3 等 r1 ，记作 t3-->r1
考虑一下t1,t2,t3都持有 各自的锁
t1 等 r2 ，记作 t1，r1-->r2
t2 等 r3 ，记作 t2，r2-->r3
t3 等 r1 ，记作 t3，r3-->r1
这里引申出有向图:

如果用代码实现检测出代码中的锁的申请存在上面的有向图结构，是不是就可以检测出代码中的死锁了？！

3 用代码实现死锁检测

思路：用dlsym对 pthread_mutex_lock ， pthread_mutex_unlock进行hook,
在hook的代码里面实现有向图边的建立与删除（在一个线程T中进行）：lock前建立有向图的边，unlock的时候删除这条边。
当程序出现死锁的时候，线程T中通多扫描所有的边，找出其中的有向图，从而得知哪里出现了死锁。

3.1 hook部分

if (!pthread_mutex_lock_f)
pthread_mutex_lock_f = dlsym(RTLD_NEXT, "pthread_mutex_lock");

if (!pthread_mutex_unlock_f)
pthread_mutex_unlock_f = dlsym(RTLD_NEXT, "pthread_mutex_unlock");

3.2 实现有向图的代码

数据结构

typedef unsigned long int uint64;


#define MAX        100

enum Type {
   
   PROCESS, RESOURCE};

struct source_type {
   
   

    uint64 id;
    enum Type type;

    uint64 lock_id;
    int degress;
};

struct vertex {
   
   

    struct source_type s;
    struct vertex *next;

};

struct task_graph {
   
   

    struct vertex list[MAX];
    int num;

    struct source_type locklist[MAX];
    int lockidx; //

    pthread_mutex_t mutex;
};

增删改查

struct vertex *create_vertex(struct source_type type) {
   
   
    struct vertex *tex = (struct vertex *)malloc(sizeof(struct vertex ));
    tex->s = type;
    tex->next = NULL;
    return tex;
}

int search_vertex(struct source_type type) {
   
   
    int i = 0;
    for (i = 0;i < tg->num;i ++) {
   
   
        if (tg->list[i].s.type == type.type && tg->list[i].s.id == type.id) {
   
   
            return i;
        }
    }
    return -1;
}

void add_vertex(struct source_type type) {
   
   
    if (search_vertex(type) == -1) {
   
   
        tg->list[tg->num].s = type;
        tg->list[tg->num].next = NULL;
        tg->num ++;
    }
}

int add_edge(struct source_type from, struct source_type to) {
   
   
    add_vertex(from);
    add_vertex(to);
    struct vertex *v = &(tg->list[search_vertex(from)]);
    while (v->next != NULL) {
   
   
        v = v->next;
    }
    v->next = create_vertex(to);
}


int verify_edge(struct source_type i, struct source_type j) {
   
   
    if (tg->num == 0) return 0;
    int idx = search_vertex(i);
    if (idx == -1) {
   
   
        return 0;
    }
    struct vertex *v = &(tg->list[idx]);
    while (v != NULL) {
   
   
        if (v->s.id == j.id) return 1;
        v = v->next;        
    }
    return 0;
}
int remove_edge(struct source_type from, struct source_type to) {
   
   

    int idxi = search_vertex(from);
    int idxj = search_vertex(to);

    if (idxi != -1 && idxj != -1) {
   
   

        struct vertex *v = &tg->list[idxi];
        struct vertex *remove;

        while (v->next != NULL) {
   
   

            if (v->next->s.id == to.id) {
   
   

                remove = v->next;
                v->next = v->next->next;
                free(remove);
                break;
            }
            v = v->next;
        }
    }
}

文章参考与<零声教育>的C/C++linux服务期高级架构系统教程学习:链接