о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 8 Vol.36 No.8 1999



ϵͳ̬Ϊģͼʽ
Ǯ
ժҪ̻ϵͳ̬Ϊļģͺʽ㷨ģ͡߼ģͣڽ̴ģͺͷI/OԶPetriActorģͣԵشӱϷͱȽϵͳ̬Ϊص.л˻绷µķֲϵͳһЩҪͷֲ.һȫµĽǶȥЩҪġΪģͺͷԷֲϵͳĶ̬ΪصԷͱȽϣΪϵͳؽֲϵͳļģͺ۴һ.
ؼʡ̬Ϊģͣʽֲ
ͼšTP311TP311.1TP311.5
SEMANTIC MODELS AND FORMAL DESCRIPTIONS OF SYSTEM DYNAMIC BEHAVIORS
QIAN Jun and FENG Yu-Lin
(Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100080)
(Object Technology Center, Institute of Software, Chinese Academy of Sciences, Beijing 100080)
AbstractFor the description of dynamic behaviors of software systems, some important existing models are analyzed and compared, including algorithm models, logic models, models, and formal calculi based on process algebra, I/O automata, Petri nets, and actor models. In addition, some crucial properties of object interactive systems such as interaction, concurrency, and distribution are also discussed. As part of a larger project which focuses on the direction of component software theory and design methodology, this work will help to clear the concept, consolidate the understanding, and lay down a deep foundation for the research on model and semantics of distributed object computation and the specification and verification of an object system.
Key wordsdynamic behavior, semantic model, formal description, interaction, concurrency, distribution
1
ϵͳĶ̬Ϊϵͳľ.ϵͳĹҪɷΪ׶Σ㷨ɼϵͳʵֺͽʽϵͳʵ.
ŷǳḻں.ҪŪʲôǼ㣬ͱ¼㹻ʶ⣺
(1) ѧģͣ
(2) ʽ
(3) ɼԣ
(4) 㸴ԣ
ԣɼԺͼ㸴Եо۽ڶԼģ͵ѡȡͶԼʽ֮.˵ǶԹ̵һָ߶ȳ.ȥǶ㷨Ϊ̵ĳǶԸϵͳΪ̵ĳ.Сһָһϵͳ䶼ɳΪ㣬.㷨ɼԳΪ뵽ĺӳ䣬һյļ.ϵͳļ㣬ϵͳⲿĽ(interaction)ϵͳڲЭͬɣһŵġġͬʱֿǷֲļ.Turing㷨ģ͵Ĵʽ㷨ɼϵͳĴ.Turingһһ״̬תƹ̣óѧʾ߾ͬı.ϵͳ(Ϊʽϵͳ)ļģ޶ۣ÷оڼѧ۵ǰؿ.֮԰Ѽϵͳļ㷽ΪٴӴм򲢷תƣڴӷռ򿪷żת.
ķչǼӲٶԽԽ졢ɱԽԽ͡ԽԽСķչȴպ෴.ĹģԽԽʱԽԽάͲԵķԽԽ.ҪԱϵͳγɵȫһɿԱ֤ĲԺάǲҲвͨģΪԲܴϱ֤Զ.ϸؽֻķƺʵֵвϸʽܱ֤õһɿġȷϵͳ.ȻҲ֪ܴһʵġ걸ʽϵͳ.
ʵϣϵͳ˾綯̬Ϊ֮⣬͡ɽṹȾ̬ϵͳࡢ̳СװԵ.ϵͳľ̬ȫϵͳĶ̬֮⣬оĲʱͷм̳쳣1.йⷽоȻҲҪ۵ص.ǰصڼ㷽棬̻ϵͳĶ̬Ϊ֮.
оϵͳ̬Ϊģͺͷв.У߼ʽҪһ/֧ʱ߼2ݡģ̬3ݡֲʱ߼TLA4Լ߼5ݵȵ.ǿϵͳԼʣϵͳİȫԡԡƽԼԵ.߼ʽϵͳϣԽϵͳ.ڿ̻ϵͳΪϵģͺͷҪΪ(interleaving)ģͺ沢ģ.InterleavingģͰϵͳĲԽΪĳֳϵķȷԣǿϵͳԭ.沢ģǿϵͳڲͳһʱӣ¼֮䲻ϵ.Interleavingһ̶ϼϵͳĲ˲ģϵͳĲΪķܶ࣬Ϊ͵CCSCSPACPȻڽ̴ģͺͷ68ݣԼI/OԶBchiԶԶģͣ910.߼ڽ̴ģͺʽܹ̻ΪϸµϵͳΪϵ.CCSCSPкܺõĴʣǲп̻ϵͳΪģͣнʽϵͳ.⣬CCSûģϵ̻̼ĵȼ۹ϵʵϱ֤ϵͳ淶ʵֵһ.I/OԶһּ򵥶ķֲʽϵͳļģͣصֶͣǿֲϵͳ¼ϵͳ()ʱϵͳɽⲿ붯.ϵͳΪ沢ģPetriPomest¼ṹȣ1113.УPetriŹ㷺ӦãԽʾϵͳಢԣȱֻģͶû.ActorģרΪĲԶƵģֲ֧첽ͨźͼڲ״̬Ķģͣ14.Ļ˻ڶĽģ.ͷֲ绷·ֲϵͳҪ.ΪĵܽᣬԷֲϵͳҪԼֲͬļģͺͷۺԵķͱȽ.
2߼ģͺͷ
߼ĽǶȳоϵͳΪϵͳԼЭԼ.ͳ㷨ɼϵͳķԣԿһ뵽ĺӳ.Hoare߼DijkstraǰνۣͿͨģǰνʶЧ壬̻㷨ɼϵͳĶ̬ΪԼ.Hoare߼ǰν۶һ߼.
Lamport70ĩѲͷӦ(reactive)ϵͳʷΪ࣬ȫԺͻ.ʽؽȫǡϵͳ¼ԶᷢǡϵͳԤΪվᷢ.ϵͳֹܲϵͳٿ뵽ӳ䣬Hoare߼ǰν۲зǺϵͳĶ̬Ϊ.ʱ߼һ߼䣬˱ʾʱģ̬ӣԷͷӦϵͳԼʣ

