一、背景

　　在工作项目使用多进程、多线程过程中，因争夺资源而造成一种资源竞态，所以需加锁处理。如下图所示，线程A想获取线程B的锁，线程B想获取线程C的锁，线程 C 想获取线程D的锁， 线程D想获取线程A的锁，从而构建了一个资源获取环，当进程或者线程申请的锁处于相互交叉锁住的情况，就会出现死锁，它们将无法继续运行。YEQ拜客生活常识网

YEQ拜客生活常识网

　　死锁的存在是因为有资源获取环的存在，所以只要能检测出资源获取环，就等同于检测出死锁的存在。YEQ拜客生活常识网

二、原理

　　在不改变项目源代码的情况下，采用图算法来检测环的存在，使用有向图来存储；如线程A获取线程B已占用的锁（表示线程B获取锁成功），则为线程A指向线程B；启动一个线程定时对图进行检测是否有环的存在。YEQ拜客生活常识网

（1）数据结构

//数据/点
struct node{

    uint64 thread_id;//线程ID
    uint64 lock_id;//锁ID
    int degress;
};

//数据和数据结构分开
struct vertex{

    struct node *d;
    struct vertex *next;
};

struct graph{

    struct vertex list[THREAD_MAX];//存储图的所有节点
    int num;//已经使用了多少个

    struct node locklist[THREAD_MAX];
    int lockidx;
    
    pthread_mutex_t mutex;//预留：线程安全考虑，在对图修改时加锁
};

（2）图的操作

　　　　a.创建图节点YEQ拜客生活常识网

//创建图节点
struct vertex *create_vertex(struct node *d){

    struct vertex *tex =  (struct vertex*)calloc(1,sizeof(struct vertex));
    if(tex == NULL) return NULL;

    tex->d = d;
    tex->next = NULL;
    return tex;
}

　　b.查找节点YEQ拜客生活常识网

//查找节点，是否存在
int search_vertex(struct node *d){

    int i;
    for (i = 0; i < tg->num; i++)
    {
        if (tg->list[i].d->thread_id == d->thread_id)
        {
            return i;
        }
    }
    

　　c.添加节点YEQ拜客生活常识网

//添加节点，只是把添加的节点放到list中，还没有确定各节点间的指向，必须通过add_edge添加边来确定
void add_vertex(struct node *d){

    if (search_vertex(d) == -1)
    {
        tg->list[tg->num].d = d;//添加到list中
        tg->list[tg->num].next = NULL;

        tg->num++;//节点数累加
    }
}

　　d.添加边，指定方向YEQ拜客生活常识网

//添加边，指定方向，谁指向谁
void add_edge(struct node *from, struct node *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);
}

　　e.检测节点间是否有边YEQ拜客生活常识网

//检测节点from和to间是否有边连接
int verifty_edge(struct node *from, struct node *to){

    if(tg->num == 0) return 0;
    
    int idx = search_vertex(from);
    if(idx == -1) return 0;

    struct vertex *v = &(tg->list[idx]);
    while(v != NULL){
        if(v->d->thread_id == to->thread_id) return 1;
        v = v->next;
    }

    return 0;
}

　　f.删除边YEQ拜客生活常识网

//删除边
void remove_edge(struct node *from, struct node *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->d->thread_id == to->thread_id){//找到要删除的节点
                remove = v->next;
                v->next = v->next->next;

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

（3）图遍历

　　本文采用图遍历中最为常用的深度优先搜索进行遍历，代码如下。

相关阅读: