Title:
SPACE-LIMITED MARKING STRUCTURE FOR TRACING GARBAGE COLLECTORS
Document Type and Number:
WIPO Patent Application WO1999019802
Kind Code:
A3
Abstract:
A data processing method and apparatus are described for tracing paths through stored data structures defined by data objects (52) coupled by identifying pointers and within a contiguous area of memory (50). A fixed sized marking stock or queue (54) builds up a list of located objects as the structure or structures are traversed. The contiguous memory (50) is divided into discrete pages (P.0-P.5) with the linked data objects within each being considered in turn: any link to an open object in another page causes an identifier for that page to be entered in a page list (56) if one does not already exist, and a page table (58) for each page identifies the location of the first and last identified objects within a page to set a range for subsequent scanning.
Inventors:
HOULDSWORTH RICHARD JAMES
Application Number:
PCT/IB1998/001502
Publication Date:
September 10, 1999
Filing Date:
September 28, 1998
Export Citation:
Assignee:
KONINKL PHILIPS ELECTRONICS NV (NL)
PHILIPS SVENSKA AB (SE)
PHILIPS SVENSKA AB (SE)
International Classes:
G06F12/00; G06F12/02; (IPC1-7): G06F12/02
Other References:
MOSTLY PARALLEL GARBAGE COLLECTION, HANS-J. BOEHM, ALAN J. DEMERS, SCOTT SHENKER, PROCEEDINGS OF ACM SIGPLAN '91, CONFERENCE ON PROGRAMMING LANGUAGE DESIGN AND IMPLEMENTATION, SIGPLAN Notices 26, 6, pages 157-164.
COMMUNICATIONS OF THE ACM, Volume 26, No. 6, June 1983, HENRY LIEBERMAN and CARL HEWITT, "A Real-Time Garbage Collector Based on the Lifetimes of Objects", pages 419-429.
COMMUNICATIONS OF THE ACM, Volume 26, No. 6, June 1983, HENRY LIEBERMAN and CARL HEWITT, "A Real-Time Garbage Collector Based on the Lifetimes of Objects", pages 419-429.
Download PDF: