ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.2P.235-239



ڹͼĻؾ㷨͹ϻָ
ӱµлܽũ
ժҪͼṹķֲʽģ(extended graph-oriented model,ExGOM)ṩһֶ֧̬õϵͳ.ϵͳĶ̬ðϵͳʱʱԼֹϺ.Ϻ漰֮һλָϵͳԭ״̬,ؾʹ,˻ڹͼ첽ؾ㷨͹ϻָ.㷨ͲԿʱежϽ̵.첽ؾϻָ㷨,㷨ֲ,Թнڵлؾ,ӶЧؽϵͳ.
ؼʣֲʽ,,ؾ,ϻָ.
ţTP311
Rollback Algorithm and Crash Recovery Based on Fault-Sensitive Graphs
LIU YingCHEN Dao-xuXIE Li
(State Key Laboratory for Novel Software Technology Nanjing University,Nanjing,210093)
CAO Jian-nong
(Department of Computing Hong Kong Polytechnic University,Hong Kong)
AbstractExtended graph-oriented distributed programming model (ExGOM) provides a system architecture to support dynamic configuration.Dynamic configuration involves system expansion and shrink during execution,upgrading while running,and reconfiguration after a fault occurs.One problem in reconfiguration is how to recover the system to the consistent states that exist just before the occurrence of faults.This paper is focused on this problem and proposes an asynchronous rollback algorithm and a crash recovery mechanism based on fault-sensitive graphs.The issue of multiple faulty processes on a single transient faulty host is addressed.Compared with other asynchronous rollback and recovery algorithms,the algorithm presented in this paper localizes the region of faults.Only fault-sensitive nodes are rolled back.This results in a minimized system overhead.
Key wordsDistributed programming,checkpoint,rollback,crash recovery.
ͼṹķֲʽģ(extended graph-oriented model,ExGOM)ṩһֶ֧̬õϵͳ.ֶֶ֧̬,ϵͳʱͼϵͳʱϵͳģ滻Լϵͳйϻԭ(縺ءЧʵ)µĸ̵ӳ.ڵ3,Ǩ,ָ,Ҫʵر̵״̬,Թϻָ,ַҲΪ㡱.Ŀǰ,ⶼдڼ㷨о14,д¿ɷΪͬ첽.ͬ,нЭ㶯Իһȫһµ״̬.첽,ÿ̸Զؽм㶯,ϻָʱЭؾһȫһ״̬.Ϣģ͵ķֲʽϵͳ,̳½״̬,䴫ݵϢ.ĸĻؾ㷨͹ϻָ첽㷽ʽ.
1 ϵͳģ
Ϊ˸õ˵,ڽҪܻؾ͹㷨ϵExGOMģ.
ExGOMµķֲʽӦó3ɣ5ݣ߼ṹͼӦóԼӦóͼнڵٵӳϵ.ûڸģ±дֲʽӦóʱȶһ߼ṹͼ,߼ͼṹӳ˸Ӧ½̼ĳʼ̬ϵ,ûҲͨڵ߶ǱڵĽ̹ϵ.ʵڵζŷϵĽһӦüɲУڵϵĽ̶̬.һߵ˵Ϊʵڵ,ñΪʵ,Ϊ.ɼ,߱һһ̬Ľ̼ǱڵͨŹϵ.Ȼûڶͼṹ֮,ͼṩĶֲд.߼ͼṹӳϵڸӦõļж.ִһExGOMӦʱ,ϵͳȡϢ,춯ִ̬ͼDEG(dynamic execution graph),ӳϵ̲.˺ϵͳάִ̬ͼ.
ÿһϵͳĺ(kernel).ÿ˶άһDEG.,DEGһµ.ϵͳĺ˽ṹͼ1ʾ.SLG(static logical graph)ûĳʼ߼ͼṹ,FSG(fault-sensitive graph)ǵϷDEGõĹͼ.

Fig.1Core structure of run-time system
ͼ1ϵͳĺ˽ṹ
2 ͼ
ϵͳ⵽ĳ̨ʱ,֪ͨصϵͳ,ϵͳǼӳ,ҳڸϵн,DEGϱע.ͼ2һйϽ̵DEG.

Fig.2DEG with fault processes tagged
ͼ2йϽ̵DEG
FSGһͽṹ,ĶĳһϽڵ(ĳһڵϵĽΪϽʱ,ýڵǹϽڵ).ϽڵDEGеĸڵͺӽڵ㶼ӽFSG,FSGиڵıҲӽFSG.ٶÿFSGƬϽڵ(ڶļʱ).ͼ2ɵõͼ3ʾFSGƬ,ͼ3ҲԿFSGеĽڵп໥.

