ѧ
JOURNAL OF SOFTWARE
1999 6 10 Vol.10 No.6 1999



ֲʵȫLOTOS淶ת
л »ɽ
ժҪLOTOS淶,´ϵͳܹ淶,ʵϵͳķֲ,Ƶʵϵͳṹģ黯淶ת.ñעȫLOTOSԹ淶︴ӵϵͳֲ,оʹù㲥ͨŷʽЭͬġֱӴģ黮ֵĹ淶ֽ㷨.
ؼʡֲʽϵͳ,̴,LOTOS淶,淶ֽ.
ͼšTP393

Decomposition Transformation for the Distributed 
Implementation of Full LOTOS Specification
XIE BingCHEN Huo-wangWANG Bing-shan
(Department of Computer Science Changsha Institute of Technology Changsha 410073)
Abstract In this paper, based on the LOTOS specification language, the authors present the transformation which starts from the functional specification and the distributed properties of target system to the corresponding modular specification. The authors present the tagged specification to represent the complex distributed properties of the full LOTOS specifications and study the decomposition transformation of full LOTOS specification which using the broadcasting communication gates in the system's internal coordinating communications and directly decomposing the multiple subsets.
Key wordsDistributed system, process algebra, LOTOS specification, specification decomposition.
ϵͳܹ淶ʵϸ޹ص.ڷֲʽϵͳʵʱ,ԱҪƳģĹܹ淶.Щģִֵϵͳ,ͨģͨţЭͬʵϵͳܹ淶.оһ㷨,ʹԱȷĿϵͳķֲԺ,ֱƵģ黯淶.ֹ淶תɱʾΪϵͳܹ淶+ʵϵͳֲԪϵͳģ黯淶,Ϊ淶ֽⷽ.ӦڷֲϵͳĲ,ģ淶ϿԷֽһķֲģ淶.ظʹù淶ֽⷽ,տɵõȫĿϵͳṹģ淶,ӶϵͳĽṹƹ.
LOTOS1,2ISO֯Ϊŵķֲʽϵͳƶһֹ淶.ڣһϵͳͨⲿ۲쵽Ľʱϵ.LOTOS淶ķֲʵвٵо3,4,ԲݲֵĻLOTOS淶оΪʽķֽⷽ,һоһΪķֽⷽ.ȫLOTOSԹ淶,о˸ӵϵͳֲԼ,ʹù㲥ͨŷʽЭͬĶģֱӷֽת㷨.
1 ϵͳķֲʵģ
ֲϵͳɷֲĴģ.ÿģ鶼ܶΪ,ģͨһͨŽṹЭͬ.ĵо·ֲϵͳģ:1 ϵͳֹ֧㲥ͨŷʽ2 ҪЭͬģ֮䶼ֱͨŵ3 ͨŵǿɿ,бϢ˳޶ʧӵ.
1.1. ֲϵͳDSһԪ,DS=M,BG,
.M={m1,...,mn}ϵͳķֲģ鼯
.BGģͨž,gij...kBG,Ϊg={mi,mj,...,mk}.
ʹsyncij...kΪģmi,mj,...,mkЭͬžض.ģmiϵΪýPiʾ,ģ̼P={P1,...,Pn}ģ鼯M.Զ1.1еžBG,S1,S2P,SGS1,S2={syncij...kt1,t2{i,j,...,k},Pt1S1Pt2S2}ʾS1ģS2ģͨž.
1.2. ֲϵͳ淶ͨڲͨЭͬĹ淶,еڲͨΪ.һֲϵͳDSģ黯淶SPECDS
SPECDS=hide BG in (P1SG{P1},{P2,...,Pn}ݣ(P2SG {P2},{P3,...,Pn}ݣ(P3...SG{Pn-1},{Pn}ݣPn)...)).
2ϵͳķֲԼע淶
ȫLOTOSϵͳаΪֺݲ.Ӧϵͳķֲʵ,3Ĺ淶ԪأݡݲΪֲܷڲͬģ.Щ淶ԪϾעӦķֲģ,γ˱ע淶,Դ˱ϵͳʵʷֲ.
һ򻯵ԶȡATMΪ.ATMž:In-cardǿƬ,ӿ϶ûʺ;InڽûȡĿļ;Outû;Displayʾ;Comͨſ,ͬеķͨ.淶еmoney-boxATMдĻ.ATMΪ3ģ:ûӿڲ(user-part)ΪP1,ͨŻ(communicator)ΪP2,Ǯϻ(box)ΪP3.ӳʵϵͳֲԵıע淶:
Proc ATMIn-card(P1),In(P1),Out(P3),Display(P1),Com(P2)(money-box(P3):Money-type):noexit:=
In-card(P1)?Account-no;In(P1)!GET-PASSWORD?password;Com(P2)!Account-no!password;
(Com(P2)!PASS-OK;
(In(P1)!GET-MONEY?m:Money;Com(P2)!GET-MONEY!m;
(Com(P2)!OK;Out(P3)!m;(Display(P1)!SUCCESSCom(P2)!SUCCESS )
ATMIn-card(P1),In(P1),Out(P3),Display(P1),Com(P2)(new-money(P3)=Dec-Money(P3)(money-box,m))
ۣCom(P2)!NOT-ENOUGH;Display(P1)!ERROR;
ATM In-card(P1),In(P1),Out(P3),Display(P1),Com(P2)(money-box(P3))))
ۣCom(P2)!PASS-INVALID;ATMIn-card(P1),In(P1),Out(P3),Display(P1),Com(P2)(money-box(P3))
)
endproc
ϵͳֲԵһݱԪģ鼯,Դӱע淶зõ,ref(x)ʾ.ATMݱԪģ鼯:ref(money-box)={P3}, ref(m)={P1,P2,P3},ref(money-box)={P3}, ref(Account-no)={P1,P2}, ref(password)={P1,P2}.
3 淶ֽת㷨
ֲģе,ģΪǲ.,ֲģͨͨЭʵϵͳ.ϵͳΪ˳ϵ,ǰΪֲڲͬģ,Ҫͬ¼Ա˳ϵ.һ,ֲģܾ.ҪͨģĴֵͨЭ֤ͬݱԪȫʵʱһ.ɼ,ϵͳڲдͬͨźʹֵͨЭͬ.ֽת㷨оʹͨŽЭͬķ.
3.1 ϵͳڲЭͬ¼
оΪʽĹ淶ֽ,ҪֵֿܲЭͬ¼,Эͬ¼м淶ṹϢͬͬ¼.
ṹϢǹ淶ṹı.¼ʽ:(1) ԭ淶P,ֲģPkеӦʹõڲЭͬ¼ӦС!PʽĽṹϢ;(2) ѡΪB1ۣ...ۣBn,i֧BiӦĸģϵӦΪTkBiеڲЭͬ¼ӦС!ciʽĽṹϢ;(3) ԲΪB1...ݣBn,i֧BiӦĸģϵӦΪTkBiеڲЭͬ¼ӦС!piʽĽṹϢ.
LOTOSԵ﷨嶨,ǽϵͳڲЭͬ¼Ϊsyncij...kd1...dnʽΪ,syncij...kϵͳеڲͨŵ,di(1in)ΪṹϢֵž.
3.2 ֽת㷨
淶ֽת㷨ݹ淶Ԫصķֲ,оģ淶Ĳ.ǰֽ⡢ԭΪֽ⡢Ϊʽֽͽáֽ4ηֱо淶ֽת㷨.ÿ,пܵķֲת.ƪ,ҪݲֽΪʽֽ.
ģPi,Ti:ע淶Piģ淶Ϊת.ڷֽвڲЭͬ¼Ҫʹù淶ṹϢ,˳ΪֽΪķֲģй,ԿɽTiΪע淶ṹϢģϢPiģ淶.ںĵת㷨ȷ˽ṹϢģϢĲʹ.
ڱĵ㷨,Ϊ﷽,θi,synciid=,Ϊմ.
3.2.1 ݲֽ㷨
ԭ淶УһݲԱԪһֲģִеĲ,Ҫȼֵ,ͽ.һ,һֵԪǶģĹԪ,òִϺ,ӦɢֵԪʵʱֵ.ɴ,һtķֲʵְ3˳ִв:ǰΪTi-f(t)tִǰЭͬ;Ϊ任Ti-m(t)תtֽʽ;ΪTi-b(t)tִкӦЭͬΪ.ݲֽ,ͨģĴֵͨЭͬ,ȷݱԪʵʱһ.
ֶģ乲ݱԪϵͳȫӳһµĻƿԼΪ:ÿԪxģϾһxľֲӳ.ģxľֲӳ,xֵʱ,ʹģͬϵӳֵ.ͨ㲥ʽͬ,ref(x)Ϊ{Pi,Pj,...,Pk},㲥ž趨Ϊsyncij...k.ʹsyncref(x)ʾž.
tֲģPi,淶ֽĽṹϢΪdx,ģPk,
Tk(t,i,dx):=Tk-f(t,i,dx);Tk-m(t,i,dx);Tk-b(t,i,dx),
iΪtֲģ,;Ϊָ,Ϊ˳ϵ.
tĲͬ,Ըת㷨:
(1) ı任

