Towards a viewpoint oriented design methodology for Multi-processor Real-Time Systems

  • L. Zhang Delft University of Technology
  • J. van Katwijk Delft University of Technology

Resumo


In this paper we describe a design methodology for the development of (potentially multi-processor) real-time system. Our proposed methodology differs fundamentally from current methodology and serves to help manage the complexity of massive-intensive systems. One of the distinguishing aspects of this methodology is in its ability to express timing constraints and verify to what extent such constraints are met. A second distinguishing aspect of this methodology is to develop a system according to five views of systems. In particular, the problems concerned with the transformation of the specifications into the parallel programs are addressed. The proposed methodology is applied to develop an onboard generator for generating transfer frames, complyannt to the CCSDS Recommendations [34], [35]. This onboard generator is implemented on a transputer network [1], [2].

Palavras-chave: Real-time systems, specification, performance evaluation, parallel processing, CCSDS, Transputer

Referências

U. de Carlini and U.Villano. Transputers and parallel architectures: message-passing distributed systems, ELLIS HORWOOD LIMITED, 1991.

I.Granham and T.King, The Transputer Handbook. Prentice Hall, 1990.

J.A. Stankovic, "Misconception about real-time computing: A serious problem for next generation systems," IEEE Computer. Vol.21, No.10, pp 10-19, October 1988.

S.T.Allworth and R.N.Zobel. Introduction to real-time software design. Macmillan computer science series 1987.

C.R.Andrews, Concurrent programming. The Benjamin/Cummings Publishing Company INC. 1991.

F.Becceli and Z.Lui, "On the execution of parallel programs on multiprocessor systems -A queuing theory approach," Journal of the association for computing machinery, Vol.37, No.2, 1990.

T.DeMarco, Structured Analysis and System Specification. Yourdon Press, ISBN 0-917072-07-3. 1978.

D.Bustard, J.Elder and J.Welsh. Concurrent program structures. C.A.R. Hoare Series Editor. Prentice Hall, 1988.

P.Chretienne, "The basic cyclic scheduling with deadlines," Disc. APP. Math., VOL 30, PP 109-123, 1991.

E.Gelenbe and G. Pujolle. Introduction to networks of queues. John Wiley, New York, 1986.

H. Gomaa, "A software design method for roi time systems." Communications of ACM, Vol. 27. No.9. 1984.

K.Hwang, F.A. Brigges. Computer architecture and parallel processing. Megraw-Hill Book Company, 1984.

INMOS, Transputer development system 2.0. INMOS. 1988.

Estelle." a formal description technique based on an extended state transition model." Draft Interational Standard ISO/TC97/SC21-DP9074. September 1987.

LOTOS."a formal description technique based on an the temporal ordering of observational behaviour," Draft International Standard ISO/TC97/5C'21-DP8807, September 1987.

L.Lamport. "What it means for a concurrent program to statisfy a specification: Why no one has specified priority," in Conference record of the 12th annual A.C.M. Symposium on Principles of programming languages, New Orleans. 1985.

Z. Manna. P.Wolper. "Synthesis of communicating processes from temporal logic specifications," ACM Transaction on programming languages and systems, Vol.6. No.1 January 1984.

A.Pnueli, "The temporal logic of programs," 18th I.E.E.E. Symposium on Foundations of computer Science, pp.46-57, 1977.

R. Milner, "A Calculus of Communicating Systems." In Lecture Notes in Computer Science. Vol. 92, Springer-Verlag. 1980.

D.Pountain and D. May, A tutorial introduction to OCCAM programming. INMOS, March 1987.

J.A. Stankovic and K.Ramamritham, "Hard real-time systems", IEEE Computer Society. Order Number 819. 1988.

W.Reisig, Petri Nets, Springer-Verlag, Berlin Heidelberg New York Tokyo, 1982.

INMOS, IMS B008 User Guide. 1989.

M.Jackson, System development. C.A.R. HOARE series, Prentice-Hall 1983.

Joint IECCA and MUF Committe on MASCOT (JIMCOM), The Official Handbook of MASCOT. Her Majesty's Stationery Office (June) 1987.

P.T. Ward and S.J. Mellor, Structured development for real-time systems. Yourdon Computing series-YOURDON PRESS-Prentice-Hall. 1985.

D. Harel. "Statecharts, a visual formalism for complex systems." Sciences of computer programming. North Holland, Vol.8, 1987, P.231-274.

HOOD Working Group. HOOD Reference Manual. draft B issue 3.0 (June 1989).

G.Berry and G. Gonthier: "The synchronous language ESTEREL: Design, Semantics and Impementation", INRIA report 842, 1988.

CCITT: "Functional specification and description language (SDL), Recommandations 2.101-Z.104." Vol.VI, Fasc. VI.7. Genova 1981.

E. Hirsh. Les Transputers: Application à la programmation concurrente. Editions Eyrolles 1990.

