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.

1. Introduction

A real-time tasks system consists of a set of tasks whose worst case response times are constrained by a deadline. The system is said to be feasible if all its tasks meet their deadlines. If a task of such a system completes its execution after its deadline, the result of this task can become invalid. Feasibility conditions based on the worst case execution time (WCET) of these tasks permits to grant that the deadlines are always met for all possible release time scenarios. The computation of the WCET can be made with different techniques [10], but it is often a difficult step. In a system having an uncertain environment, it can be interesting to provide a more flexible feasibility analysis which supports temporal fault resulting to WCETs overruns. We consider in this paper a sliding window fault model, where at most tasks can have WCETs overruns in a system of tasks as defined in [3].