ѧ
Journal of Software
2000 Vol.11 No.1 P.95-103



ֲʽʵʱϵͳеԤ㷨
塡粨л
ժҪڷֲʽʵʱϵͳе,һϵо̬㷨,Чؽ˸ضµ͵.Щ㷨Ҫص,ǾҪ󱻵Ϊ֪.Ȼںܶʵʱϵͳ,ʱһЩһɵ,̬㷨Чܽܵ.ڷضӦñеĴ֮,õģ,ģͽڷֲʽʵʱϵͳѾõӦõľ̬㷨SAA(static allocation algorithms),˶ȵԤ㷨PAA(predicting allocation algorithm).ִʱͳ,ʵĺԤͶĶ̬,ϵͳʵʱ.,ģ,PAA㷨SAA㷨,ʱ䡢ؾȡϵͳӦʱ估زʵȶ෽.
ؼʡֲʽʵʱϵͳ,,㷨,Ԥ.
ͼšTP316
Predicting Allocation Algorithm in Distributed Real-Time Systems
XU Jian-fengZHU Qing-boHU NingXIE Li
(State Key Laboratory for Novel Software TechnologyNanjing University Nanjing210093)
AbstractFor periodic tasks in a distributed real-timesystem, a number of static allocation algorithms have been developed which solve the problem of assigning and scheduling tasks effectively under some determined conditions. The principal limitation of these approaches is that the attributes of the tasks have to be known. Sometimes the execution time or the number of subtasks of a periodic task might be a stochastic process obeying some rule. In such cases, the performance of the static schemes will decrease greatly. According to the analysis of the processing in specific application fields, the authors model two types of random tasks in distributed real-time systems and introduce the static allocation algorithms (SAA) which have been applied in engineering for the two task models separately. On the basis of SAA, a predicting allocation algorithm (PAA) is presented for the assignment and the scheduling of multitasks in distributed systems. The proposed algorithm, depending on the statistic features of the task execution time or of the number of subtasks included in the tasks, can predict the task parameters reasonably and implement dynamic allocation of the tasks, so that the system can meet the timing requirements more efficiently. The results of the simulation of the two task models have shown that compared with SAA scheme, the performance of PAA is significantly better in task finishing time, load balancing, system response time, ratio of discarded tasks, etc.
Key wordsDistributed real-time system, periodic task, allocation algorithm, predicting.
ʵʱϵͳ,Ǽȹע¼(event)(task)֮߼ϵȷ,ҲעϵͳָܷʱӦ¼,ӦĴ,ϵͳʵʱ.ϵͳӲ豸ȫȷ,ӰϵͳʵʱԵıȡĸֲԺ㷨.Եϵͳ,ʵֺʵ(scheduling)㷨ϵͳʵʱܵĹؼڣڷֲʽϵͳ,ڴڶڵ(processing node,PN),ÿPNϵĵ㷨,ڶPNϵķ(assigning)Ҳں̶ܴӰʵʱ,ڷֲʽʵʱϵͳ,ķ(allocating)һֱܵǵĹע.Ȼ,һЩ򵥵,ŻҲNP1.,о,Ҫһϵм,ЩµŻ㷨.
һ,ʵʱϵͳеԷΪԵ(periodic)ͷԵ(aperiodic),,ǿࡢҲΪıǾ̬㷨(static algorithm)210.һϵо̬㷨,еʹϵͳȡСļͨŸأ5ݣеʹ֮ĸԾ6,7ݣеʹPNеʱȡСֵΪĿ810.ྲ̬㷨Ҫ,ǾҪ󱻵,ʱ䡢˴֮ǰͺ̹ϵͨŹϵͨϢΪ֪,Щδ֪仯Χϴʱ,㷨ԴﵽĿ.Դǿʼ㷨,Ҫ˼,ʵʱԴʽϴȱ仯,ʵ,εƳÿһڸԴĹֵ,ԴΪȵ,ⷽĹѾȡһЩЧĽ11.Ŀǰ㷨еĲ֮ǵƺĽнϴ,ֵʵʲ֮ƫԿ,ʲʵʱҪȽϸߵϵͳ.
ںܶʵʱϵͳ,ʱϳֳһɵ,ķضӦñеĴ,õģ,ģͽڷֲʽʵʱϵͳеõӦõľ̬㷨SAA(static allocation algorithm),˶ȵԤ㷨PAA(predicting allocation algorithm).ִʱͳ,ʵֶĶ̬,Խʵʱ.ǸһЩSAAPAA㷨ܷ,,һķ.
1ģ
ִϢϵͳ״ǺCT,ҪԾԵźУԡڴԵزɼⲿź,ϢпΪźŵĵǵڵ,ɽΪڵ,ǳΪ֡(frame)ԡⲿı仯ͲĴ,źϻ϶кܴԣԡ֡Ϣطӳźŵ,֡ڵźűֳǿ.
źŽеĴ,ܽضԵǰ֡,ۺϿǵǰ֡źݵ,ȷǵľ,ϢϵͳйΪõش.,״źźݴ,󡢶εشͬʱ,ʹϢ̿ɱΪһϵش.״ĿΪشҪ.
1.1ԭ
һ,ȡʵĿϢĹ,i֡źΪSi,鳬޵¼,

