2022年源程序-分布式系统死锁探测 .pdf

/源程序-分布式系统死锁探测/Project:Deadlock Detection./Chandy MisraHaasedge chasingdeadlockdetection-(AND方式)/-/Project:Deadlock Detection./程序语言:C+/MPI 并行程序#includempi.h#include#include#include#include#include#include#includeusingnamespace std;/level1 functions:boolcheckDebug(intargc,char*argv);voidcall_end(intpSize,intmyid);boolcheckNumprocs(i#includempi.h#include#include#include#include#include#include#includeusingnamespace std;/level1 functions:boolcheckDebug(intargc,char*argv);voidcall_end(intpSize,intmyid);boolcheckNumprocs(intpSize,intnumprocs);multimap readEdge(char*argv,int&p1,int&pSize,int&numEdge);voidprobeSending_first(int*probe,vector&Sender_Tracker,multimap&myEdge,intii,intn_total,intn_ini,intdebug,intmyid,intMY_LITTLE_TAG,MPI_Status&名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 10 页 -myStatus,MPI_Request&myRequest);voidprobeSending_rest(int*probe,vector&Sender_Tracker,multimap&myEdge,intii,intn_total,intn_ini,intdebug,intmyid,intMY_LITTLE_TAG,MPI_Status&myStatus,MPI_Request&myRequest);voidprobeReceiving(int*probe,vector&Sender_Tracker,intii,intn_total,intmyid,intMY_LITTLE_TAG,MPI_Status&myStatus,MPI_Request&myRequest,vector&deadlock,vector&isReceiving);/level2 functions:voidDeadlockDection(multimap myEdge,intmyRank,intnumprocs,intpSize,intp1,intnumEdge,MPI_Status&myStatus,MPI_Request&myRequest,intargc,char*argv);intmain(intargc,char*argv)/mpiinitialization.intmyRank,numprocs;intpSize=0,p1=0,numEdge=0;MPI_Init(&argc,&argv);MPI_Comm_size(MPI_COMM_WORLD,&numprocs);MPI_Comm_rank(MPI_COMM_WORLD,&myRank);MPI_Request myRequest;MPI_Status myStatus;/Disableoutputbufferingon STDOUT so thatoutputisshown as soon as we write/itto thedisplay.setvbuf(stdout,NULL,_IONBF,0);/usea multimaptostoretheedge listmultimap myEdge=readEdge(argv,p1,pSize,numEdge);/implementthedetection;DeadlockDection(myEdge,myRank,numprocs,pSize,p1,numEdge,myStatus,myRequest,argc,argv);MPI_Finalize();return0;/*名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 10 页 -/level1 Function:checkDebug/This functioniscalledtoseta bool value=1ifthe excecutionisindebugging mode./Return Value/-/bool/Value Parameters/-/argvcharargument vector/argcintargument count/*boolcheckDebug(intargc,char*argv)stringoption(-debug);stringoption_dummy;if(argc=3)option_dummy=argv2;if(pare(option_dummy)=0)return1;elsereturn0;/*/level1 Function:readEdge/Functionto read the Edge List/Return Value/-/multimap/Value Parameters/-/argvcharargument vector/argcintargument count名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 10 页 -/p1inttheprocess thatsends out thefirstprobe/pSizeintnumber ofprocessesfrom theinput/numEdgeintnumber ofEdges from the input/*Thefollowinggivesa sample inputedge list:070 11 22 33 43 54 55 66 0-1-1Note that:thefirstlinemeans theprocess0 sends out thefirstprobe;thesecond linemeans thereare 7 nodes;the restisan edge list.0 1 means edge from process 0 to 1,1 2 means edge from process1 to2containgthe edgep1-p2,then row 1 and columb 2 is1;-1indicatestheend ofedge list.*/*multimap readEdge(char*argv,int&p1,int&pSize,int&numEdge)inte1,e2;/anedge is(e1,e2);multimap myEdge;/usea multimaptostoretheedge listFILE*f=fopen(argv1,r);fscanf(f,%d,&p1);fscanf(f,%d,&pSize);fscanf(f,%d,&numEdge);for(inti=0;i numEdge;i+)fscanf(f,%d,&e1);fscanf(f,%d,&e2);myEdge.insert(pair(e1,e2);fclose(f);returnmyEdge;名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 10 页 -/*/level1 Function:probeReceiving/Thisfunctioniscalledtosend probesotherthanthefirstprobe./arguments/-/int*probe:theprobe fordetection;/vector&Sender_Tracker:vectorthatstoressendersinfoateach roundofsendingofa probe;/intii:thenth round ofsendingouta probe;/intn_totalthe totalnumber ofprocesses;/intdebug:outputoption;/intmyid:therank ofprocess/intMY_LITTLE_TAG:mpi message tag;/MPI_Status&myStatus/MPI_Request&myRequest/vector&deadlock:whetherthe processison the deadlockedloop/vector&isReceiving:whethertheprocessreceiveda probe at laststep/*void probeReceiving(int*probe,vector&Sender_Tracker,intii,intn_total,intmyid,intMY_LITTLE_TAG,MPI_Status&myStatus,MPI_Request&myRequest,vector&deadlock,vector&isReceiving)for(intj=0;j n_total;j+)if(Sender_Trackermyid+n_total*j=1)MPI_Irecv(probe,3,MPI_INT,j,MY_LITTLE_TAG,MPI_COMM_WORLD,&myRequest);MPI_Wait(&myRequest,&myStatus);isReceivingii=1;/coutprobe0,probe1,probe2endl;if(probe0=probe2)deadlockmyid=1;名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 10 页 -/*/level1 Function:probeSending_rest/Thisfunctioniscalledtosend probesotherthanthefirstprobe./arguments/-/int*probe:theprobefordetection;/vector&Sender_Tracker:vectorthatstoressendersinfoateach round ofsendingofa probe;/intii:thenth round ofsendingouta probe;/intpSize:thetotalnumber ofprocessesfrom the input;/multimap&myEdge:the edge list/intp1:theprobe thatsendingout thefirstprobe;/intisDebug:outputoption;/intmyRank:the rankof process/intmyTag:mpi message tag;/MPI_Status&myStatus/MPI_Request&myRequest/*voidprobeSending_rest(int*probe,vector&Sender_Tracker,multimap&myEdge,intii,intpSize,intp1,intisDebug,intmyRank,intmyTag,MPI_Status&myStatus,MPI_Request&myRequest)multimap:iteratorit;it=myEdge.find(myRank);名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 10 页 -while(it!=myEdge.end()probe0=p1;probe1=myRank;probe2=it-second;MPI_Isend(probe,3,MPI_INT,probe2,myTag,MPI_COMM_WORLD,&myRequest);MPI_Wait(&myRequest,&myStatus);Sender_Trackerprobe2+pSize*myRank=1;if(isDebug=1)coutPROCESS myRank SENDS p1,myRank,probe2 TO PROCESS probe2endl;myEdge.erase(it);it=myEdge.find(myRank);/*/level1 Function:probeSending_first/Thisfunctioniscalledtosend the firstprobe./arguments/-/int*probe:theprobe fordetection;/vector&Sender_Tracker:vectorthatstoressendersinfoateach roundofsendingofa probe;/intii:thenth round ofsendingouta probe;/intpSize:thetotalnumber ofprocessesfrom the input;/multimap&myEdge:the edge list/intp1:theprobe thatsendingout thefirstprobe;/intisDebug:outputoption;/intmyRank:the rankof process/intmyTag:mpi message tag;/MPI_Status&myStatus/MPI_Request&myRequest/*名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 10 页 -voidprobeSending_first(int*probe,vector&Sender_Tracker,multimap&myEdge,intii,intpSize,intp1,intisDebug,intmyRank,intmyTag,MPI_Status&myStatus,MPI_Request&myRequest)multimap:iteratorit;it=myEdge.find(myRank);while(it!=myEdge.end()probe0=p1;probe1=p1;probe2=it-second;MPI_Isend(probe,3,MPI_INT,probe2,myTag,MPI_COMM_WORLD,&myRequest);MPI_Wait(&myRequest,&myStatus);Sender_Trackerprobe2+pSize*myRank=1;if(isDebug=1)coutPROCESS myRank SENDS p1,myRank,probe2 TO PROCESS probe2endl;myEdge.erase(it);it=myEdge.find(myRank);/*/level1 Function:call_end/This functioniscalledtoexitexecutionifthe number ofprocessdoes not match theinputfile./arguments/-/intpSize:thetotalnumber ofprocessesfrom the input;/intmyid:therank ofprocess/*名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 10 页 -*voidcall_end(intpSize,intmyid)if(myid=0)coutYoushouldusepSizeprocessestosimulatetheproblem!endl;MPI_Finalize();exit(1);/*/level2 Function:DeadlockDection/Thisfunctioniscalledtowrap up theimplementationof DeadlockDection./arguments/-/multimap&myEdge:the edge list/intpSize:thetotalnumber ofprocessesfrom the input;/intnumEdge:the totalnumber ofedges from theinput;/intp1:theprobe thatsendingout thefirstprobe;/intnumprocs:totalnumber ofprocessesthe program called./intmyRank:the rankof process/intmyTag:mpi message tag;/MPI_Status&myStatus/MPI_Request&myRequest/charargv:argumentvector/intargc:argument count/*voidDeadlockDection(multimap myEdge,intmyRank,intnumprocs,intpSize,intp1,intnumEdge,MPI_Status&myStatus,MPI_Request&myRequest,intargc,char*argv)multimap:iteratorit;if(pSize!=numprocs)call_end(pSize,myRank);boolisDebug=checkDebug(argc,argv);intmyTag=1;intprobe3;/initializetheprobe.probe0=-1;probe1=-2;probe2=-3;/prepareforthe simulationboolisDeadlock=0;vector deadlock(numprocs,-1);名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 10 页 -vector Sender_Tracker(pSize*numprocs,-1);/forcollectingsendersinfovector Tracker_dummy(pSize*numprocs,-1);vector isReceiving(pSize,0);for(intii=0;iipSize;ii+)Sender_Tracker=Tracker_dummy;/p1sendingoutthe firstprobeif(ii=0)&(myRank=p1)probeSending_first(probe,Sender_Tracker,myEdge,ii,pSize,p1,isDebug,myRank,myTag,myStatus,myRequest);for(inti=0;i=1)&(isReceivingii-1=1)probeSending_rest(probe,Sender_Tracker,myEdge,ii,pSize,p1,isDebug,myRank,myTag,myStatus,myRequest);MPI_Barrier(MPI_COMM_WORLD);/updatingsendersinfofor(intk=0;knumprocs;k+)MPI_Bcast(&(Sender_Trackerk*pSize),pSize,MPI_INT,k,MPI_COMM_WORLD);MPI_Barrier(MPI_COMM_WORLD);/receivingprobes.isReceivingii=0;probeReceiving(probe,Sender_Tracker,ii,pSize,myRank,myTag,myStatus,myRequest,deadlock,isReceiving);MPI_Barrier(MPI_COMM_WORLD);/checkifthe processison a deadlockedloopfor(inti=0;inumprocs;i+)MPI_Bcast(&(deadlocki),1,MPI_INT,i,MPI_COMM_WORLD);for(inti=0;inumprocs;i+)if(deadlocki=1)isDeadlock=1;isReceivingii=0;break;if(isDeadlock=1)break;for(inti=0;i10000;i+)MPI_Barrier(MPI_COMM_WORLD);if(isDeadlock!=1&myRank=0)cout THE SYSTEM IS NOTDEADLOCKEDendl;if(isDeadlock=1&myRank=0)cout THE SYSTEM IS DEADLOCKEDendl;名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 10 页 -