УGFֱΪalwaysӺeventually.
ԴPnuli70ĩʹʱ߼ϵͳʽõ˺ܿ췢չ.Ƚϵ͵Kozenģ̬3ݣClarke˵CTL2ݣFisherLadnerĶ̬߼15ݣChandyMisraUnity߼16ԼMannaPnuliĲ뷴Ӧ߼17; LamportTLA(temporal logic of actions)4ݺEhrichķֲʱ߼.Уģ̬ʱ߼Ļˡ⶯(act)͡ڶ(act)ģ̬ӣԼݹС󲻶㣬ΪһϸϵͳΪԼṩ.
ʱ߼ǻΪ.νΪָϵͳ״̬һУΪټ(trace).пܵټϵͳ.һΪ¾״̬ĹϵһԭӲ.ϴ淶18ݣԼϵͳľ̬ṹΪ͵EhrichĶ淶.ǲʱ߼ϴ淶ķһ̻װԵĶ1921.źǣڷ֧ʱ߼Ͻɿ걸ʽϵͳһ޵.ֱ1995꣬WalukiewiezŸһĹϵͳ22.һԷ֧ʱ߼һģ̬걸ʽϵͳ񲻵ö֪.
3ڽ̴ģͺͷ
CCSCSPǽ̴ĴͨźͲϵͳ.ǾԽΪ㵥λ̵ĻԭԶ.νԭԣָٷ֣Ҷִ˲ʱ.ϵͳУ̼佻˫(handshake)ɣһͬͨŷʽ.ͬʱCCSCSPǼģ.ȻCCSCSP֮Ҳвͬ.CCSͬ(synchronization tree)ʾ̣Ϊ״̬תͼCSPʧܼ(failure set)ʾ.CCSУʹò(ģ)ͽ(ĵȼ)CSPУʹָ(ʧ)ͽ(ĵȼ).
3.1CSPʧܼ
CSPУеĻ̵ܹĳЩִ.ڽִе׼κοܵĶܾʱͷ(deadlock).ˣһ̵ʷ(Ϊ)Ҫôһټ(trace)Ҫôټһ.
AʾϣءAΪټʾΪִֹеĶ.XAΪһܾʾ̿˵Ķ.(,X)һʧܶԣʧܶԵļϳΪʧܼ.CSPĽ̾ʧܼʾ.ˣCSPУȫпܵ޾۲õ.̳Ϊʧܵȼ(failure equivalent)ҽӵͬʧܼ.CSPḺ̌£

FʾһCSP.
3.2CCS״̬תͼ
LΪһֵļϣΪLĹּϣ.Ϊڲ(ⲿɹ۲Ķ).Ϊ㣺.VΪ()ϣCCSḺ̌ʽ£

