System and method for asynchronous parallel garbage collection
A system and method for asynchronously graying and blackening objects in the marking phase of parallel garbage collection. The system and method use a matrix to control a series of linked list of work to be grayed and blackened. The threads of the garbage collector are each assigned entries within the matrix upon which they may either gray an entry in the linked list or blacken and entry on the linked list. Further restrictions upon the use of the matrix allow non-garbage collection thread to asynchronously or synchronously add objects to be processed by the garbage collector.
1. A method of facilitating in a memory management system asynchronously marking objects during multi-threaded garbage collection, the method comprising:
adding to a head of a linked list an object to be worked on by a garbage collection thread, the linked list determined by iterating a row of a matrix corresponding to the garbage collection thread to find a matrix entry; and
finding work to be performed by the first thread by iterating across a column of the matrix corresponding to the garbage collection thread and updating a worked on position indicator of objects in the linked list indicated by a linked list referenced by a matrix entry.
2. The method of claim 1 , wherein the number of rows and number of columns of the matrix equals the number of garbage collection threads.
3. The method of claim 1 , wherein the garbage collection thread adds to the head of the linked list, the garbage collection thread omits matrix entries where the column corresponds to the garbage collection thread.
4. The method of claim 3 , further comprising:
adding the object to the linked list by an other than garbage collection thread, the link list referenced by a matrix entry, wherein an index to determine the matrix are equal values for both the column and the row.
5. The method of claim 4 , wherein the other than garbage collection thread is a plurality of threads, and
synchronization is performed when updating the head of a list.
6. The method of claim 1 , wherein the finding work to be performed further performs the step of:
searching for further object references in the object; and
adding the further object referenced to the head of a linked list an object to be worked on.
7. The method of claim 1 , wherein only the garbage collection thread may add objects in the link list referenced by matrix entries in the row corresponding to the garbage collection thread, and
only the garbage collection thread may find object in the link list referenced by matrix entries in the column corresponding to the garbage collection thread.
8. A memory management system asynchronously marking objects during multi-threaded garbage collection, the system comprising:
a processor operatively coupled to a memory, the processor configured to implement computer-readable code, the computer-readable code configured to:
adding to a head of a linked list an object to be worked on by a garbage collection thread, the linked list determined by iterating a row of a matrix corresponding to the garbage collection thread to find a matrix entry; and
finding work to be performed by the first thread by iterating across a column of the matrix corresponding to the garbage collection thread and updating a worked on position indicator of objects in the linked list indicated by a linked list referenced by a matrix entry.
9. The system of claim 8 , wherein the number of rows and number of columns of the matrix equals the number of garbage collection threads.
10. The system of claim 8 , wherein the garbage collection thread adds to the head of the linked list, the garbage collection thread omits matrix entries where the column corresponds to the garbage collection thread.
11. The system of claim 10 , further comprising:
adding the object to the linked list by an other than garbage collection thread, the link list referenced by a matrix entry, wherein an index to determine the matrix are equal values for both the column and the row.
12. The system of claim 8 , wherein the finding work to be performed further performs the step of:
searching for further object references in the object; and
adding the further object referenced to the head of a linked list an object to be worked on.
13. The system of claim 8 , wherein only the garbage collection thread may add objects in the link list referenced by matrix entries in the row corresponding to the garbage collection thread, and
only the garbage collection thread may find object in the link list referenced by matrix entries in the column corresponding to the garbage collection thread.
14. The system of claim 8 , wherein the other than garbage collection thread is a plurality of threads, and
synchronization is performed when updating the head of a list.
15. A computer readable medium having computer readable code stored thereon for asynchronously marking objects during multi-threaded garbage collection comprising:
a processor operatively coupled to a memory, the processor configured to implement computer-readable code, the computer-readable code configured to: adding to a head of a linked list an object to be worked on by a garbage collection thread, the linked list determined by iterating a row of a matrix corresponding to the garbage collection thread to find a matrix entry; and
finding work to be performed by the first thread by iterating across a column of the matrix corresponding to the garbage collection thread and updating a worked on position indicator of objects in the linked list indicated by a linked list referenced by a matrix entry.
16. The computer readable medium of claim 15 , wherein the number of rows and number of columns of the matrix equals the number of garbage collection threads.
17. The computer readable medium of claim 15 , wherein the garbage collection thread adds to the head of the linked list, the garbage collection thread omits matrix entries where the column corresponds to the garbage collection thread.
18. The computer readable medium of claim 17 , further comprising:
adding the object to the linked list by an other than garbage collection thread, the link list referenced by a matrix entry, wherein an index to determine the matrix are equal values for both the column and the row.
19. The computer readable medium of claim 15 , wherein the finding work to be performed further performs the step of:
searching for further object references in the object; and
adding the further object referenced to the head of a linked list an object to be worked on.
20. The computer readable medium of claim 15 , wherein only the garbage collection thread may add objects in the link list referenced by matrix entries in the row corresponding to the garbage collection thread, and
only the garbage collection thread may find object in the link list referenced by matrix entries in the column corresponding to the garbage collection thread.
21. A method of facilitating in a memory management system marking objects during multi-threaded garbage collection, the method comprising:
adding to a head of a linked list an object to be worked on by a garbage collection thread, the linked list determined by iterating a row of a matrix corresponding to the garbage collection thread to find a matrix entry;
finding work to be performed by the first thread by iterating across a column of the matrix corresponding to the garbage collection thread and updating asynchronously a worked on position indicator of objects in the linked list indicated by a linked list referenced by a matrix entry; and
finding additional work to be performed by a first thread by iterating across a column unassigned to any to any garbage collection thread and updating synchronously a worked on position indicator of objects in the link list indicated by a lined list reference by a matrix entry.
22. The method of claim 21 , wherein the number of rows of the matrix equals the number of garbage collection threads and number of columns of the matrix is greater than the number of garbage collection threads.
23. A method of facilitating in a memory management system marking objects during multi-threaded garbage collection, the method comprising:
adding to a head of a linked list an object to be worked on by a garbage collection thread, the linked list determined by iterating a row of a matrix corresponding to the garbage collection thread to find a matrix entry;
finding work to be performed by the first thread by iterating across a column of the matrix corresponding to the garbage collection thread and updating synchronously a worked on position indicator of objects in the linked list indicated by a linked list referenced by a matrix entry; and
finding, upon exhaustion of work to be performed by the first thread by iterating across a column of the matrix corresponding to the garbage collection thread, other work to be performed by the first thread by iterating across a column of the matrix corresponding to another garbage collection thread and updating synchronously a worked on position indicator of objects in the link list indicated by a linked list referenced by a matrix entry.
24. The method of claim 23 , wherein the number of rows and number of columns of the matrix equals the number of garbage collection threads.