Patent US4695949A successfully refreshed from Google Patents.
US4695949A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for efficient support for reference counting
Assignee: Texas Instruments Inc
•
Filing: 1984-07-19
•
Granted: 1987-09-22
•
Expires: 2004-07-19
Abstract
Abstract A method and apparatus for managing a block oriented memory of the type in which each memory block has an associated reference count representing the number of pointers to it from other memory blocks and itself. Efficient and cost-effective implementation of reference counting alleviates the need for frequent garbage collection, which is an expensive operation. The apparatus includes a hash table into which the virtual addresses of blocks of memory which equal zero are maintained. When the reference count of a block increases from zero, its virtual address is removed from the table. When the reference count of a block decreases to zero, its virtual address is inserted into the table. When the table is full, a reconciliation operation is performed to identify those addresses which are contained in a set of binding registers associated with the CPU, and any address not contained in the binding registers are evacuated into a garbage buffer for subsequent garbage collection operations. The apparatus can be implemented by a cache augmented by the hash table, providing a back-up store for the cache.
Inventors
- 👤 Satish Thatte
- 👤 Donald W. Oxley
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 18:25
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: 4
Claim 1
Independent Claim
154 words
Apparatus for identifying garbage blocks in a block oriented memory of the type in which each memory block has an associated reference count representing a number of pointers to it from other memory blocks and itself, but not including pointers from a CPU, comprising: means for creating a data structure for containing pointers to blocks of memory; means for inserting in the data structure a pointer to each block of memory which has a reference count of zero; means for deleting from the data structure the pointer to each block of memory whose reference count changes from zero; means for comparing pointers in the CPU with the pointers in the data structure; means for marking memory blocks which are in the data structure and not pointed to by the CPU as garbage blocks; and means for moving the pointers to memory blocks marked as garbage blocks from the data structure to a garbage buffer.
Claim 2
Dependent Claim
154 words
Apparatus for identifying garbage blocks in a block oriented memory of the type in which each memory block has an associated reference count representing a number of pointers to it from other memory blocks and itself, but not including pointers from a CPU, comprising: means for creating a data structure for containing pointers to blocks of memory; means for inserting in the data structure a pointer to each block of memory which has a reference count of zero; means for deleting from the data structure the pointer to each block of memory whose reference count changes from zero; means for comparing pointers in the CPU with the pointers in the data structure; means for marking memory blocks which are in the data structure and not pointed to by the CPU as garbage blocks; and means for moving the pointers to memory blocks marked as garbage blocks from the data structure to a garbage buffer.
Claim 3
Independent Claim
159 words
A method for managing a block oriented memory of the type in which each memory block has an associated reference count representing a number of pointers to it from at least memory blocks and itself, but not from a CPU comprising: storing a first list of pointers to memory blocks which have a reference count of zero; inserting into such list a pointer to each block of memory which has a reference count which changes to zero; deleting from such list the pointer of each block of memory whose reference count changes from zero; identifying the blocks which have pointers in the list as potential garbage blocks; and when the list of pointers reaches a preselected size, obtaining a second list of pointers contained in the CPU, deleting from the first list those pointers which are not contained in the second list, and returning the memory blocks having pointers deleted from the first list to the system for reuse.
Claim 4
Independent Claim
159 words
A method for managing a block oriented memory of the type in which each memory block has an associated reference count representing a number of pointers to it from at least memory blocks and itself, but not from a CPU comprising: storing a first list of pointers to memory blocks which have a reference count of zero; inserting into such list a pointer to each block of memory which has a reference count which changes to zero; deleting from such list the pointer of each block of memory whose reference count changes from zero; identifying the blocks which have pointers in the list as potential garbage blocks; and when the list of pointers reaches a preselected size, obtaining a second list of pointers contained in the CPU, deleting from the first list those pointers which are not contained in the second list, and returning the memory blocks having pointers deleted from the first list to the system for reuse.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1990-09-21 | 1991-03-23 | 1991-09-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1994-09-21 | 1995-03-23 | 1995-09-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1998-09-21 | 1999-03-23 | 1999-09-22 | $7700.00 | Window Closed / Lapsed |