| 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
Porto, Portugal, April 11-13 2018
[BibTeX][PDF][Link][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},
address = {Porto, Portugal},
month = {April 11-13},
url = {https://ieeexplore.ieee.org/document/8430080},
keywords = {kuan, georg, junjie},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2018_rtas_zheng.pdf},
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][PDF][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},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/khchentc2018.pdf},
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 , 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, Nikhil Bansal, Samarjit Chakraborty and Georg von der Brüggen.
Packing Sporadic Real-Time Tasks on Identical Multiprocessor Systems.
In International Symposium on Algorithms and Computation (ISAAC)
Jiaoxi, Yilan County, Taiwan, December 16-19 2018
[BibTeX][PDF][Link][Abstract]@inproceedings { Chen-ISAAC-2018,
author = {Chen, Jian-Jia and Bansal, Nikhil and Chakraborty, Samarjit and Br\"uggen, Georg von der},
title = {Packing Sporadic Real-Time Tasks on Identical Multiprocessor Systems},
booktitle = {International Symposium on Algorithms and Computation (ISAAC)},
year = {2018},
address = {Jiaoxi, Yilan County, Taiwan},
month = {December 16-19},
url = {https://doi.org/10.1109/PRDC.2018.00010},
keywords = {georg},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2018-isaac-jj.pdf},
confidential = {n},
abstract = {In real-time systems, in addition to the functional correctness recurrent tasks must fulfill timing constraints to ensure the correct behavior of the system. Partitioned scheduling is widely used in real-time systems, i.e., the tasks are statically assigned onto processors while ensuring that all timing constraints are met. The decision version of the problem, which is to check whether the deadline constraints of tasks can be satisfied on a given number of identical processors, has been known N P-complete in the strong sense. Several studies on this problem are based on approximations involving resource augmentation, i.e., speeding up individual processors. This paper studies another type of resource augmentation by allocating additional processors, a topic that has not been explored until recently. We provide polynomial-time algorithms and analysis, in which the approximation factors are dependent upon the input instances. Specifically, the factors are related to the maximum ratio of the period to the relative deadline of a task in the given task set. We also show that these algorithms unfortunately cannot achieve a constant approximation factor for general cases. Furthermore, we prove that the problem does not admit any asymptotic polynomial-time approximation scheme (APTAS) unless P = NP when the task set has constrained deadlines, i.e., the relative deadline of a task is no more than the period of the task.},
}
In real-time systems, in addition to the functional correctness recurrent tasks must fulfill timing constraints to ensure the correct behavior of the system. Partitioned scheduling is widely used in real-time systems, i.e., the tasks are statically assigned onto processors while ensuring that all timing constraints are met. The decision version of the problem, which is to check whether the deadline constraints of tasks can be satisfied on a given number of identical processors, has been known N P-complete in the strong sense. Several studies on this problem are based on approximations involving resource augmentation, i.e., speeding up individual processors. This paper studies another type of resource augmentation by allocating additional processors, a topic that has not been explored until recently. We provide polynomial-time algorithms and analysis, in which the approximation factors are dependent upon the input instances. Specifically, the factors are related to the maximum ratio of the period to the relative deadline of a task in the given task set. We also show that these algorithms unfortunately cannot achieve a constant approximation factor for general cases. Furthermore, we prove that the problem does not admit any asymptotic polynomial-time approximation scheme (APTAS) unless P = NP when the task set has constrained deadlines, i.e., the relative deadline of a task is no more than the period of the task.
|
| Georg von der 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][PDF][Link][Abstract]@inproceedings { brueggenetalPRDC2018,
author = {Br\"uggen, Georg von der 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},
url = {https://ieeexplore.ieee.org/document/8639554},
keywords = {georg, lea},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2018-prdc-georg.pdf},
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][Link][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},
url = {https://ieeexplore.ieee.org/document/8607245},
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.
|
| 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, junjie},
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.
|
| 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)
Barcelona, Spain, July 3 - 6 2018
[BibTeX][PDF][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},
address = {Barcelona, Spain},
month = {July 3 - 6},
url = {http://drops.dagstuhl.de/opus/volltexte/2018/8997/pdf/LIPIcs-ECRTS-2018-6.pdf},
keywords = {kuan, Georg},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2018-ecrts-georg.pdf},
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 , Outstanding Paper Award
[BibTeX][PDF][Link][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 , Outstanding Paper Award },
url = {https://ieeexplore.ieee.org/document/8607246},
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