The feasibility of general task systems with precedence constraints on multiprocessor platforms |
| |
Authors: | Nathan Fisher Sanjoy Baruah |
| |
Affiliation: | (1) Department of Computer Science, Wayne State University, Detroit, MI, USA;(2) Department of Computer Science, The University of North Carolina at Chapel Hill, Chapel Hill, NC, USA |
| |
Abstract: | Feasibility analysis determines (prior to system execution-time) whether a specified collection of hard-real-time jobs executed on a processing platform can meet all deadlines. In this paper, we derive near-optimal sufficient tests for determining whether a given collection of jobs can feasibly meet all deadlines upon a specified multiprocessor platform assuming job migration is permitted. The collection of jobs may contain precedence constraints upon the order of execution of these jobs. The derived tests are general enough to be applied even when the collection of jobs is incompletely specified. We discuss the applicability of these tests to the scheduling of collections of jobs that are generated by systems of recurrent real-time tasks. We also show that our feasibility conditions may be used to obtain global-EDF schedulability conditions. |
| |
Keywords: | Feasibility analysis Schedulability analysis Earliest-deadline-first scheduling Recurrent task models Resource-augmentation analysis |
本文献已被 SpringerLink 等数据库收录! |