ѧ
JOURNAL OF SOFTWARE
1999 1 No.1 1999



һֻڼľػָǨϵͳ*
֣γᡡ
ժҪChaRMһֲгϻָǨϵͳ.ʵ˶ԹվȺϵͳ˲ʱϵĻָ,ͨʱMirror洢ͽǨƼ,ʵ˶ԻȺϵͳùϵĻָ,֧ϵͳӲάԴ/ʱʹúͶ̬ƽȹ.ҪChaRMϵͳļؾָǨƵʵּ,˲.
ؼʡ,ؾָ,Ǩ,վȺ.
ͼšTP393
A Checkpoint-based Rollback Recovery and Process Migration System 
WANG Dong-sheng SHEN Mei-ming ZHENG Wei-min PEI Dan 
AbstractChaRM is a checkpoint-based backward fault recovery and process migration system. It is designed to recovery the fault of NOWs (networks of workstations) by checkpointing and rollback recovery. It offers functions of on-line software and hardware maintenance, process migration and load balance, etc. ChaRM is able to run on NOWs that change over time due to failure, load or availability. As long as there is at least one node alive in the cluster, the computation will complete in an efficient manner. The checkpointing, rollback recovery and process migration techniques, and some performance evaluation results are discussed in this paper.
Key wordsCheckpointing, rollback recovery, process migration, NOWs (networks of workstations).
ִ졢աʵ硢ʯ͵ӦԼϵͳܺͿɿԽԽߵҪ.д߼㲻ӦЧ;.ݴ߼ɿԵҪ֤.վȺNOW(networks of workstations)еĹվԴ,ͨĳֽṹɵĲϵͳ.ûͶʷСṹչԺáûɼ̳ԭеԴ̷㲢ҹ򵥵ص,ĿǰѳΪдչ֮һ.NOWŹģĲ,ڼзϵļҲָ,ͬʱNOWͨΪûʹ,Դʱ,һʱܲٿ,нϴĿɱ.ϵͳڷ쳣¼ʱᵼ±βмĳʧ,ǰĴ㲻ٿ,磺вͬӦóû쳣¼ĳҪռCPUԴ,ֹûýԴ쳣ػܽ(˲ʱ/Ъ/)ϣϵͳ,άȵ.
ģѧִ̼ʱ䶼ϳ,һĳ㷢쳣¼,ϵͳʧ,򲻵òͷʼִ.Ϊ˱ϵͳڷ¼ڴͷʼִжϵĴ˷,߻ȺϵͳĿ,ϵͳеʵʱü(Checkpoint),ϵͳʱĹ淶״̬,Ը̽Ըٺͼ¼.ϵͳϺ,ؽ̻ؾ(Rollback)ǰϵͳһ״̬(),״ָ̬Ӹü㴦ִ,Ǵӳʼִ,Ӷʡ˴ظʱ,ֻȺϵͳĲ.ֻڼĺָԶϵͳ˲ʱ/ЪϽԶָ,Ҳǻָδ֪ϡĳһӦƹδԤϵĹϵΨһֶ.1
ChaRM(checkpoint-based rollback recovery and process migration)ΪʵֹվȺϵͳݴܺʵָƽƵĲглؾָǨ.ChaRMʵ˶ԻȺϵͳ˲ʱϵĻָ,ͨʱMirror洢ͽǨƼ,ʵ˶ԻȺϵͳùϵĻָ֧ϵͳάԴʱʹúͶ̬ƽ.
1 ˼Ŀ
ʵֲ/ֲϵͳݴķж:ʹݴӲЧ,ڼӵеĻȺϵͳȥӦصķԭﴦҪģ(ϢģͲ)֧֣ķʵʱϵͳ,ҪʹöĴ,ЩЧӦڹվȺϵͳ.ؾָCRR(checkpointing and rollback recovery)Ϊһָֺ,ͨϵͳйü,ϵͳʱһ״̬,ͨĻؾ(ļ)ʵֶϵͳϵĻָ.ͬʱ,ҲʵֽǨơҵгԵЧֶ.
еĲ/ֲϵͳCRR¿ԷΪʽЭʽ24,ǰһַʽ,̶üҪ໥Э,޶ȵ̵,ŵЧӦ.Ϣ¼Message-logging)ǱŵЧӦЧֶ.÷ֶȷģPDM(piecewise deterministic model),ͨϢ¼ȷطŻƱ˶ŵЧӦķ.ЭʽԱŵЧӦ,ϵͳΪ˽,ҪϢ,ͬͨŴ۽ϴ.һϵͳ˵,ͨΪϵͳлڼ¼Ķ÷ʽЭļ÷ʽС,ΪΪϵͳһ״̬µͬ.ͨٶȽϵͳ˵,ȷʵ,ΪʱϵͳʱϢ¼ԽС.ڲлȺϵͳ˵,ͨٶȵĲ,Ϣ¼Ĵ۷ЭĴҪ.ڼܼͲӦ˵,оʵ,Э÷ʾϺõ,Ҿлؾ̡ʵּ򵥡ҪԽִеķֶȷԼ,ͬʱ̶̹ϵŵ.ϵͳ϶Ҫؾָʱ,ϵͳؽֻؾһ,ϵͳֻ豣һ,,ռ(Garbage Collection)㷨.
Эļ÷ʽлؾСָ㷨򵥡洢Сռռ򵥵ŵ,CoCheck5,MIST(migration and integrated scheduling tools)6ݵϵͳѡַʽ.ChaRMҲЭļü.ChaRMϵͳ¹ܺص:
.Զָ˲ʱ/ù;
.òкļ÷ʽ,Сϵͳд;
.ͬʱ֧ݴǨ;
.ûʵ,ʹñ׼UNIXϵͳ,޸UNIXں,ҪӲ֧,ڲͬUNIX汾;
.û͸,ϵͳпʽṩû.ûʹʱֻ轫ӦóĿļChaRMṩп,ʽԶʽʹϵͳݴǨƵȹ;
.ڲм㻷ͨſ֮ʵ,һֲ. 
2ChaRMϵͳṹ
Ϊ벢лȺϵͳϵͳǺ,лؾָϵͳѡPVMΪг򿪷.ϵͳ4ģ鹹ɣ
.ܿģ(ChaRM-manager)Эϵͳáϵͳ⡢Ǩؾȹ
.ؾָģ(CRR)ʱЭнü,ϵͳʱȫһ״̬,ϵͳ쳣¼ʱ,гĻؾָ
.ϵͳģ(WatchD)ͨЭ,쳣Լdaemon״̬,ʱChaRM-manager,ԱChaRM-managerо߲Ӧ
.Ǩļģ(Mig&Mir)ϵͳĽǨ,ļĴ洢ȹ.
ϵͳṹͼ1ʾ.ϵͳʱ,ͨʱTimerԵ֪ͨϵͳִмò,ChaRM-managerЭϵͳͬü.WatchD⵽ʱ,error¼ؾǰļλ,ͨϢĻָ(Restore)ͳط(Replay)ԼҪʱĽǨ,ﵽϻָĿ.msg-filterڼڽдͨеϢ(in-Transit),Ϣ¼(Message-logging).

