| |
| |
| Preface | |
| |
| |
| |
| Typical Real-Time Applications | |
| |
| |
| |
| Digital Control | |
| |
| |
| |
| High-Level Controls | |
| |
| |
| |
| Signal Processing | |
| |
| |
| |
| Other Real-Time Applications | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Hard Versus Soft Real-Time Systems | |
| |
| |
| |
| Jobs and Processors | |
| |
| |
| |
| Release Times, Deadlines, and Timing Constraints | |
| |
| |
| |
| Hard and Soft Timing Constraints | |
| |
| |
| |
| Hard Real-Time Systems | |
| |
| |
| |
| Soft Real-Time Systems | |
| |
| |
| |
| Summary | |
| |
| |
| |
| A Reference Model of Real-Time Systems | |
| |
| |
| |
| Processors and Resources | |
| |
| |
| |
| Temporal Parameters of Real-Time Workload | |
| |
| |
| |
| Periodic Task Model | |
| |
| |
| |
| Precedence Constraints and Data Dependency | |
| |
| |
| |
| Other Types of Dependencies | |
| |
| |
| |
| Functional Parameters | |
| |
| |
| |
| Resource Parameters of Jobs and Parameters of Resources | |
| |
| |
| |
| Scheduling Hierarchy | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Commonly Used Approaches to Real-Time Scheduling | |
| |
| |
| |
| Clock-Driven Approach | |
| |
| |
| |
| Weighted Round-Robin Approach | |
| |
| |
| |
| Priority-Driven Approach | |
| |
| |
| |
| Dynamic versus Static Systems | |
| |
| |
| |
| Effective Release Times and Deadlines | |
| |
| |
| |
| Optimality of the EDF and LST Algorithms | |
| |
| |
| |
| Nonoptimality of the EDF and the LST Algorithms | |
| |
| |
| |
| Challenges in Validating Timing Constraints in Priority-Driven Systems | |
| |
| |
| |
| Off-Line versus On-Line Scheduling | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Clock-Driven Scheduling | |
| |
| |
| |
| Notations and Assumptions | |
| |
| |
| |
| Static, Timer-Driven Scheduler | |
| |
| |
| |
| General Structure of Cyclic Schedules | |
| |
| |
| |
| Cyclic Executives | |
| |
| |
| |
| Improving the Average Response Time of Aperiodic Jobs | |
| |
| |
| |
| Scheduling Sporadic Jobs | |
| |
| |
| |
| Practical Considerations and Generalizations | |
| |
| |
| |
| Algorithm for Constructing Static Schedules | |
| |
| |
| |
| Pros and Cons of Clock-Driven Scheduling | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Priority-Driven Scheduling of Periodic Tasks | |
| |
| |
| |
| Static Assumption | |
| |
| |
| |
| Fixed-Priority versus Dynamic-Priority Algorithms | |
| |
| |
| |
| Maximum Schedulable Utilization | |
| |
| |
| |
| Optimality of the RM and DM Algorithms | |
| |
| |
| |
| A Schedulability Test for Fixed-Priority Tasks with Short Response Times | |
| |
| |
| |
| Schedulability Test for Fixed-Priority Tasks with Arbitrary Response Times | |
| |
| |
| |
| Sufficient Schedulability Conditions for the RM and DM Algorithms | |
| |
| |
| |
| Practical Factors | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Scheduling Aperiodic and Sporadic Jobs in Priority-Driven Systems | |
| |
| |
| |
| Assumptions and Approaches | |
| |
| |
| |
| Deferrable Servers | |
| |
| |
| |
| Sporadic Servers | |
| |
| |
| |
| Constant Utilization, Total Bandwidth, and Weighted Fair-Queueing Servers | |
| |
| |
| |
| Slack Stealing in Deadline-Driven Systems | |
| |
| |
| |
| Slack Stealing in Fixed-Priority Systems | |
| |
| |
| |
| Scheduling of Sporadic Jobs | |
| |
| |
| |
| Real-Time Performance for Jobs with Soft Timing Constraints | |
| |
| |
| |
| A Two-Level Scheme for Integrated Scheduling | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Resources and Resource Access Control | |
| |
| |
| |
| Assumptions on Resources and Their Usage | |
| |
| |
| |
| Effects of Resource Contention and Resource Access Control | |
| |
| |
| |
| Nonpreemptive Critical Sections | |
| |
| |
| |
| Basic Priority-Inheritance Protocol | |
| |
| |
| |
| Basic Priority-Ceiling Protocol | |
| |
| |
| |
| Stack-Based, Priority-Ceiling (Ceiling-Priority) Protocol | |
| |
| |
| |
| Use of Priority-Ceiling Protocol in Dynamic-Priority Systems | |
| |
| |
| |
| Preemption-Ceiling Protocol | |
| |
| |
| |
| Controlling Accesses to Multiple-Unit Resources | |
| |
| |
| |
| Controlling Concurrent Accesses to Data Objects | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Multiprocessor Scheduling, Resource Access Control, and Synchronization | |
| |
| |
| |
| Model of Multiprocessor and Distributed Systems | |
| |
| |
| |
| Task Assignment | |
| |
| |
| |
| Multiprocessor Priority-Ceiling Protocol | |
| |
| |
| |
| Elements of Scheduling Algorithms for End-to-End Periodic Tasks | |
| |
| |
| |
| Schedulability of Fixed-Priority End-to-End Periodic Tasks | |
| |
| |
| |
| End-to-End Tasks in Heterogeneous Systems | |
| |
| |
| |
| Predictability and Validation of Dynamic Multiprocessor Systems | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Scheduling Flexible Computations and Tasks with Temporal Distance Constraints | |
| |
| |
| |
| Flexible Applications | |
| |
| |
| |
| Tasks with Temporal Distance Constraints | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Real-Time Communication | |
| |
| |
| |
| Model of Real-Time Communication | |
| |
| |
| |
| Priority-Based Service Disciplines for Switched Networks | |
| |
| |
| |
| Weighted Round-Robin Service Disciplines | |
| |
| |
| |
| Medium Access-Control Protocols of Broadcast Networks | |
| |
| |
| |
| Internet and Resource Reservation Protocols | |
| |
| |
| |
| Real-Time Protocol | |
| |
| |
| |
| Communication in Multicomputer Systems | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Operating Systems | |
| |
| |
| |
| Overview | |
| |
| |
| |
| Time Services and Scheduling Mechanisms | |
| |
| |
| |
| Other Basic Operating System Functions | |
| |
| |
| |
| Processor Reserves and Resource Kernel | |
| |
| |
| |
| Open System Architecture | |
| |
| |
| |
| Capabilities of Commercial Real-Time Operating Systems | |
| |
| |
| |
| Predictability of General-Purpose Operating Systems | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Posix Thread and Real-Time Extensions | |
| |
| |
| Bibliography | |
| |
| |
| Index | |