实时系统（英文影印版） (2009 年度畅销榜NO.11584 )

本书内容及特色如下：\r\n\r\n 1．理论性强。对许多问题用数学语言进行了形式化描述，给出了相关的公式、定义、定理，并进行了推导或证明。本书集中了两位作者从事实时系统教学和研究工作近2O年所取得的成果，同时也包含了该领域国际上许多最新的研究成果。\r\n\r\n 2．可读性好。每章通过许多例题阐述了相关实时系统的设计方法和性能评价方法，分析了目前许多先进的实时系统的各个方面。因此本书不仅理论性强，同时也非常注重理论联系实际，便于读者阅读。\r\n\r\n 3．注重系统设计与性能评价。全书以实时系统的设计方法和性能评价方法为主线展开，讲述了多种实时系统的设计方法和性能评价方法，同时也介绍了几种进行实时系统设计和性能评价的工具。读者学会了这些设计方法和评价工具，对研究和开发其他实时系统很有帮助。\r\n\r\n 4．硬件和软件结合。大多数实时系统是由硬件和软件共同组成的，本书在分别介绍硬件部分和软件部分的工作原理、设计方法和性能分析方法的同时，也给出了在设计实时系统时软件与硬件如何做到平衡。\r\n\r\n\r\n
\r\n

