The freeze free algorithm for process migration
E.T. Roush · 1995
Dynamic process migration moves a running process to a new machine, and supports both load sharing and processor fault tolerance. This thesis introduces the {\sl Freeze Free} process migration algorithm, which uses the following six techniques to dramatically reduce the overhead and complexity of dynamic process migration. First, existing systems use request and response messages to initiate process migrations and transfer some elements of the process state. The {\sl Freeze Free} algorithm eliminates all request and response messages from the process migration latency period. The combined process control and execution state message implicitly signals the start of a process migration. The current stack page message implicitly tells the new host to resume execution. The old host blasts the combined process control and execution state, the current code page, the current heap page, and the current stack page to the new host without delay during the latency period. This information can not be further reduced and support process migration for a broad class of processes. Second, the {\sl Freeze Free} algorithm delivers the first critical pages without page faults. The program counter identifies the current code page, and the stack pointer identifies the current stack page. A heuristic identifies the current heap page by examining the instruction stream. The system truncates the top stack page to the portion currently in use. Third, the {\sl Freeze Free} design separates process control and communication state, which allows process migration and message receipt to proceed in parallel. The new design effectively eliminates the message freeze time, which plagued prior systems. Fourth, the {\sl Freeze Free} design separates process control and file state, which allows the process to resume execution on the new host, while the system flushes data to the file server. Fifth, the {\sl Freeze Free} algorithm preallocates and partially initializes a set of data structures for use at process migration time, which moves expensive operations out of the critical path. Sixth, the {\sl Freeze Free} design reorganizes data structures so that information about an object appears only within that same object. This drastically reduces the cost of extracting and inserting state. The net result of these techniques is a reduction in the process migration latency time by an order of magnitude, while simultaneously supporting processor fault tolerance and effectively eliminating message freeze times. Furthermore the latency cost does not change with process size. The latency time is 13.9ms on a 4kB page system, 20.8ms on an 8kB page system, and 36.9ms on a 16kB system. This thesis shows that process migration latency costs are now a small fraction of the demand page operations across the network. The analysis also reveals further potentially large savings in both process migration latency and cross network demand paging. The thesis demonstrates the negative impact of increasing