Fig.3FSG derived from DEG
ͼ3DEGõFSG
FSGΪǿǵһֲʽӦеĳһ̷Ϻ,Զڸý̵ĽӦԼִȥؾ,ҲǱԺĻؾ㷨͹ϻָĻ˼.ϵͳյĹ֪ͨϢ󼴹𱾵ؽ,״̬ΪABNORMAL.˺,ϵϵͳҲ.ĳؽڷϢ,䷢ͶϺ󱻹.͵Ϣɱϵͳһ,ΪTEM-QUEUE.,ڸϵͳͬʱֹתϻָ,һϵͳпյϵͳתϢ,ЩϢҲ豣.,ǹеĽһյNORMALϢؾͿɼִ.ϸ̽ںڸ.
3 ؾ㷨
3.1 
ԲϢģ͵ķֲʽӦ˵,Ӧÿɿ¼,һÿյһϢʹһ״̬תһ״̬.ף1нϢΪ¼,ei,jʾPiĵj¼,si,jʾ¼ei,j״̬,SENTi,j(e)ʾ¼eΪֹPi͵PjϢ,RECDi,j(e)ʾ¼eΪֹPiյPjϢ.ϵͳΪÿһؽ̱һϵSENTRECD.ÿͻһϢ,ӦĲ1,Ϣһ𱣴浽ȶĴ洢(Ӳ̡Ŵ).һϵͳռϵĿ.ڽΪ۵Ĵ洢ʶ,Ϊһǿе,ڽĹԽоЧؽϵͳһ.
Ϸ״̬һ.ؾ㷨ĿļҪҵһȫֵһ״̬.Ƕһȫֵһ״̬һ¼,ÿڸüһ¼Ӧ,¼eiej֮SENTi,j(ei)RECDj,i(ej)ԼSENTj,i(ej) RECDi,j(ei).,ҪϢ.
3.2ؾ㷨
ؾ㷨ɷݹϺϵͳ.ϵͳȴϵͳ߼ͼṹĿ,Ȼͨϵͳ¼Ķ̬ϢõDEG,DEGõFSG.,ǷֱϵϵͳִеĻؾ㷨(㷨1)ϵͳִеĻؾ㷨(㷨2).
㷨1.
while FSGδ loop
rbiFSGڵϹϽPi¼
if FSGһϽPkthen
rbkPk¼
if SENTk,i(rbk)RECDi,k(rbi) then
Piؾֱ¼e,ʹSENTk,i(rbk)RECDi,k(e);
rbie;
else if SENTi,k(rbi)RECDk,i(rbk) then
Pkؾֱ¼e,ʹSENTi,k(rbi)RECDk,i(e);
rbke;
ȱFSG:
ifĽPjһ then
PlΪPjڽڵĸڵϵḶ̌
if PlΪϽؾ״̬Ϊrblthen
PjϵϵͳUPDATE(SENTl,j(rbl),Pj);
end loop
㷨2.
while յϢ loop
if ϢΪUPDATE(SENTi,j(rbi),Pj)Ϣ then
ȶ洢еõPj¼rbj
if SENTi,j(rbi)RECDj,i(rbj) then
Pjؾֱ¼e,ʹSENTi,j(rbi)RECDj,i(e);
rbje;
end loop
eiΪPi¼,ejΪPj¼.֤SENTi,j(ei)RECDj,i(ej)SENTj,i(ej)RECDi,j(ei)ͬʱ.֤£
֤Ϊ,ǷֱSENTi,j(ei)RECDj,i(ej)дΪSENT(ei)RECD(ej).SENT(ei)RECD(ej),ζPiϢmϷ.SENT(ei)δ,PjյϢmRECD(ej)Ѹ.ڴ֮ǰ,PiPj״̬һµ.SENT(ej)RECD(ei),ζPj¼ejϢm䵫ȴδSENT(ej),PiյϢmҸRECD(ei).Ƕ¼Ķ弰ei,ejֱΪPiPj¼ǰ,mPjյm.Ϣ͵ļٶ,m¼ei󵽴Pi,Pi¼ei,,PiյϢm䲢RECD(ei).SENTi,j(ei)RECDj,i(ej)SENTj,i(ej)RECDi,j(ei)ͬʱ.
䲻ͬʱ,㷨еĵĵͿԱ֤Ϊһȫһ״̬.
4 ϻָ
ϵͳ,ָҪTEM-QUEUEеϢ.(㷨3)
㷨3.
while TEM-QUEUEǿloop
ifϢǷؽ thenýдϢ,ỵ́
ifϢǷһϽ then
ifϢǷһԶ thenг洦
end loop
ϵͳ㲥TEM-FINISHϢ
ifյϵͳTEM-FINISHϢ
thenתִ㷨4; elseȴ.
ϵͳִлؾ㷨,Ȼõһ״̬Ͻ,״̬־ΪNORMAL.㷨4Ҫ˻ָеǰϵͳδԱؽ̵Ľ뷢ԼδNORMALϢ.
PfΪһԭϽ,efΪؾ㣻PnΪĳFSGϵһ,enΪؾ,enlΪ¼PuΪһκFSGϵ.
㷨4.
ifϢPfһϽ thenг洦
if ϢPfPn then
ϵͳг洦,ȻתԶ̵ϵͳԶϵͳȼ״̬־
if ״̬־ΪABNORMAL then
if RECD(en)SENT(ef) then
if enenlthen enΪһ¼յϢ
else Pn״̬־ΪNORMAL,,ڽ̷NORMALϢ
if PfPf͵Ϣ thenг洦
if PfPn͵Ϣ then
if Pn״̬־ΪABNORMAL then
ϵͳRECD(ef)תԶϵͳԶϵͳӵSENT(en)RECD(ef);
if SENT(en)RECD(ef) then
ӱĿĵΪPfķϢҵRECD(ef)1Ϣ͸Pf
if Ϊenenlthen
Pn״̬־ΪNORMAL,,ڽӽ̹㲥NORMALϢ
if ϢǷĳؽPkNORMALϢ then
if Pk״̬־ΪABNORMAL then
if PkĳһFSG then
״̬־ΪNORMAL,,вһFSGϵڽӽ̹㲥NORMALϢ.
ͨ㷨,һ֪̽Ͻ̺ʱ,ִ.
5 ᡡ
ؾ㷨ϻָĿǰдо,о˸ַ14,68.ּΪЩʱֶ֧̬õͼṹķֲʽģ(ExGOM)ṩʱϵݴ.ؾ㷨ϻָڹͼ֮,ʹӦ㷨н̶лؾ,ǹеĽ̲ػؾ,Ӷ˻ָĿ.
ʱϵݴõϵݴ.,ͨʵݴϵͳԼʱػǶڵؽϢƵԵ.Ϸ,ɶԵлָ.ʱ,Եɲʱϵݴ.
Ŀоõ863߿ƼĿ(No.863-306-ZT02-03-01)ʽѧо
.
߼飺ӱ,Ů,1973,ʿ,ҪоΪֲʽϵͳ,м,ݴ.
µ,1947,,ҪоΪֲʽϵͳ,м,.
л,1942,,ʿʦ,ҪоΪмֲʽ.
ܽũ,1960,ʿ,,ҪоΪֲʽϵͳ,ݴ.
ߵλӱ(Ͼѧ¼صʵҡϾ210093)
µ(Ͼѧ¼صʵҡϾ210093)
л(Ͼѧ¼صʵҡϾ210093)
ܽũ(ѧϵ)
οף
1Venkatesan S,Tony Tong-ying Juang,Sridhar Alagar.Optimistic crash recovery without changing application messages.IEEE Transactions on Parallel and Distributed Systems,1997,8(3):263270
2Wong K E,Franklin M.Checkpointing in distributed computing systems.Journal of Parallel and Distributed Computing,1996,35(1):6775
3Sunondo Ghosh,Melhem R,Daniel Mosse.Fault-Tolerance through scheduling of aperiodic tasks in hard real-time multiprocessor systems.IEEE Transactions on Parallel and Distributed Systems,1997,8(3):272284
4Wei Xiao-hui,Ju Jiu-bin.Checkpointing algorithms in distributed systems.Chinese Journal of Computers,1998,21(4):367375
(κ,Ͼű.ֲʽϵͳеļ㷨.ѧ,1998,21(4):367375)
5Liu Ying,Xie Li,Cao Jian-nong.GOM:a graph-oriented model for distributed programming.Chinese Journal of Computers,1998,21(1):1825
(ӱ,л,ܽũ.ͼṹķֲʽģGOM.ѧ,1998,21(1):1825)
6Pankaj Jalote.Fault Tolerance in Distributed Systems.Englwood Cliffs,NJ:PTR Prentice Hall,Inc.,1994
7Smith S W,Johnson D B.Minimizing timestamp size for completely asynchronous optimistic recovery with minimal rollback.In:Proceedings of the 15th IEEE Symposium on Reliable Distributed Systems.1996.6675
8Plank J S.Improving the performance of coordinated checkpointers on networks of workstations using RAID techniques.In:Proceedings of the 15th IEEE Symposium on Reliable Distributed Systems.1996.7685
ոڣ1998-09-15
޸ڣ1999-02-02
