Work stealing of partially-marked objects

Abstract

A process may utilize multiple garbage collector threads, each having the capability to steal partially-marked object references from an accessible mark stack having additional work that has yet to be processed. A partially-marked object reference may be represented as a pair of entries on a mark stack. A garbage collector thread may utilize an atomic operation to access the pair of entries in a prescribed manner to steal an unprocessed partially-marked object reference. In this manner, the workload of an overloaded garbage collector thread is offloaded to another garbage collector thread that may be idle thereby balancing the workload more evenly among multiple garbage collector threads.

What is claimed: 
     
       1. A computer-implemented method, comprising:
 storing onto a mark stack, by a first garbage collector thread, a partially-marked object reference having a pair of consecutive entries in the mark stack, one entry of the pair representing a parent object and a second entry of the pair representing a child object reference, the mark stack accessible by multiple garbage collector threads concurrently, the child object reference comprises a location of a reference of the parent object that has not been marked; 
 searching the mark stack, by a second garbage collector thread, for a partially-marked object reference, the first garbage collector thread different from the second garbage collector thread; and 
 stealing from the mark stack, by the second garbage collector thread, the partially-marked object reference by replacing the child object reference with a stolen value. 
 
     
     
       2. The computer-implemented method of  claim 1 , further comprising:
 marking, by the second garbage collector thread, objects referenced by the child object reference. 
 
     
     
       3. The computer-implemented method of  claim 1 , the searching step further comprising:
 reading the mark stack for a first entry having a parent object reference; 
 reading the mark stack for a second entry having a child object reference; and 
 determining that the first entry and the second entry form a partially-marked object reference. 
 
     
     
       4. The computer-implemented method of  claim 3 , further comprising:
 atomically replacing the second entry with a stolen value if the child object reference has not been stolen. 
 
     
     
       5. The computer-implemented method of  claim 1 , further comprising:
 reading the mark stack for a first entry having a parent object reference; 
 reading the mark stack for a second entry having a child object reference; and 
 determining that the first and second entry form a partially-marked object reference when the child object reference is contained within an address range encompassed by the parent object reference. 
 
     
     
       6. The computer-implemented method of  claim 5 , further comprising:
 atomically replacing the second entry with a stolen value if the child object reference has not been stolen. 
 
     
     
       7. The computer-implemented method of  claim 1 , further comprising:
 pushing a first place holder onto the mark stack; and 
 pushing a second place holder onto the mark stack immediately after the first place holder. 
 
     
     
       8. The computer-implemented method of  claim 7 , further comprising:
 replacing the first place holder with a parent object reference; and 
 replacing the second place holder with a child object reference. 
 
     
     
       9. A device,
 comprising: 
 at least one processor and a memory; 
 the at least one processor configured to: 
 push a first entry onto a mark stack as a place holder for a parent object reference associated with a partially-marked object reference, the mark stack including references yet to be marked; 
 push a second entry onto a mark stack as a place holder for a child object reference that is associated with a parent object reference; and 
 replace the first entry with a parent object reference and the second entry with a child object reference that is associated with the parent object reference, 
 wherein the partially-marked object reference includes a pair of consecutive entries in the mark stack, a first entry representing the parent object reference and a second entry representing the child object reference, the child object reference comprises a location of a reference of the parent object that has not been marked. 
 
     
     
       10. The device of  claim 9 , wherein the at least one processor is further configured to:
 traverse the mark stack to find a partially marked object reference. 
 
     
     
       11. The device of  claim 10 , wherein the at least one processor is further configured to:
 steal the child object reference in the second entry by replacing the second entry with a stolen value when a current read of the second entry matches a last read of the second entry. 
 
     
     
       12. The device of  claim 11 , wherein an atomic instruction is used to match a stored value of the second entry from the last read with a current value of the second entry from the current read and to replace the second entry with the stolen value. 
     
     
       13. The device of  claim 10 , wherein the at least one processor is further configured to:
 mark the second entry as being stolen when the child object reference lies with an address range of the parent object reference and the child object reference has not changed since a last read of the child object reference. 
 
     
     
       14. The device of  claim 13 , wherein an atomic operation is used to mark the second entry as being stolen. 
     
     
       15. A system, comprising:
 a plurality of processors; 
 at least one process, each process having instructions that when executed on a processor allocates objects dynamically; and 
 a garbage collector having a plurality of garbage collector threads and a plurality of mark stacks, 
 at least one mark stack including at least one partially-marked object reference, each partially-marked object reference representing objects requiring marking, each partially-marked object reference including a pair of consecutive entries in the mark stack, a first entry of the pair representing a parent object reference and a second entry of the pair representing a child object reference, each mark stack accessible by each garbage collector thread concurrently, the child object reference comprises a location of a reference of the parent object that has not been marked, 
 each garbage collector thread containing instructions that when executed on a processor removes a partially-marked object reference from any mark stack for the garbage collector thread to mark objects starting from the child object reference. 
 
     
     
       16. The system of  claim 15 , the garbage collector thread contains further instructions that when executed on a processor, performs a first read on the parent object reference and a first read on the child object reference to determine that the parent object reference and the child object reference are a partially-marked object reference, and steals the child object reference when a subsequent atomic read on the child object reference matches a stored value of the child object reference. 
     
     
       17. The system of  claim 15 , the garbage collector thread contains further instructions, that when executed on a processor, performs a first read on the parent object reference and a first read on the child object reference and when an address of the child object reference lies within an address range of the parent object reference, the child object reference is stolen. 
     
     
       18. The system of  claim 17 , the garbage collector thread steals the child object reference after determining that the child object reference has not been stolen. 
     
     
       19. The system of  claim 17 , the garbage collector thread contains an atomic instruction, that when executed on a processor, compares a stored value of the child object reference with a current value of the child object reference and when the stored value of the child object reference matches the current value of the child object references, replaces the child object reference with a stolen value. 
     
     
       20. The system of  claim 15 , wherein the garbage collector threads do not execute on a same processor concurrently.