US4755939A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Garbage collection in a computer system
Assignee: Fujitsu Services Ltd
•
Filing: 1986-11-24
•
Granted: 1988-07-05
•
Expires: 2006-11-24
Abstract
Abstract A computer system is described, having memory cells organized in a directed graph structure by means of pointers. Each cell has a reference count, and each pointer has a weight value. If a new pointer to a cell is created by copying an existing pointer, the new and existing pointers are given weights whose sum equals the old value of the existing pointer. In this way, the sum of the weights of the pointers to any cell are maintained equal to its reference count. If a pointer is destroyed, the reference count of the cell to which it points is reduced by the weight of the pointer. Thus, when the reference count of a cell reaches zero, it is safe to assume that there are no more existing pointers to it, and hence that cell my be reclaimed (garbage-collected) for re-use.
Inventors
- 👤 Paul Watson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 19:13
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/0223; G06F12/023; G06F12/0253; G06F12/0261; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99956; Y10S707/99957
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
220 words
A method of garbage collection in a computer system having storage means containing a plurality of memory cells, at least some of which contain pointers to others of the cells thereby defining a directed graph structure in which each cell represents a node of the graph, wherein the method comprises steps as follows: (a) each pointer is provided with a variable weight value, (b) each cell is provided with a variable reference count value, (c) whenever a cell is allocated in the storage means, the reference count of the cell is initially set to a predetermined value and the weights of any pointers to that cell are set to non-zero values such that the sum of those weights (or the weight if there is only one such pointer) is equal to the reference count of that cell, (d) whenever a new pointer to a cell is created by copying an existing pointer, the new pointer and the existing pointer are given non-zero weight values whose sum equals the old weight value of the existing pointer, but the reference count of the cell is unaltered, (e) whenever a pointer is destroyed, the reference count of the cell to which the pointer points is reduced by the weight of that pointer, (f) and cells with reference count equal to zero are reclaimed.
Claim 2
Dependent Claim
59 words
A method according to claim 1 wherein the weight of each pointer is a power of two, and wherein, whenever a pointer is created by copying an existing pointer of weight greater than one, the weight of the existing pointer is divided by two and the result is stored as the weight value of the new and existing pointers.
Claim 3
Dependent Claim
28 words
A method according to claim 2 wherein the weight of each pointer is encoded in a compressed form as the logarithm to the base two of the weight.
Claim 4
Dependent Claim
81 words
A method according to claim 3 wherein, whenever a pointer is to be created by copying an existing pointer of weight equal to one, a dummy cell is created into which the existing pointer is copied along with its weight, the dummy cell is given a reference count greater than one, and the new and existing pointers are both made to point to this dummy cell, and are given non-zero weights whose sum equals the reference count of the dummy cell.
Claim 5
Dependent Claim
16 words
A method according to claim 3 in which the system is a multi-processor distributed computer system.
Claim 6
Dependent Claim
81 words
A method according to claim 2 wherein, whenever a pointer is to be created by copying an existing pointer of weight equal to one, a dummy cell is created into which the existing pointer is copied along with its weight, the dummy cell is given a reference count greater than one, and the new and existing pointers are both made to point to this dummy cell, and are given non-zero weights whose sum equals the reference count of the dummy cell.
Claim 7
Dependent Claim
16 words
A method according to claim 2 in which the system is a multi-processor distributed computer system.
Claim 8
Dependent Claim
81 words
A method according to claim 1 wherein, whenever a pointer is to be created by copying an existing pointer of weight equal to one, a dummy cell is created into which the existing pointer is copied along with its weight, the dummy cell is given a reference count greater than one, and the new and existing pointers are both made to point to this dummy cell, and are given non-zero weights whose sum equals the reference count of the dummy cell.
Claim 9
Dependent Claim
17 words
A method according to claim 8 in which the computer system is a multiple-processor distributed computer system.
Claim 10
Dependent Claim
17 words
A method according to claim 1 in which the computer system is a multi-processor distributed computer system.
References Cited (Backward Citations)
US4121286A
Cited
US4325120A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1991-07-05 | 1992-01-04 | 1992-07-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1995-07-05 | 1996-01-04 | 1996-07-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1999-07-05 | 2000-01-04 | 2000-07-05 | $7700.00 | Window Closed / Lapsed |