CCSУ̱Ϊ״̬תƣԶбʵĲͬ.һԶȻҲһ״̬תͼǰ̻ܵ.ԶܵɣCCSȴ㣬a.(b+c)a.b+a.cͬһ.ҲΪʲôCCS̿ԶһԵ.
һCCS̶ӦһŴжǵ״̬תͼ״̬ɽδִеĶ.ͬ״̬תͼܱʾͬһ.CCSý̼Ļģϵ(bisimulation relation)̵̻ĵȼ.ǳƽgh֮ڻģϵRΪgRh,(g,h)R.
(1) (s,t)Rgбsas䣬hһڱtat䣬(s,t)R
(2) (s,t)Rhбtat䣬gһڱsas䣬(s,t)R.
s,st,tֱΪgͽh״̬.
3.3ģ
CCSCSPȽ̴ϵͳInterleavingģʵ÷ȷԴϵͳĲ.ܹһǱֶԭԣһ̶϶м򻯣ΪϵͳõĴ.CCSÿ̻ȷԵѡӡ+ڲʾ̵ĸӡ|̼ͬͨţǰ׺ӡ.ѡӡ+ڲӵĶAӣAȣӣ͹һн̶Ĵϵͳ(ֵϵͳ).
̴ϵͳInterleavingģȱǺܶಢڲ̵߳Ĳִ.ʣȷԲܴ沢.
3.4ͬͨż첽ͨ
׼CCSCSPͬͨŵķʽ̼ĽϢķͷڽܷܹϢ״̬£ܷϢϢһ͵õȴ.ڽ˫ͨŵʱ̣ⲿĽ룬CCSӡ\̻.
ǣ绷µķֲϵͳͨȡ첽ͨŵķʽнϢķͷʱϢܷͬ.ͬʱͷڷϢִĶ.CCSĻϽһĸĽ(﷨ϣ)Եõ첽ͨŵϵͳ2325.⣬ϢĽܷʽֿɷΪͬԼϢܷʽͬԼϢܷʽ.
4Զģ
ԶоϵͳĶ̬ΪҲһֳķ.I/OԶ(input-output automaton)еһ.صҪУ
(1) ֶ
I/OԶһǶ(action signature)ԪSig(A)=(in, out, int),in,out,intֱ3ཻĶϣin붯,outintڲ.ext=inoutΪⲿϣlocal=outintΪϵͳ(Զ)ֲƵĶϣAct=inoutintΪжļ.
(2) Զʱ̶ܽⲿ붯
붯ԣӳ˷ֲϵͳ¼.һI/OԶΪһԪA=(Q,Q0,S,T,P)У

Aʣ붯ain״̬qQqQʹ(q,a,q)T.
(3) ԶԸ(composition)
ϷǿԶI/OԶϵͳ̬Ϊ¼Ҫ
۲ I/OԶCCSһInterleavingģԭ.ڷCCSģʱﲻظ.
۷ֲ I/OԶֶͣҪӳϵͳڲɿƶϵͳɿƵⲿ붯.Զʱ̶ܽⲿ붯ӳ˷ֲϵͳ¼.I/OԶһصʺֲʽϵͳĶ̬Ϊ.
5Petri
һЩۼȸģָϵͳCCSCSP.Petriֻģͣû.Petriһ沢ģͣ䲻ִУCCSƯϵͳԿ̻Ĳ粢ìܼӴȵ.
PetriҪأ¼.ÿһʱӦ¼ɷȻԭ仯һЩӳΪһЩִӲΪǣһЩ¼Է.
Petriõתƹϵͳһ״̬һ״̬Ǩ.һ¼֮ûϵԲ.Petriϵͳвһͳһʱӣ۵ı.
ҪPetri֣C/EϵͳP/Tϵͳ.C/Eϵͳ/¼ϵͳļƣõѡĸ(case)ͨҶÿ¼ڸ֣ʹܹ֮ڴ״̬µ.P/Tϵͳλ/ǨϵͳļƣC/EϵͳȣP/Tϵͳ磺
(1) һλпж룬һαǨʹػ
(2) ͬһǨԷ
(3) ͬһǨԡҲضط
(4) ͬһṹԼȳìֲֳ.
ƪǲPetriĶϸ.ֻPetriϵͳĶ̬ΪһЩͱȽ.
۲ Petriһ沢ģͣĲ.ԷֲϵͳнĶ󣬿ɿǲPetri.
۽ Petriֻģͣû.ΪPetriĴʣPomsetPetri26.ܵ˵Petri֤ϵͳļԽΪ.ǿ԰Petri˼Ӧõ̻ϵͳĽ֮.
6Actorģ
ǽҪһҪģ.ActorģͷΪרΪ󲢷COOPƵһģͣǿҵ.
ActorģУ㵥λΪactor,һ԰(self-contained)ġĶactor3
(1) create𴴽µactor,ɺṩĶ̬ԴĴչ㣻
(2) send toactorϢ.ÿactorһϢкһ̶mailַڴactorʱȷ
(3) becomeΪ滻ΪactorһʷصΪ(״̬).


