Method and apparatus for enhancing data storage efficiency

• US 4,989,134 A
• Filed: 03/20/1987
• Issued: 01/29/1991
• Est. Priority Date: 03/20/1987
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Company (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Shaw, Robert A.
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): Napiorkowski, Maria
• Application Number:
  US07/028,808
• Time in Patent Office: 1,411 Days
• Field of Search: 364/200, 364/900, 364/300
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

The present invention improves the interaction of a virtual memory systems and a garbage collection system, thereby reducing garbage collection effort and improving virtual memory performance. The method includes the steps of: (1) developing a secondary memory (e.g. disk) dirty page map; (2) developing a saved state map from a primary memory (e.g. RAM) dirty page map; (3) using the secondary memory dirty page map and the primary memory dirty page map to effectively reduce the size of the base set; (4) performing a garbage collection routine on at least a segment of the heap based upon the effectively reduced base set; and (5) performing a virtual memory routine using the primary memory dirty page map and the saved state map. The apparatus of the present invention implements the method on a digital computer system with a combination of hardware and software.

Claims

1. A method for enhancing data storage efficiency in a virtual memory system including a primary memory and a secondary memory having a plurality of pages where a base set and a heap reside within pages of said primary memory and said secondary memory, and a primary memory dirty page map of said primary memory which indicates when pages in said primary memory have been written to;

said method comprising the steps of;

developing a secondary memory dirty page map of said secondary memory;

developing a saved state map from said primary memory dirty page map;

utilizing said primary memory dirty page map and said secondary memory dirty page map to determine which pages within the base set have not been written to since said dirty page maps were last cleared, thereby effectively reducing the size of said base set which needs to be utilized by a garbage collection routine by allowing the garbage collection routine to ignore any page in the base set which has not been written to;

performing said garbage collection routine on at least a segment of said heap based upon said effectively reduced base set; and

performing a virtual memory routine including writing a first page from said secondary memory to a first page in said primary memory utilizing both said primary dirty page map and said saved state map to determine whether or not said first page in said primary memory first needs to be saved to a second page in said secondary memory because it had been written after it came into primary memory.

2. A method for enhancing data storage efficiency in a virtual memory system as recited in claim 1 further comprising the step of dividing said heap into a plurality of segments by said garbage collection routine which are differentiated by their various ages as determined by the number of garbage collection routines said segments had been subjected to, where said garbage collection routine is responsive to the relative ages of the segments of the heap.

3. A method for enhancing data storage efficiency in a virtual memory system as recited in claim 2 wherein said plurality of segments include a new heap, an aging heap and a stable heap.

4. A method for enhancing data storage efficiency by aging data in a memory system including a base set and a heap, where at least a portion of said heap is subjected to a periodic garbage collection routine, said method comprising the steps of:

a. chronologically grouping data comprised of datum which is stored within said heap into a plurality of segments including a new heap having a first designated logical memory space where new data is created, an aging heap which has a second designated logical memory space which is contiguous with said first designated logical memory space for data which has survived at least one garbage collection routine, and a stable heap having a third designated logical memory space which is contiguous with said second designated logical memory space for data which has survived a greater number of garbage collection routines than said aging heap and which is no longer subjected to routine garbage collection, where the boundary between said first designated logical memory space and said second designated logical memory space is designated by a first pointer and where the boundary between said second designated logical memory space and third designated logical memory space is designated by a second pointer, wherein the age of a datum within said heap is imprecisely determined by its inclusion within said new heap, said aging heap or said stable heap rather than by a specific age associated with said datum;

b. selectively performing said garbage collection routine by removing datum from said new heap and said aging heap which is neither directly nor indirectly referenced by pointers stored within said base set, and by not removing datum from said stable heap; and

c. repeating steps a. and b.

5. A method for enhancing data storage efficiency in a memory system as recited in claim 4 wherein said aging heap is eventually joined, after at least two garbage collection routines have been performed on said heap, with said stable heap by combining data of said aging heap with said stable heap by changing said second pointer.

6. A method for enhancing data storage efficiency in a memory system as recited in claim 5 wherein said new heap is redefined as said aging heap after said aging heap is joined with said stable heap by changing said first pointer.

7. A virtual memory system for enhancing data storage efficiency comprising:

primary memory means and secondary memory means, said primary memory means and said secondary memory means collectively including a multiple page base set area and a heap area, where said base set area has references to said heap area;

primary dirty page map storage means which is capable of being cleared;

save state map storage means;

secondary dirty page map storage means which is capable of being cleared;

means responsive to said primary memory dirty page map storage means and said secondary memory dirty page map storage means for effectively reducing said base set area for garbage collection purposes by determining which pages within said base set area have not been written to since said primary dirty page map storage means and said secondary dirty page map storage means were last cleared;

garbage collection means responsive to said reduced base set area and operative to remove un-referenced data from said heap area; and

virtual memory means responsive to said primary dirty page map storage means and said saved state map storage means and operative to manage said primary memory means and said secondary memory means.

8. A virtual memory system as recited in claim 7 wherein said garbage collection means further comprises means for chronologically dividing said heap into a plurality of segments, where said garbage collection means is responsive to the relative ages of said plurality of segments during subsequent garbage collections.

9. A virtual memory system as recited in claim 8 wherein said plurality of segments include a new heap, an aging heap, and a table heap.