Updater process ended with error 255 moto g4 plus

IN TRODUCTION

TO EM

BEDDED SYSTEM S

A CYBER-PHYSICAL SYSTEM

S APPROACH Edw

ard Ashford Lee and Sanjit Arunkum

ar Seshia

computer science/electrical engineering

Introduction to Embedded Systems A Cyber-Physical Systems Approach second edition Edward Ashford Lee and Sanjit Arunkumar Seshia

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 sta- tion. 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 interac- tion with physical processes. This book takes a cyber-physical approach to embedded systems, introducing the engi- neering 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.

Edward Ashford Lee is the Robert S. Pepper Distinguished Professor in the Department of Electrical Engineering and Computer Sciences at the University of California, Berkeley. Sanjit Arunkumar Seshia is a Professor in the Depart- ment of Electrical Engineering and Computer Sciences at the University of California, Berkeley.

“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 under- stand and design the computing systems that make our world function. No other book provides such a comprehen- sive 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 complex- ities 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 Mod- eling 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

The MIT Press Massachusetts Institute of Technology Cambridge, Massachusetts 02142 http://mitpress.mit.edu 9 780262 533812

90000

978-0-262-53381-2

second edition

INTRODUCTION TO EMBEDDED SYSTEMS A CYBER-PHYSICAL SYSTEMS APPROACH

Second Edition

Edward Ashford Lee and Sanjit Arunkumar Seshia

Modeling

Design

Analysis

Copyright c© 2017 Edward Ashford Lee & Sanjit Arunkumar Seshia

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Second Edition, Version 2.2

ISBN: 978-0-262-53381-2

Please cite this book as:

E. A. Lee and S. A. Seshia, Introduction to Embedded Systems - A Cyber-Physical Systems Approach,

Second Edition, MIT Press, 2017.

This book is dedicated to our families.

Contents

Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x

1 Introduction 1 1.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Motivating Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3 The Design Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

I Modeling Dynamic Behaviors 17

2 Continuous Dynamics 18

2.1 Newtonian Mechanics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.2 Actor Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.3 Properties of Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.4 Feedback Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

CONTENTS

3 Discrete Dynamics 42

3.1 Discrete Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.2 The Notion of State . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.3 Finite-State Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.4 Extended State Machines . . . . . . . . . . . . . . . . . . . . . . . . . . 60

3.5 Nondeterminism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

3.6 Behaviors and Traces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

4 Hybrid Systems 78

4.1 Modal Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

4.2 Classes of Hybrid Systems . . . . . . . . . . . . . . . . . . . . . . . . . 82

4.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

5 Composition of State Machines 109

5.1 Concurrent Composition . . . . . . . . . . . . . . . . . . . . . . . . . . 111

5.2 Hierarchical State Machines . . . . . . . . . . . . . . . . . . . . . . . . 126

5.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

6 Concurrent Models of Computation 135

6.1 Structure of Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

6.2 Synchronous-Reactive Models . . . . . . . . . . . . . . . . . . . . . . . 141

6.3 Dataflow Models of Computation . . . . . . . . . . . . . . . . . . . . . . 147

6.4 Timed Models of Computation . . . . . . . . . . . . . . . . . . . . . . . 162

6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

Lee & Seshia, Introduction to Embedded Systems v

http://LeeSeshia.org
CONTENTS

II Design of Embedded Systems 178

7 Sensors and Actuators 179 7.1 Models of Sensors and Actuators . . . . . . . . . . . . . . . . . . . . . . 181

7.2 Common Sensors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

7.3 Actuators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200

7.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

8 Embedded Processors 210 8.1 Types of Processors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

8.2 Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220

8.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238

9 Memory Architectures 239

9.1 Memory Technologies . . . . . . . . . . . . . . . . . . . . . . . . . . . 240

9.2 Memory Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

9.3 Memory Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251

9.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257

10 Input and Output 260

10.1 I/O Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

10.2 Sequential Software in a Concurrent World . . . . . . . . . . . . . . . . 272

10.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284

11 Multitasking 291

11.1 Imperative Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294

11.2 Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298

vi Lee & Seshia, Introduction to Embedded Systems

http://LeeSeshia.org
CONTENTS

11.3 Processes and Message Passing . . . . . . . . . . . . . . . . . . . . . . . 311

11.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318

12 Scheduling 322

12.1 Basics of Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323

12.2 Rate Monotonic Scheduling . . . . . . . . . . . . . . . . . . . . . . . . 329

12.3 Earliest Deadline First . . . . . . . . . . . . . . . . . . . . . . . . . . . 334

12.4 Scheduling and Mutual Exclusion . . . . . . . . . . . . . . . . . . . . . 339

12.5 Multiprocessor Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . 344

12.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351

III Analysis and Verification 357

13 Invariants and Temporal Logic 358

13.1 Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359