ͼ1ChaRMϵͳ߼ṹ
3 ChaRMϵͳCRRǨƻ
3.1 ChaRMϵͳúͻؾָ
ChaRMϵͳͨЭ֮ʵ,ͨͨɿļ,ʱ뿼ϵͳ״̬һµĹ¶Ϣ;Ϣ.Ϊ,һܵķѡʵķʱܿ;Ϣͨͨ״̬.ڶͨͨ״̬ļ޷ͨſ֮ʵ,ǲöʱļ뷽ʽ,ʱѡ޷ȷ.һܵķڼ֮⸨Զ;Ϣļ¼,ؾָʱЩϢط.ڼ㷢ʱ,Щ;Ϣͣ硢ϵͳ塢ͨſ⻺֮еκһ,ڲϵͳͨſǰ,ֱӷЩطԻȡ;Ϣǲܵ.
ChaRMϵͳĽ,ڼ㷢ʱ,ͨͨ״̬;Ϣ,ǽͨŻƱϡ;Ϣ,ͬʱӳļ,մﵽ޹¶ϢͶʧϢȫ״̬½Ŀ.ʵϾPVMͨͨFIFO ,ͨſ֮ʵһЭ.ϵͳԲκβм㻷רýcinitΪЭĹ,õ֧ڲͬлĿֲ.Э.
1ͬ
(1.1) cinit̡õЭcinitӦý̷ͬźCKPTSIG,
(1.2) Ӧý̡ÿӦýյCKPTSIG,Ӧý̷͡׼Ϣ
RDY MSG,
(1.3) Ӧý̡ÿӦýͣ,͵Ϣ,ֱյӦý̵RDYMSG.ڴ˹,յRDYMSGϢ(ϡ;ӦϢ),浽ԤָĽջ,
(1.4) Ӧý̡˳PVM.
2ü.ɵȫּ״̬һ.
(2.1) Ӧý̡ü,
(2.2) Ӧý̡¼PVM,
(2.3) Ӧý̡cinitRJNMSG(old-tid,new-tid)Ϣ,
(2.4) cinit̡ݸ̵RJNMSG,֯ƥ(mapping-table),
(2.5) cinit̡Ӧý̹㲥mapping-table,
(2.6) Ӧý̡յmapping-table,Եƥ,׶.
ЭЭcinitӦý̷ͬźCKPTSIG,Эи̼ͬ,ͨͨFIFO,ڹ¶Ϣ.ͬʱ,յĳӦý̵RDYMSGʱ,ƶϴӱ˽̵̵ĵͨͨѱ,ϵ;Ϣڣ,ѱ̲Ʊ.,(1.3),Ӧý̿Կ϶дӦý̵ͨͨϵ;Ϣѱ϶ǰ,ȫ״̬ΪӦý״̬()ɵļ.,֤Эõļһȫּ.ChaRMҲƵЭʵͬؾ,˴.
3.2ChaRMϵͳǨƻ
̴ԴǨĿĻĹ,ʵCRRʵֵĽԴĹĿĻĻָ.ǨƷʱ,ϵͳĿĻΪԴǨƽ̴һǼܽ,,Ǩƽü,ֱͨUNIX׽֣SocketͨǼܽ.,ǨƽԶֹ.Ǽ̴ܽͨж,̽״ָ̬Ϊ㱣״̬,Ӵ˼.,Ч,Ǩƽ̴ԴǨƵĿĻִ.
Ϊ˱֤ϵͳǨƹе״̬һ,ӦñǨƷʱӦý̷Ǩƽ̵;Ϣ,ͬʱǨڼǨƽ̷Ǩƽ̵ӦϢ.Ǩƹ̼£
1ͬ.ǨƷʱ,ΪⷢǨƽ̵;Ϣ,ʹϻƽЩϢǨƽ̲ǰ.ֻиǨƽNMP(non-migration process)ǨƽMP(migration process)ϢͨҪ,Эʽв.
(1.1) NMPMP̷RDYMSGϢ
(1.2) MPȴӦý̵RDYMSG.ڴڼ,յRDYMSGϢ,Ǳ϶ӦϢ,浽ض.NMPճ.
2Ǩ.ʱ,MP;Ϣȫǰ.MP,ϢͨsocketֱӴ͵ĿĻ,ĿĻϻָ.NMPճִ.ǨϺ,ָ̽ű仯֪ͨcinit,cinitָн̸ӳ.
ڴЭ,NMPǨƷʱMPRDYMSGϢ,ԼǨƽʱcinitָ¸ӳ,һֱļ.
һΪʵֽǨ,ҪʮָӵϢת,Ϊ޸PVM daemon̵ʵϢʧ,ChaRMʹˡӳٷ֧͡첽Ǩ.ɼ,Ǩڼ䷢Ǩƽ̵ӦϢ,ӳٵӳºʵʷ,ȷطĿĻϵĻָ.,ӳٷϢӦóдĸӿС,:һ,ϢִеĹؼ·,˷ӳٶԷͽ̣NMPļֱӰ죻һ,ڽս̣MPֱǨӳº,ż,ӦϢ,,ӳٵǨϺִ,ΪȴϢִʱ.
3.3㾵ùϻָ
ͨıŵλ,ǿʵֲͬݴģʽ.㱣浽شֻ˲ʱϻЪ.RAIDredundant arrays of inexpensive disksݴ˼,ǿѡλöָù.ڼʱ˾ƽ洢,Ͻ̵ļ㱣浽ش,ͬʱ̨,ЩļϢؾ.,ĳ㷢ù,ִеӦóļϢϻ,Ӽ㴦ؼظӦó.Ҫmm1,ҽ轫ÿÿ̵ļϢڱش,mĴ.ɼ,mùϵļ㾵ʽһļ㱾شŷʽmĿռ俪.ƽ洢֤ϵͳԽùϵĻָ,ұ˻ָĸزƽ.
4ܲԼعȽ
,Ƕ4дԵĿѧӦýмúͻؾָܲ.ʹõĲƽ̨4̨SUN SPARC20վ(32Mڴ,1GӲ,Solaris2.4ϵͳ)ͨ10M EthernetӶɵĻȺϵͳ.ChaRMϵͳָҪǼõʱ俪Ϳռ俪(ƽÿμø̽ļļСܺ).ͬʱ,Ϊ˿㱣ҪŻʽдʱܵĸ,ǻϸʹдʱŻʽµļʱ俪.1Ƚʹͬļͽͬļ,ŻʽдʱŻʱ俪.ɼ,дʱŻʹд뱾ش㲢,̶ͬȵؼ˼õʱ俪.Խ,4ӦóĲͬ,ؾָͬļ㶼ܵõȷļôʱӶС5%,ƽÿμõʱ俪С1%ƽÿμõĿռ俪ӦóģĲͬ仯ܴ.
1 ŻдʱÿȽ 
޼ʱ4̨ʱ
(s)/ռ俪
(s/Mֽ)Żдʱ
4̨ʱ
(s)ʱ
(%)

