Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-02-04
2002-09-03
Chaki, Kakali (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C707S793000
Reexamination Certificate
active
06446257
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to a method and apparatus for software development tools and is directed more particularly to a generational garbage collection tool of a compiler system in a computer system.
BACKGROUND OF THE INVENTION
Compiler systems operating in a computer system may manage allocation of computer resources such as computer memory at compile-time or at run-time. One method of computer resource allocation is garbage collection which is the automatic management of dynamically allocated computer resources, or storage. By the technique of garbage collection computer resources occupied by data objects are reclaimed when the data object may not be accessed again by an executing program. The reclaimed data object is referred to herein as “garbage.” It would be advantageous for garbage collection to accurately and effectively operate in a threaded environment and with objects that are referenced by interior as well as exterior pointers.
The term “compile-time” refers to the period of compilation before a computer program is loaded and executing on the computer system, and the term “run-time” refers to the period of compilation after the computer program is loaded and is able to execute on the computer system. The term “storage” refers herein to computer resources such as memory, and may be data or instructions used in executing a computer program.
A live object may be globally known. That is, procedures other than the one that created the object may access the object. Therefore, a garbage collector includes bookkeeping techniques to determine at run-time when an object is no longer live relative to any program that may attempt to access the object and this state is referred to herein as an object being “dead.” This bookkeeping method may include a determination of a safe point of the program. The safe point therefore is a point during program execution where the execution of the objects of a program may be halted and garbage collection may be safely performed. That is, at a safe point the garbage collector may safely dispose of all unresolved pointers and program code related to a dead object without impairing the functionality of the programs when garbage collection has completed and the programs are executing again.
Live objects, and not garbage, are preserved by a garbage collector thereby ensuring that pointers are not directed at dead, deallocated objects. Further, the efficiency of access to live objects may be improved during garbage collection by relocating the objects to contiguous storage locations. Therefore, after relocation of a live object, and since there may be more than one pointer referencing the object, garbage collection may work with threading techniques to ensure that the relationship between all the pointers referencing the object is maintained while only updating one pointer. That is, the pointers may be threaded thereby requiring update of only one pointer after object relocation.
Garbage collectors have been inhibited by the problem of reclaiming system resources in a multi-threaded programming environment. It will be appreciated that the term “thread” refers to a linear control flow of an executing program, and in a multi-threaded environment, several execution paths in an executing program may be executing simultaneously. Recall that a garbage collector requires access to system resources to relocate objects. Therefore, when several threads are being executed, including a garbage collector thread and another thread, both threads may be halted if they are simultaneously attempting to access the same system resources. Since system resources typically may be allocated in a serial fashion, the simultaneous attempts to obtain system resources will not be satisfied and the program may be indefinitely halted in a deadlocked state.
Further, current garbage collectors have been inhibited by the problem of locating a true safe point. For instance, it has not been possible to accurately determine during run-time the safe point of programs with interior pointers, especially in a multi-threaded environment. It will be appreciated that interior pointers may traverse unpredictable paths and therefore make identification of live or dead objects difficult. Accordingly there is a need to improve garbage collection to enable safe access to interior pointers in thread-based programs.
SUMMARY OF THE INVENTION
An embodiment of the present invention includes a generational garbage collection tool and method for a computer system that pre-allocates computer resources during compile-time for later use by a generational garbage collector at run-time. A purpose of generational garbage collection is to reduce the overall cost of dealing with long-lived objects and thereby allow a generational garbage collector to focus deallocation efforts on young objects, which are more likely to be dead. Another purpose of generational garbage collection is to reduce pause time to a level that does not disturb interactive users. The term “pause time” refers herein to the time a program is halted due to garbage collection. The technique of generational garbage collection achieves both purposes by segregating objects by age, and by collecting older generations much less frequently than younger ones. Therefore, improving the efficiency and expanding the scope of generational garbage collection will improve the management and allocation of computer resources. The terms “garbage collector” and “generational garbage collector” will be used interchangeably herein.
Fundamental concepts of generational garbage collection are explained in, “Unprocessed Garbage Collection Techniques,” by Paul R. Wilson. Also, garbage collection is explained in “Garbage Collection Algorithms for Automatic Dynamic Memory Management,” by Richard Jones and Rafael Lins, 1996, John Wiley & Sons.
When an object is threaded and a pointer that references the object is interior, accurate allocation of space to facilitate run-time generational garbage collection is very difficult. Therefore, it is an object of the invention to allocate space for interior pointers at compile-time when the location of interior pointers is known and thereby facilitate generational garbage collection. By enabling the use of threaded pointers that reference objects for generational garbage collection, the resource savings of threads may be employed. More particularly, by enabling the use of threaded interior pointers during generational garbage collection, live object relocation is improved by requiring an update to one pointer instead of updating each pointer that references an object.
It will be appreciated that the terms “instructions,” “data structures,” and “data” may refer to values such as integer, real, or complex numbers; or characters. Alternatively, the values may be pointers that reference values. Therefore, a pointer provides direction to locate a referenced value. The term “interior pointer” refers to a pointer to a location within a program other than the starting point for the program execution. The term “object” refers herein to a structured data record that may include instructions that operate and execute in association with the compilation system. Further an object may include instructions at locations that may be referenced by pointers. It will be appreciated that objects may include encapsulation and inheritance features such as are used in object-oriented programming. Those skilled in the art will appreciate these techniques used in object-oriented programming.
It is another object of the invention to efficiently manage at compile-time the bookkeeping necessary to allocate storage to pointers for use during generational garbage collection. That is the present embodiment identifies the pointers that may be updated due to generational garbage collection, and by selectively allocating space to those pointers that may be accessed during generational garbage collection and not all pointers, computer resources are saved. More particularly, with reference to interior pointers the present embo
Hennecke Mark D.
Mehta Michey N
Meshenberg Ruslan
Pradhan Salil
Chaki Kakali
Hewlett--Packard Company
Smith Christine H.
LandOfFree
Method and apparatus for pre-allocation of system resources... 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 and apparatus for pre-allocation of system resources..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for pre-allocation of system resources... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2839360