13.2 Linear Temporal Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . 362

13.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372

14 Equivalence and Refinement 376

14.1 Models as Specifications . . . . . . . . . . . . . . . . . . . . . . . . . . 377

14.2 Type Equivalence and Refinement . . . . . . . . . . . . . . . . . . . . . 378

14.3 Language Equivalence and Containment . . . . . . . . . . . . . . . . . . 381

14.4 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387

14.5 Bisimulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395

14.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399

Lee & Seshia, Introduction to Embedded Systems vii

http://LeeSeshia.org
CONTENTS

15 Reachability Analysis and Model Checking 404

15.1 Open and Closed Systems . . . . . . . . . . . . . . . . . . . . . . . . . 405

15.2 Reachability Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406

15.3 Abstraction in Model Checking . . . . . . . . . . . . . . . . . . . . . . . 413

15.4 Model Checking Liveness Properties . . . . . . . . . . . . . . . . . . . . 417

15.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425

16 Quantitative Analysis 427

16.1 Problems of Interest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428

16.2 Programs as Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430

16.3 Factors Determining Execution Time . . . . . . . . . . . . . . . . . . . . 435

16.4 Basics of Execution Time Analysis . . . . . . . . . . . . . . . . . . . . . 442

16.5 Other Quantitative Analysis Problems . . . . . . . . . . . . . . . . . . . 451

16.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455

17 Security and Privacy 459

17.1 Cryptographic Primitives . . . . . . . . . . . . . . . . . . . . . . . . . . 461

17.2 Protocol and Network Security . . . . . . . . . . . . . . . . . . . . . . . 469

17.3 Software Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474

17.4 Information Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477

17.5 Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485

17.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 490

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491

viii Lee & Seshia, Introduction to Embedded Systems

http://LeeSeshia.org
CONTENTS

IV Appendices 492

A Sets and Functions 493 A.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493

A.2 Relations and Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 494

A.3 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501

B Complexity and Computability 502

B.1 Effectiveness and Complexity of Algorithms . . . . . . . . . . . . . . . . 503

B.2 Problems, Algorithms, and Programs . . . . . . . . . . . . . . . . . . . . 506

B.3 Turing Machines and Undecidability . . . . . . . . . . . . . . . . . . . . 508

B.4 Intractability: P and NP . . . . . . . . . . . . . . . . . . . . . . . . . . . 514

B.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519

Bibliography 521

Notation Index 541

Notation Index 541

Index 543

Lee & Seshia, Introduction to Embedded Systems ix

http://LeeSeshia.org
Preface

What This Book Is About

The most visible use of computers and software is processing information for human consumption. We use them to write books (like this one), search for information on the web, communicate via email, and keep track of financial data. 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 control your microwave oven, refrigerator, and dishwasher. They run printers ranging from desktop inkjet printers to large industrial high-volume printers. They command robots on a factory floor, power generation in a power plant, processes in a chemical plant, and traffic lights in a city. They search for microbes in biological samples, construct images of the inside of a human body, and measure vital signs. They process radio signals from space looking for supernovae and for extraterrestrial intelligence. They bring toys to life, enabling them to react to human touch and to sounds. They control aircraft and trains. These less visible computers are called embedded systems, and the software they run is called embedded software.

Despite this widespread prevalence of embedded systems, computer science has, through- out its relatively short history, focused primarily on information processing. Only recently have embedded systems received much attention from researchers. And only recently has

PREFACE

the community recognized that the engineering techniques required to design and ana- lyze these systems are distinct. Although embedded systems have been in use since the 1970s, for most of their history they were seen simply as small computers. The principal engineering problem was understood to be one of coping with limited resources (limited processing power, limited energy sources, small memories, etc.). As such, the engineer- ing challenge was to optimize the designs. Since all designs benefit from optimization, the discipline was not distinct from anything else in computer science. It just had to be more aggressive about applying the same optimization techniques.

Recently, the community has come to understand that the principal challenges in em- bedded systems stem from their interaction with physical processes, and not from their limited resources. The term cyber-physical systems (CPS) was coined by Helen Gill at the National Science Foundation in the U.S. to refer to the integration of computation with physical processes. In CPS, embedded computers and networks monitor and control the physical processes, usually with feedback loops where physical processes affect compu- tations and vice versa. The design of such systems, therefore, requires understanding the joint dynamics of computers, software, networks, and physical processes. It is this study of joint dynamics that sets this discipline apart.

When studying CPS, certain key problems emerge that are rare in so-called general- purpose computing. For example, in general-purpose software, the time it takes to per- form a task is an issue of performance, not correctness. It is not incorrect to take longer to perform a task. It is merely less convenient and therefore less valuable. In CPS, the time it takes to perform a task may be critical to correct functioning of the system. In the physical world, as opposed to the cyber world, the passage of time is inexorable.

