实时系统：英文本

　　20世纪末，以计算机和通信技术为代表的信息科学和技术对世界经济、科技、军事、教育和文化等产生了深刻影响。信息科学技术的迅速普及和应用，带动了世界范围信息产业的蓬勃发展，为许多国家带来了丰厚的回报。 进入21世纪，尤其随着我国加入WTO，信息产业的国际竞争将更加激烈。我国信息产业虽然在20世纪末取得了迅猛发展，但与发达国家相比，甚至与印度、爱尔兰等国家相比，还有很大差距。国家信息化的发展速度和信息产业的国际竞争能力，最终都将取决于信息科学技术人才的质量和数量。引进国外信息科学和技术优秀教材，在有条件的学校推动开展英语授课或双语教学，是教育部为加快培养大批高质量的信息技术人才采取的一项重要举措。 为此，教育部要求由高等教育出版社首先开展信息科学和技术教材的引进试点工作。同时提出了两点要求，一是要高水平，二是要低价格。在高等教育出版社和信息科学技术引进教材专家组的努力下，经过比较短的时间，第一批引进的20多种教材已经陆续出版。这套教材出版后受到了广泛的好评，其中有不少是世界信息科学技术领域著名专家、教授的经典之作和反映信息科学技术最新进展的优秀作品，代表了目前世界信息科学技术教育的一流水平，而且价格也是最优惠的，与国内同类自编教材相当。 这项教材引进工作是在教育部高等教育司和高教社的共同组织下，由国内信息科学技术领域的专家、教授广泛参与，在对大量国外教材进行多次遴选的基础上，参考了国内和国外著名大学相关专业的课程设置进行系统引进的。其中，John Wiley公司出版的贝尔实验室信息科学研究中心副总裁Silberchatz教授的经典著作《操作系统概念》，是我们经过反复谈判，做了很多努力才得以引进的。William Stallings先生曾编写了在美国深受欢迎的信息科学技术系列教材，其中有多种教材获得过美国教材和学术著作者协会颁发的计算机科学与工程教材奖，这批引进教材中就有他的两本著作。留美中国学者Jiawei Han先生的《数据挖掘》是该领域中具有里程碑意义的著作。由达特茅斯学院刀Thomas Cormen和麻省理工学院、哥伦比亚大学的几位学者共同编著的经典著作《算法导论》，在经历了11年的锤炼之后于2001年出版了第二版。目前任教于美国Massachusetts大学的James Kurose教授，曾在美国三所高校先后10次获得杰出教师或杰出教学奖，由他主编的《计算机网络》出版后，以其体系新颖、内容先进而倍受欢迎。在努力降低引进教材售价方面，高等教育出版社做了大量和细致的工作。这套引进的教材体现了权威性、系统性、先进性和经济性等特点。

　　作者JaneW.S.Liu现执教于美国伊利诺依大学，是ACM会员，IEEE成员，目前的研究兴趣集中在为实时应用提供开放环境的最佳途径。

PREFA CE
1 TYPICAL REAL-TlME APPLICATJONS
1.1 Digital Control
1.2 High-Level Controls
1.3 Signal Processing
1.4 Other Real-Time Applications
1.5 Summary
2 HARD VERSUS SOFT REAL-TlME SYSTEMS
2.1 Jobs and Processors
2.2 Release Times, Deadlines, and Timing Constraints
2.3 Hard and Soft Timing Constraints
2.4 Hard Real-Time Systems
2.5 Soft Real-Time Systems
2.6 Summary
3 A REFERENCE MODEL OF REAL-TIME SYSTEMS
3.1 Processors and Resources
3.2 Temporal Parameters of Real-Time Workload
3.3 Periodic Task Model
3.4 Precedence Constraints and Data Dependency
3.5 Other Types of Dependencies
3.6 Fanctional Parameters
3.7 Resource Parameters of Jobs and Paramelers of Resources
3.8 Sckeduling Hierarchy
3.9 Summary
4 COMMONLY USED APPROACHES TO REAL-TME SCHEDULIG
4.1 Clock-Driven Approach
4.2 Weighted Round-Robin Approach
4.3 Priority-Driven Approach
4.4 Dynamic versus Static Systems
4.5 Effective Release Times and Deadlines
4.6 Optimality of the EDF and LST Algorithms
4.7 Nonoptimality of the EDF and the LST Algorithms
4.8 Challenges in Validating Timing Constraints
in Ptiority-Driven Systems
4.9 Off-Line versus On-Line Scheduling
4.10 Summry
4.11 Exercises
5 CLOCK-DRIVEN SCHEDULING
5.1 Notations and Assumptions
5.2 Static, Timer-Driven Scheduler
5.3 General Structure of Cyclic Schedules
5.4 Cyclic Executives
5.5 Improving the Average Response Time of Aperiodic Jobs
5.6 Scheduling Sporadic Jobs
5.7 Practical Considerations and Generalizations
5.8 Algorithm for Constructing Static Schedules
5.9 Pros and Cons of Clock-Driven Scheduling
5.10 Sammary
6 PRIOROTY-DRIVEN SCHEDULING OF PERIODIC TASKS
6.1 Static Assumption
6.2 Fixed-Priority versus Dynamic-Ptiority Algorithms
6.3 Maximum Schedulable Utilization
6.4 Optimality of the RM and DM Algorithms
6.5 A Schedulability Test for Fixed-Priority Tasks with Shon Response Times
6.6 Schedulability Test for Fixed-hriority Tasks with Arbitrary Response Times
6.7 Sufficient Schedulability Conditions for the RM and DM Algorthms
6.8 Ptactical Factors
6.9 Sammary
7 SCHEDULING APERIODIC AND SPORADIC JOBS W PRIORITY-DRfVEN SYSTEMS
7.1 Assumptions and Approaches
7.2 Deferrable Servers
7.3 Sporadic Servers
7.4 Constant Utilization, Total Bandwidth, and Weighted Fair-Queueing Servers
7.5 Slack Stealing in Deadline-Driven Systems
7.6 Slack Stealing in Fixed-Priority Systems
7.7 Scheduling of Sporadic Jobs
7.8 Real-Time Performance for Jobs with Soft Timing Constraints
7.9 A Two-Level Scheme for Integrated Scheduling
7.10 Summary
8 RESOURCES AND RESOURCE ACCESS CONTROL
8.1 Assumptions on Resources and Their Usage
8.2 Effects of Resource Contention aad Resource Access Control
8.3 Nonpreemptive Critical Sections
8.4 Basic Priority-Inheritance Protocol
8.5 Basic Priority-Ceiling Protocol
8.6 Stack-Based, Priority-Ceiling (Ceiling-Priority) Protocd
8.7 Use of Priority-Ceiling Protocol in Dynamic-Priority Systems
8.8 Preemption-Ceiling Protocol
8.9 Controlling Accesses to Multiple-Unit Resources
8.10 Controlling Concurrent Accesses to Data Objects
8.11 Summary
9 MU TIPROCESSOR SCHEDULING, RESOURCE ACCESS CONTROL,AND SYNCHRONIZATION
9.1 Model of Multiprocessor and Distributed Systems
9.2 Task Assignment
9.3 Multiprocessor Priority-Ceiling Protocol
9.4 Elements of Scheduling Algorithms for End-to-End Periodic Tasks
9.5 Schedulability of Fixed-Priority End-to-End Periodic Tasks
9.6 End-to-End Tasks in Heterogeneous Systems
9.7 Predictability and Validation of Dynamic Multiprocessor Systems
9.8 Summary
10 SCHEDULING FLEXIBLE COMPPUTATIONS AND TASKS WITH TEMPORAL DISTANCE CONSTRAINTS
10.1 Flexible Applications
10.2 Tasks with Temporal Distance Constraints
10.3 Summary
11 REAL-TlME COMMUNICAION
11.1 Model of Real-Time Communication
11.2 Priority-Based Service Disciplines for Switched Networks
11.3 Weighted Round-Robin Service Disciplines
11.4 Medium Access-Control Protocols of Broadcast Networks
11.5 Internet and Resource Reservation Protocols
11.6 Real-Time Protocol
11.7 Communication in Multicomputer Systems
11.8 Summary
12 OPERATING SYSTENIS
12.1 Overiew
12.2 Time Services and Scheduling Mechanisms
12.3 Other Basic Operating System Functions
12.4 Processor Reserves and Resource Kernel
12.5 Open System Architecture
12.6 Capabilities of Commercial Real-Time Operating Systems
12.7 Predictability of Ceneral-Purpose Operating Systems
12.8 Summary
APPENDIX POSIX THREAD AND REAL-TIME EXTENSIONS
BIBLIOGRAPHY
INDEX