目錄

引言

一.理論聯立

1.死鎖的概念和原因

2.死鎖檢測的基本思路

?

3.有向圖在死鎖檢測中的應用

二.代碼實現案例（我們會介紹部分重要接口解釋）

1.我們定義一個線性表來存線程ID和鎖ID

2.表中數據的查詢接口

3.表中數據的刪除接口

4.表中數據的添加接口

5.before_lock接口

6.afterlock接口

7.after_unlock接口

8.加鎖和解鎖的接口

9.檢測死鎖的接口

三.結果展示

---

?

引言

死鎖是指在計算機系統中，多個進程（或線程）因競爭資源而造成的一種僵局，若無外力作用，這些進程（或線程）都將無法向前推進

我們將基于多個線程和多個互斥鎖來介紹死鎖的長生

?

一.理論聯立

1.死鎖的概念和原因

①.死鎖是操作系統和學術概念，指線程占用資源導致互相等待對方釋放資源的情況。

②.死鎖常見于多線程環境中，導致CPU占用率100%，出現死循環。

圖中有線程A，線程B，和線程C 三個線程 它們各自擁有自己各自的資源的情況下?其中

線程A想占用線程B的資源

線程B 想占用線程C的資源

線程C想占用線程A的資源?

最后形成了一個環 最后導致了死鎖

2.死鎖檢測的基本思路

①.死鎖檢測依賴于資源占用情況的檢測，通過判斷是否構成環來實現。

②.環的構成表示線程間形成了死鎖。

?

3.有向圖在死鎖檢測中的應用

①.有向圖是否成環的問題是死鎖檢測的底層算法。

②.通過有向圖來判斷是否構成環，從而檢測死鎖。

③.有向圖的構建通過節點和邊來表示線程和資源的關系。

④.環的檢測通過深度優先搜索（DFS）來實現。

?

?

?

二.代碼實現案例（我們會介紹部分重要接口解釋）

