ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.2P.229-234



һಢʵʱϵͳԶ֤
Խ֣Dan Van Hung
ժҪһ㷺֤ʵʱϵͳķǸݱ֤ʵʱ,ʹʵ˫ģȼ۹ϵʹ޵״̬ռתΪ޵״̬ȼռ.㷨ֻҪ޵ĵȼռͿԵõȷ.,ȼռĹģһϵͳģըԵ,ںܶ,ռǲʵ.һȼ۹ϵ֤һɶʵʱԶͨɵĲϵͳǷһʱ.ͬʱ˸֮ļݹϵ״̬ȼռ.ϵ,һ㷨֤ǷһʵʱԶһʱ.ʵоʾ,㷨ĳЩ±һЩиõʱͿռЧ.
ؼʣģ֤,ʵʱϵͳ.
ţTP311
Automatic Verification of a Class of Concurrent Real-Time Systems
ZHAO Jian-huaZHENG Guo-liang
(Department of Computer Science and Technology Nanjing University,Nanjing,210093)
Dan Van Hung
(International Institute for Software Technology The United Nations University,Macau)
AbstractA widely used method for checking real-time systems is,according to the real-time property to be checked,to use a proper bi-simulation equivalence relation to convert the infinite-timed state space to a finite equivalence class space.The algorithm needs only to explore the finite space to get a correct answer.In most cases,exhaustive exploration is very difficult because the equivalence class space increases explosively when the scale of the system increases.In this paper,an equivalence relation is introduced to check whether a concurrent system,which is composed of a finite set of real-time automata,satisfies a linear duration property.To avoid exhaustive exploration,this paper also introduces a compatibility relation between timed states (configurations).Based on these two relations,an algorithm is proposed to check whether a real-time automaton network satisfies a linear duration property.The cases study shows that under some conditions this algorithm has better efficiency than the tools in the literature.
Key wordsModel-checking,real-time system.
ڹȥļ,оһЩʵʱϵͳԶ֤ߣ13.Щʹõĺ㷨AlurDill4ǵĿԹʱԶĿɴԷ㷨.ǻһϵеķͼ״̬ռ䱬ը,ҪȼռĸЧݽṹ5ݺͱ״̬ռ㷨.
ڱ,ʹʱ(һֵ͵ʱ(duration calculus)ʽ)Ϊϵͳ淶ʹʵʱԶΪϵͳģ.Ϊʱͨϵͳڸ״̬ϵʱ,ڿɴԷ˵,ʱԸ֤,ڽпɴԷʱʹõĵ˼۹ϵֱ֤ʱ.ܳʹԹ滮ķ֤ǷΪһʵʱԶһʱԵ6.ļչ֤ʱԶһӼ7.
Ľ֤һʵʱԶͨɵĲϵͳ(ʵʱԶ)һʱԵȷ.ָ,һʵʱԶһʱԵҽΪ.ǶʵʱԶĸּϵĵȼ۹ϵͼݹϵ,ϵһ֤㷨.FischerЭʵо,һЩ¿Ժ̶ܴȵؼͿռʱϵĿ.
ĵ1ʽ˴ʵʱԶ.2ڱʱԺʵʱԶ.3ڸǵĻ˼㷨.4ʹǵ㷨FischerЭ֤ʱõһЩͳƽԼߵıȽ.һǶԱĵܽ.
1 ʵʱԶ
һ,ǽʵʱԶʽ.ڱ,ʹNatʾǸ,IntvʾNatϵļ.ȣʵʱԶ6ݵĶ.
1.һʵʱԶһԪ顴A,,:(1) A=S,s0,EһԶ;S״̬,s0ǳʼ״̬,Eתļ.(2) ǴEIntvһӳ;Eеÿתeһae,beݻae,),,ae,be,0aebe.aeʾeСʱ,beޱʾeʱ.
һs1s2תe,ñʾԴ״̬s1,ñʾĿ״̬s2.һSе״̬s,ʹUsʾmaxbes.ãae,be(be=ʱ,ʹãae,))ʾ䦣e.
 2.һʵʱԶN(дΪʵʱԶ)һԪ顴P,V,G,R,:(1) P=A1,A2,,AnһʵʱԶ޼;еi,Ai=Ai,iAiSi,qi0,Ei.(2) V=v1,v2,...,vmһļ.(3) Gһ(E1E2...EnVarguard(ʽ)һӳ.(4) Rһ(E1E2...En(VNat)һӳ.ÿһתe,R(e)һӹVNatĲӳ.eʱ,ÿһR(e)еĹvֵΪR(e)(v),Ĺֲֵ.
VarguardеĹʽǹڹĲʽ,﷨£գTruevc|1Ħ2,vһ,cһ.VarguardеĹʽVһȡֵϵֵΪ汻().ڱĵಿ,һ,xiʾĵiԪ,ãxiiʾͨеiԪ滻xiõ.
3.N=P,V,G,RһʵʱԶ.Nһʱ״̬һnά,siǵiʵʱԶAiһ״̬.NһһԪ顴,,,Nһʱ״̬;һnάǸʵ,tiʾʵʱԶAiһתʱ̵ǰʱ;ǹһȡֵ.
4.N=P,V,G,RһʵʱԶ.,,͡,,䡵N.ǶNתϵͳ:
(1)(eAiһת)ҽ(a)(si=)ģ=/i,tiʣae,beݡġ䣽0i,(b) G(e)(),ҡǽR(e)ĶеÿֵΪR(e)(v)õĹȡֵ.
(2)(d0)ҽ==䲢Ҷеj,(1jn),(tjtjd)ģtjUsj).
C1C2,һתe,һʵd,ҽһCʹòҳ,Ǽ.תϵͳĻ,ǿԶʵʱԶִ.ʵʱԶNһִбʾ˸ӳʼֿʼݻ.һִЦԱʾ,C0Nĳʼ.ǰѴʱ䳤ȵת(ei,di)(ei+1,di+1)...(ej,dj)(1ijm),ΪCi-1ʼһNΪ.һ֡,,ΪֵҽԪض.Ϊִеҽеdi,1im1,ʱ,еCi.
2 ʱ
ڿʼ,ʹNʾ涨2жʵʱԶ.ʱʾʵʱϵͳʵʱ㹫ʽ.һʱ禷MĹ״̬ʱλֵԲʽ,Ц,ÿi(1ik),SiһNʱ״̬ϵν,ciMʵ(ciΪӦSiϵ).Nһִ,Siڦϵʱλ֡SiɡSi,Цiu0um(uSi,uCuʱ״̬.,ʱԦM,ڦϵֵԼ,

jCjʱ״̬,.
5.һʵʱԶN㦷MҽNִЦ㦷M.
,ͼ1ʾʵʱԶ;:1Զ״̬AϵʱǱ״̬Bϵʱ䳤.ʿʱԱʾɡatB-atA0,atAatBνʣ㡴A,CatA,A,DatA,B,CatB,B,DatB.

Fig.1A real-time network with shared variables
(v is a shard variable)
ͼ1һʵʱԶ磨vһ
3 㡡
3.1ʵʱԶԼʱԵһЩ
ڱ,覷Mһʱ.ʹܹڿ,Ӷ.
1.NκִЦ,ȻһNִЦ䣬ʹæܦ䣩.
֪,ʵʱԶN㦷M,ȻһNִЦ㦷M.,֤NǷ㦷M,ֻҪ֤ǷNִж㦷M.µּļݹϵ͵ȼ۹ϵֳֻ޶ȼԼԵȼռ.
6.C1=,,C2=,,N.C1C2,C1C2,ҽеi,1in,Ĺʽ.
(tit'i)(ti>RgBndsit'i>RgBndsi)(LowBndsi<ti<t'i)(ti>t'ie.(=sibe=)),
RgBndsimax({ae|=si}{be1(=s)}(be<)}),LowBndsi=max({ae=si}).
ݹϵԷԺʹ.
2.C1,C2N,C1C2.ô,κתe(Ǧ),κd,һC2 ʹó,ôȻһC1ʹòC1C2.
7. C1C2ȼ,C1C2,ҽ(C1C2)(C2C1).
ӡԺ͵ĶԿ,һȼ۹ϵ,ҽNֿռ仮Ϊ޶ȼ.
3.RN={[C](CNһɴ)}һ޼,УCݱʾCġԵĵȼ.
3.2Ȩͼ
һʵʱԶNĶӦʱԦMļȨͼ:ͼĽڵ㼯RN.һڵnһڵnһȨΪDaıaҽһתeCn,Cn,ʹöĳd,aȨDa,Cʱ״̬.Կ,Da,Ȼһdʹò.ȨͼĳʼڵǰԶĳʼֵĽڵ.ͼ2ʾͼ1еʵʱԶӦʱԡatB-atA0ļȨͼ.һC=,,,LCʾminUsi-ti1in.ֵʾNڵǰʱ״̬ܵȴʱ.,(p)ʾpĳ,.ӼȨͼĶԵó.
