# US 12,112,195 B2 · Concurrent marking garbage collection with finger pointer

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

- Number: US 12,112,195 B2
- Document ID: US12112195B2
- Status: Granted
- Kind: B2
- Application number: 17/002,824
- Filed: 2020-08-26
- Published: 2022-03-03
- Granted: 2024-10-08
- Earliest claimed: 2020-08-26
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Michihiro Horie; Kazunori Ogata
- Web page: https://patentgrep.com/patent/US12112195B2

## CPC

- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/5038: {considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups)}
- G06F 9/505: {considering the load}
- G06F 12/0253: {Garbage collection, i.e. reclamation of unreferenced memory}
- G06F 12/0269: {Incremental or concurrent garbage collection, e.g. in real-time systems (G06F12/0261 takes precedence)}
- G06F 2209/5022: Workload threshold
- G06F 2209/508: Monitor
- G06F 2212/1024: Latency reduction
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A computer-implemented method, system, and computer program product are provided. The approach includes popping a first task from a queue of a garbage collection thread. The approach also includes identifying a second task from the popped first task, where the second task is associated with a bit of a bitmap and the bit is located at a location within the bitmap that has not yet been passed by a finger pointer. The approach also includes pushing the second task to the queue of the garbage collection thread.

## Claims

### Claim 1

A computer-implemented method comprising:
popping a first task from a queue of a garbage collection thread;
iterating a finger pointer over a bitmap, wherein:
the first task corresponds to a first bit at a first location that has been marked in the bitmap;
locations not yet passed by the finger pointer correspond to tasks which have been marked but direct children have not yet been marked; and
locations that have been passed by the finger pointer correspond to tasks which have been marked and direct children have been marked;
identifying a reference object by scanning the first task;
responsive to identifying the reference object, creating a second task from the popped first task, wherein:
creating the second task comprises marking a second bit of the bitmap;
the second task is associated with the second bit of the bitmap; and
the second bit is located at a second location within the bitmap that has not yet been passed by the finger pointer; and
responsive to identifying the bit at the second location within the bitmap that has not yet been passed by the finger pointer, pushing the second task to the queue of the garbage collection thread.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, further comprising:
determining that a first number of tasks in the queue of the garbage collection thread is equal to or smaller than a first threshold number of tasks; and
wherein pushing the second task to the queue of the garbage collection thread is responsive to determining that the first number of tasks in the queue of the garbage collection thread is equal to or smaller than the first threshold number of tasks.

### Claim 3 (depends on 2)

The computer-implemented method of claim 2, further comprising:
calculating a difference between (i) the first number of tasks in the queue of the garbage collection thread subsequent to popping the first task and (ii) a second number of tasks in the queue of the garbage collection thread subsequent to popping a task before popping the first task;
determining that the difference meets or exceeds a second threshold number of tasks; and
responsive to the difference meeting or exceeding the second threshold number of tasks, increasing the first threshold number of tasks.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1, wherein the first task is associated with a first object and the second task is associated with a second object via a reference to the second object within the first object.

### Claim 5 (depends on 1)

The computer-implemented method of claim 1, further comprising:
marking the bit of the bitmap based on the identification of the second task from the popped first task.

### Claim 6 (depends on 1)

The computer-implemented method of claim 1, wherein the garbage collection thread is of a plurality of garbage collection threads operating concurrently.

### Claim 7 (depends on 1)

The computer-implemented method of claim 1, wherein the garbage collection thread is of a garbage-first garbage collector (G1GC).

### Claim 8

