# US 2009/0276478 A1 · Method and system for hybrid garbage collection of multi-tasking systems

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2009/0276478 A1
- Document ID: US20090276478A1
- Status: Published application
- Kind: A1
- Application number: 12/112,978
- Filed: 2008-04-30
- Published: 2009-11-05
- Earliest claimed: 2008-04-30
- Assignees: Sun Microsystems, Inc.
- Inventors: Sunil Soman; Laurent Philippe Daynes
- Web page: https://patentgrep.com/patent/US20090276478A1

## CPC

- G06F 12/0276: {Generational garbage collection}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

In general, the invention relates to a method for garbage collection. The method includes examining old regions to obtain a mark bitmap, a connectivity matrix, and fragmentation information, where the mark bitmap describes marked words and unmarked words for the old regions. The method further includes identifying a fragmented region in the old regions based on the fragmentation information, where the fragmented region includes at least one of the marked words. The method further includes copying the at least one of the marked words to a new region allocated from a pool of free regions, designating each of the unmarked words not in the fragmented region as free, adjusting a cross-region reference to the fragmented region in the marked words to point to the new region based on the connectivity matrix, and adding the fragmented region to the pool of free regions.

## Claims

### Claim 1

A method for garbage collection comprising:
examining a plurality of old regions to obtain a mark bitmap, a connectivity matrix, and fragmentation information, wherein the mark bitmap describes a plurality of marked words for the plurality of old regions and a plurality of unmarked words for the plurality of old regions;
identifying a fragmented region in the plurality of old regions based on the fragmentation information, wherein the fragmented region comprises at least one of the plurality of marked words;
copying the at least one of the plurality of marked words to a new region allocated from a pool of free regions;
designating each of the plurality of unmarked words not in the fragmented region as free;
adjusting a cross-region reference to the fragmented region in the plurality of marked words to point to the new region based on the connectivity matrix; and
adding the fragmented region to the pool of free regions.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
after copying the at least one of the plurality of marked words to the new region, replacing the at least one of the plurality of marked words in the fragmented region with a forwarding pointer to the new region.

### Claim 3 (depends on 2)

The method of claim 2, wherein the cross-region reference is adjusted based on the forwarding pointer.

### Claim 4 (depends on 1)

The method of claim 1, wherein an old generation of an application comprises the plurality of old regions, wherein the application is one of a plurality of applications.

### Claim 5 (depends on 4)

The method of claim 4, wherein examining the plurality of old regions comprises:
obtaining a root for the application;
examining a plurality of live objects based on the root to obtain the mark bitmap and the connectivity matrix; and
examining the plurality of unmarked words to obtain the fragmentation information.

### Claim 6 (depends on 4)

The method of claim 4, wherein the plurality of unmarked words not in the fragmented region designated as free are only available to the application, and wherein the fragmented region added to the pool of free regions is available to each of the plurality of applications.

### Claim 7 (depends on 1)

The method of claim 1, wherein the fragmented region is identified based on the fragmentation information when a proportion of live data in the fragmented region satisfies a specified threshold.

### Claim 8 (depends on 1)

The method of claim 1, wherein the fragmented region is identified based on the fragmentation information when an average size of a continuous area of dead space in the fragmented region and a proportion of live data in the fragmented region satisfy specified thresholds.

### Claim 9

A system for garbage collection comprising:
an old generation pool comprising memory for use in an old generation of an application;
a garbage collector configured to:
examine a plurality of old regions in the old generation to obtain a mark bitmap, a connectivity matrix, and fragmentation information, wherein the mark bitmap describes a plurality of marked words for the plurality of old regions and a plurality of unmarked words for the plurality of old regions;
identify a fragmented region in the plurality of old regions based on the fragmentation information, wherein the fragmented region comprises at least one of the plurality of marked words;
copy the at least one of the plurality of marked words to a new region allocated from a pool of free regions;
designate each of the plurality of unmarked words not in the fragmented region as free;
adjust a cross-region reference to the fragmented region in the plurality of marked words to point to the new region based on the connectivity matrix; and
add the fragmented region to the pool of free regions.

### Claim 10 (depends on 9)

The system of claim 9, wherein the garbage collector is further configured to, after copying the at least one of the plurality of marked words to the new region, replace the at least one of the plurality of marked words in the fragmented region with a forwarding pointer to the new region.

### Claim 11 (depends on 10)

The system of claim 10, wherein the cross-region reference is adjusted based on the forwarding pointer.

### Claim 12 (depends on 9)

The system of claim 9, wherein examining the plurality of old regions comprises:
obtaining a root for the application;
examining a plurality of live objects based on the root to obtain the mark bitmap and the connectivity matrix; and
examining the plurality of unmarked words to obtain the fragmentation information.

### Claim 13 (depends on 9)

The system of claim 9, wherein the fragmented region is identified based on the fragmentation information when a proportion of live data in the fragmented region satisfies a specified threshold.

### Claim 14 (depends on 9)

The system of claim 9, wherein the fragmented region is identified based on the fragmentation information when an average size of a continuous area of dead space in the fragmented region and a proportion of live data in the fragmented region satisfy specified thresholds.

### Claim 15 (depends on 9)

The system of claim 9, wherein the plurality of unmarked words not in the fragmented region designated as free are only available to the application, and wherein the fragmented region added to the pool of free regions is available to each of a plurality of applications, wherein the application is one of the plurality of applications.

### Claim 16

A computer readable medium comprising executable instructions for garbage collection in a multitasking environment, wherein the executable instructions comprise instructions to:
examine a plurality of old regions to obtain a mark bitmap, a connectivity matrix, and fragmentation information, wherein the mark bitmap describes a plurality of marked words for the plurality of old regions and a plurality of unmarked words for the plurality of old regions;
identify a fragmented region in the plurality of old regions based on the fragmentation information, wherein the fragmented region comprises at least one of the plurality of marked words;
copy the at least one of the plurality of marked words to a new region allocated from a pool of free regions;
designate each of the plurality of unmarked words not in the fragmented region as free;
adjust a cross-region reference to the fragmented region in the plurality of marked words to point to the new region based on the connectivity matrix; and
add the fragmented region to the pool of free regions.

### Claim 17 (depends on 16)

The computer readable medium of claim 16, wherein an old generation of an application comprises the plurality of old regions, wherein the application is one of a plurality of applications.

### Claim 18 (depends on 17)

The computer readable medium of claim 17, wherein the plurality of unmarked words not in the fragmented region designated as free are only available to the application, and wherein the fragmented region added to the pool of free regions is available to each of the plurality of applications.

### Claim 19 (depends on 16)

The computer readable medium of claim 16, wherein the fragmented region is identified based on the fragmentation information when a proportion of live data in the fragmented region satisfies a specified threshold.

### Claim 20 (depends on 16)

The computer readable medium of claim 16, wherein the fragmented region is identified based on the fragmentation information when an average size of a continuous area of dead space in the fragmented region and a proportion of live data in the fragmented region satisfy specified thresholds.
