US5355483A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Asynchronous garbage collection
Assignee: Next Software Inc
•
Filing: 1991-07-18
•
Granted: 1994-10-11
•
Expires: 2011-07-18
Abstract
Abstract The present invention consists of a new type of garbage collector, one that runs in a different process being scanned. With this method, the process being collected communicates its memory state ("a memory snapshot") to a garbage collecting process (GC), and the GC process scans the memory and sends back the information about garbage. As a result, the present invention permits garbage collection to be performed asynchronously. The process being scanned for garbage is interrupted only briefly, to obtain the memory snapshot. The process then runs without interruption while the garbage collection is being performed. The present invention makes the assumption that if an object is garbage at the time of the memory snapshot it remains garbage any time later, since new pointers to that object cannot be created during asynchronous collection. The method further considers the case where the results of a cache computation is a collectable object itself. The method includes keeping a list while a collection is in progress of all the objects being given away from the cache. When an object is received as garbage from the GC, it is only freed if it is not on the list. The garbage collecting process is performed using a conservative scan. The garbage collector finds out if an object is garbage by scanning the memory address space and comparing the value found in each scanned memory address to see if the value matches the candidate for garbage. If no match is found, this means that the candidate for garbage is not referenced and therefore, is garbage.
Inventors
- 👤 Bertrand Serlet
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 08:21
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/0223; G06F12/023; G06F12/0253; G06F12/0269; G06F2212/00; G06F2212/70; G06F2212/702
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
140 words
A method for identifying free memory address locations in a computer system comprising the steps of: executing a first process in said computer system that references a first collectible memory area in said computer system, said first collectible memory area having allocated and unallocated memory address locations; executing a second process in said computer that identifies free memory address locations; transferring a first image of a memory state of said first collectible memory area of said first process to said second process; scanning each address in said first image by said second process to determine if said address is referenced; adding by said second process each address of said first image that is not referenced to a list of unallocated memory addresses; transferring by said second process said list of unallocated addresses from said second process to said first process.
Claim 2
Independent Claim
140 words
A method for identifying free memory address locations in a computer system comprising the steps of: executing a first process in said computer system that references a first collectible memory area in said computer system, said first collectible memory area having allocated and unallocated memory address locations; executing a second process in said computer that identifies free memory address locations; transferring a first image of a memory state of said first collectible memory area of said first process to said second process; scanning each address in said first image by said second process to determine if said address is referenced; adding by said second process each address of said first image that is not referenced to a list of unallocated memory addresses; transferring by said second process said list of unallocated addresses from said second process to said first process.
Claim 3
Dependent Claim
15 words
The method of claim 1 wherein said first process is executed on a first processor.
Claim 4
Dependent Claim
20 words
The method of claim 2 wherein said second process is executed concurrently with said first process on said first processor.
Claim 5
Dependent Claim
15 words
The method of claim 2 wherein said second process is executed on a second processor.
Claim 6
Dependent Claim
16 words
The method of claim 1 wherein said first process and said second process are executed asynchronously.
Claim 7
Dependent Claim
102 words
The method of claim 1 further including the steps of: executing in said computer system a third process that references a second collectible memory area having allocated and unallocated memory address locations; transferring a second image of a memory state of said second collectible memory of said third process to said second process; scanning each address in said second image by said second process to determine if said address is referenced; adding each address of said second image that is not referenced to said list of unallocated addresses; transferring said list of unallocated addresses from said second process to said third process.
Claim 8
Dependent Claim
76 words
The method of claim 1 wherein said first collectible memory area contains cache pointers further including the steps of: disguising said cache pointers by said computer system by changing the value of said cache pointers; generating a table of said cache pointers by said computer system; comparing said list of unallocated memory addresses with said table of said cache pointers; adding an object to said list of unallocated addresses that is not found in said table.
Claim 9
Dependent Claim
22 words
The method of claim 7 wherein said step of disguising said cache pointer is accomplished by adding 1 to said cache pointer.
Claim 10
Independent Claim
194 words
A method for identifying free memory address locations in a computer system comprising the steps of: executing in said computer system a first process that references a first collectible memory area in said computer system, said first collectible memory area having allocated and unallocated memory address locations and pointers to cache in said computer system; executing in said computer system a second process that identifies free memory address locations; disguising said cache pointers by said computer system by changing the value of said cache pointers; generating a table of said cache pointers by said computer system; transferring a first image of a memory state of said first collectible memory area of said first process to said second process; scanning each address in said first image by said second process to determine if said address is referenced; adding each address of said first image that is not referenced to a list of "free" addresses; transferring said list of "free" addresses from said second process to said first process; comparing said list of "free" memory addresses with said table of said cache pointers; freeing an object on said list that is not found in said table.
Claim 11
Independent Claim
194 words
A method for identifying free memory address locations in a computer system comprising the steps of: executing in said computer system a first process that references a first collectible memory area in said computer system, said first collectible memory area having allocated and unallocated memory address locations and pointers to cache in said computer system; executing in said computer system a second process that identifies free memory address locations; disguising said cache pointers by said computer system by changing the value of said cache pointers; generating a table of said cache pointers by said computer system; transferring a first image of a memory state of said first collectible memory area of said first process to said second process; scanning each address in said first image by said second process to determine if said address is referenced; adding each address of said first image that is not referenced to a list of "free" addresses; transferring said list of "free" addresses from said second process to said first process; comparing said list of "free" memory addresses with said table of said cache pointers; freeing an object on said list that is not found in said table.
Claim 12
Dependent Claim
15 words
The method of claim 9 wherein said first process is executed on a first processor.
Claim 13
Dependent Claim
20 words
The method of claim 10 wherein said second process is executed concurrently with said first process on said first processor.
Claim 14
Dependent Claim
20 words
The method of claim 10 wherein said second process is executed concurrently with said first process on a second processor.
Claim 15
Dependent Claim
16 words
The method of claim 9 wherein said first process and said second process are executed asynchronously.
Claim 16
Dependent Claim
103 words
The method of claim 9 further including the steps of: executing in said computer system a third process that references a second collectible memory area having allocated and unallocated memory address locations; transferring a second image of a memory state of said second collectible memory area of said third process to said second process; scanning each address in said second image by said second process to determine if said address is referenced; adding each address of said second image that is not referenced to said list of "free" address; transferring said list of "free" addresses from said second process to said third process.
Claim 17
Dependent Claim
22 words
The method of claim 9 wherein said step of disguising said cache pointer is accomplished by adding 1 to said cache pointer.
Claim 18
Dependent Claim
29 words
The method of claim 9 wherein said step of disguising said cache pointer is accomplished by passing each pointer value through an "exclusive or" gate with a standard constant.
References Cited (Backward Citations)
US4685125A
Cited
US4989137A
Cited
US4648065A
Cited
US4775932A
Cited
US4598361A
Cited
US4814971A
Cited
US4755939A
Cited
US4912629A
Cited
US4989134A
Cited
US4961137A
Cited
US4807120A
Cited
US4888681A
Cited
US5093782A
Cited
US4907151A
Cited
US5088036A
Cited
US4951194A
Cited
US5109336A
Cited
US5241673A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-10-10 | 1998-04-11 | 1998-10-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-10-10 | 2002-04-11 | 2002-10-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-10-10 | 2006-04-11 | 2006-10-11 | $7700.00 | Window Closed / Lapsed |