EMBEDDED SYSTEMS A Contemporary Design Tool

Cover
Title Page
Copyright
Contents
About the Author
Foreword
Preface
Acknowledgment
About the Companion Website
PART 1 HARDWARE AND SOFTWARE INFRASTRUCTURE
Chapter 1 The Hardware Side – Part 1: An Introduction
	1.1 Introduction
	1.2 The Hardware Side – Getting Started
	1.3 The Core Level
		1.3.1 The Microprocessor
		1.3.2 The Microcomputer
		1.3.3 The Microcontroller
		1.3.4 The Digital Signal Processor
	1.4 Representing Information
		1.4.1 Word Size
	1.5 Understanding Numbers
		1.5.1 Resolution
		1.5.2 Propagation of Error
			1.5.2.1 Addition
			1.5.2.2 Multiplication
	1.6 Addresses
	1.7 Instructions
	1.8 Registers – A First Look
	1.9 Embedded Systems – An Instruction Set View
		1.9.1 Instruction Set – Instruction Types
		1.9.2 Data Transfer Instructions
			1.9.2.1 Addressing Modes
		1.9.3 Execution Flow
			1.9.3.1 Sequential Flow
			1.9.3.2 Branch
			1.9.3.3 If‐else Construct
			1.9.3.4 Loop
			1.9.3.5 Procedure or Function Call
			1.9.3.6 Arithmetic and Logic
	1.10 Embedded Systems – A Register View
		1.10.1 The Basic Register
		1.10.2 Register Operations
			1.10.2.1 Write to a Register
			1.10.2.2 Read from a Register
	1.11 Register Transfer Language
	1.12 Register View of a Microprocessor
		1.12.1 The Datapath
		1.12.2 Processor Control
			1.12.2.1 Fetch
			1.12.2.2 Decode
			1.12.2.3 Execute
			1.12.2.4 Next
	1.13 Summary
	1.14 Review Questions
	1.15 Thought Questions
	1.16 Problems
Chapter 2 The Hardware Side – Part 2: Combinational Logic – A Practical View
	2.1 Introduction
	2.2 A Look at Real‐World Gates – Part 1: Signal Levels
		2.2.1 Logic Levels
		2.2.2 A First Look Inside the Logic Gate
		2.2.3 Fan‐In and Fan‐Out
	2.3 A Look at Real‐World Gates – Part 2: Time
		2.3.1 Rise and Fall Times
		2.3.2 Propagation Delay
		2.3.3 Race Conditions and Hazards
			2.3.3.1 Static Hazard
			2.3.3.2 Dynamic Hazard
	2.4 A Look at Real‐World Gates – Part 3: Signal Behavior in the Real World – the Legacy of Early Physicists
	2.5 Look For the Guilty – A First Look at Signal Quality
		2.5.1 Resistors
			2.5.1.1 A Discrete Component First‐Order Resistor Model
		2.5.2 Capacitors
			2.5.2.1 Discrete Component First‐Order Capacitor Model
		2.5.3 Inductors
			2.5.3.1 Magnetic Field Lines – The First Principle
			2.5.3.2 Magnetic Field Lines – The Second Principle
			2.5.3.3 Magnetic Field Lines – The Third Principle
	2.6 Inductance in Action
		2.6.1 Wires and Conductors
	2.7 Logic Circuit Models and Parasitic Components
		2.7.1 First‐Order RC Circuit Model
		2.7.2 First‐Order RL Circuit Model
		2.7.3 Second‐Order Series RLC Circuit Model
		2.7.4 Tristate Drivers
			2.7.4.1 Open Gate Inputs
	2.8 Testing Combinational Circuits – Introduction and Philosophy
	2.9 Modeling, Simulation, and Tools
	2.10 Structural Faults
		2.10.1 Stuck‐at Faults
			2.10.1.1 Stuck‐at‐Zero Faults
			2.10.1.2 Stuck‐at‐One Faults
		2.10.2 Open Circuit Faults
		2.10.3 Bridging Faults
			2.10.3.1 Nonfeedback Bridge Faults
			2.10.3.2 Feedback Bridge Faults
	2.11 Functional Faults
		2.11.1 Hazards and Race Conditions
	2.12 Summary
	2.13 Review Questions
	2.14 Thought Questions
	2.15 Problems
Chapter 3 The Hardware Side – Part 3: Storage Elements and Finite‐State Machines – A Practical View
	3.1 Introduction
	3.2 The Concepts of State and Time
		3.2.1 Time
		3.2.2 State
		3.2.3 State Changes
	3.3 The State Diagram
	3.4 Finite‐State Machines – A Theoretical Model
	3.5 Designing Finite–State Machines – Part 1: Registers
		3.5.1 Storage Registers
		3.5.2 Shift Registers
			3.5.2.1 Shift Right Shift Register
			3.5.2.2 Parallel In/Serial Out – Serial In/Parallel Out Left Shift Registers
		3.5.3 Linear Feedback Shift Registers
	3.6 Designing Finite‐State Machines – Part 2: Counting and Dividing
		3.6.1 Dividers
			3.6.1.1 Divide by Two
		3.6.2 Asynchronous Dividers and Counters
		3.6.3 Synchronous Dividers and Counters
		3.6.4 Johnson Counters
			3.6.4.1 Two‐Stage Johnson Counter
			3.6.4.2 Three‐ or Greater Stage Johnson Counter
	3.7 Practical Considerations – Part 1: Timing in Latches and Flip‐Flops
		3.7.1 Gated Latches
		3.7.2 Flip‐Flops
		3.7.3 Propagation Delays
		3.7.4 Timing Margin
	3.8 Practical Considerations – Part 2: Clocks and Clock Distribution
		3.8.1 The Source
			3.8.1.1 Frequency
			3.8.1.2 Precision and Stability
		3.8.2 Designing a Clock System
			3.8.2.1 Single‐Phase Clocks
			3.8.2.2 Multiple‐Phase Clocks
			3.8.2.3 More Than Four Phases
			3.8.2.4 Multiple Clocks Versus Multiple Phases
			3.8.2.5 Gating the Clock
	3.9 Testing Sequential Circuits
		3.9.1 The Finite‐State Machine Model Revisited
		3.9.2 Sequential Circuit Test – A First Look
			3.9.2.1 Defining Homing and Transfer Sequences
		3.9.3 Scan Design Techniques
		3.9.4 Boundary Scan – Extending Scan‐Path Techniques
	3.10 Summary
	3.11 Review Questions
	3.12 Thought Questions
	3.13 Problems
