Brute-Force Determination of Multiprocessor Schedulability for Sets of Sporadic Hard-Deadline Tasks
This report describes a necessary and sufficient test for the schedulability of a set of sporadic hard-deadline tasks on a multiprocessor platform, using any of a variety of scheduling policies including global fixed task-priority and earliest-deadline-fi
- PDF / 493,057 Bytes
- 14 Pages / 430 x 660 pts Page_size
- 74 Downloads / 143 Views
Florida State University, Tallahassee, FL 32306, USA [email protected] http://www.cs.fsu.edu/˜baker 2 Scuola Superiore Sant’Anna, Pisa, Italy [email protected]
Abstract. This report describes a necessary and sufficient test for the schedulability of a set of sporadic hard-deadline tasks on a multiprocessor platform, using any of a variety of scheduling policies including global fixed task-priority and earliest-deadline-first (EDF). The contribution is to establish an upper bound on the computational complexity of this problem, for which no algorithm has yet been described. The compute time and storage complexity of the algorithm, which performs an exhaustive search of a very large state space, make it practical only for tasks sets with very small integer periods. However, as a research tool, it can provide a clearer picture than has been previously available of the real success rates of global preemptive priority scheduling policies and low-complexity sufficient tests of schedulability.
1 Introduction This report describes a “brute force” algorithm for determining whether a hard-deadline sporadic task system will always be scheduled so as to meet all deadlines, for global preemptive priority scheduling policies on multiprocessor platforms. The algorithm is presented in a generic form, that can easily be applied to earliest-deadline-first, fixedpriority, least-laxity-first, earliest-deadline-zero-laxity, throwforward, and a variety of other scheduling policies. Symmetric multiprocessor platforms have long been used for high performance realtime systems. Recently, with the introduction of low-cost multi-core microprocessor chips, the range of potential embedded applications of this kind of architecture as expanded rapidly. The historically dominant approach to scheduling real-time applications on a multiprocessor has been partitioned; that is, to assign each task (statically) to a processor, and then apply a single-processor scheduling technique on each processor. The alternative is global scheduling; that is, to maintain a single queue of ready jobs and assign jobs
This material is based upon work supported in part by the National Science Foundation under Grant No. 0509131, and a DURIP grant from the Army Research Office.
E. Tovar, P. Tsigas, and H. Fouchal (Eds.): OPODIS 2007, LNCS 4878, pp. 62–75, 2007. c Springer-Verlag Berlin Heidelberg 2007
Brute-Force Determination of Multiprocessor Schedulability
63
from that queue dynamically to processors. Despite greater implementation overhead, the global approach is conceptually appealing in several respects. Several sufficient tests have been derived for the schedulability of a sporadic task set on a multiprocessor using a given scheduling policy, such as global preemptive scheduling based on fixed task priorities (FTP) or deadlines (EDF) [1,2,3,5,6,7,10,14]. For example, it can be shown that a set of independent periodic tasks with deadline equal to period will not miss any deadlines if it is scheduled by a global EDF policy on m processors, provided
Data Loading...
