AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

实现死锁检测组件

2023-11-10 60
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 实现死锁检测组件

一、死锁

死锁，是指多个线程或者进程在运行过程中因争夺资源而造成的一种僵局，当进程或者线程处于这种僵持状态，若无外力作用，它们将无法再向前推进。


如下图所示，以申请锁资源为例。线程 A 想申请线程 B 的锁，线程 B 想申请线程 C 的锁，线程 C 想申请线程 D 的锁，线程 D 想申请线程 A 的锁，从而构建了一个资源申请环。

653073e07bde5127008c9ad207410b29_3794830de8494ca593ea4e1817b18cd6.png

多个线程之间依次想要访问其他线程的资源，这样相互僵持形成的一个资源申请闭环。

死锁的存在是因为有资源申请环的存在，所以只要能检测出资源申请环，就等同于检测出

死锁的存在。


1.2 死锁产生的条件

1.条件互斥：进程/线程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程/线程所占用。

2.请求与保持：当进程/线程因请求资源而阻塞时，对已获得的资源保持不放。

3.不剥夺：进程/线程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放。

4.环路等待：在发生死锁时，必然存在一个进程/线程——资源的环形链。


二、死锁检测

为了能检测系统是否发生死锁，需要有两点


  1. 用某种数据结构来保存资源的请求和分配信息；
  2. 提供一种算法，利用上述信息检测系统是否进入死锁状态。

2.1 资源分配图

在资源分配图中，有两种结点，两种边

1）两种结点


  • 进程结点：对应一个进程
  • 资源结点：对应一类资源，资源可能有多个

2）两种边


  • 进程结点 ——> 资源结点：表示进程想申请几个资源（每条边代表一个）
  • 资源结点 ——> 进程结点：表示已经为进程分配了几个资源（每条边代表一个）
  • c8af05f2a8dcb184883dcf53de18ea20_3bc69c0a184d40a0b9ff8e6a955649b9.png

如图，顶点表示进程；黄色边代表资源申请边；红色边代表资源获取边。

每个进程获取了自己的资源（锁），同时又申请了其他线程的资源（锁）。


上图展示了一个死锁，检测死锁的关键是检测资源申请边有没有构成一回路。


我们可以采用有向图来存储资源申请环，则问题转化为检测有向图是否成环。


2.2 有向图

有向图的构建有矩阵、邻接表两种方式，本文选择邻接表。

如，有向图

8c700f41fcff792e888e55b2e5260648_4d0b2b16030049718d7f9f2efe8e3abd.png

其邻接表

662a1037949ef7bbbbf3a3c33270ef16_f0256d8165bc484aaeddd10b2a921ea4.png


2.3 死锁检测组件 – hook

死锁检测的流程可大致归纳为：

1）hook拦截系统的锁接口（pthread_mutex_lock和pthread_mutex_unlock）；

2）在hook后的锁接口中，利用有向图存储资源分配图的信息

线程A申请线程B的资源锁：若锁未被占有，则占有这个锁；若锁被占有，构建线程A指向线程B的申请边。

3）创建一个线程，定时检测图进程是否有环的存在。


hook类似于C++中的重载。通过hook，系统的pthread_mutex_lock和pthread_mutex_unlock，将指向我们自己定义的函数。


hook重载的函数中，把线程与锁的申请关系构建成有向图。通过线程加锁前、加锁后、释放锁，这3个阶段维护有向图

1）加锁前：检测当前申请的锁是否被占用


  • 若被占用：构建当前线程指向占有锁的线程之间的申请边
  • 若未被占用：继续执行后续（占有这个锁）

2）加锁后：占有这个锁之后，检测


  • 该锁在之前没有被占有过：建立线程id与锁id的对应关系
  • 该锁在之前被占有过：释放之前创建的申请边，建立线程id与锁id的对应关系
  • 该锁在之前没被占有过：建立线程id与锁id的对应关系

3）释放锁：清除锁与线程的对应关系


三、死锁设计


3.1 有向图

3.1.1 数据结构

线程既可以拥有资源，也可以申请资源，资源绑定线程。为了实现复用，增加了 type 字段，当 type = RESOURCE，该结构体作为资源使用，放入资源链表； type = PROCESS，该结构体作为线程使用。


1）顶点资源信息，即线程所拥有的资源信息


