Real-Time Embedded Systems
Description
More details
Other editions
Additional editions
Person
Content
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 ¿ 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 Reliability Measurement 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
Chapter 1
Introduction to Real-Time Embedded Systems
Real-time embedded systems have become pervasive. They are in your cars, cell phones, Personal Digital Assistants (PDAs), watches, televisions, and home electrical appliances. There are also larger and more complex real-time embedded systems, such as air-traffic control systems, industrial process control systems, networked multimedia systems, and real-time database applications. It is reported that in the Lexus LS-460 released in September 2006, there are more than 100 microprocessors embedded when all optional features are installed. It is also estimated that 98% of all microprocessors are manufactured as components of embedded systems. In fact, our daily life has become more and more dependent on real-time embedded applications. This chapter explains the concepts of embedded systems and real-time systems, introduces the fundamental characteristics of real-time embedded systems, and defines hard and soft real-time systems. The automotive antilock braking system (ABS) is used as an example to show a real-world embedded system.
1.1 Real-Time Embedded Systems
An embedded system is a microcomputer system embedded in a larger system and designed for one or two dedicated services. It is embedded as part of a complete device that often has hardware and mechanical parts. Examples include the controllers built inside our home electrical appliances. Most embedded systems have real-time computing constraints. Therefore, they are also called real-time embedded systems. Compared with general-purpose computing systems that have multiple functionalities, embedded systems are often dedicated to specific tasks. For example, the embedded airbag control system is only responsible for detecting collision and inflating the airbag when necessary, and the embedded controller in an air conditioner is only responsible for monitoring and regulating the temperature of a room.
Another noteworthy difference between a general-purpose computing system and an embedded system is that a general-purpose system has full-scale operating system support, while embedded systems may or may not have operating system support at all. Many small-sized embedded systems are designed to perform simple tasks and thus do not need operating system support.
Embedded systems are reactive systems in nature. They are basically designed to regulate a physical variable in response to the input signal provided by the end users or sensors, which are connected to the input ports. For example, the goal of a grain-roasting embedded system is regulating the temperature of a furnace by adjusting the amount of fuel being injected into the furnace. The regulation or control is performed based on the difference between the desired temperature and the real temperature detected by temperature sensors.
Embedded systems can be classified based on their complexity and performance into small-scale, medium-scale, and large-scale. Small-scale systems perform simple functions and are usually built around low-end 8- or 16-bit microprocessors or microcontrollers. For developing embedded software for small-scale embedded systems, the main programming tools are an editor, assembler, cross-assembler, and integrated development environment (IDE). Examples of small-scale embedded systems are mouse and TV remote control. They typically operate on battery. Normally, no operating system is found in such systems.
Medium-scale systems have both hardware and software complexities. They use 16- or 32-bit microprocessors or microcontrollers. For developing embedded software for medium-scale embedded systems, the main programming tools are C, C++, JAVA, Visual C++, debugger, source-code engineering tool, simulator, and IDE. They typically have operating system support. Examples of medium-scale embedded systems are vending machines and washing machines.
Large-scale or sophisticated embedded systems have enormous hardware and software complexities, which are built around 32- or 64-bit microprocessors or microcontrollers, along with a range of other high-speed integrated circuits. They are used for cutting-edge applications that need hardware and software codesign techniques. Examples of large-scale embedded systems are flight-landing gear systems, car braking systems, and military applications.
Embedded systems can be non-real-time or real-time. For a non-real-time system, we say that it is correctly designed and developed if it delivers the desired functions upon receiving external stimuli or internal triggers, with a satisfied degree of QoS (Quality of Service). Examples are TV remote controls and calculators.
Real-time systems, however, are required to compute and deliver correct results within a specified period of time. In other words, a job of a real-time system has a deadline, being it hard or soft. If a hard deadline is missed, then the result is useless, even if it is correct. Consider the airbag control system in automobiles. Airbags are generally designed to inflate in the cases of frontal impacts in automobiles. Because vehicles change speed so quickly in a crash, airbags must inflate rapidly to reduce the risk of the occupant hitting the vehicle's interior. Normally, from the onset of the crash, the entire deployment and inflation process is about 0.04 seconds, while the limit is 0.1 seconds.
Non-real-time embedded systems may have time constraints as well. Imagining if it takes more than 5 seconds for your TV remote control to send a control signal to your TV and then the embedded device inside the TV takes another 5 seconds to change the channel for you, you will certainly complain. It is reasonable that consumers expect a TV to respond to remote control event within 1 second. However, this kind of constraints is only a measure of system performance.
Traditional application domains of real-time embedded systems include automotive, avionics, industrial process control, digital signal processing, multimedia, and real-time databases. However, with the continuing rapid advance in information and communication technology and the emergence of Internet of things and pervasive computing, real-time embedded applications will be found in any objects that can be made smart.
1.2 Example: Automobile Antilock Braking System
A distinguished application area of real-time embedded systems is automobiles. Automotive embedded systems are designed and developed to control engine, automatic transmission, steering, brake, suspension, exhaustion, and so on. They are also used in body electronics, such as instrument panel, key, door, window, lighting, air bag, and seat bag. This section introduces the ABS.
An ABS is an automobile safety system. It is designed to prevent the wheels of a vehicle from locking when brake pedal pressure is applied, which may occur all of a sudden in case of emergency or short stopping distance. A sudden lock of wheels will cause moving vehicles to lose tractive contact with the road surface and skid uncontrollably. For this reason, ABS also stands for antiskid braking system. The main benefit from ABS operation is retaining the directional control of the vehicle during heavy braking in rare circumstances.
1.2.1 Slip Rate and Brake Force
When the brake pedal is depressed during driving, the wheel velocity (the tangential speed of the tire surface) decreases, and so does the vehicle velocity. The decrease in the vehicle velocity, however, is not always synchronized with the wheel velocity. When the maximum friction between a tire and the road surface is reached, further increase in brake pressure will not increase the braking force, which is the product of the weight of the vehicle and the friction coefficient. As a consequence, the vehicle velocity is greater than the wheel speed, and the wheel starts to skid. The wheel slip rate, s, is defined as
where V, ?, and R denote the vehicle speed, wheel angular velocity, and wheel rolling radius, respectively. Under normal driving conditions, V = ?R and thus, s = 0. During severe braking, it is common to have ? = 0 and V > 0, which translates to s = 1, a case of wheel lockup.
Figure 1.1 describes the relationship among the slip rate, braking force, and cornering force. The continuous line in the figure represents the relationship between the slip rate and braking force. It shows that the braking force is the largest when the slip rate is between 10% and 20%. The braking distance is the shortest at this rate. With further increase in slip rate, the braking force is decreased, which results in a longer braking distance. The dashed line depicts the relationship between the slip rate and cornering force. The cornering force is generated by a vehicle tire during cornering. It works on the front wheels as steering force and on the rear wheels to keep the vehicle stable. It decreases as the slip rate increases. In case of a lockup, the cornering force becomes 0 and steering is disabled.
Figure 1.1 Relationship among the slip rate, braking force, and cornering force.
1.2.2 ABS Components
The ABS is composed of four components. They are speed sensors, valves, pumps, and an electrical control unit (ECU). Valves and pumps are often housed in hydraulic control units (HCUs).
1.2.2.1 Sensors
There are multiple types of sensors used in the ABS. A wheel speed sensor is a sender device used for reading a vehicle's wheel rotation rate. It is an electromagnet...
