InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

An Efficient Scheme for Migration of in-use Objects in a Distributed System

IP.com Disclosure Number: IPCOM000019885D
Original Publication Date: 2003-Oct-07
Included in the Prior Art Database: 2003-Oct-07

Publishing Venue



This invention presents a scheme that allows migrating an object in a multi-threaded environment without requiring that all accesses to the object be synchronized. Instead, provided is a means of determining whether or not another thread is using an object which we want to migrate, only incurring a significant overhead for those objects we wish to migrate.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 14% of the total text.

Page 1 of 10

An Efficient Scheme for Migration of in-use Objects in a Distributed System

Distributed object systems use the master-proxy object model to represent and use objects. Each object in the system has one master object on one node (called the master node) and can have several proxies (one proxy per node) on other nodes in the system. Invoking a method on a proxy can be implemented either by method shipping; i.e., redirecting the method to the master node where the master object resides, or by object shipping where the master object is moved to where the method was invoked. Even in systems that use method shipping, it is sometimes preferable to move the object to where it is mostly used to avoid many remote accesses. Thus, an efficient object migration mechanism is important to the performance of distributed object systems.

    Object migration in a multi-threading environment is difficult since several threads can use the object that is being moved. In other words, if we are careless, the state of the object may change while moving. Thus, the target node can get an object with inconsistent data. A simple and inefficient solution to this is to lock each object before it is used. Thus if the object is moved, other threads using the object will wait until migration is completed before using the object.

    A solution where we lock every object when an operation is applied on it may incur large overhead and may reduce parallelism, and thus performance, significantly (due to serializing operations on objects). Also, the introduction of extra synchronization may introduce deadlocks. From a different perspective, it is often the case that (1) most objects are transient and need not be locked and (2) only a few (unknown in advance) of the threads use the object being moved.

    In multi-threaded environments applications cannot assume specific thread execution order. Therefore, in case where one thread reads an object field and another thread writes to the same field, without proper synchronization the application cannot assume what is executed first. Thus, either the application does not care, and no synchronization is required, or the applications writer uses synchronization primitives to ensure "correct" order. For this reason, the algorithm presented here handles threads that either mutate the object or acquire a lock but not threads that read from the object. In the sequel we use the term 'mutate' to mean either writing to the object or locking it.

    The main advantage of our algorithm is that it achieves the following goals simultaneously:

It is correct and deadlock-free. It is adequate for running in a multithreaded

environment. The overhead required of threads that do not access the migrated object is

negligible, in particular, their run is never stopped for synchronization. The overhead required for threads that access an object while it is being moved

is minimal: they basically wait until it is moved and then access it remotely.

Outline of the A...