EP0430668A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method and system for reclaiming unreferenced computer memory space
Assignee: Xerox Corp
•
Filing: 1990-11-28
•
Granted: —
•
Expires: 2010-11-28
Abstract
Abstract A system and method for reclaiming unreferenced computer memory space, also known as garbage collection operates in a virtual memory environment wherein user memory space is divided into pages. For each active page, a table stores the age of the oldest object on the page (A-value) and the age of the youngest object pointed to from that page (F-value). A generational partition divides the pages into "safe" pages and "threatened" pages, based on their A-values. Rescuer pages, which may contain pointers to threatened pages, are determined by comparing the F-values to the generational partition. All potential pointers on the rescuing pages are traced and the objects pointed to are marked as reachable. All objects reachable from other reachable objects are also marked. Unmarked threatened objects are de-allocated.
Inventors
- 👤 Mark D. Weiser
- 👤 Alan J. Demers
- 👤 Daniel G. Bobrow
- 👤 Barry Hayes
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-02 00:16
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/0223; G06F12/023; G06F12/0253; G06F12/0269; G06F12/0276; G06F2212/00; G06F2212/70; G06F2212/702
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
171 words
A garbage collection system for reclaiming unreferenced memory space in a computer, the system comprising: a computer having a memory; a plurality of objects stored in said memory, at least some of said objects containing pointer values pointing to other objects; each of said objects having one associated A-value stored in said memory for representing a partial ordering of the objects; each of said objects having one associated F-value stored in said memory for representing a range of A-values; and garbage collection means for deallocating unreachable objects by: receiving a partition value; partitioning the objects into a safe set and a threatened set by comparing the partition value to the A-values; identifying rescuer objects in the safe set by comparing the partition value to the F-values; identifying as reachable objects all objects in the threatened set that are pointed to from the rescuer objects and all objects in the threatened set that are pointed to from other reachable objects; and de-allocating all objects in the threatened set not identified as reachable.
Claim 2
Dependent Claim
28 words
The system of claim 1 further comprising allocator means for allocating objects and wherein the A-value associated with an object represents the time of allocation of the object.
Claim 3
Dependent Claim
32 words
The system of claim 1 or claim 2 wherein the F-value associated with an object is greater than or equal to the A-values associated with the objects pointed to by the object.
Claim 4
Dependent Claim
24 words
The system of claim 3 further comprising means for maintaining the F-value associated with an object in response to a change to the object.
Claim 5
Independent Claim
57 words
The system of any one of claims 1 to 4 wherein said garbage collection means partitions objects into a safe set and a threatened set such that objects in the safe set have an A-value less than the partition value and objects in the threatened set have an A-value greater than or equal to the partition value.
Claim 6
Dependent Claim
26 words
The system of claim 5 wherein said garbage collection means identifies rescuer objects as objects having an F-value greater than or equal to the partition value.
Claim 7
Independent Claim
202 words
A method for reclaiming unreferenced memory space in a computer having a memory and a plurality of objects stored in the memory, at least some of said objects containing pointer values pointing to other objects, the method comprising the steps of: storing a plurality of A-values; associating each A-value with at least one of the objects such that each object O has one associated A-value A(O) fpr representing a partial ordering of objects; storing a plurality of F-values; associating each F-value with at least one of the objects such that each object O has one associated F-value F(O) for indicating a range of values containing the A-value A(O') if object O points to object O'; receiving a partition value; partitioning the objects into a safe set and a threatened set by comparing the partition value to the A-values; identifying rescuer objects in the safe set by comparing the partition value to the F-values associated with the objects; identifying as reachable objects all objects in the threatened set that are pointed to from the rescuer objects and all objects in the threatened set that are pointed to from other reachable objects; and de-allocating all objects in the threatened set not identified as reachable.
Claim 8
Dependent Claim
21 words
The method of claim 7 wherein said step of identifying reachable objects comprises storing an indication that the object is reachable
Claim 9
Dependent Claim
41 words
The method of claim 7 or claim 8 wherein the step of associating each A-value with at least one of the objects comprises associating with each object an A-value less than or equal to the time of allocation of the object.
Claim 10
Independent Claim
55 words
The method of any one of claims 7 to 9 wherein the step of associating each F-value with at least one of the objects comprises the step of maintaining each F-value so that each object O has an F-value F(O) greater than or equal to the A-value A(O') if object O points to object O'.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.