一、背景

　　在工作項(xiàng)目使用多進(jìn)程、多線程過程中，因爭(zhēng)奪資源而造成一種資源競(jìng)態(tài)，所以需加鎖處理。如下圖所示，線程A想獲取線程B的鎖，線程B想獲取線程C的鎖，線程 C 想獲取線程D的鎖， 線程D想獲取線程A的鎖，從而構(gòu)建了一個(gè)資源獲取環(huán)，當(dāng)進(jìn)程或者線程申請(qǐng)的鎖處于相互交叉鎖住的情況，就會(huì)出現(xiàn)死鎖，它們將無(wú)法繼續(xù)運(yùn)行。

　　死鎖的存在是因?yàn)橛匈Y源獲取環(huán)的存在，所以只要能檢測(cè)出資源獲取環(huán)，就等同于檢測(cè)出死鎖的存在。

二、原理

　　在不改變項(xiàng)目源代碼的情況下，采用圖算法來(lái)檢測(cè)環(huán)的存在，使用有向圖來(lái)存儲(chǔ)；如線程A獲取線程B已占用的鎖（表示線程B獲取鎖成功），則為線程A指向線程B；啟動(dòng)一個(gè)線程定時(shí)對(duì)圖進(jìn)行檢測(cè)是否有環(huán)的存在。

（1）數(shù)據(jù)結(jié)構(gòu)

//數(shù)據(jù)/點(diǎn)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];//存儲(chǔ)圖的所有節(jié)點(diǎn)int num;//已經(jīng)使用了多少個(gè)struct node locklist[THREAD_MAX];int lockidx;pthread_mutex_t mutex;//預(yù)留：線程安全考慮，在對(duì)圖修改時(shí)加鎖};

（2）圖的操作

　　　　a.創(chuàng)建圖節(jié)點(diǎn)

//創(chuàng)建圖節(jié)點(diǎn)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é)點(diǎn)

//查找節(jié)點(diǎn)，是否存在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é)點(diǎn)

//添加節(jié)點(diǎn)，只是把添加的節(jié)點(diǎn)放到list中，還沒有確定各節(jié)點(diǎn)間的指向，必須通過add_edge添加邊來(lái)確定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é)點(diǎn)數(shù)累加}}

　　d.添加邊，指定方向

//添加邊，指定方向，誰(shuí)指向誰(shuí)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.檢測(cè)節(jié)點(diǎn)間是否有邊

//檢測(cè)節(jié)點(diǎn)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ǎng)h除的節(jié)點(diǎn)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，保證同一個(gè)節(jié)點(diǎn)只能遍歷一次path[k++] = idx;while(v->next !=NULL){dfs(search_vertex(v->next->d));k–;v = v->next;}return 1;}//遍歷圖，任意從圖的一個(gè)節(jié)點(diǎn)出發(fā)，對(duì)每一個(gè)節(jié)點(diǎn)進(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）啟動(dòng)檢測(cè)

C++后臺(tái)開發(fā)架構(gòu)師免費(fèi)學(xué)習(xí)地址：C/C++Linux服務(wù)器開發(fā)/后臺(tái)架構(gòu)師【零聲教育】-學(xué)習(xí)視頻教程-騰訊課堂

另外還整理一些C++后臺(tái)開發(fā)架構(gòu)師 相關(guān)學(xué)習(xí)資料，面試題，教學(xué)視頻，以及學(xué)習(xí)路線圖，免費(fèi)分享有需要的可以自行添加點(diǎn)擊 正在跳轉(zhuǎn) 群文件共享

　　啟動(dòng)線程定時(shí)檢測(cè)圖是否有環(huán)，代碼如下。

//從第0個(gè)節(jié)點(diǎn)開始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”);}}//檢測(cè)鎖線程funcstatic void *thread_func(void *args){while(1){sleep(5);check_dead_lock();}}//啟動(dòng)檢測(cè)鎖線程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

　　為了不改變項(xiàng)目原代碼，使用hook在應(yīng)用程序調(diào)用系統(tǒng)加鎖、解鎖API時(shí)進(jìn)行劫持，使其實(shí)際調(diào)用的是應(yīng)用程序定義的加鎖、解鎖API；再進(jìn)行加鎖、解鎖前，我們先去理解3個(gè)狀態(tài)，加鎖前、加鎖后、解鎖后，即：lock_before、lock_after、unlock_after，通過這三個(gè)函數(shù)與圖構(gòu)建起來(lái)，具體實(shí)現(xiàn)如下。

//1.沒有被其他線程占用，不用處理//2.有被其它線程占用，就要把邊構(gòu)建起來(lái)//添加邊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.沒有被其它線程占用//先加入一個(gè)節(jié)點(diǎn)add_edge//2.有被占用//是進(jìn)不來(lái)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);//不在死鎖檢測(cè)的圈里面了,所以刪除邊}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鉤子主要實(shí)現(xiàn)pthread_mutex_lock、pthread_mutex_unlock的劫持，具體實(shí)現(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

//測(cè)試樣例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();//啟動(dòng)檢測(cè)死鎖線程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;}

原文地址：死鎖檢測(cè)實(shí)現(xiàn) – MrJuJu – 博客園