Multiprocessor Feasibility Analysis of Recurrent Task Systems with Specified Processor Affinities
Authors:
- Sanjoy BaruahSBSanjoy Baruah
- Bjorn BrandenburgBBBjorn Brandenburg
- 1 December 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10528725,p. 160-169
Abstract
In many current multiprocessor real-time operating systems, programmers have the ability to set affinity masks that pin a process to a specified subset of the processors in the system. Given a real-time task system consisting of a collection of implicit-deadline sporadic tasks with an affinity mask specified for each task that is to be implemented upon an identical multiprocessor platform, this paper addresses the question of determining whether the task system can be implemented upon the platform to always meet all deadlines, while respecting the affinity mask restrictions. An algorithm is derived that answers this question efficiently in run-time that is polynomial in the representation of the task system.Keywords
This publication has 10 references indexed in Scilit:
- Outstanding Paper Award: Schedulability Analysis of the Linux Push and Pull Scheduler with Arbitrary Processor Affinities2013
- A counter-example to: Sticky-ERfair: a task-processor affinity aware proportional fair schedulerReal-Time Systems, 2011
- Sticky-ERfair: a task-processor affinity aware proportional fair schedulerReal-Time Systems, 2011
- Deadline Scheduling with Processor Affinity and Feasibility Check on Uniform Parallel Machines2007
- Feasibility Analysis of Preemptive Real-Time Systems upon Heterogeneous Multiprocessor Platforms2005
- An in-depth analysis of the impact of processor affinity on network performance2005
- A new polynomial-time algorithm for linear programmingCombinatorica, 1984
- On Preemptive Scheduling of Unrelated Parallel Processors by Linear ProgrammingJournal of the ACM, 1978
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973
- On Representatives of SubsetsJournal of the London Mathematical Society, 1935