ѧ
JOURNAL OF SOFTWARE
1999ꡡ1011ڡVol.10No.111999



¼걸߼ʱ
ꡡǿ
ժҪԷֲʽӦϵͳҪȵ˳ѵö,ԭ֮һǷֲʽӦϵͳҪ˳ӵö.Ϊ˴ֲʽӦϵͳĸ,˶ԷֲʽӦϵͳ¼гĵԷ,ַûӲͬĲι۲ֲʽӦϵͳΪ.ڶԷֲʽӦϵͳеԺͳʱ,¼¼֮ڹϵҪ,߼ʱȷ¼ڹϵ.¸һּ¼걸߼ʱӵķ,ַķռ洢С,Ҽٶȿ.,л㷨ȷ֤.
ؼʡֲʽϵͳ,,,걸߼ʱ.
ͼšTP311
Abstraction Events' Complete Logical-time
DONG Hong SUN Yong-qiang
(Department of Computer Science and Engineering Shanghai Jiaotong University Shanghai 200030)
Abstract Debugging the distributed applications is very difficult. One of the reasons why this problem is made is that the distributed applications are inherently more complex than sequential ones. To solve this problem, the method of abstracting events is proposed, which lets the users grasp the various aspects of behaviors of a distributed application. Abstract event timestamp is used to decide the happened before relation among abstract events, which plays a very important role in abstracting and debugging the distributed applications. In this paper, a new complete algorithm of timestamping abstract event is proposed, which needs less storage and costs less time than others. Proofs of the correctness of the algorithms are also given in this paper.
Key wordsDistributed system, debugging, abstraction, complete logic-timestamp.
ֲʽӦϵͳԺƷֲʽϵͳһЩԶ˳,Щ໥Эͬһ,ͨϢͨͬ.ֲʽϵͳĳĳʱ״̬ǸýڴʱбֵԼ֮йصĻϢĴֵϢȣܺ,ϵͳ״̬н״̬ĺ.¼Ǹʱ״̬ıʵ壨ֵ½̵ȣ.
ԷֲʽϵͳҪȵ˳ѵö1,ԭ֮һǷֲʽϵͳҪ˳ӵö.Bates2,LumppCasavant3ݷֱ˶¼гķϵͳ,ʹûӲͬĲι۲ֲʽϵͳΪ.Zernikü򵥳ķʵһϵͳ4.¼ĳǰһ¼ϳһ¼,һϵͲĳ¼ϳһϸ߲εĳ¼.
(happened before)ϵӳ¼,ڵҪ,߼ʱȷڹϵͼķ5.¼߼ʱѹ㷺Ӧ,¼߼ʱӻۣ5,6֮,ĸһռ洢СҼٶȿĳ¼¼߼ʱӵļ㷽.
1 ¼Ĺϵ
1.1¼Ĺϵ
->ϵһ¼Ĺϵ:
(1) ¼abͬһP,ab֮ǰҲڷa֮b֮ǰPе¼,a->b;
(2) aһ̵ķ¼,bһ̵Ľa͵ϢĽ¼,a->b;
(3) abͬ¼,ô,a->bb->a.
ڹϵǹϵ->Էݱհ.¼abҽͬһ¼ʱͳ.d->c,ͳdΪcֱǰdֱc,cΪdֱӺ̻cֱӺd.
1.2¼Ĺϵ
ٶAΪһֲʽϵͳ¼,A¼iAA(bA:b->iA),A¼oAA(bA:oA->b).IAA¼ļ,OAA¼ļ.
¼ڹϵҲáʾ.¼AB,ABҽһ¼aAҴһ¼bB:ab,A->BAΪBֱǰBΪAֱӺ̣ҽһ¼oAAҴһ¼iBB:oA->iB,ABABǲеģ,ҽ(AB)(BA).
¼AB,׼ϵ:
(1) aA,bB:ab,AB;
(2) ABBC,ô,AC.
ABAB׼еģ,ҽ(AB)(BA).
ٶֲʽϵͳ¼ɵļPE,ԷֲʽϵͳгǹһPE1={E1,...,Em},PEE1...Em,EiEj=(1i,jm,ij).PE1ΪPEһγ󣨻,Ei(1im)Ϊ¼.PE1ٽг,PE2PE1ĳ,ô,PEĸ߲εģΣ.ͬ,PE2Ҳٽг,һֱȥ,ֱPEk{PEk-1}.
һֲʽϵͳPEPEn,¼A,BPEn,ABAB,ôͳΪȷ.ֻȷĳܷӳϵͳ3,7.ûԲͬϵͳòĺľԶֲʽϵͳʱ¼,,ͬʱЩǷȷĳ.James˰һĽṹгķ3,Cheung˶Գṹо8,ĿǰеĿʵõȷṹΪȫȳ󡢺ԼЭ.
2 ¼߼ʱӣevents' logical time
ֲʽϵͳPE߼ʱǸÿ¼ePEֵT(e)ļPT,ͨеֵT(e)PT¼ڹϵ.߼ʱ:1 ߼ʱӼ㷽,θ¼ePEֵT(e);2 ߼ʱӵжϷ,߼ʱֵT(e)PTȹϵ.
ڷֲʽϵͳPE߼ʱPT,e1,e2PE,e1e2T(e1)T(e2),(T(e1)T(e2)e1e2),ͳPTΪ걸(incompleted);e1e2T(e1)T(e2),ͳPTΪ걸(completed).
ںǹ涨,nάABֵ,ΪԶӦԪصֵɵnά,ٶC=max{A,B},Ci=max{Ai,Bi},i=1,...,n.
3 ¼߼ʱ
ȫȳ걸߼ʱף8Ѹ,ѳ¼߼ʱӽڸ¼߼ʱӵĻ֮,ÿ¼һ,ֻȫȳ,ӦΧϴĺԼЭ.
κȷ걸߼ʱǸÿ¼Eϣ¼ʱӵļETI¼ʱӵļETO5.ֳ¼߼ʱȱ:(1) ռڴ̫,ÿһ¼Ҫ롢¼ʱ,ϵͳN,Ҫ2NNά,NNľ;(2) ж¼A,Bȹϵʱѵʱ,ҪһȽATOBTI,ȽϲɹҪһBTOATIȽ,㷨ĸӶΪO(N2).ĸһ첽ϵͳ¿κȷ걸߼ʱ,ÿһ¼ֻһ,豣,ж¼ȹϵֻȽ,Ҳ,㷨ĸӶȽΪO(N).
ͨԳ¼ʷķ,첽ֲʽϵͳ³걸߼ʱ㷨Լ㷨ȷ֤.
3.1¼ʷ
3.1¼Ȼ. ٶP1,...,PNΪֲʽϵͳĽ,Pi(1iN)е¼ִΪei1,ei2,...,PEiΪPi¼ļ,PEi{ei1,ei2,...}.PE=PE1PE2...PENΪϵͳ¼ļ.PEiи¼ĳִ1,2,...Ϊ¼Ȼ.
3.2Ȼ¼Ȼ¼. һ¼EPE¼aPEiaE,bEbPEibȻŴaȻ,aΪEȻ¼,aĳ¼AٶaA,AΪEȻȼ;aż1b,aΪEֱȻ¼,Ӧĳ¼AΪEֱȻȼ.
3.3¼ʷ. ¼APEʷH(A)={bbBBA}A.H(A)PEiϵͶӰH(A)i=H(A)PEi.PEPE1PE2...PENΪȫ,,H(A)=H(A)1ݡH(A)2ݡ...H(A)N.
3.1. һֲʽϵͳPEһPE1¼A,BPE1,ABĪbBbH(A),(1) BH(A);(2) BA.
֤:ɳ֪,ϵͳеһ¼ֻһ¼,ͨ3.3ֱӵó.
3.2. һֲʽϵͳPEһPE1¼A,BPE1AB,ʷ׼ϵ֮:
(1) AB Iff AH(B);
(2) AB Iff AH(B)BH(A).
֤:ֱɶ3.3ó.Ӷ3.3ֱӵó첽ֲʽϵͳ¼AʷH(A)㷨1.
㷨1. ʷ㷨
(1) H(A)=A,ת(2);
(2) AֱȻȼ,ת(3),,ֱȻȼʷ¼뵽H(A),ٶAֱȻȼΪE1,...,Em,H(A)=H(E1)...H(Em)H(A),ת(3);
(3) A޽¼,,,з͸Ϣ¼ʷ¼뵽H(A),ٶAE1,...,EsϢ,H(A)=H(E1)...H(Es)H(A),.
3.3. Pii=1,...,N)¼PEi={ei1,...,eim},eijH(A)i,ei1,...,ei(j-1)H(A)i.
֤:ٶeijE,3.1֪,EA;ei1eij,...,ei(j-1)eij,ٶei1E1,...,ei(j-1)Ej1,E1EA,...,Ej-1EA,3.3,E1,...,Ej-1H(A),,ei1,...,ei(j-1)H(A);H(A)iݵĶ֪,۳.
3.4. NɵķֲʽϵͳPE,¼APEʷT(A)Nά,T(A)i=H(A)iݣ(i=1,...,N).
3.3˵,H(A)iݣ1iNԪص±̻,,H(A)ΨһNάT(A)ʾ.
3.4. A,BPEΪ¼,H(A),H(B)ֱΪǵʷ,T(A),T(B)ֱΪӦʷ,ô,T(H(A)H(B))=max{T(A),T(B)}.
֤:ɶ3.3Ͷ3.4,ͨ3.3ֱƳ.
3.2걸߼ʱ
ͨ3.4,ɴ㷨1ó첽ֲʽϵͳĳ¼ʷ㷨,㷨Ǳ¼߼ʱӵ㷨. 
3.5¼߼ʱӣ. ٶP1,...,PNΪһ첽ֲʽϵͳĽ,ϵͳĳ¼߼ʱӣʷ㷨2.
㷨2.
(1) VĳֵΪ0:Vk=0(k=1,...,N);
(2) ѡȡһδ¼E,EӦûֱȻȼ,ֱȻȼЩֱȻȼѴ,ѡE,,,ת(3);
(3) E:нPi(i=1,...,N),EmPi¼,Vi=Vi+m,T(E)i=Vi;EûPi¼,T(E)i=0,ת(4).
(4) EûֱȻȼ,ת(5);,T(E)ΪT(E)EֱȻȼʱӵֵ,ٶElֱȻȼE1,...,El,T(E)=max(T(E),T(E1),...,T(El)),ת(5);
(5) EûнϢ¼,ת(6);,T(E)ΪT(E)ѸEĽϢ¼ϵֵ,ٶEsϢ¼r1,...,rsѸеT(E1),...,T(Es),T(E)=max(T(E),T(E1),...,T(Es)),ת(6);
(6) EûзϢ¼,ת(2);,ٶEtϢ¼s1,...,st,ӦĽϢ¼Ϊr1,...,rt,ÿri(i=1,...,t)´ת(2).
riĳ¼ErѴ,T(Er)=max{T(Er),T(E)};,T(E)ri.
,ͼ14ɵ첽ֲʽϵͳһȷʱͼ,߿ʾ¼,¼߼ʱΪ:

