Volume 6 Number 11 (Nov. 2011)
Home > Archive > 2011 > Volume 6 Number 11 (Nov. 2011) >
JSW 2011 Vol.6(11): 2308-2320 ISSN: 1796-217X
doi: 10.4304/jsw.6.11.2308-2320

Two-level Hierarchical Scheduling Algorithm for Real-time Multiprocessor Systems

Muhammad Khurram Bhatti, C´ecile Belleudy, Michel Auguin
LEAT research laboratory, University of Nice-Sophia Antipolis, Nice, France

Abstract—The Earliest Deadline First (EDF) scheduling algorithm has the least runtime complexity among joblevel fixed-priority algorithms for scheduling tasks on multiprocessor architectures. However, EDF suffers from suboptimality in multiprocessor systems. This paper proposes a new restricted migration-based scheduling algorithm for multiprocessor real-time systems, called Two-level Hierarchical Scheduling Algorithm (2L-HiSA), to address this sub-optimality. 2L-HiSA algorithm divides the problem of multiprocessor scheduling into a two-level hierarchy of schedulers. This algorithm works in two phases: i- A taskpartitioning phase in which, each task from application task set is assigned to a specific processor by following simple bin-packing approach. If a task can not be partitioned on any processor in the platform, it qualifies as migrating task. ii- A processor-grouping phase in which, processors are clustered together such that, per cluster, the unused fragmented computation power equivalent to at most one processor is available. We provide schedulability analysis and experimental evaluation to support our proposition. Moreover, our simulation results show an average difference of 18-folds in the number of preemptions and 10-folds in the number of task migrations under 2L-HiSA and PD2 algorithm.

Index Terms—Real-time Systems, Multiprocessor, Scheduling, EDF, Partitioned scheduling, Global scheduling.


Cite: Muhammad Khurram Bhatti, C´ecile Belleudy, Michel Auguin, "Two-level Hierarchical Scheduling Algorithm for Real-time Multiprocessor Systems," Journal of Software vol. 6, no. 11, pp. 2308-2320, 2011.

General Information

ISSN: 1796-217X (Online)
Frequency:  Bimonthly (Since 2020)
Editor-in-Chief: Prof. Antanas Verikas
Executive Editor: Ms. Yoyo Y. Zhou
Abstracting/ Indexing: DBLP, EBSCO, Google Scholar, ProQuest, INSPEC(IET), ULRICH's Periodicals Directory, WorldCat, etc
E-mail: jsw@iap.org
  • Apr 26, 2021 News!

    Vol 14, No 4- Vol 14, No 12 has been indexed by IET-(Inspec)     [Click]

  • Jun 22, 2020 News!

    Papers published in JSW Vol 14, No 1- Vol 15 No 4 have been indexed by DBLP     [Click]

  • Sep 13, 2021 News!

    The papers published in Vol 16, No 6 have all received dois from Crossref    [Click]

  • Jan 28, 2021 News!

    [CFP] 2021 the annual meeting of JSW Editorial Board, ICCSM 2021, will be held in Rome, Italy, July 21-23, 2021   [Click]

  • Sep 13, 2021 News!

    Vol 16, No 6 has been published with online version     [Click]