The Transactions of the Korean Institute of Electrical Engineers D (대한전기학회논문지:시스템및제어부문D)

The Korean Institute of Electrical Engineers (대한전기학회)
권호 표지

Checkpoint Placement for Multiple Real-time Periodic Tasks with Hard Deadlines

하드 데드라인을 가지는 다중 실시간 주기적 태스크에서의 체크포인팅 기법

  • Published : 2004.08.01
Download PDF
⟨ Previous Next ⟩

Abstract

We analyze checkpoint strategy for multiple real-time periodic tasks with hard deadlines. Real-time tasks usually have deadlines associated with them. For multiple real-time tasks, checkpoint strategy considering deadlines of all tasks is very difficult to derive. We analyze the problem of checkpoint placement for such multiple periodic tasks. In our strategy, the interval between checkpoints is determined for each task considering its deadline. An approximated failure probability over a specified interval is derived. Then the number of checkpoints for each task is selected to minimize the approximated failure probability. To show the usefulness of our strategy, error bound between the exact and the approximated failure probability is estimated, which is revealed to be quite small.

Keywords

References

  1. C. M. Krishna and A. D. Singh, 'Optimal configuration of redundant real-time systems in the face of correlated failure,' IEEE Trans. on Reliability, vol. 44, pp. 587-594. Dec. 1995 https://doi.org/10.1109/24.475977
  2. Seong Woo Kwak and Byung Kook Kim, 'Task Scheduling Strategies for Reliable TMR Controllersusing Task Grouping and Assignment', IEEE Tr. Reliability, vol. 49, no. 4, pp. 355-362, Dec. 2000 https://doi.org/10.1109/24.922488
  3. C. M. Krishina and Kang G. Shin, Real-Time Systems, New York: McGraw-Hill, 1997
  4. D. P. Siewiorek and R. S. Swarz, Reliable Computer Systems, Digital Press, 1992
  5. Avi Ziv and Jehoshua Bruck, 'An on-line algorithm for checkpoint placement,' IEEE Trans. on Computers, vol. 46, pp. 976-984, Sep. 1997 https://doi.org/10.1109/12.620479
  6. R. Geist, R. Reynolds and J. Westall, 'Selection of a checkpoint interval in a critical-task environment,' IEEE Trans. on Reliability, vol. 37, pp. 395-400, Oct. 1988 https://doi.org/10.1109/24.9847
  7. Kang G. Shin, Tein-Hsiang Lin, and Yann-Hang Lee, 'Optimal checkpointing of real-time tasks,' IEEE Trans. on Computers, vol. C-36, pp. 1328-1341, Nov. 1987 https://doi.org/10.1109/TC.1987.5009472
  8. C. M. Krishna and A. D. Singh, 'Reliability of checkpointed real-time systems using time redundancy,' IEEE Trans. on Reliability, vol. 42, pp. 427-435, Sep. 1993 https://doi.org/10.1109/24.257826
  9. Seong Woo Kwak, Byung Jae Choi and Byung Kook Kim, 'Optimal Checkpointing Strategy for Real-Time Control Systems under Faults with Exponential Duration', IEEE Tr. Reliability, vol. 50, no. 3, pp. 293-301, Sep. 2001 https://doi.org/10.1109/24.974127
  10. Seong Woo, Kwak, 'Reliability Analysis and Design of Real-time Fault Tolerant Control Systems under Transient Faults', Ph.D thesis, KAIST, 2000
  11. John W. Young, 'A first order approximation to the optimal checkpoint intervals,' Comm. of the ACM, vol. 17, pp.530-531, Nov. 1974 https://doi.org/10.1145/361147.361115
  12. Hagbae Kim and Kang G. Shin, 'Modeling of externally-induced/common-cause faults in faulttolerant systems,' IEEE/AIAA Digital Avionics System Conference, pp. 402-407, Oct. 1994 https://doi.org/10.1109/DASC.1994.369450