Mostly concurrent compaction in a garbage collection system
First Claim
1. A method for relocating objects allocated to a program, comprising:
- marking regions of memory in which a pointer is modified by said program, concurrent with execution of said program;
identifying a first set of variables pointing to objects in a subset of memory, concurrent with execution of said program;
suspending execution of said program;
identifying, while said execution of said program is suspended, a second set of variables pointing to said objects in said subset of memory, said second set of variables contained in said marked regions of memory;
modifying, while said execution of said program is suspended, said first set of variables and said second set of variables to point to locations outside of said subset of memory;
copying, while said execution of said program is suspended, said objects in said subset of memory to said locations outside of said subset of memory; and
restarting execution of said program.
2 Assignments
0 Petitions
Accused Products
Abstract
A system for mostly concurrent compaction in a garbage collection system is disclosed. Objects that have been allocated to a program are relocated by first identifying those variables pointing to a selected set of objects that are in use within a subset of memory. As these pointers are identified, they are added to a data structure. The selection of the objects, identification of the pointers, and addition of the pointers to the data structure may all be performed concurrently with execution of the program. At the same time, a write barrier marks as “dirty” those memory regions in which one or more pointers are modified by the program. A number of locations outside the subset of memory are reserved to be used to store the selected objects. Execution of the program is then suspended. The memory regions marked as “dirty” are examined to identify any further variables pointing to the selected objects. Any such identified variables are added to the data structure. Those variables contained in the data structure that continue to point to the selected objects are modified to point to corresponding locations outside of the subset of memory. The selected set of objects is then copied to the locations outside of the subset of memory, the subset of memory is returned to the free list, and the program is restarted.
100 Citations
44 Claims
-
1. A method for relocating objects allocated to a program, comprising:
-
marking regions of memory in which a pointer is modified by said program, concurrent with execution of said program;
identifying a first set of variables pointing to objects in a subset of memory, concurrent with execution of said program;
suspending execution of said program;
identifying, while said execution of said program is suspended, a second set of variables pointing to said objects in said subset of memory, said second set of variables contained in said marked regions of memory;
modifying, while said execution of said program is suspended, said first set of variables and said second set of variables to point to locations outside of said subset of memory;
copying, while said execution of said program is suspended, said objects in said subset of memory to said locations outside of said subset of memory; and
restarting execution of said program. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A system for relocating objects allocated to a program, said system including a computer readable memory having one or more computer instructions stored thereon, said instructions comprising:
-
instructions operative to mark regions of memory in which a pointer is modified by said program, concurrent with execution of said program;
instructions operative to identify a first set of variables pointing to objects in a subset of memory, concurrent with execution of said program;
instructions operative to suspend execution of said program;
instructions operative to identify, while said execution of said program is suspended, a second set of variables pointing to said objects in said subset of memory, said second set of variables contained in said marked regions of memory;
instructions operative to modify, while said execution of said program is suspended, said first set of variables and said second set of variables to point to locations outside of said subset of memory;
instructions operative to copy, while said execution of said program is suspended, said objects in said subset of memory to said locations outside of said subset of memory; and
instructions operative to restart execution of said program. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28)
-
-
29. A computer program product including a computer readable medium, said computer readable medium having a computer program stored thereon, said program for relocating objects allocated to a user program, said program comprising:
-
program code for marking regions of memory in which a pointer is modified by said user program, concurrent with execution of said user program;
program code for identifying a first set of variables pointing to objects in a subset of memory, concurrent with execution of said user program;
program code for suspending execution of said user program;
program code for identifying, while said execution of said user program is suspended, a second set of variables pointing to said objects in said subset of memory, said second set of variables contained in said marked regions of memory;
program code for modifying, while said execution of said user program is suspended, said first set of variables and said second set of variables to point to locations outside of said subset of memory;
program code for copying, while said execution of said user program is suspended, said objects in said subset of memory to said locations outside of said subset of memory; and
program code for restarting execution of said user program. - View Dependent Claims (30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42)
-
-
43. A computer data signal embodied in a carrier wave, said computer data signal including a computer program, said computer program for relocating objects allocated to a user program, said computer program comprising:
-
program code for marking regions of memory in which a pointer is modified by said user program, concurrent with execution of said user program;
program code for identifying a first set of variables pointing to objects in a subset of memory, concurrent with execution of said user program;
program code for suspending execution of said user program;
program code for identifying, while said execution of said user program is suspended, a second set of variables pointing to said objects in said subset of memory, said second set of variables contained in said marked regions of memory;
program code for modifying, while said execution of said user program is suspended, said first set of variables and said second set of variables to point to locations outside of said subset of memory;
program code for copying, while said execution of said user program is suspended, said objects in said subset of memory to said locations outside of said subset of memory; and
program code for restarting execution of said user program.
-
-
44. A system for relocating objects allocated to a user program, comprising:
-
means for marking regions of memory in which a pointer is modified by said user program, concurrent with execution of said user program;
means for identifying a first set of variables pointing to objects in a subset of memory, concurrent with execution of said user program;
means for suspending execution of said user program;
means for identifying, while said execution of said user program is suspended, a second set of variables pointing to said objects in said subset of memory, said second set of variables contained in said marked regions of memory;
means for modifying, while said execution of said user program is suspended, said first set of variables and said second set of variables to point to locations outside of said subset of memory;
means for copying, while said execution of said user program is suspended, said objects in said subset of memory to said locations outside of said subset of memory; and
means for restarting execution of said user program.
-
Specification