Checkpointing and the Modeling of Program Execution Time

摘要

Checkpointing is a commonly used technique for reducing the execution time oflong-running programs in the presence of failures. With checkpointing, the status of the program under execution is saved intermittently. Upon the occurrence of a failure, the program execution is restarted from the most recent checkpoint rather than from the beginning. Due to its overhead, checkpointing may not always be beneficial, and, if it is, an optimal checkpointing strategy may be determined so as to minimize the expected execution time or to maximize the probability of the execution time not exceeding a critical limit. The paper considers several models of checkpointing and recovery in a program in order to derive the distribution of program execution time or its expectation. It makes important extensions to some existing results as well as introduces and analyzes new models. It is shown that the expected execution time increases linearly (exponentially) with the processing requirement in the presence (absence) of checkpointing. Furthermore, these models can be used to compare different checkpointing strategies and to determine an optimal interval between checkpoints.