Multiprocessor Scheduling for Real-Time Systems

Frontmatter

1. Introduction: Background, Scope, and Context

Abstract

Motivated by both vastly increased computational demand of real-time workloads and the trend in hardware toward multicore and multiprocessor CPUs, real-time systems are increasingly coming to be implemented upon multiprocessor platforms. Multiprocessor real-time scheduling theory, the subject of this book, is concerned with the development of techniques and methodologies that enable the correct and resource-efficient implementation of real-time systems upon multiprocessor platforms.

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

2. Preliminaries: Workload and Platform Models

Abstract

Multiprocessor real-time scheduling theory studies the scheduling of real-time workloads upon multiprocessor platforms. This chapter describes some of the models that are currently widely used for representing such workloads and platforms, and provides some explanation and justification for the use of these particular models.

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

3. Preliminaries: Scheduling Concepts and Goals

Abstract

In this chapter we define and discuss some concepts that form an important part of the background and vocabulary used in discussions of real-time scheduling. The concepts of feasibility and schedulability, discussed in Sect. 3.1 below, formalize required properties of hard-real-time scheduling algorithms. Section 3.2 introduces a classification of scheduling algorithms that we will be using a lot in the remainder of this book to categorize the different scheduling algorithms we will study. The notions of sustainability and predictability, discussed in Sect. 3.3, formalize some other desired properties we seek in our real-time scheduling algorithms.

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

4. A Review of Selected Results on Uniprocessors

Abstract

In this chapter we briefly review some important concepts and results from uniprocessor real-time scheduling theory that we will be using during our study of multiprocessor real-time systems in the later chapters.

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

5. Implicit-Deadline (L&L) Tasks

Abstract

This chapter, and the next few ones, are devoted to the multiprocessor scheduling of implicit-deadline sporadic task systems. We will see that a large amount of research has been conducted upon this topic, and quite a lot is known. Additionally, many of the techniques and approaches that underpin multiprocessor real-time scheduling theory, and that have subsequently gone on to be used in the analysis of systems represented using more sophisticated workload and platform models, were first discovered in the context of implicit-deadline task systems.

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

6. Partitioned Scheduling of L&L Tasks

Abstract

In this chapter, we consider the partitioned preemptive scheduling of implicit-deadline sporadic task systems on identical multiprocessor platforms.

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

7. Global Dynamic-Priority Scheduling of L&L Tasks

Abstract

Pfair scheduling is characterized by the fact that tasks are explicitly required to make progress at steady rates. Consider a task in which both the parameters Ci and Ti are positive integers, and suppose that a job of this task is released at time-instant to. In a pfair schedule, scheduling decisions are made at integer time boundaries; hence, jobs are scheduled for execution an integer unit at a time (to, too, is assumed to be an integer).

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

8. Global Fixed-Job-Priority Scheduling of L&L Tasks

Abstract

Recall the classification in Sect. 3.2 of scheduling algorithms into dynamic priority (DP), fixed-job priority (FJP), and fixed-task priority (FTP) ones, according to the restrictions that are placed upon the manner in which scheduling algorithms may assign priorities to jobs. This chapter is devoted to FJP scheduling.

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

9. Global Fixed-Task-Priority (FTP) Scheduling of L&L Tasks

Abstract

In fixed-task-priority (FTP) scheduling algorithms, each task is assigned a distinct priority and all the jobs generated by a task inherit the priority of the task. FTP algorithms are therefore a special case of fixed-job-priority (FJP) scheduling algorithms: all FTP algorithms are also FJP algorithms, while not all FJP algorithms are FTP algorithms.

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

10. The Three-Parameter Sporadic Tasks Model

Abstract

We now move on from the implicit-deadline sporadic tasks model: this and the next several chapters discuss the multiprocessor scheduling and analysis of task systems that are modeled using the more general three-parameter sporadic tasks model. There is a lot of ground to cover here, particularly with regards to global scheduling. Some of the results and techniques that we will discuss may be considered to be generalizations of ideas previously introduced in the context of implicit-deadline sporadic task systems; many others are brand new and were developed specifically for three-parameter task systems.

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

11. Partitioned Scheduling

Abstract

In this chapter, we consider approximation algorithms for partitioning a sporadic task system upon an identical multiprocessor platform. Since earliest-deadline-first (\(\textsf{EDF}\)) is known to be an optimal algorithm for scheduling upon a preemptive uniprocessor, we will assume in this chapter that each individual processor will be \(\textsf{EDF}\)-scheduled during run-time.

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

12. Global Scheduling: General Comments

Abstract

The next several chapters delve into the global scheduling of three-parameter sporadic task systems. There is a lot of material to cover here: the real-time scheduling research community has devoted considerable effort to devise schedulability analysis tests for such systems. Since many proposed tests are incomparable to each other in the sense that there are task systems deemed schedulable by one that the others fail to identify as being schedulable, it is difficult to choose just one or a few representative “best” tests to include in this book.

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

13. Density-Based Global Schedulability Tests

Abstract

Most of the utilization-based schedulability tests presented in Chaps. 7–9 concerning the global scheduling of systems of implicitdeadline tasks can be generalized to the constrained- and arbitrarydeadline systems represented by the three-parameters task model, by replacing the utilizations with densities (recall that the density of the task is defined to be ).

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

14. A Strategy for Global Schedulability Analysis

Abstract

In this chapter, we describe, at a high level, a strategy that has proven effective in deriving global schedulability tests. Various specific instantiations of this strategy, yielding different sufficient schedulability tests, are described in the following chapters. (Although we do not cover nonpreemptive schedulability analysis in the book, we point out that this strategy has also been successfully applied to nonpreemptive schedulability analysis [101].)

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

15. The [BCL] and [BAR] Tests