ͼ1Actorģ
ActorģҪص㣺
ģͣ ̻ϵͳһactorڼдµactor.
۽ ÿactorһϢbufferactor֮첽ͨŷʽ.
۲ ActorĶԭ.ϵͳĲģinterleavingģ.
״̬ ActorУ״̬ıΪ滻becomeɵ.ע⣬״̬һµĶ״̬actorΪĸı䣬ִһϢתΪִϢϵһϢ.
 actorģͣԼϵĴ27ݣactorĲиϡڲactorؼ.
7󽻻ģ͵
Ŷķչͳ죬˾½Ƴһ׼ͲƷCORBA/DSOM/OPENDOCCOM/OLE/ActiveX,Java/JavaBeansȣǸı˴ͳϵͳĹ̽ṹٲ̿ʹϵͳһЩԤƵĻ¶ģ龭װɣõĿɻԡάԺԴĿɸԣ2930.绷µķֲϵͳĿǰΪҪһֽʽϵͳ.صҪУ(1) (interactive)
(2) (concurrent)
(3) ֲ(distributed)
(4) (active objects)
(5) ƶ(mobile objects)
(6) ڲ״̬
(7) (Ӵ)
(8) һЩǺȫ(security)ʵʱʵ.
УͷֲǶ󽻻ϵͳάҪ3132.


ͼ2󽻻ϵͳάģ
ϵͳıϵͳΪӵҪԴɽ.벻ɿƵⲿĽΪϵͳųƵǿŵļϵͳǸϵͳ.ֲµĶϵͳͨϢݵ첽ͨʽ.첽ʽʹϢͷϢܷͬڷϢִ.ϢĽֿܷɰͬԼϢܷʽڽյϢִУͬԼϢܷʽϢ.ͬԼҪ״̬.
Ĺ.ĺڲһ.ͬʱܶڶڲж߳ͬʱ.ˣΪʹϵͳԤڵ񣬾ͱԲȡ.
ֲָϵͳӶϿλĲ֮ͬ.ֲʹöͨž첽ӳٵ.
󽻻ģ޶ۣ󽻻ϵͳҲдо.еһЩHonda,Tokoro˽첽ͨŻϵĶ2324ݣNierstrasz˶ԿϵͳĸԵо33ݣEhrich÷ֲʱ߼Զϵͳڽй淶ȵ.ԷֲϵͳĶ̬Ϊģͺʽϵͳоһ.
8ۺϷȽ
ڣԶ󽻻ϵͳĶ̬Ϊϸ۵ģͺʽýۺϱȽ.
󽻻ϵͳĶ̬

ֲƶڲ״̬Լ
ͬͨ첽ͨ沢
㷨ģ͡
߼ģ͡ϴ淶
̴䡡߽ס
I/OԶ
Petri
Actorģ͡