Chapter 4 Memories and the Memory Subsystem
	4.1 Introduction
	4.2 Classifying Memory
	4.3 A General Memory Interface
	4.4 ROM Overview
		4.4.1 Read Operation
	4.5 Static RAM Overview
		4.5.1 Write Operation
		4.5.2 Read Operation
	4.6 Dynamic RAM Overview
		4.6.1 Read Operation
		4.6.2 Write Operation
		4.6.3 Refresh Operation
	4.7 Chip Organization
	4.8 Terminology
	4.9 A Memory Interface in Detail
	4.10 An SRAM Design
		4.10.1 The Memory Array
		4.10.2 Reading and Writing
		4.10.3 Write
		4.10.4 Read
	4.11 A DRAM Design
		4.11.1 DRAM Timing Analysis
			4.11.1.1 Core Components
		4.11.2 DRAM Refresh
	4.12 The DRAM Memory Interface
		4.12.1 Refresh Timing
		4.12.2 Refresh Address
		4.12.3 Refresh Arbitration
	4.13 The Memory Map
	4.14 Memory Subsystem Architecture
	4.15 Basic Concepts of Caching
		4.15.1 Locality of Reference
		4.15.2 Cache System Architecture
	4.16 Designing a Cache System
		4.16.1 A High‐Level Description
	4.17 Caching – A Direct Mapped Implementation
	4.18 Caching – An Associative Mapping Cache Implementation
	4.19 Caching – A Block‐Set Associative Mapping Cache Implementation
	4.20 Dynamic Memory Allocation
		4.20.1 Swapping
		4.20.2 Overlays
		4.20.3 Multiprogramming
			4.20.3.1 Fixed
			4.20.3.2 Variable Number
	4.21 Testing Memories
		4.21.1 RAM Memory
		4.21.2 ROM Memory
	4.22 Summary
	4.23 Review Questions
	4.24 Thought Questions
	4.25 Problems
Chapter 5 An Introduction to Software Modeling
	5.1 Introduction
	5.2 An Introduction to UML
	5.3 UML Diagrams
	5.4 Use Cases
		5.4.1 Writing a Use Case
	5.5 Class Diagrams
		5.5.1 Class Relationships
			5.5.1.1 Inheritance or Generalization
			5.5.1.2 Interface
			5.5.1.3 Containment
	5.6 Dynamic Modeling with UML
	5.7 Interaction Diagrams
		5.7.1 Call and Return
		5.7.2 Create and Destroy
		5.7.3 Send
	5.8 Sequence Diagrams
	5.9 Fork and Join
	5.10 Branch and Merge
	5.11 Activity Diagram
	5.12 State Chart Diagrams
		5.12.1 Events
		5.12.2 State Machines and State Chart Diagrams
			5.12.2.1 UML State Chart Diagrams
			5.12.2.2 Transitions
			5.12.2.3 Guard Conditions
			5.12.2.4 Composite States
	5.13 Dynamic Modeling with Structured Design Methods
		5.13.1 Brief Introduction to the Structured Design Philosophy
		5.13.2 Data and Control Flow Diagrams
			5.13.2.1 The Elements
	5.14 Summary
	5.15 Review Questions
	5.16 Thought Questions
	5.17 Problems
Chapter 6 The Software Side – Part 1: The C Program
	6.1 Introduction
	6.2 Software and Its Manifestations
		6.2.1 Combining Hardware and Software
		6.2.2 High‐Level Language
		6.2.3 Preprocessor
		6.2.4 Cross Compiler
		6.2.5 Assembler
		6.2.6 Linker and Loader
		6.2.7 Storing
	6.3 An Embedded C Program
		6.3.1 A Program
		6.3.2 Developing Embedded Software
			6.3.2.1 Abstraction
	6.4 C Building Blocks
		6.4.1 Fundamental Data – What's in a Name?
			6.4.1.1 Identifiers in C
		6.4.2 Defining Variables – Giving Them a Name and a Value
		6.4.3 Defining Variables – Giving Them a Type, Scope, and Storage Class
			6.4.3.1 Type
			6.4.3.2 The const Qualifier
			6.4.3.3 Variable Names Revisited
			6.4.3.4 Type Conversions
			6.4.3.5 Scope
			6.4.3.6 Storage Class
	6.5 C Program Structure
		6.5.1 Separate Compilation
		6.5.2 Translation Units
		6.5.3 Linking and Linkage
			6.5.3.1 Linking
			6.5.3.2 Linkage
		6.5.4 Where C Finds Functions
		6.5.5 Makefiles
		6.5.6 Standard and Custom Libraries
		6.5.7 Debug and Release Builds
	6.6 Summary
	6.7 Review Questions
	6.8 Thought Questions
	6.9 Problems
Chapter 7 The Software Side – Part 2: Pointers and Functions
	7.1 Introduction
	7.2 Bitwise Operators
		7.2.1 Bit Manipulation Operations
		7.2.2 Testing, Resetting, and Setting Bits
		7.2.3 Arithmetic Operations
	7.3 Pointer Variables and Memory Addresses
		7.3.1 Getting Started
		7.3.2 Simple Pointer Arithmetic
			7.3.2.1 Pointer Comparison
		7.3.3 Const Pointers
		7.3.4 Generic and NULL Pointers
			7.3.4.1 Generic Pointers
			7.3.4.2 Null Pointers
	7.4 The Function
		7.4.0
			7.4.1.1 Function Header
			7.4.1.2 Function Name
			7.4.1.3 Arguments or Parameter List
			7.4.1.4 Return
			7.4.1.5 The Function Body
		7.4.2 Using a Function
		7.4.3 Pass By Value
		7.4.4 Pass By Reference
		7.4.5 Function Name Scope
		7.4.6 Function Prototypes
		7.4.7 Nesting Functions
	7.5 Pointers to Functions
	7.6 Structures
		7.6.1 The Struct
		7.6.2 Initialization
		7.6.3 Access
		7.6.4 Operations
		7.6.5 Structs as Data Members
			7.6.5.1 Accessing Members
			7.6.5.2 Initialization and Assignment
			7.6.5.3 Functions
		7.6.6 Pointers to Structs
			7.6.6.1 Accessing Members
		7.6.7 Passing Structs and Pointers to Structs
	7.7 The Interrupt
		7.7.1 The Interrupt Control Flow
		7.7.2 The Interrupt Event
		7.7.3 The Interrupt Service Routine – ISR
		7.7.4 The Interrupt Vector Table
		7.7.5 Control of the Interrupt
			7.7.5.1 Enable–Disable
			7.7.5.2 Recognizing an Interrupting Event
			7.7.5.3 Interrupting and Masking an Interrupting Event
	7.8 Summary
	7.9 Review Questions
	7.10 Thought Questions
	7.11 Problems
