| Junjie Shi, Niklas Ueter, Georg von der Brüggen and Jian-Jia Chen.
Multiprocessor Synchronization of Periodic Real-Time Tasks Using Dependency Graphs.
In 25th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS, pages 279--292
2019
[BibTeX][PDF][Link][Abstract]@inproceedings { DBLP:conf/rtas/ShiUBC19,
author = {Shi, Junjie and Ueter, Niklas and Br\"uggen, Georg von der and Chen, Jian-Jia},
title = {Multiprocessor Synchronization of Periodic Real-Time Tasks Using Dependency Graphs},
booktitle = {25th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS},
year = {2019},
pages = {279--292},
url = {https://doi.org/10.1109/RTAS.2019.00031},
keywords = {georg, junjie},
file = {https://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2019-rtas-junjie.pdf},
confidential = {n},
abstract = {When considering recurrent real-time tasks in multiprocessor systems, access to shared resources, via so-called critical sections, can jeopardize the schedulability of the system. The reason is that resource access is mutual exclusive and a task must finish its execution of the critical section before another task can access the same resource. Therefore, the problem of multiprocessor synchronization has been extensively studied since the 1990s, and a large number of multiprocessor resource sharing protocols have been developed and analyzed. Most protocols assume work-conserving scheduling algorithms which make it impossible to schedule task sets where a critical section of one task is longer than the relative deadline of another task that accesses the same resource. The only known exception to the work-conserving paradigm is the recently presented Dependency Graph Approach where the order in which tasks access a shared resource is not determined online, but based on a pre-computed dependency graph. Since the initial work only considers frame-based task systems, this paper extends the Dependency Graph Approach to periodic task systems. We point out the connection to the uniprocessor non-preemptive scheduling problem and exploit the related algorithms to construct dependency graphs for each resource. To schedule the derived dependency graphs, List scheduling is combined with an earliest-deadline-first heuristic. We evaluated the performance considering synthesized task sets under different configurations, where a significant improvement of the acceptance ratio compared to other resource sharing protocols is observed. Furthermore, to show the applicability in real-world systems, we detail the implementation in LITMUS RT and report the resulting scheduling overheads.},
}
When considering recurrent real-time tasks in multiprocessor systems, access to shared resources, via so-called critical sections, can jeopardize the schedulability of the system. The reason is that resource access is mutual exclusive and a task must finish its execution of the critical section before another task can access the same resource. Therefore, the problem of multiprocessor synchronization has been extensively studied since the 1990s, and a large number of multiprocessor resource sharing protocols have been developed and analyzed. Most protocols assume work-conserving scheduling algorithms which make it impossible to schedule task sets where a critical section of one task is longer than the relative deadline of another task that accesses the same resource. The only known exception to the work-conserving paradigm is the recently presented Dependency Graph Approach where the order in which tasks access a shared resource is not determined online, but based on a pre-computed dependency graph. Since the initial work only considers frame-based task systems, this paper extends the Dependency Graph Approach to periodic task systems. We point out the connection to the uniprocessor non-preemptive scheduling problem and exploit the related algorithms to construct dependency graphs for each resource. To schedule the derived dependency graphs, List scheduling is combined with an earliest-deadline-first heuristic. We evaluated the performance considering synthesized task sets under different configurations, where a significant improvement of the acceptance ratio compared to other resource sharing protocols is observed. Furthermore, to show the applicability in real-world systems, we detail the implementation in LITMUS RT and report the resulting scheduling overheads.
|
| Junjie Shi, Niklas Ueter, Georg von der Brüggen and Jian-Jia Chen.
Partitioned Scheduling for Dependency Graphs in Multiprocessor Real-Time Systems.
In 25th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA, pages 1--12
Hangzhou, China, August 18-21 2019
[BibTeX][PDF][Link][Abstract]@inproceedings { DBLP:conf/rtcsa/ShiUBC19,
author = {Shi, Junjie and Ueter, Niklas and Br\"uggen, Georg von der and Chen, Jian-Jia},
title = {Partitioned Scheduling for Dependency Graphs in Multiprocessor Real-Time Systems},
booktitle = {25th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA},
year = {2019},
pages = {1--12},
address = {Hangzhou, China},
month = {August 18-21},
url = {https://ieeexplore.ieee.org/document/8864591},
keywords = {georg, junjie},
file = {https://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/shi-partitioned.pdf},
confidential = {n},
abstract = {Effectively handling precedence constraints and resource synchronization is a challenging problem in the era of multiprocessor systems even with massively parallel computation power. One common approach is to apply list scheduling to a given task graph with precedence constraints. However, in some application scenarios, such as the OpenMP task model and multiprocessor partitioned scheduling for resource synchronization using binary semaphores, several operations can be forced to be tied to the same processor, which invalidates the list scheduling. This paper studies a special case of this challenging scheduling problem, where a task comprised of (at most) three subtasks is executed sequentially on the same processor and the second subtasks of the tasks may have sequential dependencies, e.g., due to synchronization. We demonstrate the limits of existing algorithms and provide effective heuristics considering preemptive execution. The evaluation results show a significant improvement, compared to the existing multiprocessor partitioned scheduling strategies.},
}
Effectively handling precedence constraints and resource synchronization is a challenging problem in the era of multiprocessor systems even with massively parallel computation power. One common approach is to apply list scheduling to a given task graph with precedence constraints. However, in some application scenarios, such as the OpenMP task model and multiprocessor partitioned scheduling for resource synchronization using binary semaphores, several operations can be forced to be tied to the same processor, which invalidates the list scheduling. This paper studies a special case of this challenging scheduling problem, where a task comprised of (at most) three subtasks is executed sequentially on the same processor and the second subtasks of the tasks may have sequential dependencies, e.g., due to synchronization. We demonstrate the limits of existing algorithms and provide effective heuristics considering preemptive execution. The evaluation results show a significant improvement, compared to the existing multiprocessor partitioned scheduling strategies.
|
DAES