Attacking the Process Migration Bottleneck Edward R. Zayas Computer Science Departrnent Carnegie Mellon University Pittsburgh, PA 15213 (Currently at the Information Technology Center, Carnegie Mellon University) Abstract Moving the contents of a large virtual address space stands out as the bottleneck in process migration, dominating all other costs and growing with the size of the program. Copy- on-reference shipment is shown to successfully attack this problem in the Accent distributed computing environment. Logical memory transfers at migration time with individual on-demand page fetches during remote execution allows relocations to occur up to one thousand times faster than with standard techniques. While the amount of allocated memory varies by four orders of magnitude across the processes studied, their transfer times are practically constant. The number of bytes exchanged between machines as a result of migration and remote execution drops by an average of 58% in the representative processes studied, and message-handling costs are cut by over 47% on average. The assumption that processes touch a relatively small part of their memory while executing is shown to be correct, helping to account for these figures. Accent's copy-on-reference facility can be used by any application wishing to take advantage of lazy shipment of data. 1. Introduction Process migration is a valuable resource management tool in a distributed computing environment. However, very few migration facilities exist for such systems. Part of the problem lies in providing an efficient method for naming resources that is completely independent of their location. The major difficulty, though, is the cost of transferring a computation's context from one system node to another. This context, which consists primarily of the process virtual ad- dress space, is typically large in proportion to the usable bandwidth of the interconnection medium. Moving the con- tents of a large virtual address space thus stands out as the bottleneck in process migration, dominating all other costs. As programs continue to grow, the cost of migrating them by direct copy will also grow in a linear fashion. This research was supported by the AT&T Cooperative Research Fellowship Program. It was also supported by the Defense Advanced Research Projects Agency (DoD), ARPA Order No. 3597, monitored by the Air Force Avionics Laboratory under contract F33615-g4-K-1520. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specfic permission. © 1987 ACM 089791-242-X/87/0011/0013 $1.50 13 Any attempt to make process migration a more usable and attractive facility in the presence of large address spaces must focus on this basic bottleneck. One approach is to perform a logical transfer, which in reality requires only portions of the address space to be physically transmitted. Instead of ship- ping the entire contents at migration time, an IOU for all or part of of the data can be sent. As the relocated process executes on the new host, attempts to reference "owed" memory pages will result in the generation of requests to copy in the desired blocks from their remote locations. Context transmission times during migration are greatly reduced with this demand-driven copy-on-reference approach, and are vir- tually independent of the size of the address space. Processes are assumed to touch relatively small portions of their address spaces, justifying the higher cost of accessing each page during remote execution. This paper describes the process migration facility built for the SPICE [12] environment at Carnegie Mellon University, which demonstrates the validity of using copy-on-reference transfer to attack the migration bottleneck. Section 2 describes the design of the Accent copy-on-reference mechanism, available to any application wishing to lazy- evaluate its data transfers. Accent's organization and abstrac- tions not only provide the transparency needed to support migration, but lend themselves to the natural construction of such a mechanism. Section 3 show how the migration system capitalizes on copy-on-reference data delivery. Section 4 presents performance measurements taken on a set of repre- sentative processes that were migrated using different trans- mission strategies. Process relocations occur up to one thousand times faster using copy-on-reference transfers. While the amount of allocated data varies by four orders of magnitude across the processes studied, their transfer times are practically constant. The number of bytes exchanged between machines as a result of migration and remote execu- tion drops by 58.2% on average, and message-handling costs are cut by 47.8%. The assumption that processes touch a relatively small part of their memory while executing is shown to be correct, helping to account for these figures. The detailed measurements are used to assess the effect of such copy-on-reference variations as prefetching in response to remote page requests and migration-time transfer of the ad- dress space portions resident in main memory. Section 5 compares the Accent migration work to other activity in thefield. Finally, Section 6 summarizes the lessons learned from the Accent migration system and considers future research directions suggested by this work. 2. The Accent Copy-On-Reference Mechanism Accent's design and organization allows such intelligent vir- tual memory techniques as copy-on-write to be applied to data passed through the IPC system. It is this feature which aids in the construction of another intelligent strategy, copy-on- reference. This section begins by providing a quick overview of the Accent features that contribute to the natural construc- tion of a transparent, genetic copy-on-reference facility. Accent's imaginary segment abstraction serves as the basis for lazy data