TASK MIGRATION

Introduction

• Singhal and Shivaratri define process/task migration as the transfer of partially executed tasks to another node in a distributed system - in other words, preemptive task transfer. Some references to task migration include the transfer of processes before execution begins, but the most difficult issues are those related to preemption.
• Terminology:
  • Task placement: non-preemptive transfer of process that has never run
  • Task migration: preemptive transfer of process that has been executed
  • Home node: site where the process originates
  • Foreign process: process executing on a node other than its home node
  • Freezing: when a process is migrated, its execution is interrupted (frozen) for the time it takes to move the process to another site.
• Migration is useful for several reasons:
  • load distribution, to equalize workload due to
    • transient periods of high load at some network nodes (transfer processes from temporarily overloaded node to another node)
    • or in a system where process origination is always unbalanced (a few workstations consistently generate many processes )
  • to return a workstation to its owner. (migrate a foreign process back to its home node when owner returns)
  • to improve communication (processes that communicate frequently can be moved to the same node; processes that access resources at a remote site may be moved to that site)
• Two steps in task migration:
  • State transfer: collect all information crucial to process execution  and transfer to another machine
    • Process control block contains register contents, memory map information, etc.
    • Process address space includes stack, heap, plus virtual pages currently in memory
      At some point during state collection, the process must be frozen
  • Unfreeze: after installing the process state at the new site, the process is put in the Ready queue to be scheduled

 

Issues in Task Migration

• State Transfer: Issues to consider here include
  • Cost in processor time, network bandwidth, etc.: When a process is moved to another node, it is frozen until the transfer is complete. There is the cost of a complete context switch, plus transfer, plus possible affect on other processes that might be affected. (Processes that interact with the migrating process may timeout during the interval when it is frozen, and thus could be aborted)
  • Residual dependencies: These are resources that the original host node must maintain on behalf of the migrated process. For example, a process may transfer pages in virtual memory only as they are referenced; the original host may have to forward messages directed to the process at its original site.
• Location Transparency: Users aren't required to know where a task is executed; there should be no affect on the process. Process names, file names, etc., must be independent of the host machine. A uniform name space is important to allow the process to maintain access to system resources, to continue to be able to communicate with other processes, etc.
• Structure of the Migration Mechanism: Singhal and Shivaratri emphasize the separation of policy from mechanism.  Policy decides when/where/why transfer to be done (see discussion of policies earlier) while mechanism is the act of collecting state, sending it elsewhere, etc. As always, there are benefits to separating the two: for example, policies can be changed without affecting mechanisms.
• Performance: This is the major drawback to any kind of dynamic task migration facility.

 

Process Migration Mechanisms

Stallings identifies the following issues in designing a process migration facility:

• Who initiates the migration?
• What part of the process is migrated?
• What happens to messages and signals?

Migration Initiation

• Migration can be initiated either by a module in the operating system, or by the process itself.
• OS module is the most common when load sharing is the primary objective of the migration
• If the goal is to move closer to resources or other processes, then the migration could be initiated by the process itself.

What is Migrated

• The process control block (PCB) is required, but is relatively easy to transfer from one machine to another (especially if the machines are heterogeneous)
• Process address space is more difficult.  The process will have a number of virtual pages in memory, and the question is whether to some or all, whether to precopy (move pages to new host while execution continues on old host), etc.  Some possibilities include:
  • Immediately move all of them (eager transfer)
  • Move all pages that are dirty, but transfer others on demand only
  • Move no pages at all until they are referenced
  • Flush pages to disk, page back in when they are referenced on the remote site

Messages and Signals

• Any messages or signals intended for a frozen process are stored at the host until the process transfer is complete
• Other messages and signals must be routed from the home site to the new host.

 

Heterogeneity

Many distributed systems consist of a variety of different platforms, running several different operating systems. This brings up a number of problems; e.g.,

• Object code for one machine won’t execute on a machine with a different instruction set.
• Data representations may differ from one platform to another
• Register structure will be different; information in PCB may not be directly transferable to a different computer.

Solutions are based on ideas such as

• Maintaining a migration stack that has platform-independent representations of platform-specific data
• Use of some sort of virtual machine approach, such as a common intermediate code that can be recompiled quickly for different platforms (similar to Java’s virtual machine concept)

 

Instances of Load Distribution and Process Migration

• Clusters dedicated to the execution of parallel programs often use static load distribution; less often would use dynamic load distribution, seldom use process migration
• Many research-based distributed systems, including Sprite, Charlotte, V-System, implemented process migration in the context of a network of workstations. 
• Current research in areas such as grid computing visualizes using remote resources on a wide-area network.
• Mobile agent research focuses on independently initiated movement of processes around a network to do various tasks: searches in a distributed data base, comparison shopping, etc.

 

Mobile Agents

Mobile agent systems deploy middleware on participating systems that support process migration.  “Agent” processes are written in Java, Tcl, or other language that can be interpreted at each host. The agent is executed much like a downloaded Java applets.  See references below

 

          1.  Mobile Agents - Process migration and its implications    By David Reilly

Abstract : Mobile agents are agents that can physically travel across a network, and perform tasks on machines that provide agent hosting capability. This allows processes to migrate from computer to computer, for processes to split into multiple instances that execute on different machines, and to return to their point of origin. Unlike remote procedure calls, where a process invokes procedures of a remote host, process migration allows executable code to travel and interact with databases, file systems, information services and other agents. The technology behind mobile agents is examined, and an analysis of its uses and implications is offered.

URL: http://www.davidreilly.com/topics/software_agents/mobile_agents/

 

2. Mobile Agents and the Future of the Internet  By David Kotz and Robert S. Gray, Department of Computer Science/Thayer School of Engineering, Dartmouth College,Hanover, New Hampshire 03755.  Copyright 1999 by David Kotz and Bob Gray.

URL: http://www.cs.dartmouth.edu/~dfk/papers/kotz:future2/

Mobile agents are programs that can migrate from host to host in a network, at times and to places of their own choosing. The state of the running program is saved, transported to the new host, and restored, allowing the program to continue where it left off. Mobile-agent systems differ from process-migration systems in that the agents move when they choose, typically through a ``jump'' or ``go'' statement, whereas in a process-migration system the system decides when and where to move the running process (typically to balance CPU load). Mobile agents differ from ``applets'', which are programs downloaded as the result of a user action, then executed from beginning to end on one host.