о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999Vol.36No.7P.842-847



һֻ״̬Ǩͼģ
Ρ˳
ժҪڼϵͳѡ͡ĽҪ.ʹģģͺͶнģͿɶԼϵͳܽз.ǹʹģģ͵ķýϸ.нģҪϵͳ϶ļ򻯺ͼ.ģ͵Ĳ㣬лͼۺԶһµĻ״̬Ǩͼļϵͳģͣһ״̬ǨͼģʵʱϵͳӦʱ㷨.֤ʱ临Է㷨ȷЧ.
ؼʣۣ״̬Ǩͼģͣ㷨
ţTP302
AN PERFORMANCE EVALUATION MODEL BASED ON
FINITE STATE TRANSITION GRAPH
LIU Xiao-Dong
Department of Computer Science and Engineering, Harbin Institute of Technology, Harbin 150001
LI Lian-Zhi
Department of Computer Science and Engineering, Harbin Institute of Technology, Harbin 150001
GUO Fu-Shun
Department of Computer Science and Engineering, Harbin Institute of Technology, Harbin 150001
AbstractPerformance evaluation is important in selection, improvement, and design of computer systems. Simulation and queue model can be used to analyze the performance of computer systems. It is expensive to create and use simulation model. Queue model needs more hypothesis and simplification. Aiming at the shortcomings of the two models, a finite state transition graph (FSTG) model based on chart and automaton theory is presented to analyze performance of computer systems in this paper. An algorithm based on FSTG for solving the response time of real-time systems is also presented. By proving and complexity analysis, the algorithm is correct and effective.
Key wordsperformance evaluation state transition graph model algorithm
1
۾Ҫָһϵͳһϵͳָ1.ڼϵͳѡ͡ĽоҪ.һ˵ȶҪ۵ļϵͳһʵģͣȻģ͵ָ꣬Աϵͳ.
һֳõģǶģͣ2.ŶۺΪۻ.ϵͳĸֲԱҪĸҵ˿͡˿͡ŶӵȴԱΪĳַ.ģһҪϵͳ϶ѧ裨衰˿͡г޵ģϸ̶ȽϲӶӰ˽.⣬ڲкͷֲʽȴ͸ϵͳģ׼ȷȫϵͳΪ.
Թϵͳģģͣʹ֮ģʵϵͳʵϵͳͬķʽУͨģͽвӶƶϳϵͳ.ģģͨһ൱ĳʵֵģɱͷǽϸߵ.
ģ͵Ĳ㣬һµļϵͳģ͡״̬Ǩͼģ. ͼۺԶΪۻܹϵͳĸֹ켣¼ڼϵͳĸ״̬Լ״̬ĸı䣬Ըݻͼ۵ʽ㷨׼ȷؼָ.ȶԸģͼϷ﷨嶨壬ָʱܲ״̬ըⲢȼ۵.һڸģ͵㷨ʵʱϵͳӦʱ.
2ģͶ
1. һһ2ԪP=(V, E).VǷǿ״̬.EVϵĶԪǨƹϵ.PӦһͼVе״̬ӦŽ㣬v,wV(v,w)Eͼдvwһ.PΪ״̬Ǩͼ.
2. q1, q2,,qnPеһ״̬Уi1(qi,qi+1)TƸΪһ·.
3. һʱ״̬Ǩͼһ8ԪG=(N,ninit,X,,C,T,A,I).У
(1) N㼯ϣ
(2) ninitǳʼ㣻
(3) XʱӼϣ
(4) ¼.ӡʦһ¼ʾ̵
(5) C={y|yxr,xrԭӹʽrR,xX}
(6) TǨƻ.TNC2XN
(7) AN2T.һӦпܵĻϣ
(8) INCÿһϵʱ.
IΪÿһnNһʱƣ֮Ϊ.ֻеǰʱI(n)ʱϵͳĿƲͣڸý㣬xrԭӹʽĲ.һǨtr=(n1,c,e,Y,n2)TǰĽn1ʱcôϵͳܹǨ.ΪǨƷĽϵͳ¼eYеʱֵΪ0Ƶһn2.
4. G1,G2,,Gnn̵ʱ״̬Ǩͼ.Gi=(Ni,ninit,Xi,i,Ci,Ti,Ai,Ii). n̹ɵĲϵͳʱ״̬ǨͼΪG=G1G2Gn=(N,ninit,X,,C,T,A,I).У


ڶǰȸһЩ.һǨtr=(n1,c,e,Y,n2)source(tr)Դn1target(tr)Ŀn2, cond(tr)cevent(tr)¼eԼreset(tr)ʱӼY.v,v1,ʱֵ.
5. һʱ״̬ǨͼG=(N,ninit,X,,C,T,A,I)һΪһִУԣ
(1) n0=ninit,v0(x)=0(xX)t0=0
(2) (vi+r)I(ni)i00r(ti+1-ti)
(3) ÿһi1TдŴni-1niǨtriʹ
(vi-1+ti-ti-1)Cond(tri)

