Title: From RUN to QPS: new trends for optimal real-time multiprocessor scheduling

Authors: Ernesto Massa; George Lima; Paul Regnier

Addresses: State University of Bahia, Rodovia Alagoinhas/Salvador – BR 110, Km 03, Bahia, Brazil ' Federal University of Bahia, Av. Adhemar de Barros, S/N, Ondina, Salvador, Bahia, Brazil ' Federal University of Bahia, Av. Adhemar de Barros, S/N, Ondina, Salvador, Bahia, Brazil

Abstract: Until recently, there has been a common belief that optimal multiprocessor real-time scheduling algorithms necessarily incur a high number of task preemptions and migrations. New scheduling algorithms have shown that this is not the case. In this paper, we explain why two of these algorithms, reduction to uniprocessor (RUN) and quasi-partition scheduling (QPS), achieve optimality with only a few preemptions and migrations, exhibiting their similarities and differences. We also compare these two algorithms via simulations, highlighting the consequences of their differences in their performance. By putting RUN and QPS side-by-side, we bring about their fundamental properties and help in the understanding of the multiprocessor real-time scheduling problem.

Keywords: real-time scheduling; optimality; optimal scheduling; multiprocessor scheduling; reduction to uniprocessor RUN; quasi-partition scheduling; QPS; simulation.

DOI: 10.1504/IJES.2016.080390

International Journal of Embedded Systems, 2016 Vol.8 No.5/6, pp.440 - 451

Received: 12 Mar 2015
Accepted: 18 Feb 2016

Published online: 21 Nov 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article