research-article

Scheduling of fault-tolerant embedded systems with soft and hard timing constraints

Authors:

Viacheslav Izosimov,

Zebo PengAuthors Info & Claims

DATE '08: Proceedings of the conference on Design, automation and test in Europe

Pages 915 - 920

https://doi.org/10.1145/1403375.1403596

Published: 10 March 2008 Publication History

Abstract

In this paper we present an approach to the synthesis of fault-tolerant schedules for embedded applications with soft and hard real-time constraints. We are interested to guarantee the deadlines for the hard processes even in the case of faults, while maximizing the overall utility. We use time/utility functions to capture the utility of soft processes. Process re-execution is employed to recover from multiple faults. A single static schedule computed off-line is not fault tolerant and is pessimistic in terms of utility, while a purely online approach, which computes a new schedule every time a process fails or completes, incurs an unacceptable overhead. Thus, we use a quasi-static scheduling strategy, where a set of schedules is synthesized off-line and, at run time, the scheduler will select the right schedule based on the occurrence of faults and the actual execution times of processes. The proposed schedule synthesis heuristics have been evaluated using extensive experiments.

References

[1]

H. Aydin, R. Melhem, and D. Mosse, "Tolerating Faults while Maximizing Reward", 12^th Euromicro Conf. on RTS, 219--226, 2000.

Digital Library

[2]

G. Buttazzo and F. Sensini, "Optimal Deadline Assignment for Scheduling Soft Aperiodic Tasks in Hard Real-Time Environments", IEEE Trans. on Computers, 48(10), 1035--1052, 1999.

Digital Library

[3]

L. A. Cortes, P. Eles, and Z. Peng, "Quasi-Static Scheduling for Real-Time Systems with Hard and Soft Tasks", DATE Conf., 1176--1181, 2004.

Digital Library

[4]

R. I. Davis, K. W. Tindell, and A. Burns, "Scheduling Slack Time in Fixed Priority Pre-emptive Systems", RTSS, 222--231, 1993.

[5]

C. Dima, A. Girault, C. Lavarenne, and Y. Sorel, "Off-line Real-Time Fault-Tolerant Scheduling", Euromicro Parallel and Distributed Processing Workshop, 410--417, 2001.

[6]

C. C. Han, K. G. Shin, and J. Wu, "A Fault-Tolerant Scheduling Algorithm for Real-Time Periodic Tasks with Possible Software Faults", IEEE Trans. on Computers, 52(3), 362--372, 2003.

Digital Library

[7]

V. Izosimov, P. Pop, P. Eles, and Z. Peng, "Design Optimization of Time- and Cost-Constrained Fault-Tolerant Distributed Embedded Systems", DATE Conf., 864--869, 2005.

Digital Library

[8]

V. Izosimov, "Scheduling and Optimization of Fault-Tolerant Embedded Systems", Licentiate Thesis No. 1277, Dept. of Computer and Information Science, Linköping University, 2006.

[9]

N. Kandasamy, J. P. Hayes, and B. T. Murray, "Transparent Recovery from Intermittent Faults in Time-Triggered Distributed Systems", IEEE Trans. on Computers, 52(2), 113--125, 2003.

Digital Library

[10]

H. Kopetz, "Real-Time Systems - Design Principles for Distributed Embedded Applications", Kluwer Academic Publishers, 1997.

Digital Library

[11]

F. Liberato, R. Melhem, and D. Mosse, "Tolerance to Multiple Transient Faults for Aperiodic Tasks in Hard Real-Time Systems", IEEE Trans. on Computers, 49(9), 906--914, 2000.

Digital Library

[12]

P. M. Melliar-Smith, L. E. Moser, V. Kalogeraki, and P. Narasimhan, "Realize: Resource Management for Soft Real-Time Distributed Systems", DARPA Information Survivability Conf., 1, 281--293, 2000.

[13]

C. Pinello, L. P. Carloni, A. L. Sangiovanni-Vincentelli, "Fault-Tolerant Deployment of Embedded Software for Cost-Sensitive Real-Time Feedback-Control Applications", DATE, 1164--1169, 2004.

Digital Library

[14]

Wang Fuxing, K. Ramamritham, and J. A. Stankovic, "Determining Redundancy Levels for Fault Tolerant Real-Time Systems", IEEE Trans. on Computers, 44(2), 292--301, 1995.

Digital Library

[15]

Y. Xie, L. Li, M. Kandemir, N. Vijaykrishnan, and M. J. Irwin, "Reliability-Aware Co-synthesis for Embedded Systems", Proc. 15^th IEEE Intl. Conf. on Appl.-Spec. Syst., Arch. and Proc., 41--50, 2004.

Digital Library

[16]

Ying Zhang and K. Chakrabarty, "A Unified Approach for Fault Tolerance and Dynamic Power Management in Fixed-Priority Real-Time Embedded Systems", IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 25(1), 111--125, 2006.

Digital Library

Cited By

Ranjbar BEjlali AKumar ARanjbar BEjlali AKumar A(2023)Fault-Tolerance- and Power-Aware Multi-core Mixed-Criticality System DesignQuality-of-Service Aware Design and Management of Embedded Mixed-Criticality Systems10.1007/978-3-031-38960-3_6(127-156)Online publication date: 24-Jul-2023
https://doi.org/10.1007/978-3-031-38960-3_6
Ranjbar BEjlali AKumar ARanjbar BEjlali AKumar A(2023)Preliminaries and Related WorkQuality-of-Service Aware Design and Management of Embedded Mixed-Criticality Systems10.1007/978-3-031-38960-3_2(17-36)Online publication date: 24-Jul-2023
https://doi.org/10.1007/978-3-031-38960-3_2
Kada BKalla H(2019)An Efficient Fault-Tolerant Scheduling Approach with Energy Minimization for Hard Real-Time Embedded SystemsCybernetics and Information Technologies10.2478/cait-2019-003519:4(45-60)Online publication date: 1-Nov-2019
https://dl.acm.org/doi/10.2478/cait-2019-0035
Show More Cited By

