Real-Time Systems Design and Analysis E-Book

Phillip A. Laplante

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 897

Veröffentlichungsjahr: 2011

Beschreibung

The leading text in the field explains step by step how to write software that responds in real time

From power plants to medicine to avionics, the world increasingly depends on computer systems that can compute and respond to various excitations in real time. The Fourth Edition of Real-Time Systems Design and Analysis gives software designers the knowledge and the tools needed to create real-time software using a holistic, systems-based approach. The text covers computer architecture and organization, operating systems, software engineering, programming languages, and compiler theory, all from the perspective of real-time systems design.

The Fourth Edition of this renowned text brings it thoroughly up to date with the latest technological advances and applications. This fully updated edition includes coverage of the following concepts:

• Multidisciplinary design challenges

• Time-triggered architectures

• Architectural advancements

• Automatic code generation

• Peripheral interfacing

• Life-cycle processes

The final chapter of the text offers an expert perspective on the future of real-time systems and their applications.

The text is self-contained, enabling instructors and readers to focus on the material that is most important to their needs and interests. Suggestions for additional readings guide readers to more in-depth discussions on each individual topic. In addition, each chapter features exercises ranging from simple to challenging to help readers progressively build and fine-tune their ability to design their own real-time software programs.

Now fully up to date with the latest technological advances and applications in the field, Real-Time Systems Design and Analysis remains the top choice for students and software engineers who want to design better and faster real-time systems at minimum cost.

Leseprobe

Table of Contents

Cover

Series page

Title page

Copyright page

DEDICATION

PREFACE

ACKNOWLEDGMENTS

1 FUNDAMENTALS OF REAL-TIME SYSTEMS

1.1 CONCEPTS AND MISCONCEPTIONS

1.2 MULTIDISCIPLINARY DESIGN CHALLENGES

1.3 BIRTH AND EVOLUTION OF REAL-TIME SYSTEMS

1.4 SUMMARY

1.5 EXERCISES

2 HARDWARE FOR REAL-TIME SYSTEMS

2.1 BASIC PROCESSOR ARCHITECTURE

2.2 MEMORY TECHNOLOGIES

2.3 ARCHITECTURAL ADVANCEMENTS

2.4 PERIPHERAL INTERFACING

2.5 MICROPROCESSOR VERSUS MICROCONTROLLER

2.6 DISTRIBUTED REAL-TIME ARCHITECTURES

2.7 SUMMARY

2.8 EXERCISES

3 REAL-TIME OPERATING SYSTEMS

3.1 FROM PSEUDOKERNELS TO OPERATING SYSTEMS

3.2 THEORETICAL FOUNDATIONS OF SCHEDULING

3.3 SYSTEM SERVICES FOR APPLICATION PROGRAMS

3.4 MEMORY MANAGEMENT ISSUES

3.5 SELECTING REAL-TIME OPERATING SYSTEMS

3.6 SUMMARY

3.7 EXERCISES

4 PROGRAMMING LANGUAGES FOR REAL-TIME SYSTEMS

4.1 CODING OF REAL-TIME SOFTWARE

4.2 ASSEMBLY LANGUAGE

4.3 PROCEDURAL LANGUAGES

4.4 OBJECT-ORIENTED LANGUAGES

4.5 OVERVIEW OF PROGRAMMING LANGUAGES

4.6 AUTOMATIC CODE GENERATION

4.7 COMPILER OPTIMIZATIONS OF CODE

4.8 SUMMARY

4.9 EXERCISES

5 REQUIREMENTS ENGINEERING METHODOLOGIES

5.1 REQUIREMENTS ENGINEERING FOR REAL-TIME SYSTEMS

5.2 FORMAL METHODS IN SYSTEM SPECIFICATION

5.3 SEMIFORMAL METHODS IN SYSTEM SPECIFICATION

5.4 THE REQUIREMENTS DOCUMENT

5.5 SUMMARY

5.6 EXERCISES

5.7 APPENDIX 1: CASE STUDY IN SOFTWARE REQUIREMENTS SPECIFICATION

6 SOFTWARE DESIGN APPROACHES

6.1 QUALITIES OF REAL-TIME SOFTWARE

6.2 SOFTWARE ENGINEERING PRINCIPLES

6.3 PROCEDURAL DESIGN APPROACH