Preface \r\n\r\n 1 Introduction \r\n\r\n 1.1 A Car-and-Driver Example \r\n\r\n 1.2 Issues in Real-Time Computing \r\n\r\n 1.3 Structure of a Real-Time System \r\n\r\n 1.4 Task Classes \r\n\r\n 1.5 Issues Covered in this Book \r\n\r\n 1.5.1 Architecture Issues \r\n\r\n 1.5.2 Operating System Issues \r\n\r\n 1.5.3 Other Issues \r\n\r\n 2 Characterizing Real-Time Systems and Tasks \r\n\r\n 2.1 Introdoction \r\n\r\n 2.2 Performance Measures for Real-Time Systems \r\n\r\n 2.2.1 Properties of Performance Measures \r\n\r\n 2.2.2 Traditional Performance Measures \r\n\r\n 2.2.3 Performability \r\n\r\n 2.2.4 Cost Functions and Hard Deadlines \r\n\r\n 2.2.5 Discussion \r\n\r\n 2.3 Estimating Program Run Times \r\n\r\n 2.3.1 Analysis of Source Code \r\n\r\n 2.3.2 Accounting for Pipelining \r\n\r\n 2.3.3 Caches \r\n\r\n 2.3.4 Virtual Memory \r\n\r\n 2.4 Soggestions For Funher Reading \r\n\r\n Exercises \r\n\r\n References \r\n\r\n 3 Task Assignment and Scheduling \r\n\r\n 3.1 Invoduction \r\n\r\n 3.1.1 How to Read This Chapter \r\n\r\n 3.1.2 Notation \r\n\r\n 3.2 Classical Uniprocessor Scheduling Algorithms \r\n\r\n 3.2.l Rate-Monotonic Scheduling Algorithm \r\n\r\n 3.2.2 Preemptive Earliest Deadline First \r\n\r\n (EDF) Algorithm \r\n\r\n 3.2.3 Allowing for Precedence and Exclusion Conditions' \r\n\r\n 3.2.4 Using Primary and Alternative Tasks \r\n\r\n 3.3 Uniprocessor Scheduling of IRIS Tasks \r\n\r\n 3.3.1 Identical Linear Reward Functions \r\n\r\n 3.3.2 Nonidentical Linear Reward Functions \r\n\r\n 3.3.3 0/1 Reward Functions \r\n\r\n 3.3.4 Identical Concave Reward Functions \r\n\r\n (No Mandatory Portions) \r\n\r\n 3.3.5 Nonidentical Concave Reward Functions' \r\n\r\n 3.4 Task Assignment \r\n\r\n 3.4.1 Utilization-Balancing Algorithm \r\n\r\n 3.4.2 A Next-Fit Algorithm for RM Scheduling \r\n\r\n 3.4.3 A Bin-Packing Assignment Algorithm for EDF \r\n\r\n 3.4.4 A Myopic Offline Scheduling (MOS) Algorithm \r\n\r\n 3.4.5 Focused Addressing and Bidding (FAB) Algorithm \r\n\r\n 3.4.6 The Buddy Strategy \r\n\r\n 3.4.7 Assignment with Precedence Conditions \r\n\r\n 3.5 Mode Changes \r\n\r\n 3.6 Fault-Tolerant Scheduling \r\n\r\n 3.7 Suggestions for Further Reading \r\n\r\n Exercises \r\n\r\n References \r\n\r\n 4 Programming Languages and Tools \r\n\r\n 4.1 Introduction \r\n\r\n 4.2 Desired Language Characteristics \r\n\r\n 4.3 Data Typing \r\n\r\n 4.4 Control Structures \r\n\r\n 4.5 Facilitating Hierarchical Decomposition \r\n\r\n 4.5.1 Blocks \r\n\r\n 4.5.2 Procedures and Functions \r\n\r\n 4.6 Packages \r\n\r\n 4.7 Run-Time Error (Exception) Handling \r\n\r\n 4.8 Overloading and Generics \r\n\r\n 4.9 Multitasking \r\n\r\n 4.1O Low-Level Programming \r\n\r\n 4.11 Task Scheduling \r\n\r\n 4.11.1 Task Dispatching Policy \r\n\r\n 4.11.2 Entry Queueing Policy \r\n\r\n 4.11.3 protected Data Types \r\n\r\n 4.12 Timing Specifications \r\n\r\n 4.13 Some Experimental Languages \r\n\r\n 4.13.1 Flex \r\n\r\n 4.13.2 Euclid \r\n\r\n 4.14 Programming Environments \r\n\r\n 4.15 Run-Time Support \r\n\r\n 4.15.1 Compiler \r\n\r\n 4.15.2 Linker \r\n\r\n 4.15.3 Debagger \r\n\r\n 4.15.4 Kernel \r\n\r\n 4.16 Suggestions for Further Reading \r\n\r\n Exercises \r\n\r\n References \r\n\r\n 5 Real-Time Databases \r\n\r\n 5.1 Introduction \r\n\r\n 5.2 Basic Definitions \r\n\r\n 5.3 Real-Time vs. General-Purpose Databases \r\n\r\n 5.3.1 Absolute vs. Relative Consistency \r\n\r\n 5.3.2 Need for Response-Time predictability \r\n\r\n 5.3.3 Relaxing the ACID Properties \r\n\r\n 5.4 Main Memory Databases \r\n\r\n 5.5 Transaction Priorities \r\n\r\n 5.6 Transaction Aborts \r\n\r\n 5.7 Concurrency Control Issues \r\n\r\n 5.7.1 Pessimistic Concarrency Control \r\n\r\n 5.7.2 Optimistic Concanency Control \r\n\r\n 5.8 Disk Scheduling Algorithms \r\n\r\n 5.9 A Two-Phase Approach to Improve Predictability \r\n\r\n 5.1O Maintaining Serialization Consistency \r\n\r\n 5.1O.1 Serialization Consistency without Altemtion of \r\n\r\n Serialization Order \r\n\r\n 5.1O.2 Serialization Consistency with Alteration of \r\n\r\n Serialization Order \r\n\r\n 5.11 Databases for Hard Real-Time Systems \r\n\r\n 5.12 Suggestions for Further Reading \r\n\r\n Exercises \r\n\r\n References \r\n\r\n 6 Real-Time Communication \r\n\r\n 6.1 Introduction \r\n\r\n 6.1.1 Communications Media \r\n\r\n 6.2 Network Topologies \r\n\r\n 6.2.1 Sending Messages \r\n\r\n 6.2.2 Network Architecture Issues \r\n\r\n 6.3 Protocols \r\n\r\n 6.3.1 Contention-Based Ptotocols \r\n\r\n 6.3.2 Token-based Protocols \r\n\r\n 6.3.3 Stop-and-Go Multihop Protocol \r\n\r\n 6.3.4 The Polled Bus protocol \r\n\r\n 6.3.5 Hierarchical Round-Robin Protocol \r\n\r\n 6.3.6 Deadline-Based Protocols \r\n\r\n 6.3.7 Fault-Tolerant Routing \r\n\r\n 6.4 Suggestions for Further Reading \r\n\r\n Exercises \r\n\r\n References \r\n\r\n 7 Fault-Tolerance Techniques \r\n\r\n 7.1 Introduction \r\n\r\n 7.1.1 Definitions \r\n\r\n 7.2 What Causes Failures? \r\n\r\n 7.3 Fault Types \r\n\r\n 7.3.1 Temporal Behavior Classification \r\n\r\n 7.3.2 Output Behavior Classification \r\n\r\n 7.3.3 Independence and Correlation \r\n\r\n 7.4 Fault Detection \r\n\r\n 7.5 Fault and Error Containment \r\n\r\n 7.6 Redundancy \r\n\r\n 7.6.1 Hardware Redandancy \r\n\r\n 7.6.2 Sofiware Redundancy \r\n\r\n 7.6.3 Time Redundancy-Implementing Backward Error \r\n\r\n Recovery \r\n\r\n 7.6.4 Information Redundancy \r\n\r\n 7.7 Data Diversity \r\n\r\n 7.8 Reversal Checks \r\n\r\n 7.9 Malicious or Byzantine Failures \r\n\r\n 7.1O Integrated Failure Handling \r\n\r\n 7.11 Suggestions for Further Reading \r\n\r\n Exercises \r\n\r\n References \r\n\r\n 8 Reliability Evaluation Techniques \r\n\r\n 8.1 Introduction \r\n\r\n 8.2 Obtaining Parameter Values \r\n\r\n 8.2.1 Obtaining Device-Failure Rates \r\n\r\n 8.2.2 Measuring Error-Propagation Time \r\n\r\n 8.2.3 Choosing the Best Distribution \r\n\r\n 8.3 Reliability Models for Hardware Redundancy \r\n\r\n 8.3.1 Permanent Faults Only \r\n\r\n 8.3.2 Fault Latency' \r\n\r\n 8.3.3 Introduction of Transient Faults \r\n\r\n 8.3.4 The Use of State Aggegation \r\n\r\n 8.4 Software-Error Models \r\n\r\n 8.4.1 The Limited Usefulness of Software-Error Models \r\n\r\n 8.5 Taking Time into Account \r\n\r\n 8.6 Suggestions for Further Reading \r\n\r\n Exercises \r\n\r\n References \r\n\r\n 9 Clock Synchronization \r\n\r\n 9.1 Introdoction \r\n\r\n 9.2 Clocks \r\n\r\n 9.2.1 Synchronization \r\n\r\n 9.3 A Nonfault-Toterant Synchronization Algorithm \r\n\r\n 9.4 Impact of Faults \r\n\r\n 9.4.1 Loss of Synchrony \r\n\r\n 9.5 Fanlt-Tolerant Synchronization in Hardware \r\n\r\n 9.5.1 Completely Connected, Zero-Propagation-Time System \r\n\r\n 9.5.2 Sparse-Interconnection, Zero-Propagation-Time System \r\n\r\n 9.5.3 Accounting for Signal-Propagation Delays \r\n\r\n 9.5.4 Multiple-Fault Classes \r\n\r\n 9.5.5 Advantages and Disadvantages of Hardware \r\n\r\n Synchronization \r\n\r\n 9.6 Synchronization in Software \r\n\r\n 9.6.1 Interactive Convergence Averaging Algorithm, CA1 \r\n\r\n 9.6.2 Interactive Convergence Averaging Algorithm, CA2 \r\n\r\n 9.6.3 Convergence Nonaveraging Algorialm, CNA \r\n\r\n 9.7 Suggestions for Further Reading \r\n\r\n Exercises \r\n\r\n References \r\n\r\n Appendix Review of Modeling Techniques \r\n\r\n A.1 Review of Basic Probability Theory \r\n\r\n A.2 Z-Transforms and Laplace Transforms \r\n\r\n A.3 Some Important Probability Distribution Fanctions \r\n\r\n A.3.1 The Uniform Distribution Functions \r\n\r\n A.3.2 The Exponential Distribution Functions \r\n\r\n A.3.3 The Poisson Process \r\n\r\n A.3.4 The Erlangian Distribution \r\n\r\n A.3.5 The Weibull Distribution Functions \r\n\r\n A.4 Basics of Markov Modeling \r\n\r\n A.4.1 Discrete-Time Markov Chains \r\n\r\n A.4.2 Continuous-Time Markov Chains \r\n\r\n A.4.3 Some Additional Remarks about Markov Chains \r\n\r\n A.4.4 The Method of Stages \r\n\r\n A.5 A Brief Glimpse of Queueing Theory \r\n\r\n A.6 Saggestions For Further Reading \r\n\r\n References \r\n\r\n Index \r\n
\r\n