// 顶点资源信息
struct source_type {
  uint64 id;      // 拥有该资源的线程 id
  enum Type type;   // 顶点类型：线程 or 资源
  uint64 lock_id;   // 资源（锁） id
  int degress;      // 资源的出度，该资源被多少顶点（线程）申请
};

2）顶点，表示线程；图的资源申请边，表示线程间的资源申请关系。


// 顶点信息
struct vertex {
  struct source_type s; // 顶点资源信息
  struct vertex *next;  // 指向下一个顶点（邻接表）
};

3）图的结构，资源 (type = RESOURCE) 存储在资源链表，线程（type = PROCESS) 作为图上的顶点。

// 图结构
struct task_graph {
  struct vertex list[MAX];      // 存储顶点于数组中
  int num;              // 顶点的数量
  struct source_type locklist[MAX]; // 存储所有顶点资源（锁）
  int lockidx;            // 资源（锁）的数量
  pthread_mutex_t mutex;
};

3.1.2 图的基本操作接口

1）创建顶点：create_vertex(struct source_type type)

2）增加顶点：add_vertex(struct source_type type)

3）寻找与资源对应的顶点所在的下标：search_vertex(struct source_type type)

4）增加一条资源申请边：add_edge(struct source_type from, struct source_type to)

5）检查资源i和j之间是否存在边：verify_edge(struct source_type i, struct source_type j)

6）删除资源from到to之间的边：remove_edge(struct source_type from, struct source_type to)


// 创建结点
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);
}
// 检查资源i和j之间是否存在边
int verify_edge(struct source_type i, struct source_type j) {
  if (tg->num == 0) return 0;
  // 寻找资源i对应的结点下标
  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;
}
// 删除资源from到to之间的边
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;
    }
  }
}

3.1.3 判断有向图是否成环

// 打印环  cycle : 1 --> 2 --> 3 --> 4 --> 2
void print_deadlock(void) {
  int i = 0;
  printf("cycle : ");
  for (i = 0;i < k-1;i ++) {
    printf("%ld --> ", tg->list[path[i]].s.id);
  }
  printf("%ld\n", tg->list[path[i]].s.id);
}
int DFS(int idx) {
  struct vertex *ver = &tg->list[idx];
  // 如果当前结点已经访问过，说明存在环
  if (visited[idx] == 1) {
    path[k++] = idx;
    print_deadlock();
    deadlock = 1;
    return 0;
  }
  // 否则将标记置为1，代表访问了，继续DFS
  visited[idx] = 1;
  path[k++] = idx;
  while (ver->next != NULL) {
    DFS(search_vertex(ver->next->s));
    k --;
    ver = ver->next;
  }
  return 1;
}
//从list[idx]的顶点开始，检测是否存在环
int search_for_cycle(int idx) {
  struct vertex *ver = &tg->list[idx];
  visited[idx] = 1; // 标记idx处顶点被访问过
  k = 0;    
  path[k++] = idx;  // 记录起点
  while (ver->next != NULL) {
    // 把visited数组的开始到idx-1处的值都置为0
    int i = 0;
    for (i = 0;i < tg->num;i ++) {
      if (i == idx) continue;
      visited[i] = 0;
    }
    // 把path数组的第i到MAX处的值都置为-1
    for (i = 1;i <= MAX;i ++) {
      path[i] = -1;
    }
    k = 1;
    DFS(search_vertex(ver->next->s));
    ver = ver->next;
  }
}

3.2 hook

3.2.1 重载系统的锁接口