(2) ִǰЭͬΪ

(3) ִкЭͬΪ

3.2.2 ԭΪֽ㷨
ԭΪֽ,Ϊģ黮ֽͶӰ,ΪеݲҪʹòֽ㷨ȷͬģЭͬ.ΪеıԪֵ?x,迼xĹԣԾǷxԪʵʱֵĴ.ȫLOTOSԹ淶ԭΪĲͬʽ,Լ漰ĹݺݲķֲλãֱӦת.,g(Pi)?xķֽ㷨:

3.2.3 Ϊʽֽ㷨
Ϊʽֽ㷨Ϊʱϵķֲʵ.ǶԼֻΪʽֱ.Ϊӵıʽֽ.
(1) Ϊǰ׺ʽֽⷽ.Ϊ˳ϵɸݸΪԼִеΪģ飬ȷҪͬͨ.
3.1. һΪʽB,ĿΪPosAct(B)ݹ鶨:
(1) Ϊǰ׺ΪʽB=a;B,PosAct(B):={a};
(2) ѡΪʽ
(3) ԲΪʽ
(4) Խʵproc,proc=B,PosAct(B):=PosAct(proc):=PosAct(B).
3.2. Mod(a)ΪΪaĻģ,ΪBĿΪģ鼯Ϊ
PAMS(B)={Mod(a)aPosAct(B)}.
,Ϊǰ׺ʽ:B=atag(a);Btag,ģPjķֽת㷨Ϊ
Tj(B,dx,pams)=Tj(atag(a),dx);Tsyncj(Pi,dx,PAMS(Btag));Tj(Btag,dx,pams).
Tsync(Pi,dx,PAMS(B))ΪڲЭͬΪ,:

