Transparent Process Migration: Design Alternatives and the Sprite
Implementation

Fred Douglis and John Ousterhout

One-line summary: This paper discusses the tradeoffs encountered in
supporting process migration in Sprite.

Overview/Main Points

   * Background:

        o The design of the Sprite process migration system involved a
          tradeoff between transparency, residual dependencies, performance,
          and complexity, all of which conflict with each other. Sprite
          emphasized transparency and performance. Transparency is difficult
          because it can force shared state to be distributed and difficult
          to manage.

        o Sprite Environment:

             + Idle hosts are plentiful (backed by stats).

             + Users expect to receive the full capabilities of the
               workstations on their desks.

             + The design of the kernel requires the use of kernel calls for
               interprocess communication. (This makes transparency
               difficult).

             + Sprite provides strong network support, including remote
               access to files and devices (central file servers/disk-less
               workstations) and a single network-wide space of process ids.

        o Rsh offers remote execution, but lacks transparency, eviction,
          performance, and automatic selection. Some UNIX systems provide a
          checkpoint/restart mechanism that handles some of the above, but
          this may not be enough (depending on the user/process and
          process/process interaction required).

        o Sprite takes a much more extreme approach than above, allowing
          processes to be moved at any time as transparently as possible,
          with the system automatically choosing the idle machines (through
          the central migration server, which orders machines depending upon
          idle time.) and determining when migration should occur. The user,
          however, must choose which processes will be migrated.

   * Difficulties:

     Processes have lots of state. Some things must be on the same machine
     as the process, and the overhead cannot be excessive. The options are
     to:

        o Transfer the state.
        o Arrange for forwarding.
        o Ignore the state, sacrifice transparency.

     Specific cases:

        o Virtual memory: May be very large amount of data to transfer. Can
          use an eager (freeze or pre-copy) or lazy approach. Eager may cost
          more, but lazy leaves more residual dependencies. For exec it is
          not much of an issue. Sprite's VM files are sent to the file
          server, which is accessed lazily. Processes sharing VM are not
          allowed.

        o Open files: State includes the file descriptor, access positions,
          and cache. Sharing causes one copy of this data to be maintained
          by the server, similar to file sharing in Sprite.

        o Message channels: Connection data and cache/buffers.

        o Execution state: Register values and condition codes.

     The process control block is maintained on both the home machine as
     well as the remote machine. The execution environment looks the same in
     both places, and the process's appearance to the rest of the world is
     unaffected by migration.

     Some additional modifications made:

        o File system modified so that every machine sees the same name
          space.

        o Enough state was transfered at migration time to ensure that
          normal kernel calls would work on the remote machine.

        o Some special kernel calls were forwarded home (i.e. gettimeofday
          and getpgrp)

        o Some kernel calls got hacked (i.e. fork - child must have same
          home as parent, but created on remote).

     Residual dependencies are only allowed on the home machine, reducing
     complexity but increasing dependence.

   * Performance:

        o 1/10 of a second to select and idle host and start a new process
          on it, not counting open file transfer or the flushing of modified
          data. Average migration time is 330 ms, which is pretty small in
          comparison to long-running programs such as compilation.

        o For properly structure applications, they saw a five-fold speedup
          (not close to linear on the # of machines, though, due to
          bottlenecks on the file server and home workstation).

        o Over a month of use, remote processes accounted for ~31% of all
          processing, with evictions occurring infrequently.

Conclusions

This paper supplied a very solid and exhaustive analysis of process
migration. Many machines are generally idle, making this approach very
favorable.

How would this fit in to the usual use of most of the world's computers? It
seems great for rendering and compilation, what about MS Word and the common
user? This is a lot of work if it only works for the uncommon case.

How is fault tolerance/recovery handled?
  ------------------------------------------------------------------------
Back to index