Skip to main content
main-content

Über dieses Buch

This book describes state-of-the-art techniques for designing real-time computer systems. The author shows how to estimate precisely the effect of cache architecture on the execution time of a program, how to dispatch workload on multicore processors to optimize resources, while meeting deadline constraints, and how to use closed-form mathematical approaches to characterize highly variable workloads and their interaction in a networked environment. Readers will learn how to deal with unpredictable timing behaviors of computer systems on different levels of system granularity and abstraction.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract
Embedded systems are playing a more and more important role in our daily life; they exist everywhere in our society from consumer electronics such as multimedia systems, mobile phones, microwave ovens, refrigerators to industrial fields such as robotics, telecommunications, environment monitoring, and nuclear power plants. According to statistics reported by ARTEMIS [1], 98 % computing devices in the world are embedded systems.
Nan Guan

Cache Analysis for WCET Estimation

Frontmatter

Chapter 2. MRU Cache Analysis for WCET Estimation

Abstract
Most previous work on cache analysis for WCET estimation assumes a particular replacement policy LRU. In contrast, much less work has been done for non-LRU policies, since they are generally considered to be very unpredictable. However, most commercial processors are actually equipped with these non-LRU policies, since they are more efficient in terms of hardware cost, power consumption, and thermal output, while still maintaining almost as good average-case performance as LRU.
Nan Guan

Chapter 3. FIFO Cache Analysis for WCET Estimation

Abstract
Although most previous work in cache analysis for WCET estimation assumes the LRU replacement policy, in practice more processors use simpler non-LRU policies for lower cost, power consumption, and thermal output. This chapter focuses on the analysis of FIFO, one of the most widely used cache replacement policies. Previous analysis techniques for FIFO caches are based on the same framework as for LRU caches using qualitative always-hit/always-miss classifications. This approach, though works well for LRU caches, is not suitable to analyze FIFO and usually leads to poor WCET estimation quality.
Nan Guan

Real-Time Scheduling on Multicores

Frontmatter

Chapter 4. Analyzing Preemptive Global Scheduling

Abstract
Recently, there have been several promising techniques developed for schedulability analysis and response time analysis for multiprocessor systems based on over-approximation.
Nan Guan

Chapter 5. Analyzing Non-preemptive Global Scheduling

Abstract
Non-preemptive scheduling is usually considered inferior to preemptive scheduling for time critical systems, because the non-preempti1ve block would lead to poor task responsiveness.
Nan Guan

Chapter 6. Liu and Layland’s Utilization Bound

Abstract
Liu and Layland discovered the famous utilization bound \(N(2^{ \frac{1} {N} } - 1)\) for fixed-priority scheduling on single-processor systems in the 1970s.
Nan Guan

Chapter 7. Parametric Utilization Bounds

Abstract
Future embedded real-time systems will be deployed on multi-core processors to meet the dramatically increasing high-performance and low-power requirements. This trend appeals to generalize established results on uniprocessor scheduling, particularly the various utilization bounds for schedulability test used in system design, to the multiprocessor setting.
Nan Guan

Chapter 8. Cache-Aware Scheduling

Abstract
The major obstacle to use multicores for real-time applications is that we may not predict and provide any guarantee on real-time properties of embedded software on such platforms; the way of handling the on-chip shared resources such as L2 cache may have a significant impact on the timing predictability.
Nan Guan

Real-Time Calculus

Frontmatter

Chapter 9. Finitary Real-Time Calculus

Abstract
Real-time calculus (RTC) is a powerful framework to analyze real-time performance of distributed embedded systems. However, RTC may run into serious analysis efficiency problems when applied to systems of large scale and/or with complex timing parameter characteristics. The main reason is that many RTC operations generate curves with periods equal to the hyper-period of the input curves. Therefore, the analysis in RTC has exponential complexity. In practice the curve periods may explode rapidly when several components are serially connected, which leads to low analysis efficiency.
Nan Guan

Chapter 10. EDF in Real-Time Calculus

Abstract
Response time analysis (RTA) is one of the key problems in real-time system design. This chapter proposes new RTA methods for EDF scheduling, with general system models where workload and resource availability are represented by request/demand bound functions and supply bound functions. The main idea is to derive response time upper bounds by lower-bounding the slack times. We first present a simple over-approximate RTA method, which lower bounds the slack time by measuring the “horizontal distance” between the demand bound function and the supply bound function. Then we present an exact RTA method based on the above idea but eliminating the pessimism in the first analysis. This new exact RTA method not only allows to precisely analyze more general system models than existing EDF RTA techniques, but also significantly improves analysis efficiency. Experiments are conducted to show efficiency improvement of our new RTA technique, and tradeoffs between the analysis precision and efficiency of the two proposed methods are discussed. We also illustrate the application of the proposed RTA techniques to Real-Time Calculus for the analysis of components with EDF scheduling in a distributed computing environment.
Nan Guan

Backmatter

Weitere Informationen