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.
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 *