Global EDF scheduling for parallel real-time tasks

Jing Li, Zheng Luo, David Ferry, Kunal Agrawal, Christopher Gill, Chenyang Lu

Research output: Contribution to journalArticlepeer-review

46 Scopus citations

Abstract

As multicore processors become ever more prevalent, it is important for real-time programs to take advantage of intra-task parallelism in order to support computation-intensive applications with tight deadlines. In this paper, we consider the global earliest deadline first (GEDF) scheduling policy for task sets consisting of parallel tasks. Each task can be represented by a directed acyclic graph (DAG) where nodes represent computational work and edges represent dependences between nodes. In this model, we prove that GEDF provides a capacity augmentation bound of$$4-\frac{2}{m}$$4-2m and a resource augmentation bound of$$2-\frac{1}{m}$$2-1m. The capacity augmentation bound acts as a linear-time schedulability test since it guarantees that any task set with total utilization of at most $$m/(4-\frac{2}{m})$$m/(4-2m) where each task’s critical-path length is at most $$1/(4-\frac{2}{m})$$1/(4-2m) of its deadline is schedulable on $$m$$m cores under GEDF. In addition, we present a pseudo-polynomial time fixed-point schedulability test for GEDF; this test uses a carry-in work calculation based on the proof for the capacity bound. Finally, we present and evaluate a prototype platform—called PGEDF—for scheduling parallel tasks using global earliest deadline first (GEDF). PGEDF is built by combining the GNU OpenMP runtime system and the $$\text {LITMUS}^\text {RT}$$LITMUSRT operating system. This platform allows programmers to write parallel OpenMP tasks and specify real-time parameters such as deadlines for tasks. We perform two kinds of experiments to evaluate the performance of GEDF for parallel tasks. (1) We run numerical simulations for DAG tasks. (2) We execute randomly generated tasks using PGEDF. Both sets of experiments indicate that GEDF performs surprisingly well and outperforms an existing scheduling techniques that involves task decomposition.

Original languageEnglish (US)
Pages (from-to)395-439
Number of pages45
JournalReal-Time Systems
Volume51
Issue number4
DOIs
StatePublished - Oct 28 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Modeling and Simulation
  • Computer Science Applications
  • Computer Networks and Communications
  • Control and Optimization
  • Electrical and Electronic Engineering

Keywords

  • Capacity augmentation bound
  • Global EDF
  • Parallel scheduling
  • Real-time scheduling
  • Resource augmentation bound

Fingerprint

Dive into the research topics of 'Global EDF scheduling for parallel real-time tasks'. Together they form a unique fingerprint.

Cite this