Method of replication-based garbage collection in a multiprocessor system

• US 6,430,580 B1
• Filed: 06/25/1999
• Issued: 08/06/2002
• Est. Priority Date: 06/30/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Petrank, Erez, Kolodner, Elliot Karl, Azagury, Alain
• Primary Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US09/344,721
• Time in Patent Office: 1,138 Days
• Field of Search: 702/1-206, 714/47, 714/48, 711/154, 711/147-160, 711/200-209, 707/1-206, 709/102-108
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

Improved method of replication-based garbage collection in a multiprocessing system comprising a plurality of processors, a memory divided into a current area (from-space) used by the processors during current program execution and a reserved area (to-space), and at least a garbage collector for performing, when necessary, a garbage collection consisting in flipping the roles of the current area and reserved area after all the live objects stored in current area have been copied into the reserved area and for reclaiming the current area after the flipping operation. Several program threads (mutators) are currently running in parallel and the garbage collector performs the garbage collection in parallel with the program threads, the flipping operation being performed after the program threads have been stopped and the garbage collection has been completed. The method comprises the steps of storing, during normal program execution, a record in a local buffer allocated to each program thread each time this one updates a memory location, and adding this local buffer when full to a global list of buffers using a first wait-free synchronization operation, and, during garbage collection, removing the local buffers one by one from the global list of buffers using a second wait-free synchronization operation, and looping over records in each removed local buffer and copying the updated memory locations into the reserved area until the global list is empty.

Claims

1. In a multiprocessing system comprising a plurality of processors, a memory divided into a current area (from-space) used by said processors during current program execution and a reserved area (to-space), and at least one garbage collector for performing a garbage collection of flipping the roles of said current area and reserved area after all the live objects stored in said current area have been copied into said reserved area and for reclaiming said current area after the flipping operation, and wherein several program threads (mutators) or the like are currently running in parallel and said garbage collector performs said garbage collection in parallel with said program threads, the flipping operation being performed after said program threads have been stopped and said garbage collection has been completed;

an improved method of replication-based garbage collection comprising the following steps;

during normal program execution, each program thread storing a record in a local buffer allocated thereto each time said program thread updates a memory location, monitoring said local buffer to determine when it is full, and adding said local buffer when full to a global list of buffers using a first synchronization operation, and

during garbage collection, said collector removing the local buffers one by one from said global list of buffers using a second synchronization operation, looping over records in each removed local buffer, and copying the updated memory locations into said reserved area until said global list is empty.

2. The method according to claim 1, wherein said synchronization operation is an instruction of wait-free synchronization performed without blocking any of said program thread and said collector which initializes such an instruction.

3. The method according to claim 2, wherein said wait-free synchronization instruction is of the type <

<

compare and swap>

>

instruction.

4. The method according to claim 1, further comprising the following steps after said program threads have been stopped:

determining whether said global list is not empty, such that is contains other buffers which have been added to the global list during the removing of buffers by said collector, and

if said global list is not empty, said collector removing the new added buffers one by one from said global list, looping over the records in each removed buffer, and copying the updated memory locations into said reserved area until said global list is empty.

5. The method according to claim 2, further comprising the following steps after said program threads have been stopped:

determining whether said global list is not empty, such that is contains other buffers which have been added to the global list during the removing of buffers by said collector, and

if said global list is not empty, said collector removing the new added buffers one by one from said global list, looping over the records in each removed buffer, and copying the updated memory locations into said reserved area until said global list is empty.

6. The method according to claim 3, further comprising the following steps after said program threads have been stopped:

determining whether said global list is not empty, such that is contains other buffers which have been added to the global list during the removing of buffers by said collector, and

if said global list is not empty, said collector removing the new added buffers one by one from said global list, looping over the records in each removed buffer, and copying the updated memory locations into said reserved area until said global list is empty.

7. The method according to claim 4, wherein said step of looping over records and copying the updated memory in said reserved area is also performed with all local buffers allocated to said program threads after said global list has been emptied.

8. The method according to claim 5, wherein said step of looping over records and copying the updated memory in said reserved area is also performed with all local buffers allocated to said program threads after said global list has been emptied.

9. The method according to claim 6, wherein said step of looping over records and copying the updated memory in said reserved area is also performed with all local buffers allocated to said program threads after said global list has been emptied.

10. The method according to claim 1, wherein said step of looping over records in a local buffer consists in copying the contents of locations which have been updated from said current area to said reserved area.

11. The method according to claim 10, further comprising the step of determining whether the value copied in said reserved area is a pointer and if so, scanning the referred-to objects and updating said pointer.

12. The method according to claim 5, wherein said step of looping over records in a local buffer consists in copying the contents of locations which have been updated from said current area to said reserved area.

13. The method according to claim 12, further comprising the step of determining whether the value copied in said reserved area is a pointer and if so, scanning the referred-to objects and updating said pointer.

14. The method according to claim 6, wherein said step of looping over records in a local buffer consists in copying the contents of locations which have been updated from said current area to said reserved area.

15. The method according to claim 14, further comprising the step of determining whether the value copied in said reserved area is a pointer and if so, scanning the referred-to objects and updating said pointer.

16. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for replication-based garbage collection in a multiprocessing system comprising a plurality of processors, a memory divided into a current area (from-space) used by said processors during current program execution and a reserved area (to-space), and at least one garbage collector for performing a garbage collection of flipping the roles of said current area and reserved area after all the live objects stored in said current area have been copied into said reserved area and for reclaiming said current area after the flipping operation, and wherein several program threads (mutators) or the like are currently running in parallel and said garbage collector performs said garbage collection in parallel with said program threads, the flipping operation being performed after said program threads have been stopped and said garbage collection has been completed the improved method of replication-based garbage collection comprising the steps of:

during normal program execution, each program thread storing a record in a local buffer allocated thereto each time said program thread updates a memory location, monitoring said local buffer to determine when it is full, and adding said local buffer when full to a global list of buffers using a first synchronization operation, and

during garbage collection, said collector removing the local buffers one by one from said global list of buffers using a second synchronization operation, looping over records in each removed local buffer, and copying the updated memory locations into said reserved area until said global list is empty.