Real-Time Embedded Systems

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 xiiiBook Layout xvAcknowledgments xvii1 Introduction to Real-Time Embedded Systems 11.1 Real-Time Embedded Systems 11.2 Example: Automobile Antilock Braking System 31.2.1 Slip Rate and Brake Force 31.2.2 ABS Components 41.2.2.1 Sensors 41.2.2.2 Valves and Pumps 51.2.2.3 Electrical Control Unit 71.2.3 ABS Control 81.3 Real-Time Embedded System Characteristics 101.3.1 System Structure 101.3.2 Real-Time Response 101.3.3 Highly Constrained Environments 111.3.4 Concurrency 121.3.5 Predictability 121.3.6 Safety and Reliability 131.4 Hard and Soft Real-Time Embedded Systems 13Exercises 14Suggestions for Reading 15References 152 Hardware Components 172.1 Processors 172.1.1 Microprocessors 172.1.2 Microcontrollers 192.1.3 Application-Specific Integrated Circuits (ASICs) 192.1.4 Field-Programmable Gate Arrays (FPGAs) 192.1.5 Digital Signal Processors (DSPs) 202.1.6 Application-Specific Instruction Set Processors (ASIPs) 202.1.7 Multicore Processors 202.1.8 Von Neumann Architecture and Harvard Architecture 212.1.9 Complex Instruction Set Computing and Reduced Instruction Set Computing 222.2 Memory and Cache 232.2.1 Read-Only Memory (ROM) 232.2.2 Random-Access Memory (RAM) 242.2.3 Cache Memory 242.3 I/O Interfaces 262.4 Sensors and Actuators 272.5 Timers and Counters 29Exercises 30Suggestions for Reading 31References 313 Real-Time Operating Systems 333.1 Main Functions of General-Purpose Operating Systems 333.1.1 Process Management 343.1.2 Memory Management 363.1.3 Interrupts Management 393.1.4 Multitasking 393.1.5 File System Management 393.1.6 I/O Management 413.2 Characteristics of RTOS Kernels 423.2.1 Clocks and Timers 423.2.2 Priority Scheduling 443.2.3 Intertask Communication and Resource Sharing 453.2.3.1 Real-Time Signals 453.2.3.2 Semaphores 463.2.3.3 Message Passing 463.2.3.4 Shared Memory 463.2.4 Asynchronous I/O 473.2.5 Memory Locking 473.3 RTOS Examples 483.3.1 LynxOS 483.3.2 Ose 493.3.3 Qnx 493.3.4 VxWorks 493.3.5 Windows Embedded Compact 50Exercises 50Suggestions for Reading 52References 524 Task Scheduling 534.1 Tasks 534.1.1 Task Specification 544.1.2 Task States 564.1.3 Precedence Constraints 584.1.4 Task Assignment and Scheduling 594.2 Clock-Driven Scheduling 594.2.1 Structured Clock-Driven Scheduling 624.2.1.1 Frames 624.2.1.2 Task Slicing 654.2.2 Scheduling Aperiodic Tasks 664.2.3 Scheduling Sporadic Tasks 684.3 Round-Robin Approach 694.4 Priority-Driven Scheduling Algorithms 704.4.1 Fixed-Priority Algorithms 704.4.1.1 Schedulability Test Based on Time Demand Analysis 724.4.1.2 Deadline-Monotonic Algorithm 764.4.2 Dynamic-Priority Algorithms 764.4.2.1 Earliest-Deadline-First (EDF) Algorithm 764.4.2.2 Optimality of EDF 784.4.3 Priority-Driven Scheduling of Aperiodic and Sporadic Tasks 824.4.3.1 Scheduling of Aperiodic Tasks 824.4.3.2 Scheduling of Sporadic Tasks 854.4.4 Practical Factors 854.4.4.1 Nonpreemptivity 854.4.4.2 Self-Suspension 864.4.4.3 Context Switches 874.4.4.4 Schedulability Test 874.5 Task Assignment 894.5.1 Bin-Packing Algorithms 894.5.1.1 First-Fit Algorithm 904.5.1.2 First-Fit Decreasing Algorithm 914.5.1.3 Rate-Monotonic First-Fit (RMFF) Algorithm 914.5.2 Assignment with Communication Cost 92Exercises 94Suggestions for Reading 97References 975 Resource Sharing and Access Control 995.1 Resource Sharing 995.1.1 Resource Operation 1005.1.2 Resource Requirement Specification 1005.1.3 Priority Inversion and Deadlocks 1015.1.4 Resource Access Control 1035.2 Nonpreemptive Critical Section Protocol 1035.3 Priority Inheritance Protocol 1065.3.1 Rules of Priority Inheritance Protocol 1065.3.2 Properties of Priority Inheritance Protocol 1095.4 Priority Ceiling Protocol 1115.4.1 Rules of Priority Ceiling Protocol 1125.4.2 Properties of Priority Ceiling Protocol 1145.4.3 Worst-Case Blocking Time 1165.5 Stack-Sharing Priority Ceiling Protocol 1195.5.1 Rules of Stack-Sharing Priority Ceiling Protocol 1195.5.2 Properties of Stack-Sharing Priority Ceiling Protocol 121Exercises 122Suggestion for Reading 125References 1256 Concurrent Programming 1276.1 Introduction 1276.2 POSIX Threads 1286.3 Synchronization Primitives 1336.3.1 Race Conditions and Critical Sections 1336.3.2 Mutex 1346.3.3 Condition Variables 1376.3.4 Semaphores 1426.4 Communication among Tasks 1486.4.1 Message Queues 1496.4.2 Shared Memory 1556.4.3 Shared Memory Protection 1576.5 Real-Time Facilities 1626.5.1 Real-Time Signals 1626.5.1.1 Blocking Signals 1636.5.1.2 Dealing with Signals 1646.5.2 Timers 1656.5.3 Implement Periodic Tasks 1696.5.3.1 Using sleep() Function 1696.5.3.2 Using Timers 1726.5.4 Implement an Application with Multiple Periodic Tasks 173Exercises 173Suggestions for Reading 177References 1777 Finite-State Machines 1797.1 Finite State Machine Basics 1797.2 Deterministic Finite Automation (DFA) 1817.2.1 Moore Machines 1827.2.2 Mealy Machines 1847.3 Nondeterministic Finite Automation 1887.4 Programming Finite-State Machines 188Exercises 191Suggestions for Reading 194References 1958 UML State Machines 1978.1 States 1988.2 Transitions 2008.3 Events 2018.4 Composite States 2028.4.1 Hierarchy 2038.4.2 Orthogonality 2058.4.3 Submachine States 2068.5 Pseudostates 2068.5.1 History Pseudostates 2068.5.2 Entry and Exit Points 2088.5.3 Fork and Join Pseudostates 2108.5.4 Terminate Pseudostates 2108.6 UML State Machine of Antilock Braking System 211Exercises 215Suggestions for Reading 217References 2179 Timed Petri Nets 2199.1 Petri Net Definition 2199.1.1 Transition Firing 2219.1.2 Modeling Power 2229.2 Petri Net Properties 2259.2.1 Behavioral Properties 2259.2.1.1 Reachability 2259.2.1.2 ω Markings 2269.2.1.3 Reachability Analysis Algorithm 2279.2.1.4 Boundedness and Safeness 2299.2.1.5 Liveness 2299.2.2 Structural Properties 2309.2.2.1 T-Invariants and S-Invariants 2309.2.2.2 Siphons and Traps 2339.3 Timed Petri Nets 2349.3.1 Deterministic Timed Petri Nets 2349.3.1.1 Performance Evaluation Based on DTPNs 2379.3.2 Time Petri Nets 2409.3.2.1 States in a Time Petri Net 2419.3.2.2 Enabling and Firing Conditions of Transitions 2429.3.2.3 Firing Rules 243Exercises 244Suggestions for Reading 250References 25110 Model Checking 25310.1 Introduction to Model Checking 25310.2 Temporal Logic 25410.2.1 Linear Temporal Logic 25610.2.1.1 Syntax of LTL 25610.2.1.2 Parse Trees for LTL Formulas 25710.2.1.3 Semantics of LTL 25810.2.1.4 Equivalencies of LTL Formulas 26210.2.1.5 System Property Specification 26310.2.2 Computation Tree logic 26410.2.2.1 Syntax of CTL 26410.2.2.2 Semantics of CTL 26510.2.2.3 Equivalencies of CTL Formulas 26810.2.3 LTL versus CTL 26810.3 The NuSMV Model Checking Tool 26910.3.1 Description Language 26910.3.1.1 Single-Module SMV Program 26910.3.1.2 Multimodule SMV Program 27110.3.1.3 Asynchronous Systems 27310.3.2 Specifications 27410.3.3 Running NuSMV 27510.4 Real-Time Computation Tree Logic 279Exercises 285Suggestions for Reading 290References 29011 Practical Issues 29311.1 Software Reliability 29311.1.1 Software Faults 29311.1.2 Reliability Measurement 29411.1.3 Improving Software Reliability 29511.1.3.1 Fault Avoidance 29511.1.3.2 Fault Removal 29511.1.3.3 Fault Tolerance 29511.1.3.4 Fault Recovery 29611.2 Software Aging and Rejuvenation 29611.3 Security 29711.3.1 Challenges 29711.3.2 Common Vulnerabilities 29811.3.3 Secure Software Design 29911.4 Safety 30011.5 Power Conservation 301Suggestions for Reading 302References 302Index 305