Part 2 DEVELOPING THE FOUNDATION
Chapter 8 Safety, Security, Reliability, and Robust Design
	8.1 Introduction
	8.2 Safety
	8.3 Reliability
	8.4 Faults, Errors, and Failures
	8.5 Another Look at Reliability
	8.6 Some Real‐World Examples
		8.6.1 Big Word … Small Register
		8.6.2 It's My Turn – Not Yours
		8.6.3 Where Do I Put My Stuff?
	8.7 Single‐Point and Common Mode Failure Model
	8.8 Safe Specifications
	8.9 Safe, Secure, and Robust Designs
		8.9.1 Understanding System Requirements
		8.9.2 Managing Essential Information
		8.9.3 The Review Process
		8.9.4 Bug Lists
		8.9.5 Errors and Exceptions
		8.9.6 Use the Available Tools
	8.10 Safe and Robust Designs – The System
	8.11 System Functional Level Considerations
		8.11.1 Control and Alarm Subsystems
		8.11.2 Memory and Bus Subsystems
		8.11.3 Data Faults and the Communications Subsystem
		8.11.4 Power and Reset Subsystems
		8.11.5 Peripheral Device Subsystems
		8.11.6 Clock Subsystem
	8.12 System Architecture Level Considerations
		8.12.1 Fail Operational2/Fail Operational Capability
			8.12.1.1 Same Design
			8.12.1.2 Alternative Designs
		8.12.2 Reduced Capability
			8.12.2.1 Lightweight Redundancy
			8.12.2.2 Monitor Only
	8.13 Busses – The Subsystem Interconnect
		8.13.1 The Star Configuration
		8.13.2 The Multidrop Bus Configuration
		8.13.3 The Ring Configuration
	8.14 Data and Control Faults – Data Boundary Values
		8.14.1 Type Conformance
		8.14.2 Boundary Values
	8.15 Data and Control Faults – The Communications Subsystem
		8.15.1 Damaged Data
			8.15.1.1 Detectability
			8.15.1.2 Extent
			8.15.1.3 Response
		8.15.2 Managing Damaged Data
			8.15.2.1 Parity
			8.15.2.2 Linear Codes
	8.16 The Power Subsystem
		8.16.1 Full Operation
		8.16.2 Reduced Operation
		8.16.3 Backup Operation
	8.17 Peripheral Devices – Built‐in Self‐Test (BIST)
		8.17.1 Self‐Tests
		8.17.2 Busses
		8.17.3 ROM Memory
		8.17.4 RAM Memory
			8.17.4.1 Peripheral Devices
			8.17.4.2 What to Do If a Test Fails?
	8.18 Failure Modes and Effects Analysis
	8.19 Security – Look Behind You
	8.20 Understanding the Problem – Looking at the System
	8.21 Analyzing the Problem – Looking at Potential Vulnerabilities
	8.22 Understanding the Problem – Looking at the Attacks
		8.22.1 Looking at the Software
		8.22.2 Looking at the Hardware
	8.23 Dealing with the Problem – Protecting Against the Attacks
		8.23.1 Protecting the Software
			8.23.1.1 First Steps
			8.23.1.2 Second Steps
			8.23.1.3 Third Steps
			8.23.1.4 Fourth Steps
		8.23.2 Software Testing Tools
		8.23.3 Protecting the Hardware
			8.23.3.1 First Steps
			8.23.3.2 Second Steps
			8.23.3.3 Third Steps
		8.23.4 Protecting a Network Interface
			8.23.4.1 First Steps
			8.23.4.2 Second Steps
		8.23.5 Firewall
	8.24 Closure
	8.25 Tomorrow
	8.26 Summary
	8.27 Review Questions
	8.28 Thought Questions
	8.29 Problems