Real-time Systems

影印版序

《实时系统》(Red—time Systems)一书由美国Massachusetts大学的C.M. Krishna教授和Michigan大学的Kang G. Shin教授共同编写. 两位教授从事实时系统及相关领域的教学与研究已经很多年, 发表了大量学术论文, 取得了很多项研究成果, 也出版过多本实时系统方面的书籍.

“实时系统”的发展非常迅速, 特别是嵌入式计算机的出现并广泛应用, 推动了实时系统的发展. 在以往出版的相关书籍中, 通常以一二个章节介绍一些具体的实时系统, 如实时控制系统. 实时数据库. 实时操作系统. 实时通信系统等, 本书则全面分析并系统阐述了多种实时系统的工作原理. 设计方法和性能评价方法.

本书可作为理工科相关专业研究生或高年级本科生的教材, 也可作为参考书或研究用资料. 另外, 本书也是相关领域实习工程师必备的一本很好的工具书. 本书的主要特点如下：

1. 理论性强. 对许多问题用数学语言进行了形式化描述, 给出了相关的公式. 定义. 定理, 并进行了推导或证明. 本书主要是根据两位作者从事实时系统方面的教学和研究工作近20年所取得的成果写成的, 同时也包含了该领域国际上许多最新的研究成果.

2. 可读性好. 每章都有许多例题, 有些章有几十个例题, 通过大量的例题阐述了相关实时系统的设计方法和性能评价方法, 通过例题分析了目前许多先进的实时系统的各个方面. 因此, 本书不仅理论性强, 同时也非常注重理论联系实际, 便于读者阅读.