λʱ

()4̨ʱ
(s)ʱ
(%)

λʱ俪()

180*180,300718.43100/8.9744.913.6975.27726.581.1371.62

512*512,502883.83300/27.92970.243.0093.332933.661.7391.92
ƫ΢ַ
N=28,T=100001248.34100/13.11281.062.62122.181270.211.75121.46
ƫ΢ַ
N=29,T=1000519.33100/31.7535.203.0556.11530.302.1154.22
任
100008774.11600/9.58939.601.89141.358848.050.84140.60
EMBAR(167)709.21100/6.4716.891.0871.55709.910.1070.14
ǽڼõĲгؾָͽǨϵͳChaRM,CoCheck5,MIST6ݽ˱Ƚ.2ʾ,ChaRM̳CoCheckMISTû͸ûʵ֡Эļüƺ͹ص,ҽCoCheckͨſ֮ʵԼMIST֧첽ǨƵŵ.ͬʱ,ChaRMCRRƹ̲ڲм㻷ʵ,õ֧ڲͬл֮Ŀֲ.ChaRMϵͳʵ˶ԽN-ùϵ̺ϵͳڼú͹ϻָгֵĹ(CRR)Ĺ. 
2 ڼõĲгؾָͽǨϵͳȽ 

ChaRMCoCheckMIST
 û͸̡̡
 ûʵ̡̡֡
 ͨſ֮ʵ̡̡֡
 Эʽá̡̡
 첽Ǩơ̡
 CRRϡ̡
 N-ùϵ̡̡
 ̲ڲм㻷̡