Chapter 9 Embedded Systems Design and Development – Hardware–Software Co‐Design
	9.1 Introduction
	9.2 System Design and Development
		9.2.1 Getting Ready – Start Thinking
		9.2.2 Getting Started
	9.3 Life‐Cycle Models
		9.3.1 The Waterfall Model
		9.3.2 The V Cycle Model
		9.3.3 The Spiral Model
		9.3.4 Rapid Prototyping – Incremental
	9.4 Problem Solving – Six Steps To Design
	9.5 Hardware–Software Co‐Design
		9.5.1 The First Steps
		9.5.2 Traditional Embedded Systems Development
	9.6 History
		9.6.1 Advantages of the Co‐Design Methodology
	9.7 Co‐Design Process Overview
	9.8 The Co‐Design Process
	9.9 Laying the Foundation
	9.10 Identifying the Requirements
	9.11 Formulating the Requirements Specification
		9.11.1 The Environment
			9.11.1.1 Characterizing External Entities
		9.11.2 The System
			9.11.2.1 Characterizing the System
	9.12 The System Design Specification
		9.12.1 The System
		9.12.2 Quantifying the System
			9.12.2.0 Quantifying the Specification
	9.13 System Requirements Versus System Design Specifications
	9.14 Executing the Hardware–Software Co‐Design Process
	9.15 Functional Decomposition
		9.15.0 Identifying the Functions
		9.15.0 Functional Decomposition
	9.16 Partitioning and Mapping to an Architecture
		9.16.1 Initial Thoughts
		9.16.2 Coupling
		9.16.3 Cohesion
		9.16.4 A Few More Considerations
		9.16.5 Approaches to Partitioning and Mapping
			9.16.5.1 The Approach
			9.16.5.2 The Method
		9.16.6 Evaluation of a Partition
			9.16.6.0 Mapping to Hardware and Software
	9.17 Architectural Design
		9.17.1 Mapping Functions to Hardware
		9.17.2 Hardware and Software Specification and Design
			9.17.2.0 Developing the Architecture
	9.18 Functional Model Versus Architectural Model
		9.18.1 The Functional Model
		9.18.2 The Architectural Model
		9.18.3 The Need for Both Models
	9.19 Modeling Tools and Languages for Co‐Design
		9.19.1 Why are We Modeling?
		9.19.2 What are We Modeling?
		9.19.3 Characterizing the Model
		9.19.4 Classes of MoCs
			9.19.4.1 Conceptual Model
			9.19.4.2 Analytic Model
		9.19.5 A Look at Some Models
			9.19.5.1 The Logic Circuit
			9.19.5.2 The Random Access Machine – RAM
			9.19.5.3 The Turing Machine
			9.19.5.4 The Pushdown Automaton Machine
			9.19.5.5 The Basic Finite State Machine
			9.19.5.6 Communicating Finite State Machines
			9.19.5.7 Extended FSM
			9.19.5.8 Co‐Design FSM
			9.19.5.9 Program State Machines
			9.19.5.10 UML State Charts
			9.19.5.11 Petri Nets
			9.19.5.12 Kahn Process Network
			9.19.5.13 Control Flow – Data Flow – CDFG Graphs
	9.20 Co‐Synthesis
		9.20.1 Constraints
		9.20.2 Software Synthesis
			9.20.2.1 System Characterization
			9.20.2.2 Scheduling
			9.20.2.3 Synthesis Methods
	9.21 Implementing The System
		9.21.1 Analyzing the System Design
			9.21.1.1 Static Analysis
			9.21.1.2 Dynamic Analysis
	9.22 Co‐Simulation
		9.22.1 Tools Supporting Modeling
		9.22.2 Types of Simulations
		9.22.3 Approaches
			9.22.3.1 Detailed Processor Model
			9.22.3.2 Cycle‐Based Simulation – Bus Model
			9.22.3.3 Instruction Set Architecture – ISA Mode
			9.22.3.4 Compiled Model
			9.22.3.5 Hardware Model
			9.22.3.6 Master Slave Model
			9.22.3.7 Distributed Co‐Simulation
			9.22.3.8 Heterogeneous Modeling – The Ptolemy Project
			9.22.3.9 Domains
			9.22.3.10 Classes of MoCs
	9.23 Co‐Verification
		9.23.1 Hardware–Software Co‐Verification
		9.23.2 Tools Supporting Simulation and Verification
			9.23.2.1 Basic Capabilities
			9.23.2.2 Levels of Abstraction
	9.24 Other Considerations
		9.24.1 Capitalization and Reuse
			9.24.1.1 Capitalization
			9.24.1.2 Reuse
		9.24.2 Requirements Traceability and Management
			9.24.2.1 Requirements Traceability
			9.24.2.2 Requirements Management
	9.25 Archiving the Project
	9.26 Summary
	9.27 Review Questions
	9.28 Thought Questions
	9.29 Problems
Chapter 10 Hardware Test and Debug
	10.1 Introduction
	10.2 Some Vocabulary
	10.3 Putting Together a Strategy
	10.4 Formulating a Plan
	10.5 Formalizing the Plan – Writing a Specification
	10.6 Executing the Plan – The Test Procedure and Test Cases
	10.7 Applying the Strategy – Egoless Design
	10.8 Applying the Strategy – Design Reviews
	10.9 Applying the Strategy – Module Debug and Test
		10.9.1 Black Box Tests
		10.9.2 White Box Tests
		10.9.3 Gray Box Tests
	10.10 Applying the Strategy – The First Steps
		10.10.1 The Parts
		10.10.2 Initial Tests and Measurements – Before Applying Power
		10.10.3 Initial Tests and Measurements – Immediately After Applying Power
	10.11 Applying the Strategy – Debugging and Testing
		10.11.1 The Reset System
		10.11.2 The Clocks and Timing
		10.11.3 The Inputs and Outputs
		10.11.4 Sudden Failure during Debugging
	10.12 Testing and Debugging Combinational Logic
	10.13 Path Sensitizing
		10.13.1 Single Variable–Single Path
			10.13.1.1 Testing
			10.13.1.2 Debugging
		10.13.2 Single Variable–Two Paths
	10.14 Masking and Untestable Faults
	10.15 Single Variable–Multiple Paths
	10.16 Bridge Faults
	10.17 Debugging – Sequential Logic
	10.18 Scan Design Testing
	10.19 Boundary‐Scan Testing
	10.20 Memories and Memory Systems
	10.21 Applying the Strategy – Subsystem and System Test
	10.22 Applying the Strategy – Testing for Our Customer
		10.22.1 Alpha and Beta Tests
		10.22.2 Verification Tests
		10.22.3 Validation Tests
		10.22.4 Acceptance Tests
		10.22.5 Production Tests
	10.23 Self‐Test
		10.23.1 On Demand
		10.23.2 In Background
	10.24 Summary
	10.25 Review Questions
	10.26 Thought Questions
	10.27 Problems
PART 3 DOING THE WORK
Chapter 11 Real‐Time Kernels and Operating Systems
	11.1 Introduction
	11.2 Tasks and Things
	11.3 Programs and Processes
	11.4 The CPU Is a Resource
		11.4.1 Setting a Schedule
		11.4.2 Changing Context
	11.5 Threads – Lightweight and Heavyweight
		11.5.1 A Single Thread
		11.5.2 Multiple Threads
	11.6 Sharing Resources
		11.6.1 Memory Resource Management
			11.6.1.1 System‐Level Management
		11.6.2 Process‐Level Management
		11.6.3 Reentrant Code
	11.7 Foreground / Background Systems
	11.8 The Operating System
	11.9 The Real‐Time Operating System (RTOS)
	11.10 Operating System Architecture
	11.11 Tasks and Task Control Blocks
		11.11.1 The Task
		11.11.2 The Task Control Block
		11.11.3 A Simple Kernel
		11.11.4 Interrupts Revisited
	11.12 Memory Management Revisited
		11.12.1 Duplicate Hardware Context
		11.12.2 Task Control Blocks
		11.12.3 Stacks
			11.12.3.1 Runtime Stack
			11.12.3.2 Application Stacks
			11.12.3.3 Multiprocessing Stacks
	11.13 Summary
	11.14 Review Questions
	11.15 Thought Questions
	11.16 Problems
Chapter 12 Tasks and Task Management
	12.1 Introduction
	12.2 Time, Time‐Based Systems, and Reactive Systems
		12.2.1 Time
		12.2.2 Reactive and Time‐Based Systems
	12.3 Task Scheduling
		12.3.1 CPU Utilization
		12.3.2 Scheduling Decisions
		12.3.3 Scheduling Criteria
			12.3.3.1 Priority
			12.3.3.2 Turnaround Time
			12.3.3.3 Throughput
			12.3.3.4 Waiting Time
			12.3.3.5 Response Time
	12.4 Scheduling Algorithms
		12.4.1 Asynchronous Interrupt Event Driven
		12.4.2 Polled and Polled with a Timing Element
		12.4.3 State Based
		12.4.4 Synchronous Interrupt Event Driven
		12.4.5 Combined Interrupt Event Driven
		12.4.6 Foreground–Background
		12.4.7 Time‐Shared Systems
			12.4.7.1 First‐Come First‐Served
			12.4.7.2 Shortest Job First
			12.4.7.3 Round Robin
		12.4.8 Priority Schedule
			12.4.8.1 Rate‐Monotonic
			12.4.8.2 Earliest Deadline
			12.4.8.3 Least Laxity
			12.4.8.4 Maximum Urgency
	12.5 Real‐Time Scheduling Considerations
	12.6 Algorithm Evaluation
		12.6.1 Deterministic Modeling
		12.6.2 Queuing Models
		12.6.3 Simulation
		12.6.4 Implementation
	12.7 Tasks, Threads, and Communication
		12.7.1 Getting Started
		12.7.2 Intertask / Interthread Communication
		12.7.3 Shared Variables
			12.7.3.1 Global Variables
			12.7.3.2 Shared Buffer
			12.7.3.3 Shared Double Buffer – Ping‐Pong Buffer
			12.7.3.4 Ring Buffer
			12.7.3.5 Mailbox
		12.7.4 Messages
			12.7.4.1 Communication
			12.7.4.2 Buffering
	12.8 Task Cooperation, Synchronization, and Sharing
		12.8.1 Critical Sections and Synchronization
		12.8.2 Flags
		12.8.3 Token Passing
		12.8.4 Interrupts
		12.8.5 Semaphores
		12.8.6 Process Synchronization
		12.8.7 Spin Lock and Busy Waiting
		12.8.8 Counting Semaphores
	12.9 Talking and Sharing in Space
		12.9.1 The Bounded Buffer Problem
		12.9.2 The Readers and Writers Problem
	12.10 Monitors
		12.10.1 Condition Variables
		12.10.2 Bounded Buffer Problem with Monitor
	12.11 Starvation
	12.12 Deadlocks
	12.13 Summary
	12.14 Review Questions
	12.15 Thought Questions
	12.16 Problems
Chapter 13 Deadlocks
	13.1 Introduction
	13.2 Sharing Resources
	13.3 System Model
	13.4 Deadlock Model
		13.4.1 Necessary Conditions
	13.5 A Graph Theoretic Tool – The Resource Allocation Graph
	13.6 Handling Deadlocks
	13.7 Deadlock Prevention
		13.7.1 Mutual Exclusion
		13.7.2 Hold and Wait
		13.7.3 No Preemption
		13.7.4 Circular Wait
	13.8 Deadlock Avoidance
		13.8.1 Algorithms Based on the Resource Allocation Graph
		13.8.2 Banker's Algorithm and Safe States
	13.9 Deadlock Detection
		13.9.1 Detection in a Single‐Instance Environment
		13.9.2 Deadlock Recovery
			13.9.2.1 Task Termination
			13.9.2.2 Resource Preemption
	13.10 Summary
	13.11 Review Questions
	13.12 Thought Questions
	13.13 Problems
