Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-06-30
2002-06-04
Courtenay, III, St. John (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C711S200000
Reexamination Certificate
active
06401137
ABSTRACT:
BACKGROUND OF THE INVENTION
A. Field of the Invention
This invention relates to systems for processing a virtual call in a multi-threaded environment and, more particularly, to systems for processing a virtual call during execution of a multi-threaded program using a memory storage device having a predetermined boundary in order to atomically patch the virtual call to an appropriate method.
B. Description of the Related Art
In object-oriented programming, a “class” provides a template for the creation of objects. Each class shares certain attributes determined by the class. These attributes typically include a set of data fields and a set of methods. The data fields hold values for an object and the methods define operations for manipulating these values of the object.
When a call is made to an object's method, a compiler determines the appropriate method to use. Sometimes, the compiler can easily do this because the method called is static, i.e., is bound to a determined definition of the method in a specific object class. However, when the method is not static (i.e., the method is a virtual method), binding of the particular method to the specific object class is dynamic and more complex but provides the object-oriented programmer with a greater degree of flexibility. In particular, those skilled in the art will realize that using virtual methods allows a programmer the flexibility to execute completely different methods using the same virtual call.
A call to a virtual method is typically referred to as a virtual call. When a virtual call is made, dynamic binding of the virtual call to the appropriate definition of the target method is performed. One technique for binding a virtual call is to use a conventional inline cache as described in an article entitled “Efficient Implementation of the Smalltalk-80 System” by L. Peter Deutsch and Allen M. Schiffinan and published by the Association for Computing Machinery (ACM) in 1983. Those skilled in the art will recognize that in an implementation of a conventional inline cache, a direct call is made to the last method invoked at a call site. A call site is defined as the location in a program at which a virtual call is made. The initial state of the call site is to invoke a binding routine, which determines the appropriate method associated with the virtual call from the class of a receiver object in the virtual call. The binding method then patches the call site, which dynamically binds the call to the appropriate method so to invoke the appropriate method.
In an implementation of an inline cache, the prologue of each virtual method compares the class of the receiver object to the class last used at that call site. If the classes do not match, a programmatic branch is taken to the binding routine, which determines the correct method for the virtual call and then patches the call site accordingly.
Unfortunately, various problems may be encountered when processing such a virtual call within a multi-threaded environment. A multi-threaded environment is essentially a programming environment where a computer program or application, also referred to as a multi-threaded program, is partitioned into logically independent “threads” of control that can execute in parallel. Each thread includes a sequence of instructions and data used by the instructions to carry out a particular program task. When employing a computer system with multiple processors, each processor may execute one or more threads depending upon the number of processors to achieve multi-processing of the program.
When attempting to patch a virtual call to a method during execution of a multi-threaded program, problems may occur because another thread may be executing the same instruction being patched. Furthermore, on some computer architectures, processing the virtual call to patch the call to the appropriate method can be complicated and undesirably slow because of the number of items to patch (e.g., the appropriate method and a large address identifier or pointer) as well as the unspecified amount of time it takes to propagate to the inline caches on other processors.
One way to resolve this problem is to stop any threads from entering the sequence of instructions being patched by suspending execution of all threads. Unfortunately, suspending execution of all threads undesirably affects the performance of the system by slowing execution of the multi-threaded program as a whole.
Another way to resolve this problem is to perform a conventional “lock out” sequence related to the call sequence when patching the instructions. While this also prevents any other thread from interrupting the patching call sequence, it requires a large overhead of instructions to be executed before and after the locked out patching call sequence. Thus, such a conventional “lock out” is also undesirable because of the slow performance of handling a virtual call.
Accordingly, there is a need for a system within a multi-threaded environment that efficiently processes a virtual call and allows one thread to patch the instructions of the virtual call while other threads may be safely and quickly executing the instructions.
SUMMARY OF THE INVENTION
Methods, systems, and articles of manufacture consistent with the present invention overcome the shortcomings of existing virtual call processing techniques by patching the instructions related to the virtual call within a single instruction cycle so that the patching process is not interruptible and is atomic. Methods, systems, and articles of manufacture consistent with the present invention, as embodied and broadly described herein, identify a target associated with a virtual call. A target is typically a targeted method defined by a class of receiver object, which is associated with the virtual call. Next, an address identifier is determined that is associated with the identified target. In particular, the address identifier may be a pointer to a memory address location within a restricted address space for maintaining the class of the receiver object. Once the target has been identified and the address identifier is determined, the virtual call and the address identifier (more particularly, instructions related to each of these) are placed within a predetermined boundary of a memory storage device. Once placed within the predetermined boundary, the virtual call is patched to the target and the contents of a memory storage device are patched to a value of the address identifier during a single instruction cycle.
In accordance with another aspect of the present invention, methods, systems, and articles of manufacture, as embodied and broadly described herein describe, a virtual call processing system having a memory storage device having a predetermined boundary and capable of being updated within a single instruction cycle. The system also includes a processor coupled to the memory storage device. The processor is capable of updating the memory storage device within the single instruction cycle and configured to execute the multi-threaded program. During execution of the multi-threaded program, the processor is also operative to detect the virtual call, identify a target associated with the virtual call, and determine an address identifier associated with the target. The address identifier is within a restricted address space typically maintaining a class of an object related to the virtual call. The processor is also operative to place the virtual call and the address identifier within the predetermined boundary of the memory storage device. In such a configuration, the processor is then operative to, within a single instruction cycle, patch the virtual call to the target and patch the contents of the memory storage device to the value of the address identifier. More particularly stated, the processor may atomically update both a call instruction to reflect the targeted method and update a set instruction to reflect the value of the address identifier without allowing other threads to execute the updated call instruction with a non-updated address
Knippel Ross Charles
Wolczko Mario Iwan
Courtenay III St. John
Nguyen Van H.
Sun Microsystems Inc.
LandOfFree
Method, apparatus, and article of manufacture for processing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method, apparatus, and article of manufacture for processing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, apparatus, and article of manufacture for processing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2912297