3. 注重系统设计与性能评价. 全书以实时系统的设计方法和性能评价方法为主线展开, 讲述了多种实时系统的设计方法和性能评价方法, 同时也介绍了几种进行实时系统设计和性能评价的工具, 读者学会了这些设计方法和评价工具, 对研究和开发其他实时系统很有帮助.

4. 硬件与软件结合. 大多数实时系统是由硬件和软件共同组成的, 本书在分别介绍硬件部分和软件部分的工作原理. 设计方法和性能分析方法的同时, 也给出了在设计实时系统时软件与硬件如何做到平衡.

每章后面都给出进一步阅读的建议, 告诉读者如何深入学习, 并附有参考书和相关论文, 其中有许多论文是本书作者的研究成果. 另外每章后面都有练习题, 便于读者系统掌握本书的内容.

汤志忠教授

清华大学计算机科学与技术系

2001年7月

Real-time systems have proliferated over the past few years.Today, computers are found embedded in almost everything, from toasters to cars to fiy-by-wire aircraft. The computational workload of such embedded systems varies widely, from machines expected to do a few arialmetic operations every second to computers executing complex calculations at Remendous rates. The consequences of computer failure also vary widely, from burnt toast at the one extreme to the loss of life in an air crash or a chemical plant explosion at the oaler.

The objective of this book is to introduce readers to design and evaluation issues in such systems. We cover a wide range of topics; both hardware and software issues are ueated in some detail. We expect this book to be used by both practicing engineers and graduate or final-year underpaduate students.

Some of the discussion is mathematical. Wherever possible, we have separated ale more mathematical portions from the descriptive. This enables the text to be read at multiple levels. The more advanced sections are stamed (*); these require additional perseverance or ability to understand them, and can be skipped if necessary. However, we urge the reader to avoid skipping the mathematical ponions. Most often, avoidance of mathematics is grounded on nothing more substantial than a primitive fear of and negative associations with mathematical symbols. A true understanding of many of the issues covered here cannot be achieved without undersanding their mathematical underpinnings.

This book contains far more material than can comfonably be covered in a one-semester course. Instructors may decide to concenuate on particular topics, for example, ask assignment and scheduling, or fault-tolerance. Altematively,they may decide to present a wide-ranging survey of the various topics of interest to the real-time systems engineer. To enable both approaches to be used, we have tried to make the chapters as independent of one another as possible. In addition, this allows the book to be used as a reference handbook by the practicing engineer. Typographical or other errors should be reponed to the authors at rtbook@tikva . ecs . umass . edu

We plan to maintain a page of errata on the World Wide Web at

http : / /www. ecs . amass . edu/ece/gradfac/krishna .html

ACKNOWLEDGMENTS

Many people have contributed to making this book a reality. We would like to thank Eric Munson of McGraw-Hill for commissioning it, and for being willing to countenance a delay of over a year beyond our original deadline. It is perhaps ironic that the authors of a book that deals largely with tasks meeting deadlines were themselves unable to meet their contracted deadline!

A number of our colleagues and students have read through this book, either in part on in its entirety, and provided valuable suggestions or pointed out mistakes. We list them below in random order.

Y.-H. Lee C. Ravishankar N. Soparkar

A. Ansari J. Rexford S. H. Son

N. Sud J. Strosnider F. Zhou

A. Mehra W. Feng A. Shaikh

T. Abdelzaher A. Indiresan E. Atkins

P. Ramanathan S. Daniel T. Koprowski

S. Wilson K. Ramamritham W. Preska

Beverly Monaghan of The University of Michigan and June Daehler of ale University of Massachuseffs provided valuable secretarial assistance. Julie F. Nemer of ETP Hamison was the copyeditor, and her comments helped improve the readability of the text. Thanks are also due to Michael J. Kolibaba for coordinating our interactions with the copyeditor and to the following reviewers: Wei Zhao, In-Sup Lee, William Marcy, and Borko Furht.

C. M. Krishna

Kang G. Shin