Accurately determining an object's lifetime

Details Accurately determining an object's lifetime Accurately determining an object's lifetime

2000-12-29

2004-09-21

Rones, Charles (Department: 2175)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000, C709S224000, C709S241000, C717S127000, C717S128000

Reexamination Certificate

active

06795836

ABSTRACT:

FIELD OF THE INVENTION
The invention is generally relates to computers and computer software. More specifically, the invention relates to the management of data structures and functions in an object oriented programming system.
BACKGROUND OF THE INVENTION
Managing available memory is critically important to the performance and reliability of a computer system. Such systems must store vast quantities of data within limited memory address space. Such data is commonly stored in the form of “objects.” Memory space allocated for an object is known as an object heap. Typically each computer program has its own object heap.
Objects comprise both data structures and operations, known collectively as methods. Methods access and manipulate data structures. Objects having identical data structures and common behavior can be grouped together into classes. Each object inherits the data structure and methods of the particular class from which it was instantiated. Further, a hierarchical inheritance relationship exists between multiple classes. For example, one class may be considered a parent of another, child class. The child class is said to be derived from the parent class and thus, inherits all of the attributes and methods of the parent class.
Object structure includes data and pointer fields. Pointers contain the addresses of other memory locations; data fields embody information or other objects. The object
10
of
FIG. 1
has an identifier field
12
, data field
14
and pointers
16
,
18
. The identifier field
12
contains processing instructions used only when the object
10
is compiled, so it is not necessarily stored with the object
10
. A dashes distinguish the identifier field
12
from information stored at run time.
In the figure, pointers
16
are represented as arrows pointing to other objects
20
. A nil value of pointer
18
is represented by an “X” within the corresponding pointer field. Items
14
are contained by the object and are referred to as internal objects, while objects
20
referenced by the object's
10
pointers are known as external objects.
The exemplary object
10
also has names
22
associated with it. Each name is a labeled pointer to the object. Since names are only used by the compiler at compile time, they do not require any storage at run time. This fact is represented by the use of dashed boxes to enclose the name pointers. Note that external objects can also contain pointers to other objects recursively, creating an object with arbitrary “depth.”
The depth of an object is determined by counting the number of pointers that must be followed to reach it, starting from a name. Thus in the figure, names
22
are at depth
0
, the object
10
is at depth
1
, and the external objects
20
are at depth
2
. For consistency, the depth attributed to the manipulation of a pointer corresponds to the depth at which the pointer is stored. Thus, manipulations of pointers
16
as shown in
FIG. 1
are considered to be at depth
1
.
Whenever a program creates a new object, available memory is reserved using a process known as memory allocation. The Java programming environment developed by Sun Microsystems is one example of a programming framework that utilizes memory allocation. Given the limited amount of memory available in such an environment, it is important to deallocate memory reserved for data no longer in use. Otherwise, system performance will suffer as available memory is consumed.
A computer program known as a garbage collector empties unused memory that has been allocated by other programs. Generally, a garbage collection algorithm carries out storage management by automatically reclaiming storage. Garbage collectors are typically activated when an object heap becomes full. A key functionality of a garbage collection algorithm involves determining if an object is no longer reachable by an executing program. A properly collectable object must be unreachable either directly or through a chain of pointers.
Thus, the garbage collector must identify pointers directly accessible to the executing program. Further, the collector must identify references contained within that object, allowing the garbage collector to transitively trace chains of pointers. When the data structure of an object is deemed unreachable, the garbage collector reclaims memory. The memory is deallocated even if it has not been explicitly designated by the program.
Specific methods for memory reclamation include reference counting, mark-scan and the copying garbage collection. In reference counting collection, as diagramed in
FIG. 2
, each external object
20
is associated with a count
24
reflecting the number of objects that point to it. Every time a new pointer implicates an external object
20
, the count
24
is incremented. Conversely, the count
24
is decremented every time an existing reference is destroyed. When the count
24
goes to zero, the object
20
and its associated count
24
are deallocated.
A variation of the reference counting scheme known as weighted reference counting removes the requirement of referencing shared memory, but some bookkeeping is still required at run time. Another variation known as lazy reference counting reduces the run-time CPU requirements by deferring deallocation operations and then combining them with allocations, but does not eliminate them entirely.
An alternative method, called mark-scan garbage collection, never explicitly deallocates external objects. Periodically, the garbage collection process marks all data blocks that can be accessed by any object. Unreachable memory is reclaimed by scanning the entire memory and deallocating unmarked elements.
Each cycle of the mark-scan algorithm sequentially operates in mark and sweep stages. In the mark stage, the collector scans through an object heap beginning at its roots, and attempts to mark objects that are still reachable from a root. An object is deemed reachable if it is referenced directly by a root or by a chain of objects reachable from a root. In the sweep stage, the collector scans through the objects and deallocates any memory reserved for objects that are unmarked as of completion of the mark stage. Some variations of mark-scan require that active program threads be halted during collection, while others operate concurrently.
Copying garbage collectors are similar to those of the mark-scan variety. However, instead of marking those items that can be reached by reference, all reachable data structures are periodically copied from one memory space into another. The first memory space can then be reclaimed in its entirety. A specific implementation of a copying garbage collector is a generational garbage collector, which partitions an object heap into new and old partitions. A generational garbage collector relies on a tendency for newer objects to cease to be used more frequently than older objects. Put another way, as an object is used over time, it becomes less and less likely that the object will cease being used.
A generational garbage collector manages an object heap by scanning through newer objects in a new partition of the heap. The collector deallocates memory for objects that are no longer in use, and move objects that live beyond a predetermined period into an old partition. Given that older objects tend to be more stable, typically no scanning of the old partition of the object heap is required.
Despite the progresses afforded by the above garbage collection techniques, obstacles to memory management remain. One particular area of concern relates to “short lived” objects. Although such objects may be used only briefly, they tend to linger and take up space in the object heap between garbage collection cycles. Further, the overhead associated with allocating and deallocating short lived objects is disproportionally high relative to “longer lived” objects.
Deallocating processes require the computer to perform certain operations that are outside of normal productive operations. These additional processes burden the overall operation of the computer. The

Affiliated with

Also associated with

Rating

Accurately determining an object's lifetime does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Accurately determining an object's lifetime, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Accurately determining an object's lifetime will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3250009