Paper Info
Title
Exact Feasibility Tests for Real-Time Scheduling of Periodic Tasks upon Multiprocessor Platforms
Abstract
In this paper we study the global scheduling of periodic task systems upon multipro- cessor platforms. We first show two very general properties which are well-known for uniprocessor platforms and which remain for multiprocessor platforms: (i) under few and not so restrictive assumptions, we show that feasible schedules of periodic task systems are periodic from some point with a period equal to the least common multiple of task periods and (ii) for the specific case of synchronous periodic task systems, we show that feasible schedules repeat from the origin. We then present our main result: we characterize, for task-level fixed-priority schedulers an d for asynchronous constrained or arbitrary deadline periodic task models, upper bounds of the first time instant where the schedule repeats. We show that job-level fixed-priority schedulers are predictable upon unrelated multiprocessor platforms. For task-level fixed-priority schedulers, based on the upper bounds and the predictability property, we provide for asynchronous constrained or arbitrary deadline periodic task sets, exact feasibility tests. Finally, for the job-level fixed- priority EDF scheduler, for which such an upper bound remains unknown, we provide an exact feasibility test as well.
Year
Venue
Keywords
2008
Clinical Orthopaedics and Related Research
operating system,upper bound
Field
DocType
Volume
Metrical task system,Asynchronous communication,Uniprocessor system,Upper and lower bounds,Scheduling (computing),Computer science,Parallel computing,Real-time computing,Multiprocessing,Schedule,Periodic graph (geometry),Distributed computing
Journal
abs/0801.4
Citations 
PageRank 
References 
0
0.34
6
Authors
2
Name
Order
Citations
PageRank
Liliana Cucu11718.91
Joël Goossens266649.22