#include<stdio.h>
#include<pthread.h>
#include<unistd.h>
#define _GNU_SOURCE
#include <dlfcn.h>
#include<stdlib.h>#define MAX		100typedef unsigned long int uint64;struct rela_node{pthread_mutex_t *mtx;pthread_t thid;
};struct rela_node rela_table[MAX]={0};//search
pthread_t search_rela_table(pthread_mutex_t*mtx){int i = 0;for(i;i<MAX;i++){if(mtx==rela_table[i].mtx){return rela_table[i].thid;}}return 0;
}//dele
int dele_rela_table(pthread_t tid,pthread_mutex_t *mtx){int i =0;for(i;i<MAX;i++){if((rela_table[i].thid==tid)&&(rela_table[i].mtx==mtx)){rela_table[i].thid=0;rela_table[i].mtx=NULL;return 0;}}return -1;
}//add
int add_rela_table(pthread_t tid,pthread_mutex_t *mtx){int i =0;for(i;i<MAX;i++){if((rela_table[i].thid==0)&&(rela_table[i].mtx==NULL)){rela_table[i].thid=tid;rela_table[i].mtx=mtx;return 0;}}return -1;
}#if 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;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;}}}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;}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;}}int init_graph(void){tg=(struct task_graph*)malloc(sizeof(struct task_graph));tg->num=0;
}#endifvoid before_lock(pthread_t tid,pthread_mutex_t*mtx){pthread_t otherid=search_rela_table(mtx);if(otherid!=0){//mtx有線程在占用struct source_type from;from.id=tid;from.type=PROCESS;struct source_type to;to.id=otherid;to.type=PROCESS;add_edge(from,to);}}//如果走到after_lock 則表明mtx沒有被線程占用 把之前的邊刪除 然后我們占用該mtx
void after_lock(pthread_t tid,pthread_mutex_t*mtx){pthread_t otherid=search_rela_table(mtx);if(otherid!=0){//刪除舊邊struct source_type from;from.id=tid;from.type=PROCESS;struct source_type to;to.id=otherid;to.type=PROCESS;if(verify_edge(from,to)){remove_edge(from,to);}}//mtx無線程在占用 則占我們占用add_rela_table(tid,mtx);
}
void after_unlock(pthread_t tid,pthread_mutex_t*mtx){dele_rela_table(tid,mtx);//有小問題 這個死鎖工具可能只能檢測一次 如果存在解鎖情況 可能會導致after_lock mtx找不到舊線程id
}//檢測死鎖
void check_dead_lock(void){int i =0;for(i;i<tg->num;i++){search_for_cycle(i);}
}static void *thread_routine(void*arg){while(1){sleep(5);check_dead_lock();}
}
void start_check(void) {pthread_t tid;pthread_create(&tid, NULL, thread_routine, NULL);}#if 1  //hook
typedef int (*pthread_mutex_lock_t)(pthread_mutex_t*mtx);
pthread_mutex_lock_t pthread_mutex_lock_f=NULL;typedef int (*pthread_mutex_unlock_t)(pthread_mutex_t*mtx);
pthread_mutex_unlock_t pthread_mutex_unlock_f=NULL;typedef int (*pthread_create_t)(pthread_t *restrict thread, const pthread_attr_t *restrict attr,void *(*start_routine)(void *), void *restrict arg);
pthread_create_t pthread_create_f = NULL;int pthread_mutex_lock(pthread_mutex_t*mtx){// printf("before pthread_mutex_lock%ld,%p \n",pthread_self(),mtx);pthread_t selfid = pthread_self();before_lock(selfid, mtx);pthread_mutex_lock_f(mtx);// printf("after pthread_mutex_lock\n");after_lock(selfid,mtx);
}int pthread_mutex_unlock(pthread_mutex_t*mtx){pthread_t selfid = pthread_self();pthread_mutex_unlock_f(mtx);after_unlock(selfid,mtx);// printf("after pthread_mutex_unlock%ld,%p \n",pthread_self(),mtx);}int pthread_create(pthread_t *restrict thread, const pthread_attr_t *restrict attr,void *(*start_routine)(void *), void *restrict arg) {pthread_create_f(thread,attr,start_routine,arg);struct source_type v1;v1.id=*thread;v1.type=PROCESS;add_vertex(v1);
}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");}if (!pthread_create_f) {pthread_create_f = dlsym(RTLD_NEXT, "pthread_create");}}
#endif#if 1//debug
pthread_mutex_t mtx1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mtx2 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mtx3 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mtx4 = PTHREAD_MUTEX_INITIALIZER;void * t1_cb(void*arg){printf("pid1=%ld\n",pthread_self());pthread_mutex_lock(&mtx1);sleep(1);pthread_mutex_lock(&mtx2);pthread_mutex_unlock(&mtx2);pthread_mutex_unlock(&mtx1);}
void * t2_cb(void*arg){printf("pid2=%ld\n",pthread_self());pthread_mutex_lock(&mtx2);sleep(1);pthread_mutex_lock(&mtx3);pthread_mutex_unlock(&mtx3);pthread_mutex_unlock(&mtx2);}void * t3_cb(void*arg){printf("pid3=%ld\n",pthread_self());pthread_mutex_lock(&mtx3);sleep(1);pthread_mutex_lock(&mtx4);pthread_mutex_unlock(&mtx4);pthread_mutex_unlock(&mtx3);
}void * t4_cb(void*arg){printf("pid4=%ld\n",pthread_self());pthread_mutex_lock(&mtx4);sleep(1);pthread_mutex_lock(&mtx1);pthread_mutex_unlock(&mtx1);pthread_mutex_unlock(&mtx4);
}
int main(){init_graph();//有向圖的初始化init_hook();//hook函數的初始化pthread_t t1,t2,t3,t4;start_check();//開始檢測死鎖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_join(t1,NULL);pthread_join(t2,NULL);pthread_join(t3,NULL);pthread_join(t4,NULL);printf("complete\n");
}
#endif

具體代碼接口的實現

1.我們定義一個線性表來存線程ID和鎖ID

typedef unsigned long int uint64;struct rela_node{pthread_mutex_t *mtx;pthread_t thid;
};struct rela_node rela_table[MAX]={0};

2.表中數據的查詢接口

//search
pthread_t search_rela_table(pthread_mutex_t*mtx){int i = 0;for(i;i<MAX;i++){if(mtx==rela_table[i].mtx){return rela_table[i].thid;}}return 0;
}

?

3.表中數據的刪除接口

//dele
int dele_rela_table(pthread_t tid,pthread_mutex_t *mtx){int i =0;for(i;i<MAX;i++){if((rela_table[i].thid==tid)&&(rela_table[i].mtx==mtx)){rela_table[i].thid=0;rela_table[i].mtx=NULL;return 0;}}return -1;
}

4.表中數據的添加接口

//add
int add_rela_table(pthread_t tid,pthread_mutex_t *mtx){int i =0;for(i;i<MAX;i++){if((rela_table[i].thid==0)&&(rela_table[i].mtx==NULL)){rela_table[i].thid=tid;rela_table[i].mtx=mtx;return 0;}}return -1;
}

?

5.before_lock接口

void before_lock(pthread_t tid,pthread_mutex_t*mtx){pthread_t otherid=search_rela_table(mtx);if(otherid!=0){//mtx有線程在占用struct source_type from;from.id=tid;from.type=PROCESS;struct source_type to;to.id=otherid;to.type=PROCESS;add_edge(from,to);}}

我們傳入當前線程id和鎖

我們先對鎖進行判斷是否有線程在占用 如果有線程在占用我們則和該線程建立一條邊

6.afterlock接口

//如果走到after_lock 則表明mtx沒有被線程占用 把之前的邊刪除 然后我們占用該mtx
void after_lock(pthread_t tid,pthread_mutex_t*mtx){pthread_t otherid=search_rela_table(mtx);if(otherid!=0){//刪除舊邊struct source_type from;from.id=tid;from.type=PROCESS;struct source_type to;to.id=otherid;to.type=PROCESS;if(verify_edge(from,to)){remove_edge(from,to);}}//mtx無線程在占用 則占我們占用add_rela_table(tid,mtx);
}

我們要先判斷該鎖之前是否和其他線程建立邊 如果有我們就刪除舊邊 然后占用該把鎖

7.after_unlock接口

void after_unlock(pthread_t tid,pthread_mutex_t*mtx){dele_rela_table(tid,mtx);//有小問題 這個死鎖工具可能只能檢測一次 如果存在解鎖情況 可能會導致after_lock mtx找不到舊線程id
}

8.加鎖和解鎖的接口

int pthread_mutex_lock(pthread_mutex_t*mtx){// printf("before pthread_mutex_lock%ld,%p \n",pthread_self(),mtx);pthread_t selfid = pthread_self();before_lock(selfid, mtx);pthread_mutex_lock_f(mtx);// printf("after pthread_mutex_lock\n");after_lock(selfid,mtx);
}int pthread_mutex_unlock(pthread_mutex_t*mtx){pthread_t selfid = pthread_self();pthread_mutex_unlock_f(mtx);after_unlock(selfid,mtx);// printf("after pthread_mutex_unlock%ld,%p \n",pthread_self(),mtx);}

9.檢測死鎖的接口

//檢測死鎖
void check_dead_lock(void){int i =0;for(i;i<tg->num;i++){search_for_cycle(i);}
}static void *thread_routine(void*arg){while(1){sleep(5);check_dead_lock();}
}
void start_check(void) {pthread_t tid;pthread_create(&tid, NULL, thread_routine, NULL);}

?

三.結果展示

?