ͼ1 Ľ첽ϵͳȷʱͼ
T(G)=0,0,0,2, T(E)=max{0,2,2,0, T(H)}=0,2,2,2,
T(A)=max{2,0,0,0, T(E)}=2,2,2,2, T(B)=max{4,4,0,0, T(E),T(A)}=4,4,2,2,
T(H)=max{0,0,4,4,T(E),T(G)}=0,2,4,4, T(C)=max{6,6,0,0,T(B),T(I)}=6,6,6,6,
T(I)=max{0,0,6,6,T(C),T(H)}=6,6,6,6, T(D)=max{8,0,0,0,T(C)}=8,6,6,6,
T(J)=max{0,0,0,7,TI}=6,6,6,7,
T(F)=max{0,8,8,0,T(C),T(J),T(I)}=6,8,8,7,
T(K)=max{0,0,9,8,T(F),T(J)}=6,8,9,8.
3.6. u,vΪnά߼ʱ.
(1) uvIffukݡvk(k=1,...,m);
(2) u<vIffuvuv;
(3) uvIff(uv)(vu).
֤3.5Ͷ3.6첽ֲʽϵͳ걸߼ʱ.
3.5. һNɵ첽ֲʽϵͳPE¼A,BPE:
(1) ABIffT(A)T(B);
(2) ABIffT(A)T(B).
֤:(1) ٶAB,3.2,AH(B);3.3͵Ĵ,H(A)H(B),,H(A)kH(B)k(k=1,...,N),ӶT(A)k=H(A)kݣܣH(B)kݣ=T(B)k(k=1,...,N),T(A)T(B).
֮,ٶT(A)T(B),3.3֪,H(A)kH(B)k(k=1,...,N),H(A)H(B);AH(A)H(B),3.1,AB.
(2) (1)͡ԼĶֱӵó.
3.1. 첽ֲʽϵͳPEĳPE1ȷ,ô,3.5Ͷ3.6PE1еĳ¼߼ʱ걸.
֤:A,BPE1,(1) ȷĶ֪,AB,aA,bB:ab,AB;(2) ɵĶ֪,ABAB;ۺ(1)(2),3.5ֱӵó.
4  
3.5Ͷ3.6첽ֲʽϵͳ³¼걸߼ʱ,ÿ¼ʱֻһ,Ļ¼걸߼ʱӼ˶ڴͼ,㷨ӶO(N2)ΪO(N).㷨1㷨2첽ϵͳ,Ͷ֤ѿ,Ƕʺͬϵͳ,㷨2жͬ¼ӦĴ,ͬ¼ɷ¼¼,ͬҲʺͬϵͳ.
ĿоõȻѧ.
߼飺,1959,ʿ,ҪоΪֲʽϵͳ,.
ǿ,1931,ڣʿʦ,ҪоΪ.
ߵλϺͨѧѧ빤ϵϺ 200030
ͨѶϵ:꣬Ϻ 200030,Ϻͨѧѧ빤ϵ
ο
1Cheng Wing-hong, Black J P, Manning E. A frame work for distributed debugging. IEEE Software, 1990,7(1):106115
2Peter Butes. Distributed debugging tools for heterogeneous distributed systems. In: Davis C T ed. Proceedings of the 8th International Conference on Distributed Computing System. San Jose, CA: IEEE Computer Society Press, 1988.308315
3Lumpp J E, Jr Casavant T L, Siegel H J et al. Specification and identification of events for debugging and performance monitoring of distributed mutiprocessor systems. In: Gerard Le Lann, Walt Koheler eds. Proceedings of the 10th International Conference on Distributed Computing Systems. Paris: IEEE Computer Society Press, 1990. 476483
4Dror Zernik, Marc Snir, Daliamaki. Using visualization tools to understand concurrency. IEEE Software, 1992,9(3):8792
5Reinhard Schwarz, Friedemann Mattern. Detecting casual relationships in distributed computations: in search of the holy grail. Distributed Computing, 1994,7(3):149174
6Suresh K. Damodaran-Kamal, Brown J S. Toward heterogeneous distributed debugging. Technical Report, No. LAUR-97-906, Los Alamos National Laboratory, Los Alamos, NM-87545, 1997
7Kunz T. Event abstraction: some definition and theorems. Technical Report, TI-Z/93, Darmstadt: Technical Univer-sity, 1996
8Cheung Wing-hong. Process and event abstraction for debugging distributed programs. Technical Report T-189, Computer Communications Network Group, Ontario: University of Waterloo, 1992
1998-03-11յԭ,1998-11-23յ޸ĸ