ʽ,Tsyncj(Pi,dx,PAMS(Btag))Ҫģ䴿ͬЭͬ.aΪĺЭͬΪԼPosAct(B)ΪǰЭͬΪҲϵͳΪͬϵ.,ɵĴͬ¼ɴ˻.
(2) ˳Ϊʽֽⷽ.˳ΪʽB=B1>>B2,ֽ㷨Ϊ
Ti(B,dx,pams)=Ti(B1,dx,PAMS(B2))>>Ti(B2,dx,pams).
(3) ѡΪʽֽⷽ.ĶѡΪֽ,ΪѡΪ.ǰ,ѡΪʽΪB=a1;B1ۣa2;B2ۣ...ۣam;Bm,ֽתΪ
Ti(B,dx,pams):=(Ti-f(a1,dx)Ti-f(a2,dx)...Ti-f(am,dx))>>(
Ti-m(a1,dx);Ti-b(a1,dx!c1);Tsynci(tag(a1),dx!c1,PAMS(B1));Ti(B1,dx!c1,pams)
ۣTi-m(a2,dx);Ti-b(a2,dx!c2);Tsynci(tag(a2),dx!c2, PAMS(B2));Ti(B2,dx!c2,pams)
...ۣTi-m(am,dx);Ti-b(am,dx!cm);Tsynci(tag(am),dx!cm,PAMS(Bm));Ti(Bm,dx!cm,pams))
(4) Ϊʽֽⷽ.B=B1g1tag(g1),...,gntag(gn)ݣ B2,ֽ㷨Ϊ
Ti(B,dx,pams)=Ti(B1,dx!p1,pams)PJi(g1tag(g1),...,gntag(gn))ݣ Ti(B2,dx!p2,pams),
PJižģPiϵͶӰ.
3.3 ֽʵ
ԱATMıע淶,ֽĽ淶.Լ,ģͨЭͬͨšֲʵԭܹ淶.
Proc ATM In-card,In,Out,Display,Com (money-box:Money-type):noexit:=
hide sync12,sync123,sync23 in USER-PARTIn-card,In,Display( )sync12,sync123ݣ
(COMMUNICATORCom()sync23,sync123ݣ BOX Out(money-box))
where
Proc USER-PARTIn-card,In,Display():noexit:=
In-card?Account-no;sync12!Account-no;In!GET-PASSWORD?password;sync12!password;
(sync12!c1;
(In!GET-MONEY?m:Money;sync123!m;
(sync123!c1!c1;(Display!SUCCESSsync12!c1!c1!p2)>>USER-PARTIn-card,In,Display()
ۣsync12!c1!c2;Display!ERROR;USER-PARTIn-card,In,Display())
ۣsync12!c2;USER-PARTIn-card,In,Display())
)
endproc
Proc COMMUNICATORCom():noexit:=
sync12?Account-no;sync12?password;Com!Account-no!password;
 (Com!PASS-OK;sync12!c1;
(sync123?m;Com!GET-MONEY!m;
(Com!OK;sync23!c1!c1;sync123!c1!c1;(Com!SUCCESS;sync12!c1!c1!p2;)>>
COMMUNICATORCom()
ۣCom!NOT-ENOUGH;sync12!c1!c2;COMMUNICATORCom()))
ۣCom!PASS-INVALID;sync12!c2;COMMUNICATORCom()
)
endproc
Proc BOX Out(money-box:Money-type):noexit:=
((sync123?m;
(sync23!c1!c1;Out!m;sync123!c1!c1;BOXOut(new-money=Dec-Money(money-box,m))
ۣBOX Out(money-box)))
ۣBOX Out(money-box))
endproc
endproc
4 
˱ע淶ķԱ︴ӵϵͳֲ.ڴ˻,о˽ȫLOTOSԹ淶ʵֻķֲҪֽɶЭͬĹ淶ת.÷ܽһԭ淶ΪֽΪһڲЭͬΪ,ֽһƵ.,Իڽ̴ʽ֤:ͨڲͨЭͬ,ֽĽ淶ԭʼ淶ֹ۲ȼ,ɴ˱֤ϵͳƵȷ.
еĹ,ȫLOTOSԹ淶,оݷֲĳԼֲʵ.ķֱӴ໮ּ,ʹֹֽܷķʵ.ĹҪǣķֽо.о,һǻڴ淶,Ļģʽ;һģ淶вԭʼ淶в,оΪʽķֽת㷨.
*оõȻѧ͹863߿ƼĿ.
߼顡л,1970ʿ,ҪоΪֲʽϵͳ.
»,1936,,ʿʦ,йԺԺʿ,ҪоΪ Զ,ѧ. 
ɽ,1938,,ҪоΪѧ,.ͨѶϵ:л,100871,ѧѧ뼼ϵCASE
ߵλɳѧԺѧϵ ɳ 410073
ο
1ISO. LOTOS, a formal description technique based on the temporal ordering of observational behavior. ISO IS8807, 1988
2Bolognesi T, Brinksma E. Introduction to the ISO specification language LOTOS. Computer Network and ISDN Systems, 1987,14:2559
3Rom Langerak. Transformation and semantics for LOTOS Ph.D. Thesis. University of Twente, Netherlands, 1992
4Maria Hultstrom. Structural decomposition. Protocol Specification, Testing and Verification XV, 1995. 201216
1998-01-16յԭ,1998-07-08յ޸ĸ
