第1页 / 共528页
第2页 / 共528页
第3页 / 共528页
第4页 / 共528页
第5页 / 共528页
第6页 / 共528页
第7页 / 共528页
第8页 / 共528页
Hard Real-Time Computing Systems 3rd edition.pdf
GetFullPageImage
front-matter
Hard Real-Time Computing Systems
CONTENTS
PREFACE
Contents of the chapters
Difference with the second edition
Acknowledgments
fulltext
1 A GENERAL VIEW
1.1 INTRODUCTION
1.2 WHAT DOES REAL TIME MEAN?
1.2.1 THE CONCEPT OF TIME
1.2.2 LIMITS OF CURRENT REAL-TIME SYSTEMS
1.2.3 DESIRABLE FEATURES OF REAL-TIME SYSTEMS
1.3 ACHIEVING PREDICTABILITY
1.3.1 DMA
1.3.2 CACHE
1.3.3 INTERRUPTS
APPROACH A
APPROACH B
APPROACH C
1.3.4 SYSTEM CALLS
1.3.5 SEMAPHORES
1.3.6 MEMORY MANAGEMENT
1.3.7 PROGRAMMING LANGUAGE
Exercises
fulltext(1)
2 BASIC CONCEPTS
2.1 INTRODUCTION
2.2 TYPES OF TASK CONSTRAINTS
2.2.1 TIMING CONSTRAINTS
2.2.2 PRECEDENCE CONSTRAINTS
2.2.3 RESOURCE CONSTRAINTS
2.3 DEFINITION OF SCHEDULING PROBLEMS
2.3.1 CLASSIFICATION OF SCHEDULING ALGORITHMS
GUARANTEE-BASED ALGORITHMS
BEST-EFFORT ALGORITHMS
2.3.2 METRICS FOR PERFORMANCE EVALUATION
2.4 SCHEDULING ANOMALIES
NUMBER OF PROCESSORS INCREASED
COMPUTATION TIMES REDUCED
PRECEDENCE CONSTRAINTS WEAKENED
ANOMALIES UNDER RESOURCE CONSTRAINTS
ANOMALIES UNDER NON-PREEMPTIVE SCHEDULING
ANOMALIES USING A DELAY PRIMITIVE
Exercises
fulltext(2)
3 APERIODIC TASK SCHEDULING
3.1 INTRODUCTION
3.2 JACKSON’S ALGORITHM
3.2.1 EXAMPLES
EXAMPLE 1
EXAMPLE 2
3.2.2 GUARANTEE
3.3 HORN’S ALGORITHM
3.3.1 EDF OPTIMALITY
3.3.2 EXAMPLE
3.3.3 GUARANTEE
3.4 NON-PREEMPTIVE SCHEDULING
3.4.1 BRATLEY’S ALGORITHM
3.4.2 THE SPRING ALGORITHM
3.5 SCHEDULING WITH PRECEDENCE CONSTRAINTS
3.5.1 LATEST DEADLINE FIRST
3.5.2 EDF WITH PRECEDENCE CONSTRAINTS
MODIFICATION OF THE RELEASE TIMES
MODIFICATION OF THE DEADLINES
PROOF OF OPTIMALITY
3.6 SUMMARY
Exercises
fulltext(3)
4 PERIODIC TASK SCHEDULING
4.1 INTRODUCTION
4.1.1 PROCESSOR UTILIZATION FACTOR
4.2 TIMELINE SCHEDULING
4.3 RATE MONOTONIC SCHEDULING
4.3.1 OPTIMALITY
4.3.2 CALCULATION OF ULUB FOR TWO TASKS
4.3.3 CALCULATION OF ULUB FOR N TASKS
4.3.4 HYPERBOLIC BOUND FOR RM
4.4 EARLIEST DEADLINE FIRST
4.4.1 SCHEDULABILITY ANALYSIS
4.4.2 AN EXAMPLE
4.5 DEADLINE MONOTONIC
4.5.1 SCHEDULABILITY ANALYSIS
4.5.2 RESPONSE TIME ANALYSIS
4.5.3 WORKLOAD ANALYSIS
4.6 EDF WITH CONSTRAINED DEADLINES
4.6.1 THE PROCESSOR DEMAND APPROACH
4.6.2 REDUCING TEST INTERVALS
EXAMPLE
4.7 COMPARISON BETWEEN RM AND EDF
Exercises
fulltext(4)
5 FIXED-PRIORITY SERVERS
5.1 INTRODUCTION
5.2 BACKGROUND SCHEDULING
5.3 POLLING SERVER
5.3.1 SCHEDULABILITY ANALYSIS
5.3.2 DIMENSIONING A POLLING SERVER
5.3.3 APERIODIC GUARANTEE
5.4 DEFERRABLE SERVER
5.4.1 SCHEDULABILITY ANALYSIS
CALCULATION OF ULUB FOR RM+DS
5.4.2 DIMENSIONING A DEFERRABLE SERVER
5.4.3 APERIODIC GUARANTEE
5.5 PRIORITY EXCHANGE
5.5.1 SCHEDULABILITY ANALYSIS
5.5.2 PE VERSUS DS
5.6 SPORADIC SERVER
5.6.1 SCHEDULABILITY ANALYSIS
5.7 SLACK STEALING
5.7.1 SCHEDULABILITY ANALYSIS
5.8 NON-EXISTENCE OF OPTIMAL SERVERS
5.9 PERFORMANCE EVALUATION
5.10 SUMMARY
Exercises
fulltext(5)
6 DYNAMIC PRIORITY SERVERS
6.1 INTRODUCTION
6.2 DYNAMIC PRIORITY EXCHANGE SERVER
6.2.1 SCHEDULABILITY ANALYSIS
6.2.2 RECLAIMING SPARE TIME
6.3 DYNAMIC SPORADIC SERVER
6.3.1 SCHEDULABILITY ANALYSIS
6.4 TOTAL BANDWIDTH SERVER
6.4.1 SCHEDULABILITY ANALYSIS
6.5 EARLIEST DEADLINE LATE SERVER
6.5.1 EDL SERVER PROPERTIES
6.6 IMPROVED PRIORITY EXCHANGE SERVER
6.6.1 SCHEDULABILITY ANALYSIS
6.6.2 REMARKS
6.7 IMPROVING TBS
6.7.1 AN EXAMPLE
6.7.2 OPTIMALITY
6.8 PERFORMANCE EVALUATION
6.9 THE CONSTANT BANDWIDTH SERVER
6.9.1 DEFINITION OF CBS
6.9.2 SCHEDULING EXAMPLE
6.9.3 FORMAL DEFINITION
6.9.4 CBS PROPERTIES
6.9.5 SIMULATION RESULTS
6.9.6 DIMENSIONING CBS PARAMETERS
TAKING OVERHEADS INTO ACCOUNT
6.10 SUMMARY
Exercises
fulltext(6)
7 RESOURCE ACCESS PROTOCOLS
7.1 INTRODUCTION
7.2 THE PRIORITY INVERSION PHENOMENON
7.3 TERMINOLOGY AND ASSUMPTIONS
7.4 NON-PREEMPTIVE PROTOCOL
7.4.1 BLOCKING TIME COMPUTATION
7.5 HIGHEST LOCKER PRIORITY PROTOCOL
7.5.1 BLOCKING TIME COMPUTATION
7.6 PRIORITY INHERITANCE PROTOCOL
7.6.1 PROTOCOL DEFINITION
EXAMPLES
7.6.2 PROPERTIES OF THE PROTOCOL
7.6.3 BLOCKING TIME COMPUTATION
EXAMPLE
7.6.4 IMPLEMENTATION CONSIDERATIONS
7.6.5 UNSOLVED PROBLEMS
CHAINED BLOCKING
DEADLOCK
7.7 PRIORITY CEILING PROTOCOL
7.7.1 PROTOCOL DEFINITION
EXAMPLE
7.7.2 PROPERTIES OF THE PROTOCOL
7.7.3 BLOCKING TIME COMPUTATION
7.7.4 IMPLEMENTATION CONSIDERATIONS
7.8 STACK RESOURCE POLICY
7.8.1 DEFINITIONS
PRIORITY
PREEMPTION LEVEL
RESOURCE UNITS
RESOURCE REQUIREMENTS
RESOURCE CEILING
SYSTEM CEILING
7.8.2 PROTOCOL DEFINITION
OBSERVATIONS
EXAMPLE
7.8.3 PROPERTIES OF THE PROTOCOL
7.8.4 BLOCKING TIME COMPUTATION
7.8.5 SHARING RUNTIME STACK
7.8.6 IMPLEMENTATION CONSIDERATIONS
7.9 SCHEDULABILITY ANALYSIS
7.10 SUMMARY
Exercises
fulltext(7)
8 LIMITED PREEMPTIVE SCHEDULING
8.1 INTRODUCTION
8.1.1 TERMINOLOGY AND NOTATION
8.2 NON-PREEMPTIVE SCHEDULING
8.2.1 FEASIBILITY ANALYSIS
8.3 PREEMPTION THRESHOLDS
8.3.1 FEASIBILITY ANALYSIS
8.3.2 SELECTING PREEMPTION THRESHOLDS
8.4 DEFERRED PREEMPTIONS
8.4.1 FEASIBILITY ANALYSIS
8.4.2 LONGEST NON-PREEMPTIVE INTERVAL
8.5 TASK SPLITTING
8.5.1 FEASIBILITY ANALYSIS
8.5.2 LONGEST NON-PREEMPTIVE INTERVAL
8.6 SELECTING PREEMPTION POINTS
8.6.1 SELECTION ALGORITHM
8.7 ASSESSMENT OF THE APPROACHES
8.7.1 IMPLEMENTATION ISSUES
8.7.2 PREDICTABILITY
8.7.3 EFFECTIVENESS
8.7.4 CONCLUSIONS
Exercises
fulltext(8)
9 HANDLING OVERLOAD CONDITIONS
9.1 INTRODUCTION
9.1.1 LOAD DEFINITIONS
9.1.2 TERMINOLOGY
9.2 HANDLING APERIODIC OVERLOADS
9.2.1 PERFORMANCE METRICS
9.2.2 ON-LINE VERSUS CLAIRVOYANT SCHEDULING
9.2.3 COMPETITIVE FACTOR
TASK GENERATION STRATEGY
PROOF OF THE BOUND
EXTENSIONS
9.2.4 TYPICAL SCHEDULING SCHEMES
9.2.5 THE RED ALGORITHM
9.2.6 DOVER: A COMPETITIVE ALGORITHM
9.2.7 PERFORMANCE EVALUATION
9.3 HANDLING OVERRUNS
9.3.1 RESOURCE RESERVATION
9.3.2 SCHEDULABILITY ANALYSIS
9.3.3 HANDLING WRONG RESERVATIONS
9.3.4 RESOURCE SHARING
SOLUTION 1: BUDGET CHECK
SOLUTION 2: BUDGET OVERRUN
9.4 HANDLING PERMANENT OVERLOADS
9.4.1 JOB SKIPPING
SCHEDULABILITY ANALYSIS
Sufficient condition
Necessary condition
EXAMPLE
SKIPS AND BANDWIDTH SAVING
EXAMPLE
9.4.2 PERIOD ADAPTATION
EXAMPLES
THE ELASTIC MODEL
SPRINGS WITH NO LENGTH CONSTRAINTS
INTRODUCING LENGTH CONSTRAINTS
COMPRESSING TASKS’ UTILIZATIONS
DECOMPRESSION
9.4.3 IMPLEMENTATION ISSUES
PERIOD RESCALING
CONCLUDING REMARKS
9.4.4 SERVICE ADAPTATION
Exercises
fulltext(9)
10 KERNEL DESIGN ISSUES
10.1 STRUCTURE OF A REAL-TIME KERNEL
10.2 PROCESS STATES
10.3 DATA STRUCTURES
10.4 MISCELLANEOUS
10.4.1 TIME MANAGEMENT
10.4.2 TASK CLASSES AND SCHEDULING ALGORITHM
10.4.3 GLOBAL CONSTANTS
10.4.4 INITIALIZATION
10.5 KERNEL PRIMITIVES
10.5.1 LOW-LEVEL PRIMITIVES
10.5.2 LIST MANAGEMENT
10.5.3 SCHEDULING MECHANISM
10.5.4 TASK MANAGEMENT
10.5.5 SEMAPHORES
10.5.6 STATUS INQUIRY
10.6 INTERTASK COMMUNICATION MECHANISMS
10.6.1 CYCLIC ASYNCHRONOUS BUFFERS
10.6.2 CAB IMPLEMENTATION
10.7 SYSTEM OVERHEAD
10.7.1 ACCOUNTING FOR INTERRUPT
fulltext(10)
11 APPLICATION DESIGN ISSUES
11.1 INTRODUCTION
11.2 TIME CONSTRAINTS DEFINITION
11.2.1 OBSTACLE AVOIDANCE
11.2.2 ROBOT DEBURRING
11.2.3 MULTILEVEL FEEDBACK CONTROL
11.3 HIERARCHICAL DESIGN
11.3.1 EXAMPLES OF REAL-TIME ROBOTICS APPLICATIONS
ASSEMBLY: PEG-IN-HOLE INSERTION
SURFACE CLEANING
OBJECT TACTILE EXPLORATION
CATCHING MOVING OBJECTS
11.4 A ROBOT CONTROL EXAMPLE
fulltext(11)
12 REAL-TIME OPERATING SYSTEMS AND STANDARDS
12.1 STANDARDS FOR REAL-TIME OPERATING SYSTEMS
12.1.1 RT-POSIX
12.1.2 OSEK/VDX
DETAILS ON THE OSEK/VDX STANDARD
AUTOSAR OS
12.1.3 ARINC - APEX
12.1.4 MICRO-ITRON
12.2 COMMERCIAL REAL-TIME SYSTEMS
12.2.1 VXWORKS
12.2.2 OSE
12.2.3 QNX NEUTRINO
12.3 LINUX RELATED REAL-TIME KERNELS
12.3.1 RTLINUX
12.3.2 RTAI
12.3.3 XENOMAI
12.3.4 PREEMPT RT
12.3.5 SCHED DEADLINE
12.3.6 LINUX/RK
12.4 OPEN-SOURCE REAL-TIME RESEARCH KERNELS
12.4.1 ERIKA ENTERPRISE
EFFICIENT EDF IMPLEMENTATION
MULTICORE SUPPORT
12.4.2 SHARK
KERNEL ARCHITECTURE
SCHEDULING MODULES
SHARED RESOURCE ACCESS PROTOCOLS
DEVICE MANAGEMENT
12.4.3 MARTE OS
SUPPORTED FUNCTIONALITY
APPLICATION-DEFINED SCHEDULING
INTERRUPT MANAGEMENT AT APPLICATION LEVEL
DRIVERS FRAMEWORK
ADA SUPPORT
12.5 DEVELOPMENT TOOLS
12.5.1 TIMING ANALYSIS TOOLS
12.5.2 SCHEDULABILITY ANALYSIS
12.5.3 SCHEDULING SIMULATORS
fulltext(12)
13 SOLUTIONS TO THE EXERCISES
SOLUTIONS FOR CHAPTER 1
SOLUTIONS FOR CHAPTER 2
SOLUTIONS FOR CHAPTER 3
SOLUTIONS FOR CHAPTER 4
SOLUTIONS FOR CHAPTER 5
SOLUTIONS FOR CHAPTER 6
SOLUTIONS FOR CHAPTER 7
SOLUTIONS FOR CHAPTER 8
SOLUTIONS FOR CHAPTER 9
back-matter
GLOSSARY
REFERENCES
INDEX
Hard Real-Time Computing Systems
Real-Time Systems Series
Series Editor
John A. Stankovic
University of Virginia, Virginia, USA
For further volumes:
http://www.springer.com/series/6941
Giorgio C. Buttazzo
Hard Real-Time Computing
Systems
Predictable Scheduling Algorithms
and Applications
Third Edition
Giorgio C. Buttazzo
RETIS Lab
Scuola Superiore San Anna
Pisa
Italy
g.buttazzo
ssup.it
@s
t’
N 978-1-4614-0675-4
ISSN 1867-321X
ISB
DOI 10.1007/978-1-4614-0676-1
Springer New York Dordrecht Heidelberg London
e-ISSN 1867-3228
e-ISBN 978-1-4614-0676-1
Library of Congress Control Number: 2011937234
© Springer Science+Business Media, LLC 2011
All rights reserved. This work may not be translated or copied in whole or in part without the written
permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York,
NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in
connection with any form of information storage and retrieval, electronic adaptation, computer software,
or by similar or dissimilar methodology now known or hereafter developed is forbidden.
The use in this publication of trade names, trademarks, service marks, and similar terms, even if they
are not identified as such, is not to be taken as an expression of opinion as to whether or not they are
subject to proprietary rights.
Printed on acid- free paper
Springer is part of Springer Science+Business Media (www.springer.com)
Preface
1
2
3
4
Introduction
A GENERAL VIEW
1.1
1.2 What does real time mean?
1.3 Achieving predictability
Introduction
BASIC CONCEPTS
2.1
2.2 Types of task constraints
2.3 Definition of scheduling problems
2.4
Scheduling anomalies
Introduction
Jackson’s algorithm
APERIODIC TASK SCHEDULING
3.1
3.2
3.3 Horn’s algorithm
3.4 Non-preemptive scheduling
3.5
3.6
Scheduling with precedence constraints
Summary
Introduction
PERIODIC TASK SCHEDULING
4.1
4.2 Timeline scheduling
4.3 Rate Monotonic scheduling
4.4 Earliest Deadline First
4.5 Deadline Monotonic
4.6 EDF with constrained deadlines
4.7 Comparison between RM and EDF
CONTENTS
ix
1
1
4
13
23
23
25
34
42
53
53
54
58
63
70
76
79
79
84
86
100
103
110
116
v
vi
5
6
7
Introduction
Polling Server
FIXED-PRIORITY SERVERS
5.1
5.2 Background scheduling
5.3
5.4 Deferrable Server
Priority Exchange
5.5
Sporadic Server
5.6
5.7
Slack stealing
5.8 Non-existence of optimal servers
5.9
5.10 Summary
Performance evaluation
Introduction
DYNAMIC PRIORITY SERVERS
6.1
6.2 Dynamic Priority Exchange Server
6.3 Dynamic Sporadic Server
6.4 Total Bandwidth Server
6.5 Earliest Deadline Late Server
6.6
6.7
6.8
6.9 The Constant Bandwidth Server
6.10 Summary
Improved Priority Exchange Server
Improving TBS
Performance evaluation
Introduction
RESOURCE ACCESS PROTOCOLS
7.1
7.2 The priority inversion phenomenon
7.3 Terminology and assumptions
7.4 Non-Preemptive Protocol
7.5 Highest Locker Priority Protocol
7.6
7.7
7.8
7.9
7.10 Summary
Priority Inheritance Protocol
Priority Ceiling Protocol
Stack Resource Policy
Schedulability analysis
Contents
119
119
120
121
130
139
143
149
153
155
157
161
161
162
167
171
174
178
181
185
189
201
205
205
206
209
210
212
214
226
234
246
247
Contents
8
Introduction
LIMITED PREEMPTIVE SCHEDULING
8.1
8.2 Non-preemptive scheduling
8.3
Preemption thresholds
8.4 Deferred Preemptions
8.5 Task splitting
8.6
8.7 Assessment of the approaches
Selecting preemption points
9 HANDLING OVERLOAD CONDITIONS
Introduction
9.1
9.2 Handling aperiodic overloads
9.3 Handling overruns
9.4 Handling permanent overloads
10 KERNEL DESIGN ISSUES
10.1 Structure of a real-time kernel
10.2 Process states
10.3 Data structures
10.4 Miscellaneous
10.5 Kernel primitives
10.6 Intertask communication mechanisms
10.7 System overhead
11 APPLICATION DESIGN ISSUES
11.1 Introduction
11.2 Time constraints definition
11.3 Hierarchical design
11.4 A robot control example
12 REAL-TIME OPERATING SYSTEMS AND
STANDARDS
12.1 Standards for real-time operating systems
12.2 Commercial real-time systems
12.3 Linux related real-time kernels
12.4 Open-source real-time research kernels
12.5 Development Tools
vii
251
251
257
261
266
270
274
279
287
287
293
316
326
349
349
351
356
361
366
385
392
397
398
401
408
413
419
419
428
432
437
452
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
