Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-02-27
2003-11-25
Homere, Jean R. (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06654773
ABSTRACT:
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
This invention relates generally to programming of digital computers, and, more specifically, to memory management and garbage collection.
There are presently two broad approaches to memory management: (1) programmer memory management where programmers are responsible for writing explicit program code to de-allocate memory for the storage of objects no longer needed by a program; and (2) automatic memory management where the de-allocation of memory is done automatically, after the system determines that objects are no longer needed.
If memory management is automatic, there is no room left for programmer errors in memory management, which result in memory leaks, dangling pointers, or both.
A memory leak occurs when a program fails to de-allocate an object which it no longer needs. The accumulation of such unneeded objects during the execution of a program can lead to an unnecessary exhaustion of memory available for executing the program, and a resultant program abortion.
A dangling pointer reflects the converse mistake in memory management. This occurs when program code is executed which de-allocates an object while pointers to it still exist in an executing program. If some portion of code attempts to use the de-allocated object through a pointer it still possesses, the result is unpredictable and usually erroneous.
Automatic memory management removes the possibility of either of these errors. There is therefore an increase in the expectation of the reliability of a program executed with automatic memory management, over one executed with programmer-controlled explicit memory management. There is a significant labor savings in developing software for a system that supplies automatic memory management, since memory management mistakes are difficult to discover. However, automatic memory management systems do exact a toll in the efficiency of the programs using them, as is discussed below.
Many garbage collection methods have been proposed, the purpose of all of which is to discover, automatically and in as little processing time as possible, what objects in a program's memory are no longer needed by a program, so that those objects can be de-allocated and their storage reclaimed. Some of these garbage collection methods have significant processing overhead, which reduces the desirability of these methods and even precludes them from being used in certain applications (such as high-speed real-time systems). Thus, it is desirable that automatic memory management be as efficient as possible, to allow the broadest range of applicability.
Many garbage collection systems are constructed so as to suspend the normal execution of a program at random intervals, in order to find and delete objects in memory that are no longer needed. A program executed with such a garbage collection system can never be depended on to run in exactly the same manner as any prior execution, even given all of the same operating conditions and inputs. Determinism is lost.
Determinism is important for real-time applications where physical processes outside a computer controlling them are occurring at a fixed rate. The software controlling such computers must be able to guarantee that it will respond to external events within known time limits. Under such circumstances, the use of a non-deterministic garbage collection mechanism may be precluded.
One approach to garbage collection uses reference counting. In this method, each object has a property attached to it called its reference count, which is merely the number of objects that possess a pointer to that object. Clearly, when an object's reference count becomes zero, it may safely be de-allocated.
It is fairly simple and somewhat efficient to manage a reference count for an object, but the method has a significant limitation involving circular references. Suppose a program allocates objects A and B, stores a reference to A in B, and stores a reference to B in A. Now, even if all other references to the objects A and B are deallocated, A and B would each have a reference count of 1, indicating their references to each other. Thus, A and B would never be de-allocated, and this represents a memory leak.
BRIEF SUMMARY OF THE INVENTION
The above-discussed and other drawbacks and deficiencies of the prior art are overcome or alleviated by a garbage collection method of the present invention. The garbage collection method distinguishes between local objects and managed objects, and between an ordinary pointer to an object, an owning pointer to an object, and a non-owning pointer to an object. Ordinary pointers may point only to local objects, and owning and non-owning pointers may point only to managed objects. Managed objects have attributes including a count of the number of owning pointers referring to them, and a linked list of non-owning pointers referring to them. Managed objects may only possess non-owning pointers. Only an invocation of a subroutine within a thread can possess an owning pointer. Using this method, when an invocation exits, its exit code gives up ownership of all objects it owned. When an object is no longer reachable from any owning pointer, either directly, or indirectly through non-owning pointers, the object is immediately deallocated.
By implementing data structures and methods to support owning pointers, non-owning pointers, and managed objects, and by enforcing rules regarding the use of ordinary pointers, owning pointers, and non-owning pointers, efficient and deterministic garbage collection is achieved, memory leaks and dangling pointers are eliminated, and objects containing circular references to each other are not a source of memory leaks.
The present invention is embodied in software preferably written using an object-oriented programming language. It is also embodied in multi-threaded environments, multi-process environments, and as part of a persistence management system. It is embodied as an intrinsic part of a programming language. It may also be used to access POSIX®-compliant file systems.
The garbage collection method of the present invention has the following and other advantages over prior art garbage collection methods, some of which are essential for real-time applications. It is deterministic. A given graph of managed objects, owning pointers, and non-owning pointers will always be destroyed at the same point in a program, on every run of that program under the same conditions. Given these characteristics, a program never will be pre-empted randomly while a garbage collector cleans up memory. The cost of memory management, and the timing of its execution, can always be directly derived from the program. It de-allocates as early as possible, so total memory consumption is always the minimum possible. Destruction is guaranteed before termination of the program. In an object-oriented implementation, destruction will call an object's destructor to release any resources in use by the object, which may include resources other than memory. An object-oriented programming system incorporating the present invention can guarantee that the destructor of every object will be called as soon as the object is no longer reachable by the program.
The above-discussed and other features and advantages of the present invention will be appreciated and understood by those skilled in the art from the following detailed description and drawings.
REFERENCES:
patent: 4755939 (1988-07-01), Watson
patent: 4775932 (1988-10-01), Oxley et al.
patent: 5398334 (1995-03-01), Topka et al.
patent: 5652883 (1997-07-01), Adcock
patent: 5799185 (1998-08-01), Watanabe
patent: 5848423 (1998-12-01), Ebrahim et al.
patent: 5900001 (1999-05-01), Wolczko e
Cantor & Colburn LLP
Homere Jean R.
Tajea Corporation
LandOfFree
Method of deterministic garbage collection 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 of deterministic garbage collection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of deterministic garbage collection will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3150108