REAL-TIME SYSTEMS
DESIGN AND ANALYSIS
IEEE Press
445 Hoes Lane
Piscataway, NJ 08854
IEEE Press Editorial Board
Lajos Hanzo, Editor in Chief
R. Abhari
J. Anderson
G. W. Arnold
F. Canavero
M. El-Hawary
B-M. Haemmerli
M. Lanzerotti
D. Jacobson
O. P. Malik
S. Nahavandi
T. Samad
G. 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
REAL-TIME SYSTEMS
DESIGN AND ANALYSIS
Tools for the Practitioner
Fourth Edition
PHILLIP A. LAPLANTE
SEPPO J. OVASKA
IEEE PRESS
A JOHN WILEY & SONS, INC., PUBLICATION
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, (978) 750-8400, fax (978) 750-4470, 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,
(201) 748-6011, fax (201) 748-6008, 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 specifi cally disclaim any implied
warranties of merchantability or fi tness 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 profi t 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 (800) 762-2974, outside the
United States at (317) 572-3993 or fax (317) 572-4002.
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.
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
p. cm.
2011021433
Printed in the United States of America
oBook ISBN: 9781118136607
ePDF ISBN: 9781118136577
ePub ISBN: 9781118136591
eMobi ISBN: 9781118136584
10 9 8 7 6 5 4 3 2 1
To Nancy, Chris and Charlotte, with all my love
Phil:
To Helena, Sami and Samu — my everything
Seppo:
CONTENTS
Preface
Acknowledgments
1 Fundamentals of Real-Time Systems
1.1 Concepts and Misconceptions, 2
1.1.1 Defi nitions for Real-Time Systems, 2
1.1.2 Usual Misconceptions, 14
1.2 Multidisciplinary Design Challenges, 15
1.2.1 Infl uencing Disciplines, 16
1.3 Birth and Evolution of Real-Time Systems, 16
1.3.1 Diversifying Applications, 17
1.3.2 Advancements behind Modern Real-Time Systems, 19
1.4 Summary, 21
1.5 Exercises, 24
References, 25
2 Hardware for Real-Time Systems
2.1 Basic Processor Architecture, 28
2.1.1 Von Neumann Architecture, 29
2.1.2 Instruction Processing, 30
2.1.3 Input/Output and Interrupt Considerations, 33
2.2 Memory Technologies, 36
2.2.1 Different Classes of Memory, 36
2.2.2 Memory Access and Layout Issues, 38
2.2.3 Hierarchical Memory Organization, 41
xv
xxi
1
27
vii
viii
CONTENTS
2.3 Architectural Advancements, 43
2.3.1 Pipelined Instruction Processing, 45
2.3.2 Superscalar and Very Long Instruction
Word Architectures, 46
2.3.3 Multi-Core Processors, 48
2.3.4 Complex Instruction Set versus Reduced
Instruction Set, 50
2.4 Peripheral Interfacing, 52
2.4.1 Interrupt-Driven Input/Output, 53
2.4.2 Direct Memory Access, 56
2.4.3 Analog and Digital Input/Output, 58
2.5 Microprocessor versus Microcontroller, 62
2.5.1 Microprocessors, 62
2.5.2 Standard Microcontrollers, 64
2.5.3 Custom Microcontrollers, 66
2.6 Distributed Real-Time Architectures, 68
2.6.1 Fieldbus Networks, 68
2.6.2 Time-Triggered Architectures, 71
2.7 Summary, 73
2.8 Exercises, 74
References, 76
3 Real-Time Operating Systems
79
3.1 From Pseudokernels to Operating Systems, 80
3.1.1 Miscellaneous Pseudokernels, 82
3.1.2 Interrupt-Only Systems, 87
3.1.3 Preemptive Priority Systems, 90
3.1.4 Hybrid Scheduling Systems, 90
3.1.5 The Task Control Block Model, 95
3.2 Theoretical Foundations of Scheduling, 97
3.2.1 Scheduling Framework, 98
3.2.2 Round-Robin Scheduling, 99
3.2.3 Cyclic Code Scheduling, 100
3.2.4 Fixed-Priority Scheduling: Rate-Monotonic Approach, 102
3.2.5 Dynamic Priority Scheduling: Earliest Deadline
First Approach, 104
3.3 System Services for Application Programs, 106
3.3.1 Linear Buffers, 107
3.3.2 Ring Buffers, 109
3.3.3 Mailboxes, 110
3.3.4 Semaphores, 112
3.3.5 Deadlock and Starvation Problems, 114
3.3.6 Priority Inversion Problem, 118