Patent US6289360B1 successfully refreshed from Google Patents.
US6289360B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for eliminating synchronization between sweep and allocate in a concurrent garbage collector
Assignee: International Business Machines Corp
•
Filing: 1998-10-07
•
Granted: 2001-09-11
•
Expires: 2018-10-07
Abstract
Abstract A computer-implemented method for eliminating synchronization between sweep and allocate in respect of a newly created object in a concurrent garbage collector for a heap implemented in shared memory having mark and sweep phases. In a first collection cycle, a first attribute is associated with objects believed to be reachable and a second attribute is associated with objects believed to be unreachable, whilst for each successive collection cycle, the roles of the first and second attributes are exchanged. In accordance with conventional mark-sweep garbage collectors, the attribute is a color: usually Black and White for objects which are believed to be reachable and unreachable, respectively. Exchanging the colors for each collection cycle eliminates the overhead in synchronizing the color marking of a new object depending on whether it is located in an area of the heap that has already been swept or has yet to be swept.
Inventors
- 👤 Elliot K. Kolodner
- 👤 Ethan Lewis
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 19:19
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/0223; G06F12/023; G06F12/0253; G06F12/0269; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99956; Y10S707/99957
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
128 words
A computer implemented method for eliminating synchronization between a garbage collector thread performing a sweep and a mutator thread allocating a new object, wherein there are at least two mutator threads, in a concurrent garbage collector for a heap implemented in shared memory having mark and sweep phases, without requiring more than one thread to stop simultaneously, the method comprising the steps of: (a) in a first collection cycle, associating a first attribute with objects believed to be reachable and associating a second attribute with objects believed to be unreachable, (b) in a successive collection cycle, associating said first attribute with objects believed to be unreachable and associating said second attribute with objects believed to be reachable, and (c) repeating steps (a) and (b) for all successive cycles.
Claim 2
Dependent Claim
128 words
A computer implemented method for eliminating synchronization between a garbage collector thread performing a sweep and a mutator thread allocating a new object, wherein there are at least two mutator threads, in a concurrent garbage collector for a heap implemented in shared memory having mark and sweep phases, without requiring more than one thread to stop simultaneously, the method comprising the steps of: (a) in a first collection cycle, associating a first attribute with objects believed to be reachable and associating a second attribute with objects believed to be unreachable, (b) in a successive collection cycle, associating said first attribute with objects believed to be unreachable and associating said second attribute with objects believed to be reachable, and (c) repeating steps (a) and (b) for all successive cycles.
Claim 3
Dependent Claim
15 words
The method according to claim 1 , wherein the first and second attributes are colors.
Claim 4
Dependent Claim
26 words
The method according to claim 2 , wherein the first and second colors are assigned using respective variables whose values are exchanged during alternate collection cycles.
Claim 5
Dependent Claim
22 words
The method according to claim 3 , wherein said values are exchanged towards the beginning or the end of each collection cycle.
Claim 6
Dependent Claim
41 words
The method according to claim 1 , further including the steps of: (d) employing a separate allocation value to mark newly allocated objects for each mutator thread, and (e) changing the allocation value at an appropriate point in the collection cycle.
Claim 7
Dependent Claim
24 words
The method according to claim 5 , wherein the appropriate point in the collection cycle is during the mark phase of the collection cycle.
Claim 8
Dependent Claim
40 words
The method according to claim 5 , wherein said appropriate point in the collection cycle is chosen so that each mutator thread starts marking newly allocated objects as late as possible in the collection cycle thereby eliminating some floating garbage.
Claim 9
Dependent Claim
14 words
The method according to claim 7 , wherein the allocation value is a color.
Claim 10
Dependent Claim
16 words
The method according to claim 1 , wherein the garbage collector is an on-the-fly garbage collector.
Claim 11
Dependent Claim
44 words
The method according to claim 1 , wherein the garbage collector uses an algorithm characterized in that: a status variable is changed during the collection cycle, and actions taken by the mutator threads when updating and allocating an object may depend on that status.
Claim 12
Dependent Claim
42 words
The method according to claim 1 , wherein the algorithm is characterized in that: no coordination with the garbage collector is required when a reference to an object in the heap is added or updated to, or removed from, a mutator's stack.
Claim 13
Dependent Claim
42 words
The method according to claim 10 , wherein the algorithm is characterized in that: no coordination with the garbage collector is required when a reference to an object in the heap is added or updated to, or removed from, a mutator's stack.
Claim 14
Dependent Claim
54 words
The method according to claim 11 , wherein the algorithm is further characterized in that: the collector thread has a status variable which only it can modify but which can be read by all the mutator threads, and each program thread has a respective status variable which can be read by the collector thread.
Claim 15
Dependent Claim
15 words
The method according to claim 1 , wherein the garbage collector has multiple collector threads.
Claim 16
Dependent Claim
27 words
The method according to claim 5 , wherein each mutator thread assigns to a new object an attribute whose value is stored in a respective allocation variable.
Claim 17
Dependent Claim
27 words
The method according to claim 5 , wherein each mutator thread assigns to a new object an attribute whose value is stored in a global allocation variable.
Claim 18
Dependent Claim
21 words
The method according to claim 1 , wherein one or more mutator threads intermittently takes on a rôle of garbage collection.
Claim 19
Dependent Claim
132 words
A program product, comprising: a program configured to perform a method for eliminating synchronization between a garbage collector thread performing a sweep and a mutator thread allocating a new object, wherein there are at least two mutator threads, in a concurrent garbage collector for a heap implemented in shared memory having mark and sweep phases, without requiring more than one thread to stop simultaneously, the method comprising: (a) in a first collection cycle, associating a first attribute with objects believed to be reachable and associating a second attribute with objects believed to be unreachable, (b) in a successive collection cycle, associating said first attribute with objects believed to be unreachable and associating said second attribute with objects believed to be reachable, and (c) repeating steps (a) and (b) for all successive cycles.
Claim 20
Dependent Claim
132 words
A program product, comprising: a program configured to perform a method for eliminating synchronization between a garbage collector thread performing a sweep and a mutator thread allocating a new object, wherein there are at least two mutator threads, in a concurrent garbage collector for a heap implemented in shared memory having mark and sweep phases, without requiring more than one thread to stop simultaneously, the method comprising: (a) in a first collection cycle, associating a first attribute with objects believed to be reachable and associating a second attribute with objects believed to be unreachable, (b) in a successive collection cycle, associating said first attribute with objects believed to be unreachable and associating said second attribute with objects believed to be reachable, and (c) repeating steps (a) and (b) for all successive cycles.
Claim 21
Dependent Claim
147 words
A computer implemented program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for eliminating synchronization between a garbage collector thread performing a sweep and a mutator thread allocating a new object, wherein there are at least two mutator threads, in a concurrent garbage collector for a heap implemented in shared memory having mark and sweep phases, without requiring more than one thread to stop simultaneously, the method comprising the steps of: (a) in a first collection cycle, associating a first attribute with objects believed to be reachable and associating a second attribute with objects believed to be unreachable, (b) in a successive collection cycle, associating said first attribute with objects believed to be unreachable and associating said second attribute with objects believed to be reachable, and (c) repeating steps (a) and (b) for all successive cycles.
Claim 22
Dependent Claim
147 words
A computer implemented program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for eliminating synchronization between a garbage collector thread performing a sweep and a mutator thread allocating a new object, wherein there are at least two mutator threads, in a concurrent garbage collector for a heap implemented in shared memory having mark and sweep phases, without requiring more than one thread to stop simultaneously, the method comprising the steps of: (a) in a first collection cycle, associating a first attribute with objects believed to be reachable and associating a second attribute with objects believed to be unreachable, (b) in a successive collection cycle, associating said first attribute with objects believed to be unreachable and associating said second attribute with objects believed to be reachable, and (c) repeating steps (a) and (b) for all successive cycles.
Claim 23
Dependent Claim
148 words
A computer implemented computer program product comprising a computer useable medium having computer readable program code embodied therein for eliminating synchronization between a garbage collector thread performing a sweep and a mutator thread allocating a new object, wherein there are at least two mutator threads, in a concurrent garbage collector for a heap implemented in shared memory having mark and sweep phases, without requiring more than one thread to stop simultaneously, the computer program product comprising: computer readable program code for causing the computer to associate a first attribute with objects believed to be reachable and to associate a second attribute with objects believed to be unreachable in a first collection cycle, computer readable program code for causing the computer to associate said first attribute with objects believed to be unreachable and to associate said second attribute with objects believed to be reachable in a successive collection cycle.
Claim 24
Dependent Claim
148 words
A computer implemented computer program product comprising a computer useable medium having computer readable program code embodied therein for eliminating synchronization between a garbage collector thread performing a sweep and a mutator thread allocating a new object, wherein there are at least two mutator threads, in a concurrent garbage collector for a heap implemented in shared memory having mark and sweep phases, without requiring more than one thread to stop simultaneously, the computer program product comprising: computer readable program code for causing the computer to associate a first attribute with objects believed to be reachable and to associate a second attribute with objects believed to be unreachable in a first collection cycle, computer readable program code for causing the computer to associate said first attribute with objects believed to be unreachable and to associate said second attribute with objects believed to be reachable in a successive collection cycle.
Claim 25
Dependent Claim
44 words
The method according to claim 1 , wherein: the at least two mutator threads read from and write to a shared memory, the shared memory is not sequentially consistent, and the mark sweep collector operates to avoid implicit synchronization which would otherwise be required.
References Cited (Backward Citations)
US5761670A
Cited
US5819299A
Cited
US5991779A
Cited
US6052699A
Cited
US5848423A
Cited
US5930807A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-09-10 | 2005-03-12 | 2005-09-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-09-10 | 2009-03-12 | 2009-09-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-09-10 | 2013-03-12 | 2013-09-11 | $7700.00 | Window Closed / Lapsed |