A computer-implemented method comprising:
popping a first task from a queue of a garbage collection thread;
iterating a finger pointer over a bitmap, wherein:
the first task corresponds to a first bit at a first location that has been marked in the bitmap;
locations not yet passed by the finger pointer correspond to tasks which have been marked but direct children have not yet been marked; and
locations that have been passed by the finger pointer correspond to tasks which have been marked and direct children have been marked;
identifying a reference object by scanning the first task;
responsive to identifying the reference object, creating a second task and a third task from the popped first task;
marking a second bit of the bitmap for the second task and a third bit of the bitmap for the third task, wherein:
the second task is associated with the second bit of the bitmap;
the second bit is located at a second location within the bitmap that has not yet been passed by the finger pointer;
the third task is associated with the third bit of the bitmap; and
the third bit is located at a third location within the bitmap that has been passed by the finger pointer;
pushing the third task to the queue of the garbage collection thread;
determining that a first number of tasks in the queue of the garbage collection thread is equal to or smaller than a first threshold number of tasks; and
responsive to determining that the first number of tasks in the queue of the garbage collection thread is equal to or smaller than the first threshold number of tasks, pushing the second task to the queue of the garbage collection thread.

### Claim 9

A computer program product comprising:
one or more computer readable storage media, and program instructions collectively stored on the one or more computer readable storage media, the program instructions comprising:
program instructions to pop a first task from a queue of a garbage collection thread;
program instructions to iterate a finger pointer over a bitmap, wherein:
the first task corresponds to a first bit at a first location that has been marked in the bitmap;
locations not yet passed by the finger pointer correspond to tasks which have been marked but direct children have not yet been marked; and
locations that have been passed by the finger pointer correspond to tasks which have been marked and direct children have been marked;
program instructions to identify a reference object by scanning the first task;
program instructions, responsive to identifying the reference object, to create a second task from the popped first task, wherein:
program instructions to create the second task comprise program instructions to mark a second bit of the bitmap;
the second task is associated with the second bit of the bitmap; and
the second bit is located at a second location within the bitmap that has not yet been passed by the finger pointer; and
program instructions to, responsive to identifying the bit at the second location within the bitmap that has not yet been passed by the finger pointer, push the second task to the queue of the garbage collection thread.

### Claim 10 (depends on 9)

The computer program product of claim 9, further comprising:
program instructions, collectively stored on the one or more computer readable storage media, to determine that a first number of tasks in the queue of the garbage collection thread is equal to or smaller than a first threshold number of tasks; and
wherein program instructions to push the second task to the queue of the garbage collection thread is responsive to determining that the first number of tasks in the queue of the garbage collection thread is equal to or smaller than the first threshold number of tasks.

### Claim 11 (depends on 10)

The computer program product of claim 10, further comprising:
program instructions, collectively stored on the one or more computer readable storage media, to calculate a difference between (i) the first number of tasks in the queue of the garbage collection thread subsequent to popping the first task and (ii) a second number of tasks in the queue of the garbage collection thread subsequent to popping a task before popping the first task;
program instructions, collectively stored on the one or more computer readable storage media, to determine that the difference meets or exceeds a second threshold number of tasks; and
program instructions, collectively stored on the one or more computer readable storage media, to, responsive to the difference meeting or exceeding the second threshold number of tasks, increase the first threshold number of tasks.

### Claim 12 (depends on 9)

The computer program product of claim 9, wherein the first task is associated with a first object and the second task is associated with a second object via a reference to the second object within the first object.

### Claim 13 (depends on 9)

The computer program product of claim 9, further comprising:
program instructions, collectively stored on the one or more computer readable storage media, to mark the bit of the bitmap based on the identification of the second task from the popped first task.

### Claim 14 (depends on 9)

The computer program product of claim 9, wherein the garbage collection thread is of a plurality of garbage collection threads operating concurrently.

### Claim 15 (depends on 9)

The computer program product of claim 9, wherein the garbage collection thread is of a garbage-first garbage collector (G1GC).

### Claim 16

