手写Linux死锁检测器：基于有向图环实现检测与总结

1.死锁检测的核心原理死锁的本质是产生资源依赖环我们只需检测是否有环产生便可以检测出死锁。我们可以用有向图对资源进行建模节点线程节点、锁节点。边请求边-线程请求锁-即线程--锁。持有边-线程持有锁-即锁--线程。图使用邻接表邻接数组数组的每个索引上挂一个链表。// 顶点类型枚举线程/锁 typedef enum { NODE_THREAD, // 线程节点 NODE_LOCK // 锁节点 } NodeType; // 图顶点结构邻接表节点 typedef struct GraphNode { unsigned long id; // 线程ID/锁地址统一为无符号长整数 NodeType type; // 顶点类型 struct GraphNode *next; // 邻接链表下一个节点 } GraphNode; // 有向图结构邻接表 typedef struct { GraphNode *vertices[MAX_VERTEX]; // 顶点数组最大200个顶点 int vertex_count; // 已添加顶点数 pthread_mutex_t graph_mtx; // 图操作锁保证线程安全 } Digraph; // 全局图实例存储线程-锁依赖关系 Digraph deadlock_graph;2.环境配置系统Linux依赖dlfcn.h实现函数Hook。编译需链接dl库和pthread库。头文件#define _GNU_SOURCE #include stdio.h #include dlfcn.h #include pthread.h #include stdlib.h #include unistd.h #include string.h3.代码3.1Hook通过函数指针和dlsym(RTLD_NEXT)获取原生pthread_mutex_lock()函数然后封装自己实现操作。// 函数指针指向系统原生锁函数 typedef int (*pthread_mutex_lock_ptr)(pthread_mutex_t *mtx); pthread_mutex_lock_ptr pthread_mutex_lock_f; typedef int (*pthread_mutex_unlock_ptr)(pthread_mutex_t *mtx); pthread_mutex_unlock_ptr pthread_mutex_unlock_f; // 初始化Hook获取系统函数地址 void init_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); } } // 自定义锁操作拦截更新图 void my_lock(pthread_mutex_t *mtx) { add_request(pthread_self(), mtx); // 请求锁添加「线程→锁」边 pthread_mutex_lock_f(mtx); // 调用系统原生锁函数 add_hold(pthread_self(), mtx); // 持有锁删除「线程→锁」添加「锁→线程」边 } void my_unlock(pthread_mutex_t *mtx) { pthread_t thid pthread_self(); remove_hold(thid, mtx); // 释放锁删除「锁→线程」边 pthread_mutex_unlock_f(mtx); // 调用系统原生解锁函数 }3.2有向图操作// 查找顶点返回顶点在数组中的索引未找到返回-1 int graph_find_node(unsigned long id, NodeType type) { for (size_t i 0; i deadlock_graph.vertex_count; i) { if (deadlock_graph.vertices[i]-id id deadlock_graph.vertices[i]-type type) { return i; } } return -1; } // 添加顶点已存在返回索引否则新增并返回索引 int graph_add_node(unsigned long id, NodeType type) { int idx graph_find_node(id, type); if (idx ! -1) return idx; // 避免重复添加 if (deadlock_graph.vertex_count MAX_VERTEX) { fprintf(stderr, 顶点数超出限制\n); return -1; } GraphNode *node (GraphNode *)malloc(sizeof(GraphNode)); node-id id; node-type type; node-next NULL; deadlock_graph.vertices[deadlock_graph.vertex_count] node; return deadlock_graph.vertex_count; // 返回索引先赋值后自增 } // 添加边from → to保证线程安全 void graph_add_edge(unsigned long from_id, NodeType from_type, unsigned long to_id, NodeType to_type) { pthread_mutex_lock_f(deadlock_graph.graph_mtx); // 加锁保护 int from_idx graph_add_node(from_id, from_type); int to_idx graph_add_node(to_id, to_type); if (from_idx -1 || to_idx -1) { pthread_mutex_unlock_f(deadlock_graph.graph_mtx); return; } // 检查边是否已存在避免重复 GraphNode *curr deadlock_graph.vertices[from_idx]; while (curr-next ! NULL) { if (curr-next-id to_id curr-next-type to_type) { pthread_mutex_unlock_f(deadlock_graph.graph_mtx); return; } curr curr-next; } // 新增边 GraphNode *edge (GraphNode *)malloc(sizeof(GraphNode)); edge-id to_id; edge-type to_type; edge-next NULL; curr-next edge; pthread_mutex_unlock_f(deadlock_graph.graph_mtx); } // 删除边from → to void graph_remove_edge(unsigned long from_id, NodeType from_type, unsigned long to_id, NodeType to_type) { pthread_mutex_lock_f(deadlock_graph.graph_mtx); int from_idx graph_find_node(from_id, from_type); if (from_idx -1) { pthread_mutex_unlock_f(deadlock_graph.graph_mtx); return; } GraphNode *prev deadlock_graph.vertices[from_idx]; GraphNode *curr prev-next; while (curr ! NULL) { if (curr-id to_id curr-type to_type) { prev-next curr-next; free(curr); // 释放边内存 break; } prev curr; curr curr-next; } pthread_mutex_unlock_f(deadlock_graph.graph_mtx); }3.3DFS环检测int visited[MAX_VERTEX]; // 访问标记 int path[MAX_VERTEX]; // 环路径 int path_len; // 路径长度 int had_deadlock; // 是否检测到死锁 // 打印死锁环 void print_deadlock_cycle() { printf(\n⚠️ 检测到死锁环路径\n); for (size_t i 0; i path_len; i) { int idx path[i]; GraphNode *node deadlock_graph.vertices[idx]; if (node-type NODE_THREAD) { printf(线程[hash: %d], get_thread_hash((pthread_t)node-id)); } else { printf((锁[hash: %d]), get_lock_hash((pthread_mutex_t *)node-id)); } if (i path_len - 1 node-type NODE_LOCK) printf( → ); } printf(\n); } // 递归DFS检测环 int dfs_detect_deadlock(int curr_idx) { visited[curr_idx] 1; // 标记为“访问中” path[path_len] curr_idx; // 加入路径 GraphNode *neighbor deadlock_graph.vertices[curr_idx]-next; while (neighbor ! NULL) { int next_idx graph_find_node(neighbor-id, neighbor-type); if (next_idx -1) { neighbor neighbor-next; continue; } if (visited[next_idx] 1) { // 发现环访问中重复访问 int cycle_start 0; while (cycle_start path_len path[cycle_start] ! next_idx) { cycle_start; } // 补全环的终点和起点一致 path[path_len] next_idx; print_deadlock_cycle(); had_deadlock 1; return 1; } else if (visited[next_idx] 0) { // 未访问递归 if (dfs_detect_deadlock(next_idx)) { return 1; } } neighbor neighbor-next; } visited[curr_idx] 2; // 标记为“已访问” path_len--; // 移出路径 return 0; } // 死锁检测入口 void check_deadlock() { pthread_mutex_lock_f(deadlock_graph.graph_mtx); // 重置检测状态 had_deadlock 0; memset(visited, 0, sizeof(visited)); memset(path, -1, sizeof(path)); path_len 0; // 从所有线程节点开始检测死锁一定从线程开始 for (int i 0; i deadlock_graph.vertex_count; i) { if (visited[i] 0 deadlock_graph.vertices[i]-type NODE_THREAD) { if (dfs_detect_deadlock(i)) break; // 找到死锁退出 } } if (!had_deadlock) { printf(\n✅ 未检测到死锁\n); } pthread_mutex_unlock_f(deadlock_graph.graph_mtx); }3.4测试// 全局测试锁 pthread_mutex_t mtx1 PTHREAD_MUTEX_INITIALIZER; pthread_mutex_t mtx2 PTHREAD_MUTEX_INITIALIZER; pthread_mutex_t mtx3 PTHREAD_MUTEX_INITIALIZER; // 测试线程1mtx1 → mtx2 void *func1(void *arg) { my_lock(mtx1); sleep(1); my_lock(mtx2); printf(func1执行完成\n); my_unlock(mtx2); my_unlock(mtx1); return NULL; } // 测试线程2mtx2 → mtx3 void *func2(void *arg) { my_lock(mtx2); sleep(1); my_lock(mtx3); printf(func2执行完成\n); my_unlock(mtx3); my_unlock(mtx2); return NULL; } // 测试线程3mtx3 → mtx1 void *func3(void *arg) { my_lock(mtx3); sleep(1); my_lock(mtx1); printf(func3执行完成\n); my_unlock(mtx1); my_unlock(mtx3); return NULL; } int main(int argc, char const *argv[]) { init_hook(); init_graph(); pthread_t t1, t2, t3; // 创建线程 pthread_create(t1, NULL, func1, NULL); pthread_create(t2, NULL, func2, NULL); pthread_create(t3, NULL, func3, NULL); sleep(3); // 等待线程进入阻塞死锁形成 print_chain(); // 打印锁的请求/持有关系 check_deadlock(); // 检测死锁 // 死锁后线程无法退出需CtrlC终止 pthread_join(t1, NULL); pthread_join(t2, NULL); pthread_join(t3, NULL); return 0; }3.5完整代码#define _GNU_SOURCE #include stdio.h #include dlfcn.h #include pthread.h #include stdlib.h #include unistd.h #include string.h #define MAX 100 #define MAX_VERTEX 200 // 线程锁的最大顶点数 // 线程节点 struct pthread_node_s { pthread_t pid; struct pthread_node_s *next; }; // 锁节点 struct lock_node_s { pthread_mutex_t *mtx; struct pthread_node_s *next; }; // 有向图结构 typedef enum // enum枚举类型从0开始递增字段无需再赋值 { NODE_THREAD, // 线程节点从0开始这里是0 NODE_LOCK // 锁节点这里默认值为1 } NodeType; // 图顶点结构 typedef struct GraphNode { unsigned long id; // 线程/锁ID NodeType type; // 线程/锁类型 struct GraphNode *next; // 下一位 } GraphNode; // 图结构邻接表 typedef struct { GraphNode *vertices[MAX_VERTEX]; // 顶点数组 int vertex_count; // 已添加的顶点数 pthread_mutex_t graph_mtx; // 图操作锁 } Digraph; Digraph deadlock_graph; // 死锁检测图 int visited[MAX_VERTEX]; // DFS访问标记 int path[MAX_VERTEX]; // 环路径 int path_len; // 路径长度 int had_deadlock; // 是否死锁 struct lock_node_s *locks[MAX] {0}; // 锁-请求线程链表 struct lock_node_s *holds[MAX] {0}; // 锁-持有线程链表 // 函数指针 typedef int (*pthread_mutex_lock_ptr)(pthread_mutex_t *mtx); pthread_mutex_lock_ptr pthread_mutex_lock_f; typedef int (*pthread_mutex_unlock_ptr)(pthread_mutex_t *mtx); pthread_mutex_unlock_ptr pthread_mutex_unlock_f; // 全局锁 pthread_mutex_t mtx1 PTHREAD_MUTEX_INITIALIZER; pthread_mutex_t mtx2 PTHREAD_MUTEX_INITIALIZER; pthread_mutex_t mtx3 PTHREAD_MUTEX_INITIALIZER; pthread_mutex_t locks_mtx PTHREAD_MUTEX_INITIALIZER; pthread_mutex_t hold_mtx PTHREAD_MUTEX_INITIALIZER; // 初始化Hook void init_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); } } // ✅ 正确的哈希计算基于线程ID/锁地址的真实值而非局部变量地址 // 线程ID哈希直接取pthread_t的数值兼容不同系统的pthread_t类型 int get_thread_hash(pthread_t pid) { // 将pthread_t转为无符号长整数通用写法 unsigned long tid (unsigned long)pid; return tid % MAX; } // 锁地址哈希直接取锁指针的数值 int get_lock_hash(pthread_mutex_t *mtx) { unsigned long mtx_addr (unsigned long)mtx; return mtx_addr % MAX; } // 初始化图 void init_graph() { memset(deadlock_graph.vertices, 0, sizeof(deadlock_graph.vertices)); deadlock_graph.vertex_count 0; pthread_mutex_init(deadlock_graph.graph_mtx, NULL); had_deadlock 0; } // 查找顶点 int graph_find_node(unsigned long id, NodeType type) { for (size_t i 0; i deadlock_graph.vertex_count; i) { if (deadlock_graph.vertices[i]-id id deadlock_graph.vertices[i]-type type) { return i; } } return -1; } // 添加顶点 int graph_add_node(unsigned long id, NodeType type) { int idx graph_find_node(id, type); if (idx ! -1) return idx; if (deadlock_graph.vertex_count MAX_VERTEX) { fprintf(stderr, 数量超出限制\n); return -1; } GraphNode *node (GraphNode *)malloc(sizeof(GraphNode)); node-id id; node-type type; node-next NULL; deadlock_graph.vertices[deadlock_graph.vertex_count] node; return deadlock_graph.vertex_count; // 返回索引位置 } // 添加边 void graph_add_edge(unsigned long from_id, NodeType from_type, unsigned long to_id, NodeType to_type) { pthread_mutex_lock_f(deadlock_graph.graph_mtx); // 添加节点进入deadlock_graph.vertices数组 int from_idx graph_add_node(from_id, from_type); int to_idx graph_add_node(to_id, to_type); if (from_idx -1 || to_idx -1) { pthread_mutex_unlock_f(deadlock_graph.graph_mtx); return; } // 检查边是否已存在 GraphNode *curr deadlock_graph.vertices[from_idx]; while (curr-next ! NULL) { if (curr-next-id to_id curr-next-type to_type) { return; } curr curr-next; } // 添加边 GraphNode *edge (GraphNode *)malloc(sizeof(GraphNode)); edge-id to_id; edge-type to_type; edge-next NULL; curr-next edge; pthread_mutex_unlock_f(deadlock_graph.graph_mtx); } // 删除边 void graph_remove_edge(unsigned long from_id, NodeType from_type, unsigned long to_id, NodeType to_type) { pthread_mutex_lock_f(deadlock_graph.graph_mtx); int from_idx graph_find_node(from_id, from_type); if (from_idx -1) { pthread_mutex_unlock_f(deadlock_graph.graph_mtx); return; } GraphNode *prev deadlock_graph.vertices[from_idx]; GraphNode *curr prev-next; while (curr ! NULL) { if (curr-id to_id curr-type to_type) { prev-next curr-next; free(curr); break; } prev prev-next; curr curr-next; } pthread_mutex_unlock_f(deadlock_graph.graph_mtx); } // 打印死锁环 void print_deadlock_cycle() { printf(\n⚠️ 检测到死锁环路径\n); for (size_t i 0; i path_len; i) { int idx path[i]; GraphNode *node deadlock_graph.vertices[idx]; if (node-type NODE_THREAD) { printf(线程[hash: %d], get_thread_hash((pthread_t)node-id)); // printf(线程[hash: %d, ID: %lu], get_thread_hash((pthread_t)node-id), node-id); } else { printf((锁[hash: %d]), get_lock_hash((pthread_mutex_t *)node-id)); // printf(锁[hash: %d, ID: %p], get_lock_hash((pthread_mutex_t *)node-id), (void *)node-id); } if (i path_len - 1 node-type NODE_LOCK) printf( → ); } printf(\n); } // 深度搜索递归查找环 int dfs_detect_deadlock(int curr_idx) { // 先标记 visited[curr_idx] 1; // 加入路径数组 path[path_len] curr_idx; // 找到当前节点的邻接节点 GraphNode *neighbor deadlock_graph.vertices[curr_idx]-next; while (neighbor ! NULL) { // 根据邻接节点找该节点在邻接数组中的位置 int next_idx graph_find_node(neighbor-id, neighbor-type); if (next_idx -1) { neighbor neighbor-next; continue; } // 然后定位neighbor在邻接数组的位置然后继续往下找 if (visited[next_idx] 1) // 访问过表示形成环路 { // 接下来我们要找到环路径由于next_idx已经访问过说明它在前边我们找到第一个next_idx的位置 int cycle_start 0; while (cycle_start path_len path[cycle_start] ! next_idx) { cycle_start; } // 然后我们打印cycle_start到path_len-1的索引即环路 path[path_len] next_idx; // 环路起点需和终点一样复制起点放最后做终点 neighbor deadlock_graph.vertices[next_idx]-next; // 获取线程请求的锁节点 int next_idx graph_find_node(neighbor-id, neighbor-type); // 查找锁索引 path[path_len] next_idx; // 添加锁索引 print_deadlock_cycle(); // 打印 had_deadlock 1; // 标记 return 1; } else if (visited[next_idx] 0) // 如果没有访问过那就递归访问 { if (dfs_detect_deadlock(next_idx)) // 返回1表示检测到死锁 { return 1; } } neighbor neighbor-next; } visited[curr_idx] 2; // 当前节点已访问完成 path_len--; // 从路径数组中移除当前节点 return 0; // 没有检测到死锁 } // 死锁检测入口函数 void check_deadlock() { if (!pthread_mutex_lock_f) return; pthread_mutex_lock_f(deadlock_graph.graph_mtx); // 重置检测状态 had_deadlock 0; memset(visited, 0, sizeof(visited)); memset(path, -1, sizeof(path)); path_len 0; // 遍历所有顶点检测环 for (int i 0; i deadlock_graph.vertex_count; i) { if (visited[i] 0 deadlock_graph.vertices[i]-type NODE_THREAD) // 从线程节点开始 { if (dfs_detect_deadlock(i)) break; // 找到死锁退出 } } if (!had_deadlock) { printf(\n✅ 未检测到死锁\n); } pthread_mutex_unlock_f(deadlock_graph.graph_mtx); } // 锁操作函数关联图构建 void add_request(pthread_t pid, pthread_mutex_t *mtx) { if (!mtx) return; int tid_hash get_thread_hash(pid); int lock_hash get_lock_hash(mtx); printf(线程%d请求锁%d\n, tid_hash, lock_hash); // 补充添加边线程 → 锁表示线程请求锁 unsigned long tid (unsigned long)pid; unsigned long lock_addr (unsigned long)mtx; graph_add_edge(tid, NODE_THREAD, lock_addr, NODE_LOCK); // 原有链表操作保留 struct pthread_node_s *new_pnode (struct pthread_node_s *)malloc(sizeof(struct pthread_node_s)); new_pnode-pid pid; new_pnode-next NULL; pthread_mutex_lock_f(locks_mtx); if (locks[lock_hash] NULL) { struct lock_node_s *new_lnode (struct lock_node_s *)malloc(sizeof(struct lock_node_s)); new_lnode-mtx mtx; new_lnode-next NULL; locks[lock_hash] new_lnode; } struct lock_node_s *lns locks[lock_hash]; new_pnode-next lns-next; lns-next new_pnode; pthread_mutex_unlock_f(locks_mtx); } // 删除请求修复处理所有节点包括头节点 void remove_request(pthread_t pid, pthread_mutex_t *mtx) { int lock_hash get_lock_hash(mtx); if (locks[lock_hash] NULL || locks[lock_hash]-next NULL) return; pthread_mutex_lock_f(locks_mtx); struct pthread_node_s *prev NULL; struct pthread_node_s *curr locks[lock_hash]-next; // 找目标线程节点 while (curr ! NULL curr-pid ! pid) { prev curr; curr curr-next; } // 找到节点则删除 if (curr ! NULL) { if (prev NULL) // 头节点 { locks[lock_hash]-next curr-next; } else // 中间/尾节点 { prev-next curr-next; } free(curr); // 释放内存 } pthread_mutex_unlock_f(locks_mtx); } // 添加占有 void add_hold(pthread_t pid, pthread_mutex_t *mtx) { int tid_hash get_thread_hash(pid); int lock_hash get_lock_hash(mtx); printf(线程%d占有锁%d\n, tid_hash, lock_hash); remove_request(pid, mtx); // 补充1. 删除线程→锁边 2. 添加锁→线程边锁被线程持有 unsigned long tid (unsigned long)pid; unsigned long lock_addr (unsigned long)mtx; graph_remove_edge(tid, NODE_THREAD, lock_addr, NODE_LOCK); graph_add_edge(lock_addr, NODE_LOCK, tid, NODE_THREAD); // 原有链表操作保留 pthread_mutex_lock_f(hold_mtx); if (holds[lock_hash] NULL) { struct lock_node_s *lns (struct lock_node_s *)malloc(sizeof(struct lock_node_s)); lns-mtx mtx; lns-next NULL; holds[lock_hash] lns; } struct pthread_node_s *new_pnode (struct pthread_node_s *)malloc(sizeof(struct pthread_node_s)); new_pnode-pid pid; new_pnode-next NULL; holds[lock_hash]-next new_pnode; pthread_mutex_unlock_f(hold_mtx); } // 删除占有 void remove_hold(pthread_t pid, pthread_mutex_t *mtx) { int lock_hash get_lock_hash(mtx); pthread_mutex_lock_f(hold_mtx); if (holds[lock_hash] holds[lock_hash]-next) { struct pthread_node_s *pns holds[lock_hash]-next; if (pns-pid pid) { free(pns); holds[lock_hash]-next NULL; // 补充删除锁→线程边锁被释放 unsigned long tid (unsigned long)pid; unsigned long lock_addr (unsigned long)mtx; graph_remove_edge(lock_addr, NODE_LOCK, tid, NODE_THREAD); } } pthread_mutex_unlock_f(hold_mtx); } // 修复后的打印函数精准输出锁的请求/持有关系 void print_chain() { printf(\n 锁状态明细 \n); pthread_mutex_lock(locks_mtx); pthread_mutex_lock(hold_mtx); // 遍历所有锁的请求/持有状态 for (int i 0; i MAX; i) { if (locks[i] NULL) continue; int lock_hash get_lock_hash(locks[i]-mtx); printf(锁%d -, lock_hash); // 打印请求该锁的线程列表 struct pthread_node_s *req locks[i]-next; if (req NULL) { printf(无请求线程 ); } else { printf(请求线程[); while (req) { printf(%d, get_thread_hash(req-pid)); req req-next; if (req) printf(,); } printf(] ); } // 打印持有该锁的线程 int hold_idx get_lock_hash(locks[i]-mtx); if (holds[hold_idx] holds[hold_idx]-next) { int hold_tid get_thread_hash(holds[hold_idx]-next-pid); printf(- 持有线程%d, hold_tid); } else { printf(| 无持有线程); } printf(\n); } pthread_mutex_unlock(hold_mtx); pthread_mutex_unlock(locks_mtx); printf(\n\n); } // 自定义锁操作 void my_lock(pthread_mutex_t *mtx) { add_request(pthread_self(), mtx); pthread_mutex_lock_f(mtx); add_hold(pthread_self(), mtx); } void my_unlock(pthread_mutex_t *mtx) { pthread_t thid pthread_self(); remove_hold(thid, mtx); printf(线程%d释放锁%d\n, get_thread_hash(thid), get_lock_hash(mtx)); pthread_mutex_unlock_f(mtx); } // 测试线程函数 void *func1(void *arg) { my_lock(mtx1); sleep(1); my_lock(mtx2); printf(func1执行完成\n); my_unlock(mtx2); my_unlock(mtx1); return NULL; } void *func2(void *arg) { my_lock(mtx2); sleep(1); my_lock(mtx3); printf(func2执行完成\n); my_unlock(mtx3); my_unlock(mtx2); return NULL; } void *func3(void *arg) { my_lock(mtx3); sleep(1); my_lock(mtx1); printf(func3执行完成\n); my_unlock(mtx1); my_unlock(mtx3); return NULL; } int main(int argc, char const *argv[]) { init_hook(); init_graph(); // 补充初始化图 pthread_t t1, t2, t3; // 创建线程 pthread_create(t1, NULL, func1, NULL); pthread_create(t2, NULL, func2, NULL); pthread_create(t3, NULL, func3, NULL); // 等待线程进入阻塞状态关键确保状态稳定 sleep(3); // 等待线程阻塞 print_chain(); check_deadlock(); // 补充检测死锁并输出结果 // 死锁后线程不会退出CtrlC终止即可 pthread_join(t1, NULL); pthread_join(t2, NULL); pthread_join(t3, NULL); printf(complete\n); return 0; }https://github.com/0voice