C++后端开发（3.2.4）——手写死锁检测组件

1 死锁现象以及原理
2 死锁检测实现

小节提纲

死锁现象以及原理
pthread_mutex_lock/pthread_mutex_unlock disym的实现
有向图的构建
有向图dfs判断环的存在
三个原语操作lock_before，lock_after,unlock_after
死锁检程线程的实现

死锁的四个必要条件和解决办法

dlsym用法

1 死锁现象以及原理

1.1 死锁概念及产生原理

概念：多个并发进程因争夺系统资源而产生相互等待的现象。
原理：当一组进程中的每个进程都在等待某个事件发生，而只有这组进程中的其他进程才能触发该事件，这就称这组进程发生了死锁。
本质原因：

系统资源有限。
进程推进顺序不合理。

1.2 死锁产生的4个必要条件

互斥：某种资源一次只允许一个进程访问，即该资源一旦分配给某个进程，其他进程就不能再访问，直到该进程访问结束。
占有且等待：一个进程本身占有资源（一种或多种），同时还有资源未得到满足，正在等待其他进程释放该资源。
不可抢占：别人已经占有了某项资源，你不能因为自己也需要该资源，就去把别人的资源抢过来。
循环等待：存在一个进程链，使得每个进程都占有下一个进程所需的至少一种资源。

当以上四个条件均满足，必然会造成死锁，发生死锁的进程无法进行下去，它们所持有的资源也无法释放。这样会导致CPU的吞吐量下降。所以死锁情况是会浪费系统资源和影响计算机的使用性能的。那么，解决死锁问题就是相当有必要的了。

1.3 死锁举例

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

2 死锁检测实现

资源获取环可以采用图来存储，使用有向图来存储。线程 A 获取线程 B 已占用的锁，则为线程 A 指向线程 B。如何为线程 B 已占用的锁？运行过程线程 B 获取成功的锁。
检测的原理采用另一个线程定时对图进程检测是否有环的存在。

2.1 有向图的构建

2.1.1 图相关结构体

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 task_graph *tg = NULL;
int path[MAX + 1];
int visited[MAX];
int k = 0;
int deadlock = 0;

2.1.2 图算法，检测成环

// 创造顶点
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;
        }
    }
}

2.1.3 图算法的测试入口函数

int main()
{
#if 1
    tg = (struct task_graph *)malloc(sizeof(struct task_graph));
    tg->num = 0;

    struct source_type v1;
    v1.id = 1;
    v1.type = PROCESS;
    add_vertex(v1);

    struct source_type v2;
    v2.id = 2;
    v2.type = PROCESS;
    add_vertex(v2);

    struct source_type v3;
    v3.id = 3;
    v3.type = PROCESS;
    add_vertex(v3);

    struct source_type v4;
    v4.id = 4;
    v4.type = PROCESS;
    add_vertex(v4);

    struct source_type v5;
    v5.id = 5;
    v5.type = PROCESS;
    add_vertex(v5);

    add_edge(v1, v2);
    add_edge(v2, v3);
    add_edge(v3, v4);
    add_edge(v4, v5);
    add_edge(v3, v1);

    search_for_cycle(search_vertex(v1));
#endif
}

2.2 有向图dfs

2.2.1 有向图dfs判断环的存在

// 死锁打印
void print_deadlock(void)
{
    int i = 0;

    printf("deadlock : ");
    for (i = 0; i < k - 1; i++)
    {
        printf("%ld --> ", tg->list[path[i]].s.id);
    }

    printf("%ld\n", tg->list[path[i]].s.id);
}

// DFS
int DFS(int idx)
{
    struct vertex *ver = &tg->list[idx];
    if (visited[idx] == 1)
    {
        path[k++] = idx;
        print_deadlock();
        deadlock = 1;

        return 0;
    }

    visited[idx] = 1;
    path[k++] = idx;

    while (ver->next != NULL)
    {
        DFS(search_vertex(ver->next->s));
        k--;

        ver = ver->next;
    }

    return 1;
}

// 查找是否存在回环
int search_for_cycle(int idx)
{
    struct vertex *ver = &tg->list[idx];
    visited[idx] = 1;
    k = 0;
    path[k++] = idx;

    while (ver->next != NULL)
    {
        int i = 0;
        for (i = 0; i < tg->num; i++)
        {
            if (i == idx)
                continue;

            visited[i] = 0;
        }

        for (i = 1; i <= MAX; i++)
        {
            path[i] = -1;
        }
        k = 1;

        DFS(search_vertex(ver->next->s));
        ver = ver->next;
    }
}

2.2.2 通过另外开启线程，检测资源环。

// 查找死锁
void check_dead_lock(void)
{
    int i = 0;

    deadlock = 0;
    for (i = 0; i < tg->num; i++)
    {
        if (deadlock == 1)
            break;
        search_for_cycle(i);
    }

    if (deadlock == 0)
    {
        printf("no deadlock\n");
    }
}

// 死锁检测线程
static void *thread_routine(void *args)
{
    while (1)
    {
        sleep(5);
        check_dead_lock();
    }
}

// 开启死锁检测线程
void start_check(void)
{
    tg = (struct task_graph *)malloc(sizeof(struct task_graph));
    tg->num = 0;
    tg->lockidx = 0;

    pthread_t tid;

    pthread_create(&tid, NULL, thread_routine, NULL);
}

