The week's pick
Reseach Article
Reliability-Driven Fault Tolerant Scheduling Heuristics for Distributed Embedded Real-Time Systems
| 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
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
- Rushby, J. Critical System Properties: Survey and Taxonomy Reliability Engineering and Systems Safety, 1994, 43, 189-219
- Suri, N. & Ramamritham, K. Editorial: Special Section on Dependable Real-Time Systems IEEE Trans. on Parallel and Distributed Systems, 1999, 10, 529-531
- Avizienis, A.; Laprie, J. & Randell, B. Fundamental Concepts in Dependability 3rd IEEE Information Survivability Workshop, ISW'00, 2000, 7-12
- Jalote, P. Fault-Tolerance in Distributed Systems Prentice-Hall, 1994
- Kopetz, H. & Bauer, G. The Time-Triggered Architecture Proceedings of the IEEE, 2003, 91, 112-126
- Torres-Pomales, W. Software Fault Tolerance: a Tutorial 2000
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Shatz, S.; Wang, J. & Goto, M. Task Allocation for Maximizing Reliability of Distributed Computer Systems IEEE Trans. on Computers, 1992, 41, 1156-1168
- 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
Keywords