In CPS, moreover, many things happen at once. Physical processes are compositions of many things going on at once, unlike software processes, which are deeply rooted in sequential steps. Abelson and Sussman (1996) describe computer science as “proce- dural epistemology,” knowledge through procedure. In the physical world, by contrast, processes are rarely procedural. Physical processes are compositions of many parallel processes. Measuring and controlling the dynamics of these processes by orchestrating actions that influence the processes are the main tasks of embedded systems. Conse- quently, concurrency is intrinsic in CPS. Many of the technical challenges in designing and analyzing embedded software stem from the need to bridge an inherently sequential semantics with an intrinsically concurrent physical world.

Lee & Seshia, Introduction to Embedded Systems xi

http://LeeSeshia.org
PREFACE

Why We Wrote This Book

The mechanisms by which software interacts with the physical world are changing rapidly. Today, the trend is towards “smart” sensors and actuators, which carry microprocessors, network interfaces, and software that enables remote access to the sensor data and remote activation of the actuator. Called variously the Internet of Things (IoT), Industry 4.0, the Industrial Internet, Machine-to-Machine (M2M), the Internet of Everything, the Smarter Planet, TSensors (Trillion Sensors), or The Fog (like The Cloud, but closer to the ground), the vision is of a technology that deeply connects our physical world with our information world. In the IoT world, the interfaces between these worlds are inspired by and derived from information technology, particularly web technology.

IoT interfaces are convenient, but not yet suitable for tight interactions between the two worlds, particularly for real-time control and safety-critical systems. Tight interactions still require technically intricate, low-level design. Embedded software designers are forced to struggle with interrupt controllers, memory architectures, assembly-level pro- gramming (to exploit specialized instructions or to precisely control timing), device driver design, network interfaces, and scheduling strategies, rather than focusing on specifying desired behavior.

The sheer mass and complexity of these technologies (at both the high level and the low level) tempts us to focus an introductory course on mastering them. But a better intro- ductory course would focus on how to model and design the joint dynamics of software, networks, and physical processes. Such a course would present the technologies only as today’s (rather primitive) means of accomplishing those joint dynamics. This book is our attempt at a textbook for such a course.

Most texts on embedded systems focus on the collection of technologies needed to get computers to interact with physical systems (Barr and Massa, 2006; Berger, 2002; Burns and Wellings, 2001; Kamal, 2008; Noergaard, 2005; Parab et al., 2007; Simon, 2006; Val- vano, 2007; Wolf, 2000). Others focus on adaptations of computer-science techniques (like programming languages, operating systems, networking, etc.) to deal with techni- cal problems in embedded systems (Buttazzo, 2005a; Edwards, 2000; Pottie and Kaiser, 2005). While these implementation technologies are (today) necessary for system de- signers to get embedded systems working, they do not form the intellectual core of the discipline. The intellectual core is instead in models and abstractions that conjoin com- putation and physical dynamics.

xii Lee & Seshia, Introduction to Embedded Systems

http://LeeSeshia.org
PREFACE

A few textbooks offer efforts in this direction. Jantsch (2003) focuses on concurrent mod- els of computation, Marwedel (2011) focuses on models of software and hardware behav- ior, and Sriram and Bhattacharyya (2009) focus on dataflow models of signal processing behavior and their mapping onto programmable DSPs. Alur (2015) focuses on formal modeling, specification, and verification of cyber-physical systems. These are excellent textbooks that cover certain topics in depth. Models of concurrency (such as dataflow) and abstract models of software (such as Statecharts) provide a better starting point than imperative programming languages (like C), interrupts and threads, and architectural an- noyances that a designer must work around (like caches). These texts, however, do not address all the needs of an introductory course. They are either too specialized or too advanced or both. This book is our attempt to provide an introductory text that follows the spirit of focusing on models and their relationship to realizations of systems.

The major theme of this book is on models and their relationship to realizations of sys- tems. The models we study are primarily about dynamics, the evolution of a system state in time. We do not address structural models, which represent static information about the construction of a system, although these too are important to embedded system design.

Working with models has a major advantage. Models can have formal properties. We can say definitive things about models. For example, we can assert that a model is determinate, meaning that given the same inputs it will always produce the same outputs. No such absolute assertion is possible with any physical realization of a system. If our model is a good abstraction of the physical system (here, “good abstraction” means that it omits only inessential details), then the definitive assertion about the model gives us confidence in the physical realization of the system. Such confidence is hugely valuable, particularly for embedded systems where malfunctions can threaten human lives. Studying models of systems gives us insight into how those systems will behave in the physical world.

