Allowance-Fit: A partitioning algorithm for temporal robustness of hard real-time systems upon multiprocessors

We consider in this paper a partitioned real-time multiprocessor scheduling problem for sporadic task having constrained deadlines and a fixed priority scheduling. A major problem with partitioned scheduling is to determine if there exists a valid partitioning satisfying all the tasks deadlines. Many algorithms have tried to solve this problem. Most of them have considered first fit partitioning to minimize the number of processors required at the price of maximizing the load on each assigned processors. In this paper, we propose another partitioning strategy that aims at maximizing the allowance of WCETs of the tasks defined as the maximum extra duration that can be given to a task without compromising the task deadlines. The allowance-fit partitioning we propose uses the allowance criteria. We show that the partition found by our algorithm improves the temporal robustness of all the tasks of the system in the case of WCET overruns faults.