Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-11-09
2001-02-20
Hafiz, Tariq R. (Department: 2762)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06192517
ABSTRACT:
BACKGROUND OF THE INVENTION
A. Field of the Invention
This invention generally relates to garbage collection for computer systems and, more particularly, to a methodology for determining the existence of reference conflicts in Java bytecodes and for modifying the bytecodes to eliminate the conflicts, thereby improving the performance of garbage collection.
B. Description of the Related Art
An important concept in memory management of computer systems is the way in which memory is allocated to a task, deallocated, and then reclaimed. Memory deallocation and reclamation may be explicit and controlled by an executing program, or may be carried out by another special purpose program which locates and reclaims memory which is unused, but has not been explicitly deallocated. “Garbage collection” is the term used to refer to a class of algorithms used to carry out memory management, specifically, automatic reclamation. There are many known garbage collection algorithms, including reference counting, mark-sweep, and generational garbage collection algorithms. These, and other garbage collection techniques, are described in detail in a book entitled “Garbage Collection, Algorithms For Automatic Dynamic Memory Management” by Richard Jones and Raphael Lins, John Wiley & Sons, 1996. Unfortunately, many of the described techniques for garbage collection have specific requirements which cause implementation problems.
The Java™ programming language is an object-oriented programming language that is described, for example, in a text entitled “The Java Language Specification” by James Gosling, Bill Joy, and Guy Steele, Addison-Wesley, 1996. This language is typically compiled to a universal executable format, using a “bytecode instruction set,” which can be executed on any platform supporting the Java virtual machine (JVM). The JVM is described, for example, in a text entitled “The Java Virtual Machine Specification,” by Tim Lindholm and Frank Yellin, Addison Wesley, 1996.
The JVM may stop an executing program at many bytecode boundaries to execute a garbage collector and optimize memory management in accordance with the collector's algorithm. The difficulty with this scheme, however, is providing accurate information for garbage collection at all points where collection is required.
In an object-oriented system, such as one or more related programs written in Java, a “class” provides a template for the creation of “objects” (which represent items or instances manipulated by the system) having characteristics of that class. The term template denotes that the objects (i.e., data items) in each class, share certain characteristics or attributes determined by the class. Objects are typically created dynamically during system operation. Methods associated with a class generally operate on the objects of the same class.
An object may be located by a “reference,” or a small amount of information that can be used to access the object. One way to implement a reference is by means of a “pointer” or “machine address,” which uses multiple bits of information, however, other implementations are possible. Objects can themselves contain primitive data items, such as integers or floating point numbers, and/or references to other objects. In this manner, a chain of references can be created, each reference pointing to an object which, in turn, points to another object.
Garbage collection algorithms generally determine reachability of objects from the references held in some set of roots. When an object is no longer reachable, the memory that the object occupies can be reclaimed and reused even if it has not been explicitly deallocated by the program. To be effective, garbage collection techniques should be able to, first, identify references that are directly accessible to the executing program, and, second, given the reference to an object, identify references contained within that object, thereby allowing the garbage collector to transitively trace chains of references.
In most language implementations, stacks form one component of the root set. A stack is a region of memory in which stack frames may be allocated and deallocated. In typical object-oriented systems, each method executing in a thread of control allocates a stack frame, and uses the slots of that stack to hold the values of local variables. Some of those variables may contain references to heap-allocated objects. Such objects must be considered reachable as long as the method is executing. The term stack is used because the stack frames obey a last-in/first-out allocation discipline within a given thread of control. There is generally a stack associated with each thread of control.
A garbage collector may be exact or conservative in how it treats different sources of references, such as stacks. A conservative collector knows only that some region of memory (e.g., a slot in the stack frame) may contain references, but does not know whether or not a given value in that region is a reference. If such a collector encounters a value that is a possible reference value, it must keep the referenced object alive. Because of the uncertainty in recognizing references, the collector is constrained not to move the object, since that would require updating the reference, which might actually be an unfortunately-valued integer or floating-point number. The main advantage of conservative collection is that it allows garbage collection to be used with systems not originally designed to support collection. For example, the collectors described in Bartlett, Joel F., mostly-Copying Collection Picks Up Generations and C++, Technical Report TN-12, DEC Western Research Laboratory, October 1989, and Boehm, Hans Juergen and Weiser, Mark, Garbage Collection in an Uncooperative Environment. Software-Practice & Experience, 18(9), p. 807-820, September 1988, use conservative techniques to support collection for C and C++programs.
In contrast, a collector is exact in its treatment of a memory region if it can accurately distinguish references from non-reference values in that region. Exactness has several advantages over conservatism. A conservative collector may retain garbage referenced by a non-reference value that an exact collector would reclaim. Perhaps more importantly, an exact collector is free to relocate objects referenced only by exactly identified references. In an exact system, one in which references and non-references can be distinguished everywhere, this enables a wide range of useful and efficient garbage-collection techniques that cannot easily be used in a conservative setting.
However, a drawback of exact systems is that they must provide the information that makes them exact, i.e., information on whether a given value in memory is a reference or a primitive value. This may introduce both performance and complexity overhead. For purposes of this description, “val” is used to refer to a primitive data item, such as an integer or a floating point number, that does not function as a reference (“ref”).
One technique for providing information distinguishing references from primitive values in exact systems is “tagging,” in which values are self-describing: one or more bits in each value is reserved to indicate whether the value is a reference. The MIT LISP Machine was one of the first architectures which used garbage collection and had a single stack with explicitly tagged memory values. Its successor, the Symbolics 3600, commercially available from Symbolics Inc., Cambridge, Mass., also used explicitly tagged memory values.
If tagging is not used, then the system must associate data structures with each memory region allowing references and non-references to be distinguished in that region. For example, each object may start with a reference to a descriptor of the type of the object, which would include a “layout map” describing which fields of the object contain references. Stack frames also contain references, and if the JVM were to offer exact garbage collection it must be able to distinguish slots in the frame assigned to vari
Agesen Ole
Detlefs David L.
Das Chameli C.
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Hafiz Tariq R.
Sun Microsystems Inc.
LandOfFree
Method, apparatus, and product for improved garbage... 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 product for improved garbage..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, apparatus, and product for improved garbage... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2594064