Newsgroups: comp.parallel From: cronk@shark.icase.edu (Cronk David) Subject: process migration Organization: ICASE/NASA Langley Date: Tue, 14 Jun 1994 10:19:00 GMT A couple of weeks ago I posted requesting information on process migration. Thank you to all who responded. Along with the helpful information, I also got many requests to post the results of my inquiry. Well, here in a list of the references I received. Again, thanks to all who responded. Dave ============================================================================= Dave Cronk Dave Cronk College of William and Mary ICASE cronk@cs.wm.edu cronk@icase.edu =========================================================================== =========================================================================== >From tossy@lfbs.rwth-aachen.de Thu Jun 9 07:59:23 1994 Hi, I faced process migration in my diploma thesis 'process migration in massively parallel system'. As I've not got time at the moment, I just forward you my list of references of the thesis. There are a lot of references concerning task and process migration. Sorry that it's in German - but the titles speak for themselves. Feel free to contact me again. Frank ---- cut here ---- [Astf93] G. Astfalk, "Fundamentals and practicalies of MPP", The Leading Edge, August 1993, Seiten 839-843 ; September 1993, Seiten 907- 911; Oktober 1993, Seiten 992-998 [AtBaBo88] G. Attardi, A. Baldi, U. Boni und andere, "Techniques for Dyna- mic Software Migration", ESPRIT '88, Putting the Technology to Use, (Proceedings of the 5th Annual ESPRIT Conference, Brussels, Begium, November 1988), Seiten 475-491 [BGW93] A. Barak, S. Guday, R.G. Wheeler, "The MOSIX Distributed Ope- rating System: Load Balancing for UNIX", Springer-Verlag Berlin Heidelberg, 1993 [Biek91] B. Bieker, "Benutzertransparentes Monitoring von Multitranspu- tersystemen", Studienarbeit an der Universit"at-GH-Paderborn, FB 14, 1991 [Biek93] B. Bieker, "Evaluation of User-Transparent Checkpointing", ES- PRIT Project 6731, Report R 3.2.1, 1993 [B"ose93] R. B"ose, "Migration von Prozessen", Ausarbeitung im Rahmen des Seminars "Auftragsbearbeitung in Parallelrechnern verschiede- ner Architekturen", Lehrstuhl f"ur Betriebssysteme, RWTH Aachen 1993 [BrLiLi91] A. Bricker, M. Litzkow und M. Livny, "Condor Technical Sum- mary", Technical Report, Computer Science Department, Univer- sity of Wisconsin-Madison, 1991 [BuFrNo90] S. Burkhardt, M. Fritzsche und O. Nowak, "COMPARE - Com- puter mit Parallelarchitektur f"ur Experimentalzwecke", Informat* *i- onstechnik it 32, Juni 1990, Seiten 393-399 96 LITERATURVERZEICHNIS [CaVi91] U. d. Carlini und U. Villano, "Transputers and parallel Architec* *tu- res: message passing distributed systems", Ellis Horwood Limited 1991 [DVCL93] G. Deconinck, J. Vounckx, R. Cuyvers, R. Lauwereins, "Survey of Checkpointing and Rollback Techniques", ESPRIT Project 6731, Technical Reports O3.1.8 and O3.1.12, ESAT-ACCA Laboratory, Katholieke Universiteit Leuven, Belgium, Juni 1993 [DoOu91] F. Douglis und J. Ousterhout, "Transparent Process Migration: Design Alternatives and the Sprite Implementation", Software- Practice and Experience, Vol 21(8), August 1991, Seiten 757-785 [EsKn93] R. Esser, R. Knecht, "Intel Paragon XP/S _ Architecture and Software Environment", Supercomputer '93, Proceedings zum Se- minar, Mannheim, 1993 [Flyn66] M.J. Flynn, "Very High Speed Computing Systems", Proceedings of the IEEE, Vol. 54 (12), 1966 [Gosc91] A. Goscinski, "Distributed Operating Systems: The Logical De- sign", undergraduate text, Addison-Wesley Publishing Company, Sydney, 1991 [Hac89] A. Hac, "A Distributed Algorithm for Performance Improvement Through File Replication, File Migration, and Process Migration", IEEE Transactions on Software Engineerig, Vol. 11/15, November 1989 [Haup92] D. Haupt, "Betriebssysteme I", Vorlesungsskript, RWTH Aachen, 1992 [HP91] Hewlett-Packard Company, "HP 9000 Series 300/400 and 600/700/800 Computers Berkley IPC Programmer's Guide", Hewlett-Packard Company 1991 [Hoar85] C.A.R Hoare, "Communicating Sequential Processes", Prentice- Hall International, UK, Ltd., 1985 [H"off92] M. H"offgen, "Konzepte zur Realisierung von Systemen zur Feh- lersuche bei Hochsprachenprogrammierung mit Schwerpunkt auf leichte Protierbarkeit Portierbarkeit f"ur unterschiedliche Proz* *esso- ren", Diplomarbeit am Lehrstuhl f"ur Betriebssysteme der RWTH Aachen, 1992 [Imbu93] O. Imbusch, "Ein Mikrokernel f"ur massiv-parallele Systeme", Di- plomarbeit am Lehrstuhl f"ur Betriebssysteme der RWTH Aachen, 1993 [Inmo88a] Inmos Ltd. , "Transputer Instruction Set: A compiler writer's guide", Prentice Hall International, 1988 LITERATURVERZEICHNIS 97 [Inmo89a] Inmos Ltd. , "The Transputer Applications Notebook: Systems and Performance", Inmos 1989 [Inmo89b] Inmos Ltd. , "The Transputer Applications Notebook: Architecture and Software", Inmos 1989 [Inmo90a] Inmos Ltd., "ANSI C Toolset User Manual", Inmos, 1990 [Inmo90b] Inmos Ltd., "ANSI C Toolset Reference Manual", Inmos, 1990 [Inmo91] Inmos Ltd., "The T9000 Transputer Products Overview Manual", Inmos, erste Auflage 1991 [Inmo93a] Inmos Ltd., "The T9000 Transputer Hardware Reference Manual", Inmos, erste Auflage 1993 [Inmo93b] Inmos Ltd., "The Transputer Databook", Inmos, dritte Auflage 1993 [LeTa87] J. v. Leeuwen und R.B. Tan, "Interval Routing", The Computer Journal, Vol. 30, No. 4, 1987, Seiten 298-307 [LiLi90] M. Litzkow, M. Livny, "Experience With the Condor Distributed Batch System", Proceedings of the IEEE Workshop on Experimen- tal Distributed Systems, Hunstville, 1990 [LiSo92] M. Litzkow, M. Solomon, "Supporting Checkpointing and Process Migration outside the Unix Kernel", USENIX Winter Conference, San Francisco, California, 1992, Seiten 1-8 [Ludw93] T. Ludwig, "Automatische Lastverwaltung f"ur Parallelrechner", BI Wissenschaftsverlag, Mannheim 1993 [Manh94] T. Manhardt, "Lastabh"angige, nutzertransparente Migrationssteue- rung in massiv parallelen Systemen mit Mehrbenutzerbetrieb", Di- plomarbeit am Lehrstuhl f"ur Betriebssysteme der RWTH Aachen, 1994 [MaThWe93] M.D. May, P.W. Thomson und P.H. Welch, "Networks, Routers and Transputers: Function, Performance and applications", Inmos Limited 1993, IOS Press [Meik93] Meiko, "Computing Surface CS-2: Product Description", Meiko, 1993 [MiZiDa92] D.S. Milojicic, W. Zint, A. Dangel, "Task Migration on top of the Mach Microkernel _ Design and Implementation", Technical Report 6/92 Zentrum Rechnergest"utzte Ingenieursysteme, Univer- sit"at Kaiserslautern [MGZD93a] D.S. Milojicic, P. Giese, W. Zint, A. Dangel, "Task Migration on top of the Mach Microkernel", Proceedings of the USENIX Mach III Symposium, Santa Fe, New Mexico, USA, 1993 98 LITERATURVERZEICHNIS [MiGiZi93a] D.S. Milojicic, P. Giese, W. Zint, "Load Distribution on Microke* *r- nels", IEEE Workshop "Future Trends in Distributed Computing Systems", Lissabon, Portugal 1993 [MiGiZi93b] D.S. Milojicic, P. Giese, W. Zint, "Experiences with Load Distri- bution on top of the Mach Microkernel", [MTMB90] D.A.P. Mitchell, J.A. Thompson, G.A.Manson, G.R. Brookes, "In- side the Transputer", Backwell Scientific Publications, 1990 [Mohr93] M. Mohring, "Mach 3 Shared Virtual Memory Implementation", Diplomarbeit am Institut f"ur Informatik der TU M"unchen, 1993 [NiMcK93] L.M. Ni und P.K. McKinley, "A Survey of Wormhole Routing Tech- niques in Direct Networks", IEEE Computer, Feb. 1993, Seiten 62-76 [NiRe90] D.M. Nicol und P.F. Reynolds, Optical Dynamic Mapping of Data Parallel Computation", IEEE Transactions on Computers, Vol. 2/39, Februar 1990 [Nolt92] T. Nolte, "Prozessmigration auf Rechnersystemen mit unterschied- lichen Prozessorarchitekturen", Diplomarbeit am Lehrstuhl f"ur B* *e- triebssysteme der RWTH Aachen, 1992 [Oed93] W. Oed, "The Cray Research: Massively Parallel Processor System CRAY T3D", Cray Research GmbH, November 1993 [Olle93] S. Ollenhauer, "Entwicklung von Schedulingverfahren mit statisti* *k- basierter Ansteuerung f"ur massiv parallele Systeme", Diplomarbe* *it am Rechenzentrum der RWTH Aachen, 1993 [Pars91a] Parsytec, "Parsytec GC, Technical Summary", Parsytec GmbH, 1991 [Pars91b] Parsytec, "Helios Operating System Manual", Parsytec GmbH, 1991 [Pars91c] Parsytec, "Network Configuration Manager: Software Documenta- tion", Version 3.0/3.3, Parsytec GmbH, 1991 [Pars93a] Parsytec, "PARIX Release 1.2: Software Documentation", Parsy- tec GmbH, M"arz 1993 [Pars93b] Parsytec, "PARIX Release 1.2: Reference Manual", Parsytec GmbH, M"arz 1993 [Pars93c] Parsytec, ausgew"ahlte Programmquellen des Parix 1.2 Systemker- nes. [Penn91] V. Penner, "Konzepte zur parallelen Programmierung verteilter Sy- steme", 1991 LITERATURVERZEICHNIS 99 [Peri89a] Perihelion Software, "The Helios Operating System", Prentice Hal* *l, 1989 [Peri90a] Perihelion Software, "Helios C Manual", Perihelion, 1990 [Peri90b] Perihelion Software, "The Helios Encyclopaedia", Vol. I&II, Peri- helion, 1990 [Petr93] M. Petrosky, "Eizellen: WAN-Standard ATM auf dem Weg in die lokalen Netze", c't 6/1993, Seiten 84-87 [Powe93] F. Langhammer, "The PowerStone Project", PowerStone Parallel- rechner GmbH, November 1993 [PoMi83] M.L. Powell, B.P. Miller, "Process Migration in DEMOS/MP", Proceedings of the 9th ACM Symposium on Operating Systems Principles, 1983, Seiten 110-119 [Reit92] F. Reiter, "Konzeptionierung und Realisation einer Datenschnitt- stelle f"ur die Betriebssteuerung eines massiv parallelen System* *s im Rechenzentrumsbetrieb", Diplomarbeit am Lehrstuhl f"ur Betriebs- systeme der RWTH Aachen, 1992 [Rein93] M. Reiner, "Prozesszustandsinformationen auf Transputersyste- men", Studienarbeit am Lehrstuhl f"ur Betriebssysteme der RWTH Aachen, 1993 [Scha92] L. Schauff, "Spezielle Kommunikation in massiv parallelen Syste- men", Diplomarbeit am Lehrstuhl f"ur Betriebssysteme der RWTH Aachen, 1992 [Schm92] A. Schmidt, "Prozessmigration", Ausarbeitung im Rahmen des Seminars "Auftragsbearbeitung in massiv parallelen Systemen", Lehrstuhl f"ur Betriebssysteme, RWTH Aachen, 1992 [Schi90] A. Schill, "Migrationssteuerung und Konfigurationsverwaltung f"ur verteilte objektorientierte Anwendungen", Springer Verlag, Berlin Heidelberg, 1990 [Smit88] J.M. Smith, "A Survey of Process Migration Mechanisms", Ope- rating Systems Review, July 1988, vol. 22, no. 3, Seiten 28-40 [SmMa88] J.M. Smith und G.Q. Maguire, "Process Migration: Effects on Scientific Computation", ACM SIGPLAN Notices 23(3), M"arz 1988, Seiten 102-106 [Stei87] R. Steinmetz, "OCCAM 2: Die Programmiersprache f"ur parallele Verarbeitung", H"uthig Verlag Heidelberg, 1987 [Stev90] W.R.Stevens, "UNIX Network Programming", Prentice Hall, Englewood Cliffs 1990 100 LITERATURVERZEICHNIS [Sun90] Sun Microsystems, "Network Programming Guide", Sun Microsy- stems, Part Number 800-3850-10, Revision A of 27 March 1990 [Tane92] A.S. Tanenbaum, "Modern Operating Systems", Prentice-Hall In- ternational, 1992 [ZGG90] W. Zhu, A. Goscinski, G.W. Gerrity, "Process Migration in RHO- DOS", Technical Report CS90/9, University College, The Univer- sity of New South Wales, 1990 [ZhGo90a] W. Zhu, A. Goscinski, "Load Balancing in RHODOS", Technical Report CS90/8, University College, The University of New South Wales, 1990 [ZhGo90b] W. Zhu, A. Goscinski, "The Development of the Load Balancing Server and Process Migration Manager for RHODOS", Technical Report CS90/47, University College, The University of New South Wales, 1990 [ZRBP93] R. Zajcew, P. Roy, D. Black, C. Peak und andere, "An OSF/1 UNIX for Massively Parallel Multicomputers", Winter USENIX Conference, 1993, Seiten 449-468 [ZTB93] R. Zajcew, S. Tritscher, M. Barnett, "Load Leveling Using Process Migration On Massively Parallel Multicomputers", SEDMS, 1993, Seiten 37-45 -- ............................................................................. >From pmar@dcs.ed.ac.uk Tue Jun 7 13:51:35 1994 I don't know what aspects of migration you are particularly interested in, but I've been doing some work on implementing an OS for a load balancing multicomputer and you might be interested in a couple of technical reports I've just completed. Paul. ---------------------------------------------------------------------- "The Formal Specification in Z of Task Migration on the Testbed Multicomputer" by Paul Martin, University of Edinburgh KEYWORDS: formal specification, correctness proofs, the Z language, task migration. ABSTRACT: This report introduces a message-passing multicomputer called the `Testbed' and describes its facilities for transparent task migration between processors. A specification in the formal language Z is given for the key operating system components which support migration. Finally, rigorous arguments are presented which verify that task migration is correct and safe. The contributions of this report are an extended specification showing the application of Z to a real system and a detailed demonstration of the verification of safety and correctness properties. Conclusions are drawn about the utility of formal methods in general. DETAILS: File is compressed postscript, 239825 bytes, 69 pages. FTP: ftp.dcs.ed.ac.uk:/pub/pmar/ECS-CSG-2-94.ps.Z WWW: ftp://ftp.dcs.ed.ac.uk/pub/pmar/ECS-CSG-2-94.ps.Z ---------------------------------------------------------------------- The following technical report is now available in electronic form. "The Performance Profiling of a Load Balancing Multicomputer" by Paul Martin, University of Edinburgh KEYWORDS: message-passing multicomputers, operating system design, load balancing, task migration, performance measurements. ABSTRACT: This report introduces a message-passing multicomputer called the `Testbed' and describes the operating system and hybrid monitoring support for load balancing. A series of experiments are reported in which detailed and accurate performance figures are established for the functions associated with task migration, thus parameterising some key properties of the Testbed. A number of different performance metrics are compared in terms of their costs versus their utility for load balancing. Finally, a sample load balancing strategy is outlined for the Testbed and speedup results obtained for a range of applications. DETAILS: File is compressed postscript, 424880 bytes, 84 pages. FTP: ftp.dcs.ed.ac.uk:/pub/pmar/ECS-CSG-3-94.ps.Z WWW: ftp://ftp.dcs.ed.ac.uk/pub/pmar/ECS-CSG-3-94.ps.Z ---------------------------------------------------------------------- Replied: kurts@domino.larc.nasa.gov ================ SOURCE: NASA TECHNICAL LIBRARY CATALOG ======================= 1) Transparent process migration: Design alternatives and the Sprite implementation copies: 1 (DOC-RECON) DOUGLIS, FRED type: DOC NASA-CR-189966 pubyear: 1991 The Sprite operating system allows executing processes to be moved between hosts at any time. We use this process migration mechanism to offload work onto idle machines, and also to evict migrated processes when idle workstations are reclaimed by their owners. Sprite's migration mechanism provides a high degree of transparency both for migrated processes and for users. Idle machines are identified, and eviction is invoked, automatically by daemon processes. On Sprite it takes up to a few hundred milliseconds on SPARCstation 1 workstations to perform a remote exec, while evictions typically occur in a few seconds. The pmake program uses remote invocation to invoke tasks concurrently. Compilations commonly obtain speedup factors in the range of three to six; they are limited primarily by contention for centralized resources such as file servers. CPU-bound tasks such as simulations can make more effective use of idle hosts, obtaining as much as eight-fold speedup over a period of hours. Process migration has been in regular service for over two years. 2) Process migration in UNIX environments copies: 1 (DOC-RECON) LU, CHIN type: DOC NASA-CR-182951 pubyear: 1988 To support process migration in UNIX environments, the main problem is how to encapsulate the location dependent features of the system in such a way that a host independent virtual environment is maintained by the migration handlers on the behalf of each migrated process. An object-oriented approach is used to describe the interaction between a process and its environment. More specifically, environmental objects were introduced in UNIX systems to carry out the user-environment interaction. The implementation of the migration handlers is based on both the state consistency criterion and the property consistency criterion. 3) Correctness criteria for process migration copies: 1 (DOC-RECON) LU, CHIN type: DOC NASA-CR-182939 pubyear: 1987 Two correctness criteria, the state consistency criterion and the property consistency criterion for process migration are discussed. The state machine approach is used to model the interactions between a user process and its environment. These criteria are defined in terms of the model. The idea of environment view was introduced to distinguish what a user process observes about its environment from what its environment state really is and argue that a consistent view of the environment must be maintained for every migrating process. 4) Process migration in distributed systems. copies: 1 (CHECKD-OUT) Lu, Chin type: DOC CN-157,936 ================================= SOURCES =================================== http://cs.indiana.edu/cstr/search?process+migration+mink%3D2 http://www.research.att.com/cgi-bin/bibsearch_html?process+migration ============================================================================== J. R. Lyle and C. Lu, "Load balancing from a unix shell," in Proc. 13th Conference on Local Computer Networks, (Minneapolis, Minn.), pp. 181--183, IEEE Computer Society, Oct. 1988. Abstract: A local area network of workstations often has a number of idle workstations that could be used to lower the load of active workstations. Distributed operating systems that do load balancing or process migration are not widely used and are expensive to produce. Widely used operating systems, such as Unix, often have the capability of remotely executing a program, but no automatic load balancing facilities. We report on a low cost solution to workstation load redistribution by allowing the shell to select an alternate host for comment execution. P. Krueger and M. Livny, "A comparison of preemptive and non-preemptive load distributing," in Proc. 8th Intl. Conf. on Distributed Computing Systems, (San Jose, Calif.), pp. 123--131, June 1988. Abstract: Numerous load distributing algorithms have been proposed over the past several years, with widely varying characteristics. While some of these algorithms rely solely on non-preemptive process placement, others make use of preemptive process migration. Because the state of a process becomes considerably more complex after it begins execution, the mechanism necessary for migration is correspondingly more complex than that for placement, and may incur significantly greater resource overhead. In light of this complexity, as well as the consequent implementation expense, we consider whether the addition of a migration facility to a distributed scheduler already capable of placement can significantly improve performance. We examine performance over a broad range of workload characteristics and file system structures. We find that, while placement alone is capable of large improvement in performance, the addition of migration can achieve considerable additional improvement. A. Hac, "A distributed algorithm for performance improvement through file replication, file migration and process migration," IEEE Trans. Software Engineering, vol. 15, pp. 1459--1470, Nov. 1989. F. Douglis, "Experience with process migration in sprite," in Workshop on Experiences with Distributed and Multiprocessor Systems, (Fort Lauderdale, Florida), pp. 59--72, Oct. 1989. Y. Artsy and R. Finkel, "Designing a process migration facility: The charlotte experience," Computer, vol. 22, pp. 47--56, Sept. 1989. D. Freedman, "Experience building a process migration subsystem for UNIX," in Proc. 1991 Winter USENIX Conf., (Dallas, Texas), Jan. 1991. =========================== SOURCE: NTIS ==================================== Theimer, M ; Hayes, B. "Heterogeneous Process Migration by Recompilation," Xerox Palo Alto Research Center, CA. Report No. CSL-92-3, Sponsored by Stanford Univ. Dept of Computer Science, 1992. Heterogeneous process migration involves moving a process between machines that have differing hardware and software configurations, including different processor architectures, machine instruction sets, and operating systems. The paper describes an approach to heterogeneous process migration that involves building a machine-independent "migration program" that specifies the current code and data state of the process to be migrated. When the program is compiled and executed on the target machine, it will first reconstruct the process's state and then continue the normal execution of the now-migrated process. The principal advantage of this approach is that it hides the details of code and data translation in the compilers for each machine. =========================== SOURCE: INSPEC ================================== Dediu, H.; Chang, C.H.; Azzam, H. "Heavyweight Process Migration," Proceedings of the Third Workshop on Future Trends of Distributed Computing Systems, pp. 221-225, IEEE Comput. Soc. Press, Publisher, April 1992. (Practical) The authors consider a class of processes which is characterized by very long running times and very large data dependencies. Such processes exploit the availability of all system resources on the executing host. The long running times imply a need for undivided CPU bandwidth as well as intolerance for system faults. The authors consider the problem of supporting the execution of such heavyweight processes on small systems whose reliability and availability cannot be guaranteed. The support mechanism uses process migration and redundant execution which checkpointing to guarantee process completion. =========================== SOURCE: INSPEC ================================== van Dijk, G.J.W.; van Gils, M.J.; "Efficient process migration in the EMPS multiprocessor system," Proceedings 6th International Parallel Processing Symposium, pp. 58-66, IEEE Comput. Soc. Press, Publisher, March 1992. (Theoretical/Mathematical) The process migration facility in the Eindhoven multiprocessor system (EMPS) is presented. In the EMPS system, mailboxes are used for interprocess communication. These mailboxes provide transparency of location for communicating processes. The major advantages of mailbox communication in the EMPS system are: 1) interprocess communication can proceed without losing messages; 2) the communication paths can be updated very efficiently when a process moves to another processor. By redirecting the mailbox connection of the migrating process, the communication paths of all processes connected to the same mailbox are updated. =========================== SOURCE: INSPEC ================================== Taudes, A. "How to migrate process in distributed computing systems--a Markov team approach," Proceedings of the 12th International Conf. on Distributed Computing Systems, pp. 354-61, IEEE Comput. Soc. Press, Publisher, June 1992. (Practical) A process migration mechanism offers a means to exploit the performance reserves present in networks of workstations used as personal computers by allowing migration of processes from overloaded to underused processors. Several distributed operating systems provide such a facility, the benefits of its use depending on the specification of a proper process migration policy. An analytical model, the Markov team model, to assist in the design of such a policy is presented. This model is derived from results of classical team theory and Markov decision processes. The special case of homogeneous distributed computing systems and methods for parameter estimation are discussed. Numerical examples are used to demonstrate the benefits of using this model.