Table of contents for Embedded systems : a contemporary design tool / James K. Peckol.

Bibliographic record and links to related information available from the Library of Congress catalog.

Note: Contents data are machine generated based on pre-publication provided by the publisher. Contents may have variations from the printed book or be incomplete or contain other coding.


Counter
Embedded Systems - A Contemproary Design Tool Table of Contents
- i - Copyright 2006 Oxford Consulting Ltd
Preface................................................................................................................................xix
Chapter 0 Introduction to Embedded Systems ................................................................32
0.1 Embedded Systems ..............................................................................................35
0.1.1 What is an Embedded System? .............................................................35
0.1.2 Building an Embedded System .............................................................37
0.2 The Embedded Design and Development Process ..............................................41
0.3 Summary..............................................................................................................48
0.4 Review Questions ................................................................................................50
0.5 Thought Questions...............................................................................................51
Chapter 1 The Hardware Side - Part 1.............................................................................52
An Introduction
1.0 Introduction..........................................................................................................53
1.1 The Hardware Side ? Getting Started ..................................................................55
1.2 The Core Level ....................................................................................................55
1.2.1 The Microprocessor...............................................................................58
1.2.2 The Microcomputer...............................................................................59
1.2.3 The Microcontroller...............................................................................60
1.2.4 The Digital Signal Processor .................................................................60
1.3 Representing Information ....................................................................................62
1.4 Understanding Numbers ......................................................................................63
1.4.1 Resolution..............................................................................................63
1.4.2 Propagation of Error ..............................................................................65
1.5 Addresses .............................................................................................................67
1.6 Instructions...........................................................................................................69
1.7 Registers - A First Look.......................................................................................72
1.8 Embedded Systems ? An Instruction Set View ...................................................75
1.8.1 Instruction Set ? Instruction Types........................................................76
1.8.2 Data Transfer Instructions .....................................................................77
1.8.3 Execution Flow......................................................................................87
1.9 Embedded Systems ? A Register View ...............................................................97
1.9.1 The Basic Register.................................................................................98
1.9.2 Register Operations ...............................................................................99
1.10 Register Transfer Language.................................................................................100
1.11 Register View of a Microprocessor .....................................................................102
1.11.1 The Datapath .........................................................................................103
1.11.2 Processor Control ..................................................................................104
1.12 Summary..............................................................................................................112
1.13 Review Questions ................................................................................................113
1.14 Thought Questions...............................................................................................116
1.15 Problems ..............................................................................................................119
Chapter 2 The Hardware Side ? Part 2............................................................................133
Embedded Systems - A Contemproary Design Tool Table of Contents
- ii - Copyright 2006 Oxford Consulting Ltd
Combinational Logic - A Practical View
2.0 Introduction..........................................................................................................134
2.1 A Look at Real World Gates ? Part 1 Signal Levels ...........................................135
2.1.1 Logic Levels ..........................................................................................136
2.1.2 A First Look Inside the Logic Gate.......................................................139
2.1.3 Fan In and Fan Out ................................................................................140
2.2 A Look at Real World Gates ? Part 2 Time.........................................................146
2.2.1 Rise and Fall Times ...............................................................................146
2.2.2 Propagation Delay .................................................................................147
2.2.3 Race Conditions and Hazards................................................................150
2.3 A Look at Real World Gates ? Part 3 The Legacy of Early Physicists ...............153
2.3.1 Resistors ................................................................................................154
2.3.2 Capacitors ..............................................................................................158
2.4 Logic Circuits and Parasitic Components............................................................161
2.4.1 First Order RC Circuits .........................................................................161
2.4.2 Second Order RLC Circuits...................................................................166
2.5 Testing Combinational Circuits - Introduction and Philosophy ..........................169
2.6 Modeling, Simulation, and Tools ........................................................................170
2.7 Structural Faults...................................................................................................171
2.7.1 Stuck-at Faults .......................................................................................171
2.7.2 Open Circuit Faults................................................................................174
2.7.3 Bridging Faults ......................................................................................175
2.8 Functional Faults..................................................................................................179
2.9 Summary..............................................................................................................180
2.10 Review Questions ................................................................................................181
2.11 Thought Questions...............................................................................................184
2.12 Problems ..............................................................................................................187
Chapter 3 The Hardware Side - Part 3.............................................................................198
Storage Elements and Finite State Machines -
A Practical View
3.0 Introduction..........................................................................................................199
3.1 The Concepts of State and Time..........................................................................200
3.2 The State Diagram ...............................................................................................201
3.3 Finite State Machines ? A Theoretical Model .....................................................202
3.4 Designing Finite State Machines ? Part 1 Registers............................................205
3.4.1 Storage Registers ...................................................................................205
3.4.2 Shift Registers .......................................................................................206
3.4.3 Linear Feedback Shift Registers............................................................212
3.5 Designing Finite State Machines ? Part 2 ? Counting and Dividing...................215
3.5.1 Dividers .................................................................................................215
3.5.2 Asynchronous Dividers and Counters ...................................................216
3.5.3 Synchronous Dividers and Counters .....................................................219
3.5.4 Johnson Counters...................................................................................220
Embedded Systems - A Contemproary Design Tool Table of Contents
- iii - Copyright 2006 Oxford Consulting Ltd
3.6 Practical Considerations ? Part 1 Timing in Latches and Flip-Flops ..................224
3.6.1 Gated Latches ........................................................................................224
3.6.2 Flip-Flops ..............................................................................................225
3.6.3 Propagation Delays................................................................................225
3.6.4 Timing Margin.......................................................................................226
3.7 Practical Considerations ? Part 2 Clocks and Clock Distribution .......................229
3.7.1 The Source.............................................................................................229
3.7.2 Designing a Clock System.....................................................................232
3.8 Testing Sequential Circuits..................................................................................238
3.8.1 The Finite State Machine Model Revisited ...........................................239
3.8.2 Sequential Circuit Test ? A First Look..................................................239
3.8.3 Scan Design Techniques........................................................................247
3.8.4 Boundary Scan ? Extending Scan Path Techniques..............................248
3.9 Summary..............................................................................................................253
3.10 Review Questions ................................................................................................254
3.11 Thought Questions...............................................................................................257
3.12 Problems ..............................................................................................................261
Chapter 4 Memories and the Memory Subsystem...........................................................279
4.0 Introduction..........................................................................................................280
4.1 Classifying Memory ............................................................................................281
4.2 A General Memory Interface...............................................................................282
4.3 ROM Overview....................................................................................................284
4.3.1 Read Operation......................................................................................285
4.4 Static Ram Overview ...........................................................................................286
4.4.1 Write Operation .....................................................................................286
4.4.2 Read Operation......................................................................................286
4.5 Dynamic RAM Overview....................................................................................287
4.5.1 Read Operation......................................................................................287
4.5.2 Write Operation .....................................................................................288
4.5.3 Refresh Operation..................................................................................288
4.6 Chip Organization................................................................................................290
4.7 Terminology.........................................................................................................290
4.8 A Memory Interface in Detail..............................................................................293
4.9 An SRAM Design................................................................................................294
4.10 A DRAM Design .................................................................................................298
4.10.1 DRAM Timing Analysis .......................................................................300
4.10.2 DRAM Refresh......................................................................................301
4.11 The DRAM Memory Interface ............................................................................302
4.11.1 Refresh Timing......................................................................................302
4.11.2 Refresh Address.....................................................................................303
4.11.3 Refresh Arbitration................................................................................305
4.12 The Memory Map ................................................................................................308
Embedded Systems - A Contemproary Design Tool Table of Contents
- iv - Copyright 2006 Oxford Consulting Ltd
4.13 Memory Subsystem Architecture ........................................................................309
4.14 Basic Concepts of Caching ..................................................................................310
4.14.1 Locality of Reference ............................................................................310
4.14.2 Cache System Architecture ...................................................................312
4.15 Designing a Cache System ..................................................................................312
4.15.1 A High Level Description .....................................................................313
4.16 Caching - A Direct Mapped Implementation ......................................................314
4.17 Caching ? An Associative Mapping Cache Implementation...............................318
4.18 Caching ? A Block-Set Associative Mapping Cache Implementation................321
4.19 Dynamic Memory Allocation ..............................................................................323
4.19.1 Swapping ...............................................................................................323
4.19.2 Overlays.................................................................................................324
4.19.3 Multiprogramming ................................................................................324
4.20 Testing Memories ................................................................................................326
4.20.1 RAM Memory .......................................................................................328
4.20.2 ROM Memory .......................................................................................331
4.21 Summary..............................................................................................................333
4.22 Review Questions ................................................................................................334
4.23 Thought Questions...............................................................................................337
4.24 Problems ..............................................................................................................340
Chapter 5 An Introduction to Software Modeling .............................................................346
5.0 Introduction..........................................................................................................347
5.1 An Introduction to UML......................................................................................348
5.2 UML Diagrams ....................................................................................................349
5.3 Use Cases.............................................................................................................351
5.4 Class Diagrams ....................................................................................................353
5.4.1 Inheritance or Generalization ................................................................355
5.4.2 Interface.................................................................................................355
5.4.3 Containment ..........................................................................................356
5.5 Dynamic Modeling with UML ............................................................................357
5.6 Interaction Diagrams............................................................................................358
5.6.1 Call and Return......................................................................................359
5.6.2 Create and Destroy ................................................................................359
5.6.3 Send .......................................................................................................360
5.7 Sequence Diagrams..............................................................................................360
5.8 Fork and Join .......................................................................................................361
5.9 Branch and Merge................................................................................................362
5.10 Activity Diagram .................................................................................................363
5.11 State Chart Diagrams ..........................................................................................363
5.11.1 Events ....................................................................................................363
5.11.2 State Machines and State Chart Diagrams ...........................................364
5.12 Dynamic Modeling with Structured Design Methods .........................................368
Embedded Systems - A Contemproary Design Tool Table of Contents
- v - Copyright 2006 Oxford Consulting Ltd
5.12.1 Brief Introduction to the Structured Design Philosophy .......................368
5.12.2 Data and Control Flow Diagrams..........................................................369
5.13 Summary..............................................................................................................373
5.14 Review Questions ................................................................................................374
5.15 Thought Questions...............................................................................................377
5.16 Problems ..............................................................................................................380
Chapter 6 The Software Side - Part 1 ..............................................................................383
The C Program
6.0 Introduction..........................................................................................................384
6.1 Software and Its Manifestations ..........................................................................384
6.1.1 Combining Hardware and Software ......................................................385
6.1.2 High Level Language ............................................................................386
6.1.3 Preprocessor ..........................................................................................387
6.1.4 Cross Compiler......................................................................................387
6.1.5 Assembler..............................................................................................388
6.1.6 Linker and Loader .................................................................................388
6.1.7 Storing ...................................................................................................391
6.2 An Embedded C Program ....................................................................................391
6.2.1 A Program .............................................................................................391
6.2.2 Developing Embedded Software...........................................................392
6.3 C Building Blocks................................................................................................393
6.3.1 Fundamental Data ? What?s in a Name?...............................................393
6.3.2 Defining Variables ? Giving Them a Name and a Value......................394
6.3.3 Defining Variables ? Giving them a Type, Scope, and Storage Class ..396
6.4 C Program Structure ............................................................................................419
6.4.1 Separate Compilation ............................................................................419
6.4.2 Translation Units ...................................................................................420
6.4.3 Linking and Linkage..............................................................................421
6.4.4 Where C Finds Functions ......................................................................424
6.4.5 Make Files .............................................................................................424
6.4.6 Standard and Custom Libraries .............................................................426
6.4.7 Debug and Release Builds.....................................................................426
6.5 Summary..............................................................................................................427
6.6 Review Questions ................................................................................................428
6.7 Thought Questions...............................................................................................430
6.8 Problems ..............................................................................................................433
Chapter 7 The Software Side - Part 2 ..............................................................................438
Pointers and Functions
7.0 Introduction..........................................................................................................439
7.1 Bitwise Operators ................................................................................................439
7.1.1 Bit Manipulation Operations .................................................................441
7.1.2 Testing, Resetting, and Setting Bits ......................................................441
Embedded Systems - A Contemproary Design Tool Table of Contents
- vi - Copyright 2006 Oxford Consulting Ltd
7.1.3 Arithmetic Operations ...........................................................................446
7.2 Pointer Variables and Memory Addresses...........................................................447
7.2.1 Getting Started.......................................................................................447
7.2.2 Simple Pointer Arithmetic.....................................................................453
7.2.3 Const Pointers........................................................................................458
7.2.4 Generic and NULL Pointers..................................................................460
7.3 The Function ........................................................................................................461
7.3.1 Using a Function....................................................................................463
7.3.2 Pass by Value ........................................................................................468
7.3.3 Pass by Reference..................................................................................471
7.3.4 Function Name Scope............................................................................472
7.3.5 Function Prototypes...............................................................................473
7.3.6 Nesting Functions..................................................................................475
7.4 Pointers to Functions ...........................................................................................476
7.5 Structures .............................................................................................................482
7.5.1 The Struct ..............................................................................................483
7.5.2 Initialization...........................................................................................486
7.5.3 Access....................................................................................................486
7.5.4 Operations..............................................................................................487
7.5.5 Structs as Data Members .......................................................................488
7.5.6 Pointers to Structs..................................................................................493
7.5.7 Passing structs and Pointers to structs ...................................................494
7.6 The Interrupt ........................................................................................................496
7.6.1 The Interrupt Control Flow ...................................................................496
7.6.2 The Interrupt Event................................................................................497
7.6.3 The Interrupt Service Routine ? ISR .....................................................497
7.6.4 The Interrupt Vector Table....................................................................498
7.6.5 Control of the Interrupt..........................................................................501
7.7 Summary..............................................................................................................503
7.8 Review Questions ................................................................................................504
7.9 Thought Questions...............................................................................................508
7.10 Problems ..............................................................................................................512
Chapter 8 Safety, Reliability, and Robust Design ............................................................517
8.0 Introduction..........................................................................................................518
8.1 Safety ...................................................................................................................518
8.2 Reliability.............................................................................................................520
8.3 Faults, Errors, and Failures ..................................................................................522
8.4 Another Look at Reliability .................................................................................523
8.5 Some Real World Examples ................................................................................525
8.6 Single Point and Common Mode Failure Model .................................................528
8.7 Safe Specifications...............................................................................................529
8.8 Safe and Robust Designs .....................................................................................530
Embedded Systems - A Contemproary Design Tool Table of Contents
- vii - Copyright 2006 Oxford Consulting Ltd
8.8.1 Understanding System Requirements....................................................530
8.8.2 Managing Essential Information ...........................................................531
8.8.3 The Review Process ..............................................................................532
8.8.4 Bug Lists................................................................................................533
8.8.5 Errors and Exceptions............................................................................534
8.8.6 Use the Available Tools ........................................................................538
8.9 Safe and Robust Designs ? The System ..............................................................539
8.10 System Functional Level Considerations ............................................................539
8.10.1 Control and Alarm Subsystems .............................................................540
8.10.2 Memory and Bus Subsystems ...............................................................540
8.10.3 Data Faults and the Communications Subsystem .................................540
8.10.4 Power and Reset Subsystems ................................................................540
8.10.5 Peripheral Device Subsystems ..............................................................541
8.10.6 Clock Subsystem ...................................................................................541
8.11 System Architecture Level Considerations..........................................................542
8.11.1 Fail Operational2 / Fail Operational Capability ....................................542
8.11.2 Reduced Capability ...............................................................................544
8.12 Busses ? The Subsystem Interconnect.................................................................546
8.12.1 The Star Configuration ..........................................................................546
8.12.2 The Multidrop Bus Configuration .........................................................546
8.12.3 The Ring Configuration.........................................................................547
8.13 Data and Control Faults ? Data Boundary Values...............................................548
8.13.1 Type Conformance ................................................................................548
8.13.2 Boundary Values ...................................................................................549
8.14 Data and Control Faults ? The Communications Subsystem ..............................550
8.14.1 Damaged Data .......................................................................................550
8.14.2 Managing Damaged Data......................................................................552
8.15 The Power Subsystem..........................................................................................567
8.15.1 Full Operation........................................................................................567
8.15.2 Reduced Operation ................................................................................569
8.15.3 Backup Operation..................................................................................570
8.16 Peripheral Devices ? Built In Self Test - BIST ...................................................571
8.16.1 Self Tests ...............................................................................................571
8.16.2 Busses ....................................................................................................572
8.16.3 ROM Memory .......................................................................................574
8.16.4 RAM Memory .......................................................................................575
8.16.5 Peripheral Devices.................................................................................575
8.16.6 What to Do if a Test Fails?....................................................................575
8.17 Failure Modes and Effects Analysis ....................................................................576
8.18 Summary..............................................................................................................580
8.19 Review Questions ................................................................................................581
8.20 Thought Questions...............................................................................................583
8.21 Problems ..............................................................................................................585
Embedded Systems - A Contemproary Design Tool Table of Contents
- viii - Copyright 2006 Oxford Consulting Ltd
Chapter 9 Embedded Systems Design and Development...............................................589
9.0 Introduction..........................................................................................................590
9.1 System Design and Development ........................................................................592
9.1.1 Getting Ready ? Start Thinking.............................................................593
9.1.2 Getting Started.......................................................................................594
9.2 Life Cycle Models ...............................................................................................595
9.2.1 The Waterfall Model .............................................................................596
9.2.2 The V Cycle Model ...............................................................................598
9.2.3 The Spiral Model...................................................................................599
9.2.4 Rapid Prototyping - Incremental ...........................................................600
9.3 Problem Solving - Five Steps to Design..............................................................601
9.4 The Design Process..............................................................................................603
9.5 Identifying the Requirements...............................................................................605
9.6 Formulating the Requirements Specification ......................................................608
9.6.1 The Environment ...................................................................................609
9.6.2 The System ............................................................................................610
9.7 The System Design Specification ........................................................................623
9.7.1 The System ............................................................................................623
9.7.2 Quantifying the System .........................................................................624
9.8 System Specifications versus System Requirements...........................................639
9.9 Partitioning and Decomposing a System .............................................................641
9.9.1 Initial Thoughts .....................................................................................641
9.9.2 Coupling ................................................................................................644
9.9.3 Cohesion................................................................................................645
9.9.4 More Considerations .............................................................................647
9.10 Functional Design ................................................................................................648
9.11 Architectural Design ............................................................................................653
9.11.1 Mapping Functions to Hardware ...........................................................654
9.11.2 Hardware and Software Specification and Design................................655
9.12 Functional Model versus Architectural Model ....................................................659
9.12.1 The Functional Model ...........................................................................659
9.12.2 The Architectural Model .......................................................................659
9.12.3 The Need for Both Models ....................................................................660
9.13 Prototyping...........................................................................................................660
9.13.1 Implementation......................................................................................661
9.13.2 Analyzing the System Design ...............................................................661
9.14 Other Considerations ...........................................................................................664
9.14.1 Capitalization and Reuse .......................................................................664
9.14.2 Requirements Traceability and Management........................................665
9.15 Archiving the Project ...........................................................................................666
9.16 Summary..............................................................................................................668
9.17 Review Questions ................................................................................................669
9.18 Thought Questions...............................................................................................672
Embedded Systems - A Contemproary Design Tool Table of Contents
- ix - Copyright 2006 Oxford Consulting Ltd
9.19 Problems ..............................................................................................................675
Chapter 10 Hardware Test and Debug ..............................................................................681
10.0 Introduction to Debugging and Testing ...............................................................682
10.1 Some Vocabulary.................................................................................................682
10.2 Putting Together a Strategy .................................................................................684
10.3 Formulating a Plan...............................................................................................685
10.4 Formalizing the Plan ? Writing a Specification...................................................687
10.5 Executing the Plan ? The Test Procedure and Test Cases...................................689
10.6 Applying the Strategy ? Egoless Design? .........................................................691
10.7 Applying the Strategy ? Design Reviews ............................................................691
10.8 Applying the Strategy ? Module Debug and Test ...............................................692
10.8.1 Black Box Tests....................................................................................693
10.8.2 White Box Tests ....................................................................................694
10.8.3 Gray Box Tests ......................................................................................695
10.9 Applying the Strategy ? The First Steps..............................................................695
10.9.1 The Parts................................................................................................696
10.9.2 Initial Tests and Measurements ? Before Applying Power...................698
10.9.3 Initial Tests and Measurements ? Immediately After Applying Power 698
10.10 Applying the Strategy ? Debugging and Testing.................................................699
10.10.1 The Reset System ..................................................................................700
10.10.2 The Clocks and Timing .........................................................................700
10.10.3 The Inputs and Outputs .........................................................................700
10.10.4 Sudden Failure During Debugging........................................................701
10.11 Testing and Debugging Combinational Logic.....................................................703
10.12 Path Sensitizing....................................................................................................704
10.12.1 Single Variable ? Single Path................................................................705
10.12.2 Single Variable - Two Paths..................................................................707
10.13 Masking and Untestable Faults............................................................................709
10.14 Single Variable ? Multiple Paths .........................................................................710
10.15 Bridge Faults........................................................................................................712
10.16 Debugging ? Sequential Logic ............................................................................713
10.17 Scan Design Testing ............................................................................................717
10.18 Boundary Scan Testing........................................................................................721
10.19 Memories and Memory Systems .........................................................................723
10.20 Applying the Strategy ? Subsystem and System Test .........................................723
10.21 Applying the Strategy ? Testing for Our Customer.............................................724
10.21.1 Alpha and Beta Tests?.........................................................................724
10.21.2 Verification Tests? ..............................................................................724
10.21.3 Validation Tests?.................................................................................724
10.21.4 Acceptance Tests? ...............................................................................725
10.21.5 Production Tests ....................................................................................725
10.22 Self Test ...............................................................................................................725
Embedded Systems - A Contemproary Design Tool Table of Contents
- x - Copyright 2006 Oxford Consulting Ltd
10.22.1 On Demand............................................................................................726
10.22.2 In Background .......................................................................................726
10.23 Summary..............................................................................................................726
10.24 Review Questions ................................................................................................728
10.25 Thought Questions...............................................................................................730
10.26 Problems ..............................................................................................................732
Chapter 11 Real-Time Kernels and Operating Systems....................................................733
11.0 Introduction..........................................................................................................734
11.1 Tasks and Things .................................................................................................734
11.2 Programs and Processes.......................................................................................736
11.3 The CPU is a Resource ........................................................................................737
11.3.1 Setting a Schedule .................................................................................738
11.3.2 Changing Context..................................................................................739
11.4 Threads ? Lightweight and Heavyweight............................................................740
11.4.1 A Single Thread.....................................................................................741
11.4.2 Multiple Threads ...................................................................................741
11.5 Sharing Resources................................................................................................743
11.5.1 Memory Resource Management............................................................743
11.5.2 Re-entrant Code.....................................................................................745
11.6 Foreground / Background Systems......................................................................746
11.7 The Operating System .........................................................................................746
11.8 The Real Time Operating System - RTOS ..........................................................748
11.9 Operating System Architecture............................................................................749
11.10 Tasks and Task Control Blocks ...........................................................................750
11.10.1 The Task ................................................................................................750
11.10.2 The Task Control Block ........................................................................751
11.10.3 A Simple Kernel ....................................................................................753
11.10.4 Interrupts Revisited ...............................................................................759
11.11 Memory Management Revisited..........................................................................765
11.11.1 Duplicate Hardware Context .................................................................766
11.11.2 Task Control Blocks ..............................................................................767
11.11.3 Stacks.....................................................................................................767
11.12 Summary..............................................................................................................771
11.13 Review Questions ................................................................................................772
11.14 Thought Questions...............................................................................................774
11.15 Problems ..............................................................................................................776
Chapter 12 Tasks and Task Management.........................................................................779
12.0 Introduction..........................................................................................................780
12.1 Time, Time Based Systems, and Reactive Systems ............................................780
12.1.1 Time.......................................................................................................780
12.1.2 Reactive and Time Based Systems........................................................781
12.2 Task Scheduling...................................................................................................784
Embedded Systems - A Contemproary Design Tool Table of Contents
- xi - Copyright 2006 Oxford Consulting Ltd
12.2.1 CPU Utilization .....................................................................................785
12.2.2 Scheduling Decisions ............................................................................786
12.2.3 Scheduling Criteria................................................................................786
12.3 Scheduling Algorithms ........................................................................................789
12.3.1 Asynchronous Interrupt Event Driven...................................................789
12.3.2 Polled and Polled with a Timing Element.............................................790
12.3.3 State Based ............................................................................................791
12.3.4 Synchronous Interrupt Event Driven.....................................................791
12.3.5 Combined Interrupt Event Driven .........................................................792
12.3.6 Foreground ? Background.....................................................................792
12.3.7 Time Shared Systems ............................................................................792
12.3.8 Priority Schedule ...................................................................................793
12.4 Real-Time Scheduling Considerations ................................................................797
12.5 Algorithm Evaluation ..........................................................................................798
12.5.1 Deterministic Modeling.........................................................................798
12.5.2 Queuing Models ....................................................................................801
12.5.3 Simulation..............................................................................................802
12.5.4 Implementation......................................................................................802
12.6 Tasks, Threads and Communication....................................................................802
12.6.1 Getting Started.......................................................................................802
12.6.2 Intertask / Interthread Communication..................................................803
12.6.3 Shared Variables....................................................................................804
12.6.4 Messages................................................................................................808
12.7 Task Cooperation, Synchronization, and Sharing ...............................................815
12.7.1 Critical Sections and Synchronization...................................................815
12.7.2 Flags ......................................................................................................821
12.7.3 Token Passing........................................................................................823
12.7.4 Interrupts................................................................................................824
12.7.5 Semaphores............................................................................................824
12.7.6 Process Synchronization........................................................................827
12.7.7 Spin Lock and Busy Waiting.................................................................827
12.7.8 Counting Semaphores............................................................................828
12.8 Talking and Sharing in Space ..............................................................................829
12.8.1 The Bounded Buffer Problem ..............................................................829
12.8.2 The Readers and Writers Problem.........................................................832
12.9 Monitors...............................................................................................................835
12.9.1 Condition Variables...............................................................................836
12.9.2 Bounded Buffer Problem with Monitor ................................................839
12.10 Starvation .............................................................................................................841
12.11 Deadlocks.............................................................................................................841
12.12 Summary..............................................................................................................841
12.13 Review Questions ................................................................................................842
12.14 Thought Questions...............................................................................................844
Embedded Systems - A Contemproary Design Tool Table of Contents
- xii - Copyright 2006 Oxford Consulting Ltd
12.15 Problems ..............................................................................................................846
Chapter 13 Deadlocks........................................................................................................854
13.0 Introduction..........................................................................................................855
13.1 Sharing Resources................................................................................................855
13.2 System Model ......................................................................................................856
13.3 Deadlock Model...................................................................................................857
13.4 A Graph Theoretic Tool ? The Resource Allocation Graph................................858
13.5 Handling Deadlocks.............................................................................................862
13.6 Deadlock Prevention............................................................................................863
13.6.1 Mutual Exclusion...................................................................................863
13.6.2 Hold and Wait........................................................................................864
13.6.3 No Preemption.......................................................................................864
13.6.4 Circular Wait .........................................................................................865
13.7 Deadlock Avoidance............................................................................................866
13.7.1 Resource Allocation Graph Based Algorithms .....................................866
13.7.2 Banker?s Algorithm and Safe States......................................................867
13.8 Deadlock Detection..............................................................................................871
13.8.1 Detection in Single Instance Environment ............................................871
13.8.2 Deadlock Recovery ...............................................................................872
13.9 Summary..............................................................................................................874
13.10 Review Questions ................................................................................................875
13.11 Thought Questions...............................................................................................876
13.12 Problems ..............................................................................................................878
Chapter 14 Performance Analysis and Optimization .........................................................883
14.0 Introduction..........................................................................................................884
14.1 Getting Started .....................................................................................................884
14.2 Performance or Efficiency Measures...................................................................885
14.2.1 Introduction ...........................................................................................885
14.2.2 The System ............................................................................................886
14.2.3 Some Limitations...................................................................................887
14.3 Complexity Analysis ? A High Level Measure...................................................888
14.4 The Methodology.................................................................................................891
14.4.1 A Simple Experiment ............................................................................891
14.4.2 Working with Big Numbers ..................................................................892
14.4.3 Asymptotic Complexity.........................................................................893
14.5 Comparing Algorithms ........................................................................................893
14.5.1 Big-O Notation ......................................................................................895
14.5.2 Big-O Arithmetic...................................................................................896
14.6 Analyzing Code ...................................................................................................897
14.6.1 Constant Time Statements.....................................................................897
14.6.2 Looping Constructs ...............................................................................898
14.6.3 Sequences of Statements .......................................................................900
Embedded Systems - A Contemproary Design Tool Table of Contents
- xiii - Copyright 2006 Oxford Consulting Ltd
14.6.4 Conditional Statements..........................................................................900
14.6.5 Function Calls........................................................................................901
14.7 Analyzing Algorithms..........................................................................................901
14.7.1 Analyzing Search...................................................................................902
14.7.2 Analyzing Sort.......................................................................................903
14.8 Analyzing Data Structures ...................................................................................904
14.8.1 Array......................................................................................................905
14.8.2 Linked List.............................................................................................906
14.9 Instructions in Detail............................................................................................906
14.9.1 Getting Started.......................................................................................907
14.9.2 Flow of Control .....................................................................................908
14.9.3 Analyzing the Flow of Control - Two Views........................................910
14.10 Time Etc. ? A More Detailed Look .....................................................................917
14.11 Response Time.....................................................................................................919
14.11.1 Polled Loops..........................................................................................919
14.11.2 Coroutine ...............................................................................................921
14.11.3 Interrupt Driven Environment ..............................................................921
14.12 Time Loading.......................................................................................................923
14.12.1 Instruction Counting.............................................................................923
14.12.2 Simulation..............................................................................................924
14.12.3 Timers....................................................................................................926
14.12.4 Instrumentation......................................................................................926
14.13 Memory Loading .................................................................................................926
14.13.1 Memory Map.........................................................................................927
14.13.2 Designing a Memory Map.....................................................................928
14.14 Evaluating Performance.......................................................................................930
14.15 Thoughts on Performance Optimization..............................................................932
14.16 Performance Optimization ...................................................................................932
14.17 Tricks of the Trade...............................................................................................933
14.18 Hardware Accelerators ........................................................................................940
14.19 Optimizing for Power Consumption....................................................................941
14.19.1 Software.................................................................................................942
14.19.2 Hardware ...............................................................................................944
14.20 Caches and Performance......................................................................................949
14.21 Trade-offs.............................................................................................................951
14.22 Summary..............................................................................................................951
14.23 Review Questions ................................................................................................952
14.24 Thought Questions...............................................................................................954
14.25 Problems ..............................................................................................................956
Chapter 15 Working Outside of the Processor I.................................................................962
A Model of Interprocess Communication
15.0 Communication and Synchronization with the Outside World ...........................963
Embedded Systems - A Contemproary Design Tool Table of Contents
- xiv - Copyright 2006 Oxford Consulting Ltd
15.1 First Steps ? Understanding the Problem ............................................................964
15.2 Interprocess Interaction Revisited .......................................................................965
15.3 The Model............................................................................................................967
15.3.1 Information ............................................................................................967
15.3.2 Places.....................................................................................................968
15.3.3 Control and Synchronization.................................................................969
15.3.4 Transport................................................................................................970
15.4 Exploring the Model ............................................................................................971
15.4.1 The Transport Mechanism.....................................................................972
15.4.2 Control and Synchronization.................................................................977
15.4.3 Information Flow...................................................................................977
15.4.4 Places.....................................................................................................980
15.5 Summary..............................................................................................................981
15.6 Review Questions ................................................................................................982
15.7 Thought Questions...............................................................................................983
Chapter 16 Working Outside of the Processor I.................................................................985
Refining the Model of Interprocess Communication
16.0 Communication and Synchronization with the Outside World ...........................986
16.1 The Local Device Model .....................................................................................986
16.1.1 Control, Synchronization, and Places....................................................987
16.1.2 Information - Data .................................................................................990
16.1.3 Transport................................................................................................990
16.2 Implementing the Local Device Model ? A First Step ........................................991
16.2.1 An Overview .........................................................................................991
16.2.2 Main Memory Address Space ? Memory Mapped I/O .........................993
16.2.3 I/O Ports ? Program Controlled I/O ......................................................998
16.2.4 The Peripheral Processor.......................................................................998
16.3 Implementing the Local Device Model ? A Second Step ...................................1000
16.3.1 Information Interchange ? An Event.....................................................1000
16.3.2 Information Interchange ? A Shared Variable ......................................1001
16.3.3 Information Interchange ? A Message ..................................................1001
16.4 Implementing an Event Driven Exchange ? Interrupts and Polling ....................1002
16.4.1 Polling....................................................................................................1002
16.4.2 Interrupts................................................................................................1004
16.4.3 Masking Interrupts.................................................................................1013
16.5 A Message............................................................................................................1014
16.5.1 Asynchronous Information Exchange ...................................................1015
16.5.2 Synchronous Information Exchange .....................................................1018
16.6 The Remote Device Model ..................................................................................1023
16.6.1 Places and Information ..........................................................................1025
16.6.2 Control and Synchronization.................................................................1026
16.6.3 Transport................................................................................................1026
Embedded Systems - A Contemproary Design Tool Table of Contents
- xv - Copyright 2006 Oxford Consulting Ltd
16.7 Implementing the Remote Device Model ? A First Step.....................................1026
16.7.1 The OSI and TCP/IP Protocol Stacks....................................................1028
16.7.2 The Models............................................................................................1032
16.8 Implementing the Remote Device Model ? A Second Step ................................1034
16.8.1 The Messages ........................................................................................1034
16.8.2 The Message Structure ..........................................................................1035
16.8.3 Message Control and Synchronization..................................................1036
16.9 Working with Remote Tasks ...............................................................................1038
16.9.1 Preliminary Thoughts on Working with Remote Tasks ........................1038
16.9.2 Procedures and Remote Procedures ......................................................1040
16.9.3 Node Failure, Link Failure, Message Loss............................................1045
16.10 Group Multicast Revisited ...................................................................................1048
16.11 Connecting to Distributed Processes - Pipes, Streams and Sockets ....................1049
16.11.1 Pipes ......................................................................................................1049
16.11.2 Sockets...................................................................................................1050
16.11.3 Stream Communication.........................................................................1052
16.12 Summary..............................................................................................................1053
16.13 Review Questions ................................................................................................1054
16.14 Thought Questions...............................................................................................1056
16.15 Problems ..............................................................................................................1058
Chapter 17 Working Outside of the Processor II................................................................1060
Interfacing to Local Devices
17.0 Shared Variable I/O ? Interfacing to Peripheral Devices ....................................1061
17.1 The Shared Variable Exchange............................................................................1062
17.2 Generating Analog Signals ..................................................................................1062
17.2.1 Binary Weighted Digital to Analog Convertor .....................................1063
17.2.2 R/2R Ladder Digital to Analog Convertor ............................................1066
17.3 Common Measurements ......................................................................................1069
17.3.1 Voltage ..................................................................................................1069
17.3.2 Current...................................................................................................1070
17.3.3 Resistance ..............................................................................................1070
17.4 Measuring Voltage...............................................................................................1070
17.4.1 Dual Slope Analog to Digital Conversion.............................................1071
17.4.2 Successive Approximation Analog to Digital Conversion....................1077
17.4.3 VCO Analog to Digital Conversion ......................................................1080
17.5 Measuring Resistance ..........................................................................................1082
17.6 Measuring Current ...............................................................................................1084
17.7 Measuring Temperature .......................................................................................1085
17.7.1 Sensors...................................................................................................1085
17.7.2 Making the Measurement .....................................................................1086
17.7.3 Working with Nonlinear Devices..........................................................1087
17.8 Generating Digital Signals...................................................................................1090
Embedded Systems - A Contemproary Design Tool Table of Contents
- xvi - Copyright 2006 Oxford Consulting Ltd
17.8.1 Motors and Motor Control.....................................................................1090
17.8.2 DC Motors.............................................................................................1090
17.8.3 Servo Motors .........................................................................................1092
17.8.4 Stepper Motor........................................................................................1092
17.9 Controlling DC and Servo Motors.......................................................................1093
17.9.1 DC Motors.............................................................................................1093
17.9.2 Servo Motors .........................................................................................1095
17.9.3 Controlling Stepper Motors...................................................................1096
17.9.4 Motor Drive Circuitry............................................................................1098
17.9.5 Motor Drive Noise.................................................................................1101
17.10 LEDs and LED Displays......................................................................................1102
17.10.1 Individual LEDs ....................................................................................1102
17.10.2 Multi ? LED Displays ...........................................................................1102
17.11 Measuring Digital Signals ...................................................................................1105
17.11.1 The Approach ........................................................................................1106
17.11.2 Working with Asynchronous Signals....................................................1107
17.11.3 Buffering Input Signals .........................................................................1108
17.11.4 Inside vs. Outside ..................................................................................1109
17.11.5 Measuring Frequency and Time Interval ..............................................1109
17.12 Summary.............................................................................................................1115
17.13 Review Questions ................................................................................................1116
17.14 Thought Questions...............................................................................................1118
17.15 Problems ..............................................................................................................1120
Chapter 18 Working Outside of the Processor III...............................................................1127
Interfacing to Remote Devices
18.0 Common Network Based I/O Architectures........................................................1128
18.1 Network Based Systems ......................................................................................1128
18.2 RS-232 / EIA-232 ? Asynchronous Serial Communication................................1129
18.2.1 Introduction ...........................................................................................1129
18.2.2 The EIA-232 Standard...........................................................................1130
18.2.3 EIA-232 Addressing..............................................................................1134
18.2.4 Asynchronous Serial Communication...................................................1135
18.2.5 Configuring the Interface ......................................................................1136
18.2.6 Data Recovery and Timing....................................................................1136
18.2.7 EIA-232 Interface Signals .....................................................................1138
18.2.8 An Implementation................................................................................1139
18.3 The Universal Serial Bus ? Synchronous Serial Communication .......................1140
18.3.1 Background............................................................................................1140
18.3.2 The Universal Serial Bus Architecture..................................................1142
18.3.3 The Universal Serial Bus Protocol ........................................................1142
18.3.4 USB Devices .........................................................................................1143
18.3.5 Transfer Types.......................................................................................1144
Embedded Systems - A Contemproary Design Tool Table of Contents
- xvii - Copyright 2006 Oxford Consulting Ltd
18.3.6 Device Descriptors ................................................................................1144
18.3.7 Network Configuration..........................................................................1146
18.3.8 USB Transactions..................................................................................1147
18.3.9 USB Interface Signals ...........................................................................1149
18.3.10 The Physical Environment ....................................................................1150
18.3.11 Detecting Device Attachment and Speed ..............................................1151
18.3.12 Differential Pair Signaling.....................................................................1152
18.3.13 Implementation......................................................................................1152
18.4 I2C ? A Local Area Network...............................................................................1153
18.4.1 The Architecture....................................................................................1153
18.4.2 Electrical Considerations.......................................................................1154
18.4.3 Basic Operation .....................................................................................1155
18.4.4 Flow of Control .....................................................................................1156
18.4.5 Multiple Masters....................................................................................1157
18.4.6 Using the I2C Bus .................................................................................1159
18.5 The Controller Area Network ? The CAN Bus ...................................................1159
18.5.1 The Architecture....................................................................................1159
18.5.2 Electrical Considerations.......................................................................1160
18.5.3 Message Types ......................................................................................1161
18.5.4 Message Format.....................................................................................1162
18.5.5 Basic Operation .....................................................................................1163
18.5.6 Using the CAN Bus...............................................................................1165
18.6 Summary..............................................................................................................1165
18.7 Review Questions ................................................................................................1167
18.8 Thought Questions...............................................................................................1169
18.9 Problems ..............................................................................................................1171
Chapter 19 Programmable Logic Devices .........................................................................1174
19.0 Introduction..........................................................................................................1175
19.1 Why Use Programmable Logic Devices?............................................................1176
19.2 Basic Concepts.....................................................................................................1178
19.3 Basic Configurations............................................................................................1181
19.3.1 The (P)ROM..........................................................................................1181
19.3.2 Programmable Array Logic ? PAL .......................................................1182
19.3.3 Programmable Logic Array ? PLA .......................................................1182
19.3.4 Programmable Logic Sequencer ? PLS.................................................1183
19.3.5 PLA vs. PAL vs. (P)ROM.....................................................................1183
19.4 Programmable and Reprogrammable Technologies............................................1183
19.4.1 Programmable Technologies .................................................................1183
19.4.2 Reprogrammable Technologies.............................................................1184
19.5 Architectures........................................................................................................1186
19.5.1 PLDs......................................................................................................1187
19.5.2 CPLD.....................................................................................................1189
Embedded Systems - A Contemproary Design Tool Table of Contents
- xviii - Copyright 2006 Oxford Consulting Ltd
19.5.3 FPGAs ...................................................................................................1190
19.6 Example PLD Devices.........................................................................................1193
19.6.1 Xilinx XC 9500XLTM Family ...............................................................1194
19.6.2 Altera Flex 10KTM FPGA.....................................................................1196
19.6.3 Cypress CY8C21x23TM PSOC .............................................................1203
19.7 The Design Process..............................................................................................1205
19.8 Design Examples .................................................................................................1206
19.8.1 Lane Departure Detection Implementation and Acceleration ...............1206
19.8.2 Local Area Tracking System - LATS with uCLinuxTM OS .................1211
19.9 Summary..............................................................................................................1214
19.10 Review Questions ................................................................................................1215
19.11 Thought Questions...............................................................................................1216
Chapter 20 References......................................................................................................1218
Chapter A Verilog Overview.............................................................................................1231
The Verilog Hardware Description Language
A.0 Introduction..........................................................................................................1232
A.1 An Overview of a Verilog Program.....................................................................1233
A.2 Creating a Verilog Program.................................................................................1234
A.2.1 Some Concepts in a Verilog Source File...............................................1234
A.2.2 Modules .................................................................................................1235
A.3 Three Models ? The Gate-Level, the Dataflow, and the Behavioral ...................1241
A.3.1 The Structural / Gate Level Model........................................................1242
A.3.2 The Dataflow Model..............................................................................1250
A.3.3 The Behavioral Model...........................................................................1257
A.4 Testing and Verifying the Circuit ........................................................................1271
A.4.1 The Circuit Module ...............................................................................1272
A.4.2 The Test Module....................................................................................1272
A.4.3 The Test Bench......................................................................................1275
A.4.4 Performing the Simulation ....................................................................1276
A.5 Summary..............................................................................................................1276
Chapter B Laboratory Projects .........................................................................................1277
B.0 Introduction..........................................................................................................1278
B.1 Getting Started? .................................................................................................1279
B.2 Developing Skills?.............................................................................................1285
B.3 Bringing It Together? ........................................................................................1303

Library of Congress Subject Headings for this publication:

Embedded computer systems.
Object-oriented methods (Computer science).