Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

A METHOD FOR DETECTING FREE AREAS DURING GARBAGE COLLECTION, WITHOUT HAVING TO ACCESS THE COLLECTED AREA ITSELF

IP.com Disclosure Number: IPCOM000020391D
Original Publication Date: 2003-Nov-19
Included in the Prior Art Database: 2003-Nov-19
Document File: 3 page(s) / 76K

Publishing Venue

IBM

Abstract

A method is disclosed that improves the mechanism of Sweep in Mark-Sweep Garbage collectors.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 42% of the total text.

Page 1 of 3

A METHOD FOR DETECTING FREE AREAS DURING GARBAGE COLLECTION, WITHOUT HAVING TO ACCESS THE COLLECTED AREA ITSELF

Within a Mark and Sweep Garbage collection, for object oriented programs, this method provides a way for performing the Sweep phase with minimal amount of cache misses, while preserving the ability to reclaim any size of free memory. The major innovation here is the use of an additional marking utility (usually resulting in an additional data structure of a bit vector, similar is size and access techniques to the mark bits vector) that is used to mark the beginning of each free area in the heap. With this bit vector, and the existing mark and allocation bit vectors, it is possible to find and reclaim any size of unused memory, without any access to the heap itself, thus saving all cache misses that result from this extra effort of heap access.

Introduction and related art

    This method relates to the Mark/sweep garbage collector used for memory management of the heap, in programs that implement implicit Garbage collection (Such as Java*)

    Mark/Sweep garbage collector reclaims unused memory in two phases. In the initial Mark phase, all the objects reachable from the roots (stack and globals) are marked. This is done by traversing all the objects graph that is referenced from the roots, and marking each object when it is visited. In the following Sweep phase all memory chunks, that are left unmarked, are reclaimed for later reuse. Adjacent unmarked memory chunks are coalesced and reclaimed as larger chunks, that may later accommodate larger allocation requests.

    Usually the marking is done using "mark bit array", where each bit maps to an area in the heap. This area's size is small enough so that each object must start at the beginning of such area. If, for example, the smallest memory unit is 8 bytes, and all objects in the heap start on an 8 bytes boundary, than the N bit in the mark bit array is mapped to the 8*N byte of the heap. A bit N that is set to "1" in this vector, marks the start of a live object, an the 8*N byte of the heap . At the end of the mark phase all bits in the mark bit vector that map to the start of a live object is set to 1 and all the rest of the bits are set to 0.

The basic sweep algorithm

    The basic sweep algorithm examine the heap sequentially, and reclaim all objects that are not marked. This is done by looking tat the mark bit vector. Getting from a heap object (live or not) to the next object is done by moving forward by that object's size, a data which many Mark/Sweep implementations chose to located in the object itself.

The more sophisticated sweep algorithm

    The more sophisticated sweep algorithm examines the mark bit array sequentially. whenever a 1 set bit is found, its corresponding (marked) object is checked for its size, and all memory after that size and till the beginning of the next marked object (again found by the next set bit in the mark bit array) is reclaimed. This sweep algorithm...