6.4 OBJECT-ORIENTED DESIGN APPROACH

6.5 LIFE CYCLE MODELS

6.6 SUMMARY

6.7 EXERCISES

6.8 APPENDIX 1: CASE STUDY IN DESIGNING REAL-TIME SOFTWARE

7 PERFORMANCE ANALYSIS TECHNIQUES

7.1 REAL-TIME PERFORMANCE ANALYSIS

7.2 APPLICATIONS OF QUEUING THEORY

7.3 INPUT/OUTPUT PERFORMANCE

7.4 ANALYSIS OF MEMORY REQUIREMENTS

7.5 SUMMARY

7.6 EXERCISES

8 ADDITIONAL CONSIDERATIONS FOR THE PRACTITIONER

8.1 METRICS IN SOFTWARE ENGINEERING

8.2 PREDICTIVE COST MODELING

8.3 UNCERTAINTY IN REAL-TIME SYSTEMS

8.4 DESIGN FOR FAULT TOLERANCE

8.5 SOFTWARE TESTING AND SYSTEMS INTEGRATION

8.6 PERFORMANCE OPTIMIZATION TECHNIQUES

8.7 SUMMARY

8.8 EXERCISES

9 FUTURE VISIONS ON REAL-TIME SYSTEMS

9.1 VISION: REAL-TIME HARDWARE

9.2 VISION: REAL-TIME OPERATING SYSTEMS

9.3 VISION: REAL-TIME PROGRAMMING LANGUAGES

9.4 VISION: REAL-TIME SYSTEMS ENGINEERING

9.5 VISION: REAL-TIME APPLICATIONS

9.6 SUMMARY

9.7 EXERCISES

GLOSSARY

ABOUT THE AUTHORS

Index

IEEE Press

445 Hoes Lane

Piscataway, NJ 08854

IEEE Press Editorial Board

Lajos Hanzo, Editor in Chief

R. AbhariM. El-HawaryO. P. MalikJ. AndersonB-M. HaemmerliS. NahavandiG. W. ArnoldM. LanzerottiT. SamadF. CanaveroD. JacobsonG. Zobrist

Kenneth Moore, Director of IEEE Book and Information Services (BIS)

Technical Reviewers

Larry Bernstein, Stevens Institute of Technology

Bernard Sick, University of Kassel

Olli Vainio, Tampere University of Technology

Cover photo courtesy of NASA.

Copyright © 2012 by the Institute of Electrical and Electronics Engineers, Inc.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey. All rights reserved.

Published simultaneously in Canada

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permissions.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Laplante, Phillip A.

 Real-time systems design and analysis : tools for the practitioner / Phillip A. Laplante, Seppo J. Ovaska.—4th ed.

p. cm.

 ISBN 978-0-470-76864-8 (hardback)

 1. Real-time data processing. 2. System design. I. Ovaska, Seppo J., 1956- II. Title.

 QA76.54.L37 2012

 004'.33–dc23

2011021433

oBook ISBN: 9781118136607

ePDF ISBN: 9781118136577

ePub ISBN: 9781118136591

eMobi ISBN: 9781118136584

Phil:

To Nancy, Chris and Charlotte, with all my love

Seppo:

To Helena, Sami and Samu—my everything

PREFACE

This book is an introductory text about real-time systems—systems where timeliness is a crucial part of the correctness of the system. Real-time software designers must be familiar with computer architecture and organization, operating systems and related services, programming languages, systems and software engineering, as well as performance analysis and optimization techniques. The text provides a pragmatic discussion of these subjects from the perspective of the real-time systems designer. Because this is a staggering task, depth is occasionally sacrificed for breadth. Nevertheless, thoughtful suggestions for additional literature are provided where depth has been sacrificed due to the available page budget or other reasons.

This book is intended for junior–senior level and graduate computer science, computer engineering and electrical engineering students, as well as practicing software, systems and computer engineers. It can be used as a graduate level text if it is supplemented with an advanced reader or a focused selection of scholarly articles on a specific topic (which could be gathered from the up-to-date bibliographies of this edition). Our book is especially useful in an industrial setting for new real-time systems designers who need to get “up to speed” very quickly. Earlier editions of this book have been used in this way to teach short courses for several industrial clients. Finally, we intend for the book to be a desk reference of long-lasting value, even for experienced real-time systems designers and project managers.