Rijһ¼,о롢ٶȡλȵȲ;niΪi֡¼,0ĳһ֮仯,УSiΪһ.źŲʽԼźпܺӲʵĿȶϢ,źԵжϱԭ.
ԭRijΪĿݵĳֱҪǣi֡ź,i֮֡K2K֡ź,ڲСN(K)L֡ź,еL¼Ri1j1,Ri2j2,...,RiLjL

,KNΪ,DΪб,GΪ,Щɾģȷ.
ݼԭ,Siеÿ¼Si-K,...,Si-1,Si+1,...,Si+Kеĸ¼ش,ܻʵ.ʵʴ,Եi֡źSi,ǰK֡źΪһش,Siÿһ¼ǰK֡źÿһ¼б.شµ֡źŵϺ,ǾܹʵSiǰ2K֡źصҪ,ع̳Ϊش,Petriģͼ1ʾ.

Fig.1Petri net model o fmoving windows correlation processing
ͼ1شPetriģ
Petriͼиλõľ庭.p0ǰ֡źŵpiǰ֡źǰK-i+1֡źŵش(0iK)pjǰK-j+2֡źȡǰK-j+1֡ź(Kj2K)p2Kǰ֡źȡǰһ֡źţp2K+1ȴһ֡ź.
̼ģ͵,ǿԵóشҪ.
(1) SiǰK֡źŵشΪһTi,SiĵԵ,TiҲԵ.
(2) SiSjشninjα˴֮Ⱥ˳޹صغļб,,ÿһμбΪһ,ڵǰ֡ΪSiΪKشTi,ĶΪ

Ϊ֤˱ʽڱ߽µȷ,Ǽٶ