(4) titi+1i0.
6. һִУӦΪǣ(event(tr1)t1),(event(tr2)t2),(event(tr3)t3),.
3״̬ը
̵ܵʱ״̬Ǩͼģͳߴ粢Ǻܴ󣬵ɶ̹ɵĲϵͳʱ״̬Ǩͼģ͵ĳߴ罫Ѹ.磬nm״̬Ľ̹ɵĲϵͳʱ״̬Ǩͼģͣ״̬пܸߴmn.ϵͳ״̬ռߴָ֮Ϊ״̬ը.ʵʱϵͳбΪأΪʵʱϵͳƵʱֵ״̬ռ.Ϊ˱ȼ۵⣬Ӷʹ״̬Ǩͼģ͵ϷΪ.
7. һʷָǰΪֹϵͳѾִйģǨƣʱ̣Ե.
һʱ״̬ǨͼGexecs(G)Ϊִеļϣsteps(G)Ϊִвļ.. ʽأǸ¶.
8. ֪һʱ״̬ǨͼG=(N,ninit,X,,C,T,A,I).Ӧʷ״̬ǨͼΪH=(S,S0,L,TR)У

һʷh=<(tr0,t0),(tr1,t1),(tr2,t2),(trk,tk)>.untimed(h)=<tr0,tr1,tr2,trk>.״̬s=(n,h)untimed(s)=<n,untimed(h)>.ʽضʷȼ۹ϵ.
9. һԪϵhSS(s1,s2)ʦhuntimed(s1)=untimed(s2).ƦhΪʷȼ۹ϵ.
10. H=(S,S0,L,TR),H=(S,S0L,TR)f:HHһӳ.ԣ
(1) (n,h)S,f(n,h)=(n,untimed(h))
(2) (ninit,<(tr0,0)>)S0f(ninit,<(tr0,0)>)=(ninit,<tr0>);
(3) (tr,t)L,f(tr,t)=tr;
(4) (s1,(tr,t),s2)TR,f(s1,(tr,t),s2)=(untimed(s1),tr,untimed(s2)),fʷȼӳ.
֤f۵ӳ.ʷȼ۵״̬Ǩͼ״̬Ѵ٣״̬ռ仹Ǻܴпܰ״̬.ΪˣҪһ.
11. ָӵǰ״̬ҪִеǨ.
12. ֪H=(S,S0,L,TR)һԪϵfSS(s1,s2)ʦfУ
(1) (s1,tr,s1)TRʱôs2ʹ(s2,tr,s2)TR(s1,s2)ʦf
(2) (s2,tr,s2)TRʱôs1ʹ(s1,tr,s1)TR(s1,s2)ʦfƶԪϵfΪȼ۹ϵ.
Կǽһȼڵ㽫ȼ۹ϵ״̬ϲһ״̬Դﵽ״̬ռĿ.ʽأ¶.
13. H=(S,S0,L,TR)ʷȼ״̬ǨͼF=(Sf,S0f,Lf,TRf)һ״̬Ǩͼһӳg:HF.ԣ
(1) sS,g(s)=equiv(s)Sf.equiv(s)ʾsĽȼࣻ
(2) sS0,g(s)=equiv(s)S0f
(3) trL,g(tr)=trLf
(4) (s1,tr,s2)TR,g(s1,tr,s2)=(g(s1),tr,g(s2))TRfgΪȼӳ.
֤g۵ӳ.ȼ۵״̬Ǩͼ״ֽ̬һ٣γ״̬Ǩͼ.
ԣȻʱпܲ״̬ը⣬Ⱥ󾭹ʷ뽫ȼ۵ӳڱϢǰ£Խ״̬ǨͼתΪ״̬Ǩͼʹ״̬ռߴ󻯼.
4һӦʵ
ʵʱϵͳܼʱӦⲿ¼㹻ٶɶ¼ĴļӦϵͳ3.Ӧʱָӽյⲿ¼ɴӦ֮ӳʱ.ʵʱϵͳҪָ֮һ.ӳԹʵʱϵͳʱ״̬ǨͼΪӦʱ䣬Ҫһۼ״̬Ǩͼ. 
14. GL=(QL,IL,FL,W,TL)һ״̬Ǩͼ.УQLΪ״̬ϣILQLΪʼ״̬ϣFLQLΪֹ״̬ϣWΪż.ŴǨƳɱʱ䣩TLQLWQLGLΪɱ״̬Ǩͼ.֪ɱ״̬ǨͼԷʱ״̬Ǩͼת.Խһۼ״̬Ǩͼ.
15. Ga=(Qa,I,F,Ta)һ״̬Ǩͼ.УQa=QLWΪ״̬ϣI={(q,0)|qIL }Ϊʼ״̬ϣF={(q,t)|qFL,tW}Ϊֹ״̬ϣTaQaQa((q,t), (q,t))Taҽ (q,w,q)TLt=t+wGaΪۼ״̬Ǩͼ.
16. RQaGaеһ״̬ӼN(R)={r| (r, r)Ta, rR}ΪRĺ״̬.NF=Qa-FΪֹ״̬.
幹һʵʱϵͳۼ״̬ǨͼGaGaвŴ״̬ǨƵʱ䣬Iʱ״̬FӦʱ״̬.ȻӦʱ伴ΪIFֹ·ϵʱСֵ.Сֵ㷨.
ʵʱϵͳӦʱĻ״̬ͼ㷨£
룺GaIFNF
ӦʱTmin
BEGIN
(1) Tmin=;
(2) R=I;
(3) LOOP
(4) RF=RF;
(5) IF RF THEN
(6) BEGIN
(7) M=min{t|(q,t)(RF};
(8) IF M<Tmin THEN Tmin=M;
(9) END;
(10) R=RNF;
(11) IF R= THEN RETURN (Tmin);
(12) R=N(R);
(13) ENDLOOP
END.
LOOPΪѭ.minеСֵ.ռ.RRΪ״̬Ӽ.㷨ȷ֤.
1. 㷨Уiѭǰ(q, t)R ҽq, tǴIһ·ϵĵi״̬tΪ״̬ʱѵʱ䣬Ҹ·ֻһ״̬пֹ״̬.
֤. ѧɷ.ʼʱi=1ѭǰ㷨(2)R=I15֪.i=k-1ѭǰ.i=kѭ֮ǰ㷨еk-1ѭʱ㷨(10)R=RNF15ɼ֪(q,t)R䣬(q,t)ǴIһ·ϵĵk-1״̬tΪ״̬ʱѵʱ䣬Ҹ·ûֹ״̬.ִе㷨(12)R=N(R) ʱݶ1516֪RRĺ״̬(q,t)R(q,t)ǴIһ·ϵĵ(k-1)+1=k״̬tΪ״̬ʱѵʱ䣬Ҹ·ֻһ״̬пֹ״̬..i1.
֤.
2. 㷨УiѭǰTminǴIFвi״̬·ϵʱСֵ.·ĻTminΪ.
֤. 㷨(1)Tmin=..iѭǰi-1ѭʱ㷨(4)RF=RF֪(q,t)RF(q,t)R(q,t)F.⣬1֤֪̿i-1ѭʱִֻе㷨(12)ʱRе״̬ǴIһ·ϵĵi״̬ڵ(4)ʱRе״ֻ̬ǴIһ·ϵĵi-1״̬.ɶ15֪(q,t)ǴIһ·ϵĵi-1״ֹ̬״̬.tΪ״̬ʱʱ.㷨(7)tСֵM.㷨(8)СֵTminȽϣM<TminTmin=M.ȷTminǱдIFĲi״̬·ϵСʱ.ˣ2.
֤.
1. 㷨ȷ.
֤. iѭʱ㷨(4)RF=RF1֤֪̿RFаʼIľi״̬·ϵֹ״̬.RF٣ôִ㷨(6)(9)2Tmin˵ǰѵֹ״̬·ʱСֵ.㷨(10)R=RNFʹRаʼI·ϵĵiֹ״̬.R=ʾ·ѵֹ״̬ôʱTminͱдIF·ϵʱСֵݶ壬TminΪӦʱ.㷨(11)ȷTmin.
㷨ǿֹ.Ϊκ״̬Ǩͼ˵IF·Ϊ.㷨(10)(11)֪㷨ֻǵֹ״̬·һ.ˣ֮㷨ֹ.
֤.
ϵͳN״̬.ݼӷͳ˷4ݣԼ㷨ʱ临ΪON2.
5
ģģģ͵Ĳ㣬һµĻ״̬ǨͼļϵͳģͣͼۺԶΪͨʽżϵͳĸָ꣬ˣģģ;и͵Ŀɱ.⣬Ըϵͳʵ켣׼ȷطӳ״̬仯ϵͳܵӰ죬ʱǿκƣˣܹñȶģ͸׼ȷ.״̬ǨͼģͣһʵʱϵͳӦʱ㷨.֤͸Է㷨ȷЧ.
߼飺У1971ʿҪоΪʵʱ΢ں˷ֲʽϵͳܡۡݿ.
ΣŮ1935ڣҪоΪֲʽϵͳ.
˳У1932ڣҪоΪʵʱϵͳ֪ʶ⡢˹ǡܡ.
ߵλҵѧѧ빤ϵ150001
Σҵѧѧ빤ϵ150001
˳ҵѧѧ빤ϵ150001
οף
1µ. ϵͳ. Ϻ: ѧ,1986
(Wu Lide et al. Performance Evaluation for Computer Systems(in Chinese). Shanghai: Science & Technology Press, 1986)
2Stallings W. Operating Systems: Internals and Design Principles. Beijing: Tsinghua University Press, 1998
3Ԭɹ. ʵʱϵͳеĿɿԼ.  廪ѧ, 1995
(Yuan Youguang. The Reliability Techniques in Real-Time Systems(in Chinese). Beijing: Tsinghua University Press, 1995)
4ݹ˳, , . ݽṹ.  ѧ, 1998
(Guo Fushun, Wang Xiaofen, Li Lianzhi. Data Structure(in Chinese). Dalian: Dalian University of Science & Technology Press, 1998)
ոڣ1998-11-10
޸ڣ1999-02-08
