SPACE-LIMITED MARKING STRUCTURE FOR TRACING GARBAGE COLLECTORS

摘要

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.