оõ863߿ƼĿ
߽ܣ,1966,ʿ,,ҪоΪд,ݴ.
,Ů,1938,,ʿʦ,ҪоΪ/ֲܼϵͳ.
֣γ,1946,,ʿʦ,ҪоΪ/ֲϵͳ,б.
ᵤ,1973,˶ʿ,ҪоΪǨ,ϻָ.
ͨѶϵˣ, 100084,廪ѧѧ뼼ϵ
ߵλ֣γᡡ廪ѧѧ뼼ϵ100084
E-mail: wds@tsinghua.edu.cn 
ο
1Plank J S, Kim Y et al. Fault-tolerant matrix operations for networks of workstations using diskless checkpointing. Journal of Parallel and Distributed Computing, 1997,43(2):125138
2Plank J S, Beck M, Kinsley G. Libckpt: transparent checkpointing under Unix. http: www.cs.utk.edu/plank/plank/papers/USEUIX-95w.html
3Chandy K M, Lamport L. Distributed snapshots: determining global states of distributed systems. ACM Transactions on Computer Systems, 1985,3(1):6375
4Koo R, Toueg S. Checkpointing and rollback-recovery for distributed systems. IEEE Transactions on Software Engi-neering, 1987,13(1):2331
5Stellner G, Pruyne J. Resource management and checkpointing for PVM. In: Hermes P P eds. Proceedings of the 2nd Europe PVM User Group Meeting. 1995. 131136
6Casas J, Clark D et al. MIST: PVM with transparent migration and checkpointing. http: www.cse.ogi.edu/DISC/projects/mist/
1997-10-06յԭ,1998-01-19յ޸ĸ 