G. Pujolle and S.Fdida, Modèles de systemes et de réseaux. Editions Eyrolles. Paris, 1989.

P.Richard. Y. Edward. Tsuchiya. "A task allocation model for distributed computing systems." IEEE Transactions on Computers vol. 31. No.1. pp 41-47. 1982.

CCSDS. Recommendation for Space Data System Standards. Packet Telemetry. CCSDS Recommendation, Blue Book. Issue-2. January 1987 or later issue.

CCSDS, Advanced Orbiting Systems, Networks and Data links. CCSDS 700.0-G-2. October 1989.

I.G.L Technology, SADT, Un langage pour communiquer. Editions EYRolles, 1989.

D.J. Haltley, I.A. Pirbhai, Strategies for real-time systems. Yourdon computing series-Yourdon Press Prentice Hall 1985.

J.A. Stankovic, "A perspective on distributed computer systems," IEEE Trans. Computer. Vol c33, No. 12, pp 1102-1105, 1984.

P.Heidelberger and S.S. Lavenberg, "Computer performance evaluation methodology," IEEE Trans. Computer. Vol c33, No.12, pp 1102-105. 1984.

R.A. Sahner and K.S. Trivedi, "Performance and reliability analysis using directed acyclic graphs." IEEE Trans. Software Eng. vol. SE-13, No.10. 1987.

D.L. Eager, E.D. Lazowska, and J. Zahorjan, "Adaptive loading sharing in homogeneous distributed systems," IEEE Trans. Software. vol SE 12. No. 5, 1987.

W.W. Chu and L.M-T. Lan, "Task allocation and precedence relations for distributed real-time systems," IEEE Trans. Computer. Vol. C36 No. 6. 1987.

J.P. Huang, "Modeling of software partition for distributed real-time applications," IEEE Trans. Software. vol SE 11, No. 10, 1985.

L.M.Ni. C.W.Xu, and T.B. Gendreau, "A distributed drafting algorithm for load balancing." IEEE Trans. Software. vol SE 11, No. 10, 1985.

D.W:. Leinbaugh and M.R.Yamini. "Guaranteed response Times in a Distributed Hard - Real-Time Environment." IEEE Trans. Software. vol SE 12, No. 12, 1986.

S.S.Yau and J.J.P.Tsai. "A survey of Software Design Techniques," IEEE Trans. Software. vol SE 12. No. 6, 1986.

A. Dinning. "A survey of synchronization methods for parallel computers. Computer." IEEE Computer Society July 1989.

A. Thomasion and P.F. Bay. "Analytic queueing network models for parallel processing of task systems," IEEE Trans. Computer. Vol. C-35. No.12. 1986.

C.C. Roman. "A Taxonomy of current issues in requirements engineering, Computer," IEEE Computer Society, April. 1985.

D.T.Ross, "Applications and Extensions of SADT." IEEE Computer Society. April. 1985.

M. Alford, "SREM at the age of eight: the distributed computing design system." IEEE Computer Society. April, 1985.

Sol M. Shatz and J.P. Wang, "Introduction to distributed-software Engineering," IEEE Computer Society., October, 1987.

Hoare. C.A.R., "Communicating Sequential Processes," Comm. ACM. Aug. 1978, pp. 666-677.

J.A. Stankovic, K. Ramamritham, and S.Cheng, " Evaluation of a flexible Scheduling algorithm for distributed Hard Real-time Systems, IEEE Trans. Computer." Vol.C-34, No.12, 1985.

W. Zhao, K. Ramamritham. and J.A. Stankovic, "Scheduling Tasks with Resource Requirements in Hard Real-time Systems," IEEE Trans. Software. vol SE 13, No. 5, 1987.

M. Molloy, "Discrete Time Stochastic Petri Nets, IEEE Trans. Software Eng. vol SE 11, No. 4, 1985.

Y.T. Wang and R.J.T. Morris, "Load sharing in distributed systems," IEEE Trans. Computer. Vol. c-34, No.3, 1985,

B. Auernherimer and R. A. Kemmerer, "RT-ASLAN: A specification Langage for Real-time Systems" IEEE Trans. Software Eng. Vol. Se-12. No. 9, 1986.

F. Jahanian and A.K. Mok, "Safety Analysis of Timing properties in Real-time systems." IEEE Trans. Software Eng. Vol. Se-12. No. 9, 1986.

R.G. Fichman and C.F. Kemerer, "Object-oriented and conventional analysis and design methodologies," Computer, IEEE Computer Society. October 1992.

P. T. Ward, "The Transformation Schema: An Extension of the data flow diagram to represent control and timing," IEEE Trans. Software Eng. Vol. Se-12. No. 2, 1986.

G.Booch. "Object-oriented Development." IEEE Trans. Software Eng. Vol. Se-12. No. 2. 1986.

