Notification: Our email services are now fully restored after a brief, temporary outage caused by a denial-of-service (DoS) attack. If you sent an email on Dec 6 and haven't received a response, please resend your email.
CFP last date
20 December 2024
Reseach Article

Reliability-Driven Fault Tolerant Scheduling Heuristics for Distributed Embedded Real-Time Systems

by Salim Kalla, Hamoudi Kalla, Chafik Arar
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 36 - Number 5
Year of Publication: 2011
Authors: Salim Kalla, Hamoudi Kalla, Chafik Arar
10.5120/4485-6311

Salim Kalla, Hamoudi Kalla, Chafik Arar . Reliability-Driven Fault Tolerant Scheduling Heuristics for Distributed Embedded Real-Time Systems. International Journal of Computer Applications. 36, 5 ( December 2011), 5-11. DOI=10.5120/4485-6311

@article{ 10.5120/4485-6311,
author = { Salim Kalla, Hamoudi Kalla, Chafik Arar },
title = { Reliability-Driven Fault Tolerant Scheduling Heuristics for Distributed Embedded Real-Time Systems },
journal = { International Journal of Computer Applications },
issue_date = { December 2011 },
volume = { 36 },
number = { 5 },
month = { December },
year = { 2011 },
issn = { 0975-8887 },
pages = { 5-11 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume36/number5/4485-6311/ },
doi = { 10.5120/4485-6311 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:22:20.934388+05:30
%A Salim Kalla
%A Hamoudi Kalla
%A Chafik Arar
%T Reliability-Driven Fault Tolerant Scheduling Heuristics for Distributed Embedded Real-Time Systems
%J International Journal of Computer Applications
%@ 0975-8887
%V 36
%N 5
%P 5-11
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
Abstract

We present a new scheduling approach to produce automatically a fault tolerant distributed schedule for critical distributed and real-time embedded systems. The approach that we propose take as input a set of operations (tasks), a target distributed architecture, some distribution constraints, some indications on the execution times of the operations on the processors of the target architecture, some indications on the communication times of the data-dependencies on the media communications of the target architecture, and the reliability of processors. IT produces a fault-tolerant distributed and static scheduling of the operations on the architecture, with an indication whether or not the real-time constraints are satisfied. The scheduling approach that we propose for architectures with multiple processors linked by a set of channels (links), consist of a list scheduling heuristic based on active replication strategy. In order to reduce the probability of fault occurrence, the replication process of each operation is based on a Global System Failure Rate (GSFR) objective function. Finally, simulation results show the performance of our approach.

References
  1. Rushby, J. Critical System Properties: Survey and Taxonomy Reliability Engineering and Systems Safety, 1994, 43, 189-219
  2. Suri, N. & Ramamritham, K. Editorial: Special Section on Dependable Real-Time Systems IEEE Trans. on Parallel and Distributed Systems, 1999, 10, 529-531
  3. Avizienis, A.; Laprie, J. & Randell, B. Fundamental Concepts in Dependability 3rd IEEE Information Survivability Workshop, ISW'00, 2000, 7-12
  4. Jalote, P. Fault-Tolerance in Distributed Systems Prentice-Hall, 1994
  5. Kopetz, H. & Bauer, G. The Time-Triggered Architecture Proceedings of the IEEE, 2003, 91, 112-126
  6. Torres-Pomales, W. Software Fault Tolerance: a Tutorial 2000
  7. Girault, A. & Kalla, H. A Novel Bicriteria Scheduling Heuristics Providing a Guaranteed Global System Failure Rate IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, 2009, 6, 241-254
  8. Assayad, I.; Girault, A. & Kalla, H. A Bi-Criteria Scheduling Heuristics for Distributed Embedded Systems Under Reliability and Real-Time Constraints International Conference on Dependable Systems and Networks, DSN'04, IEEE, 2004, 347-356
  9. Girault, A.; Kalla, H.; Sighireanu, M. & Sorel, Y. An Algorithm for Automatically Obtaining Distributed and Fault-Tolerant Static Schedules International Conference on Dependable Systems and Networks, DSN'03, IEEE, 2003
  10. Chen, H.; Luo, W.; Wang, W. & Xiang;, J. A novel real-time fault-tolerant scheduling algorithm based on distributed control systems International Conference on Computer Science and Service System, 2011
  11. Chen, J.; Yang, C.; Kuo, T. & Tseng;, S. Real-Time Task Replication for Fault Tolerance in Identical Multiprocessor Systems 13th IEEE Symposium on Real Time and Embedded Technology and Applications, 2007
  12. Gan, J.; Gruian, F.; Pop, P. & Madsen, J. Energy/reliability trade-offs in fault-tolerant event-triggered distributed embedded systems 16th Asia and South Pacific on Design Automation Conference, 2011
  13. Jinyong, Y.; Hanguang, S.; Li, Y. & Qiangqiang, C. A Real-time Fault-tolerant Scheduling Algorithm for Software/Hardware Hybrid Tasks International Conference on Mechatronic Science, Electric Engineering and Computer, 2011
  14. Dogan, A. & Özgüner, F. Matching and Scheduling Algorithms for Minimizing Execution Time and Failure Probability of Applications in Heterogeneous Computing IEEE Trans. on Parallel and Distributed Systems, 2002, 13, 308-323
  15. Sih, G. & Lee, E. A Compile-Time Scheduling Heuristic for Interconnection Constraint Heterogeneous Processor Architectures IEEE Trans. on Parallel and Distributed Systems, 1993, 4, 175-187
  16. Hashimoto, K.; Tsuchiya, T. & Kikuno, T. Effective Scheduling of Duplicated Tasks for Fault-Tolerance in Multiprocessor Systems IEICE Trans. on Information and Systems, 2002, E85-D, 525-534
  17. Ahn, K.; Kim, J. & Hong, S. Fault-Tolerant Real-Time Scheduling using Passive Replicas Pacific Rim International Symposium on Fault-Tolerant Systems, PRFTS'97, 1997
  18. Qin, X.; Jiang, H. & Swanson, D. An Efficient Fault-tolerant Scheduling Algorithm for Real-time Tasks with Precedence Constraints in Heterogeneous Systems International Conference on Parallel Processing, ICPP'02, 2002, 360-386
  19. Gummadi, K.; Pradeep, M. & Murthy, C. R. An Efficient Primary-Segmented Backup Scheme for Dependable Real-Time Communication in Multihop Networks IEEE/ACM Trans. on Networking, 2003, 11
  20. Dima, C.; Girault, A.; Lavarenne, C. & Sorel, Y. Off-Line Real-Time Fault-Tolerant Scheduling 9th Euromicro Workshop on Parallel and Distributed Processing, PDP'01, 2001, 410-417
  21. Pinello, C.; Carloni, L. & Sangiovanni-Vincentelli, A. Fault-Tolerant Deployment of Embedded Software for Cost-Sensitive Real-Time Feedback-Control Applications Design, Automation and Test in Europe, DATE'04, IEEE, 2004
  22. Girault, A.; Kalla, H. & Sorel, Y. Transient Processor/Bus Fault Tolerance for Embedded Systems IFIP Working Conference on Distributed and Parallel Embedded Systems, DIPES'06, Springer, 2006, 135-144
  23. Girault, A.; Kalla, H. & Sorel, Y. A Scheduling Heuristics for Distributed Real-Time Embedded Systems Tolerant to Processor and Communication Media Failures International Journal of Production Research, 2004, 42, 2877-2898
  24. Girault, A.; Kalla, H. & Sorel, Y. An Active Replication Scheme that Tolerates Failures in Distributed Embedded Real-Time Systems IFIP Working Conference on Distributed and Parallel Embedded Systems, DIPES'04, Kluwer Academic Publishers, 2004
  25. Shatz, S.; Wang, J. & Goto, M. Task Allocation for Maximizing Reliability of Distributed Computer Systems IEEE Trans. on Computers, 1992, 41, 1156-1168
  26. Grandpierre, T. & Sorel, Y. From Algorithm and Architecture Specifications to Automatic Generation of Distributed Real-Time Executives: A Seamless Flow of Graphs Transformations International Conference on Formal Methods and Models for Codesign, MEMOCODE'03, IEEE, 2003.
Index Terms

Computer Science
Information Sciences

Keywords

Embedded systems Distributed systems Real-time systems Fault tolerance Transient faults Reliability Scheduling heuristics Active replication