Chapter 14 Performance Analysis and Optimization
	14.1 Introduction
	14.2 Getting Started
	14.3 Performance or Efficiency Measures
		14.3.1 Introduction
		14.3.2 The System
		14.3.3 Some Limitations
	14.4 Complexity Analysis – A High‐Level Measure
	14.5 The Methodology
		14.5.1 A Simple Experiment
		14.5.2 Working with Big Numbers
		14.5.3 Asymptotic Complexity
	14.6 Comparing Algorithms
		14.6.1 Big‐O Notation
		14.6.2 Big‐O Arithmetic
	14.7 Analyzing Code
		14.7.1 Constant Time Statements
		14.7.2 Looping Constructs
			14.7.2.1 For Loops
			14.7.2.2 While Loops
		14.7.3 Sequences of Statements
		14.7.4 Conditional Statements
		14.7.5 Function Calls
	14.8 Analyzing Algorithms
		14.8.1 Analyzing Search
			14.8.1.1 Linear Search
			14.8.1.2 Binary Search
		14.8.2 Analyzing Sort
			14.8.2.1 Selection Sort
			14.8.2.2 Quick Sort
	14.9 Analyzing Data Structures
		14.9.1 Array
		14.9.2 Linked List
	14.10 Instructions in Detail
		14.10.1 Getting Started
		14.10.2 Flow of Control
			14.10.2.1 Sequential
			14.10.2.2 Branch
			14.10.2.3 Loop
			14.10.2.4 Function Call
		14.10.3 Analyzing the Flow of Control – Two Views
			14.10.3.1 Sequential Flow
			14.10.3.2 Branch
			14.10.3.3 Loop
			14.10.3.4 Function Call
			14.10.3.5 Co‐routine
			14.10.3.6 Interrupt Call
	14.11 Time, etc. – A More Detailed Look
		14.11.1 Metrics
	14.12 Response Time
		14.12.1 Polled Loops
		14.12.2 Co‐routine
		14.12.3 Interrupt‐Driven Environment
			14.12.3.1 Preemptive Schedule
			14.12.3.2 Nonpreemptive Schedule
		14.12.4 Meeting Real‐Time Constraints
			14.12.4.1 Deadline Monotonic Analysis
			14.12.4.2 Vocabulary
			14.12.4.3 Analysis
			14.12.4.4 Priority Ceiling Protocol
	14.13 Time Loading
		14.13.1 Instruction Counting
		14.13.2 Simulation
			14.13.2.1 Models
		14.13.3 Timers
		14.13.4 Instrumentation
	14.14 Memory Loading
		14.14.1 Memory Map
		14.14.2 Designing a Memory Map
			14.14.2.1 Instruction/Firmware Area
			14.14.2.2 RAM Area
			14.14.2.3 Stack Area
	14.15 Evaluating Performance
		14.15.1 Early Stages
		14.15.2 Mid‐stages
		14.15.3 Later Stages
	14.16 Thoughts on Performance Optimization
		14.16.1 Questions to Ask
	14.17 Performance Optimization
		14.17.1 Common Mistakes
	14.18 Tricks of the Trade
	14.19 Hardware Accelerators
	14.20 Introduction – Target Low Power
	14.21 Low Power – A High‐Level View
		14.21.1 Zero Power Consumption
		14.21.2 Static Power Consumption
			14.21.2.1 Sources of Static Power Consumption
			14.21.2.2 Addressing Static Power Consumption
		14.21.3 Dynamic Power Consumption
			14.21.3.1 Sources of Dynamic Power Consumption – Hardware
			14.21.3.2 Sources of Dynamic Power Consumption – Software
	14.22 Addressing Dynamic Power Consumption – Hardware
		14.22.1 Power Management Schemes – Hardware
		14.22.2 Advanced Configuration and Power Interface (ACPI)
		14.22.3 Dynamic Voltage and Frequency Scaling
	14.23 Addressing Dynamic Power Consumption – Software
		14.23.1 Measuring Power Consumption
		14.23.2 Caches and Performance
	14.24 Trade‐Offs
	14.25 Summary
	14.26 Review Questions
	14.27 Thought Questions
	14.28 Problems
Part 4 DEVELOPING THE FOUNDATION
Chapter 15 Working Outside of the Processor I: A Model of Interprocess Communication
	15.1 Communication and Synchronization with the Outside World
	15.2 First Steps: Understanding the Problem
	15.3 Interprocess Interaction Revisited
	15.4 The Model
		15.4.1 Information
		15.4.2 Places
		15.4.3 Control and Synchronization
		15.4.4 Transport
	15.5 Exploring the Model
		15.5.1 The Transport Mechanism
			15.5.1.1 The Interconnection Topology
			15.5.1.2 Star
			15.5.1.3 Ring
		15.5.2 Control and Synchronization
		15.5.3 Information Flow
			15.5.3.1 Direction of Flow
			15.5.3.2 Magnitude of the Flow
			15.5.3.3 I/O Timing
			15.5.3.4 Software Device Drivers
		15.5.4 Places
	15.6 Summary
	15.7 Review Questions
	15.8 Thought Questions
Chapter 16 Working Outside of the Processor I: Refining the Model of Interprocess Communication
	16.1 Communication and Synchronization with the Outside World
	16.2 The Local Device Model
		16.2.1 Control, Synchronization, and Places
			16.2.1.1 A Serial Model
			16.2.1.2 A Parallel Model
		16.2.2 Information – Data
		16.2.3 Transport
	16.3 Implementing the Local Device Model – A First Step
		16.3.1 An Overview
			16.3.1.1 Main Memory Address Space
			16.3.1.2 I/O Ports
			16.3.1.3 Peripheral Processor
		16.3.2 Main Memory Address Space – Memory‐Mapped I/O
			16.3.2.1 Address Bus
			16.3.2.2 Data Bus
			16.3.2.3 Control Bus
			16.3.2.4 Read
			16.3.2.5 Write
			16.3.2.6 Bidirectional Bus
		16.3.3 I/O Ports – Program‐Controlled I/O
		16.3.4 The Peripheral Processor
	16.4 Implementing the Local Device Model – A Second Step
		16.4.1 Information Interchange – An Event
		16.4.2 Information Interchange – A Shared Variable
		16.4.3 Information Interchange – A Message
	16.5 Implementing an Event‐Driven Exchange – Interrupts and Polling
		16.5.1 Polling
		16.5.2 Interrupts
			16.5.2.1 Single Interrupt Line with Single Device
			16.5.2.2 Single Interrupt Line with Multiple Devices
			16.5.2.3 Multiple Interrupt Lines
		16.5.3 Masking Interrupts
	16.6 A Message
		16.6.1 Asynchronous Information Exchange
			16.6.1.1 Strobes
			16.6.1.2 Strobe with Acknowledge
			16.6.1.3 Full Handshake
			16.6.1.4 Resynchronization
			16.6.1.5 Analysis
		16.6.2 Synchronous Information Exchange
			16.6.2.1 Bit Synchronization
	16.7 The Remote Device Model
		16.7.1 Places and Information
		16.7.2 Control and Synchronization
		16.7.3 Transport
	16.8 Implementing the Remote Device Model – A First Step
		16.8.1 The OSI and TCP/IP Protocol Stacks
			16.8.1.1 OSI – Physical Layer
			16.8.1.2 OSI – Data Link Layer
			16.8.1.3 TCP/IP – Host to Network
			16.8.1.4 OSI – Network Layer
			16.8.1.5 TCP/IP – Internet Layer
			16.8.1.6 OSI – Transport Layer
			16.8.1.7 TCP/IP – Transport Layer
			16.8.1.8 OSI – Session Layer
			16.8.1.9 OSI – Presentation Layer
			16.8.1.10 OSI – Application Layer
			16.8.1.11 TCP/IP – Application Layer
		16.8.2 The Models
			16.8.2.1 The Client–Server Model
			16.8.2.2 The Peer‐to‐Peer Model
			16.8.2.3 The Group Multicast Model
	16.9 Implementing the Remote Device Model – A Second Step
		16.9.1 The Messages
		16.9.2 The Message Structure
		16.9.3 Message Control and Synchronization
			16.9.3.1 The Header
			16.9.3.2 The Transfer Scheme
	16.10 Working with Remote Tasks
		16.10.1 Preliminary Thoughts on Working with Remote Tasks
			16.10.1.1 Local vs. Remote Addresses and Data
			16.10.1.2 Repeated Task Execution
			16.10.1.3 Node Failure, Link Failure, Message Loss
		16.10.2 Procedures and Remote Procedures
			16.10.2.1 Calling a Remote Procedure – RPC Semantics
			16.10.2.2 The Transport
			16.10.2.3 Message Source and Destination
			16.10.2.4 The Protocol
			16.10.2.5 RPC Interface Definition
		16.10.3 Node Failure, Link Failure, Message Loss
			16.10.3.1 Node Failure and Loss
			16.10.3.2 Message Loss
	16.11 Group Multicast Revisited
		16.11.1 Atomic Multicast
		16.11.2 Reliable Multicast
	16.12 Connecting to Distributed Processes – Pipes, Sockets, and Streams
		16.12.1 Pipes
		16.12.2 Sockets
		16.12.3 Stream Communication
	16.13 Summary
	16.14 Review Questions
	16.15 Thought Questions
	16.16 Problems
