Analysis of Federated Scheduling for Integer-Valued Workloads
Marion Sudvarg, Chris Gill · 2022
In federated scheduling of parallel real-time tasks on multiprocessor systems, high-utilization tasks are allocated dedicated processors on which they execute exclusively. Several methods exist for allocating a sufficient number of processors to guarantee that each task meets its deadline. In this paper, we propose two new strategies for allocating unit-speed cores to tasks with integer workload and deadline values. The first method can be performed in constant time for each high-utilization task, given the task’s total workload, critical-path length, and deadline. The second method exploits the DAG structure of high-utilization tasks, providing a potentially better schedule in pseudo-polynomial time. We analyze and evaluate these new bounds in the context of existing techniques, and demonstrate that, in practice, they often allocate fewer processor cores. We also present a novel method for assigning an optimal number of dedicated cores to heavy tasks, describe how this method can be used in practice, and consider cases for which this is efficient.