校招VIP，专题

死锁检测实现的原理？

资源获取环可以采用图来存储，使用有向图来存储。线程A获取线程B已占用的锁，则为线程A指向线程B。如何为线程B已占用的锁？运行过程线程B获取成功的锁。检测的原理采用另一个线程定时对图进程检测是否有环的存在。数据结构定义:图算法，检测成环#define_GNU_SOURCE#include<dlfcn.h>#include<stdio.h>#include<pthread.h>#include<unistd.h>#include<stdlib.h>#include<stdint.h>#include<unistd.h>#defineTHREAD_NUM10typedefunsignedlongintuint64;typedefint(*pthread_mutex_lock_t)(pthread_mutex_t*mutex);pthread_mutex_lock_tpthread_mutex_lock_f;typedefint(*pthread_mutex_unlock_t)(pthread_mutex_t*mutex);pthread_mutex_unlock_tpthread_mutex_unlock_f;#if1//graph#defineMAX100enumType{PROCESS,RESOURCE};structsource_type{uint64id;enumTypetype;uint64lock_id;intdegress;};structvertex{structsource_types;structvertex*next;};structtask_graph{structvertexlist[MAX];intnum;structsource_typelocklist[MAX];intlockidx;pthread_mutex_tmutex;};structtask_graph*tg=NULL;intpath[MAX+1];intvisited[MAX];intk=0;intdeadlock=0;structvertex*create_vertex(structsource_typetype){structvertex*tex=(structvertex*)malloc(sizeof(structvertex));tex->s=type;tex->next=NULL;returntex;}intsearch_vertex(structsource_typetype){inti=0;for(i=0;i<tg->num;i++){if(tg->list[i].s.type==type.type&&tg->list[i].s.id==type.id){returni;}}return-1;}voidadd_vertex(structsource_typetype){if(search_vertex(type)==-1){tg->list[tg->num].s=type;tg->list[tg->num].next=NULL;tg->num++;}}intadd_edge(structsource_typefrom,structsource_typeto){add_vertex(from);add_vertex(to);structvertex*v=&(tg->list[search_vertex(from)]);while(v->next!=NULL){v=v->next;}v->next=create_vertex(to);}intverify_edge(structsource_typei,structsource_typej){if(tg->num==0)return0;intidx=search_vertex(i);if(idx==-1){return0;}structvertex*v=&(tg->list[idx]);while(v!=NULL){if(v->s.id==j.id)return1;v=v->next;}return0;}intremove_edge(structsource_typefrom,structsource_typeto){intidxi=search_vertex(from);intidxj=search_vertex(to);if(idxi!=-1&&idxj!=-1){structvertex*v=&tg->list[idxi];structvertex*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;}}}voidprint_deadlock(void){inti=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);}intDFS(intidx){structvertex*ver=&tg->list[idx];if(visited[idx]==1){path[k++]=idx;print_deadlock();deadlock=1;return0;}visited[idx]=1;path[k++]=idx;while(ver->next!=NULL){DFS(search_vertex(ver->next->s));k--;ver=ver->next;}return1;}intsearch_for_cycle(intidx){structvertex*ver=&tg->list[idx];visited[idx]=1;k=0;path[k++]=idx;while(ver->next!=NULL){inti=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;}}#if0intmain(){tg=(structtask_graph*)malloc(sizeof(structtask_graph));tg->num=0;structsource_typev1;v1.id=1;v1.type=PROCESS;add_vertex(v1);structsource_typev2;v2.id=2;v2.type=PROCESS;add_vertex(v2);structsource_typev3;v3.id=3;v3.type=PROCESS;add_vertex(v3);structsource_typev4;v4.id=4;v4.type=PROCESS;add_vertex(v4);structsource_typev5;v5.id=5;v5.type=PROCESS;add_vertex(v5);add_edge(v1,v2);add_edge(v2,v3);add_edge(v3,v4);add_edge(v4,v5);add_edge(v3,v1);search_for_cycle(search_vertex(v1));}#endif#endifvoidcheck_dead_lock(void){inti=0;deadlock=0;for(i=0;i<tg->num;i++){if(deadlock==1)break;search_for_cycle(i);}if(deadlock==0){printf("nodeadlock\n");}}staticvoid*thread_routine(void*args){while(1){sleep(5);check_dead_lock();}}voidstart_check(void){tg=(structtask_graph*)malloc(sizeof(structtask_graph));tg->num=0;tg->lockidx=0;pthread_ttid;pthread_create(&tid,NULL,thread_routine,NULL);}#if1intsearch_lock(uint64lock){inti=0;for(i=0;i<tg->lockidx;i++){if(tg->locklist[i].lock_id==lock){returni;}}return-1;}intsearch_empty_lock(uint64lock){inti=0;for(i=0;i<tg->lockidx;i++){if(tg->locklist[i].lock_id==0){returni;}}returntg->lockidx;}#endifintinc(int*value,intadd){intold;__asm__volatile("lock;xaddl%2,%1;":"=a"(old):"m"(*value),"a"(add):"cc","memory");returnold;}voidprint_locklist(void){inti=0;printf("print_locklist:\n");printf("---------------------\n");for(i=0;i<tg->lockidx;i++){printf("threadid:%ld,lockid:%ld\n",tg->locklist[i].id,tg->locklist[i].lock_id);}printf("---------------------\n\n\n");}voidlock_before(uint64thread_id,uint64lockaddr){intidx=0;//list<threadid,toThreadid>for(idx=0;idx<tg->lockidx;idx++){if((tg->locklist[idx].lock_id==lockaddr)){structsource_typefrom;from.id=thread_id;from.type=PROCESS;add_vertex(from);structsource_typeto;to.id=tg->locklist[idx].id;tg->locklist[idx].degress++;to.type=PROCESS;add_vertex(to);if(!verify_edge(from,to)){add_edge(from,to);}}}}voidlock_after(uint64thread_id,uint64lockaddr){intidx=0;if(-1==(idx=search_lock(lockaddr))){//locklistoperainteidx=search_empty_lock(lockaddr);tg->locklist[eidx].id=thread_id;tg->locklist[eidx].lock_id=lockaddr;inc(&tg->lockidx,1);}else{structsource_typefrom;from.id=thread_id;from.type=PROCESS;structsource_typeto;to.id=tg->locklist[idx].id;tg->locklist[idx].degress--;to.type=PROCESS;if(verify_edge(from,to))remove_edge(from,to);tg->locklist[idx].id=thread_id;}}voidunlock_after(uint64thread_id,uint64lockaddr){intidx=search_lock(lockaddr);if(tg->locklist[idx].degress==0){tg->locklist[idx].id=0;tg->locklist[idx].lock_id=0;//inc(&tg->lockidx,-1);}}intpthread_mutex_lock(pthread_mutex_t*mutex){pthread_tselfid=pthread_self();//lock_before(selfid,(uint64)mutex);pthread_mutex_lock_f(mutex);lock_after(selfid,(uint64)mutex);}intpthread_mutex_unlock(pthread_mutex_t*mutex){pthread_tselfid=pthread_self();pthread_mutex_unlock_f(mutex);unlock_after(selfid,(uint64)mutex);}staticintinit_hook(){pthread_mutex_lock_f=dlsym(RTLD_NEXT,"pthread_mutex_lock");pthread_mutex_unlock_f=dlsym(RTLD_NEXT,"pthread_mutex_unlock");}pthread_mutex_tmutex_1=PTHREAD_MUTEX_INITIALIZER;pthread_mutex_tmutex_2=PTHREAD_MUTEX_INITIALIZER;pthread_mutex_tmutex_3=PTHREAD_MUTEX_INITIALIZER;pthread_mutex_tmutex_4=PTHREAD_MUTEX_INITIALIZER;void*thread_rountine_1(void*args){pthread_tselfid=pthread_self();//pthread_mutex_lock(&mutex_1);sleep(1);pthread_mutex_lock(&mutex_2);pthread_mutex_unlock(&mutex_2);pthread_mutex_unlock(&mutex_1);return(void*)(0);}void*thread_rountine_2(void*args){pthread_tselfid=pthread_self();//pthread_mutex_lock(&mutex_2);sleep(1);pthread_mutex_lock(&mutex_3);pthread_mutex_unlock(&mutex_3);pthread_mutex_unlock(&mutex_2);return(void*)(0);}void*thread_rountine_3(void*args){pthread_tselfid=pthread_self();//pthread_mutex_lock(&mutex_3);sleep(1);pthread_mutex_lock(&mutex_4);pthread_mutex_unlock(&mutex_4);pthread_mutex_unlock(&mutex_3);return(void*)(0);}void*thread_rountine_4(void*args){pthread_tselfid=pthread_self();//pthread_mutex_lock(&mutex_4);sleep(1);pthread_mutex_lock(&mutex_3);pthread_mutex_unlock(&mutex_3);pthread_mutex_unlock(&mutex_4);return(void*)(0);}intmain(){init_hook();start_check();pthread_ttid1,tid2,tid3,tid4;pthread_create(&tid1,NULL,thread_rountine_1,NULL);pthread_create(&tid2,NULL,thread_rountine_2,NULL);pthread_create(&tid3,NULL,thread_rountine_3,NULL);pthread_create(&tid4,NULL,thread_rountine_4,NULL);pthread_join(tid1,NULL);pthread_join(tid2,NULL);pthread_join(tid3,NULL);pthread_join(tid4,NULL);return0;}

来自：操作系统-死锁-死锁检测