2.3 pthread_mutex_lock / pthread_mutex_unlock / disym的实现


// 上锁
int pthread_mutex_lock(pthread_mutex_t *mutex)
{
    pthread_t selfid = pthread_self(); //

    lock_before(selfid, (uint64)mutex);
    pthread_mutex_lock_f(mutex);
    lock_after(selfid, (uint64)mutex);
}

// 去锁
int pthread_mutex_unlock(pthread_mutex_t *mutex)
{

    pthread_t selfid = pthread_self();

    pthread_mutex_unlock_f(mutex);
    unlock_after(selfid, (uint64)mutex);
}

// hook函数    dlsym的使用
static int init_hook()
{
    pthread_mutex_lock_f = dlsym(RTLD_NEXT, "pthread_mutex_lock");

    pthread_mutex_unlock_f = dlsym(RTLD_NEXT, "pthread_mutex_unlock");
}

2.4 三个原语操作lock_before / lock_after / unlock_after

// 三大原语
// 加锁之前
void lock_before(uint64 thread_id, uint64 lockaddr)
{

    int idx = 0;
    // list<threadid, toThreadid>

    for (idx = 0; idx < tg->lockidx; idx++)
    {
        if ((tg->locklist[idx].lock_id == lockaddr))
        {

            struct source_type from;
            from.id = thread_id;
            from.type = PROCESS;
            add_vertex(from);

            struct source_type to;
            to.id = tg->locklist[idx].id;
            tg->locklist[idx].degress++;
            to.type = PROCESS;
            add_vertex(to);

            if (!verify_edge(from, to))
            {
                add_edge(from, to); //
            }
        }
    }
}

// 加锁之后
void lock_after(uint64 thread_id, uint64 lockaddr)
{

    int idx = 0;
    if (-1 == (idx = search_lock(lockaddr)))
    { // lock list opera

        int eidx = search_empty_lock(lockaddr);

        tg->locklist[eidx].id = thread_id;
        tg->locklist[eidx].lock_id = lockaddr;

        inc(&tg->lockidx, 1);
    }
    else
    {

        struct source_type from;
        from.id = thread_id;
        from.type = PROCESS;

        struct source_type to;
        to.id = tg->locklist[idx].id;
        tg->locklist[idx].degress--;
        to.type = PROCESS;

        if (verify_edge(from, to))
            remove_edge(from, to);

        tg->locklist[idx].id = thread_id;
    }
}

// 解锁之后
void unlock_after(uint64 thread_id, uint64 lockaddr)
{

    int idx = search_lock(lockaddr);

    if (tg->locklist[idx].degress == 0)
    {
        tg->locklist[idx].id = 0;
        tg->locklist[idx].lock_id = 0;
        // inc(&tg->lockidx, -1);
    }
}

2.5 使用实例

#if DEADLOCK_DEBUG

pthread_mutex_t mutex_1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex_2 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex_3 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex_4 = PTHREAD_MUTEX_INITIALIZER;

void *thread_rountine_1(void *args)
{
    pthread_t selfid = pthread_self(); //

    printf("thread_routine 1 : %ld \n", selfid);

    pthread_mutex_lock(&mutex_1);
    sleep(1);
    pthread_mutex_lock(&mutex_2);

    pthread_mutex_unlock(&mutex_2);
    pthread_mutex_unlock(&mutex_1);

    return (void *)(0);
}

void *thread_rountine_2(void *args)
{
    pthread_t selfid = pthread_self(); //

    printf("thread_routine 2 : %ld \n", selfid);

    pthread_mutex_lock(&mutex_2);
    sleep(1);
    pthread_mutex_lock(&mutex_3);

    pthread_mutex_unlock(&mutex_3);
    pthread_mutex_unlock(&mutex_2);

    return (void *)(0);
}

void *thread_rountine_3(void *args)
{
    pthread_t selfid = pthread_self(); //

    printf("thread_routine 3 : %ld \n", selfid);

    pthread_mutex_lock(&mutex_3);
    sleep(1);
    pthread_mutex_lock(&mutex_4);

    pthread_mutex_unlock(&mutex_4);
    pthread_mutex_unlock(&mutex_3);

    return (void *)(0);
}

void *thread_rountine_4(void *args)
{
    pthread_t selfid = pthread_self(); //

    printf("thread_routine 4 : %ld \n", selfid);

    pthread_mutex_lock(&mutex_4);
    sleep(1);
    pthread_mutex_lock(&mutex_1);

    pthread_mutex_unlock(&mutex_1);
    pthread_mutex_unlock(&mutex_4);

    return (void *)(0);
}
#endif

int main()
{

#if DEADLOCK_DEBUG
    init_hook();
    start_check();

    printf("start_check\n");
    pthread_t tid1, tid2, tid3, tid4;

    pthread_create(&tid1, NULL, thread_rountine_1, NULL);
    pthread_create(&tid2, NULL, thread_rountine_2, NULL);
    pthread_create(&tid3, NULL, thread_rountine_3, NULL);
    pthread_create(&tid4, NULL, thread_rountine_4, NULL);

    pthread_join(tid1, NULL);
    pthread_join(tid2, NULL);
    pthread_join(tid3, NULL);
    pthread_join(tid4, NULL);
#endif
}

原文链接：https://blog.csdn.net/weixin_43687811/article/details/123748969