| Niklas Ueter.
Reservation-Based Federated Scheduling for Parallel Real-Time Tasks.
Master's Thesis, 2018
[BibTeX][PDF]@mastersthesis { Ueter:2018,
title = {Reservation-Based Federated Scheduling for Parallel Real-Time Tasks},
author = {Ueter, Niklas},
school = {TU Dortmund},
year = {2018},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/theses/ueter.pdf},
confidential = {n},
adviser = {Prof. Dr. Jian-Jia Chen and Dipl. Inf. Georg von der Br\"uggen},
} |
| Jian-Jia Chen, Georg von der Brüggen and Niklas Ueter.
Push Forward: Global Fixed-Priority Scheduling of Arbitrary-Deadline Sporadic Task Systems.
In 30th Euromicro Conference on Real-Time Systems (ECRTS) 2018 , pages 8:1--8:24
Barcelona, Spain, July 3-6, 2018 2018
[BibTeX][PDF][Link][Abstract]@inproceedings { Chen2018ECRTS,
author = {Chen, Jian-Jia and Br\"uggen, Georg von der and Ueter, Niklas},
title = {Push Forward: Global Fixed-Priority Scheduling of Arbitrary-Deadline Sporadic Task Systems},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS) 2018 },
year = {2018},
pages = {8:1--8:24},
address = {Barcelona, Spain},
month = {July 3-6, 2018},
url = {http://drops.dagstuhl.de/opus/volltexte/2018/8996/pdf/LIPIcs-ECRTS-2018-8.pdf},
keywords = {georg},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2018-ecrts-jj.pdf},
confidential = {n},
abstract = {The sporadic task model is often used to analyze recurrent execution of tasks in real-time systems. A sporadic task defines an infinite sequence of task instances, also called jobs, that arrive under the minimum inter-arrival time constraint. To ensure the system safety, timeliness has to be guaranteed in addition to functional correctness, i.e., all jobs of all tasks have to be finished before the job deadlines. We focus on analyzing arbitrary-deadline task sets on a homogeneous (identical) multiprocessor system under any given global fixed-priority scheduling approach and provide a series of schedulability tests with different tradeoffs between their time complexity and their accuracy. Under the arbitrary-deadline setting, the relative deadline of a task can be longer than the minimum inter-arrival time of the jobs of the task. We show that global deadline-monotonic (DM) scheduling has a speedup bound of 3 − 1/M against any optimal scheduling algorithms, where M is the number of identical processors, and prove that this bound is asymptotically tight.},
}
The sporadic task model is often used to analyze recurrent execution of tasks in real-time systems. A sporadic task defines an infinite sequence of task instances, also called jobs, that arrive under the minimum inter-arrival time constraint. To ensure the system safety, timeliness has to be guaranteed in addition to functional correctness, i.e., all jobs of all tasks have to be finished before the job deadlines. We focus on analyzing arbitrary-deadline task sets on a homogeneous (identical) multiprocessor system under any given global fixed-priority scheduling approach and provide a series of schedulability tests with different tradeoffs between their time complexity and their accuracy. Under the arbitrary-deadline setting, the relative deadline of a task can be longer than the minimum inter-arrival time of the jobs of the task. We show that global deadline-monotonic (DM) scheduling has a speedup bound of 3 − 1/M against any optimal scheduling algorithms, where M is the number of identical processors, and prove that this bound is asymptotically tight.
|
| Jian-Jia Chen, Georg von der Brüggen, Junjie Shi and Niklas Ueter.
Dependency Graph Approach for Multiprocessor Real-Time Synchronization.
In IEEE Real-Time Systems Symposium, RTSS 2018, pages 434--446
Nashville, TN, USA, December 11-14 2018
[BibTeX][PDF][Link][Abstract]@inproceedings { DBLP:conf/rtss/ChenBSU18,
author = {Chen, Jian-Jia and Br\"uggen, Georg von der and Shi, Junjie and Ueter, Niklas},
title = {Dependency Graph Approach for Multiprocessor Real-Time Synchronization},
booktitle = {IEEE Real-Time Systems Symposium, RTSS 2018},
year = {2018},
pages = {434--446},
address = {Nashville, TN, USA},
month = {December 11-14},
url = {https://doi.org/10.1109/RTSS.2018.00057},
keywords = {georg},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2018-rtss-jj.pdf},
confidential = {n},
abstract = {Over the years, many multiprocessor locking protocols have been designed and analyzed. However, the performance
of these protocols highly depends on how the tasks are partitioned and prioritized, and how the resources are shared locally and globally. This paper answers a few fundamental questions when real-time tasks share resources in multiprocessor systems. We explore the fundamental difficulty of the multiprocessor synchronization problem and show that a very simplified version of this problem is N P -hard in the strong sense regardless of the number of processors and the underlying scheduling paradigm. Therefore, the allowance of preemption or migration does not reduce the computational complexity. On the positive side, we develop a dependency-graph approach that is specifically useful
for frame-based real-time tasks, i.e., when all tasks have the same period and release their jobs always at the same time. We present a series of algorithms with speedup factors between 2 and 3 under semi-partitioned scheduling. We further explore methodologies for and tradeoffs between preemptive and non-preemptive scheduling algorithms, and partitioned and semi-partitioned scheduling algorithms. Our approach is extended to periodic tasks under certain conditions. },
}
Over the years, many multiprocessor locking protocols have been designed and analyzed. However, the performance
of these protocols highly depends on how the tasks are partitioned and prioritized, and how the resources are shared locally and globally. This paper answers a few fundamental questions when real-time tasks share resources in multiprocessor systems. We explore the fundamental difficulty of the multiprocessor synchronization problem and show that a very simplified version of this problem is N P -hard in the strong sense regardless of the number of processors and the underlying scheduling paradigm. Therefore, the allowance of preemption or migration does not reduce the computational complexity. On the positive side, we develop a dependency-graph approach that is specifically useful
for frame-based real-time tasks, i.e., when all tasks have the same period and release their jobs always at the same time. We present a series of algorithms with speedup factors between 2 and 3 under semi-partitioned scheduling. We further explore methodologies for and tradeoffs between preemptive and non-preemptive scheduling algorithms, and partitioned and semi-partitioned scheduling algorithms. Our approach is extended to periodic tasks under certain conditions.
|
| Niklas Ueter, Georg von der Brüggen, Jian-Jia Chen, Jing Li and Kunal Agrawal.
Reservation-Based Federated Scheduling for Parallel Real-Time Tasks.
In 2018 IEEE Real-Time Systems Symposium, RTSS 2018, pages 482--494
Nashville, TN, USA, December 11-14 2018, Outstanding Paper Award
[BibTeX][PDF][Link][Abstract]@inproceedings { DBLP:conf/rtss/UeterBCLA18,
author = {Ueter, Niklas and Br\"uggen, Georg von der and Chen, Jian-Jia and Li, Jing and Agrawal, Kunal},
title = {Reservation-Based Federated Scheduling for Parallel Real-Time Tasks},
booktitle = {2018 IEEE Real-Time Systems Symposium, RTSS 2018},
year = {2018},
pages = {482--494},
address = {Nashville, TN, USA},
month = {December 11-14},
note = { Outstanding Paper Award },
url = {https://doi.org/10.1109/RTSS.2018.00061},
keywords = {georg},
file = {https://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2018-rtss-niklas.pdf},
confidential = {n},
abstract = {Multicore systems are increasingly utilized in real-time systems in order to address the high computational demands. To fully exploit the advantages of multicore processing, possible intra-task parallelism modeled as a directed acyclic graph (DAG) must be utilized efficiently. This paper considers the scheduling problem for parallel real-time tasks with constrained and arbitrary deadlines. In contrast to prior work in this area, it generalizes federated scheduling and proposes a novel reservation-based approach. Namely, we propose a reservation-based federated scheduling strategy that reduces the problem of scheduling arbitrary-deadline DAG task sets to the problem of scheduling arbitrary-deadline sequential task sets by allocating reservation servers. We provide the general reservation design for sporadic parallel tasks, such that any scheduling algorithm and analysis for sequential tasks with arbitrary deadlines can be used to execute the allocated reservation servers of parallel tasks. Moreover, the proposed reservation-based federated scheduling algorithms provide constant speedup factors with respect to any optimal scheduler for arbitrary-deadline DAG task sets. We demonstrate via numerical and empirical experiments that our algorithms are competitive with the state of the art.},
}
Multicore systems are increasingly utilized in real-time systems in order to address the high computational demands. To fully exploit the advantages of multicore processing, possible intra-task parallelism modeled as a directed acyclic graph (DAG) must be utilized efficiently. This paper considers the scheduling problem for parallel real-time tasks with constrained and arbitrary deadlines. In contrast to prior work in this area, it generalizes federated scheduling and proposes a novel reservation-based approach. Namely, we propose a reservation-based federated scheduling strategy that reduces the problem of scheduling arbitrary-deadline DAG task sets to the problem of scheduling arbitrary-deadline sequential task sets by allocating reservation servers. We provide the general reservation design for sporadic parallel tasks, such that any scheduling algorithm and analysis for sequential tasks with arbitrary deadlines can be used to execute the allocated reservation servers of parallel tasks. Moreover, the proposed reservation-based federated scheduling algorithms provide constant speedup factors with respect to any optimal scheduler for arbitrary-deadline DAG task sets. We demonstrate via numerical and empirical experiments that our algorithms are competitive with the state of the art.
|
DAES