1.2ģ
,ǽNPNķֲʽͬϵͳеģ.
ģ͡ϵͳTΪ,ÿ֡ҪJ໥T1,T2,...,TJ,ڴǲͨżԴ,ʼÿTiһPNϵִʱȵ,Ϊһ̣Ci(k),Tiڵk֡ڵִʱΪCi(k),ڵkڽʱųΪ֪,ڻ֡ϵCi(k)֮(i=1,2,...,J).
ģ͡ϵͳTΪ,ÿ֡ҪJ໥T1,T2,...,TJ,ÿTiְni(k)ti1,ti2,...,tini(k)(i=1,2,...,J),ni(k)ǵk֡Tiе,һΧ仯,ڵkڽʱųΪ֪,ʣni(k)Ϊһ,ڻ֡ڵni(k).ͬ,ڲͨżԴ,ǼÿTiеһPNϵִʱ䶼ͬ,ΪDi(i=1,2,...,J).
2̬㷨SAA
ڷֲʽϵͳнȵҪ׼ǣÿһ֡ϵͳʱԼⲿ¼ӦʱӦȡСֵ.ʱȡϵͳPNִʱ,ʹȡСĿͨڸPNϵĺʵ.һ,ǿԽÿһΪⲿ¼һӦ,ĵȴʱ֮ΪϵͳӦʱ,ϵͳеķȷԺ,PNϽкȵҪĿıǼСӦʱ.,ֲʽʵʱϵͳķȷΪ裺ȷÿһ֡ڸPNϵķ,ȷPNԷϵĸĵȲ.
ģų,ģִʱ估ģиΪ,õľǷֲʽϵͳΪ򵥵Ķ,ʱԸ֪Ԥȷ͵Ȳ,Ǿ̬SAA㷨.,Ƿֱģ͵SAA㷨,PAA㷨Ļ.
2.1ڢģ͵ľ̬㷨SAA()
NJΪ,,ڪģе,ͨһЩ(ٷ)ҵʹϵͳȡʱķ䷽ʽ,ѱ֤һNP걸12,ʵʱϵͳĶ̬ûн.һʵֵĽƷ㷨.
ʧһ,ʱУCiǵݼ,,Ʒ㷨ѧɷ(iT1䵽PN1ϣ(ii)T1,...,Ti-1ѷ䵽PN,ҴʱϵͳС,СĽڵPNm(iiiTi䵽PNm,i =2,3,...,J.
˽㷨Ƿѽⷨ,ʣ12ݣ(1) J2Nʱ,㷨ľѷ䣻(2) һ,㷨õϵͳʱΪb*,㷨õϵͳʱΪb,b-b*b*;(3) ˽㷨ĸӶΪO(Jlog2J).
ڴ,㷨ѾڹʵеõӦ.SAA㷨,Ǽʵֶķ.
ڸPNϵ,ȶһһ֡еӦʱΪӱ֡ʼʱʱƬ,һPNӦʱ伴ΪӦʱ֮.Ȼ,ֲʽϵͳ䵽PNԺ,ÿPNõСӦʱ,ϵͳҲСӦʱ.ǼǶ,֮ûԤõȼ,ȷµԭTiTjǷͬһPN,(i) CiCjʱ,TiȼTjȼ(ii) Ci=Cjijʱ,TiȼTjȼ.
Ȼ,Ŷԭ,ĵ׼ܹʹPNﵽСӦʱ.
2.2ڢģ͵ľ̬㷨SAA()
ڿǢģ͵ķʱ,ȻԼУDiǵݼ,ڸеɵ,ʿɽΪģе,ʱ,öڢģ͵SAA㷨,ԻŻĽ㷨.ÿPNڲĵ,ȴֱӦâģ͵ķ,ΪԢģͶ,ϵͳӦʱ䲢ֱȡPNϸӦʱ,ɸӦʱ,˱ĵȲԣ
Ti,Ǽз䵽PNϵֱΪmi1,mi2,...,miN,,

3Ԥ㷨PAA
3.1˲-Ԥⷽ
,һʶڢģͶԾִʱ,ڢģͶԾе.ģгʱ,ҪSAA㷨,ֵֻ㷨ҪȷĲ,ķ,ֵںܶ֡пԶʵֵ,ȷķȷԶѷ.Ϊ˱֤1֡,òҪPNбʵߺܶĴ.ͬʱ,ڷԵ,ʹϵͳڲ״̬,ҲԽĽһ.,PNĴܵ,һһ֡ʼʱжִ,ҲĲ¹ߵز.ⷽ,бҪѰķ㷨.Դע⵽ģԵҪ.
(1) ȶԵӰ.ⲿϵͳȶ仯ᵼ¼ı仯,״ϵͳΪ,ɿռӱ,ϵȥԶ,Ȼı仯ȶйɵ,һ̶ǿԤ֪.
(2) ԵӰ.żȻصĴڳᵼⲿ㶯,㶯ɼı仯,״Ϊ,ϵͳڲⲿ״ӲֶӼ,㶯ȫġɫ,޷Ԥ֪.
ɼ,ϵͳܹʵķ,СصӰ,ܱȽ׼ȷعƳ֡,ķȲ.һ,˲Ϊṩֶ.Իع˲ά˲ȨС˲Ϳ˲ȷܹӦ͵Ķ̬ģ,ϵͳĹƾȣ13.Щ˶ѧѧ,Ӧѳķ,PAA㷨ڦ--˲,Ļʽ
״̬

X(k)ǲڵk֡еסһ׼׵ɵһά,w(k)Ϊֵ
˹,

ⷽ

y(k)Ϊǲڵk֡ʵʲֵ,H(k)=1 0 0,v(k)ǾֵΪ0ĸ˹
,䷽Ϊ.
˲Ԥⷽ

,kΪ֡,(k/k)Ϊk֡ƽֵ,(k/k-1)Ϊk-1֡ʱԵk֡Ԥֵ.
״̬֪̿,￼ǵҪǶױ仯ģ,߽׵ķֵİʾ.ںܶϵͳģϵķԺ,Բ˲ʵеĴӦ.ⷽеֵ˹,䷽ѡ˲,,òҪ.ǽ01֮С,һڦȷԺ,ԸŹϵʽ

ȷͦ.ڦ--˲Ҫص,˲ȷԺ,ʵʱвҪٿϵͳ˶ģ,˸֡еļ㸺С,ʹǽӦڴڴķֲʽϵͳΪ.
3.2Ԥ㷨PAA
һ,ֲʽϵͳеĶ̬ȼȿǷֲ,ҲǼе.ڷֲʽ,PNμӵ,񵽴ĳһPNʱ,ԸԴ״̬ȷܷɸ,ڲܽʱɽƼPN.ڼʽ,һPN,ȽPN,ȷʵķȲԺPNִ.PAA㷨üеȻ,ϵͳдһPN,һеĸʱ,PNܹøʵʲ,ݴ˽жһڸ˲Ԥ,ȻԤ·͵.Ϊģ,ݲǷֲʽϵͳͨʵʱܵӰ.
˲-Ԥ֪ⷽ̿,֡˲Ԥǰһ֡Ԥ,ϵͳʼʱ,Ǳ֪ʶԼ֡ڵʵʲԤ,PAA㷨Ϊʼ׶κ׶.
(1) ʼ׶
ϵͳʼǰ3֡,ľֵΪֵ,ͨSAA㷨,ʵϵͳеķ.ͬʱ,ڴ3֡,ǿԵõʵʵC(1),C(2)C(3)(ڴ3֡гز,޴ʵֵ),,ͨƷ,Եõ4֡˲Ԥ

(2) ׶
ڻԤֵԺ,ڴӵ4֡ʼÿһ֡,е˲-Ԥⷽ,ܹõһ֡Ԥֵ.Ȼ,ڲͬӦģ,ķõĹƾǲһ.˾ȶһЩģͿͨѧƵõ,Ҳͨõ,ʵʵȹͨʵʱͳƻֵ.ڴæ--÷ĹΪM,,

Ϊڵk֡еĹֵ.֮Ҫô˹ֵ,ΪڴԴ㹻,ݲʵԱ֤һ֡ʼʱ,ⳣʵʱϵͳΪҪ׼.,øĹ޺,ɸSAA㷨ԭʵֶķ͵.
˲Ԥֻⷽ6ζʽļ,PAA㷨ĸӶȻSAA㷨൱.
4㷨
SAA㷨ǹʵеõӦõķ㷨,PAA㷨ΪеĽ.ڶദģϵͳʵSAAPAA㷨,Ԣģͺ͢ģͷֱMonte Carlo㷨.ڢģ,10PNϵ40Ӧ;ڢģ,10PNϵ10,ÿԻֵҲϵʽ仯,Ļֵںͳʼλѡȡ,ǹעҪĿ꺯¼.
ʱϵڵn֡PNִʱΪPn,Ƕ

Ϊn֡ڵʱϵ.Ȼ,ֵС,ϵͳǱ.
ؾϵڵn֡PNִʱΪQn,Ƕ

Ϊn֡ڵĸؾϵ.ֱ,KPnKBn,ǽͨ㷨Դ
֤.
ӦʱϵڵnTiʱΪWn(i),Ƕ

Ϊn֡ڵӦʱϵ.ϵͳȵһҪԭǻСKRn.
زʡ,ദϵͳܱ֤ڽֹʱ֮ǰ,رǵʱ,ĳЩڹڽʱز.Ƕn֡еز֮ΪزKDn.
һϵͼгҪķ.
ͼ2ϵͳʼ750֡ĳһʵֵԤֵֵ,ڼҹɱ仯,Բʵֵһ߸㶯,㶯ķΧ뷽ĴС,ʱòķ͵Ȼ.ԤЧ,ϵͳӳ̬̬ҪһʱĻ,ڿʼʮ֡,Ԥֵʵֵ֮нϴ.̬Ժ,Ԥʵ߻Ǻ,Ϊǵǳʱ乤ϵͳ,ϵͳֵ̬Ժ,ԤЧʵʵȵҪ.ڲöԤⷽұ仯ܻñȽĽ,Ԥ,仯ĸӶȲǺܸʱ,ԤԿԱõЧ.


Fig.2Parameter value and predicting results of application tasks
ͼ2ӦʵֵԤЧ
ͼ310ֱԢģͺ͢ģͽ750֡õʱ䡢ؾȡӦʱϵز,ηĽͼʾͬ.ɼ,PAA㷨SAA㷨ڸָϾ.ֵָ,زʱĵСڲ3ָʹõ,,йлһز.ڢģ,SAA㷨زά40,PAA㷨ڳ̬Ԥϴ,زҲϸ,ϵͳ̬,Ԥﵽܵ͵ˮƽ,ʱزʻΪ0.ڢģ,SAA㷨زʽ2535֮,PAA㷨Ľ20,SAA40.֮Բֵܽ,ҪΪԤҲһ,ʵֵԤֵʱ,ͻֵָ߳ز.ͨԤ޲,ʹ㷨һݲ.

Fig.3Task run time for type 
ͼ3ģʱ

Fig.4Task run time for type
ͼ4ģʱ

Fig.5Performance of load balancing for type 
ͼ5ģ͸ؾ

Fig.6Performance of load balancing for type
ͼ6ģ͸ؾ

Fig.7Task response time for type 
ͼ7ģӦʱ

Fig.8Task response time for type 
ͼ8ģӦʱ

Fig.9Task time out ratio for type 
ͼ9ģز

Fig.10Task time out ratio for type 
ͼ10ģز
5
ֲʽʵʱϵͳкܶδ֪ػӰ쵽ϵͳ,ܹȽ׼ȷضЩδ֪Ԥ,Чؽ͵.㷨ⷽһ,ķ˵,ķԵõЧ.ƪ,вֵýһо,,ģ˲֮Ĺϵʼ״̬µķ׼.رҪָ,ĽԶȵӰ,δ漰ϵͳʵеһҪ,ͨ.ʵ,ֲܶʽʵʱϵͳеͨڡϢʱӵȲΪһ,Ҳܹ佨Ԥƻ,Ӷڷ㷨ۺϿͨŲ,㷨ضΪ,Ӧǰ.
оù863߿ƼĿ(No.863-308-19-01863-308-19-02)
壨Ͼѧ¼صʵҡϾ210093
粨Ͼѧ¼صʵҡϾ210093
Ͼѧ¼صʵҡϾ210093
лϾѧ¼صʵҡϾ210093
E-mail: zqb@dislab.nju.edu.cn
ο
1Garey M R, Johnson D S. Strong NP-completeness results: motivation, examples, and implications. Journal of the Association for Computing Machinery, 1978,25(3):499508
2Peng D-P, Shin K G. Modeling of concurrent task execution in a distributed system for real-time control. IEEE Transactions on Computers, 1987,36(4):500516
3Ramamritham K. Allocation and scheduling of precedence-related periodic tasks. IEEE Transactions on Parallel and Distributed Systems, 1995,6(4):412420
4C-J, Shin K G. Allocation of periodic task modules with precedence and deadline constraints in distributed real-time systems. IEEE Transactions on Computers, 1997,46(12):13381355
5Houstis C E. Module allocation of real-time applications for distributed systems. IEEE Transactions on Software Engineering, 1990,16(7):699709
6Tantawi A N, Towsley D. Optimal static load balancing in distributed computer systems. Journal of the ACM, 1985,(32):445465
7Chou T C K, Abraham J A. Load balancing in distributed systems. IEEE Transactions on Software Engineering, 1982,8(7):401422
8Shen C C, Tsai W H. A graph matching approach to optimal task assignment in distributed computing systems using a minimax criterion. IEEE Transactions on Computers, 1985,34(3):197203
9Chu W W, Lan L M T. Task allocation and precedence relations for distributed real-time systems. IEEE Transactions on Computers, 1987,36(6):667679
10Chu C C, Leung K K. Module replication and assignment for real-time distributed processing systems. Proceedings of the IEEE, 1987,(75):547562
11Tzilla Elrad, Lin Jin-long. Evolving processes and evolution schedulers for concurrent scheduling controls and parallel evolutionary computation. In: Rolim J ed. Proceedings of the 12th International Parallel Processing Symposium and the 9th Symposium on Parallel and Distributed Processing. Berlin: Springer-Verlag, 1998. 270278
12Lu Kai-cheng. Combinatorial Mathematics Algorithm and Analysis. Beijing: Tsinghua University Press, 1983
(¬.ѧ㷨.廪ѧ, 1983)
13Zhou Hong-ren, Jing Zhong-liang, Wang Pei-de. Tracking of Maneuvering Targets. Beijing: National Defense Industry Press, 1991
(ܺ,,.Ŀ.ҵ,1991)
1998-11-25ո
1999-02-02޸