Our focus is on the interplay of software and hardware with the physical environment in which they operate. This requires explicit modeling of the temporal dynamics of soft- ware and networks and explicit specification of concurrency properties intrinsic to the application. The fact that the implementation technologies have not yet caught up with this perspective should not cause us to teach the wrong engineering approach. We should teach design and modeling as it should be, and enrich this with a critical presentation of how it is. Embedded systems technologies today, therefore, should not be presented dispassionately as a collection of facts and tricks, as they are in many of the above cited books, but rather as stepping stones towards a sound design practice. The focus should be on what that sound design practice is, and on how today’s technologies both impede and achieve it.

Lee & Seshia, Introduction to Embedded Systems xiii

http://LeeSeshia.org
PREFACE

Stankovic et al. (2005) support this view, stating that “existing technology for RTES [real- time embedded systems] design does not effectively support the development of reliable and robust embedded systems.” They cite a need to “raise the level of programming abstraction.” We argue that raising the level of abstraction is insufficient. We also have to fundamentally change the abstractions that are used. Timing properties of software, for example, cannot be effectively introduced at higher levels of abstraction if they are entirely absent from the lower levels of abstraction on which these are built.

We require robust and predictable designs with repeatable temporal dynamics (Lee, 2009a). We must do this by building abstractions that appropriately reflect the realities of cyber- physical systems. The result will be CPS designs that can be much more sophisticated, including more adaptive control logic, evolvability over time, and improved safety and re- liability, all without suffering from the brittleness of today’s designs, where small changes have big consequences.

In addition to dealing with temporal dynamics, CPS designs invariably face challenging concurrency issues. Because software is so deeply rooted in sequential abstractions, con- currency mechanisms such as interrupts and multitasking, using semaphores and mutual exclusion, loom large. We therefore devote considerable effort in this book to developing a critical understanding of threads, message passing, deadlock avoidance, race conditions, and data determinism.

Note about This Edition

This is the second edition of the textbook. In addition to several bug fixes and improve- ments to presentation and wording, it includes two new chapters. Chapter 7 covers sensors and actuators with an emphasis on modeling. Chapter 17 covers the basics of security and privacy for embedded systems.

What Is Missing

