一、背景
在工作項目使用多進(jìn)程、多線程過程中，因爭奪資源而造成一種資源競態(tài)，所以需加鎖處理。如下圖所示，線程A想獲取線程B的鎖，線程B想獲取線程C的鎖，線程 C 想獲取線程D的鎖， 線程D想獲取線程A的鎖，從而構(gòu)建了一個資源獲取環(huán)，當(dāng)進(jìn)程或者線程申請的鎖處于相互交叉鎖住的情況，就會出現(xiàn)死鎖，它們將無法繼續(xù)運行。
死鎖的存在是因為有資源獲取環(huán)的存在，所以只要能檢測出資源獲取環(huán)，就等同于檢測出死鎖的存在。
二、原理
在不改變項目源代碼的情況下，采用圖算法來檢測環(huán)的存在，使用有向圖來存儲；如線程A獲取線程B已占用的鎖（表示線程B獲取鎖成功），則為線程A指向線程B；啟動一個線程定時對圖進(jìn)行檢測是否有環(huán)的存在。
（1）數(shù)據(jù)結(jié)構(gòu)
//數(shù)據(jù)/點struct node{uint64 thread_id;//線程IDuint64 lock_id;//鎖IDint degress;};//數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)分開struct vertex{struct node *d;struct vertex *next;};struct graph{struct vertex list[THREAD_MAX];//存儲圖的所有節(jié)點int num;//已經(jīng)使用了多少個struct node locklist[THREAD_MAX];int lockidx;pthread_mutex_t mutex;//預(yù)留：線程安全考慮，在對圖修改時加鎖};
（2）圖的操作
a.創(chuàng)建圖節(jié)點
//創(chuàng)建圖節(jié)點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.查找節(jié)點
//查找節(jié)點，是否存在int search_vertex(struct node *d){int i;for (i = 0; i num; i++){if (tg->list[i].d->thread_id == d->thread_id){return i;}}
c.添加節(jié)點
//添加節(jié)點，只是把添加的節(jié)點放到list中，還沒有確定各節(jié)點間的指向，必須通過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++;//節(jié)點數(shù)累加}}
d.添加邊，指定方向
//添加邊，指定方向，誰指向誰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.檢測節(jié)點間是否有邊
//檢測節(jié)點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.刪除邊
//刪除邊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){//找到要刪除的節(jié)點remove = v->next;v->next = v->next->next;free(remove);break;}v = v->next;}}}
（3）圖遍歷
本文采用圖遍歷中最為常用的深度優(yōu)先搜索進(jìn)行遍歷，代碼如下。
//dfs深度遍歷int dfs(int idx){struct vertex *v = &tg->list[idx];if(visited[idx] == 1){//有環(huán)path[k++] = idx;print_deadlock();deadlock = 1;return 0;}visited[idx] =1;//被遍歷到了，賦值為1，保證同一個節(jié)點只能遍歷一次path[k++] = idx;while(v->next !=NULL){dfs(search_vertex(v->next->d));k–;v = v->next;}return 1;}//遍歷圖，任意從圖的一個節(jié)點出發(fā)，對每一個節(jié)點進(jìn)行dfs遍歷int search_for_cycle(int idx){struct vertex *v = &tg->list[idx];visited[idx] = 1;k = 0;path[k++] = idx;while(v->next != NULL){int i = 0;for (; i num; i++){if(i == idx){continue;}visited[i] = 0;}for(i = 1; i next->d));v = v->next;}}
（4）啟動檢測
C++后臺開發(fā)架構(gòu)師免費學(xué)習(xí)地址：C/C++Linux服務(wù)器開發(fā)/后臺架構(gòu)師【零聲教育】-學(xué)習(xí)視頻教程-騰訊課堂
另外還整理一些C++后臺開發(fā)架構(gòu)師 相關(guān)學(xué)習(xí)資料，面試題，教學(xué)視頻，以及學(xué)習(xí)路線圖，免費分享有需要的可以自行添加點擊 正在跳轉(zhuǎn) 群文件共享
啟動線程定時檢測圖是否有環(huán)，代碼如下。
//從第0個節(jié)點開始dfsvoid check_dead_lock(){int i = 0;deadlock = 0;for(;i num; i++){if(deadlock == 1) break;search_for_cycle(i);}if(deadlock == 0){printf(“no deadlock”);}}//檢測鎖線程funcstatic void *thread_func(void *args){while(1){sleep(5);check_dead_lock();}}//啟動檢測鎖線程void start_check(){tg = (struct graph*)malloc(sizeof(struct graph));tg->num = 0;tg->lockidx = 0;pthread_t tid;pthread_create(&tid,NULL,thread_func,NULL);}
（5）鉤子hook
為了不改變項目原代碼，使用hook在應(yīng)用程序調(diào)用系統(tǒng)加鎖、解鎖API時進(jìn)行劫持，使其實際調(diào)用的是應(yīng)用程序定義的加鎖、解鎖API；再進(jìn)行加鎖、解鎖前，我們先去理解3個狀態(tài)，加鎖前、加鎖后、解鎖后，即：lock_before、lock_after、unlock_after，通過這三個函數(shù)與圖構(gòu)建起來，具體實現(xiàn)如下。
//1.沒有被其他線程占用，不用處理//2.有被其它線程占用，就要把邊構(gòu)建起來//添加邊void lock_before(uint64 thread_id, uint64 lockid){int idx = 0;for(;idx lockidx;idx++){if(tg->locklist[idx].lock_id == lockid){struct node from;from.thread_id = thread_id;add_vertex(&from);struct node to;to.thread_id = tg->locklist[idx].thread_id;tg->locklist[idx].degress++;add_vertex(&to);if(!verifty_edge(&from, &to)){add_edge(&from, &to);//添加邊}}}}//1.沒有被其它線程占用//先加入一個節(jié)點add_edge//2.有被占用//是進(jìn)不來lock_after的////等unlock_after 釋放后//mtx沒有主人void lock_after(uint64 threadid, uint64 lockid) {int idx = 0;if(-1 == (idx = search_lock(lockid))){int eidx = search_empty_lock();tg->locklist[eidx].thread_id = threadid;tg->locklist[eidx].lock_id = lockid;inc(&tg->lockidx, 1);}else{struct node from;from.thread_id = threadid;struct node to;to.thread_id = tg->locklist[idx].thread_id;tg->locklist[idx].degress–;if(verifty_edge(&from, &to)){remove_edge(&from, &to);//不在死鎖檢測的圈里面了,所以刪除邊}tg->locklist[idx].thread_id = threadid;}}void unlock_after(uint64 threadid, uint64 lockid) {int idx = search_lock(lockid);if(tg->locklist[idx].degress == 0){tg->locklist[idx].thread_id = 0;tg->locklist[idx].lock_id = 0;}}
honk鉤子主要實現(xiàn)pthread_mutex_lock、pthread_mutex_unlock的劫持，具體實現(xiàn)如下。
int pthread_mutex_lock(pthread_mutex_t *mutex){pthread_t selfid = pthread_self();lock_before(selfid, (uint64)mutex);pthread_mutex_lock_f(mutex);//執(zhí)行系統(tǒng)加鎖的入口函數(shù)lock_after(selfid, (uint64)mutex);}int pthread_mutex_unlock(pthread_mutex_t * mutex){pthread_t selfid = pthread_self();pthread_mutex_unlock_f(mutex);//執(zhí)行系統(tǒng)解鎖的入口函數(shù)unlock_after(selfid, (uint64)mutex);}static int init_hook(){pthread_mutex_lock_f = dlsym(RTLD_NEXT,”pthread_mutex_lock”);pthread_mutex_unlock_f = dlsym(RTLD_NEXT,”pthread_mutex_unlock”);}
（6）Demo
//測試樣例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 *th_func1(void *arg) {pthread_mutex_lock(&mtx1);sleep(1);pthread_mutex_lock(&mtx2); pthread_mutex_unlock(&mtx2);pthread_mutex_unlock(&mtx1);}void *th_func2(void *arg) {pthread_mutex_lock(&mtx2);sleep(1);pthread_mutex_lock(&mtx3);pthread_mutex_unlock(&mtx3);pthread_mutex_unlock(&mtx2);}void *th_func3(void *arg) {pthread_mutex_lock(&mtx3);sleep(1);pthread_mutex_lock(&mtx1);pthread_mutex_unlock(&mtx1);pthread_mutex_unlock(&mtx3);}void *th_func4(void *arg) {pthread_mutex_lock(&mtx2);sleep(1);pthread_mutex_lock(&mtx3);pthread_mutex_unlock(&mtx3);pthread_mutex_unlock(&mtx2);}int main(){init_hook();//初始化hookstart_check();//啟動檢測死鎖線程pthread_t t1,t2,t3,t4;pthread_create(&t1,NULL,th_func1,NULL);pthread_create(&t2,NULL,th_func2,NULL);pthread_create(&t3,NULL,th_func3,NULL);pthread_create(&t4,NULL,th_func4,NULL);pthread_join(t1,NULL);pthread_join(t2,NULL);pthread_join(t3,NULL);pthread_join(t4,NULL);return 0;}
原文地址：死鎖檢測實現(xiàn) – MrJuJu – 博客園
