| Wen-Hung Huang and Jian-Jia Chen.
Self-Suspension Real-Time Tasks under Fixed-Relative-Deadline Fixed-Priority Scheduling.
In Design, Automation and Test in Europe (DATE)
Dresden, Germany, 14 -18th Mar 2016
[BibTeX][PDF][Abstract]@inproceedings { HC16,
author = {Huang, Wen-Hung and Chen, Jian-Jia},
title = {Self-Suspension Real-Time Tasks under Fixed-Relative-Deadline Fixed-Priority Scheduling},
booktitle = {Design, Automation and Test in Europe (DATE)},
year = {2016},
address = {Dresden, Germany},
month = {14 -18th Mar},
keywords = {kevin},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/Self-Suspension-EDA-FP-6p},
confidential = {n},
abstract = {Self-suspension is becoming a prominent characteristic in real-time systems such as:
(i) I/O-intensive systems (ii) multi-core processors, and (iii) computation offloading systems
with coprocessors, like Graphics Processing Units (GPUs).
In this work, we study self-suspension systems under fixed-priority (FP) fixed-relative-deadline (FRD) algorithm by using release enforcement to control self-suspension tasks' behavior. Specifically, we use equal-deadline assignment (EDA) to assign the release phases of computations and suspensions.
We provide analysis for deriving the speedup factor of the FP FRD scheduler using suspension-laxity-monotonic (SLM) priority assignment.
This is the first positive result to provide bounded speedup factor guarantees for general multi-segment self-suspending task systems.},
}
Self-suspension is becoming a prominent characteristic in real-time systems such as:
(i) I/O-intensive systems (ii) multi-core processors, and (iii) computation offloading systems
with coprocessors, like Graphics Processing Units (GPUs).
In this work, we study self-suspension systems under fixed-priority (FP) fixed-relative-deadline (FRD) algorithm by using release enforcement to control self-suspension tasks' behavior. Specifically, we use equal-deadline assignment (EDA) to assign the release phases of computations and suspensions.
We provide analysis for deriving the speedup factor of the FP FRD scheduler using suspension-laxity-monotonic (SLM) priority assignment.
This is the first positive result to provide bounded speedup factor guarantees for general multi-segment self-suspending task systems.
|
| Wen-Hung Huang, Jian-Jia Chen and Jan Reineke.
MIRROR: Symmetric Timing Analysis for Real-Time Tasks on Multicore Platforms with Shared Resources.
In Design Automation Conference (DAC)
Austin, TX, USA, June 05-09 2016
[BibTeX][PDF][Abstract]@inproceedings { WR16,
author = {Huang, Wen-Hung and Chen, Jian-Jia and Reineke, Jan},
title = {MIRROR: Symmetric Timing Analysis for Real-Time Tasks on Multicore Platforms with Shared Resources},
booktitle = {Design Automation Conference (DAC)},
year = {2016},
address = {Austin, TX, USA},
month = {June 05-09 },
keywords = {kevin},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/PID4192125-mirror.pdf},
confidential = {n},
abstract = {The emergence of multicore and manycore platforms poses a
big challenge for the design of real-time embedded systems,
especially for timing analysis. We observe in this paper that
response-time analysis for multicore platforms with shared
resources can be symmetrically approached from two per-
spectives: a core-centric and a shared-resource-centric per-
spective. The common \core-centric" perspective is that a
task executes on a core until it suspends the execution due
to shared resource accesses. The potentially less intuitive
\shared-resource-centric" perspective is that a task performs
requests on shared resources until suspending itself back to
perform computation on its respective core.
Based on the above observation, we provide a pseudo-
polynomial-time schedulability test and response-time anal-
ysis for constrained-deadline sporadic task systems. In addi-
tion, we propose a task partitioning algorithm that achieves a
speedup factor of 7, compared to the optimal schedule. This
constitutes the rst result in this research line with a speedup
factor guarantee. The experimental evaluation demonstrates
that our approach can yield high acceptance ratios if the
tasks have only a few resource access segments.},
}
The emergence of multicore and manycore platforms poses a
big challenge for the design of real-time embedded systems,
especially for timing analysis. We observe in this paper that
response-time analysis for multicore platforms with shared
resources can be symmetrically approached from two per-
spectives: a core-centric and a shared-resource-centric per-
spective. The common \core-centric" perspective is that a
task executes on a core until it suspends the execution due
to shared resource accesses. The potentially less intuitive
\shared-resource-centric" perspective is that a task performs
requests on shared resources until suspending itself back to
perform computation on its respective core.
Based on the above observation, we provide a pseudo-
polynomial-time schedulability test and response-time anal-
ysis for constrained-deadline sporadic task systems. In addi-
tion, we propose a task partitioning algorithm that achieves a
speedup factor of 7, compared to the optimal schedule. This
constitutes the rst result in this research line with a speedup
factor guarantee. The experimental evaluation demonstrates
that our approach can yield high acceptance ratios if the
tasks have only a few resource access segments.
|
| Kuan-Hsun Chen, Georg von der Brüggen and Jian-Jia Chen.
Overrun Handling for Mixed-Criticality Support in RTEMS.
In Workshop on Mixed-Criticality Systems
Porto, Portugal, Nov 29 2016
[BibTeX][Link][Abstract]@inproceedings { WMC2016,
author = {Chen, Kuan-Hsun and Br\"uggen, Georg von der and Chen, Jian-Jia},
title = {Overrun Handling for Mixed-Criticality Support in RTEMS},
booktitle = {Workshop on Mixed-Criticality Systems},
year = {2016},
address = {Porto, Portugal},
month = {Nov 29},
url = {https://hal.archives-ouvertes.fr/hal-01438843/document},
keywords = {kuan, Georg},
confidential = {n},
abstract = {Real-time operating systems are not only used in embedded real-time systems but also useful for the simulation and
validation of those systems. During the evaluation of our paper about Systems with Dynamic Real-Time Guarantees that appears in RTSS 2016 we discovered certain unexpected system behavior in the open-source real-time operating system RTEMS. In the current implementation of RTEMS (version 4.11), overruns of an implicit-deadline task, i.e., deadline misses, result in unexpected system behavior as they may lead to a shift of the release pattern of the task. This also has the consequence that some task instances are not released as they should be. In this paper we explain the reason why such problems occur in RTEMS and our solutions.},
}
Real-time operating systems are not only used in embedded real-time systems but also useful for the simulation and
validation of those systems. During the evaluation of our paper about Systems with Dynamic Real-Time Guarantees that appears in RTSS 2016 we discovered certain unexpected system behavior in the open-source real-time operating system RTEMS. In the current implementation of RTEMS (version 4.11), overruns of an implicit-deadline task, i.e., deadline misses, result in unexpected system behavior as they may lead to a shift of the release pattern of the task. This also has the consequence that some task instances are not released as they should be. In this paper we explain the reason why such problems occur in RTEMS and our solutions.
|
| Jian-Jia Chen, Wen-Hung Huang and Cong Liu.
k2Q: A Quadratic-Form Response Time and Schedulability Analysis Framework for Utilization-Based Analysis.
In Real-Time Systems Symposium (RTSS)
Porto, Portugal, Nov. 29 - Dec. 2 2016
[BibTeX]@inproceedings { RTSS2016-k2Q,
author = {Chen, Jian-Jia and Huang, Wen-Hung and Liu, Cong},
title = {k2Q: A Quadratic-Form Response Time and Schedulability Analysis Framework for Utilization-Based Analysis},
booktitle = {Real-Time Systems Symposium (RTSS)},
year = {2016},
address = {Porto, Portugal},
month = {Nov. 29 - Dec. 2},
keywords = {kevin },
confidential = {n},
} |
| Kuan-Hsun Chen, Björn Bönninghoff, Jian-Jia Chen and Peter Marwedel.
Compensate or Ignore? Meeting Control Robustness Requirements through Adaptive Soft-Error Handling.
In Languages, Compilers, Tools and Theory for Embedded Systems (LCTES)
Santa Barbara, CA, U.S.A., June 2016
[BibTeX][PDF][Link][Abstract]@inproceedings { Chenlctes2016,
author = {Chen, Kuan-Hsun and B\"onninghoff, Bj\"orn and Chen, Jian-Jia and Marwedel, Peter},
title = {Compensate or Ignore? Meeting Control Robustness Requirements through Adaptive Soft-Error Handling},
booktitle = {Languages, Compilers, Tools and Theory for Embedded Systems (LCTES)},
year = {2016},
address = {Santa Barbara, CA, U.S.A.},
month = {June},
organization = {ACM},
url = {http://dx.doi.org/10.1145/2907950.2907952},
keywords = {kuan},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2016-khchen-lctes.pdf},
confidential = {n},
abstract = {To avoid catastrophic events like unrecoverable system failures on mobile and embedded systems caused by soft-errors, software-
based error detection and compensation techniques have been proposed. Methods like error-correction codes or redundant execution can offer high flexibility and allow for application-specific fault-tolerance selection without the needs of special hardware supports. However, such software-based approaches may lead to system overload due to the execution time overhead. An adaptive deployment of such techniques to meet both application requirements and system constraints is desired. From our case study, we observe that a control task can tolerate limited errors with acceptable performance loss. Such tolerance can be modeled as a (m, k) constraint which requires at least m correct runs out of any k consecutive runs to be correct. In this paper, we discuss how a given (m, k) constraint can be satisfied by adopting patterns of task instances with individual error detection and compensation capabilities. We introduce static strategies and provide a formal feasibility analysis for validation. Furthermore, we develop an adaptive scheme that extends our initial approach with online awareness that increases efficiency while preserving analysis results. The effectiveness of our method is shown in a real-world case study as well as for synthesized task sets.},
}
To avoid catastrophic events like unrecoverable system failures on mobile and embedded systems caused by soft-errors, software-
based error detection and compensation techniques have been proposed. Methods like error-correction codes or redundant execution can offer high flexibility and allow for application-specific fault-tolerance selection without the needs of special hardware supports. However, such software-based approaches may lead to system overload due to the execution time overhead. An adaptive deployment of such techniques to meet both application requirements and system constraints is desired. From our case study, we observe that a control task can tolerate limited errors with acceptable performance loss. Such tolerance can be modeled as a (m, k) constraint which requires at least m correct runs out of any k consecutive runs to be correct. In this paper, we discuss how a given (m, k) constraint can be satisfied by adopting patterns of task instances with individual error detection and compensation capabilities. We introduce static strategies and provide a formal feasibility analysis for validation. Furthermore, we develop an adaptive scheme that extends our initial approach with online awareness that increases efficiency while preserving analysis results. The effectiveness of our method is shown in a real-world case study as well as for synthesized task sets.
|
| Wen-Hung Huang, Maolin Yang and Jian-Jia Chen.
Resource-Oriented Partitioned Scheduling in Multiprocessor Systems: How to Partition and How to Share?.
In Real-Time Systems Symposium (RTSS)
Porto, Portugal, Nov. 29 - Dec. 2 2016, (Outstanding Paper Award).
We identified some typos and revised the paper on May. 29th 2017. Revised version
[BibTeX][PDF][Link]@inproceedings { RTSS2016-resource,
author = {Huang, Wen-Hung and Yang, Maolin and Chen, Jian-Jia},
title = {Resource-Oriented Partitioned Scheduling in Multiprocessor Systems: How to Partition and How to Share?},
booktitle = {Real-Time Systems Symposium (RTSS)},
year = {2016},
address = {Porto, Portugal},
month = {Nov. 29 - Dec. 2},
publisher = { Revised version with latexdiff},
note = { (Outstanding Paper Award).
We identified some typos and revised the paper on May. 29th 2017. Revised version},
url = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2017-synchronization-revised-diff.pdf},
keywords = {kevin},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2016-kevin-synchronization_RTSS_camera_ready.pdf},
confidential = {n},
} |
| Jian-Jia Chen.
Computational Complexity and Speedup Factors Analyses for Self-Suspending Tasks.
In Real-Time Systems Symposium (RTSS)
Porto, Portugal, Nov. 29 - Dec. 2 2016
[BibTeX][PDF]@inproceedings { RTSS2016-suspension,
author = {Chen, Jian-Jia},
title = {Computational Complexity and Speedup Factors Analyses for Self-Suspending Tasks},
booktitle = {Real-Time Systems Symposium (RTSS)},
year = {2016},
address = {Porto, Portugal},
month = {Nov. 29 - Dec. 2},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2016-JJ-Suspension-Complexity.pdf},
confidential = {n},
} |
| Jian-Jia Chen.
Partitioned Multiprocessor Fixed-Priority Scheduling of Sporadic Real-Time Tasks.
In Euromicro Conference on Real-Time Systems (ECRTS)
Toulouse, France, 05-08, July 2016,
(Outstanding Paper Award) An extended version is available via arXiv: http://arxiv.org/abs/1505.04693
[BibTeX][PDF][Abstract]@inproceedings { ChenECRTS2016-Partition,
author = {Chen, Jian-Jia},
title = {Partitioned Multiprocessor Fixed-Priority Scheduling of Sporadic Real-Time Tasks},
booktitle = {Euromicro Conference on Real-Time Systems (ECRTS)},
year = {2016},
address = {Toulouse, France},
month = {05-08, July},
note = {
(Outstanding Paper Award) An extended version is available via arXiv: http://arxiv.org/abs/1505.04693},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2016-chen-ecrts16-partition.pdf},
confidential = {n},
abstract = { Partitioned multiprocessor scheduling has been widely accepted in
academia and industry to statically assign and partition real-time
tasks onto identical multiprocessor systems. This paper studies
fixed-priority partitioned multiprocessor scheduling for sporadic
real-time systems, in which deadline-monotonic scheduling is applied
on each processor. Prior to this paper, the best known results are
by Fisher, Baruah, and Baker with speedup factors $4-\frac{2}{M}$
and $3-\frac{1}{M}$ for arbitrary-deadline and constrained-deadline
sporadic real-time task systems, respectively, where $M$ is the
number of processors. We show that a
greedy mapping strategy has a speedup factor $3-\frac{1}{M}$ when
considering task systems with arbitrary deadlines. Such a factor holds for polynomial-time
schedulability tests and exponential-time (exact) schedulability
tests. Moreover, we also improve the speedup factor to $2.84306$
when considering constrained-deadline task systems.
We also provide tight examples when the fitting strategy in the
mapping stage is arbitrary and $M$ is sufficiently large.
For both constrained- and
arbitrary-deadline task systems, the analytical result surprisingly shows that using exact tests does not gain
theoretical benefits (with respect to speedup factors) if the speedup factor analysis
is oblivious of the particular fitting strategy used.},
}
Partitioned multiprocessor scheduling has been widely accepted in
academia and industry to statically assign and partition real-time
tasks onto identical multiprocessor systems. This paper studies
fixed-priority partitioned multiprocessor scheduling for sporadic
real-time systems, in which deadline-monotonic scheduling is applied
on each processor. Prior to this paper, the best known results are
by Fisher, Baruah, and Baker with speedup factors $4-2{M}$
and $3-1{M}$ for arbitrary-deadline and constrained-deadline
sporadic real-time task systems, respectively, where $M$ is the
number of processors. We show that a
greedy mapping strategy has a speedup factor $3-1{M}$ when
considering task systems with arbitrary deadlines. Such a factor holds for polynomial-time
schedulability tests and exponential-time (exact) schedulability
tests. Moreover, we also improve the speedup factor to $2.84306$
when considering constrained-deadline task systems.
We also provide tight examples when the fitting strategy in the
mapping stage is arbitrary and $M$ is sufficiently large.
For both constrained- and
arbitrary-deadline task systems, the analytical result surprisingly shows that using exact tests does not gain
theoretical benefits (with respect to speedup factors) if the speedup factor analysis
is oblivious of the particular fitting strategy used.
|
| Georg von der Brüggen, Kuan-Hsun Chen, Wen-Hung Huang and Jian-Jia Chen.
Systems with Dynamic Real-Time Guarantees in Uncertain and Faulty Execution Environments.
In Real-Time Systems Symposium (RTSS)
Porto, Portugal, Nov. 29 - Dec. 2 2016
[BibTeX][PDF][Link][Abstract]@inproceedings { RTSS2016-dynamic-faulty,
author = {Br\"uggen, Georg von der and Chen, Kuan-Hsun and Huang, Wen-Hung and Chen, Jian-Jia},
title = {Systems with Dynamic Real-Time Guarantees in Uncertain and Faulty Execution Environments},
booktitle = {Real-Time Systems Symposium (RTSS)},
year = {2016},
address = {Porto, Portugal},
month = {Nov. 29 - Dec. 2},
url = {https://ieeexplore.ieee.org/document/7809865},
keywords = {georg, kevin, kuan},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2016_rtss_georg.pdf},
confidential = {n},
abstract = {In many practical real-time systems, the physical environment and the system platform can impose uncertain
execution behaviour to the system. For example, if transient faults are detected, the execution time of a task instance can be increased due to recovery operations. Such fault recovery routines make the system very vulnerable with respect to meeting hard real-time deadlines. In theory and in practical systems, this problem is often handled by aborting not so important tasks to guarantee the response time of the more important tasks. However, for most systems such faults occur rarely and the results of not so important tasks might still be useful, even if they are a bit late. This implicates to not abort these not so important tasks but keep them running even if faults occur, provided that the more important tasks still meet their hard real time properties. In this paper, we present Systems with Dynamic Real-Time Guarantees to model this behaviour and determine if the system can provide full timing guarantees or limited timing guarantees without any online adaptation after a fault occurred. We present a schedulability test, provide an algorithm for optimal priority assignment, determine the maximum interval length until the system will again provide full timing guarantees and explain how we can monitor the system state online. The approaches presented in this paper can also be applied to mixed criticality systems with dual criticality levels. },
}
In many practical real-time systems, the physical environment and the system platform can impose uncertain
execution behaviour to the system. For example, if transient faults are detected, the execution time of a task instance can be increased due to recovery operations. Such fault recovery routines make the system very vulnerable with respect to meeting hard real-time deadlines. In theory and in practical systems, this problem is often handled by aborting not so important tasks to guarantee the response time of the more important tasks. However, for most systems such faults occur rarely and the results of not so important tasks might still be useful, even if they are a bit late. This implicates to not abort these not so important tasks but keep them running even if faults occur, provided that the more important tasks still meet their hard real time properties. In this paper, we present Systems with Dynamic Real-Time Guarantees to model this behaviour and determine if the system can provide full timing guarantees or limited timing guarantees without any online adaptation after a fault occurred. We present a schedulability test, provide an algorithm for optimal priority assignment, determine the maximum interval length until the system will again provide full timing guarantees and explain how we can monitor the system state online. The approaches presented in this paper can also be applied to mixed criticality systems with dual criticality levels.
|
| Jian-Jia Chen, Geoffrey Nelissen and Wen-Hung Kevin Huang.
A Unifying Response Time Analysis Framework for Dynamic Self-Suspending Tasks.
In Euromicro Conference on Real-Time Systems (ECRTS)
Toulouse, France, 05-08, July 2016,
An extended version is available in technical report #850, Technische Universität Dortmund - Fakultät für Informatik
[BibTeX][PDF][Abstract]@inproceedings { ChenECRTS2016-suspension,
author = {Chen, Jian-Jia and Geoffrey Nelissen, and Huang, Wen-Hung Kevin},
title = {A Unifying Response Time Analysis Framework for Dynamic Self-Suspending Tasks},
booktitle = {Euromicro Conference on Real-Time Systems (ECRTS)},
year = {2016},
address = {Toulouse, France},
month = {05-08, July},
note = {
An extended version is available in technical report #850, Technische Universit\"at Dortmund - Fakult\"at f\"ur Informatik},
keywords = {kevin},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2016-chen-ecrts-suspension.pdf},
confidential = {n},
abstract = { For real-time embedded systems, self-suspending behaviors can cause
substantial performance/schedulability degradations. In this paper,
we focus on preemptive fixed-priority scheduling for the dynamic
self-suspension task model on uniprocessor. This
model assumes that a job of a task can dynamically suspend itself during its execution (for instance, to wait for shared resources or access co-processors or external devices).
The total suspension time of a job is upper-bounded, but this dynamic behavior drastically influences the interference generated by this task on lower-priority tasks. The state-of-the-art results for this task model can be classified
into three categories (i) modeling suspension as computation, (ii)
modeling suspension as release jitter, and (iii) modeling suspension as a blocking term.
However, several results associated to the release jitter approach have been recently proven to be erroneous, and the concept of modeling suspension as blocking was never
formally proven correct. This paper presents a unifying
response time analysis framework for the dynamic self-suspending
task model. We provide a rigorous proof and show that the existing analyses pertaining to the three categories mentioned above are analytically dominated by our proposed solution. Therefore, all those techniques are in fact correct, but they are
inferior to the proposed response time analysis in this paper. The
evaluation results show that our analysis framework can generate huge
improvements (an increase of up to $50\%$ of the number of task sets
deemed schedulable) over these state-of-the-art analyses.},
}
For real-time embedded systems, self-suspending behaviors can cause
substantial performance/schedulability degradations. In this paper,
we focus on preemptive fixed-priority scheduling for the dynamic
self-suspension task model on uniprocessor. This
model assumes that a job of a task can dynamically suspend itself during its execution (for instance, to wait for shared resources or access co-processors or external devices).
The total suspension time of a job is upper-bounded, but this dynamic behavior drastically influences the interference generated by this task on lower-priority tasks. The state-of-the-art results for this task model can be classified
into three categories (i) modeling suspension as computation, (ii)
modeling suspension as release jitter, and (iii) modeling suspension as a blocking term.
However, several results associated to the release jitter approach have been recently proven to be erroneous, and the concept of modeling suspension as blocking was never
formally proven correct. This paper presents a unifying
response time analysis framework for the dynamic self-suspending
task model. We provide a rigorous proof and show that the existing analyses pertaining to the three categories mentioned above are analytically dominated by our proposed solution. Therefore, all those techniques are in fact correct, but they are
inferior to the proposed response time analysis in this paper. The
evaluation results show that our analysis framework can generate huge
improvements (an increase of up to $50%$ of the number of task sets
deemed schedulable) over these state-of-the-art analyses.
|
| Matthias Freier and Jian-Jia Chen.
Sporadic Task Handling in Time-Triggered Systems.
In Proceedings of the 19th International Workshop on Software and Compilers for Embedded Systems, {SCOPES} 2016, Sankt Goar, Germany, May 23-25, 2016, pages 135--144
2016
[BibTeX][Link]@inproceedings { DBLP:conf/scopes/FreierC16,
author = {Freier, Matthias and Chen, Jian-Jia},
title = {Sporadic Task Handling in Time-Triggered Systems},
booktitle = {Proceedings of the 19th International Workshop on Software and Compilers for Embedded Systems, {SCOPES} 2016, Sankt Goar, Germany, May 23-25, 2016},
year = {2016},
pages = {135--144},
url = {http://doi.org/10.1145/2906363.2906383},
confidential = {n},
} |
| Georg von der Brüggen, Wen-Hung Huang, Jian-Jia Chen and Cong Liu.
Uniprocessor Scheduling Strategies for Self-Suspending Task Systems.
In Proceedings of the 24th International Conference on Real-Time Networks and Systems (RTNS), pages 119--128
Brest, October 19 - 21 2016
[BibTeX][PDF][Link][Abstract]@inproceedings { vonderBruggen:2016:USS:2997465.2997497,
author = {Br\"uggen, Georg von der and Huang, Wen-Hung and Chen, Jian-Jia and Liu, Cong},
title = {Uniprocessor Scheduling Strategies for Self-Suspending Task Systems},
booktitle = {Proceedings of the 24th International Conference on Real-Time Networks and Systems (RTNS)},
year = {2016},
pages = {119--128},
address = {Brest},
month = {October 19 - 21},
publisher = {ACM},
url = {http://dl.acm.org/ft_gateway.cfm?id=2997497\&ftid=1804918\&dwn=1\&CFID=691780547\&CFTOKEN=64912419},
keywords = {georg, kevin},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2016-rtns-georg.pdf},
confidential = {n},
abstract = {We study uniprocessor scheduling for hard real-time self-suspending task systems where each task may contain a single self-suspension interval. We focus on improving state-of-the-art fixed-relative-deadline (FRD) scheduling approaches, where an FRD scheduler assigns a separate relative deadline to each computation segment of a task. Then, FRD schedules different computation segments by using the earliest deadline first (EDF) scheduling policy, based on the assigned deadlines for the computation segments. Our proposed algorithm, Shortest Execution Interval First Deadline Assignment (SEIFDA), greedily assigns the relative deadlines of the computation segments, starting with the task with the smallest execution interval length, i.e., the period minus the self-suspension time. We show that any reasonable deadline assignment under this strategy has a speedup factor of 3. Moreover, we present how to approximate the schedulability test and a generalized mixed integer linear programming (MILP) that can be formulated based on the tolerable loss in the schedulability test defined by the users. We show by both analysis and experiments that through designing smarter relative deadline assignment policies, the resulting FRD scheduling algorithms yield significantly better performance than existing schedulers for such task systems. },
}
We study uniprocessor scheduling for hard real-time self-suspending task systems where each task may contain a single self-suspension interval. We focus on improving state-of-the-art fixed-relative-deadline (FRD) scheduling approaches, where an FRD scheduler assigns a separate relative deadline to each computation segment of a task. Then, FRD schedules different computation segments by using the earliest deadline first (EDF) scheduling policy, based on the assigned deadlines for the computation segments. Our proposed algorithm, Shortest Execution Interval First Deadline Assignment (SEIFDA), greedily assigns the relative deadlines of the computation segments, starting with the task with the smallest execution interval length, i.e., the period minus the self-suspension time. We show that any reasonable deadline assignment under this strategy has a speedup factor of 3. Moreover, we present how to approximate the schedulability test and a generalized mixed integer linear programming (MILP) that can be formulated based on the tolerable loss in the schedulability test defined by the users. We show by both analysis and experiments that through designing smarter relative deadline assignment policies, the resulting FRD scheduling algorithms yield significantly better performance than existing schedulers for such task systems.
|
| Anas Toma, Santiago Pagani, Jian-Jia Chen, Wolfgang Karl and Jörg Henkel.
An Energy-Efficient Middleware for Computation Offloading in Real-Time Embedded Systems.
In the 22th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2016)
Daegu, South Korea, August 2016.
[BibTeX][PDF][Abstract]@inproceedings { Toma-RTCSA2016,
author = {Toma, Anas and Pagani, Santiago and Chen, Jian-Jia and Karl, Wolfgang and Henkel, J\"org},
title = {An Energy-Efficient Middleware for Computation Offloading in Real-Time Embedded Systems},
booktitle = {the 22th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2016)},
year = {2016.},
address = {Daegu, South Korea},
month = {August},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2016-toma-rtcsa.pdf},
confidential = {n},
abstract = {Embedded systems have limited resources, such as computation capabilities and battery life. The Dynamic Voltage and Frequency Scaling (DVFS) technique is used to save energy by running the processor of the embedded system at low voltage and frequency levels. However, this prolongs the execution time, which may cause potential deadline misses for real-time tasks. In this paper, we propose a general-purpose middleware to reduce the energy consumption in embedded systems without violating the real-time constraints. The algorithms in the middleware adopt the computation offloading concept to reduce the workload on the processor of the embedded system by sending the computation-intensive tasks to a powerful server. The algorithms are further combined with the DVFS technique to find the running frequency (or speed) such that the energy consumption is minimized and the real-time constraints are satisfied. The evaluation shows that our approach reduces the average energy consumption down to nearly 60%, compared to executing all the tasks locally at the maximum processor speed.},
}
Embedded systems have limited resources, such as computation capabilities and battery life. The Dynamic Voltage and Frequency Scaling (DVFS) technique is used to save energy by running the processor of the embedded system at low voltage and frequency levels. However, this prolongs the execution time, which may cause potential deadline misses for real-time tasks. In this paper, we propose a general-purpose middleware to reduce the energy consumption in embedded systems without violating the real-time constraints. The algorithms in the middleware adopt the computation offloading concept to reduce the workload on the processor of the embedded system by sending the computation-intensive tasks to a powerful server. The algorithms are further combined with the DVFS technique to find the running frequency (or speed) such that the energy consumption is minimized and the real-time constraints are satisfied. The evaluation shows that our approach reduces the average energy consumption down to nearly 60%, compared to executing all the tasks locally at the maximum processor speed.
|
| Wen-Hung Huang and Jian-Jia Chen.
Utilization Bounds on Allocating Rate-Monotonic Scheduled Multi-Mode Tasks on Multiprocessor Systems.
In Design Automation Conference (DAC)
Austin, TX, USA, June 05-09 2016
[BibTeX][PDF][Abstract]@inproceedings { HC16a,
author = {Huang, Wen-Hung and Chen, Jian-Jia},
title = {Utilization Bounds on Allocating Rate-Monotonic Scheduled Multi-Mode Tasks on Multiprocessor Systems},
booktitle = {Design Automation Conference (DAC)},
year = {2016},
address = {Austin, TX, USA},
month = {June 05-09 },
keywords = {kevin},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/PID4192127-multimode-mp.pdf},
confidential = {n},
abstract = {Formal models used for representing recurrent real-time pro-
cesses have traditionally been characterized by a collection of
jobs that are released periodically. However, such a model-
ing may result in resource under-utilization in systems whose
behaviors are not entirely periodic. For instance, tasks in
cyber-physical system (CPS) may change their service levels,
e.g., periods and/or execution times, to adapt to the changes
of environments. In this work, we study a model that is a
generalization of the periodic task model, called multi-mode
task model: a task has several modes speci ed with di erent
execution times and periods to switch during runtime, inde-
pendent of other tasks. Moreover, we study the problem
of allocating a set of multi-mode tasks on a homogeneous
multiprocessor system. We present a scheduling algorithm
using any reasonable allocation decreasing (RAD) algorithm
for task allocations for scheduling multi-mode tasks on mul-
tiprocessor systems. We prove that this algorithm achieves
38% utilization for implicit-deadline rate-monotonic (RM)
scheduled multi-mode tasks on multiprocessor systems.},
}
Formal models used for representing recurrent real-time pro-
cesses have traditionally been characterized by a collection of
jobs that are released periodically. However, such a model-
ing may result in resource under-utilization in systems whose
behaviors are not entirely periodic. For instance, tasks in
cyber-physical system (CPS) may change their service levels,
e.g., periods and/or execution times, to adapt to the changes
of environments. In this work, we study a model that is a
generalization of the periodic task model, called multi-mode
task model: a task has several modes speci ed with di erent
execution times and periods to switch during runtime, inde-
pendent of other tasks. Moreover, we study the problem
of allocating a set of multi-mode tasks on a homogeneous
multiprocessor system. We present a scheduling algorithm
using any reasonable allocation decreasing (RAD) algorithm
for task allocations for scheduling multi-mode tasks on mul-
tiprocessor systems. We prove that this algorithm achieves
38% utilization for implicit-deadline rate-monotonic (RM)
scheduled multi-mode tasks on multiprocessor systems.
|
DAES