// ·······································hook··············································
// 1.定义原类型
typedef int (*pthread_mutex_lock_t)(pthread_mutex_t *mutex);
pthread_mutex_lock_t pthread_mutex_lock_f = NULL;
typedef int (*pthread_mutex_unlock_t)(pthread_mutex_t *mutex);
pthread_mutex_unlock_t pthread_mutex_unlock_f = NULL;
// 2.实现
int pthread_mutex_lock(pthread_mutex_t *mutex) {
  pthread_t selfid = pthread_self();
  // 获取锁之前，检测这个锁是否被占用。
  // 有的话就创建资源申请边，没有的话就跳过
  lock_before((uint64_t)selfid, (uint64_t)mutex);
  pthread_mutex_lock_f(mutex);
  // 获取锁之后，检测这个锁是否存在与资源列表中。
  // 存在的话，移除自己对这个锁的申请边，表示请求得到满足了；不存在的话，把这个锁加入资源列表中。
  lock_after((uint64_t)selfid, (uint64_t)mutex);
}
int pthread_mutex_unlock(pthread_mutex_t *mutex) {
  pthread_mutex_unlock_f(mutex);
  pthread_t selfid = pthread_self();
  unlock_after((uint64_t)selfid, (uint64_t)mutex);
}
// 3. 初始化
void init_hook(void) {
  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.2 加锁前——lock_before

获取资源（锁）前，检测该资源是否被其他线程占用。


  1. 如果被占用，则创建一条资源申请边，表示当前进程正在向拥有资源的线程申请该资源。
  2. 如果没有被占用，则跳过。
void lock_before(uint64_t tid, uint64_t lockaddr) {
  /*
  1.  if (lockaddr) {
      tid --> lockaddr.tid;
      }
  */
  int idx = 0;
  for (idx = 0;idx < tg->lockidx;idx ++) {
    // 1. 如果被占用
    if (tg->locklist[idx].lock_id == lockaddr) { 
      // 创建申请该资源的顶点（PROCESS类型）
      struct source_type from;
      from.id = tid;
      from.type = PROCESS;
      add_vertex(from);
      // 创建拥有该资源的顶点（PROCESS类型)
      struct source_type to;
      to.id = tg->locklist[idx].id;
      to.type = PROCESS;
      add_vertex(to);
      // 申请该资源的结点数量+1
      tg->locklist[idx].degress ++;
      // 如果两个顶点间不存在资源申请边，增加一条边
      if (!verify_edge(from, to))
        add_edge(from, to);
    }
  }
}

3.2.3 加锁前——lock_before

线程获取资源（锁）后，检查该资源是否存在（资源链表中是否存在）


  1. 若该资源之前不存在，添加资源到资源链表中
  2. 若该资源已经存在，则移除之前创建的自己对该资源的申请边，表示请求已经得到满足
void lock_after(uint64_t tid, uint64_t lockaddr) {
  /*
    if (!lockaddr) {
      tid --> lockaddr;
    } else {
      lockaddr.tid = tid;
      tid -> lockaddr;
    }
   */
  int idx = 0;
  // 1. 若该资源（锁）不存在，添加资源到资源链表中
  if (-1 == (idx = search_lock(lockaddr))) {// 
    // 寻找资源链表中空闲的位置并添加该资源
    int eidx = search_empty_lock(lockaddr);
    tg->locklist[eidx].id = tid;
    tg->locklist[eidx].lock_id = lockaddr;
    // 资源数量+1
    tg->lockidx ++;
  } 
  else {  // 2. 该资源（锁）存在，需要移除自己的请求边
    // 申请该资源的顶点（PROCESS类型）
    struct source_type from;
    from.id = tid;
    from.type = PROCESS;
    add_vertex(from);
    // 拥有该资源的顶点（PROCESS类型）
    struct source_type to;
    to.id = tg->locklist[idx].id;
    to.type = PROCESS;
    add_vertex(to);
    // 申请该资源的顶点数-1
    tg->locklist[idx].degress --;
    // 如果存在该资源申请边，则删除
    if (verify_edge(from, to))
      remove_edge(from, to);
    // 线程占用该资源（锁）
    tg->locklist[idx].id = tid;
  }
}

3.2.4 加锁后——unlock_after

线程释放该资源后，检查该资源是否还被其他线程申请，没有则将其从资源链表中移除。


void unlock_after(uint64_t tid, uint64_t lockaddr) {
  // lockaddr.tid = 0;
  // 此锁已被unlock
  int idx = search_lock(lockaddr);
  // 若该资源没有线程申请，则将其从资源链表中移除
  if (tg->locklist[idx].degress == 0) {
    tg->locklist[idx].id = 0;
    tg->locklist[idx].lock_id = 0;
  }
}

3.3 死锁检测线程

创建死锁检测线程，在程序的运行期间时刻监控线程与锁之间的关系。


// 检测死锁
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); //每隔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);
}

3.4 画图解释

1、

c0dc16a295bf4191cdc4347e41fba8a0_02ac468a38754b25bdb4b84ed73f9000.png

2、

e6d32f4f370a10475343b12caa559350_fb95c295f6fa4b6eaa7f760c415c1718.png

3、

48f3a33e5b5793742d6620b8aa3edb43_e9068690ad4b44a782564c85c27d5f15.png


四、代码实现及测试


创建5个线程，1申请2、2申请3、3申请4、4申请5、5申请1

出现死锁

