Call For Papers
Contact Us

  A Comparison of Global EDF and LLREF Scheduling Algorithms  
  Authors : Valma Prifti; Bledar Balla; Romina Zane; Juliaj Fejzaj; Igli Tafa
  Cite as:


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.


Published In : IJCSN Journal Volume 3, Issue 5

Date of Publication : October 2014

Pages : 416 - 420

Figures : 07

Tables : --

Publication Link : A Comparison of Global EDF and LLREF Scheduling Algorithms




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

















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.