The reader is assumed to have basic knowledge in programming in one of the more popular languages, but other than this, the prerequisites for this text are minimal. Some familiarity with discrete mathematics is helpful in understanding some of the formalizations, but it is not essential.

Since there are several preferred languages for real-time systems design, such as Ada, C, C++, C#, and increasingly, Java, it would be unjust to focus this book on one language, say C, when the theory and framework should be language independent. However, for uniformity of discussion, certain points are illustrated, as appropriate, in generic assembly language and C.

While the provided program codes are not intended to be ready-to-use, they can be easily adapted with a little tweaking for use in a real system.

This book is organized into nine chapters that are largely self-contained. Thus, the material can be rearranged or omitted depending on the background and interests of the instructor or reader. It is advised, however, that Chapter 1 would be explored first, because it contains an introduction to real-time systems as well as the necessary terminology.

Each of the chapters contains both easy and more challenging exercises that stimulate the reader to confront actual problems. The exercises, however, cannot serve as a substitute for carefully planned laboratory work or practical experience.

The first chapter provides an overview of the nature of real-time systems. Much of the basic vocabulary relating to real-time systems is developed along with a discussion of the main challenges facing the real-time system designer. Besides, a brief historical review is given. The purpose of this chapter is to foreshadow the rest of the book as well as quickly acquaint the reader with pertinent terminology.

The second chapter presents a detailed review of central computer architecture concepts from the perspective of the real-time systems designer. Specifically, the impact of advanced architectural features on real-time performance is discussed. The remainder of the chapter outlines different memory technologies, input/output techniques, and peripheral support for embedded systems. The intent here is to increase the reader’s awareness of the impact of the computer architecture on various design considerations.

Chapter 3 provides the core of the text for those who are building practical real-time systems. This comprehensive chapter describes the three principal real-time kernel services: scheduling/dispatching, intertask communication/synchronization, and memory management. It also covers special problems inherent in these designs, such as deadlock and priority inversion.

Chapter 4 begins with a discussion of specific language features desirable in good software engineering practice in general and real-time systems design in particular. An evaluative review of several widely used programming languages in real-time systems design, with respect to these features, follows. Our intent is to provide explicit criteria for rating a language’s ability to support real-time systems and to alert the user to the possible drawbacks of using each language in real-time applications.

In Chapter 5, the nature of requirements engineering is first discussed. Then a collection of rigorous techniques in real-time system specification is presented with illustrative examples. Such rigorous methods are particularly useful when automatic design and code-generation approaches are to be used later in the development life cycle. Next, structured and object-oriented methodologies are discussed as alternative paradigms for requirements writing. At the end of this chapter, an extensive case study is provided.

Chapter 6 surveys several commonly applied design specification techniques used in both structured and object-oriented design. An emphasis on their applicability to real-time systems is made throughout. No single technique is a silver bullet, and the reader is encouraged to adopt his or her own formulation of specification techniques for the given application. A comprehensive design case study is also provided.

Chapter 7 discusses performance analysis techniques based on diverse estimation approaches. The proposed toolset is fully usable even before it is possible to perform any direct measurements. Moreover, a pragmatic discussion on the use of classical queuing theory for analyzing real-time systems is provided. Input/output performance issues are considered with an emphasis on buffer-size calculation. Finally, a focused analysis of memory utilization in real-time systems is presented.

Chapter 8 discusses additional software engineering considerations, including the use of software metrics and techniques for improving the fault-tolerance and overall reliability of real-time systems. Later in the chapter, different techniques for improving reliability through rigorous testing are discussed. Systems integration and performance optimization issues are also considered.

In Chapter 9, we look to the future of real-time systems hardware, software, and applications. Much of this chapter is speculative, and we had great fun imagining things yet to come and the way things ought to be with respect to real-time systems technology. This chapter forms a fruitful basis for class discussions, debates, and student projects.

When our book is used in a university course, typically students are asked to build a real-time multitasking system of their choice. Usually, it is a game on a PC, but some students can be expected to build embedded hardware controllers of moderate complexity. The authors’ assignment to the reader would be to build such a game or simulation, using at least the coroutine model. The application should be useful or at least pleasing, so some sort of a game is a good choice. The mini-project should take no more than 20 hours and cover all phases of the software life cycle model discussed in the text. Hence, those readers who have never built a real-time system will have the benefit of the instructive experience.

