Linux Support for Transparent Checkpointing of Multithreaded Programs
Christopher D. Carothers, Boleslaw Karol Szymanski · 2007
The most common use of checkpointing is in fault tolerant computing where the goal is to minimize loss of CPU cycles when a long executing program crashes before completion. By checkpointing a program’s state at regular intervals, the amount of lost computation is limited to the interval from the last checkpoint to the time of crash. Research in this class of checkpoint algorithms and systems has been ongoing for at least last 15 years. Our interest here is on the fast, efficient checkpointing of threaded programs that execute on shared-memory computing platforms. We are motivated by problems that arose in our investigation of new parallel simulation and computation synchronization methodologies. There are two paradigms in which the ability to checkpoint (save the state of the computation) quickly is crucial. One is the speculative execution of a portion of code that otherwise would be suspended by synchronization. For example, consider a program reading an object mirrored on the local site. If this object changes infrequently, then instead of waiting verify the validity of the local copy, the program can checkpoint and then speculatively read the object. If the local copy is invalid, the executing copy of the program can be killed, and the copy with pre-reading state executed. The amount of time saved by not waiting to verify the validity of a local object copy defines the gain of the speculative execution. In general, let p be a probability that the speculation is unsuccessful and would require rolling back the computation to the speculation point. Let r denote the cost of such a rollback and s the saving resulting from elimination of waiting for synchronization when speculation is successful. Finally, let so be the cost of speculation, (mainly the cost of checkpointing, incurred regardless of the outcome of the speculation). Under this assumptions, speculation is beneficial when: s > o + r p or, equivalently p < ( s o)= r: