Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2000-07-31
2003-09-16
Bragdon, Reginald G. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S170000, C707S793000
Reexamination Certificate
active
06622226
ABSTRACT:
TECHNICAL FIELD
The present invention relates to garbage collection and more particularly to reclamation of allocated memory in a computing system using a modified mark-and-sweep technique having a mark-list.
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 reached 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.
In some instances, the mark-and-sweep technique might be preferred over the copying technique because it is faster than copying, since the copying of objects and updating the references takes more time than adding a garbage block to a free list. Moreover, the mark-and-sweep technique is often more efficient since it uses the whole memory, as opposed to only half, as used in the copying technique. However, in other situations, the copying technique may be preferred due to the lack of fragmentation and in instances having a relatively small number of reached memory blocks. In yet another technique, the mark-and-sweep technique is improved by adding a defragmentation or compaction step at the end of the sweep or reclamation process.
The mark-and-sweep technique has disadvantages. One such disadvantage is that the sweep function of the mark-and-sweep technique examines every single memory block. This is time consuming if the number of reachable objects is low relative to the number of objects allocated.
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 reclaiming unused memory objects in a computing system is provided. The method includes traversing memory objects referenced by a program; marking the memory objects reached; adding the memory objects reached to a mark-list; detecting if the mark-list if full; and if the mark-list is not full, avoiding traversing the unmarked memory objects during the sweeping of the memory objects, and reclaiming the memory objects not marked.
In another aspect of the present invention, a computer program product readable by a computing system and encoding instructions for a computer process for reclaiming unused memory objects is provided. The computer process comprises instructions analogous to that described above.
In another aspect of the present invention, a system for reclaiming unused memory objects in a computing system is provided. The system includes a traverse module, a mark module, a record module, a mark-list module, a sweep module, and a reclaim module. The traverse module traverses memory objected reference by a program. The mark module marks the memory objects reached. The record module adds the memory objects reached to a mark-list. The mark-list module detects if the mark-list is full, and, if the mark-list is not full, avoiding traversing through unmarked memory objects during the sweeping of the memory objects and reclaiming the memory objects not marked.
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
patent: 6304949 (2001-10-01), Houlsdworth
Courtemanche, A.J., “MultiTrash, a Parallel Garbage Collector for MultiScheme”, pp. 1-47 (Jan. 27, 1986).
Jones, R. et al., “Garbage Collection Algorithms for Automatic Dynamic Memory Management”, pp. 184-226 (1996).
Bragdon Reginald G.
Merchant & Gould P.C.
Microsoft Corporation
LandOfFree
Method and system for using a mark-list for 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 and system for using a mark-list for garbage collection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for using a mark-list for garbage collection will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3051601