Introduction to Embedded Systems, Second Edition: A Cyber-Physical Systems Approach / Edition 2

by Edward Ashford Lee, Sanjit Arunkumar Seshia

Overview

An introduction to the engineering principles of embedded systems, with a focus on modeling, design, and analysis of cyber-physical systems.

The most visible use of computers and software is processing information for human consumption. The vast majority of computers in use, however, are much less visible. They run the engine, brakes, seatbelts, airbag, and audio system in your car. They digitally encode your voice and construct a radio signal to send it from your cell phone to a base station. They command robots on a factory floor, power generation in a power plant, processes in a chemical plant, and traffic lights in a city. These less visible computers are called embedded systems, and the software they run is called embedded software. The principal challenges in designing and analyzing embedded systems stem from their interaction with physical processes. This book takes a cyber-physical approach to embedded systems, introducing the engineering concepts underlying embedded systems as a technology and as a subject of study. The focus is on modeling, design, and analysis of cyber-physical systems, which integrate computation, networking, and physical processes.

The second edition offers two new chapters, several new exercises, and other improvements. The book can be used as a textbook at the advanced undergraduate or introductory graduate level and as a professional reference for practicing engineers and computer scientists. Readers should have some familiarity with machine structures, computer programming, basic discrete mathematics and algorithms, and signals and systems.

Product Details

ISBN-13:	9780262533812
Publisher:	MIT Press
Publication date:	12/30/2016
Series:	The MIT Press
Edition description:	Second Edition
Pages:	568
Product dimensions:	7.20(w) x 9.20(h) x 0.90(d)
Age Range:	18 Years

About the Author

Edward Ashford Lee is Distinguished Professor (Emeritus) in Electrical Engineering and Computer Sciences at the University of California, Berkeley, where he runs iCyPhy, a research center focused on industrial cyber-physical systems. He is the author of Plato and the Nerd (MIT Press) and other books.

Sanjit A. Seshia is a Professor in the Department of Electrical Engineering and Computer Sciences at the University of California, Berkeley.

Table of Contents

Preface xiii

1 Introduction 1

1.1 Applications 2

1.2 Motivating Example 6

1.3 The Design Process 8

1.4 Summary 15

I Modeling Dynamic Behaviors 17

2 Continuous Dynamics 19

2.1 Newtonian Mechanics 20

2.2 Actor Models 25

2.3 Properties of Systems 28

2.4 Feedback Control 31

2.5 Summary 37

Exercises 37

3 Discrete Dynamics 41

3.1 Discrete Systems 42

3.2 The Notion of State 46

3.3 Finite-State Machines 47

3.4 Extended State Machines 56

3.5 Non determinism 62

3.6 Behaviors and Traces 66

3.7 Summary 69

Exercises 70

4 Hybrid Systems 75

4.1 Modal Models 76

4.2 Classes of Hybrid Systems 80

4.3 Summary 95

Exercises 96

5 Composition of State Machines 103

5.1 Concurrent Composition 105

5.2 Hierarchical State Machines 119

5.3 Summary 123

Exercises 124

6 Concurrent Models of Computation 129

6.1 Structure of Models 130

6.2 Synchronous-Reactive Models 132

6.3 Dataflow Models of Computation 142

6.4 Timed Models of Computation 154

6.5 Summary 163

Exercises 163

II Design of Embedded Systems 169

7 Sensors and Actuators 171

7.1 Models of Sensors and Actuators 173

7.2 Common Sensors 186

7.3 Actuators 191

7.4 Summary 196

Exercises 197

8 Embedded Processors 201

8.1 Types of Processors 202

8.2 Parallelism 212

8.3 Summary 227

Exercises 227

9 Memory Architectures 229

9.1 Memory Technologies 230

9.2 Memory Hierarchy 232

9.3 Memory Models 240

9.4 Summary 245

Exercises 245

10 Input and Output 249

10.1 I/O Hardware 250

10.2 Sequential Software in a Concurrent World 261

10.3 Summary 271

Exercises 272

11 Multitasking 279

11.1 Imperative Programs 282

11.2 Threads 286

11.3 Processes and Message Passing 298

11.4 Summary 303

Exercises 304

12 Scheduling 309

12.1 Basics of Scheduling 310

12.2 Rate Monotonic Scheduling 316

12.3 Earliest Deadline First 320

12.4 Scheduling and Mutual Exclusion 325

12.5 Multiprocessor Scheduling 329

12.6 Summary 335

Exercises 335

III Analysis and Verification 341

13 Invariants and Temporal Logic 343

13.1 Invariants 344

13.2 Linear Temporal Logic 346

13.3 Summary 354

Exercises 356

14 Equivalence and Refinement 359

14.1 Models as Specifications 360

14.2 Type Equivalence and Refinement 361

14.3 Language Equivalence and Containment 364

14.4 Simulation 370

14.5 Bisimulation 377

14.6 Summary 379