A computer program product comprising:
one or more computer readable storage media, and program instructions collectively stored on the one or more computer readable storage media, the program instructions comprising:
program instructions to pop a first task from a queue of a garbage collection thread;
program instructions to iterate a finger pointer over a bitmap, wherein:
the first task corresponds to a first bit at a first location that has been marked in the bitmap;
locations not yet passed by the finger pointer correspond to tasks which have been marked but direct children have not yet been marked; and
locations that have been passed by the finger pointer correspond to tasks which have been marked and direct children have been marked;
program instructions to identify a reference object by scanning the first task;
program instructions, responsive to identifying the reference object, create a second task and a third task from the popped first task by scanning the first task for reference objects;
program instructions to mark a second bit of the bitmap for the second task and a third bit of the bitmap for the third task, wherein:
the second task is associated with the second bit of the bitmap;
the second bit is located at a second location within the bitmap that has not yet been passed by the finger pointer;
the third task is associated with the third bit of the bitmap; and
the third bit is located at a third location within the bitmap that has been passed by the finger pointer;
program instructions to push the third task to the queue of the garbage collection thread;
program instructions to determine that a first number of tasks in the queue of the garbage collection thread is equal to or smaller than a first threshold number of tasks; and
program instructions to, responsive to determining that the first number of tasks in the queue of the garbage collection thread is equal to or smaller than the first threshold number of tasks, push the second task to the queue of the garbage collection thread.

### Claim 17

A computer system comprising:
one or more computer processors, including one or more threads, one or more computer readable storage media, and program instructions collectively stored on the one or more computer readable storage media for execution by at least one of the one or more computer processors, the program instructions comprising:
program instructions to pop a first task from a queue of a garbage collection thread;
program instructions to iterate a finger pointer over a bitmap, wherein:
the first task corresponds to a first bit at a first location that has been marked in the bitmap;
locations not yet passed by the finger pointer correspond to tasks which have been marked but direct children have not yet been marked; and
locations that have been passed by the finger pointer correspond to tasks which have been marked and direct children have been marked;
program instructions to identify a reference object by scanning the first task;
program instructions, responsive to identifying the reference object, to create a second task from the popped first task, wherein:
program instructions to create the second task comprise program instructions to mark a second bit of the bitmap;
the second task is associated with the second bit of the bitmap; and
the second bit is located at a second location within the bitmap that has not yet been passed by the finger pointer; and
program instructions to, responsive to identifying the bit at the second location within the bitmap that has not yet been passed by the finger pointer, push the second task to the queue of the garbage collection thread.

### Claim 18 (depends on 17)

The computer system of claim 17, further comprising:
program instructions, collectively stored on the one or more computer readable storage media for execution by at least one of the one or more computer processors, to determine that a first number of tasks in the queue of the garbage collection thread is equal to or smaller than a first threshold number of tasks; and
wherein program instructions to push the second task to the queue of the garbage collection thread is responsive to determining that the first number of tasks in the queue of the garbage collection thread is equal to or smaller than the first threshold number of tasks.

### Claim 19 (depends on 18)

The computer system of claim 18, further comprising:
program instructions, collectively stored on the one or more computer readable storage media for execution by at least one of the one or more computer processors, to calculate a difference between (i) the first number of tasks in the queue of the garbage collection thread subsequent to popping the first task and (ii) a second number of tasks in the queue of the garbage collection thread subsequent to popping a task before popping the first task;
program instructions, collectively stored on the one or more computer readable storage media for execution by at least one of the one or more computer processors, to determine that the difference meets or exceeds a second threshold number of tasks; and
program instructions, collectively stored on the one or more computer readable storage media for execution by at least one of the one or more computer processors, to, responsive to the difference meeting or exceeding the second threshold number of tasks, increase the first threshold number of tasks.

### Claim 20 (depends on 17)

The computer system of claim 17, wherein the first task is associated with a first object and the second task is associated with a second object via a reference to the second object within the first object.

### Claim 21 (depends on 17)

The computer system of claim 17, further comprising:
program instructions, collectively stored on the one or more computer readable storage media for execution by at least one of the one or more computer processors, to mark the bit of the bitmap based on the identification of the second task from the popped first task.

### Claim 22 (depends on 17)

The computer system of claim 17, wherein the garbage collection thread is of a plurality of garbage collection threads operating concurrently.

### Claim 23 (depends on 17)

The computer system of claim 17, wherein the garbage collection thread is of a garbage-first garbage collector (G1GC).