In this paper we are going to analyze and trying to
compare EDF and LLREF scheduling algorithms, used in
multiprocessor platforms. We will briefly describe classic EDF,
global EDF, which is an extension of EDF, and the newer
LLREF algorithm. Then we will analyze the ability of global
EDF in scheduling task sets in random manner and compare with
the LLREF one, which can schedule any task set when the total
utilization is smaller then number of processors. We will
examine optimally and the overhead of these two algorithms.
Analyzing three parameters such as: schedulability, task
migration and scheduler invocations, we will try to be as specific
as possible with our conclusions.
Valma Prifti : Polytechnic University of Tirana, Faculty of Economy Engineering
Bledar Balla : Polytechnic University of Tirana, Information Technology Faculty
Romina Zane : Polytechnic University of Tirana, Information Technology Faculty
Juliaj Fejzaj : Tirana University, Information Faculty
Igli Tafa : Polytechnic University of Tirana, Information Technology Faculty
EDF
LLREF
algorithm
scheduling
simulator
deadline
jobs
task
invocations
In this paper we examined and analyzed two scheduling
algorithms for uniform multiprocessor systems: global
EDF and LLREF. We analyzed three parameters of these
algorithms such as: schedulability, task migrations and
scheduling invocations. Based on them, we can say that
even though EDF is clear and simple, it is a non-optimal
scheduling algorithm. Some task sets could not be run
using EDF scheduling algorithm. However, the results
shows that EDF’s overhead, in terms of scheduler
invocations and task migrations, is lower than the LLREF
one. On the other hand, LLREF is an optimal scheduling
algorithm, with a higher overhead than global EDF, but
with more task sets run in it. In the end, it’s necessary for
us to decide which parameter of scheduler is more
important: optimally or low overhead, before we choose a
scheduling algorithm for multiprocessor systems.
[1] Global EDF-based Scheduling with Laxity-driven
Priority Promotion Shinpei Kato, Nobuyuki Yamasaki,
Department of Computer Science, The University of
Tokyo. Journal of Systems Architecture: the
EUROMICRO Journal, Volume57
http://dl.acm.org/citation.cfm?id=1975383.
[2] U-LLREF: An Optimal Scheduling Algorithm for
Uniform Multiprocessors Shelby H. Funk, Archana
Meka, Computer Science Department, Georgia’s
University, 30606,USA.
www.cs.uga.edu/~shelby/pubs/mapsp-shf.pdf.
[3] An Optimal Multiprocessor Algorithm for Sporadic
Task Sets with Unconstrained Deadlines
Sh.Funk, University of Georgia, Athens, GA, USA.
Published in Journal Real Time Systems; Volume 46
Issue 3, December 2010
http://dl.acm.org/citation.cfm?id=1891605.
[4] A Comparison of Scheduling Algorithms for
Multiprocessors
Dan McNulty, Lena Olson, Markus Peloquin, December
13, 2010
http://pages.cs.wisc.edu/~markus/750/smp_scheduling.p
df
[5] Energy-aware Scheduling on Multiprocessor Platforms
By Dawei Li, Jie Wu http://books.google.al/books.
[6] Retis Lab, Scuola Superiore Sant’Anna. The RTSIM
project. http://rtsim.sssup.it.
[7] A Comparison of Global and Partitioned EDF
Schedulability Tests for Multiprocessors T. Baker In
International Conf. on Real-Time and Network
Systems,2005. www.cs.fsu.edu/research/reports/tr-
051101.pdf.