J.R. Cameron, "An overview of JSD," IEEE Trans. Software Eng. Vol. Se-12. No. 2, 1986.

L.Zhang, M.Galindo. D. Marquie and Y. Raynaud. "Methodology of real-time system design using multiprocessors". Microprocessors and Microsystems. Vol 17. No 14, may 1993.

W. A. Halang, "Real-time systems: Another Perspective", The Journal of Systems and Software. April 1992. pages 101-108.

A.C.Shaw, "Towards a timing semanties for programming languages". Foundations of real. time computing: Formal specifactions and methods. Kluwer academic publishers. 1991.

B.Hoogeboom and W.A. Halang, "The concept of time in the specification of real-time systems", in [68].

K.M.Kavi. Real-time system: abstractions, languages, and design methodologies. IEEE Computer Society Press, 1992.

K.M.Kavi and S.M.Yang "Real-time systems design methodologies: An introduction and a Survey," The Journal of Systems and Software, April 1992, pages R5-99.

A.D.Stoyenko, V.C. Hamacher, and R.C.Holt "Analyzing hard real-time programs for guaranteed schedulability" IEEE Trans. Software Eng. Vol. Se-17. No. 8. August 1991, pages 7397-750.

J.S.Ostroff "Formal methods for the specification and design of real-time safety critical systems" The Journal of Systems and Software, April 1992, pages 33-60.

W.A.Halang and A.D. Stoyenko, constructing predictable real time systems, Kluwer Academic Publishers, 1991.

A.M.V. Tilborg and C.M.Koob, Foundations of real-time computing: Formal specifactions and methods. Kluwer Academic publishers, 1991.

A.M.V. Tilborg and C.M.Koob. Fundations of real-time computing: Scheduling and Resource Management. Kluwer Academic publishers, 1991.

H.GomaaSoftware design methods for concurrent and real-time systems. Addison-Wesley Publishing Company, 1993.

J.Xu and D.L. Parnas, "On satisfying timing constraints in hard real time systems", Proceeding of the ACM SIGSOFT'91 Conference on Software for Critical Systems, New Orleans. Louisiana, December 4-6.1991.

S.T.Levi and A.K.Agrawala. Real-time system design McGraw-Hill international Editions. 1990.

M.Schiebe and S.Pferrer. Real-time systems engineering and applications, Kluwer Academic Publishers. 1992.

C.Y.Park and A.C Shaw, "Experiments with a program timing tool based on source level timing schema", Readings in Real-time systems, Edited by Y.H.Lee and C.M. Krishna, IEEE Computer Society Press, 1993.

Y.H.Lee and C.M.Krishna. Reading in Real-time systems. IEEE Computer Society Press. 1993.

C.Y.Park, "Predicting program execution times by analyzing static and dynamic program paths" Real-Time Systems, 5. 1993, pages 31-42.

E.V.Sorensen, J.Nordahl and N.H.Hansen, "From CSP models to Markov models" IEEE Trans. Software Eng. Vol. 19. No. 6, June 1993, pages 554-570.

C. U. Smith and L.G. Williams. "Software performance Engineering, A case study including performance comparison with design alternatives", IEEE Trans. Software Eng. Vol. 19. No. 7, July 1993.

D. A. Menasce, "A Methodology for performance evaluation of parallel applications on multiprocessors" Journal of parallel and distributed computing, 14, 1992 pages 1-14.

A.Sowmya, "A statecharts-based specification and verfication of real-time job scheduling systems", Real-time programming, IFAC Workshop, Bruges, Belgium, 23-26 June 1992.

S.Prehn and W.J.Toetenel, "VDM'91: Formal software development methods", LNCS 551, Springer-Verlag, 1991.

L.Zhang, "Une méthodologie de conception des applications temps reél destinées a être implantées sur des machines cibles multiprocesseurs", Ph.D disseration, 1993.

N.Plat, J.van Katwijk, and W.J. Toetenel," Applications and benefits of formal methods in software development." IEE-BCS Software Engineering Journal, 7(5):335-346. 1992.

G.Booch, Software engineering with ADA. The Benjamin/Cummings Publishing Company INC, 1983.

Liu,C.L. and Layland J.W, "Scheduling algorithms for multiprogramming in a hard real-time environment.", JACM 20 (1):46-61, 1973.

R. Rajkumar. Synchronization in real-time systems : a priority inheritance Kluwer academic publishers, 1991.
Publicado
26/10/1994
ZHANG, L.; KATWIJK, J. van. Towards a viewpoint oriented design methodology for Multi-processor Real-Time Systems. In: SIMPÓSIO BRASILEIRO DE ENGENHARIA DE SOFTWARE (SBES), 8. , 1994, Curitiba/PR. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 1994 . p. 223-250. DOI: https://doi.org/10.5753/sbes.1994.24470.