Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-12-29
2003-09-09
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06618737
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to improvement in the efficiency of distributed computing systems. More particularly this invention relates to an improved caching technique that reduces the overhead of remote access of distributed objects while preserving coherency, and which permits the local execution of operations on distributed objects.
2. Description of the Related Art
In a distributed computing system caching is a common technique for avoiding overhead for remote accesses. In general, when an object is cached, some sort of coherency protocol is required to ensure that an update on one copy is correctly reflected on all other copies. Often this coherency protocol takes the form of allowing one node to update the object at a time. If objects which are read-only are cached, there are no updates, and thus no need for a coherency protocol. Once an object is cached in a node, operations (method invocations, read and write) on the object can be executed locally. Caching is most effective when used for data that is rarely or never modified.
In many cases objects are mostly or partially read-only in the sense that some subset of the object's fields are read-only. In other cases, objects cannot be proven to be read-only statically, either because there is code that modifies the fields of the object, or not all of the program code is available for static analysis. Sometimes, the execution of code that modified the fields at run time depends on input data. For some input it may never be executed. According to known prior art, for these objects to be cached, and for operations against these objects to be locally executed, one of the following would have been required: (1) the use of a coherency protocol; or (2) the use of explicit hints provided by the programmer as to whether or not it was safe to cache the object.
A Java virtual machine (JVM) is platform-specific, as regards the operating system and the hardware. It is both an operating system and a program that implements a well-defined, platform independent virtual machine. It is an example of an environment suitable for the practice of the present invention. There are currently implementations of Java virtual machines for a range of platforms from embedded systems up to mainframes.
The Java virtual machine is a stack machine whose semantics are given by a set of bytecodes. Code belongs to methods which, in turn, belong to classes. Java and the Java virtual machine are very flexible, allowing classes to be dynamically created by an application, loaded, and then executed in the same application. When executed, the bytecodes change the state of the stack and can mutate objects allocated in a heap. The Java virtual machine supports multiple concurrent threads.
The basic memory model for the data manipulated by a Java virtual machine consists of stacks and a heap. There is a stack for each thread. Each stack consists of a collection of stack frames, one for each method that was invoked and which has not yet returned, where the frame is divided into three areas; parameters, variables and a conventional push-down operand stack.
Objects are allocated on a garbage collected heap via explicit program requests to create a new object. The request to create a new object, places a reference to the object on the top of the stack, enabling the object to be further manipulated.
In addition to the heap and the stack, the Java virtual machine internally uses system memory for various resources, including metadata related to the program's classes, the program's instructions, etc. The metadata associated with a class includes information such as an object representing the class, and information on the class methods, which is maintained in an array of method block structures entries (one for each method), and more. The program's instructions are the bytecodes that make up its methods.
The Java virtual machine bytecodes are conveniently divided into different groups based upon the type of memory they access. Based upon this division, it is possible to gain an understanding of what is required to ensure the correct semantics of the bytecode in a cluster of Java virtual machines.
A large set of bytecodes only accesses the Java stack frame of a currently executing method. For example, bytecodes corresponding to load and store instructions to and from a stack frame, control flow, and arithmetic operations. It is relatively easy to guarantee a single system image for these bytecodes since the code can be replicated and since a stack frame is accessed by only a single thread.
Another group of bytecodes accesses objects in the heap. For example the bytecodes getfield and putfield access a specific object's fields. It is this group that is particularly relevant to the present invention when applied to a distributed object system. If two different nodes access the same object, it is essential that they each see the same values, within the constraints of Java's memory consistency.
The Java virtual machine as a virtual stack machine is powered by an interpreter loop. On each iteration of the loop the next bytecode is executed. The stack is modified as specified by the bytecode, the heap is accessed as appropriate and the program counter is updated. The interpreter loop can be viewed as a giant switch statement, specifying a distinct action for each of the bytecodes.
To enable correct multithreaded operations, Java provides a synchronization mechanism implemented in the Java virtual machine, which allows threads to share and manipulate data correctly. The semantics of the Java memory model are well known, and only a brief description is presented herein.
When a thread executes a synchronized operation it tries to acquire a lock on the specified object. If the lock has already been acquired by another thread, the current thread waits. When the lock is released, one of the waiting threads acquires it and the others remain in a wait state.
A thread may acquire the same lock several times in a row. A thread releases a lock L when the number of unlock operations it performs on the lock L equals the number of lock operations.
The cluster virtual machine for Java is a known implementation of the Java virtual machine, which provides a single system image of a traditional Java virtual machine, while executing in a distributed fashion on the nodes of a cluster. The cluster virtual machine for Java virtualizes the cluster, transparently distributing the objects and threads of any pure Java application. The aim of the cluster virtual machine for Java is to obtain improved scalability for Java server applications by distributing the application's work among the cluster's computing resources. While the existence of the cluster is not visible to a Java application running on top of a cluster virtual machine for Java, the cluster virtual machine for Java is cluster-aware. The implementation distributes the objects and threads created by the application among the nodes of the cluster. In addition, when a thread that is placed on one node wishes to use an object that has been placed upon another node, it is the cluster virtual machine for Java implementation that supports this remote access in a manner that is 100% transparent to the application.
The optimizations incorporated in the cluster virtual machine for Java adhere to Java memory semantics. Relevant components of the architecture of the cluster virtual machine for Java are now described. A full description can be found in the document,
cJVM: a Single System Image of a JVM on a Cluster
, Y. Aridor, M. Factor and A. Teperman. International Conference on Parallel Processing, Sep. 21-24, 1999.
FIG. 1
shows how a cluster virtual machine for java
10
executes a Java application
12
on a cluster
14
. The upper half shows the threads
16
and objects
18
of the application
12
as seen by the program. This is the view presented by a traditional Java virtual machine. The lower half shows the distributed objects
20
and distributed threads
Aridor Yariv
Eilam Tamar
Factor Michael
Schuster Assaf
Teperman Avi
Chen Te Y
Darby & Darby
Metjahic Safet
LandOfFree
Speculative caching of individual fields in a distributed... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Speculative caching of individual fields in a distributed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Speculative caching of individual fields in a distributed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3022724