Global EDF Scheduling for Parallel Real-Time Tasks

<p>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 thesis, 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-2/m and a resource augmentation bound of 2-1/m. 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-2/m) where each task's critical-path length is at most 1/(4-2/m) of its deadline is schedulable on 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 GEDF. PGEDF is built by combining the GNU OpenMP runtime system and the LITMUS_RT 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.</p>

Name thesis:degree_name

Master of Science (MS)

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science & Engineering

Year dc:date.available

2014

Author dc:creator

• Li, Jing

Contributors dc:contributor

• Chenyang Lu and Kunal Agrawal
• Roger Chamberlain

• real-time scheduling
• Computer Engineering
• Computer Sciences

Statement dc:rights

• I have not registered my thesis with the U.S. Copyright Office, but intend to later.

Language dc:language

English (en)

Identifier

https://openscholarship.wustl.edu/eng_etds/1

OAI identifier oai:identifier

oai:openscholarship.wustl.edu:eng_etds-1000