Real-time systems engineering is based on more than 50 years of experience and global contributions by numerous individuals and organizations. Rather than clutter the text with endless citations for the origin of each idea, the authors chose to cite only the key ideas where the reader would want to seek out the source for further reading. Some of the text is adapted from two other books written by the first author on software engineering and computer architecture, Laplante (2003) and Gilreath and Laplante (2003), respectively. Where this has been done, it is so noted.

Many solid theoretical treatments of real-time systems exist, and where applicable, they are noted. Nonetheless, these books or journal articles are sometimes too theoretical for practicing software engineers and students who are often impatient to wade through the derivations for the resultant payoff. They want results that they can use now in the trenches, and they want to see how they can be used, not just know that they exist. In this text, an attempt is made to distill the most valuable of the theoretical results, combined with practical experience and insight to provide a toolkit for the practitioner.

This book contains extensive bibliographies at the end of each chapter. Where verbatim phrases were used, and where a figure came from another source, the authors tried to cite it appropriately. However, if any were inadvertently overlooked, the authors wish to correct the unfortunate error. Please notify the authors if you find any errors of omission, commission, citation, and so forth by e-mail, at [email protected] or [email protected], and they will be corrected at the next possible opportunity.

Since 1992, thousands of copies of the first three editions of this book have been sold to the college text and professional markets throughout the world. The only thing more gratifying than its adoption at such prestigious universities as Carnegie Mellon University, the University of Illinois at Urbana-Champaign, Princeton University, the United States Air Force Academy, Polytechnic University, and many others around the world, has been the enthusiastic feedback received from numerous individuals thankful for the influence that the book has had on them. The continuing international success of the first three editions along with recent technological advancements demanded that a fourth edition be produced.

The most fundamental change in the fourth edition is a new co-author, Dr. Seppo Ovaska, whose vast experience greatly complements that of the first author and adds a strong and timely international perspective.

The fourth edition addresses the important changes that have occurred in the theory and practice in the construction of real-time systems since the publishing of the third edition in 2004. Chapters 1–8 have been carefully revised to incorporate new material, correction of errors, and elimination of outdated material. Moreover, Chapter 9 is a brand-new chapter devoted to future visions on real-time systems. Totally new or substantially revised discussions include:

Multidisciplinary design challengesBirth and evolution of real-time systemsMemory technologiesArchitectural advancementsPeripheral interfacingDistributed real-time architecturesSystem services for application programsSupplementary criteria for multi-core and energy-aware supportAutomatic code generationLife cycle modelsArguments related to parallelizationUncertainty in real-time systemsTesting patterns and exploratory testingReal-time device driversFuture visions on real-time systems

While approximately 30% of previous material has been discarded, another 40% has been added, resulting in a unique and modern text. In addition, several new examples have been included to illustrate various important points. Hence, it is with pride and a sense of accomplishment that we are presenting this timely and carefully composed book to students and practicing engineers.

PHILLIP A. LAPLANTE

West Chester, Pennsylvania

Seppo J. Ovaska

Hyvinkää, Finland

August 2011

REFERENCES

W. F. Gilreath and P. A. Laplante, Computer Architecture: A Minimalist Approach. Norwell, MA: Kluwer Academic Publishers, 2003.

P. A. Laplante, Software Engineering for Image Processing. Boca Raton, FL: CRC Press, 2003.

ACKNOWLEDGMENTS

Phil Laplante wishes to thank his dear friend Dr. Seppo Ovaska for being the perfect collaborator. Easy to work with, Seppo’s industriousness, experience, insight, patience, and attention to detail perfectly complemented Phil’s strengths and weaknesses. The vast majority of differences between the third and fourth editions are due to Seppo’s hard work. As a result of Seppo’s contributions, the fourth edition is far superior to any previous edition of this book. And this book is now as much his vision and legacy, as the first three editions were mine.

Phil also wishes to thank his wife Nancy and his children Christopher and Charlotte for putting up with the seemingly endless work on this manuscript and too many other projects to mention over these many years.

