Jiacun Wang
Real-Time Embedded Systems
Jiacun Wang
Real-Time Embedded Systems
- Gebundenes Buch
- Merkliste
- Auf die Merkliste
- Bewerten Bewerten
- Teilen
- Produkt teilen
- Produkterinnerung
- Produkterinnerung
This comprehensive book not only covers the fundamentals of real-time embedded systems such as hardware components, real-time operating systems, real-time programming, embedded memory and real-time resource management, but also modeling, real-time constraints verification approaches and practical issues like software rejuvenation and reliability. It's an important text for industrial practitioners with real-time and embedded software design, development, and management responsibilities and students and faculty involved in embedded and real-time software systems.
Andere Kunden interessierten sich auch für
- Krzysztof IniewskiEmbedded Systems180,99 €
- Eddie C. L. ChanIntroduction to Wireless Localization138,99 €
- James McDonaldManaging the Development of Software-Intensive Systems118,99 €
- Erdal CayirciComputer Assisted Exercises and Training162,99 €
- James J. NutaroBuilding Software for Simulation155,99 €
- J. C. HuangSoftware Error Detection Through Testing and Analysis128,99 €
- Francine KriefCommunicating Embedded Systems184,99 €
-
-
-
This comprehensive book not only covers the fundamentals of real-time embedded systems such as hardware components, real-time operating systems, real-time programming, embedded memory and real-time resource management, but also modeling, real-time constraints verification approaches and practical issues like software rejuvenation and reliability. It's an important text for industrial practitioners with real-time and embedded software design, development, and management responsibilities and students and faculty involved in embedded and real-time software systems.
Produktdetails
- Produktdetails
- Quantitative Software Engineering Series
- Verlag: Wiley & Sons
- 1. Auflage
- Seitenzahl: 336
- Erscheinungstermin: 14. August 2017
- Englisch
- Abmessung: 232mm x 156mm x 24mm
- Gewicht: 612g
- ISBN-13: 9781118116173
- ISBN-10: 1118116178
- Artikelnr.: 36625887
- Quantitative Software Engineering Series
- Verlag: Wiley & Sons
- 1. Auflage
- Seitenzahl: 336
- Erscheinungstermin: 14. August 2017
- Englisch
- Abmessung: 232mm x 156mm x 24mm
- Gewicht: 612g
- ISBN-13: 9781118116173
- ISBN-10: 1118116178
- Artikelnr.: 36625887
Jiacun Wang Ph.D. is a Professor of Software Engineering at Monmouth University, NJ, USA. He is a former member of the scientific staff at Nortel Networks where he worked on embedded software for mobility management of 3G telecommunication systems. He is the author of Timed Petri Nets: Theory and Application (Kluwer 1998) and editor of Handbook of Finite State Based Models and Applications (CRC 2012). He is a senior member of IEEE.
Preface xiii Book Layout xv Acknowledgments xvii 1 Introduction to
Real-Time Embedded Systems 1 1.1 Real-Time Embedded Systems 1 1.2 Example:
Automobile Antilock Braking System 3 1.2.1 Slip Rate and Brake Force 3
1.2.2 ABS Components 4 1.2.2.1 Sensors 4 1.2.2.2 Valves and Pumps 5 1.2.2.3
Electrical Control Unit 7 1.2.3 ABS Control 8 1.3 Real-Time Embedded System
Characteristics 10 1.3.1 System Structure 10 1.3.2 Real-Time Response 10
1.3.3 Highly Constrained Environments 11 1.3.4 Concurrency 12 1.3.5
Predictability 12 1.3.6 Safety and Reliability 13 1.4 Hard and Soft
Real-Time Embedded Systems 13 Exercises 14 Suggestions for Reading 15
References 15 2 Hardware Components 17 2.1 Processors 17 2.1.1
Microprocessors 17 2.1.2 Microcontrollers 19 2.1.3 Application-Specific
Integrated Circuits (ASICs) 19 2.1.4 Field-Programmable Gate Arrays (FPGAs)
19 2.1.5 Digital Signal Processors (DSPs) 20 2.1.6 Application-Specific
Instruction Set Processors (ASIPs) 20 2.1.7 Multicore Processors 20 2.1.8
Von Neumann Architecture and Harvard Architecture 21 2.1.9 Complex
Instruction Set Computing and Reduced Instruction Set Computing 22 2.2
Memory and Cache 23 2.2.1 Read-Only Memory (ROM) 23 2.2.2 Random-Access
Memory (RAM) 24 2.2.3 Cache Memory 24 2.3 I/O Interfaces 26 2.4 Sensors and
Actuators 27 2.5 Timers and Counters 29 Exercises 30 Suggestions for
Reading 31 References 31 3 Real-Time Operating Systems 33 3.1 Main
Functions of General-Purpose Operating Systems 33 3.1.1 Process Management
34 3.1.2 Memory Management 36 3.1.3 Interrupts Management 39 3.1.4
Multitasking 39 3.1.5 File System Management 39 3.1.6 I/O Management 41 3.2
Characteristics of RTOS Kernels 42 3.2.1 Clocks and Timers 42 3.2.2
Priority Scheduling 44 3.2.3 Intertask Communication and Resource Sharing
45 3.2.3.1 Real-Time Signals 45 3.2.3.2 Semaphores 46 3.2.3.3 Message
Passing 46 3.2.3.4 Shared Memory 46 3.2.4 Asynchronous I/O 47 3.2.5 Memory
Locking 47 3.3 RTOS Examples 48 3.3.1 LynxOS 48 3.3.2 OSE 49 3.3.3 QNX 49
3.3.4 VxWorks 49 3.3.5 Windows Embedded Compact 50 Exercises 50 Suggestions
for Reading 52 References 52 4 Task Scheduling 53 4.1 Tasks 53 4.1.1 Task
Specification 54 4.1.2 Task States 56 4.1.3 Precedence Constraints 58 4.1.4
Task Assignment and Scheduling 59 4.2 Clock-Driven Scheduling 59 4.2.1
Structured Clock-Driven Scheduling 62 4.2.1.1 Frames 62 4.2.1.2 Task
Slicing 65 4.2.2 Scheduling Aperiodic Tasks 66 4.2.3 Scheduling Sporadic
Tasks 68 4.3 Round-Robin Approach 69 4.4 Priority-Driven Scheduling
Algorithms 70 4.4.1 Fixed-Priority Algorithms 70 4.4.1.1 Schedulability
Test Based on Time Demand Analysis 72 4.4.1.2 Deadline-Monotonic Algorithm
76 4.4.2 Dynamic-Priority Algorithms 76 4.4.2.1 Earliest-Deadline-First
(EDF) Algorithm 76 4.4.2.2 Optimality of EDF 78 4.4.3 Priority-Driven
Scheduling of Aperiodic and Sporadic Tasks 82 4.4.3.1 Scheduling of
Aperiodic Tasks 82 4.4.3.2 Scheduling of Sporadic Tasks 85 4.4.4 Practical
Factors 85 4.4.4.1 Nonpreemptivity 85 4.4.4.2 Self-Suspension 86 4.4.4.3
Context Switches 87 4.4.4.4 Schedulability Test 87 4.5 Task Assignment 89
4.5.1 Bin-Packing Algorithms 89 4.5.1.1 First-Fit Algorithm 90 4.5.1.2
First-Fit Decreasing Algorithm 91 4.5.1.3 Rate-Monotonic First-Fit (RMFF)
Algorithm 91 4.5.2 Assignment with Communication Cost 92 Exercises 94
Suggestions for Reading 97 References 97 5 Resource Sharing and Access
Control 99 5.1 Resource Sharing 99 5.1.1 Resource Operation 100 5.1.2
Resource Requirement Specification 100 5.1.3 Priority Inversion and
Deadlocks 101 5.1.4 Resource Access Control 103 5.2 Nonpreemptive Critical
Section Protocol 103 5.3 Priority Inheritance Protocol 106 5.3.1 Rules of
Priority Inheritance Protocol 106 5.3.2 Properties of Priority Inheritance
Protocol 109 5.4 Priority Ceiling Protocol 111 5.4.1 Rules of Priority
Ceiling Protocol 112 5.4.2 Properties of Priority Ceiling Protocol 114
5.4.3 Worst-Case Blocking Time 116 5.5 Stack-Sharing Priority Ceiling
Protocol 119 5.5.1 Rules of Stack-Sharing Priority Ceiling Protocol 119
5.5.2 Properties of Stack-Sharing Priority Ceiling Protocol 121 Exercises
122 Suggestion for Reading 125 References 125 6 Concurrent Programming 127
6.1 Introduction 127 6.2 POSIX Threads 128 6.3 Synchronization Primitives
133 6.3.1 Race Conditions and Critical Sections 133 6.3.2 Mutex 134 6.3.3
Condition Variables 137 6.3.4 Semaphores 142 6.4 Communication among Tasks
148 6.4.1 Message Queues 149 6.4.2 Shared Memory 155 6.4.3 Shared Memory
Protection 157 6.5 Real-Time Facilities 162 6.5.1 Real-Time Signals 162
6.5.1.1 Blocking Signals 163 6.5.1.2 Dealing with Signals 164 6.5.2 Timers
165 6.5.3 Implement Periodic Tasks 169 6.5.3.1 Using sleep() Function 169
6.5.3.2 Using Timers 172 6.5.4 Implement an Application with Multiple
Periodic Tasks 173 Exercises 173 Suggestions for Reading 177 References 177
7 Finite-State Machines 179 7.1 Finite State Machine Basics 179 7.2
Deterministic Finite Automation (DFA) 181 7.2.1 Moore Machines 182 7.2.2
Mealy Machines 184 7.3 Nondeterministic Finite Automation 188 7.4
Programming Finite-State Machines 188 Exercises 191 Suggestions for Reading
194 References 195 8 UML State Machines 197 8.1 States 198 8.2 Transitions
200 8.3 Events 201 8.4 Composite States 202 8.4.1 Hierarchy 203 8.4.2
Orthogonality 205 8.4.3 Submachine States 206 8.5 Pseudostates 206 8.5.1
History Pseudostates 206 8.5.2 Entry and Exit Points 208 8.5.3 Fork and
Join Pseudostates 210 8.5.4 Terminate Pseudostates 210 8.6 UML State
Machine of Antilock Braking System 211 Exercises 215 Suggestions for
Reading 217 References 217 9 Timed Petri Nets 219 9.1 Petri Net Definition
219 9.1.1 Transition Firing 221 9.1.2 Modeling Power 222 9.2 Petri Net
Properties 225 9.2.1 Behavioral Properties 225 9.2.1.1 Reachability 225
9.2.1.2 omega Markings 226 9.2.1.3 Reachability Analysis Algorithm 227
9.2.1.4 Boundedness and Safeness 229 9.2.1.5 Liveness 229 9.2.2 Structural
Properties 230 9.2.2.1 T-Invariants and S-Invariants 230 9.2.2.2 Siphons
and Traps 233 9.3 Timed Petri Nets 234 9.3.1 Deterministic Timed Petri Nets
234 9.3.1.1 Performance Evaluation Based on DTPNs 237 9.3.2 Time Petri Nets
240 9.3.2.1 States in a Time Petri Net 241 9.3.2.2 Enabling and Firing
Conditions of Transitions 242 9.3.2.3 Firing Rules 243 Exercises 244
Suggestions for Reading 250 References 251 10 Model Checking 253 10.1
Introduction to Model Checking 253 10.2 Temporal Logic 254 10.2.1 Linear
Temporal Logic 256 10.2.1.1 Syntax of LTL 256 10.2.1.2 Parse Trees for LTL
Formulas 257 10.2.1.3 Semantics of LTL 258 10.2.1.4 Equivalencies of LTL
Formulas 262 10.2.1.5 System Property Specification 263 10.2.2 Computation
Tree logic 264 10.2.2.1 Syntax of CTL 264 10.2.2.2 Semantics of CTL 265
10.2.2.3 Equivalencies of CTL Formulas 268 10.2.3 LTL versus CTL 268 10.3
The NuSMV Model Checking Tool 269 10.3.1 Description Language 269 10.3.1.1
Single-Module SMV Program 269 10.3.1.2 Multimodule SMV Program 271 10.3.1.3
Asynchronous Systems 273 10.3.2 Specifications 274 10.3.3 Running NuSMV 275
10.4 Real-Time Computation Tree Logic 279 Exercises 285 Suggestions for
Reading 290 References 290 11 Practical Issues 293 11.1 Software
Reliability 293 11.1.1 Software Faults 293 11.1.2 ReliabilityMeasurement
294 11.1.3 Improving Software Reliability 295 11.1.3.1 Fault Avoidance 295
11.1.3.2 Fault Removal 295 11.1.3.3 Fault Tolerance 295 11.1.3.4 Fault
Recovery 296 11.2 Software Aging and Rejuvenation 296 11.3 Security 297
11.3.1 Challenges 297 11.3.2 Common Vulnerabilities 298 11.3.3 Secure
Software Design 299 11.4 Safety 300 11.5 Power Conservation 301 Suggestions
for Reading 302 References 302 Index 305
Real-Time Embedded Systems 1 1.1 Real-Time Embedded Systems 1 1.2 Example:
Automobile Antilock Braking System 3 1.2.1 Slip Rate and Brake Force 3
1.2.2 ABS Components 4 1.2.2.1 Sensors 4 1.2.2.2 Valves and Pumps 5 1.2.2.3
Electrical Control Unit 7 1.2.3 ABS Control 8 1.3 Real-Time Embedded System
Characteristics 10 1.3.1 System Structure 10 1.3.2 Real-Time Response 10
1.3.3 Highly Constrained Environments 11 1.3.4 Concurrency 12 1.3.5
Predictability 12 1.3.6 Safety and Reliability 13 1.4 Hard and Soft
Real-Time Embedded Systems 13 Exercises 14 Suggestions for Reading 15
References 15 2 Hardware Components 17 2.1 Processors 17 2.1.1
Microprocessors 17 2.1.2 Microcontrollers 19 2.1.3 Application-Specific
Integrated Circuits (ASICs) 19 2.1.4 Field-Programmable Gate Arrays (FPGAs)
19 2.1.5 Digital Signal Processors (DSPs) 20 2.1.6 Application-Specific
Instruction Set Processors (ASIPs) 20 2.1.7 Multicore Processors 20 2.1.8
Von Neumann Architecture and Harvard Architecture 21 2.1.9 Complex
Instruction Set Computing and Reduced Instruction Set Computing 22 2.2
Memory and Cache 23 2.2.1 Read-Only Memory (ROM) 23 2.2.2 Random-Access
Memory (RAM) 24 2.2.3 Cache Memory 24 2.3 I/O Interfaces 26 2.4 Sensors and
Actuators 27 2.5 Timers and Counters 29 Exercises 30 Suggestions for
Reading 31 References 31 3 Real-Time Operating Systems 33 3.1 Main
Functions of General-Purpose Operating Systems 33 3.1.1 Process Management
34 3.1.2 Memory Management 36 3.1.3 Interrupts Management 39 3.1.4
Multitasking 39 3.1.5 File System Management 39 3.1.6 I/O Management 41 3.2
Characteristics of RTOS Kernels 42 3.2.1 Clocks and Timers 42 3.2.2
Priority Scheduling 44 3.2.3 Intertask Communication and Resource Sharing
45 3.2.3.1 Real-Time Signals 45 3.2.3.2 Semaphores 46 3.2.3.3 Message
Passing 46 3.2.3.4 Shared Memory 46 3.2.4 Asynchronous I/O 47 3.2.5 Memory
Locking 47 3.3 RTOS Examples 48 3.3.1 LynxOS 48 3.3.2 OSE 49 3.3.3 QNX 49
3.3.4 VxWorks 49 3.3.5 Windows Embedded Compact 50 Exercises 50 Suggestions
for Reading 52 References 52 4 Task Scheduling 53 4.1 Tasks 53 4.1.1 Task
Specification 54 4.1.2 Task States 56 4.1.3 Precedence Constraints 58 4.1.4
Task Assignment and Scheduling 59 4.2 Clock-Driven Scheduling 59 4.2.1
Structured Clock-Driven Scheduling 62 4.2.1.1 Frames 62 4.2.1.2 Task
Slicing 65 4.2.2 Scheduling Aperiodic Tasks 66 4.2.3 Scheduling Sporadic
Tasks 68 4.3 Round-Robin Approach 69 4.4 Priority-Driven Scheduling
Algorithms 70 4.4.1 Fixed-Priority Algorithms 70 4.4.1.1 Schedulability
Test Based on Time Demand Analysis 72 4.4.1.2 Deadline-Monotonic Algorithm
76 4.4.2 Dynamic-Priority Algorithms 76 4.4.2.1 Earliest-Deadline-First
(EDF) Algorithm 76 4.4.2.2 Optimality of EDF 78 4.4.3 Priority-Driven
Scheduling of Aperiodic and Sporadic Tasks 82 4.4.3.1 Scheduling of
Aperiodic Tasks 82 4.4.3.2 Scheduling of Sporadic Tasks 85 4.4.4 Practical
Factors 85 4.4.4.1 Nonpreemptivity 85 4.4.4.2 Self-Suspension 86 4.4.4.3
Context Switches 87 4.4.4.4 Schedulability Test 87 4.5 Task Assignment 89
4.5.1 Bin-Packing Algorithms 89 4.5.1.1 First-Fit Algorithm 90 4.5.1.2
First-Fit Decreasing Algorithm 91 4.5.1.3 Rate-Monotonic First-Fit (RMFF)
Algorithm 91 4.5.2 Assignment with Communication Cost 92 Exercises 94
Suggestions for Reading 97 References 97 5 Resource Sharing and Access
Control 99 5.1 Resource Sharing 99 5.1.1 Resource Operation 100 5.1.2
Resource Requirement Specification 100 5.1.3 Priority Inversion and
Deadlocks 101 5.1.4 Resource Access Control 103 5.2 Nonpreemptive Critical
Section Protocol 103 5.3 Priority Inheritance Protocol 106 5.3.1 Rules of
Priority Inheritance Protocol 106 5.3.2 Properties of Priority Inheritance
Protocol 109 5.4 Priority Ceiling Protocol 111 5.4.1 Rules of Priority
Ceiling Protocol 112 5.4.2 Properties of Priority Ceiling Protocol 114
5.4.3 Worst-Case Blocking Time 116 5.5 Stack-Sharing Priority Ceiling
Protocol 119 5.5.1 Rules of Stack-Sharing Priority Ceiling Protocol 119
5.5.2 Properties of Stack-Sharing Priority Ceiling Protocol 121 Exercises
122 Suggestion for Reading 125 References 125 6 Concurrent Programming 127
6.1 Introduction 127 6.2 POSIX Threads 128 6.3 Synchronization Primitives
133 6.3.1 Race Conditions and Critical Sections 133 6.3.2 Mutex 134 6.3.3
Condition Variables 137 6.3.4 Semaphores 142 6.4 Communication among Tasks
148 6.4.1 Message Queues 149 6.4.2 Shared Memory 155 6.4.3 Shared Memory
Protection 157 6.5 Real-Time Facilities 162 6.5.1 Real-Time Signals 162
6.5.1.1 Blocking Signals 163 6.5.1.2 Dealing with Signals 164 6.5.2 Timers
165 6.5.3 Implement Periodic Tasks 169 6.5.3.1 Using sleep() Function 169
6.5.3.2 Using Timers 172 6.5.4 Implement an Application with Multiple
Periodic Tasks 173 Exercises 173 Suggestions for Reading 177 References 177
7 Finite-State Machines 179 7.1 Finite State Machine Basics 179 7.2
Deterministic Finite Automation (DFA) 181 7.2.1 Moore Machines 182 7.2.2
Mealy Machines 184 7.3 Nondeterministic Finite Automation 188 7.4
Programming Finite-State Machines 188 Exercises 191 Suggestions for Reading
194 References 195 8 UML State Machines 197 8.1 States 198 8.2 Transitions
200 8.3 Events 201 8.4 Composite States 202 8.4.1 Hierarchy 203 8.4.2
Orthogonality 205 8.4.3 Submachine States 206 8.5 Pseudostates 206 8.5.1
History Pseudostates 206 8.5.2 Entry and Exit Points 208 8.5.3 Fork and
Join Pseudostates 210 8.5.4 Terminate Pseudostates 210 8.6 UML State
Machine of Antilock Braking System 211 Exercises 215 Suggestions for
Reading 217 References 217 9 Timed Petri Nets 219 9.1 Petri Net Definition
219 9.1.1 Transition Firing 221 9.1.2 Modeling Power 222 9.2 Petri Net
Properties 225 9.2.1 Behavioral Properties 225 9.2.1.1 Reachability 225
9.2.1.2 omega Markings 226 9.2.1.3 Reachability Analysis Algorithm 227
9.2.1.4 Boundedness and Safeness 229 9.2.1.5 Liveness 229 9.2.2 Structural
Properties 230 9.2.2.1 T-Invariants and S-Invariants 230 9.2.2.2 Siphons
and Traps 233 9.3 Timed Petri Nets 234 9.3.1 Deterministic Timed Petri Nets
234 9.3.1.1 Performance Evaluation Based on DTPNs 237 9.3.2 Time Petri Nets
240 9.3.2.1 States in a Time Petri Net 241 9.3.2.2 Enabling and Firing
Conditions of Transitions 242 9.3.2.3 Firing Rules 243 Exercises 244
Suggestions for Reading 250 References 251 10 Model Checking 253 10.1
Introduction to Model Checking 253 10.2 Temporal Logic 254 10.2.1 Linear
Temporal Logic 256 10.2.1.1 Syntax of LTL 256 10.2.1.2 Parse Trees for LTL
Formulas 257 10.2.1.3 Semantics of LTL 258 10.2.1.4 Equivalencies of LTL
Formulas 262 10.2.1.5 System Property Specification 263 10.2.2 Computation
Tree logic 264 10.2.2.1 Syntax of CTL 264 10.2.2.2 Semantics of CTL 265
10.2.2.3 Equivalencies of CTL Formulas 268 10.2.3 LTL versus CTL 268 10.3
The NuSMV Model Checking Tool 269 10.3.1 Description Language 269 10.3.1.1
Single-Module SMV Program 269 10.3.1.2 Multimodule SMV Program 271 10.3.1.3
Asynchronous Systems 273 10.3.2 Specifications 274 10.3.3 Running NuSMV 275
10.4 Real-Time Computation Tree Logic 279 Exercises 285 Suggestions for
Reading 290 References 290 11 Practical Issues 293 11.1 Software
Reliability 293 11.1.1 Software Faults 293 11.1.2 ReliabilityMeasurement
294 11.1.3 Improving Software Reliability 295 11.1.3.1 Fault Avoidance 295
11.1.3.2 Fault Removal 295 11.1.3.3 Fault Tolerance 295 11.1.3.4 Fault
Recovery 296 11.2 Software Aging and Rejuvenation 296 11.3 Security 297
11.3.1 Challenges 297 11.3.2 Common Vulnerabilities 298 11.3.3 Secure
Software Design 299 11.4 Safety 300 11.5 Power Conservation 301 Suggestions
for Reading 302 References 302 Index 305
Preface xiii Book Layout xv Acknowledgments xvii 1 Introduction to
Real-Time Embedded Systems 1 1.1 Real-Time Embedded Systems 1 1.2 Example:
Automobile Antilock Braking System 3 1.2.1 Slip Rate and Brake Force 3
1.2.2 ABS Components 4 1.2.2.1 Sensors 4 1.2.2.2 Valves and Pumps 5 1.2.2.3
Electrical Control Unit 7 1.2.3 ABS Control 8 1.3 Real-Time Embedded System
Characteristics 10 1.3.1 System Structure 10 1.3.2 Real-Time Response 10
1.3.3 Highly Constrained Environments 11 1.3.4 Concurrency 12 1.3.5
Predictability 12 1.3.6 Safety and Reliability 13 1.4 Hard and Soft
Real-Time Embedded Systems 13 Exercises 14 Suggestions for Reading 15
References 15 2 Hardware Components 17 2.1 Processors 17 2.1.1
Microprocessors 17 2.1.2 Microcontrollers 19 2.1.3 Application-Specific
Integrated Circuits (ASICs) 19 2.1.4 Field-Programmable Gate Arrays (FPGAs)
19 2.1.5 Digital Signal Processors (DSPs) 20 2.1.6 Application-Specific
Instruction Set Processors (ASIPs) 20 2.1.7 Multicore Processors 20 2.1.8
Von Neumann Architecture and Harvard Architecture 21 2.1.9 Complex
Instruction Set Computing and Reduced Instruction Set Computing 22 2.2
Memory and Cache 23 2.2.1 Read-Only Memory (ROM) 23 2.2.2 Random-Access
Memory (RAM) 24 2.2.3 Cache Memory 24 2.3 I/O Interfaces 26 2.4 Sensors and
Actuators 27 2.5 Timers and Counters 29 Exercises 30 Suggestions for
Reading 31 References 31 3 Real-Time Operating Systems 33 3.1 Main
Functions of General-Purpose Operating Systems 33 3.1.1 Process Management
34 3.1.2 Memory Management 36 3.1.3 Interrupts Management 39 3.1.4
Multitasking 39 3.1.5 File System Management 39 3.1.6 I/O Management 41 3.2
Characteristics of RTOS Kernels 42 3.2.1 Clocks and Timers 42 3.2.2
Priority Scheduling 44 3.2.3 Intertask Communication and Resource Sharing
45 3.2.3.1 Real-Time Signals 45 3.2.3.2 Semaphores 46 3.2.3.3 Message
Passing 46 3.2.3.4 Shared Memory 46 3.2.4 Asynchronous I/O 47 3.2.5 Memory
Locking 47 3.3 RTOS Examples 48 3.3.1 LynxOS 48 3.3.2 OSE 49 3.3.3 QNX 49
3.3.4 VxWorks 49 3.3.5 Windows Embedded Compact 50 Exercises 50 Suggestions
for Reading 52 References 52 4 Task Scheduling 53 4.1 Tasks 53 4.1.1 Task
Specification 54 4.1.2 Task States 56 4.1.3 Precedence Constraints 58 4.1.4
Task Assignment and Scheduling 59 4.2 Clock-Driven Scheduling 59 4.2.1
Structured Clock-Driven Scheduling 62 4.2.1.1 Frames 62 4.2.1.2 Task
Slicing 65 4.2.2 Scheduling Aperiodic Tasks 66 4.2.3 Scheduling Sporadic
Tasks 68 4.3 Round-Robin Approach 69 4.4 Priority-Driven Scheduling
Algorithms 70 4.4.1 Fixed-Priority Algorithms 70 4.4.1.1 Schedulability
Test Based on Time Demand Analysis 72 4.4.1.2 Deadline-Monotonic Algorithm
76 4.4.2 Dynamic-Priority Algorithms 76 4.4.2.1 Earliest-Deadline-First
(EDF) Algorithm 76 4.4.2.2 Optimality of EDF 78 4.4.3 Priority-Driven
Scheduling of Aperiodic and Sporadic Tasks 82 4.4.3.1 Scheduling of
Aperiodic Tasks 82 4.4.3.2 Scheduling of Sporadic Tasks 85 4.4.4 Practical
Factors 85 4.4.4.1 Nonpreemptivity 85 4.4.4.2 Self-Suspension 86 4.4.4.3
Context Switches 87 4.4.4.4 Schedulability Test 87 4.5 Task Assignment 89
4.5.1 Bin-Packing Algorithms 89 4.5.1.1 First-Fit Algorithm 90 4.5.1.2
First-Fit Decreasing Algorithm 91 4.5.1.3 Rate-Monotonic First-Fit (RMFF)
Algorithm 91 4.5.2 Assignment with Communication Cost 92 Exercises 94
Suggestions for Reading 97 References 97 5 Resource Sharing and Access
Control 99 5.1 Resource Sharing 99 5.1.1 Resource Operation 100 5.1.2
Resource Requirement Specification 100 5.1.3 Priority Inversion and
Deadlocks 101 5.1.4 Resource Access Control 103 5.2 Nonpreemptive Critical
Section Protocol 103 5.3 Priority Inheritance Protocol 106 5.3.1 Rules of
Priority Inheritance Protocol 106 5.3.2 Properties of Priority Inheritance
Protocol 109 5.4 Priority Ceiling Protocol 111 5.4.1 Rules of Priority
Ceiling Protocol 112 5.4.2 Properties of Priority Ceiling Protocol 114
5.4.3 Worst-Case Blocking Time 116 5.5 Stack-Sharing Priority Ceiling
Protocol 119 5.5.1 Rules of Stack-Sharing Priority Ceiling Protocol 119
5.5.2 Properties of Stack-Sharing Priority Ceiling Protocol 121 Exercises
122 Suggestion for Reading 125 References 125 6 Concurrent Programming 127
6.1 Introduction 127 6.2 POSIX Threads 128 6.3 Synchronization Primitives
133 6.3.1 Race Conditions and Critical Sections 133 6.3.2 Mutex 134 6.3.3
Condition Variables 137 6.3.4 Semaphores 142 6.4 Communication among Tasks
148 6.4.1 Message Queues 149 6.4.2 Shared Memory 155 6.4.3 Shared Memory
Protection 157 6.5 Real-Time Facilities 162 6.5.1 Real-Time Signals 162
6.5.1.1 Blocking Signals 163 6.5.1.2 Dealing with Signals 164 6.5.2 Timers
165 6.5.3 Implement Periodic Tasks 169 6.5.3.1 Using sleep() Function 169
6.5.3.2 Using Timers 172 6.5.4 Implement an Application with Multiple
Periodic Tasks 173 Exercises 173 Suggestions for Reading 177 References 177
7 Finite-State Machines 179 7.1 Finite State Machine Basics 179 7.2
Deterministic Finite Automation (DFA) 181 7.2.1 Moore Machines 182 7.2.2
Mealy Machines 184 7.3 Nondeterministic Finite Automation 188 7.4
Programming Finite-State Machines 188 Exercises 191 Suggestions for Reading
194 References 195 8 UML State Machines 197 8.1 States 198 8.2 Transitions
200 8.3 Events 201 8.4 Composite States 202 8.4.1 Hierarchy 203 8.4.2
Orthogonality 205 8.4.3 Submachine States 206 8.5 Pseudostates 206 8.5.1
History Pseudostates 206 8.5.2 Entry and Exit Points 208 8.5.3 Fork and
Join Pseudostates 210 8.5.4 Terminate Pseudostates 210 8.6 UML State
Machine of Antilock Braking System 211 Exercises 215 Suggestions for
Reading 217 References 217 9 Timed Petri Nets 219 9.1 Petri Net Definition
219 9.1.1 Transition Firing 221 9.1.2 Modeling Power 222 9.2 Petri Net
Properties 225 9.2.1 Behavioral Properties 225 9.2.1.1 Reachability 225
9.2.1.2 omega Markings 226 9.2.1.3 Reachability Analysis Algorithm 227
9.2.1.4 Boundedness and Safeness 229 9.2.1.5 Liveness 229 9.2.2 Structural
Properties 230 9.2.2.1 T-Invariants and S-Invariants 230 9.2.2.2 Siphons
and Traps 233 9.3 Timed Petri Nets 234 9.3.1 Deterministic Timed Petri Nets
234 9.3.1.1 Performance Evaluation Based on DTPNs 237 9.3.2 Time Petri Nets
240 9.3.2.1 States in a Time Petri Net 241 9.3.2.2 Enabling and Firing
Conditions of Transitions 242 9.3.2.3 Firing Rules 243 Exercises 244
Suggestions for Reading 250 References 251 10 Model Checking 253 10.1
Introduction to Model Checking 253 10.2 Temporal Logic 254 10.2.1 Linear
Temporal Logic 256 10.2.1.1 Syntax of LTL 256 10.2.1.2 Parse Trees for LTL
Formulas 257 10.2.1.3 Semantics of LTL 258 10.2.1.4 Equivalencies of LTL
Formulas 262 10.2.1.5 System Property Specification 263 10.2.2 Computation
Tree logic 264 10.2.2.1 Syntax of CTL 264 10.2.2.2 Semantics of CTL 265
10.2.2.3 Equivalencies of CTL Formulas 268 10.2.3 LTL versus CTL 268 10.3
The NuSMV Model Checking Tool 269 10.3.1 Description Language 269 10.3.1.1
Single-Module SMV Program 269 10.3.1.2 Multimodule SMV Program 271 10.3.1.3
Asynchronous Systems 273 10.3.2 Specifications 274 10.3.3 Running NuSMV 275
10.4 Real-Time Computation Tree Logic 279 Exercises 285 Suggestions for
Reading 290 References 290 11 Practical Issues 293 11.1 Software
Reliability 293 11.1.1 Software Faults 293 11.1.2 ReliabilityMeasurement
294 11.1.3 Improving Software Reliability 295 11.1.3.1 Fault Avoidance 295
11.1.3.2 Fault Removal 295 11.1.3.3 Fault Tolerance 295 11.1.3.4 Fault
Recovery 296 11.2 Software Aging and Rejuvenation 296 11.3 Security 297
11.3.1 Challenges 297 11.3.2 Common Vulnerabilities 298 11.3.3 Secure
Software Design 299 11.4 Safety 300 11.5 Power Conservation 301 Suggestions
for Reading 302 References 302 Index 305
Real-Time Embedded Systems 1 1.1 Real-Time Embedded Systems 1 1.2 Example:
Automobile Antilock Braking System 3 1.2.1 Slip Rate and Brake Force 3
1.2.2 ABS Components 4 1.2.2.1 Sensors 4 1.2.2.2 Valves and Pumps 5 1.2.2.3
Electrical Control Unit 7 1.2.3 ABS Control 8 1.3 Real-Time Embedded System
Characteristics 10 1.3.1 System Structure 10 1.3.2 Real-Time Response 10
1.3.3 Highly Constrained Environments 11 1.3.4 Concurrency 12 1.3.5
Predictability 12 1.3.6 Safety and Reliability 13 1.4 Hard and Soft
Real-Time Embedded Systems 13 Exercises 14 Suggestions for Reading 15
References 15 2 Hardware Components 17 2.1 Processors 17 2.1.1
Microprocessors 17 2.1.2 Microcontrollers 19 2.1.3 Application-Specific
Integrated Circuits (ASICs) 19 2.1.4 Field-Programmable Gate Arrays (FPGAs)
19 2.1.5 Digital Signal Processors (DSPs) 20 2.1.6 Application-Specific
Instruction Set Processors (ASIPs) 20 2.1.7 Multicore Processors 20 2.1.8
Von Neumann Architecture and Harvard Architecture 21 2.1.9 Complex
Instruction Set Computing and Reduced Instruction Set Computing 22 2.2
Memory and Cache 23 2.2.1 Read-Only Memory (ROM) 23 2.2.2 Random-Access
Memory (RAM) 24 2.2.3 Cache Memory 24 2.3 I/O Interfaces 26 2.4 Sensors and
Actuators 27 2.5 Timers and Counters 29 Exercises 30 Suggestions for
Reading 31 References 31 3 Real-Time Operating Systems 33 3.1 Main
Functions of General-Purpose Operating Systems 33 3.1.1 Process Management
34 3.1.2 Memory Management 36 3.1.3 Interrupts Management 39 3.1.4
Multitasking 39 3.1.5 File System Management 39 3.1.6 I/O Management 41 3.2
Characteristics of RTOS Kernels 42 3.2.1 Clocks and Timers 42 3.2.2
Priority Scheduling 44 3.2.3 Intertask Communication and Resource Sharing
45 3.2.3.1 Real-Time Signals 45 3.2.3.2 Semaphores 46 3.2.3.3 Message
Passing 46 3.2.3.4 Shared Memory 46 3.2.4 Asynchronous I/O 47 3.2.5 Memory
Locking 47 3.3 RTOS Examples 48 3.3.1 LynxOS 48 3.3.2 OSE 49 3.3.3 QNX 49
3.3.4 VxWorks 49 3.3.5 Windows Embedded Compact 50 Exercises 50 Suggestions
for Reading 52 References 52 4 Task Scheduling 53 4.1 Tasks 53 4.1.1 Task
Specification 54 4.1.2 Task States 56 4.1.3 Precedence Constraints 58 4.1.4
Task Assignment and Scheduling 59 4.2 Clock-Driven Scheduling 59 4.2.1
Structured Clock-Driven Scheduling 62 4.2.1.1 Frames 62 4.2.1.2 Task
Slicing 65 4.2.2 Scheduling Aperiodic Tasks 66 4.2.3 Scheduling Sporadic
Tasks 68 4.3 Round-Robin Approach 69 4.4 Priority-Driven Scheduling
Algorithms 70 4.4.1 Fixed-Priority Algorithms 70 4.4.1.1 Schedulability
Test Based on Time Demand Analysis 72 4.4.1.2 Deadline-Monotonic Algorithm
76 4.4.2 Dynamic-Priority Algorithms 76 4.4.2.1 Earliest-Deadline-First
(EDF) Algorithm 76 4.4.2.2 Optimality of EDF 78 4.4.3 Priority-Driven
Scheduling of Aperiodic and Sporadic Tasks 82 4.4.3.1 Scheduling of
Aperiodic Tasks 82 4.4.3.2 Scheduling of Sporadic Tasks 85 4.4.4 Practical
Factors 85 4.4.4.1 Nonpreemptivity 85 4.4.4.2 Self-Suspension 86 4.4.4.3
Context Switches 87 4.4.4.4 Schedulability Test 87 4.5 Task Assignment 89
4.5.1 Bin-Packing Algorithms 89 4.5.1.1 First-Fit Algorithm 90 4.5.1.2
First-Fit Decreasing Algorithm 91 4.5.1.3 Rate-Monotonic First-Fit (RMFF)
Algorithm 91 4.5.2 Assignment with Communication Cost 92 Exercises 94
Suggestions for Reading 97 References 97 5 Resource Sharing and Access
Control 99 5.1 Resource Sharing 99 5.1.1 Resource Operation 100 5.1.2
Resource Requirement Specification 100 5.1.3 Priority Inversion and
Deadlocks 101 5.1.4 Resource Access Control 103 5.2 Nonpreemptive Critical
Section Protocol 103 5.3 Priority Inheritance Protocol 106 5.3.1 Rules of
Priority Inheritance Protocol 106 5.3.2 Properties of Priority Inheritance
Protocol 109 5.4 Priority Ceiling Protocol 111 5.4.1 Rules of Priority
Ceiling Protocol 112 5.4.2 Properties of Priority Ceiling Protocol 114
5.4.3 Worst-Case Blocking Time 116 5.5 Stack-Sharing Priority Ceiling
Protocol 119 5.5.1 Rules of Stack-Sharing Priority Ceiling Protocol 119
5.5.2 Properties of Stack-Sharing Priority Ceiling Protocol 121 Exercises
122 Suggestion for Reading 125 References 125 6 Concurrent Programming 127
6.1 Introduction 127 6.2 POSIX Threads 128 6.3 Synchronization Primitives
133 6.3.1 Race Conditions and Critical Sections 133 6.3.2 Mutex 134 6.3.3
Condition Variables 137 6.3.4 Semaphores 142 6.4 Communication among Tasks
148 6.4.1 Message Queues 149 6.4.2 Shared Memory 155 6.4.3 Shared Memory
Protection 157 6.5 Real-Time Facilities 162 6.5.1 Real-Time Signals 162
6.5.1.1 Blocking Signals 163 6.5.1.2 Dealing with Signals 164 6.5.2 Timers
165 6.5.3 Implement Periodic Tasks 169 6.5.3.1 Using sleep() Function 169
6.5.3.2 Using Timers 172 6.5.4 Implement an Application with Multiple
Periodic Tasks 173 Exercises 173 Suggestions for Reading 177 References 177
7 Finite-State Machines 179 7.1 Finite State Machine Basics 179 7.2
Deterministic Finite Automation (DFA) 181 7.2.1 Moore Machines 182 7.2.2
Mealy Machines 184 7.3 Nondeterministic Finite Automation 188 7.4
Programming Finite-State Machines 188 Exercises 191 Suggestions for Reading
194 References 195 8 UML State Machines 197 8.1 States 198 8.2 Transitions
200 8.3 Events 201 8.4 Composite States 202 8.4.1 Hierarchy 203 8.4.2
Orthogonality 205 8.4.3 Submachine States 206 8.5 Pseudostates 206 8.5.1
History Pseudostates 206 8.5.2 Entry and Exit Points 208 8.5.3 Fork and
Join Pseudostates 210 8.5.4 Terminate Pseudostates 210 8.6 UML State
Machine of Antilock Braking System 211 Exercises 215 Suggestions for
Reading 217 References 217 9 Timed Petri Nets 219 9.1 Petri Net Definition
219 9.1.1 Transition Firing 221 9.1.2 Modeling Power 222 9.2 Petri Net
Properties 225 9.2.1 Behavioral Properties 225 9.2.1.1 Reachability 225
9.2.1.2 omega Markings 226 9.2.1.3 Reachability Analysis Algorithm 227
9.2.1.4 Boundedness and Safeness 229 9.2.1.5 Liveness 229 9.2.2 Structural
Properties 230 9.2.2.1 T-Invariants and S-Invariants 230 9.2.2.2 Siphons
and Traps 233 9.3 Timed Petri Nets 234 9.3.1 Deterministic Timed Petri Nets
234 9.3.1.1 Performance Evaluation Based on DTPNs 237 9.3.2 Time Petri Nets
240 9.3.2.1 States in a Time Petri Net 241 9.3.2.2 Enabling and Firing
Conditions of Transitions 242 9.3.2.3 Firing Rules 243 Exercises 244
Suggestions for Reading 250 References 251 10 Model Checking 253 10.1
Introduction to Model Checking 253 10.2 Temporal Logic 254 10.2.1 Linear
Temporal Logic 256 10.2.1.1 Syntax of LTL 256 10.2.1.2 Parse Trees for LTL
Formulas 257 10.2.1.3 Semantics of LTL 258 10.2.1.4 Equivalencies of LTL
Formulas 262 10.2.1.5 System Property Specification 263 10.2.2 Computation
Tree logic 264 10.2.2.1 Syntax of CTL 264 10.2.2.2 Semantics of CTL 265
10.2.2.3 Equivalencies of CTL Formulas 268 10.2.3 LTL versus CTL 268 10.3
The NuSMV Model Checking Tool 269 10.3.1 Description Language 269 10.3.1.1
Single-Module SMV Program 269 10.3.1.2 Multimodule SMV Program 271 10.3.1.3
Asynchronous Systems 273 10.3.2 Specifications 274 10.3.3 Running NuSMV 275
10.4 Real-Time Computation Tree Logic 279 Exercises 285 Suggestions for
Reading 290 References 290 11 Practical Issues 293 11.1 Software
Reliability 293 11.1.1 Software Faults 293 11.1.2 ReliabilityMeasurement
294 11.1.3 Improving Software Reliability 295 11.1.3.1 Fault Avoidance 295
11.1.3.2 Fault Removal 295 11.1.3.3 Fault Tolerance 295 11.1.3.4 Fault
Recovery 296 11.2 Software Aging and Rejuvenation 296 11.3 Security 297
11.3.1 Challenges 297 11.3.2 Common Vulnerabilities 298 11.3.3 Secure
Software Design 299 11.4 Safety 300 11.5 Power Conservation 301 Suggestions
for Reading 302 References 302 Index 305