This paper presents several fault-tolerant extensions of the Rate-Monotonic First-Fit multiprocessor scheduling algorithm handling both active and passive task copies. In particular, the technique of backup phasing delay is used to reduce the portions of active task copies that must be always executed and to deallocate active task copies as soon as their primary task copies have been successfully executed. It is also shown how to employ this technique while considering passive task duplication so as to over-book each processor with many passive task copies, assigning tasks to processors in such a way that tasks with equal or multiple periods have a high chance to be assigned to the same processor, and partitioning the processors into groups to avoid the mix of primary, active, and passive task copies on the same processor. Extensive simulations reveal a remarkable saving of both the overall number of processors used and the total computation time of the schedulability test (achieved especially by two new algorithms, called ARR3 and S-PR-PASS) with respect to previously proposed algorithms
Scheduling hard-real-time tasks with backup phasing delay / Bertossi, Alan A; Mancini, Luigi Vincenzo; Menapace, Alessandra. - STAMPA. - (2006), pp. 107-116. (Intervento presentato al convegno 10th IEEE International Symposium on Distributed Simulation and Real-Time Applications (DS-RT 2006) tenutosi a Torremolinos, Malaga, esp nel October 2006) [10.1109/DS-RT.2006.33].
Scheduling hard-real-time tasks with backup phasing delay
MANCINI, Luigi Vincenzo;
2006
Abstract
This paper presents several fault-tolerant extensions of the Rate-Monotonic First-Fit multiprocessor scheduling algorithm handling both active and passive task copies. In particular, the technique of backup phasing delay is used to reduce the portions of active task copies that must be always executed and to deallocate active task copies as soon as their primary task copies have been successfully executed. It is also shown how to employ this technique while considering passive task duplication so as to over-book each processor with many passive task copies, assigning tasks to processors in such a way that tasks with equal or multiple periods have a high chance to be assigned to the same processor, and partitioning the processors into groups to avoid the mix of primary, active, and passive task copies on the same processor. Extensive simulations reveal a remarkable saving of both the overall number of processors used and the total computation time of the schedulability test (achieved especially by two new algorithms, called ARR3 and S-PR-PASS) with respect to previously proposed algorithmsI documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.