Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2000-07-31
2004-10-12
Bragdon, Reginald G. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C707S793000
Reexamination Certificate
active
06804762
ABSTRACT:
TECHNICAL FIELD
The present invention relates to garbage collection and more particularly to reclamation of allocated memory in a computing system using a dynamically tuned write barrier.
BACKGROUND
During execution of a computer program or computer application, memory is allocated to the program by the operating system to enable various operations. Once allocated, other executing processes cannot use the memory allocated to that program, i.e., memory use is exclusive. When the program has finished using a portion or object of allocated memory, it can explicitly de-allocate or release that memory. For example, the program might dispose, kill, or free the memory via a specific programming code function. Once freed, other applications or processes can use the memory. This methodology has disadvantages. One such disadvantage is that the program that releases the memory does not know whether another program has claimed that memory since it was originally allocated. Thus, the program could release memory that another program is utilizing.
In some instances, the program to which the memory was initially allocated does not release the memory, even after the program is finished using that memory. Moreover, when a program is done using a memory block or object, references to that object no longer exist. Without such a reference, that memory object cannot be reached by the application. Consequently, once the program has finished using the memory, that memory cannot be reused until it is freed by the program or reclaimed by another memory management program and then reallocated to either the initial application or process or to another application or process. Thus, allocated, yet unreachable, objects are unusable and are considered to be dead or garbage.
Typically, the processes of allocating memory objects to applications and reclaiming dead memory objects, i.e., garbage collection, are performed by a memory manager. The memory manager tracks which memory objects are currently allocated to the computer program and which objects are currently available to be allocated through a free list that keeps track of available objects. Thus, memory objects that are not on the free list are currently allocated to a computer program or application. Other memory managers do not use a free list and instead allocate memory using an increasing memory address scheme. In such a case, it becomes important to not only reclaim dead memory objects, but also compact the live objects to prevent using up all of the memory.
There are several common techniques for garbage collection. One technique is referred to as copying and relates to logically dividing the memory in half and using only one half of the memory at a time. During garbage collection, the memory manager copies all reachable objects to the other half of the memory. Following the copying of all reachable objects, the memory manager adds the entire first half of memory to the free list. Consequently, the previously used memory, that contained both the reachable objects and the garbage objects, becomes free memory and therefore contains only objects that are available to be allocated. In other words, the garbage memory has been reclaimed for later use.
Another common garbage collection technique relates to the mark-and-sweep method. The mark-and-sweep technique marks all reachable objects of memory. Each memory object reachable by a program application is marked as reached by the garbage collector. The garbage collector then sweeps the entire heap to reclaim all unmarked objects of memory by adding the unmarked objects to the free list. When the sweep phase is complete, all garbage objects are now on the free list and available to be reallocated to a computer program.
Generational garbage collection refers to operating the garbage collection on only a portion of the memory at a time. Generational garbage collection reduces pause times to the user by collecting only a portion of the memory rather than the entire memory. However, collecting only a portion of the memory has disadvantages. One such disadvantage is that pointers from old memory objects, those that are in the portion not being operated on, to new memory objects, those in the portion being operated on, are difficult to detect. In addition, the portion of the memory being operated on is constantly changing. making it difficult to detect generational pointers. For example, the ephemeral range changes each time the garbage collector is run. Further optimization is desired.
SUMMARY
In accordance with the present invention, the above and other problems are solved by the following:
In one aspect of the present invention, a method of detecting and indicating pointers in an ephemeral region of memory in a computing system is provided. The method includes monitoring stored memory for pointers; detecting if there are pointers above the ephemeral range; and if there are not pointers above the ephemeral range, then testing if a pointer is above a lower limit of the ephemeral range without testing if the pointer is also below an upper limit of the ephemeral range.
In another aspect of the present invention, a computer program product readable by a computing system and encoding instructions for a computer process for detecting and indicating pointers in an ephemeral region of memory in a computing system is provided. The computer process comprises instructions analogous to that described above.
In another aspect of the present invention, a system for detecting and indicating pointers in an ephemeral region of memory in a computing system is provided. The system includes a monitor module, a pointer module, and a lower limit module. The monitor module monitors stored memory for pointers. The pointer module detects if there are pointers above the ephemeral range. The lower limit module tests if a pointer is above a lower limit of the ephemeral range without testing if the pointer is also below an upper limit of the ephemeral range, if there are not pointers above the ephemeral range.
The invention may be implemented as a computer process, a computing system, or as an article of manufacture such as a computer program product. The computer program product may be a computer storage medium readable by a computer system and encoding a computer program of instructions for executing a computer process. The computer program product may also be a propagated signal on a carrier readable by a computing system and encoding a computer program of instructions for executing a computer process.
REFERENCES:
patent: 5842016 (1998-11-01), Toutonghi et al.
patent: 6055612 (2000-04-01), Spertus et al.
patent: 6065020 (2000-05-01), Dussud
Courtemanche, A., “MultiTrash, a Parallel Garbage Collector for MultiScheme”,Massachusetts Institute of Technology, pp. 1-47 (1986).
Jones, R. et al., “Garbage Collection: Algorithms for Automatic Dynamic Memory Mangement”,John Wiley&Sons, pp. 184-226 (1996).
Dussud Patrick H.
Harry Brian D.
Bragdon Reginald G.
Microsoft Corporation
LandOfFree
Method and system for garbage collection using a dynamically... 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 system for garbage collection using a dynamically..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for garbage collection using a dynamically... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3275194