Studies on Optimal Checkpoint Intervals for Computer Systems

Abstract

Computer systems have been required to operate normally and effectively, and also hold high reliability as communication and information systems have been developed and complicated. However, some errors often occur due to noises, human errors, software bugs, hardware faults, computer viruses, and so on, and lastly, they might become faults and incur system failures. To protect such faults, various kinds of fault tolerant techniques such as the redundancy of processors and memories and the configurations of systems have been provided. The high reliability and effective performance of real systems can be achieved by the use of redundant techniques in reliability theory. Some faults due to errors may be detected after some time has passed. A system consistency that may be lost by some faults should be restored by some recovery techniques. The operation of taking copies of the normal state of the system is called checkpoint. When faults have been occurred, the process goes back to the nearest checkpoint time by rollback operation, and its re-execution is made, using a consistent state stored in the checkpoint time. An initial chapter gives the introduction which is constructed by redundant techniques for improving reliability and achieving fault tolerance, failure detection and recovery methods and the organization of Thesis. Chapter 2 proposes the checking model where the backup is carried out until the latest checking time when some failure was detected. The expected cost is obtained by using the inspection policy in reliability theory and optimal policies, which minimize it for two cases of periodic and sequential checking times, are derived. Chapters 3 to 7 consider several checkpoint models when an original execution time of one process or task is given, and discuss when and how to generate checkpoints to reduce the total overhead of processes: Chapter 3 proposes two-level recovery schemes of soft and hard checkpoints, and derives an optimal interval of soft checkpoint between hard checkpoints. Chapter 4 adopts multiple modular redundant systems as the recovery techniques of error detection and error masking, and derives optimal checkpoint intervals. Chapter 5 considers the modified checkpoint model in Chapter 4 where checkpoints are placed at sequential times and error rates increase with the number of checkpoints and with an original execution time. It is supported in Chapters 6 that tasks with random processing times are executed, successively, and two types of checkpoints are placed at the end of tasks. Three schemes are considered and are compared numerically. Chapter 7 proposes the extended checkpoint model where error rates increase with the number of checkpoints as shown in Chapter 5 . The numerical examples are given in each ehapter to understand the results easily.The results are summarized in the end of thesis and future studies are described.