Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Method of deterministic garbage collection

a garbage collection and deterministic technology, applied in the field of digital computer programming, can solve problems such as memory leakage, dangling pointers, and unnecessary exhaustion of memory available for executing programs

Inactive Publication Date: 2011-05-24
TANGIE DATA HLDG
View PDF20 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Benefits of technology

[0014]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.
[0016]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 abject is no longer reachable by the program.

Problems solved by technology

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, end a resultant program abortion.
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.
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.
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).
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.
Thus, A and B would never be de-allocated, and this represents a memory leak.

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Method of deterministic garbage collection
  • Method of deterministic garbage collection
  • Method of deterministic garbage collection

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0023]The present invention specifies an invocation, an owning pointer, a non-owning pointer, and a managed object. In the preferred embodiment, these are modeled using statements of an object-oriented programming language as classes with the names Invocation, OwningPointer, NonOwningPointer, and ManagedObject, respectively. FIG. 1 shows these classes using the graphical symbols of the Unified Modeling Language (UML), as defined by Rumbaugh, James, Ivar Jacobson, and Grady Booch, “The Unified Modeling Language Reference Manual,” Reading, Mass., Addison-Wesley, 1999, which is incorporated herein by reference.

[0024]An invocation is an invocation of a subroutine within a thread of a process of a system. An invocation ceases to exist when it is exited. An owning pointer is a pointer from an invocation to a managed object that establishes an ownership relationship between the invocation and the managed object. The owner of an owning pointer owns the managed object to which it points. A n...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

A garbage collection method that 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 is presented. Ordinary pointers point only to local objects, and owning and non-owning pointers 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 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 de-allocated. 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.

Description

[0001]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[0002]This invention relates generally to programming of digital computers, and, more specifically, to memory management and garbage collection.[0003]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.[0004]If memory management is automatic, there is...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Patents(United States)
IPC IPC(8): G06F17/30G06F12/02
CPCG06F12/0261Y10S707/99939Y10S707/99938Y10S707/99957
Inventor HILLS, THEODORE S.
Owner TANGIE DATA HLDG
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products