Seppo: I am grateful to my wife Helena and my sons Sami and Samu for everything we have experienced together. Although it is a tiny gesture compared with all that you have given to me, I humbly dedicate this book to you. And finally, Phil, it was a true pleasure to work with you in this exciting and rewarding book project.

P.A.L.

S.J.O.

1

FUNDAMENTALS OF REAL-TIME SYSTEMS

The term “real time” is used widely in many contexts, both technical and conventional. Most people would probably understand “in real time” to mean “at once” or “instantaneously.” The Random House Dictionary of the English Language (2nd unabridged edition, 1987), however, defines “realtime” as pertaining to applications in which the computer must respond as rapidly as required by the user or necessitated by the process being controlled. These definitions, and others that are available, are quite different, and their differences are often the cause of misunderstanding between computer, software and systems engineers, and the users of real-time systems. On a more pedantic level, there is the issue of the appropriate writing of the term “real-time.” Across technical and pedestrian literature, various forms of the term, such as real time, real-time, and realtime may appear. But to computer, software, and systems engineers the preferred form is real-time, and this is the convention that we will follow throughout this text.

Consider a computer system in which data need to be processed at a regular rate. For example, an aircraft uses a sequence of accelerometer pulses to determine its position. Systems other than avionic ones may also require a rapid response to events that occur at nonregular rates, such as handling an overtemperature failure in a nuclear power plant. Even without defining the term “real-time,” it is probably understood that those events demand timely or “real-time” processing.

Now consider a situation in which a passenger approaches an airline check-in counter to pick up his boarding pass for a certain flight from New York to Boston, which is leaving in five minutes. The reservation clerk enters appropriate information into the computer, and a few seconds later a boarding pass is printed. Is this a real-time system?

Indeed, all three systems—aircraft, nuclear power plant, and airline reservations—are real-time, because they must process information within a specified interval or risk system failure. Although these examples may provide an intuitive definition of a real-time system, it is necessary to clearly comprehend when a system is real-time and when it is not.

To form a solid basis for the coming chapters, we first define a number of central terms and correct common misunderstandings in Section 1.1. These definitions are targeted for practitioners, and thus they have a strong practical point-of-view. Section 1.2 presents the multidisciplinary design challenges related to real-time systems. It is shown that although real-time systems design and analysis are subdisciplines of computer systems engineering, they have essential connections to various other fields, such as computer science and electrical engineering—even to applied statistics. It is rather straightforward to present different approaches, methods, techniques, or tools for readers, but much more difficult to convey the authors’ insight on real-time systems to the audience. Nevertheless, our intention is to provide some insight in parallel with specific tools for the practitioner. Such insight is built on practical experiences and adequate understanding of the key milestones in the field. The birth of real-time systems, in general, as well as a selective evolution path related to relevant technological innovations, is discussed in Section 1.3. Section 1.4 summarizes the preceding sections on fundamentals of real-time systems. Finally, Section 1.5 provides exercises that help the reader to gain basic understanding on real-time systems and associated concepts.

1.1 CONCEPTS AND MISCONCEPTIONS

The fundamental definitions of real-time systems engineering can vary depending on the resource consulted. Our pragmatic definitions have been collected and refined to the smallest common subset of agreement to form the vocabulary of this particular text. These definitions are presented in a form that is intended to be most useful to the practicing engineer, as opposed to the academic theorist.

1.1.1 Definitions for Real-Time Systems

The hardware of a computer solves problems by repeated execution of machine-language instructions, collectively known as software. Software, on the other hand, is traditionally divided into system programs and application programs.

System programs consist of software that interfaces with the underlying computer hardware, such as device drivers, interrupt handlers, task schedulers, and various programs that act as tools for the development or analysis of application programs. These software tools include compilers, which translate high-level language programs into assembly code; assemblers, which convert the assembly code into a special binary format called object or machine code; and linkers/locators, which prepare the object code for execution in a specific hardware environment. An operating system is a specialized collection of system programs that manage the physical resources of the computer. As such, a real-time operating system is a truly important system program (Anh and Tan, 2009).

Application programs are programs written to solve specific problems, such as optimal hall-call allocation of an elevator bank in a high-rise building, inertial navigation of an aircraft, and payroll preparation for some industrial company. Certain design considerations play a role in the design of system programs and application software intended to run in real-time environments.

The notion of a “system” is central to software engineering, and indeed to all engineering, and warrants formalization.