Schedulability of Fault Tolerant Real Time System Based on Local Optimum Checkpoint Under Priority Mixed Strategy

HE Zhongzheng; MEN Chaoguang; CHEN Yongjun; LI Xiang

doi:10.1049/cje.2015.04.003

Volume 24 Issue 2

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2015 > 24(2): 236-244

HE Zhongzheng, MEN Chaoguang, CHEN Yongjun, LI Xiang. Schedulability of Fault Tolerant Real Time System Based on Local Optimum Checkpoint Under Priority Mixed Strategy[J]. Chinese Journal of Electronics, 2015, 24(2): 236-244. doi: 10.1049/cje.2015.04.003

Citation:

HE Zhongzheng, MEN Chaoguang, CHEN Yongjun, LI Xiang. Schedulability of Fault Tolerant Real Time System Based on Local Optimum Checkpoint Under Priority Mixed Strategy[J]. Chinese Journal of Electronics, 2015, 24(2): 236-244. doi: 10.1049/cje.2015.04.003

Citation:

PDF( 734 KB)

Schedulability of Fault Tolerant Real Time System Based on Local Optimum Checkpoint Under Priority Mixed Strategy

doi: 10.1049/cje.2015.04.003

1.
Department of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China;
2.
China Xinxing Construction and Development General Company, Beijing 100143, China

Funds: This work is supported by the National Natural Science Foundation of China (No.60873138, No.61100004) and the Fundamental Research Funds for the Central Universities (No.HEUCF100607).

More Information

Corresponding author: MEN Chaoguang received the B.S. and Ph.D. degrees in the Department of Computer Science and Technology from Harbin Institute of Technology University, Harbin, China, and the M.S. degree in the Department of Computer Science and Technology from Harbin Engineering University, Harbin, China, where he is currently a professor. His research interests include faulttolerant computing, mobile computing and fault-tolerant scheduling. (Email:menchaoguang@hrbeu.edu.cn)
Publish Date: 2015-04-10

Abstract

Abstract

Against the defect of the real time system fault tolerant model that can only tolerate one fault, the Local optimum checkpoint (LOC) algorithm was proposed. Then according to the schedulability analysis, the worst case response time formula under the fault tolerant priority mixed strategy based on the local optimum checkpoint was deduced. Finally the Fault tolerant priority configuration search algorithm under Mixed strategy based on LOC (FTPCS-MS-LOC) was proposed. The FTPCS-MS-LOC can toleratemultiple transient faults. The algorithm can effectively reduce the search space compared to the enumeration method. The simulation shows that the FTPCS-MSLOC can significantly improve the system fault resilience than the fault tolerant priority inheritance, promotion and demotion strategy, and also the mixed strategy based on the checkpoint interval in the condition of single fault occurred.
- Real-time systems,
- Rollback recovery,
- Fault tolerant priority,
- Schedulability,
- Checkpoint interval

FullText(HTML)

References(22)

References

P. Shivakumar, M. Kistler, S.W. Keckler, et al., “Modeling the effect of technology trends on the soft error rate of combinational logic”, Proc of the Int'1 Conference on Dependable Systems and Networks, Washington, D.C., USA, pp.389-399, 2002.

Fu Zhongchuan, Chen Hongsong, Cui gang, et al., “Processor fault-tolerance technology research and prospect”, Journal ofComputer Research and Development, Vol.44, No.1, pp.154-160, 2007. (in Chinese)

J.F. Ziegler, “Experiments in soft fails in computer electronics (1978-1994)”, IBM Journal Research Development, Vol.40, No.1, pp.3-18, 1996.

J.A. Clark and D.K. Pradhan, “Fault injection: A method for validating computer system dependability”, IEEE Computer, Vol.28, No.6, pp.47-56, 1995.

F. Zhang and A. Burns, “Schedulability analysis for real-time systems with EDF scheduling”, IEEE Transactions on Computers, Vol.58, No.9, pp.1250-1258, 2009.

Wan Jia-fu, Li Di, Ye Feng, et al., “Two-level hierarchical scheduling algorithm to improve certainty of hybrid real-time tasks”, Journal of Jilin University (Engineering and Technology Edition), Vol.39, No.3, pp.753-758, 2009. (in Chinese)

Men Chaoguang, Zuo Decheng and Yang Xiaozong, “A new adaptive checkpointing strategy for mobile computing”, Chinese Journal of Electronics, Vol.14, No.1, pp.15-20, 2005.

A. Burns, S. Punnekkat, L. Stringini, et al., “Probabilistic scheduling guarantees for fault-tolerant real-time systems”, Proc. Seventh Int'l Working Conf. Dependable Computing for Critical Application, San Jose, CA, USA, pp.339-356, 1999.

Paul Pop, Viacheslav Izosimov, Petru Eles, et al., “Design optimization of time-and cost-constrained fault-tolerant embedded systems with checkpointing and replication”, IEEE Transactions on Very Large Scale Intergration Systems, Vol.17, No.3, pp.389-402, 2009.

Seong Woo Kwak and Jung-Min Yang, “Optimal checkpoint placement on real-time tasks with harmonic periods”, Journal of Computer Science and Technology, Vol.27, No.1, pp.105-112, 2012.

F. Liberato, R. Melhem and D. Mosse, “Tolerance to multiple transient faults for aperiodic tasks in hard real-time systems”, IEEE Transactions on Computers, Vol.49, No.9, pp.906-914, 2000.

S. Srinivasan and N.K. Jha, “Hardware-software co-synthesis of fault-tolerant real-time distributed embedded systems”, Proc. of European Design Automation Conference, Brighton, Great Britain, pp.334-339, 1995.

C.C. Han, K.G. Shin and J. Wu, “A fault-tolerant scheduling algorithm for real-time periodic tasks with possible software faults”, IEEE Transactions on Computers, Vol.52, No.3, pp.362-372, 2003.

S. Punnekkat, A. Burns and R. Davis, “Analysis of checkpointing for real-time systems”, Real-Time Systems, Vol.20, No.1, pp.83-102, 2001.

G.M.A. Lima and A. Burns, “An optimal fixed-priority assignment algorithm for supporting fault-tolerant hard real-time systems”, IEEE Transactions on Computers, Vol.52, No.10, pp.1332-1346, 2003.

Li Jun, Yang Fumin and Lu Yansheng, “A feasible schedulability analysis for the fault-tolerant real-time systems”, Journal of Software, Vol.16, No.8, pp.1513-1522, 2005. (in Chinese)

Li Jun, Cao Wanhua, Yang Fumin, et al., “A fault-tolerant priority configuration mixed search algorithmc”, Journal of Computer Research and Development, Vol.44, No.11, pp.1912-1919, 2007. (in Chinese)

Guo Ruifeng, Liu Xian and Ding Wanfu, “Research on realtime scheduling algorithms for rollback recovery fault-tolerance based on priority decrease strategy”, Journal of Electronics & Information Technology, Vol.34, No.2, pp.474-480, 2012. (in Chinese)

Ding Wanfu, Guo Ruifeng, Zhao Jin, et al., “Schedulability analysis for fault-tolerant hard real-time systems based on rollback recovery”, Systems Engineering and Electronics, Vol.33, No.7, pp.1673-1679, 2011. (in Chinese)

Liu Xian, Guo Ruifeng, DingWanfu, “Schedulability of rollback recovery fault-tolerant real-time system based on priority mixed strategy”, Journal of Jilin University (Engineering and Technology Edition), Vol.42, No.5, pp.1243-1250, 2012. (in Chinese)

L.C. Liu and J.W. Layland, “Scheduling algorithms for multiprogramming in a hard real-time environment”, Journal of the ACM, Vol.20, No.1, pp.46-61, 1973.

N.C. Audsley, A. Burns and A.J. Wellings, “Deadline monotonic scheduling theory and application”, Control Engineering Practice, Vol.1, No.1, pp.71-78, 1993.

Relative Articles

Supplements(0)

Cited By

Proportional views