Index Terms

Scheduling of fault-tolerant embedded systems with soft and hard timing constraints
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Embedded systems
2. Software and its engineering
  1. Software organization and properties

Recommendations

Fault-Tolerant Scheduling

We study fault-tolerant multiprocessor scheduling under the realistic assumption that the occurrence of faults cannot be predicted. The goal in these problems is to minimize the delay incurred by the jobs. Since this is an online problem we use ...
Preference-oriented real-time scheduling and its application in fault-tolerant systems

Investigate the preference-oriented executions for real-time tasks.Propose two optimal preference-oriented (PO) scheduling algorithms.Explore the application of PO scheduling algorithms for fault tolerant systems.PO scheduling algorithms can effectively ...
An Efficient Fault-Tolerant Scheduling Approach with Energy Minimization for Hard Real-Time Embedded Systems
Abstract
In this paper, we focus on two major problems in hard real-time embedded systems fault tolerance and energy minimization. Fault tolerance is achieved via both checkpointing technique and active replication strategy to tolerate multiple transient ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DATE '08: Proceedings of the conference on Design, automation and test in Europe

March 2008

1575 pages

ISBN:9783981080131

DOI:10.1145/1403375

General Chair:
Donatella Sciuto
Politecnico di Milano, Italy

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

The EDA Consortium
EDAA: European Design Automation Association
ECSI
SIGDA: ACM Special Interest Group on Design Automation
The IEEE Computer Society TTTC
IEEE Council on Electronic Design Automation (CEDA)
The Russian Academy of Sciences: The Russian Academy of Sciences

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 March 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

DATE '08

Sponsor:

EDAA
SIGDA
The Russian Academy of Sciences

DATE '08: Design, Automation and Test in Europe

March 10 - 14, 2008

Munich, Germany

Acceptance Rates

Overall Acceptance Rate 518 of 1,794 submissions, 29%

Upcoming Conference

DATE '25

Sponsor:
sigda

Design, Automation and Test in Europe

March 31 - April 2, 2025

Lyon , France

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
303
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ranjbar BEjlali AKumar ARanjbar BEjlali AKumar A(2023)Fault-Tolerance- and Power-Aware Multi-core Mixed-Criticality System DesignQuality-of-Service Aware Design and Management of Embedded Mixed-Criticality Systems10.1007/978-3-031-38960-3_6(127-156)Online publication date: 24-Jul-2023
https://doi.org/10.1007/978-3-031-38960-3_6
Ranjbar BEjlali AKumar ARanjbar BEjlali AKumar A(2023)Preliminaries and Related WorkQuality-of-Service Aware Design and Management of Embedded Mixed-Criticality Systems10.1007/978-3-031-38960-3_2(17-36)Online publication date: 24-Jul-2023
https://doi.org/10.1007/978-3-031-38960-3_2
Kada BKalla H(2019)An Efficient Fault-Tolerant Scheduling Approach with Energy Minimization for Hard Real-Time Embedded SystemsCybernetics and Information Technologies10.2478/cait-2019-003519:4(45-60)Online publication date: 1-Nov-2019
https://dl.acm.org/doi/10.2478/cait-2019-0035
Pozo FRodriguez-Navas G(2019)A Semi-Distributed Self-Healing Protocol for Run-Time Repairs of Time-Triggered Schedules2019 24th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA)10.1109/ETFA.2019.8868969(1399-1402)Online publication date: Sep-2019
https://doi.org/10.1109/ETFA.2019.8868969
Bordel BAlcarria RJara A(2017)Process execution in humanized Cyber-physical systems: Soft processes2017 12th Iberian Conference on Information Systems and Technologies (CISTI)10.23919/CISTI.2017.7975901(1-7)Online publication date: Jun-2017
https://doi.org/10.23919/CISTI.2017.7975901
Nikolov DLarsson E(2016)Optimizing the Level of Confidence for Multiple JobsIEEE Transactions on Computers10.1109/TC.2015.243925465:4(1239-1252)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1109/TC.2015.2439254
Tămaş-Selicean DPop P(2015)Design Optimization of Mixed-Criticality Real-Time Embedded SystemsACM Transactions on Embedded Computing Systems10.1145/270010314:3(1-29)Online publication date: 30-Apr-2015
https://dl.acm.org/doi/10.1145/2700103
Kumar AAlam B(2015)Real-Time Fault Tolerance Task Scheduling Algorithm with Minimum Energy ConsumptionProceedings of the Second International Conference on Computer and Communication Technologies10.1007/978-81-322-2523-2_42(441-448)Online publication date: 4-Sep-2015
https://doi.org/10.1007/978-81-322-2523-2_42
Bagheri MJervan G(2014)Fault-Tolerant Scheduling of Mixed-Critical Applications on Multi-processor PlatformsProceedings of the 2014 12th IEEE International Conference on Embedded and Ubiquitous Computing10.1109/EUC.2014.13(25-32)Online publication date: 26-Aug-2014
https://dl.acm.org/doi/10.1109/EUC.2014.13
Mottaghi MZarandi H(2014)DFTSMicroprocessors & Microsystems10.1016/j.micpro.2013.11.01338:1(88-97)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1016/j.micpro.2013.11.013
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents