Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1997-05-30
2001-03-06
Black, Thomas G. (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06199075
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of computer memory allocation and deallocation. Specifically, this invention is a new and useful method, apparatus, system, and computer program product for using generational garbage collection techniques to automatically reclaim garbage nodes from a heap memory shared by a plurality of processing units.
2. Background
Memory allocation and deallocation techniques have become very important in structured programming and object oriented programming methodologies. Memory allocated from a heap can be used to store information. Often this information is an instantiated object within an object-oriented paradigm. An allocated portion of heap memory is a node. The subsequently described techniques apply to both nodes that contain data and nodes that are instantiated objects. These nodes are explicitly allocated by a program. However, many modem systems use heap-memory garbage collection techniques to recover previously allocated nodes that are no longer used. Additionally, modem computers often have multiple processing units that can access a shared heap memory, with each processing unit allocating nodes in the shared heap (thus mutating the shared heap) and each processing unit being capable of performing garbage collection on the shared heap.
Introduction to Garbage Collection
Computer memory is a resource. Programs cause a computer to perform operations (to execute) based on instructions stored in memory. Executing programs also use memory to store information. This information is often organized into memory resident data structures. These data structures are often linked together by pointers from one structure to another and are often referenced through pointers in static, register and stack variable storage.
Executing programs often need memory for a purpose that extends for a limited period of time. For example, a program may allocate memory to hold information, store the information into the allocated memory, operate on the stored information to produce a result, and then have no further need of the stored information. Once the program no longer needs the stored information, the allocated memory can be released for later reuse.
Modern programming languages provide facilities for static, stack and heap allocation of memory. Static allocation binds variables to storage locations at compile and/or link time. Stack allocation pushes an activation frame on the processing unit's stack when a program block prepares to execute. This activation frame contains storage for variables within the scope of execution for the program block executing in the processing unit. Once the program block completes, the activation frame is popped from stack. Variables stored in the activation frame are not saved from one activation of the block to the next. Heap allocation allows memory for variables to be allocated and deallocated in any order and these variables can outlive the procedure (or block) that created them. Once memory is deallocated it is available for reallocation for another use.
A “node” is an area of memory allocated from a heap. Nodes are accessed through pointers. A direct (or simple) pointer is the node's address in the heap. An indirect pointer (sometimes called a “handle”) points to an address in memory that contains the address of the node. More complex pointers exist. Indirect pointers allow nodes to be moved in the heap without needing to update the occurrences of the handle.
The “root set” is a set of node references such that the referenced nodes must be retained regardless of the state of the heap. A node is reachable if the node is in the root set, or referenced by a reachable node. The “reference set” is the set of node references contained in a node. A memory leak occurs when a node becomes unreachable from the root set and is never reclaimed. A memory leak reduces the amount of heap memory available to the program. A garbage node is a node that becomes unreachable from the root set and can be reclaimed.
Heap memory can be used by invoking explicit node allocation and deallocation procedures. However, although a programmer knows when a new node is required, it is often difficult for the programmer to know when a node is no longer reachable. Thus, problems may occur when programmers explicitly deallocate nodes. One of these problems is that it is very difficult to debug memory leaks. Often the design of the application being programmed obfuscates when the programmer can explicitly deallocate memory. Additionally, when one portion of a program is ready to deallocate memory, it must be certain that no other portion of the program will use that memory. Thus, in object oriented programming (OOP) languages, multiple modules must closely cooperate in the memory management process. This, contrary to OOP programming methodology, leads to tight binding between supposedly independent modules.
These difficulties are reduced if the programmer need not explicitly deallocate memory. Automatic garbage collection methods scan memory for referenced nodes and recover garbage nodes—but at a cost. The process of finding and deallocating garbage nodes takes processor resources. Balancing the impact of the garbage collection process on an executing program is important because the primary function of the program may require timely operation, uninterrupted user interaction or be subject to some other real-time constraint.
A mutator program changes (mutates) the connectivity of the graph of live nodes in the heap. One skilled in the art will recognize that in the context of this invention, the term “mutation” includes any activity that accesses the nodes in the heap for purposes other than garbage collection. In a system using garbage collection, nodes are allocated from the heap as memory is needed by the mutator program. These nodes are not initially reclaimed when they are no longer needed. Instead, when a memory allocation attempt fails or in response to some condition (for example, on expiration of a clock or counter), the garbage collection process is automatically invoked and unused memory allocated to garbage nodes is reclaimed for subsequent reuse.
Some garbage collection methods copy (or scavenge) nodes (that is, these methods relocate nodes that appear to be alive from one location in the heap to another location). These methods require a mechanism that allows existing pointers to the original location of the node to be used to access the relocated node. These mechanisms include (among others) updating existing pointers to the node's original location and providing indirect pointers to the new location of the node.
Generational Garbage Collection
Generational garbage collection techniques use the observation that many nodes allocated from the heap are only used for a short period of time. These nodes are allocated for a specific short-term purpose, used for the purpose, and then can be deallocated for possible later reuse. Thus, garbage collection algorithms that concentrate on younger nodes are more efficient than those that process all nodes identically because fewer nodes need to be examined during the garbage collection process.
Generational garbage collection algorithms separate nodes into two or more areas in the heap depending on the node's age. Each area is a generation. Nodes are first allocated from the creation area within the youngest generation and are copied to the older generation if the node survives long enough (“long enough” is often until a subsequent scavenge operation). These garbage collection algorithms concentrate on reclaiming storage from the youngest generation area where most of the garbage is found. Generally, the number of live nodes in the youngest generation is significantly less than the number of live nodes in the other generation areas so that the time required to scavenge nodes in the youngest generation is less than the time required to scavenge the other generation areas. A scavenge operation of the newer generation is termed a minor collec
Ungar David M.
Wolczko Mario I.
Black Thomas G.
Coby Frantz
Park & Vaughan LLP
Sun Microsystems Inc.
LandOfFree
Method and apparatus for generational garbage collection of... 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 generational garbage collection of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generational garbage collection of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2452915