Even with the new additions, this version of the book is not complete. It is arguable, in fact, that complete coverage of embedded systems in the context of CPS is impossible. Specific topics that we cover in the undergraduate Embedded Systems course at Berkeley (see http://LeeSeshia.org) and hope to include in future versions of this book include networking, fault tolerance, simulation techniques, control theory, and hardware/software codesign.

xiv Lee & Seshia, Introduction to Embedded Systems

http://LeeSeshia.org
http://LeeSeshia.org
PREFACE

Figure 1: Map of the book with strong and weak dependencies between chapters. Strong dependencies between chapters are shown with arrows in black. Weak dependencies are shown in grey. When there is a weak dependency from chapter i to chapter j, then j may mostly be read without reading i, at most requiring skipping some examples or specialized analysis techniques.

Lee & Seshia, Introduction to Embedded Systems xv

http://LeeSeshia.org
PREFACE

How to Use This Book

This book is divided into three major parts, focused on modeling, design, and analysis, as shown in Figure 1. The three parts of the book are relatively independent of one another and are largely meant to be read concurrently. A systematic reading of the text can be accomplished in eight segments, shown with dashed outlines. Most segments include two chapters, so complete coverage of the text is possible in a 15 week semester, allowing two weeks for most modules.

The appendices provide background material that is well covered in other textbooks, but which can be quite helpful in reading this text. Appendix A reviews the notation of sets and functions. This notation enables a higher level of precision than is common in the study of embedded systems. Appendix B reviews basic results in the theory of computability and complexity. This facilitates a deeper understanding of the challenges in modeling and analysis of systems. Note that Appendix B relies on the formalism of state machines covered in Chapter 3, and hence should be read after reading Chapter 3.

In recognition of recent advances in technology that are fundamentally changing the tech- nical publishing industry, this book is published in a non-traditional way. At least the present version is available free in the form of PDF file designed specifically for reading on tablet computers. It can be obtained from the website http://LeeSeshia.org. The layout is optimized for medium-sized screens, particularly laptop computers and the iPad and other tablets. Extensive use of hyperlinks and color enhance the online reading experi- ence.

We attempted to adapt the book to e-book formats, which, in theory, enable reading on various sized screens, attempting to take best advantage of the available screen. However, like HTML documents, e-book formats use a reflow technology, where page layout is recomputed on the fly. The results are highly dependent on the screen size and prove ludicrous on many screens and suboptimal on all. As a consequence, we have opted for controlling the layout, and we do not recommend attempting to read the book on an smartphone.

Although the electronic form is convenient, we recognize that there is real value in a tangible manifestation on paper, something you can thumb through, something that can live on a bookshelf to remind you of its existence. This edition is published by MIT Press, who has assured us that they will keep the book affordable.

xvi Lee & Seshia, Introduction to Embedded Systems

http://LeeSeshia.org
http://LeeSeshia.org
PREFACE

Two disadvantages of print media compared to electronic media are the lack of hyperlinks and the lack of text search. We have attempted to compensate for those limitations by providing page number references in the margins whenever a term is used that is defined elsewhere. The term that is defined elsewhere is underlined with a discrete light gray line. In addition, we have provided an extensive index, with more than 2,000 entries.

There are typographic conventions worth noting. When a term is being defined, it will ap- pear in bold face, and the corresponding index entry will also be in bold face. Hyperlinks are shown in blue in the electronic version. The notation used in diagrams, such as those for finite-state machines, is intended to be familiar, but not to conform with any particular programming or modeling language.

Intended Audience

This book is intended for students at the advanced undergraduate level or introductory graduate level, and for practicing engineers and computer scientists who wish to under- stand the engineering principles of embedded systems. We assume that the reader has some exposure to machine structures (e.g., should know what an ALU is), computer pro- gramming (we use C throughout the text), basic discrete mathematics and algorithms, and at least an appreciation for signals and systems (what it means to sample a continuous- time signal, for example).

Reporting Errors

If you find errors or typos in this book, or if you have suggestions for improvements or other comments, please send email to:

authors@leeseshia.org

Please include the version number of the book, whether it is the electronic or the hard- copy distribution, and the relevant page numbers. Thank you!

Lee & Seshia, Introduction to Embedded Systems xvii

mailto:authors@leeseshia.org
http://LeeSeshia.org
PREFACE

Acknowledgments

The authors gratefully acknowledge contributions and helpful suggestions from Murat Arcak, Dai Bui, Janette Cardoso, Gage Eads, Stephen Edwards, Suhaib Fahmy, Shanna- Shaye Forbes, Daniel Holcomb, Jeff C. Jensen, Garvit Juniwal, Hokeun Kim, Jonathan Kotker, Wenchao Li, Isaac Liu, Slobodan Matic, Mayeul Marcadella, Le Ngoc Minh, Christian Motika, Chris Myers, Steve Neuendorffer, David Olsen, Minxue Pan, Hiren Pa- tel, Jan Reineke, Rhonda Righter, Alberto Sangiovanni-Vincentelli, Chris Shaver, Shih- Kai Su (together with students in CSE 522, lectured by Dr. Georgios E. Fainekos at Arizona State University), Stavros Tripakis, Pravin Varaiya, Reinhard von Hanxleden, Armin Wasicek, Kevin Weekly, Maarten Wiggers, Qi Zhu, and the students in UC Berke- ley’s EECS 149 class over the past years, particularly Ned Bass and Dan Lynch. The authors are especially grateful to Elaine Cheong, who carefully read most chapters and offered helpful editorial suggestions. We also acknowledge the bug fixes and suggestions sent in by several readers which has helped us improve the book since its initial publica- tion. We give special thanks to our families for their patience and support, particularly to Helen, Katalina, and Rhonda (from Edward), and Amma, Appa, Ashwin, Bharathi, Shriya, and Viraj (from Sanjit).

This book is almost entirely constructed using open-source software. The typesetting is done using LaTeX, and many of the figures are created using Ptolemy II. See:

http://ptolemy.org

xviii Lee & Seshia, Introduction to Embedded Systems

http://ptolemy.org
http://LeeSeshia.org
PREFACE

Further Reading

Many textbooks on embedded systems have appeared in recent years. These books approach the subject in surprisingly diverse ways, often reflecting the perspective of a more established discipline that has migrated into embedded systems, such as VLSI design, control systems, signal processing, robotics, real-time systems, or software engineering. Some of these books complement the present one nicely. We strongly recommend them to the reader who wishes to broaden his or her understanding of the subject.

Specifically, Patterson and Hennessy (1996), although not focused on embedded pro- cessors, is the canonical reference for computer architecture, and a must-read for any- one interested embedded processor architectures. Sriram and Bhattacharyya (2009) fo- cus on signal processing applications, such as wireless communications and digital me- dia, and give particularly thorough coverage to dataflow programming methodologies. Wolf (2000) gives an excellent overview of hardware design techniques and micropro- cessor architectures and their implications for embedded software design. Mishra and Dutt (2005) give a view of embedded architectures based on architecture description languages (ADLs). Oshana (2006) specializes in DSP processors from Texas Instru- ments, giving an overview of architectural approaches and a sense of assembly-level programming.

Focused more on software, Buttazzo (2005a) is an excellent overview of schedul- ing techniques for real-time software. Liu (2000) gives one of the best treatments yet of techniques for handling sporadic real-time events in software. Edwards (2000) gives a good overview of domain-specific higher-level programming languages used in some embedded system designs. Pottie and Kaiser (2005) give a good overview of networking technologies, particularly wireless, for embedded systems. Koopman (2010) focuses on design process for embedded software, including requirements man- agement, project management, testing plans, and security plans. Alur (2015) provides an excellent, in-depth treatment of formal modeling and verification of cyber-physical systems.

No single textbook can comprehensively cover the breadth of technologies available to the embedded systems engineer. We have found useful information in many of the books that focus primarily on today’s design techniques (Barr and Massa, 2006; Berger, 2002; Burns and Wellings, 2001; Gajski et al., 2009; Kamal, 2008; Noergaard, 2005; Parab et al., 2007; Simon, 2006; Schaumont, 2010; Vahid and Givargis, 2010).

Lee & Seshia, Introduction to Embedded Systems xix

http://LeeSeshia.org
PREFACE

Notes for Instructors

At Berkeley, we use this text for an advanced undergraduate course called Introduction to Embedded Systems. A great deal of material for lectures and labs can be found via the main web page for this text:

http://leeseshia.org

In addition, a solutions manual and other instructional material are available to qualified instructors at bona fide teaching institutions. See

http://chess.eecs.berkeley.edu/instructors/

or contact authors@leeseshia.org.

xx Lee & Seshia, Introduction to Embedded Systems

http://leeseshia.org
http://chess.eecs.berkeley.edu/instructors/
mailto:authors@leeseshia.org
http://LeeSeshia.org
1 Introduction

1.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Sidebar: About the Term “Cyber-Physical Systems” . . . . . . . . . . 5

1.2 Motivating Example . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 The Design Process . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.3.1 Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.2 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

A cyber-physical system (CPS) is an integration of computation with physical processes whose behavior is defined by both cyber and physical parts of the system. Embedded com- puters and networks monitor and control the physical processes, usually with feedback loops where physical processes affect computations and vice versa. As an intellectual challenge, CPS is about the intersection, not the union, of the physical and the cyber. It is not sufficient to separately understand the physical components and the computational components. We must instead understand their interaction.

In this chapter, we use a few CPS applications to outline the engineering principles of such systems and the processes by which they are designed.

1.1. APPLICATIONS

1.1 Applications

CPS applications arguably have the potential to eclipse the 20th century information tech- nology (IT) revolution. Consider the following examples.

Example 1.1: Heart surgery often requires stopping the heart, performing the surgery, and then restarting the heart. Such surgery is extremely risky and carries many detrimental side effects. A number of research teams have been working on an alternative where a surgeon can operate on a beating heart rather than stopping the heart. There are two key ideas that make this possible. First, surgical tools can be robotically controlled so that they move with the motion of the heart (Kre- men, 2008). A surgeon can therefore use a tool to apply constant pressure to a point on the heart while the heart continues to beat. Second, a stereoscopic video system can present to the surgeon a video illusion of a still heart (Rice, 2008). To the surgeon, it looks as if the heart has been stopped, while in reality, the heart continues to beat. To realize such a surgical system requires extensive modeling of the heart, the tools, the computational hardware, and the software. It requires careful design of the software that ensures precise timing and safe fallback be- haviors to handle malfunctions. And it requires detailed analysis of the models and the designs to provide high confidence.

Example 1.2: Consider a city where traffic lights and cars cooperate to ensure efficient flow of traffic. In particular, imagine never having to stop at a red light unless there is actual cross traffic. Such a system could be realized with expensive infrastructure that detects cars on the road. But a better approach might be to have the cars themselves cooperate. They track their position and communicate to cooperatively use shared resources such as intersections. Making such a system reliable, of course, is essential to its viability. Failures could be disastrous.

2 Lee & Seshia, Introduction to Embedded Systems

http://LeeSeshia.org
1. INTRODUCTION

Example 1.3: Imagine an airplane that refuses to crash. While preventing all possible causes of a crash is not possible, a well-designed flight control system can prevent certain causes. The systems that do this are good examples of cyber- physical systems.

In traditional aircraft, a pilot controls the aircraft through mechanical and hy- draulic linkages between controls in the cockpit and movable surfaces on the wings and tail of the aircraft. In a fly-by-wire aircraft, the pilot commands are mediated by a flight computer and sent electronically over a network to actuators in the wings and tail. Fly-by-wire aircraft are much lighter than traditional air- craft, and therefore more fuel efficient. They have also proven to be more reliable. Virtually all new aircraft designs are fly-by-wire systems.

In a fly-by-wire aircraft, since a computer mediates the commands from the pilot, the computer can modify the commands. Many modern flight control systems modify pilot commands in certain circumstances. For example, commercial air- planes made by Airbus use a technique called flight envelope protection to pre- vent an airplane from going outside its safe operating range. They can prevent a pilot from causing a stall, for example.

The concept of flight envelope protection could be extended to help prevent cer- tain other causes of crashes. For example, the soft walls system proposed by Lee (2001), if implemented, would track the location of the aircraft on which it is installed and prevent it from flying into obstacles such as mountains and build- ings. In Lee’s proposal, as an aircraft approaches the boundary of an obstacle, the fly-by-wire flight control system creates a virtual pushing force that forces the aircraft away. The pilot feels as if the aircraft has hit a soft wall that diverts it. There are many challenges, both technical and non-technical, to designing and deploying such a system. See Lee (2003) for a discussion of some of these issues.

Although the soft walls system of the previous example is rather futuristic, there are mod- est versions in automotive safety that have been deployed or are in advanced stages of research and development. For example, many cars today detect inadvertent lane changes and warn the driver. Consider the much more challenging problem of automatically cor- recting the driver’s actions. This is clearly much harder than just warning the driver.

Lee & Seshia, Introduction to Embedded Systems 3

http://LeeSeshia.org
1.1. APPLICATIONS

How can you ensure that the system will react and take over only when needed, and only exactly to the extent to which intervention is needed?

It is easy to imagine many other applications, such as systems that assist the elderly; telesurgery systems that allow a surgeon to perform an operation at a remote location; and home appliances that cooperate to smooth demand for electricity on the power grid. Moreover, it is easy to envision using CPS to improve many existing systems, such as robotic manufacturing systems; electric power generation and distribution; process con- trol in chemical factories; distributed computer games; transportation of manufactured goods; heating, cooling, and lighting in buildings; people movers such as elevators; and bridges that monitor their own state of health. The impact of such improvements on safety, energy consumption, and the economy is potentially enormous.

Many of the above examples will be deployed using a structure like that sketched in Figure 1.1. There are three main parts in this sketch. First, the physical plant is the “physical” part of a cyber-physical system. It is simply that part of the system that is not realized with computers or digital networks. It can include mechanical parts, biological or chemical processes, or human operators. Second, there are one or more computational platforms, which consist of sensors, actuators, one or more computers, and (possibly) one or more operating systems. Third, there is a network fabric, which provides the mechanisms for the computers to communicate. Together, the platforms and the network fabric form the “cyber” part of the cyber-physical system.

Figure 1.1 shows two networked platforms each with its own sensors and/or actuators. The action taken by the actuators affects the data provided by the sensors through the physical plant. In the figure, Platform 2 controls the physical plant via Actuator 1. It mea- sures the processes in the physical plant using Sensor 2. The box labeled Computation 2 implements a control law, which determines based on the sensor data what commands to issue to the actuator. Such a loop is called a feedback control loop. Platform 1 makes additional measurements using Sensor 1, and sends messages to Platform 2 via the net- work fabric. Computation 3 realizes an additional control law, which is merged with that of Computation 2, possibly preempting it.

Example 1.4: Consider a high-speed printing press for a print-on-demand ser- vice. This might be structured similarly to Figure 1.1, but with many more plat- forms, sensors, and actuators. The actuators may control motors that drive paper through the press and ink onto the paper. The control laws may include a strategy

4 Lee & Seshia, Introduction to Embedded Systems

http://LeeSeshia.org
1. INTRODUCTION

About the Term “Cyber-Physical Systems” The term “cyber-physical systems” emerged in 2006, coined by Helen Gill at the National Science Foundation in the US. We may be tempted to associate the term “cyberspace” with CPS, but the roots of the term CPS are older and deeper. It would be more accurate to view the terms “cyberspace” and “cyber-physical systems” as stem- ming from the same root, “cybernetics,” rather than viewing one as being derived from the other.

The term “cybernetics” was coined by Norbert Wiener (Wiener, 1948), an Amer- ican mathematician who had a huge impact on the development of control systems theory. During World War II, Wiener pioneered technology for the automatic aim- ing and firing of anti-aircraft guns. Although the mechanisms he used did not involve digital computers, the principles involved are similar to those used today in a huge variety of computer-based feedback control systems. Wiener derived the term from the Greek κυβερνητης (kybernetes), meaning helmsman, governor, pilot, or rudder. The metaphor is apt for control systems. Wiener described his vision of cybernetics as the conjunction of control and communication. His notion of control was deeply rooted in closed-loop feedback, where the control logic is driven by measurements of physical processes, and in turn drives the physical processes. Even though Wiener did not use digital computers, the control logic is effectively a computation, and therefore cybernetics is the conjunction of physical processes, computation, and communica- tion. Wiener could not have anticipated the powerful effects of digital computation and networks. The fact that the term “cyber-physical systems” may be ambiguously interpreted as the conjunction of cyberspace with physical processes, therefore, helps to underscore the enormous impact that CPS will have. CPS leverages an information technology that far outstrips even the wildest dreams of Wiener’s era.

The term CPS relates to the currently popular terms Internet of Things (IoT), Indus- try 4.0, the Industrial Internet, Machine-to-Machine (M2M), the Internet of Everything, TSensors (trillion sensors), and the Fog (like the Cloud, but closer to the ground). All of these reflect a vision of a technology that deeply connects our physical world with our information world. In our view, the term CPS is more foundational and durable than all of these, because it does not directly reference either implementation approaches (e.g., the “Internet” in IoT) nor particular applications (e.g., “Industry” in Industry 4.0). It focuses instead on the fundamental intellectual problem of conjoining the engineering traditions of the cyber and the physical worlds.

Lee & Seshia, Introduction to Embedded Systems 5

http://LeeSeshia.org
1.2. MOTIVATING EXAMPLE

Figure 1.1: Example structure of a cyber-physical system.

for compensating for paper stretch, which will typically depend on the type of pa- per, the temperature, and the humidity. A networked structure like that in Figure 1.1 might be used to induce rapid shutdown to prevent damage to the equipment in case of paper jams. Such shutdowns need to be tightly orchestrated across the entire system to prevent disasters. Similar situations are found in high-end in- strumentation systems and in energy production and distribution (Eidson et al., 2009).

1.2 Motivating Example

In this section, we describe a motivating example of a cyber-physical system. Our goal is to use this example to illustrate the importance of the breadth of topics covered in this text. The specific application is the Stanford testbed of autonomous rotorcraft for multi agent control (STARMAC), developed by Claire Tomlin and colleagues as a cooperative effort at Stanford and Berkeley (Hoffmann et al., 2004). The STARMAC is a small quadrotor aircraft; it is shown in flight in Figure 1.2. Its primary purpose is to serve as a testbed for

6 Lee & Seshia, Introduction to Embedded Systems

http://LeeSeshia.org
1. INTRODUCTION

Figure 1.2: The STARMAC quadrotor aircraft in flight (reproduced with permis- sion).

experimenting with multi-vehicle autonomous control techniques. The objective is to be able to have multiple vehicles cooperate on a common task.

There are considerable challenges in making such a system work. First, controlling the vehicle is not trivial. The main actuators are the four rotors, which produce a variable amount of downward thrust. By balancing the thrust from the four rotors, the vehicle can take off, land, turn, and even flip in the air. How do we determine what thrust to apply? Sophisticated control algorithms are required.

Second, the weight of the vehicle is a major consideration. The heavier it is, the more stored energy it needs to carry, which of course makes it even heavier. The heavier it is, the more thrust it needs to fly, which implies bigger and more powerful motors and rotors. The design crosses a major threshold when the vehicle is heavy enough that the rotors become dangerous to humans. Even with a relatively light vehicle, safety is a considerable concern, and the system needs to be designed with fault handling.

Third, the vehicle needs to operate in a context, interacting with its environment. It might, for example, be under the continuous control of a watchful human who operates it by re- mote control. Or it might be expected to operate autonomously, to take off, perform some mission, return, and land. Autonomous operation is enormously complex and challeng-

Lee & Seshia, Introduction to Embedded Systems 7

http://LeeSeshia.org
1.3. THE DESIGN PROCESS

ing because it cannot benefit from the watchful human. Autonomous operation demands more sophisticated sensors. The vehicle needs to keep track of where it is (it needs to perform localization). It needs to sense obstacles, and it needs to know where the ground is. With good design, it is even possible for such vehicles to autonomously land on the pitching deck of a ship. The vehicle also needs to continuously monitor its own health, to detect malfunctions and react to them so as to contain the damage.

It is not hard to imagine many other applications that share features with the quadrotor problem. The problem of landing a quadrotor vehicle on the deck of a pitching ship is sim- ilar to the problem of operating on a beating heart (see Example 1.1). It requires detailed modeling of the dynamics of the environment (the ship, the heart), and a clear understand- ing of the interaction between the dynamics of the embedded system (the quadrotor, the robot) and its environment.

The rest of this chapter will explain the various parts of this book, using the quadrotor example to illustrate how the various parts contribute to the design of such a system.

Figure 1.3: Creating embedded systems requires an iterative process of model- ing, design, and analysis.

8 Lee & Seshia, Introduction to Embedded Systems

http://LeeSeshia.org
1. INTRODUCTION

1.3 The Design Process

The goal of this book is to understand how to go about designing and implementing cyber-physical systems. Figure 1.3 shows the three major parts of the process, modeling, design, and analysis. Modeling is the process of gaining a deeper understanding of a system through imitation. Models imitate the system and reflect properties of the system. Models specify what a system does. Design is the structured creation of artifacts. It specifies how a system does what it does. Analysis is the process of gaining a deeper understanding of a system through dissection. It specifies why a system does what it does (or fails to do what a model says it should do).