Ҫģ 
ͼ3ϵͳ̬ΪһЩҪģ͵һۺϷ
ǿԿ㷨ģǲⲿļģ.
9ܡ
㷨ģ͡߼ģ͡CCSI/OԶPetriActorģͣ𲽷ͱȽϵͳ̬Ϊص.ֲϵͳǲͬ㷨ɼϵͳĸϵͳҪҵһȫļģͺʽ̻ϵͳǲܵ.ڱ֤ʽϵͳɿԵͬʱǷſ걸ԵҪƵǰ£Ѱʵļģͺʽ淶֤ǵϵͳʧΪһֺò.
ĿõȻѧصĿ(Ŀ69833030).
߼飺ǮУ196610ʿооΪֲ㡢ʽ.գУ19427оԱʿʦоΪ̡ʽֲ.
ߵλǮաйѧԺоѧоʵҡ100080йѧԺоġ100080)
ο
1Matsuoka S, Yonezawa A. Analysis of inheritance anomaly in object-oriented concurrent programming language. In: Agha G, Wegner P, Yonezawa A eds. Research Directions in Concurrent Object-Oriented Programming. Cambridge, MA: MIT Press, 1993
2Emerson E A. Temporal and modal logic. In: Leeuwen J V ed. Handbook of Theoretical Computer Science, Vol2. North-Holland: Elsevier Science Publisher, 1990
3Kozen D. Results on the propositional mu-calculus. Theoretical Computer Science, 1985, 27(3): 333354
4Lamport L. The temporal logic of actions. ACM Transactions on Programming Languages and Systems, 1994, 16(3): 872923
5Girard J Y. Linear logic. Theoretical Computer Science, 1987,50(1): 1102
6Milner R. Concurrency and Communication. London: Prentice-Hall, 1989
7Hoare C A R. Communicating Sequential Processes. New Jersey: Prentice-Hall, 1985
8Bergstra J A, Klop J W. Algebra of communicating processes with abstraction. Theoretical Computer Science, 1985, 37(1): 77121
9Lynch N A, Tuttle M R. Hierarchical correctness proofs for distributed algorithms. Laboratory for Computer Science, Massachusetts Institute of Technology, Techical Report: MIT/LCS/TR-387, 1987
10Thomas W. Automata on infinite objects. In: Leeuwen J V ed. Handbook of Theoretical Computer Science, Vol 1. North-Holland: Elsevier Science Publisher, 1990
11Reisig W. Petri Nets: An Introduction, EATCS Monographs on Theoretical Computer Science, Vol 4. New York: Springer-Verlag, 1985
12Pratt V R. Modeling concurrency with partial orders. Int J Parallel Program, 1986, 15(1): 3371
13Winskel G. An introduction to event structures. In: LNCS 354. New York: Springer-Verlag, 1989. 364397
14Agha G. Concurrent object-oriented programming. CACM, 1990, 33(9)
15Kozen D, Tiuryn J. Logics of programs. In: Leeuwen J V ed. Handbook of Theoretical Computer Science, Vol 2. North-Holland: Elsevier Science Publisher, 1990
16Chandy K M, Misra I. Parallel Program Design. Reading, MA: Addison-Wesley, 1988
17Manna Z, Pnuli A. The Temporal Logic of Reactive and Concurrent Systems (Specification). New York: Springer-Verlag, 1992
18Ehrig H. Fundamentals of Algebraic Specification. Berlin: Springer-Verlag, 1985
19ΣǮ߱. Trace.ѧ 1999, ¼
(Huang Tao, Qian Jun, Ni Bin. Trace calculus. Journal of Software (in Chinese), 1999, to appear)
20ΣǮܻ.(). ѧ 1999, ¼
(Huang Tao, Qian Jun, Zhou Huan. Object calculus . Journal of Software (in Chinese), 1999, to appear)
21ΣǮ.(). ѧ 1999, ¼
(Huang Tao, Qian Jun, Wang Xu. Object calculus . Journal of Software (in Chinese), 1999, to appear)
22Walukiewicz. A complete deductive system for the u-calculus. BRICS, Rs-95-6, 1995
23Honda K, Tokoro M. An object calculus for asynchronous communication. In: Proceedings of ECOOP91, LNCS 512. New York: Springer-Verlag, 1991. 133147
24Satoh M Tokoro. Time and asynchrony in interactions among distributed real-time objects. In: LNCS 952. New York: Springer-Verlag, 1995
25Amadio R M, Castellani H, Sangiorgi D. On Bisimimulations for the asynchronous -calculus. In: Proc of CONCUR96, LNCS 1119. New York: Springer-Verlag, New York: Springer-Verlag, 1996. 147162
26Wimmel H, Priese L. Algebraic characterization of net pomset semantics. In: Proceedings of CONCUR'97, LNCS 1243. New York: Springer-Verlag, 1997. 406420
27Talcott C L. Composable semantic models for actor theories. In: LNCS 1281 New York: Springer-Verlag 1997. 321364
28գΣ߱.. : ѧ磬1998
(Feng Yulin, Huang Tao, Ni Bin. An Introduction to Object Technology (in Chinese). Beijing: Science Press, 1998)
29Meyer B. Ojbect-Oriented Software Construction. New Jersey: Prentice-Hall, 1997
30Guerraoui R et al. Directions in object-oriented programming. ACM Computing Survey, 1996, 28(4): 691700
31Nicol J R et al. Object-orientation in heterogeneous distributed computing systems. Computer, IEEE, 1993, 5767
32Wegner P. Why interaction is more powerful than algorithms. CACM, 1997, 40(5)
33Wegner P. Interactive foundations of computing. Brown Univ, Tech Report: 1997
34Nierstrasz. Requirements for a composition language. In: LNCS 924, New York: Springer-Verlag, 1995. 147161
յڣ1998-09-14
ĸڣ1998-12-10