Chapter 17 Working Outside of the Processor II: Interfacing to Local Devices
	17.1 Shared Variable I/O – Interfacing to Peripheral Devices
	17.2 The Shared Variable Exchange
	17.3 Generating Analog Signals
		17.3.1 Binary Weighted Digital‐to‐Analog Converter
		17.3.2 R/2R Ladder Digital‐to‐Analog Converter
	17.4 Common Measurements
		17.4.1 Voltage
		17.4.2 Current
		17.4.3 Resistance
	17.5 Measuring Voltage
		17.5.1 Dual Slope Analog‐to‐Digital Conversion
		17.5.2 Successive Approximation Analog‐to‐Digital Conversion
			17.5.2.1 Sample and Hold
		17.5.3 VCO Analog‐to‐Digital Conversion
	17.6 Measuring Resistance
	17.7 Measuring Current
	17.8 Measuring Temperature
		17.8.1 Sensors
		17.8.2 Making the Measurement
		17.8.3 Working with Nonlinear Devices
	17.9 Generating Digital Signals
		17.9.1 Motors and Motor Control
		17.9.2 DC Motors
		17.9.3 Servo Motors
		17.9.4 Stepper Motors
	17.10 Controlling DC and Servo Motors
		17.10.1 DC Motors
		17.10.2 Servo Motors
		17.10.3 Controlling Stepper Motors
		17.10.4 Motor Drive Circuitry
		17.10.5 Motor Drive Noise
	17.11 LEDs and LED Displays
		17.11.1 Individual LEDs
		17.11.2 Multi‐LED Displays
	17.12 Measuring Digital Signals
		17.12.1 The Approach
		17.12.2 Working with Asynchronous Signals
		17.12.3 Buffering Input Signals
		17.12.4 Inside vs. Outside
		17.12.5 Measuring Frequency and Time Interval
			17.12.5.1 Measuring the Period – An Internal Implementation
			17.12.5.2 Measuring the Period – An External Implementation
			17.12.5.3 Counting for a Known Interval – An Internal Implementation
			17.12.5.4 Counting for a Known Interval – An External Implementation
	17.13 Summary
	17.14 Review Questions
	17.15 Thought Questions
	17.16 Problems
Chapter 18 Working Outside of the Processor III: Interfacing to Remote Devices
	18.1 Common Network‐Based I/O Architectures
	18.2 Network‐Based Systems
	18.3 RS‐232/EIA‐232 – Asynchronous Serial Communication
		18.3.1 Introduction
		18.3.2 The EIA‐232 Standard
			18.3.2.1 What It Is …
			18.3.2.2 What they Think It Is …
		18.3.3 EIA‐232 Addressing
		18.3.4 Asynchronous Serial Communication
		18.3.5 Configuring the Interface
		18.3.6 Data Recovery and Timing
		18.3.7 EIA‐232 Interface Signals
		18.3.8 An Implementation
	18.4 The Universal Serial Bus – Synchronous Serial Communication
		18.4.1 Background
		18.4.2 The Universal Serial Bus Architecture
		18.4.3 The Universal Serial Bus Protocol
		18.4.4 USB Devices
		18.4.5 Transfer Types
		18.4.6 Device Descriptors
		18.4.7 Network Configuration
		18.4.8 USB Transactions
		18.4.9 USB Interface Signals
		18.4.10 The Physical Environment
			18.4.10.1 Low‐Speed Cables
			18.4.10.2 High‐Speed Cables
			18.4.10.3 Cables and Cable Power
		18.4.11 Detecting Device Attachment and Speed
		18.4.12 Differential Pair Signaling
		18.4.13 Implementation
	18.5 I2C – A Local Area Network
		18.5.1 The Architecture
		18.5.2 Electrical Considerations
		18.5.3 Basic Operation
		18.5.4 Flow of Control
		18.5.5 Multiple Masters
			18.5.5.1 Arbitration
			18.5.5.2 Synchronization
		18.5.6 Using the I2C Bus
	18.6 The Controller Area Network – The CAN Bus
		18.6.1 The Architecture
		18.6.2 Electrical Considerations
		18.6.3 Message Types
		18.6.4 Message Format
		18.6.5 Basic Operation
			18.6.5.1 Synchronization
			18.6.5.2 Error Management
			18.6.5.3 Transmission and Arbitration
		18.6.6 Using the CAN Bus
	18.7 Summary
	18.8 Review Questions
	18.9 Thought Questions
	18.10 Problems
