Real-time garbage collection for list processing using restructu

Details Real-time garbage collection for list processing using restructu Real-time garbage collection for list processing using restructu

1986-06-26

1990-03-27

Shaw, Gareth D.

Boots, shoes, and leggings

3642811, 364280, G06F 900, G06F 1200

Patent

active

049126296

ABSTRACT:
In a list processing system, small reference counters are maintained in conjunction with memory cells for the purpose of identifying memory cells that become available for re-use. The counters are updated as references to the cells are created and destroyed, and when a counter of a cell is decremented to logical zero the cell is immediately returned to a list of free cells. In those cases where a counter must be incremented beyond the maximum value that can be represented in a small counter, the cell is restructured so that the additional reference count can be represented. The restructuring involves allocating an additional cell, distributing counter, tag, and pointer information among the two cells, and linking both cells appropriately into the existing list structure.

REFERENCES:
patent: 4016545 (1977-04-01), Lipovski
patent: 4121286 (1978-10-01), Venton et al.
patent: 4193115 (1980-03-01), Albus
patent: 4215397 (1980-07-01), Hom
patent: 4432057 (1984-02-01), Daniell et al.
patent: 4435752 (1984-03-01), Winkelman
patent: 4435766 (1984-03-01), Haber et al.
patent: 4447875 (1984-05-01), Bolton et al.
patent: 4463424 (1984-07-01), Mattson et al.
patent: 4502118 (1985-02-01), Hagenmaier et al.
patent: 4558413 (1985-12-01), Schmidt et al.
patent: 4695949 (1987-09-01), Thatte et al.
patent: 4716524 (1987-12-01), Oxley et al.
patent: 4758944 (1988-07-01), Bartley et al.
patent: 4775932 (1988-10-01), Oxley et al.
"Dynamic Page Reference Counter," IBM Technical Disclosure Bulletin, vol. 21, No. 8, Jan. 1979, J. N. McCauley and J. A. Wingert, (pp. 3139-3140).
"Efficient Real-Time Garbage Collection for LISP," Jun. 27, 1985, Robert L. Shuler, Jr.
"Performance Analysis of On the Fly Garbage Collection," Communications of the ACM, vol. 27, No. 11, Nov. 1984, Tim Hickey and Jacques Cohen, (pp. 1143-1154).
"Garbage Collection of Linked Data Structures," ACM Computing Surveys, vol. 13, No. 3, Sep. 1981, Jacques Cohen, (pp. 341-367).
"A Real-Time Garbage Collector Based on the Lifetimes of Objects," Communications of the ACM, vol. 26, No. 6, Jun. 1983, Henry Lieberman and Carl Hewitt.
"LISP," 2nd Ed., Addison-Wesley, 1984, Patrick Henry Winston and Berthold Klaus Paul Horn, (p. 141).
"An Efficient Machine-Independent Procedure for Garbage Collection in Various List Structures," Communications of the ACM, vol. 10, No. 8, Aug. 1967, H. Schorr and W. M. Waite, (pp. 501-506).

Affiliated with

Also associated with

Rating

Real-time garbage collection for list processing using restructu does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Real-time garbage collection for list processing using restructu, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Real-time garbage collection for list processing using restructu will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1655686