Table of Contents	8
	Preface	12
	Chapter 1 The Real-Time Environment	16
	OVERVIEW	16
	1.1 WHEN IS A COMPUTER SYSTEM REAL-TIME?	17
	1.2 FUNCTIONAL REQUIREMENTS	18
	1.2.1 Data Collection	18
	1.2.2 Direct Digital Control	20
	1.2.3 Man-Machine Interaction	20
	1.3 TEMPORAL REQUIREMENTS	21
	1.3.1 Where Do Temporal Requirements Come From?	21
	1.3.2 Minimal Latency Jitter	24
	1.3.3 Minimal Error-Detection Latency	24
	1.4 DEPENDABILITY REQUIREMENTS	24
	1.4.1 Reliability	24
	1.4.2 Safety	25
	1.4.3 Maintainability	26
	1.4.4 Availability	26
	1.4.5 Security	27
	1.5 CLASSIFICATION OF REAL-TIME SYSTEMS	27
	1.5.1 Hard Real-Time System versus Soft Real-Time System	27
	1.5.2 Fail-safe versus Fail-Operational	29
	1.5.3 Guaranteed-Response versus Best-Effort	29
	1.5.4 Resource-Adequate versus Resource-Inadequate	30
	1.5.5 Event-Triggered versus Time-Triggered	30
	1.6 THE REAL-TIME SYSTEMS MARKET	31
	1.6.1 Embedded Real-Time Systems	31
	1.6.2 Plant Automation Systems	34
	1.6.3 Multimedia Systems	36
	1.7 EXAMPLES OF REAL-TIME SYSTEMS	36
	1.7.1 Controlling the Flow in a Pipe	36
	1.7.2 Engine Control	37
	1.7.3 Rolling Mill	38
	POINTS TO REMEMBER	39
	BIBLIOGRAPHIC NOTES	41
	REVIEW QUESTIONS AND PROBLEMS	41
	Chapter 2 Why a Distributed Solution?	44
	OVERVIEW	44
	2.1 SYSTEM ARCHITECTURE	45
	2.1.1 Form Follows Function	45
	2.1.2 Hardware Structure	46
	2.1.3 The Communication-Network Interface	46
	2.1.4 The Communication System	48
	2.1.5 Gateways	48
	2.2 COMPOSABILITY	49
	2.2.1 Definition	49
	2.2.2 Event-Triggered Communication Systems	50
	2.2.3 Time-Triggered Communication Systems	51
	2.3 SCALABILITY	51
	2.3.1 Extensibility	51
	2.3.2 Complexity	52
	2.3.3 Silicon Cost	53
	2.4 DEPENDABILITY	54
	2.4.1 Error-Containment Regions	54
	2.4.2 Replication	55
	2.4.3 Certification Support	55
	2.5 PHYSICAL INSTALLATION	57
	POINTS TO REMEMBER	57
	BIBLIOGRAPHIC NOTES	59
	REVIEW QUESTIONS AND PROBLEMS	59
	Chapter 3 Global Time	60
	OVERVIEW	60
	3.1 TIME AND ORDER	61
	3.1.1 Different Orders	61
	3.1.2 Clocks	62
	3.1.3 Precision and Accuracy	64
	3.1.4 Time Standards	65
	3.2 TIME MEASUREMENT	66
	3.2.1 Global Time	67
	3.2.2 Interval Measurement	68
	3.2.3 ?/. -Precendence	69
	3.2.4 Fundamental Limits of Time Measurement	70
	3.3 DENSE TIME VERSUS SPARSE TIME	70
	3.3.1 Dense Time-base	71
	3.3.2 Sparse Time-Base	72
	3.3.3 Space-Time Lattice	73
	3.4 INTERNAL CLOCK SYNCHRONIZATION	74
	3.4.1 The Synchronization Condition	74
	3.4.2 Central Master Synchronization	75
	3.4.3 Distributed Synchronization Algorithms	76
	3.4.4 State Correction versus Rate Correction	79
	3.5 EXTERNAL CLOCK SYNCHRONIZATION	80
	3.5.1 Principle of Operation	80
	3.5.2 Time Formats	81
	3.5.3 Time Gateway	81
	POINTS TO REMEMBER	82
	BIBLIOGRAPHIC NOTES	83
	REVIEW QUESTIONS AND PROBLEMS	84
	Chapter 4 Modeling Real-Time Systems	86
	OVERVIEW	86
	4.1 APPROPRIATE ABSTRACTIONS	87
	4.1.1 The Purpose of the Model	87
	4.1.2 What is Relevant?	88
	4.1.3 What Is Irrelevant?	89
	4.2 THE STRUCTURAL ELEMENTS	90
	4.2.1 Task	90
	4.2.2 Node	90
	4.2.3 Fault-Tolerant Unit (FTU)	91
	4.2.4 Computational Cluster	92
	4.3 INTERFACES	92
	4.3.1 World and Message Interfaces	93
	4.3.2 Temporal Obligation of Clients and Servers	95
	4.4 TEMPORAL CONTROL VERSUS LOGICAL CONTROL	97
	4.4.1 The Rolling Mill Example Revisited	97
	4.4.2 Event-Triggered versus Time-Triggered	98
	4.4.3 Interrupts	99
	4.4.4 Trigger Task	100
	4.5 WORST-CASE EXECUTION TIME	101
	4.5.1 WCET of S-Tasks	101
	4.5.2 Preemptive S-Tasks	104
	4.5.3 WCET of Complex Tasks	104
	4.5.4 State of Practice	105
	4.6 THE HISTORY STATE (H-STATE)	106
	4.6.1 The Pocket Calculator Example	106
	4.6.2 Ground State	107
	POINTS TO REMEMBER	108
	BIBLIOGRAPHIC NOTES	109
	REVIEW QUESTIONS AND PROBLEMS	110
	Chapter 5 Real-Time Entities and Images	112
	OVERVIEW	112
	5.1 REAL-TIME ENTITIES	113
	5.1.1 Sphere of Control	113
	5.1.2 Discrete and Continuous Real-Time Entities	114
	5.2 OBSERVATIONS	114
	5.2.1 Untimed Observation	115
	5.2.2 Indirect Observation	115
	5.2.3 State Observation	115
	5.2.4 Event Observation	116
	5.3 REAL-TIME IMAGES AND REAL-TIME OBJECTS	116
	5.3.1 Real-Time Images	116
	5.3.2 Real-Time Objects	117
	5.4 TEMPORAL ACCURACY	117
	5.4.1 Definition	118
	5.4.2 Classification of Real-Time Images	120
	5.4.3 State Estimation	121
	5.4.4 Composability Considerations	122
	5.5 PERMANENCE AND IDEMPOTENCY	123
	5.5.1 Permanence	123
	5.5.2 Duration of the Action Delay	125
	5.5.3 Accuracy Interval versus Action Delay	125
	5.5.4 Idempotency	125
	5.6 REPLICA DETERMINISM	126
	5.6.1 Major Decision Point	127
	5.6.2 Basic Causes of Replica Non-determinism	128
	5.6.3 Building a Replica Determinate System	129
	5.6.4 Leader-Follower Protocol	131
	POINTS TO REMEMBER	131
	BIBLIOGRAPHIC NOTES	133
	REVIEW QUESTIONS AND PROBLEMS	133
	Chapter 6 Fault Tolerance	134
	OVERVIEW	134
	6.1 FAILURES, ERRORS, AND FAULTS	135
	6.1.1 Failures	135
	6.1.2 Errors	137
	6.1.3 Faults	139
	6.1.4 Systematic versus Application-Specific Fault Tolerance	140
	6.2 ERROR DETECTION	141
	6.2.1 Error Detection Based on A priori Knowledge	141
	6.2.2 Error Detection Based on Redundant Computations	143
	6.2.3 Duplicate Execution of Tasks	143
	6.3 A NODE AS A UNIT OF FAILURE	144
	6.3.1 Minimum Service Level of a Node	144
	6.3.2 Error Detection within a Node	145
	6.3.3 Exception Handling	145
	6.4 FAULT-TOLERANT UNITS	146
	6.4.1 Fail-Silent Nodes	146
	6.4.2 Triple-Modular Redundancy	147
	6.4.3 Byzantine Resilient Fault-Tolerant Unit	148
	6.4.4 The Membership Service	148
	6.5 REINTEGRATION OF A REPAIRED NODE	150
	6.5.1 Finding a Reintegration Point	150
	6.5.2 Minimizing the H-State	150
	6.5.3 Node Restart	152
	6.6 DESIGN DIVERSITY	152
	6.6.1 Diverse Software Versions	153
	6.6.2 An Example of A Fail-safe System	154
	6.6.3 Multilevel System	155
	POINTS TO REMEMBER	155
	BIBLIOGRAPHIC NOTES	157
	REVIEW QUESTIONS AND PROBLEMS	158
	Chapter 7 Real-Time Communication	160
	OVERVIEW	160
	7.1 REAL-TIME COMMUNICATION REQUIREMENTS	161
	7.1.1 Protocol Latency	161
	7.1.2 Support for Composability	161
	7.1.3 Flexibility	162
	7.1.4 Error Detection	162
	7.1.5 Physical Structure	163
	7.2 FLOW CONTROL	164
	7.2.1 Explicit Flow Control	164
	7.2.2 Implicit Flow Control	166
	7.2.3 Thrashing	166
	7.2.4 Flow Control in Real-Time Systems	168
	7.3 OSI PROTOCOLS FOR REAL-TIME?	169
	7.3.1 The OSI Reference Model	169
	7.3.2 Asynchronous Transfer Mode (ATM) and Real Time	170
	7.3.3 Real-Time Communication Architecture	170
	7.4 FUNDAMENTAL CONFLICTS IN PROTOCOL DESIGN	172
	7.4.1 External Control versus Composability	172
	7.4.2 Flexibility versus Error Detection	173
	7.4.3 Sporadic Data versus Periodic Data	173
	7.4.4 Single Locus of Control versus Fault Tolerance	174
	7.4.5 Probabilistic Access versus Replica Determinism	174
	7.5 MEDIA-ACCESS PROTOCOLS	174
	7.5.1 Characteristics of a Communication Channel	174
	7.5.2 CSMA/CD–LON	175
	7.5.3 CSMA/CA–CAN	176
	7.5.4 Token Bus–Profibus	176
	7.5.5 Minislotting-ARINC 629	177
	7.5.6 Central Master–FIP	178
	7.5.7 TDMA–TTP	178
	7.5.8 Comparison of the Protocols	178
	7.6 PERFORMANCE COMPARISON: ET VERSUS TT	179
	7.6.1 Problem Specification	180
	7.6.2 ET and TT Solutions	180
	7.6.3 Comparison of the Solutions	181
	7.7 THE PHYSICAL LAYER	181
	7.7.1 Properties of Transmission Codes	181
	7.7.2 Examples of Transmission Codes	182
	7.7.3 Signal Shape	183
	POINTS TO REMEMBER	183
	BIBLIOGRAPHIC NOTE S	184
	REVIEW QUESTIONS AND PROBLEMS	185
	Chapter 8 The Time-Triggered Protocols	186
	OVERVIEW	186
	8.1 INTRODUCTION TO TIME-TRIGGERED PROTOCOLS	187
	8.1.1 Protocol Objectives	187
	8.1.2 Structure of a TTP System	187
	8.1.3 Design Rationale	188
	8.1.4 Protocol Variants	190
	8.2 OVERVIEW OF THE TTP/C PROTOCOL LAYERS	190
	8.2.1 Data Link/Physical Layer	191
	8.2.2 SRU Layer	191
	8.2.3 Redundancy Management Layer (RM Layer)	192
	8.2.4 FTU Layer	192
	8.3 THE BASIC CNI	193
	8.3.1 Structure of the CNI	193
	8.3.2 Status/Control Area	194
	8.3.3 Message Area	195
	8.3.4 Consistent Data Transfer	195
	8.4 INTERNAL OPERATION OF TTP/C	196
	8.4.1 The Message Descriptor List (MEDL)	196
	8.4.2 Frame Format	198
	8.4.3 CRC Calculation	198
	8.4.4 The Membership Service	199
	8.4.5 Clock Synchronization	200
	8.5 TTP/A FORFIELD BUS APPLICATIONS	200
	8.5.1 Principles of Operation	200
	8.5.2 Error Detection and Error Handling	202
	8.5.3 Response Time of a TTP/A System	202
	POINTS TO REMEMBER	203
	BIBLIOGRAPHIC NOTES	205
	REVIEW QUESTIONS AND PROBLEMS	205
	Chapter 9 Input/Output	208
	OVERVIEW	208
	9.1 THE DUAL ROLE OF TIME	209
	9.1.1 Time as Data	209
	9.1.2 Time as Control	210
	9.2 AGREEMENT PROTOCOLS	211
	9.2.1 Raw Data, Measured Data, and Agreed Data	211
	9.2.2 Syntactic Agreement	211
	9.2.3 Semantic Agreement	212
	9.3 SAMPLING AND POLLING	213
	9.3.1 Sampling of Analog Values	213
	9.3.2 Sampling of Digital Values	213
	9.3.3 Polling	215
	9.4 INTERRUPTS	216
	9.4.1 When Are Interrupts Needed?	216
	9.4.2 Monitoring the Occurrence of an Interrupt	217
	9.5 SENSORS AND ACTUATORS	218
	9.5.1 Analog Input/Output	218
	9.5.2 Digital Input/Output	219
	9.5.3 Fault-Tolerant Actuators	220
	9.5.4 Intelligent Instrumentation	221
	9.6 PHYSICAL INSTALLATION	222
	POINTS TO REMEMBER	223
	BIBLIOGRAPHIC NOTES	224
	REVIEW QUESTIONS AND PROBLEMS	224
	Chapter 10 Real-Time Operating Systems	226
	OVERVIEW	226
	10.1 TASK MANAGEMENT	227
	10.1.1 TT Systems	227
	10.1.2 ET Systems with S-Tasks	228
	10.1.3 ET Systems with C-Tasks	230
	10.1.4 Software Portability	230
	10.2 INTERPROCESS COMMUNICATION	231
	10.2.1 Semaphore Operations	231
	10.2.2 The Non-Blocking Write (NBW) Protocol	232
	10.3 TIMEMANAGEMENT	233
	10.3.1 Clock Synchronization	233
	10.3.2 Provision of Time Services	234
	10.3.3 Support for Time Stamping	234
	10.4 ERROR DETECTION	234
	10.4.1 Monitoring Task Execution Times	234
	10.4.2 Monitoring Interrupts	235
	10.4.3 Double Execution of Tasks	235
	10.4.4 Watchdogs	235
	10.5 A CASE STUDY: ERCOS	236
	10.5.1 Task Model	236
	10.5.2 Scheduling	236
	10.5.3 Interprocess Communication	237
	10.5.4 Error Detection	237
	10.5.5 Off-line Software Tools	237
	POINTS TO REMEMBER	238
	BIBLIOGRAPHIC NOTES	239
	REVIEW QUESTIONS AND PROBLEMS	239
	Chapter 11 Real-Time Scheduling	242
	OVERVIEW	242
	11.1 THE SCHEDULING PROBLEM	243
	11.1.1 Classification of Scheduling Algorithms	243
	11.1.2 Schedulability Test	244
	11.2 THE ADVERSARY ARGUMENT	244
	11.3 DYNAMIC SCHEDULING	246
	11.3.1 Scheduling Independent Tasks	246
	11.3.2 Scheduling Dependent Tasks	248
	11.3.3 The Priority Ceiling Protocol	249
	11.3.4 Dynamic Scheduling in Distributed Systems	251
	11.4 STATIC SCHEDULING	252
	11.4.1 Static Scheduling Viewed as a Search	252
	11.4.2 Increasing the Flexibility in Static Schedules	254
	POINTS TO REMEMBER	255
	BIBLIOGRAPHIC NOTES	257
	REVIEW QUESTIONS AND PROBLEMS	257
	Chapter 12 Validation	260
	OVERVIEW	260
	12.1 BUILDING A CONVINCING SAFETY CASE	261
	12.1.1 Outline of the Safety Case	261
	12.1.2 Properties of the Architecture	262
	12.2 FORMAL METHODS	263
	12.2.1 Formal Methods in the Real World	263
	12.2.2 Classification of Formal Methods	264
	12.2.3 Benefits from the Application of Formal Methods	264
	12.3 TESTING	265
	12.3.1 The Probe Effect	266
	12.3.2 Design for Testability	267
	12.3.3 Test Data Selection	267
	12.3.4 What can be Inferred from "Perfect Working"?	268
	12.4 FAULT INJECTION	268
	12.4.1 Why Fault Injection?	268
	12.4.2 Physical Fault Injection	269
	12.4.3 Software-Implemented Fault Injection	272
	12.5 DEPENDABILITY ANALYSIS	273
	12.5.1 Fault Tree Analysis	274
	12.5.2 Failure Mode and Effect Analysis (FMEA)	275
	12.5.3 Software Reliability Growth	275
	POINTS TO REMEMBER	276
	BIBLIOGRAPHIC NOTES	277
	REVIEW QUESTIONS AND PROBLEMS	277
	Chapter 13 System Design	280
	OVERVIEW	280
	13.1 THE DESIGN PROBLEM	281
	13.1.1 Complexity	281
	13.1.2 Grand Design versus Incremental Development	282
	13.1.3 Legacy Systems	283
	13.1.4 Design Problems are Wicked	283
	13.2 REQUIREMENTS ANALYSIS	284
	13.2.1 Developing Project Standards	284
	13.2.2 Essential System Functions	285
	13.2.3 Exploring the Constraints	286
	13.3 DECOMPOSITION OF A SYSTEM INTO SUBSYSTEMS	287
	13.3.1 Identification of the Subsystems	287
	13.3.2 The Communication Network Interface	288
	13.3.3 Result of the Architecture Design Phase	289
	13.4 TEST OF A DECOMPOSITION	290
	13.4.1 Functional Coherence	290
	13.4.2 Testability	291
	13.4.3 Dependability	291
	13.4.4 Physical Characteristics	292
	13.5 DETAILED DESIGN AND IMPLEMENTATION	292
	13.5.1 Definition of the I/O Interfaces	292
	13.5.2 Task Development	292
	13.5.3 Task Scheduling	293
	13.6 REAL-TIME ARCHITECTURE PROJECTS	293
	13.6.1 SPRING	294
	13.6.2 MAFT	295
	13.6.3 FTPP	296
	POINTS TO REMEMBER	297
	BIBLIOGRAPHIC NOTES	298
	REVIEW QUESTIONS AND PROBLEMS	298
	Chapter 14 The Time-Triggered Architecture	300
	OVERVIEW	300
	14.1 LESSONS LEARNED FROM THE MARS PROJECT	301
	14.1.1 The MARS Project	301
	14.1.2 The High Error Detection Coverage Mode (HEDC)	302
	14.2 THE TIME-TRIGGERED ARCHITECTURE	303
	14.2.1 Economy of Concepts	303
	14.2.2 The Real-Time Database	304
	14.2.3 The Hardware Building Blocks	305
	14.3 SOFTWARE SUPPORT	307
	14.3.1 Operating System	307
	14.3.2 The Cluster Compiler	308
	14.3.3 Testing	309
	14.4 FAULT TOLERANCE	309
	14.4.1 Fault-Tolerant Units	309
	14.4.2 Redundant Sensors	309
	14.5 WIDE-AREA REAL-TIME SYSTEMS	310
	14.5.1 The Emergence of ATM Technology	310
	14.5.2 An ATM Gateway	310
	POINTS TO REMEMBER	311
	BIBLIOGRAPHIC NOTES	312
	List of Abbreviations	314
	Glossary	316
	References	332
	Index	344
	More eBooks at www.ciando.com	0