An EDF-based restricted-migration scheduling algorithm for multiprocessor soft real-time systems

There has been much recent interest in the use of the earliest-deadline-first (EDF) algorithm for scheduling soft real-time sporadic task systems on identical multiprocessors. In hard real-time systems, a significant disparity exists between EDF-based schemes and Pfair scheduling: on M processors, the worst-case schedulable utilization for all known EDF variants is approximately M/2, whereas it is M for optimal Pfair algorithms. This is unfortunate because EDF-based algorithms entail lower scheduling and task-migration overheads. However, such a disparity in schedulability can be alleviated by easing the requirement that all deadlines be met, which may be sufficient for soft real-time systems. In particular, in recent work, we have shown that if task migrations are not restricted, then EDF (i.e., global EDF) can ensure bounded tardiness for a sporadic task system with no restrictions on total utilization. Unrestricted task migrations in global EDF may be unappealing for some systems, but if migrations are forbidden entirely, then bounded tardiness cannot be guaranteed. In this paper, we address the issue of striking a balance between task migrations and system utilization by proposing an algorithm called EDF-fm, which is based upon EDF and treads a middle path, by restricting, but not eliminating, task migrations. Specifically, under EDF-fm, the ability to migrate is required for at most M − 1 tasks, and it is sufficient that every such task migrate between two processors and at job boundaries only. EDF-fm, like global EDF, can ensure bounded tardiness to a sporadic task system as long as the available processing capacity is not exceeded, but, unlike global EDF, may require that per-task utilizations be capped. The required cap is quite liberal, hence, EDF-fm should enable a wide range of soft real-time applications to be scheduled with no constraints on total utilization