Program

A Best-Response Algorithm for Multiprocessor Periodic Scheduling

Abstract

The problem of scheduling strictly periodic tasks, that is tasks that have to be executed at constant time intervals over an infinite time horizon, naturally arises in real-time video signal processing and in the design of critical embedded systems. We address this problem assuming that the objective is to find a schedule that maximizes the idle times between the task executions while ensuring that they do not overlap in time. This will allow an evolution margin for task budget times, should it be required in the future.
We first consider the uniprocessor scheduling problem for which we propose an approximation algorithm inspired from game theory. In this algorithm, tasks take turns in some fixed order and at its turn a task selects its offset to maximize its own utility function (which is related to evolution margins of the tasks). We prove the convergence of the algorithm to an equilibrium point where no task has any incentive to unilaterally deviate. Although the equilibrium point need not necessarily be unique, we prove that there exists at least one equilibium point that is also optimal. We also provide an efficient scheme to compute the best-response offset of a task. We then show that this best-response algorithm can be naturally extended to the multiprocessor case by allowing tasks to select a processor in addition to an offset on this processor. Numerical experiments show that this algorithm is far much quicker than the exact algorithm presented previously while at the same time it generates periodic schedules with modest relative errors.