| Zheng Dong, Cong Liu, Soroush Bateni, Kuan-Hsun Chen, Jian-Jia Chen, Georg von der Brüggen and Junjie Shi.
Shared-Resource-Centric Limited Preemptive Scheduling: A Comprehensive Study of Suspension-based Partitioning Approaches.
In IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)
2018
[BibTeX][Abstract]@inproceedings { dong2018rtas,
author = {Dong, Zheng and Liu, Cong and Bateni, Soroush and Chen, Kuan-Hsun and Chen, Jian-Jia and Br\"uggen, Georg von der and Shi, Junjie},
title = {Shared-Resource-Centric Limited Preemptive Scheduling: A Comprehensive Study of Suspension-based Partitioning Approaches},
booktitle = {IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)},
year = {2018},
keywords = {kuan, georg},
confidential = {n},
abstract = {This paper studies the problem of scheduling a set of hard real-time sporadic tasks that may access CPU cores and
a shared resource. Motivated by the observation that the CPU resource is often abundant compared to the shared resources in multi-core and many-core systems, we propose to resolve this problem from a counter-intuitive shared-resource-centric perspective, focusing on judiciously prioritizing and scheduling tasks’ requests in a limited preemptive manner on the shared resource while viewing the worst-case latency a task may experience on the CPU cores as suspension delays. We develop a rather comprehensive set of task partitioning algorithms that partition tasks onto the shared resource with the objective of guaranteeing schedulability while minimizing the required size of the shared resource, which plays a critical role in reducing the overall cost and complexity of building resource-constrained embedded systems in many application domains. A GPU-based prototype case study and extensive simulation-based experiments have been conducted, which validate both our shared-resource-centric scheduling philosophy and the efficiency of our suspension-based partitioning solutions in practice. },
}
This paper studies the problem of scheduling a set of hard real-time sporadic tasks that may access CPU cores and
a shared resource. Motivated by the observation that the CPU resource is often abundant compared to the shared resources in multi-core and many-core systems, we propose to resolve this problem from a counter-intuitive shared-resource-centric perspective, focusing on judiciously prioritizing and scheduling tasks’ requests in a limited preemptive manner on the shared resource while viewing the worst-case latency a task may experience on the CPU cores as suspension delays. We develop a rather comprehensive set of task partitioning algorithms that partition tasks onto the shared resource with the objective of guaranteeing schedulability while minimizing the required size of the shared resource, which plays a critical role in reducing the overall cost and complexity of building resource-constrained embedded systems in many application domains. A GPU-based prototype case study and extensive simulation-based experiments have been conducted, which validate both our shared-resource-centric scheduling philosophy and the efficiency of our suspension-based partitioning solutions in practice.
|
| Kuan-Hsun Chen, Georg von der Brüggen and Jian-Jia Chen.
Reliability Optimization on Multi-Core Systems with Multi-Tasking and Redundant Multi-Threading.
IEEE Transactions on Computers
2018, 10.1109/TC.2017.2769044
[BibTeX][Link][Abstract]@article { khchenTC2018,
author = {Chen, Kuan-Hsun and Br\"uggen, Georg von der and Chen, Jian-Jia},
title = {Reliability Optimization on Multi-Core Systems with Multi-Tasking and Redundant Multi-Threading},
journal = {IEEE Transactions on Computers},
year = {2018},
note = {10.1109/TC.2017.2769044},
url = {http://ieeexplore.ieee.org/abstract/document/8094023/},
keywords = {kuan, georg},
confidential = {n},
abstract = {Using Redundant Multithreading (RMT) for error detection and recovery is a prominent technique to mitigate soft-error effects in multi-core systems. Simultaneous Redundant Threading (SRT) on the same core or Chip-level Redundant Multithreading (CRT) on different cores can be adopted to implement RMT. However, only a few previously proposed approaches use adaptive CRT managements on the system level and none of them considers both SRT and CRT on the task level. In this paper, we propose to use a combination of SRT and CRT, called Mixed Redundant Threading (MRT), as an additional option on the task level. In our coarse-grained approach, we consider SRT, CRT, and MRT on the system level simultaneously, while the existing results only apply either SRT or CRT on the system level, but not simultaneously. In addition, we consider further fine-grained task level optimizations to improve the system reliability under hard real-time constraints. To optimize the system reliability, we develop several dynamic programming approaches to select the redundancy levels under Federated Scheduling. The simulation results illustrate that our approaches can significantly increase the system reliability compared to the state-of-the-art techniques.},
}
Using Redundant Multithreading (RMT) for error detection and recovery is a prominent technique to mitigate soft-error effects in multi-core systems. Simultaneous Redundant Threading (SRT) on the same core or Chip-level Redundant Multithreading (CRT) on different cores can be adopted to implement RMT. However, only a few previously proposed approaches use adaptive CRT managements on the system level and none of them considers both SRT and CRT on the task level. In this paper, we propose to use a combination of SRT and CRT, called Mixed Redundant Threading (MRT), as an additional option on the task level. In our coarse-grained approach, we consider SRT, CRT, and MRT on the system level simultaneously, while the existing results only apply either SRT or CRT on the system level, but not simultaneously. In addition, we consider further fine-grained task level optimizations to improve the system reliability under hard real-time constraints. To optimize the system reliability, we develop several dynamic programming approaches to select the redundancy levels under Federated Scheduling. The simulation results illustrate that our approaches can significantly increase the system reliability compared to the state-of-the-art techniques.
|
| 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, July 3-6, 2018, Barcelona, Spain, pages 8:1--8:24
2018
[BibTeX][Link]@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, July 3-6, 2018, Barcelona, Spain},
year = {2018},
pages = {8:1--8:24},
url = {http://drops.dagstuhl.de/opus/volltexte/2018/8996/pdf/LIPIcs-ECRTS-2018-8.pdf},
keywords = {georg},
confidential = {n},
} |
| Georg Brüggen, Lea Schönberger and Jian-Jia Chen.
Do Nothing, but Carefully: Fault Tolerance with Timing Guarantees for Multiprocessor Systems devoid of Online Adaptation.
In The 23rd IEEE Pacific Rim International Symposium on Dependable Computing (PRDC 2018)
Taipei, Taiwan, December 4-7 2018
[BibTeX][Abstract]@inproceedings { brueggenetalPRDC2018,
author = {Br\"uggen, Georg and Sch\"onberger, Lea and Chen, Jian-Jia},
title = {Do Nothing, but Carefully: Fault Tolerance with Timing Guarantees for Multiprocessor Systems devoid of Online Adaptation},
booktitle = {The 23rd IEEE Pacific Rim International Symposium on Dependable Computing (PRDC 2018)},
year = {2018},
address = {Taipei, Taiwan},
month = {December 4-7},
keywords = {georg, lea},
confidential = {n},
abstract = {Many practical real-time systems must be able to sustain several reliability threats induced by their physical environments that cause short-term abnormal system behavior, such as transient faults. To cope with this change of system behavior, online adaptions, which may introduce a high computation
overhead, are performed in many cases to ensure the timeliness of the more important tasks while no guarantees are provided for the less important tasks. In this work, we propose a system model which does not require any online adaption, but, according to the concept of dynamic real-time guarantees, provides full timing guarantees as well as limited timing guarantees, depending on the system behavior. For the normal system behavior, timeliness is guaranteed for all tasks; otherwise, timeliness is guaranteed only for the more important tasks while bounded tardiness is ensured for the less important tasks. Aiming to provide such dynamic timing guarantees, we propose a suitable system model and discuss, how this can be established by means of partitioned as well as semi-partitioned strategies. Moreover, we propose an approach for handling abnormal behavior with a longer duration, such as intermittent faults or overheating of processors, by performing task migration in order to compensate the affected system component and to increase the system’s reliability. We show by comprehensive experiments that good acceptance ratios can be achieved under partitioned scheduling, which can be further improved under semi-partitioned strategies. In addition, we demonstrate that the proposed migration techniques lead to a reasonable trade-off between the decrease in schedulability and the gain in robustness of the system. The presented approaches can also be applied to mixed-criticality systems with two criticality levels.},
}
Many practical real-time systems must be able to sustain several reliability threats induced by their physical environments that cause short-term abnormal system behavior, such as transient faults. To cope with this change of system behavior, online adaptions, which may introduce a high computation
overhead, are performed in many cases to ensure the timeliness of the more important tasks while no guarantees are provided for the less important tasks. In this work, we propose a system model which does not require any online adaption, but, according to the concept of dynamic real-time guarantees, provides full timing guarantees as well as limited timing guarantees, depending on the system behavior. For the normal system behavior, timeliness is guaranteed for all tasks; otherwise, timeliness is guaranteed only for the more important tasks while bounded tardiness is ensured for the less important tasks. Aiming to provide such dynamic timing guarantees, we propose a suitable system model and discuss, how this can be established by means of partitioned as well as semi-partitioned strategies. Moreover, we propose an approach for handling abnormal behavior with a longer duration, such as intermittent faults or overheating of processors, by performing task migration in order to compensate the affected system component and to increase the system’s reliability. We show by comprehensive experiments that good acceptance ratios can be achieved under partitioned scheduling, which can be further improved under semi-partitioned strategies. In addition, we demonstrate that the proposed migration techniques lead to a reasonable trade-off between the decrease in schedulability and the gain in robustness of the system. The presented approaches can also be applied to mixed-criticality systems with two criticality levels.
|
| Lea Schönberger, Wen-Hung Huang, Georg von der Brüggen, Kuan-Hsun Chen and Jian-Jia Chen.
Schedulability Analysis and Priority Assignment for Segmented Self-Suspending Tasks.
In The 24th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)
Hakodate, Japan, August 28-31 2018
[BibTeX][Abstract]@inproceedings { schoenbergerRTCSA2018,
author = {Sch\"onberger, Lea and Huang, Wen-Hung and Br\"uggen, Georg von der and Chen, Kuan-Hsun and Chen, Jian-Jia},
title = {Schedulability Analysis and Priority Assignment for Segmented Self-Suspending Tasks},
booktitle = {The 24th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)},
year = {2018},
address = {Hakodate, Japan},
month = {August 28-31},
keywords = {kuan, lea, Georg},
confidential = {n},
abstract = {Self-suspending behavior in real-time embedded systems can have a major and non-trivial negative impact on
timing predictability. In this work, we investigate how to analyze the schedulability of segmented self-suspending task systems under a fixed-priority assignment. For this purpose, we introduce the multi-segment workload function as well as the maximum workload function in order to quantify the maximum interference from the higher-priority tasks when constructing our (sufficient) schedulability test. Moreover, we derive an optimal priority assignment with respect to our schedulability test since it is compatible with Audsley’s Optimal Priority Assignment (OPA). We show by means of comprehensive evaluations that our approach is highly effective concerning the number of schedulable task sets.
Furthermore, one set of results reveals a rather non-intuitive observation, namely, that the worst-case suspension time of a computation segment should also be respected to improve the schedulability even if the suspension may finish earlier.},
}
Self-suspending behavior in real-time embedded systems can have a major and non-trivial negative impact on
timing predictability. In this work, we investigate how to analyze the schedulability of segmented self-suspending task systems under a fixed-priority assignment. For this purpose, we introduce the multi-segment workload function as well as the maximum workload function in order to quantify the maximum interference from the higher-priority tasks when constructing our (sufficient) schedulability test. Moreover, we derive an optimal priority assignment with respect to our schedulability test since it is compatible with Audsley’s Optimal Priority Assignment (OPA). We show by means of comprehensive evaluations that our approach is highly effective concerning the number of schedulable task sets.
Furthermore, one set of results reveals a rather non-intuitive observation, namely, that the worst-case suspension time of a computation segment should also be respected to improve the schedulability even if the suspension may finish earlier.
|
| Georg von der Brüggen, Nico Piatkowski, Kuan-Hsun Chen, Jian-Jia Chen and Katharina Morik.
Efficiently Approximating the Probability of Deadline Misses in Real-Time Systems.
In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018)
2018
[BibTeX][Link][Abstract]@inproceedings { DBLP:conf/ecrts/BruggenPCCM18,
author = {Br\"uggen, Georg von der and Piatkowski, Nico and Chen, Kuan-Hsun and Chen, Jian-Jia and Morik, Katharina},
title = {Efficiently Approximating the Probability of Deadline Misses in Real-Time Systems},
booktitle = {30th Euromicro Conference on Real-Time Systems (ECRTS 2018) },
year = {2018},
url = {http://drops.dagstuhl.de/opus/volltexte/2018/8997/pdf/LIPIcs-ECRTS-2018-6.pdf},
keywords = {kuan, Georg},
confidential = {n},
abstract = {This paper explores the probability of deadline misses for a set of constrained-deadline sporadic soft real-time tasks on uniprocessor platforms. We explore two directions to evaluate the probability whether a job of the task under analysis can finish its execution at (or before) a testing time point t. One approach is based on analytical upper bounds that can be efficiently computed in polynomial time at the price of precision loss for each testing point, derived from the well-known Hoeffding's inequality and the well-known Bernstein's inequality. Another approach convolutes the probability efficiently over multinomial distributions, exploiting a series of state space reduction techniques, i.e., pruning without any loss of precision, and approximations via unifying equivalent classes with a bounded loss of precision. We demonstrate the effectiveness of our approaches in a series of evaluations. Distinct from the convolution-based methods in the literature, which suffer from the high computation demand and are applicable only to task sets with a few tasks, our approaches can scale reasonably without losing much precision in terms of the derived probability of deadline misses. },
}
This paper explores the probability of deadline misses for a set of constrained-deadline sporadic soft real-time tasks on uniprocessor platforms. We explore two directions to evaluate the probability whether a job of the task under analysis can finish its execution at (or before) a testing time point t. One approach is based on analytical upper bounds that can be efficiently computed in polynomial time at the price of precision loss for each testing point, derived from the well-known Hoeffding's inequality and the well-known Bernstein's inequality. Another approach convolutes the probability efficiently over multinomial distributions, exploiting a series of state space reduction techniques, i.e., pruning without any loss of precision, and approximations via unifying equivalent classes with a bounded loss of precision. We demonstrate the effectiveness of our approaches in a series of evaluations. Distinct from the convolution-based methods in the literature, which suffer from the high computation demand and are applicable only to task sets with a few tasks, our approaches can scale reasonably without losing much precision in terms of the derived probability of deadline misses.
|
| Kuan-Hsun Chen, Georg von der Brüggen and Jian-Jia Chen.
Analysis of Deadline Miss Rates for Uniprocessor Fixed-Priority Scheduling.
In The 24th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)
Hakodate, Japan, August 2018, Best Student Paper Award
[BibTeX][PDF][Abstract]@inproceedings { khchenRTCSA18,
author = {Chen, Kuan-Hsun and Br\"uggen, Georg von der and Chen, Jian-Jia},
title = {Analysis of Deadline Miss Rates for Uniprocessor Fixed-Priority Scheduling},
booktitle = {The 24th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)},
year = {2018},
address = {Hakodate, Japan},
month = {August},
note = { Best Student Paper Award },
keywords = {Georg, kuan},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2018-kuanrtcsa.pdf},
confidential = {n},
abstract = {Timeliness is an important feature for many embedded systems. Although soft real-time embedded systems can tolerate and allow certain deadline misses, it is still important to quantify them to justify whether the considered systems are acceptable. In this paper, we provide a way to safely over-approximate the expected deadline miss rate for a specific sporadic real-time task under fixed-priority preemptive scheduling in uniprocessor systems. Our approach is compatible with the existing results in the literature that calculate the probability of deadline misses either based on the convolution-based approaches or analytically. We demonstrate our approach by considering randomly generated task sets with an execution behavior that simulates jobs that are subjected to soft errors incurred by hardware transient faults under a given fault rate. To empirically gather the deadline miss rates, we implemented an event-based simulator with a fault-injection module and release the scripts. With extensive simulations under different fault rates, we evaluate the efficiency and the pessimism of our approach. The evaluation results show that our approach is effective to derive an upper bound of the expected deadline miss rate and efficient with respect to the required computation time.},
}
Timeliness is an important feature for many embedded systems. Although soft real-time embedded systems can tolerate and allow certain deadline misses, it is still important to quantify them to justify whether the considered systems are acceptable. In this paper, we provide a way to safely over-approximate the expected deadline miss rate for a specific sporadic real-time task under fixed-priority preemptive scheduling in uniprocessor systems. Our approach is compatible with the existing results in the literature that calculate the probability of deadline misses either based on the convolution-based approaches or analytically. We demonstrate our approach by considering randomly generated task sets with an execution behavior that simulates jobs that are subjected to soft errors incurred by hardware transient faults under a given fault rate. To empirically gather the deadline miss rates, we implemented an event-based simulator with a fault-injection module and release the scripts. With extensive simulations under different fault rates, we evaluate the efficiency and the pessimism of our approach. The evaluation results show that our approach is effective to derive an upper bound of the expected deadline miss rate and efficient with respect to the required computation time.
|
| Nils Hölscher, Kuan-Hsun Chen, Georg von der Brüggen and Jian-Jia Chen.
Examining and Supporting Multi-Tasking in EV3OSEK.
In 14th annual workshop on Operating Systems Platforms for Embedded Real-Time applications (OSPERT 2018), Barcelona, Spain
Barcelona, Spain, July 2018
[BibTeX][PDF][Abstract]@inproceedings { Nils-OSPERT,
author = {H\"olscher, Nils and Chen, Kuan-Hsun and Br\"uggen, Georg von der and Chen, Jian-Jia},
title = {Examining and Supporting Multi-Tasking in EV3OSEK},
booktitle = {14th annual workshop on Operating Systems Platforms for Embedded Real-Time applications (OSPERT 2018), Barcelona, Spain},
year = {2018},
address = {Barcelona, Spain},
month = {July},
keywords = {kuan, Georg},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2018-nils.pdf},
confidential = {n},
abstract = {Lego Mindstorms Robots are a popular platform for graduate level researches and college education purposes. As a
portation of nxtOSEK, an OSEK standard compatible real-time operation system, EV3OSEK inherits the advantages of nxtOSEK for experiments on EV3, the latest generation of Mindstorms robots. Unfortunately, the current version of EV3OSEK still has some serious errors. In this work we address task preemption, a common feature desired in every RTOS. We reveal the errors in the current version and propose corresponding solutions for EV3OSEK that fix the errors in the IRQ-Handler and the task dispatching properly, thus enabling real multi-tasking on EV3OSEK. Our verifications show that the current design flaws are solved. Along with this work, we suggest that researchers who performed experiments on nxtOSEK should carefully examine if the flaws presented in this paper affect their results.},
}
Lego Mindstorms Robots are a popular platform for graduate level researches and college education purposes. As a
portation of nxtOSEK, an OSEK standard compatible real-time operation system, EV3OSEK inherits the advantages of nxtOSEK for experiments on EV3, the latest generation of Mindstorms robots. Unfortunately, the current version of EV3OSEK still has some serious errors. In this work we address task preemption, a common feature desired in every RTOS. We reveal the errors in the current version and propose corresponding solutions for EV3OSEK that fix the errors in the IRQ-Handler and the task dispatching properly, thus enabling real multi-tasking on EV3OSEK. Our verifications show that the current design flaws are solved. Along with this work, we suggest that researchers who performed experiments on nxtOSEK should carefully examine if the flaws presented in this paper affect their results.
|
DAES