Chapter 19 Programmable Logic Devices
	19.1 Introduction
	19.2 Why Use Programmable Logic Devices?
	19.3 Basic Concepts
	19.4 Basic Configurations
		19.4.1 The (P)ROM
		19.4.2 Programmable Array Logic – PAL
		19.4.3 Programmable Logic Array – PLA
		19.4.4 Programmable Logic Sequencer – PLS
		19.4.5 PLA vs. PAL vs. (P)ROM
	19.5 Programmable and Reprogrammable Technologies
		19.5.1 Programmable Technologies
		19.5.2 Reprogrammable Technologies
	19.6 Architectures
		19.6.1 PLDs
		19.6.2 CPLD
		19.6.3 FPGAs
	19.7 The Design Process
	19.8 Design Examples
		19.8.1 Lane Departure Detection Implementation and Acceleration
			19.8.1.1 Introduction
			19.8.1.2 Requirements
			19.8.1.3 Design
			19.8.1.4 Results
			19.8.1.5 Section Summary
		19.8.2 Local Area Tracking System – LATS with uCLinux™ OS
			19.8.2.1 Introduction
			19.8.2.2 Requirements
			19.8.2.3 System Description
			19.8.2.4 Design Procedure
			19.8.2.5 Test Plan
	19.9 Summary
	19.10 Review Questions
	19.11 Thought Questions
Chapter 20 Practical Considerations Signal Behavior in the Real World – Part 1 – Noise and Crosstalk
	20.1 Introduction – The Real World Again
	20.2 Noise
	20.3 Power Supply and Ground Noise
		20.3.1 Common Path Noise
		20.3.2 Power Distribution Wiring
			20.3.2.1 Resistance
			20.3.2.2 Inductance
		20.3.3 Board Level Bypass
			20.3.3.1 Computing the Board Level Bypass Capacitor
		20.3.4 Local Bypass Capacitors
			20.3.4.1 Computing the Local Bypass Capacitors
		20.3.5 Power and Ground Planes
	20.4 Crosstalk and Loops
		20.4.1 Crosstalk
			20.4.1.1 Preventing or Reducing Crosstalk
		20.4.2 Loops
	20.5 Summary
	20.6 Review Questions
	20.7 Problems
Chapter 21 Practical Considerations Signal Behavior in the Real World – Part 2 – High‐Speed Signaling
	21.1 Introduction – The Real World Yet Again
	21.2 The Problem
		21.2.1 Terminology
			21.2.1.1 Noise
			21.2.1.2 Switching Noise
			21.2.1.3 Crosstalk
			21.2.1.4 Ringing
			21.2.1.5 Attenuation or Loss
			21.2.1.6 Jitter
			21.2.1.7 Period Jitter
			21.2.1.8 Cycle‐to‐Cycle Jitter
			21.2.1.9 Nth‐cycle Jitter
			21.2.1.10 Aperture Time
			21.2.1.11 Reflection
			21.2.1.12 Ground Bounce
			21.2.1.13 Transmitter Output Timing Jitter
			21.2.1.14 Capacitive Loading
	21.3 The Working Environment
		21.3.1 The Signaling Environment
		21.3.2 The PCB Environment
			21.3.2.1 Microstrip
			21.3.2.2 Stripline
			21.3.2.3 Signal Propagation
			21.3.2.4 Distributed Versus Lumped
		21.3.3 Point‐to‐Point Wiring
			21.3.3.1 Signal Distortion
		21.3.4 Electromagnetic Interference in Point‐to‐Point Wiring
			21.3.4.1 EMI to Crosstalk in Point‐to‐Point Wiring
	21.4 The Transmission Line
		21.4.1 The Lossless Transmission Line
		21.4.2 The Finite Transmission Line
			21.4.2.1 Transient Input
		21.4.3 Reflections – Termination Schemes
		21.4.4 Unterminated Signal Path
			21.4.4.1 Low Source Impedance – TTL/ECL Drivers
			21.4.4.2 High Source Impedance – CMOS Drivers
		21.4.5 Parallel Termination – End Terminated
			21.4.5.1 End Terminated – Biased Termination
			21.4.5.2 End Terminated – Split Termination
		21.4.6 Source Terminated – Series Termination
	21.5 Differential Signaling
		21.5.1 Environment
	21.6 Signals in the Nonideal (Real) World
	21.7 Other Considerations
	21.8 Examining the Environment
		21.8.1 Test Equipment
		21.8.2 The Eye Diagram
			21.8.2.1 Generating the Eye Diagram
			21.8.2.2 Interpreting the Eye Diagram
	21.9 Back of the Envelope Examination
		21.9.1 A First Step Check List
		21.9.2 Routing and Topology
			21.9.2.1 Topology Alternatives
	21.10 Summary
	21.11 Review Questions
	21.12 Thought Questions
	21.13 Problems
Appendix A Verilog Overview: The Verilog Hardware Description Language
	A.1 Introduction
	A.2 An Overview of a Verilog Program
	A.3 Creating a Verilog Program
		A.3.1 Some Concepts in a Verilog Source File
		A.3.2 Modules
			A.3.2.1 Module Name
			A.3.2.2 Inputs and Outputs Declarations
			A.3.2.3 Nets and Variables
			A.3.2.4 Declaring Multibit Signals
			A.3.2.5 Subsets of Multibit Expressions
			A.3.2.6 $display and $monitor Statements
			A.3.2.7 $stop and $finish Statements
			A.3.2.8 $time Statement
	A.4 Three Models – The Gate Level, the Dataflow, and the Behavioral
		A.4.1 The Structural/Gate‐Level Model
			A.4.1.1 Creating Modules
			A.4.1.2 Using Modules
			A.4.1.3 Delays
			A.4.1.4 Defining Constants
		A.4.2 The Dataflow Model
			A.4.2.1 Continuous Assignment
			A.4.2.2 Delays
			A.4.2.3 Operators
		A.4.3 The Behavioral Model
			A.4.3.1 Program Structure
			A.4.3.2 Procedural Assignment
			A.4.3.3 Delays
			A.4.3.4 Flow of Control
	A.5 Testing and Verifying the Circuit
		A.5.1 The Circuit Module
		A.5.2 The Test Module
			A.5.2.1 Clocks and Resets
		A.5.3 The Test Bench
		A.5.4 Performing the Simulation
	A.6 Summary
Further Reading
Index
EULA