Probabilistic optimisation of checkpoint intervals for real-time multi-tasks. (English) Zbl 1276.93085
Summary: This article considers the checkpoint placement problem for real-time systems. In our environment, multiple real-time tasks with arbitrary periods are scheduled in the system by the rate monotonic algorithm, and checkpoints are inserted at a constant interval in each task while the width of the interval is different with respect to the task. We derive an explicit formula of the probability that all the tasks are successfully completed with a given set of checkpoint intervals. Then we determine the optimal checkpoint intervals that maximise the probability of task completion. The probability computation includes the schedulability analysis with respect to the numbers of re-executed checkpoint intervals. Our method does not necessitate any algebraic condition on the periods of the scheduled tasks.
Keywords:
checkpointing; fault-tolerance; checkpoint intervals; rate monotonic algorithm; arbitrary periodsReferences:
| [1] | Baldoni R, International Journal of Systems Science 28 pp 1145– (1997) · Zbl 0897.68007 · doi:10.1080/00207729708929474 |
| [2] | Biswas S, International Journal of Systems Science 41 pp 763– (2010) · Zbl 1200.93097 · doi:10.1080/00207720903244089 |
| [3] | Chen N, in Proceedings of International Conference on Embedded Software and Systems pp 315– (2009) |
| [4] | He X, International Journal of Systems Science 41 pp 937– (2010) · Zbl 1213.93123 · doi:10.1080/00207720902974744 |
| [5] | Kim BK, International Journal of Systems Science 30 pp 123– (1999) · Zbl 1065.93536 · doi:10.1080/002077299292740 |
| [6] | Kim JK, Real-Time Systems 26 pp 199– (2004) · Zbl 1101.68417 · doi:10.1023/B:TIME.0000016130.91111.75 |
| [7] | Krishina CM, Real-time Systems (1997) |
| [8] | Kwak , SW , Choi , BJ and Kim , BK . 2000 . Checkpointing Strategy for Multiple Real-time Tasks . Proceedings of 7th International Conference on Real-Time Computing Systems and Applications (RTCSA’00) . 2000 . pp. 517 – 521 . · doi:10.1109/RTCSA.2000.896436 |
| [9] | Ling Y, IEEE Transactions on Computers 50 pp 699– (2001) · doi:10.1109/12.936236 |
| [10] | Liu JWS, Real-time Systems (2000) |
| [11] | Mossé D, IEEE Transactions on Software Engineering 29 pp 752– (2003) · doi:10.1109/TSE.2003.1223648 |
| [12] | Ouyang J, International Journal of Systems Science 28 pp 945– (1997) · Zbl 1114.68329 · doi:10.1080/00207729708929459 |
| [13] | Ozaki T, IEEE Transactions on Dependable and Secure Computing 3 pp 130– (2006) · doi:10.1109/TDSC.2006.22 |
| [14] | Punnekkat S, International Journal of Time-Critical Computing Systems 20 pp 83– (2001) |
| [15] | Simon D, International Journal of Systems Science 36 pp 57– (2005) · Zbl 1068.93041 · doi:10.1080/00207720412331330408 |
| [16] | Song CY, International Journal of Systems Science 40 pp 479– (2009) · Zbl 1172.93374 · doi:10.1080/00207720802692248 |
| [17] | Tantawi A, ACM Transactions on Computer Systems 2 pp 123– (1984) · doi:10.1145/190.357398 |
| [18] | Tia TS, Ph.D. dissertation (1995) |
| [19] | Young JW, Communcations of ACM 17 pp 530– (1974) · Zbl 0294.68008 · doi:10.1145/361147.361115 |
| [20] | Ziv A, IEEE Transactions on Computers 46 pp 976– (1997) · doi:10.1109/12.620479 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
