Schedule-Abstraction Graph
What is a
schedule-abstraction graph and how does it work?
Schedule-abstraction graph (SAG) explores the space of possible decisions
that a job-level fixed-priority (JLFP) scheduler can take when
dispatching a set of jobs on processing resources. This decision space is
explored by building a graph whose vertices represent the state of the
resource (e.g., processor) after the execution of a set of jobs. The
edges of this graph represent possible scheduling decisions that evolve the
system states.
SAG has been designed for non-preemptive jobs [Nasri2017, Nasri2018,
Nasri2019, Nogd2020, Ranjha2021, Ranjha2022], hence, a scheduling decision is
to determine a next job that can possibly be dispatched' after a system
state.
Want to learn more?
·
An introduction to
schedule-abstraction graph analysis: slides
·
An introduction on my
research: slides
Implementation
Schedule-abstraction graph is an open-source analysis tool
and is available on github. The
repository is maintained by Dr. Geoffrey
Nelissen.
- Dr. Geoffrey Nelissen (Mathematics&Computer Science
Department, IRIS group, TU/e)
- Dr. Marc Geilen (Electrical Engineering Department,
Electronic Systems group, TU/e)
- Dr. Jeroen Voeten (Electrical Engineering Department,
Electronic Systems group, TU/e)
- Dr. Björn Brandenburg (Max Planck Institute for
Software Systems, Germany)
- Pourya Gohari (Ph.D. student), topic: "Smart and
Analyzable Scheduling for Real-Time Systems", Eindhoven University of
Technology, started June 2021
- Yimi Zhao (master student), topic: "Finding Counter
Examples in Reachability-Based Response-Time Analysis", Eindhoven
University of Technology
- Michal Mikolajczyk (master
student),
topic: "Response-time Analysis of Conditional DAG Tasks using
Schedule-Abstraction Technique", Eindhoven University of Technology
- Shixun Wu (master student), topic: "Machine-Learning
based Priority Assignment for Real-Time Parallel DAG Tasks", Delft
University of Technology
Publications
My publications in Google
Scholar.
Technical reports
Peer Reviewed Conference Papers
- Sayra Ranjha, Geoffrey Nelissen, Mitra Nasri,
"Partial-Order Reduction in Reachability-based Response-Time
Analyses," the IEEE Real-Time Systems Symposium (RTAS), 2022.
Best Paper Award .
paper,
slides,
video (25min, 300MB),
open source on github
-
Pourya Gohari, Mitra Nasri, Jeroen Voeten,
"Data-Age Analysis for Multi-Rate Task Chains under Timing Uncertainty,"
the International Conference on Real-Time Networks and Systems (RTNS), 2022.
[paper |
slides ]
- Sayra Ranjha, Mitra Nasri, Geoffrey
Nelissen, "Work-in-Progress: Partial-Order Reduction in
Reachability-based Response-Time Analyses," the IEEE Real-Time
Systems Symposium (RTSS), 2021. paper, slides, video
- Suhail Nogd, Geoffrey Nelissen, Mitra Nasri,
and Björn B. Brandenburg, "Response-Time Analysis for Non-Preemptive
Global Scheduling with FIFO Spin Locks," the IEEE Real-Time Systems
Symposium (RTSS), 2020. paper, presentation (25 min
video)
- Saranya Natarajan, Mitra Nasri, David
Broman, Björn B. Brandenburg, and Geoffrey Nelissen, "From Code to
Weakly Hard Constraints: A Pragmatic End-to-End Toolchain for Timed
C," the IEEE Real-Time Systems Symposium (RTSS), 2019, pp. 167-180. paper, toolchain on Github,
schedulability
analysis on Github
- Mitra Nasri, Geoffrey Nelissen, and Björn
B. Brandenburg, "Response-Time Analysis of Limited-Preemptive
Parallel DAG Tasks under Global Scheduling", the Euromicro Conference
on Real-Time Systems (ECRTS), 2019, pp. 21:1-21:23. paper, slides, schedulability
analysis on Github
- Beyazit Yalcinkaya, Mitra Nasri, and
Björn B. Brandenburg, "An Exact Schedulability Test for
Non-Preemptive Self-Suspending Real-Time Tasks", the Design,
Automation, and Test in Europe (DATE), 2019, pp. 1222-1227. paper, slides
- Mitra Nasri, Geoffrey Nelissen, and Björn
B. Brandenburg, "A Response-Time Analysis for Non-preemptive Job Sets
under Global Scheduling", the Euromicro Conference on Real-Time
Systems (ECRTS), 2018, pp. 9:1-9:23. Paper (extended version),
presentation , schedulability
analysis on Github
- Mitra Nasri and Björn B. Brandenburg,
"An Exact and Sustainable Analysis of Non-Preemptive Scheduling”, the
Real-Time Systems Symposium (RTSS), 2017, pp. 1-12. Paper, Slides, schedulability
analysis on Github
- Sayra Ranjha (master student), Thesis: "Partial-Order
Reduction in Reachability-based Schedulability Analyses", Delft
University of Technology, Thesis,
IRIS presentation (9 out
of 10)
- Srinidhi Srinivasan
(co-supervised master student), Thesis: "Schedulability Analysis of Globally
Scheduled Preemptive Applications", Delft University of Technology, Thesis
(8.5 out of 10), Presentation
- Joan Marcè i Igual
(co-supervised master student), Thesis: "Schedulability Analysis of
Limited-Preemptive Moldable Gang Tasks", Delft University of
Technology, Thesis
(9 out of 10), Presentation
- Suhail Nogd (co-supervised
master student),
Thesis: "Response-Time Analysis for Non-Preemptive Global Scheduling
with Spin Locks", Delft University of Technology, Thesis
(9.5 out of 10), Presentation