Exercises 380

15 Reachability Analysis and Model Checking 385

15.1 Open and Closed Systems 386

15.2 Reachability Analysis 387

15.3 Abstraction in Model Checking 394

15.4 Model Checking Liveness Properties 397

15.5 Summary 403

Exercises 405

16 Quantitative Analysis 407

16.1 Problems of Interest 408

16.2 Programs as Graphs 410

16.3 Factors Determining Execution Time 415

16.4 Basics of Execution Time Analysis 421

16.5 Other Quantitative Analysis Problems 431

16.6 Summary 432

Exercises 433

17 Security and Privacy 437

17.1 Cryptographic Primitives 439

17.2 Protocol and Network Security 446

17.3 Software Security 451

17.4 Information Flow 454

17.5 Advanced Topics 462

17.6 Summary 467

Exercises 467

IV Appendices 469

A Sets and Functions 471

A.1 Sets 471

A.2 Relations and Functions 472

A.3 Sequences 476

Exercises 478

B Complexity and Computability 479

B.1 Effectiveness and Complexity of Algorithms 480

R.2 Problems, Algorithms, and Programs 483

B.3 Turing Machines and Undecidabilty 485

B.4 Intractability: P and NP 491

B.5 Summary 494

Exercises 494

Bibliography 497

Notation Index 515

Index 517

What People are Saying About This

Axel Jantsch

Designers of embedded systems are only too often overwhelmed by the many skills and disciplines that have to be mastered: from writing device drivers, to worst case execution time analysis, to formal verification and modeling of continuous time systems. This book by Lee and Seshia is an excellent guide to bringing order into these complexities of design by discerning the fundamental from the detail, the essential property from the accidental aspect. It presents all the indispensable knowledge areas for an embedded systems designer and leaves out what can be delegated to other specialized disciplines.

Bruce H. Krogh

Books titled Introduction to Embedded Systems traditionally focus on computer hardware and software. By taking A Cyber-Physical Systems Approach, Lee and Seshia give students the integrated perspective they need to understand and design the computing systems that make our world function. No other book provides such a comprehensive introduction to embedded systems for real-time applications.

Endorsement

The outstanding property of this textbook is the combination of mathematical rigor and comprehensiveness. It is presented with numerous examples and with such quality that understanding the material is easy. Introduction to Embedded Systems is a must-read for those wanting to master the complexity of what is today the key enabling technology in most every complex system surrounding us: embedded and cyber-physical systems.—Werner Damm, Director, Interdisciplinary Research Center on Cooperative Critical Systems, Carl von Ossietzky University of Oldenburg

From the Publisher

Books titled Introduction to Embedded Systems traditionally focus on computer hardware and software. By taking A Cyber-Physical Systems Approach , Lee and Seshia give students the integrated perspective they need to understand and design the computing systems that make our world function. No other book provides such a comprehensive introduction to embedded systems for real-time applications.

— Bruce H. Krogh , Professor of Electrical and Computer Engineering, Carnegie Mellon University

Introduction to Embedded Systems by Lee and Seshia is an introductory yet rigorous textbook for the future Internet of Things engineer. It provides a unified systems view of computing and the physical world that will be the foundation of the 21st-century Internet of Things revolution.

— George J. Pappas , Joseph Moore Professor, University of Pennsylvania

Designers of embedded systems are only too often overwhelmed by the many skills and disciplines that have to be mastered: from writing device drivers, to worst case execution time analysis, to formal verification and modeling of continuous time systems. This book by Lee and Seshia is an excellent guide to bringing order into these complexities of design by discerning the fundamental from the detail, the essential property from the accidental aspect. It presents all the indispensable knowledge areas for an embedded systems designer and leaves out what can be delegated to other specialized disciplines.

— Axel Jantsch , Professor of Systems on Chips, Institute of Computer Technology, TU Wien, Vienna; author of Modeling Embedded Systems and SoC's

The outstanding property of this textbook is the combination of mathematical rigor and comprehensiveness. It is presented with numerous examples and with such quality that understanding the material is easy. Introduction to Embedded Systems is a must-read for those wanting to master the complexity of what is today the key enabling technology in most every complex system surrounding us: embedded and cyber-physical systems.

— Werner Damm , Director, Interdisciplinary Research Center on Cooperative Critical Systems, Carl von Ossietzky University of Oldenburg

Werner Damm

The outstanding property of this textbook is the combination of mathematical rigor and comprehensiveness. It is presented with numerous examples and with such quality that understanding the material is easy. Introduction to Embedded Systems is a must-read for those wanting to master the complexity of what is today the key enabling technology in most every complex system surrounding us: embedded and cyber-physical systems.

George J. Pappas

Introduction to Embedded Systems by Lee and Seshia is an introductory yet rigorous textbook for the future Internet of Things engineer. It provides a unified systems view of computing and the physical world that will be the foundation of the 21st-century Internet of Things revolution.