e775fb9fa67c319b1e7bddf867a2cb00_219b8322d3af409ba33509d2a02b262b.png


修改1申请2、2申请3、3申请4、4申请5

检测完成，未出现死锁


ace0b025e9c4008a9a9b06fe6ff621a6_917311a893c342758105e7781ce1e61a.png


// build: gcc -o deadlock deadlock.c -lpthread -ldl
#define _GNU_SOURCE
#include <dlfcn.h>
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <stdint.h>
//·········································有向图的结构和基本操作接口····························································
#if 1   // 图结构
typedef unsigned long int uint64;
#define MAX   100
enum Type {PROCESS, RESOURCE};
// 顶点资源信息
struct source_type {
  uint64 id;      // 拥有该资源的线程 id
  enum Type type;   // 顶点类型：线程 or 资源
  uint64 lock_id;   // 资源（锁） 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; // 死锁标记
// 创建顶点
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);
}
// 检查资源i和j之间是否存在边
int verify_edge(struct source_type i, struct source_type j) {
  if (tg->num == 0) return 0;
  // 寻找资源i对应的结点下标
  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;
}
// 删除资源from到to之间的边
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;
    }
  }
}
// 打印环  cycle : 1 --> 2 --> 3 --> 4 --> 2
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);
}
int DFS(int idx) {
  struct vertex *ver = &tg->list[idx];
  // 如果当前结点已经访问过，说明存在环
  if (visited[idx] == 1) {
    path[k++] = idx;
    print_deadlock();
    deadlock = 1;
    return 0;
  }
  // 否则将标记置为1，代表访问了，继续DFS
  visited[idx] = 1;
  path[k++] = idx;
  while (ver->next != NULL) {
    DFS(search_vertex(ver->next->s));
    k --;
    ver = ver->next;
  }
  return 1;
}
//从list[idx]的顶点开始，检测是否存在环
int search_for_cycle(int idx) {
  struct vertex *ver = &tg->list[idx];
  visited[idx] = 1; // 标记idx处顶点被访问过
  k = 0;    
  path[k++] = idx;  // 记录起点
  while (ver->next != NULL) {
    // 把visited数组的开始到idx-1处的值都置为0
    int i = 0;
    for (i = 0;i < tg->num;i ++) {
      if (i == idx) continue;
      visited[i] = 0;
    }
    // 把path数组的第i到MAX处的值都置为-1
    for (i = 1;i <= MAX;i ++) {
      path[i] = -1;
    }
    k = 1;
    DFS(search_vertex(ver->next->s));
    ver = ver->next;
  }
}
#endif
// 
#if 1
// 搜索锁lock是否在资源列表中，若有则返回下标位置
int search_lock(uint64 lock) {
  int i = 0;
  for (i = 0;i < tg->lockidx;i ++) {
    //如果lock存在就返回它在锁列表中的下标位置
    if (tg->locklist[i].lock_id == lock) {
      return i;
    }
  }
  return -1;
}
// 寻找资源列表中的一个空位置
int search_empty_lock(uint64 lock) {
  int i = 0;
  for (i = 0;i < tg->lockidx;i ++) {
    if (tg->locklist[i].lock_id == 0) {
      return i;
    }
  }
  return tg->lockidx;
}
/*
获取资源（锁）前，检测该资源是否被其他线程占用。
1. 如果被占用，则创建一条资源申请边，表示当前进程正在向拥有资源的线程申请该资源。
2. 如果没有被占用，则跳过。
*/
void lock_before(uint64_t tid, uint64_t lockaddr) {
  /*
  1.  if (lockaddr) {
      tid --> lockaddr.tid;
      }
  */
  int idx = 0;
  for (idx = 0;idx < tg->lockidx;idx ++) {
    // 1. 如果被占用
    if (tg->locklist[idx].lock_id == lockaddr) { 
      // 创建申请该资源的顶点（PROCESS类型）
      struct source_type from;
      from.id = tid;
      from.type = PROCESS;
      add_vertex(from);
      // 创建拥有该资源的顶点（PROCESS类型)
      struct source_type to;
      to.id = tg->locklist[idx].id;
      to.type = PROCESS;
      add_vertex(to);
      // 申请该资源的结点数量+1
      tg->locklist[idx].degress ++;
      // 如果两个顶点间不存在资源申请边，增加一条边
      if (!verify_edge(from, to))
        add_edge(from, to);
    }
  }
}
/*
线程获取资源（锁）后，检查该资源是否存在（资源链表中是否存在）
1. 若该资源之前不存在，添加资源到资源链表中
2. 若该资源已经存在，则移除自己对该资源的申请边，表示请求已经得到满足
*/
void lock_after(uint64_t tid, uint64_t lockaddr) {
  /*
    if (!lockaddr) {
      tid --> lockaddr;
    } else {
      lockaddr.tid = tid;
      tid -> lockaddr;
    }
   */
  int idx = 0;
  // 1. 若该资源（锁）不存在，添加资源到资源链表中
  if (-1 == (idx = search_lock(lockaddr))) {// 
    // 寻找资源链表中空闲的位置并添加该资源
    int eidx = search_empty_lock(lockaddr);
    tg->locklist[eidx].id = tid;
    tg->locklist[eidx].lock_id = lockaddr;
    // 资源数量+1
    tg->lockidx ++;
  } 
  else {  // 2. 该资源（锁）存在，需要移除自己的请求边
    // 申请该资源的顶点（PROCESS类型）
    struct source_type from;
    from.id = tid;
    from.type = PROCESS;
    add_vertex(from);
    // 拥有该资源的顶点（PROCESS类型）
    struct source_type to;
    to.id = tg->locklist[idx].id;
    to.type = PROCESS;
    add_vertex(to);
    // 申请该资源的顶点数-1
    tg->locklist[idx].degress --;
    // 如果存在该资源申请边，则删除
    if (verify_edge(from, to))
      remove_edge(from, to);
    // 线程占用该资源（锁）
    tg->locklist[idx].id = tid;
  }
}
// 线程释放该资源后，检查该资源是否还被线程申请，没有则将其从资源链表中移除。
void unlock_after(uint64_t tid, uint64_t lockaddr) {
  // lockaddr.tid = 0;
  // 此锁已被unlock
  int idx = search_lock(lockaddr);
  // 若该资源没有线程申请，则将其从资源链表中移除
  if (tg->locklist[idx].degress == 0) {
    tg->locklist[idx].id = 0;
    tg->locklist[idx].lock_id = 0;
  }
}
// ····································死锁检测的线程·········································
// 检测死锁
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); //每隔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);
}
// ··························································································
// ·······································hook··············································
// 1.定义原类型
typedef int (*pthread_mutex_lock_t)(pthread_mutex_t *mutex);
pthread_mutex_lock_t pthread_mutex_lock_f = NULL;
typedef int (*pthread_mutex_unlock_t)(pthread_mutex_t *mutex);
pthread_mutex_unlock_t pthread_mutex_unlock_f = NULL;
// 2.实现
int pthread_mutex_lock(pthread_mutex_t *mutex) {
  pthread_t selfid = pthread_self();
  // 获取锁之前，检测这个锁是否被占用。
  // 有的话就创建资源申请边，没有的话就跳过
  lock_before((uint64_t)selfid, (uint64_t)mutex);
  pthread_mutex_lock_f(mutex);
  // 获取锁之后，检测这个锁是否存在与资源列表中。
  // 存在的话，移除自己对这个锁的申请边，表示请求得到满足了；不存在的话，把这个锁加入资源列表中。
  lock_after((uint64_t)selfid, (uint64_t)mutex);
}
int pthread_mutex_unlock(pthread_mutex_t *mutex) {
  pthread_mutex_unlock_f(mutex);
  pthread_t selfid = pthread_self();
  unlock_after((uint64_t)selfid, (uint64_t)mutex);
}
// 3. 初始化
void init_hook(void) {
  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");
}
// ··························································································
#endif
// 
#if 1//sample
pthread_mutex_t r1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t r2 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t r3 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t r4 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t r5 = PTHREAD_MUTEX_INITIALIZER;
void *t1_cb(void *arg) {
  pthread_t selfid = pthread_self(); 
  printf("thread_routine 1 : %ld \n", selfid);
  pthread_mutex_lock(&r1);
  sleep(1); // 休眠，允许期间其他线程能运行
  pthread_mutex_lock(&r2);
  pthread_mutex_unlock(&r2);
  pthread_mutex_unlock(&r1);
}
void *t2_cb(void *arg) {
  pthread_t selfid = pthread_self(); 
  printf("thread_routine 2 : %ld \n", selfid);
  pthread_mutex_lock(&r2);
  sleep(1);
  pthread_mutex_lock(&r3);
  pthread_mutex_unlock(&r3);
  pthread_mutex_unlock(&r2);
}
void *t3_cb(void *arg) {
  pthread_t selfid = pthread_self(); 
  printf("thread_routine 3 : %ld \n", selfid);
  pthread_mutex_lock(&r3);
  sleep(1);
  pthread_mutex_lock(&r4);
  pthread_mutex_unlock(&r4);
  pthread_mutex_unlock(&r3);
}
void *t4_cb(void *arg) {
  pthread_t selfid = pthread_self(); 
  printf("thread_routine 4 : %ld \n", selfid);
  pthread_mutex_lock(&r4);
  sleep(1);
  pthread_mutex_lock(&r5);
  pthread_mutex_unlock(&r5);
  pthread_mutex_unlock(&r4);
}
void *t5_cb(void *arg) {
  pthread_t selfid = pthread_self(); 
  printf("thread_routine 5 : %ld \n", selfid);
  pthread_mutex_lock(&r5);
  sleep(1);
  pthread_mutex_lock(&r1);
  pthread_mutex_unlock(&r1);
  pthread_mutex_unlock(&r5);
}
// deadlock
// 
int main() {
  init_hook();
  // 启动检测死锁的线程
  start_check();
  printf("start_check\n");
  pthread_t t1, t2, t3, t4, t5;
  pthread_create(&t1, NULL, t1_cb, NULL);
  pthread_create(&t2, NULL, t2_cb, NULL);
  pthread_create(&t3, NULL, t3_cb, NULL);
  pthread_create(&t4, NULL, t4_cb, NULL);
  pthread_create(&t5, NULL, t5_cb, NULL);
  pthread_join(t1, NULL);
  pthread_join(t2, NULL);
  pthread_join(t3, NULL);
  pthread_join(t4, NULL);
  pthread_join(t5, NULL);
  printf("complete\n");
}
#endif
文章标签：
存储
C++
监控
算法
闲谈社
目录
相关文章
运营研究坊
|
3月前
|
Java 测试技术 PHP
父子任务使用不当线程池死锁怎么解决？
在Java多线程编程中，线程池有助于提升性能与资源利用效率，但若父子任务共用同一池，则可能诱发死锁。本文通过一个具体案例剖析此问题：在一个固定大小为2的线程池中，父任务直接调用`outerTask`，而`outerTask`再次使用同一线程池异步调用`innerTask`。理论上，任务应迅速完成，但实际上却超时未完成。经由`jstack`输出的线程调用栈分析发现，线程陷入等待状态，形成“死锁”。原因是子任务需待父任务完成，而父任务则需等待子任务执行完毕以释放线程，从而相互阻塞。此问题在测试环境中不易显现，常在生产环境下高并发时爆发，重启或扩容仅能暂时缓解。
运营研究坊
57 0
程韬123
|
6月前
|
存储 监控 程序员
线程死锁检测组件逻辑与源码
线程死锁检测组件逻辑与源码
程韬123
84 2
菊头蝙蝠
|
6月前
|
存储
动手实现死锁检测组件（通过hook与有向图实现）
动手实现死锁检测组件（通过hook与有向图实现）
菊头蝙蝠
83 1
码农~
|
6月前
|
数据处理 数据库
死锁检测组件实现
死锁检测组件实现
码农~
40 0
简锋
|
6月前
|
存储
死锁检测组件
死锁检测组件
简锋
36 0
整日摸鱼的小黑猫
|
6月前
|
存储 安全 C语言
手写死锁检测组件
手写死锁检测组件
整日摸鱼的小黑猫
52 0
基层搬砖的Panda
|
6月前
死锁检测组件原理及代码实现
死锁检测组件原理及代码实现
基层搬砖的Panda
84 0
ZLOSER02
|
11月前
|
算法 调度
死锁原因及死锁检测组件的实现
死锁原因及死锁检测组件的实现
ZLOSER02
123 0
xindoo
|
算法 安全 Java
死锁的原理
之前在学校学习过程中，很少写多进程的代码，虽然操作系统中学过死锁相关的内容，但考试过后也基本就忘记了，后来自己也遇到过有些多进程死锁的情况，再加上看了有些资料，对死锁才算是有了有些深入的理解。
xindoo
82 0
一个风轻云淡
|
关系型数据库 中间件 MySQL
上手全局锁，死锁
上手全局锁，死锁
一个风轻云淡
111 0
上手全局锁，死锁