Abstract

In this chapter, we will describe some of the tests that have been developed for global earliest-deadline-first (\(\textsf{EDF}\)) schedulability analysis of three-parameter sporadic task systems.

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

16. The [BAK] Test

Abstract

In this chapter, we present the sufficient schedulability test for global \(\textsf{EDF}\) that was obtained by Baker [19]. This test is based on some very deep insights, and contains some remarkably sophisticated ideas which were incorporated into tests developed later by other researchers. We consider the [BAK] test, and some related results that are also discussed in this chapter, to have played a crucial role in enabling the development of many advanced results concerning global multiprocessor real-time scheduling. However, the [BAK] test itself (as opposed to the ideas contained within it) is of limited significance today.

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

17. Response Time Analysis: The [RTA] Test

Abstract

We now describe a refinement to the basic [BCL] procedure that was proposed by Lee and Shin, that uses response-times of tasks to further reduce potentially the size of the interval of interest that must be considered. Since these response-times are of course not known prior to performing schedulability analysis, the procedure takes on an iterative flavor—maximum (or minimum) values are estimated for response times of all tasks, and these estimated values are then used to iteratively decrease (or increase) the estimations. The details are described in Sect. 17.1 below. This test, which aggregates clever ideas from many prior tests into an integrated framework, appears to perform the best in schedulability experiments upon randomly generated workloads.

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

18. Global Fixed-Task-Priority Scheduling

Abstract

We now describe some of the main schedulability tests for 3-parameter sporadic task systems that are globally scheduled using fixed-task-priority (FTP) scheduling algorithms. It will become evident that many of these tests are derived from the tests presented in the previous chapters for global \(\text{EDF}\) schedulability analysis.

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

19. Speedup Bounds for Global Scheduling

Abstract

In the preceding chapters, we have seen a variety of global schedulability analysis tests for the fixed job priority (FJP) scheduling algorithm \(\textsf{EDF}\), the fixed task priority (FTP) scheduling algorithm deadline monotonic (DM), and the dynamic priority scheduling algorithm [EDZL]. When applied to systems of sporadic three-parameter task systems, the only one of these tests for which a quantitative metric of worst-case performance was obtained is the sc [bak] test (Chap. 16): Corollary 16.1 showed that the processor speedup factor of the [bak] test is no larger than \((3+\sqrt{5})/2\), or \(\approx 2.6181\). In this chapter, we will describe the results of [63] deriving a tight speedup bound of \((2-\frac{1}{m})\) for global \(\textsf{EDF}\) scheduling of three-parameter sporadic task systems upon m processors, and a tight speedup bound of \((3-\frac{1}{m})\) for global DM scheduling of three-parameter sporadic task systems upon m processors. We will also describe how these speedup bounds were used [62, 36, 37] to derive pseudopolynomial time schedulability tests that are within a factor ϵ away from optimal, for ϵ an arbitrarily small positive number.

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

20. Global Dynamic Priority Scheduling

Abstract

In this chapter, we briefly describe the research that had been conducted in the dynamic-priority scheduling of systems of three-parameter sporadic tasks. In contrast to the situation with respect to Liu and Layland task systems (Chap. 7) where there is a very large body of work to discuss, the research on dynamic priority (DP) scheduling of three-parameter sporadic task systems is rather sparse. The one scheduling algorithm that has been explored in some detail—earliest deadline zero laxity (edzl) (discussed in Sect. 20.2)—is “almost” a fixed job priority (FJP) algorithm in a sense that will become clearer upon reading Sect. 20.2, and hence most of the analyses conducted on edzl are similar to the analyses few have seen in earlier chapters regarding earliest-deadline-first (\(\textsf{EDF}\)).

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

21. The Sporadic DAG Tasks Model

Abstract

The Liu and Layland task model and the three-parameter sporadic task model both assume that there is a single thread of execution within each task; they do not allow for the modeling of parallelism within individual tasks. This was not seen as a shortcoming of the models when they were first being developed, since both were proposed in the context of uniprocessor real-time systems for which the presence of just a single processor ruled out parallel execution.

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

22. Real-time Scheduling upon Heterogeneous Multiprocessors

Abstract

As the computational demands made by ever more complex embedded real-time applications continue to increase, there is a need for enhanced performance capabilities from these platforms. Initially, the approach adopted for obtaining such enhanced performance was to increase core counts in multiprocessor CPUs. Soon, however, chip makers began to distinguish themselves not only by offering more general-purpose cores but also by providing specialized hardware components that accelerate particular computations. Examples include multicore CPUs with specialized graphics processing cores, specialized signal-processing cores, specialized floating-point units, customizable FPGAs, etc. Computing platforms such as these with specialized components are called unrelated or heterogeneous [143] multiprocessor platforms.

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

23. Looking Ahead

Abstract

As stated in the introduction, the sheer volume of excellent research on various aspects of multiprocessor scheduling theory meant that we could not possibly hope to detail, or even mention in passing, all the important and interesting results. Instead, we have selected a self-contained collection of topics from the vast body of research literature on multiprocessor real-time scheduling theory, and have attempted to provide a cohesive, relatively deep, and complete coverage of these topics. Our choice of topics for inclusion was primarily guided by their relevance to the discipline, the maturity of our knowledge about them, and the requirement that all taken together, they should comprise a complete narrative for a substantial and important subset of multiprocessor real-time scheduling theory. In addition, our personal preferences, biases, and expertise undoubtedly played a role in determining which topics got into this book, and which stayed out. In any event, there are many important aspects of multiprocessor real-time scheduling theory that did not see much discussion in this book; we briefly list some such topics in this chapter.

Sanjoy Baruah, Marko Bertogna, Giorgio Buttazzo

Backmatter