Apparatus and system for dynamically allocating main memory among a plurality of applications

• US 7,487,320 B2
• Filed: 12/15/2004
• Issued: 02/03/2009
• Est. Priority Date: 12/15/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Modha, Dharmendra Shantilal, McKenney, Paul Edward, Bansal, Sorav
• Primary Examiner(s): Kim; Matt
• Assistant Examiner(s): Birkhimer; Christopher D
• Application Number:
  US11/014,529
• Publication Number:
  US 20060129782A1
• Time in Patent Office: 1,511 Days
• Field of Search: 711/170, 711/133, 711/159, 711/154, 711/105, 711/104
• US Class Current: 711/170
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 12/122 of the least frequently used [LFU] type, e.g. with individual count value
• CPC Class Codes: G06F 12/124 being minimized, e.g. non MRU
• CPC Class Codes: G06F 2212/502 using adaptive policy

Abstract

An apparatus and system are disclosed for dynamically allocating main memory among applications. The apparatus includes a cache memory module configured to maintain a first list and a second list, each list having a plurality of pages, and a resize module configured to resize the cache by adaptively selecting the first or second list and subtracting pages from or adding pages to the selected list. The system includes the apparatus and a cache replacement module configured to adaptively distribute a workload between the first list and the second list.

Claims

1. An apparatus to dynamically allocate main memory among a plurality of virtual operating systems, the apparatus comprising:

a cache memory module comprising an allocation of very large scale integration random access memory circuits for a virtual operating system, the cache memory module maintaining at least a first list and a second list, each list configured to store a plurality of pages, the first list containing pages requested only once since a last removal of a page from the first list and the second list containing pages requested at least twice since a last removal of pages from the second list, each list having a T portion and a B portion, the cache memory module having an allocation of pages; and

a resize module comprising computer instructions stored in a memory device, executing on a processor, that shrinks the allocation of the cache memory module by setting a size of the T portion of the first list to a new allocation, discarding pages from the T portions of the first and second lists until a sum of sizes of the T portions of the first and second lists is less than the new allocation, and if a sum of sizes of the T and B portions of the first list is greater than the new allocation, removing pages from the B portion of the first list until a sum of sizes of the B portions of the first and second lists is less than the new allocation else removing pages from the B portion of the second list until the sum of the sizes of the B portions of the first and second lists is less than the new allocation.

2. The apparatus of claim 1, wherein each T portion is configured to maintain the plurality of pages.

3. The apparatus of claim 1, wherein each B portion is configured to maintain history information about recently evicted pages.

4. The apparatus of claim 1, wherein the resize module is configured to not replace a page if the sum of the T portions is less than the new allocation.

5. A system to dynamically allocate main memory among a plurality of virtual operating systems, the apparatus comprising:

a cache memory module comprising an allocation of very large scale integration random access memory circuits for a virtual operating system, the cache memory module maintaining a first list and a second list, each list configured to store a plurality of pages, the first list containing pages requested only once since a last removal of a page from the first list and the second list containing pages requested at least twice since a last removal of pages from the second list, each list having a T portion and a B portion, the cache memory module having an allocation of pages; and

a cache replacement module comprising very large scale integration circuits and configured to adaptively distribute a workload between the first list and the second list; and

a resize module comprising computer instructions stored in a memory device, executing on a processor, that shrinks the allocation of the cache memory module by setting a size of the T portion of the first list to a new allocation, discarding pages from the T portions of the first and second lists until a sum of sizes of the T portions of the first and second lists is less than the new allocation, and if a sum of sizes of the T and B portions of the first list is greater than the new allocation, removing pages from the B portion of the first list until a sum of sizes of the B portions of the first and second lists is less than the new allocation else removing pages from the B portion of the second list until the sum of the sizes of the B portions of the first and second lists is less than the new allocation.

6. The system of claim 5, wherein the T portion is configured to maintain the plurality of pages.

7. The system of claim 5, wherein the B portion is configured to maintain history information about recently evicted pages.

8. The system of claim 5, wherein the resize module is configured to not replace a page if the sum of the T portions is less than the new allocation.

9. A program of machine-readable instructions stored in a memory device and executable by a digital processing apparatus to perform an operation to dynamically allocate main memory among a plurality of virtual operating systems, the operation comprising:

maintaining at least a first list and a second list, each list configured to store a plurality of pages, wherein the first list containing pages requested only once since a last removal of a page from the first list and the second list containing pages requested at least twice since a last removal of pages from the second list and each list comprises a T portion and a B portion;

maintaining a cache memory module allocated to the virtual operating system and having an allocation of pages; and

shrinking the allocation by setting a size of the T portion of the first list to a new allocation, discarding pages from the T portions of the first and second lists until a sum of sizes of the T portions of the first and second lists is less than the new allocation, and if a sum of sizes of the T and B portions of the first list is greater than the new allocation, removing pages from the B portion of the first list until a sum of sizes of the B portions of the first and second lists is less than the new allocation else removing pages from the B portion of the second list until the sum of the sizes of the B portions of the first and second lists is less than the new allocation.

10. The program of machine-readable of claim 9, wherein the instructions further comprise an operation to not replace a page if the sum of the T portions of the lists is less than the new allocation.

11. The program of machine-readable instructions of claim 9, wherein the instructions further comprise an operation to adaptively select a list and a portion of the list, and remove pages from the portion.

12. The program of machine-readable of claim 9, wherein the instructions further comprise an operation to remove a page from the B portion of either the first list or the second list if the sum of the T portions is greater than the new allocation, and if the sum of the B portions is greater than the new allocation.

13. An apparatus to dynamically allocate main memory among a plurality of virtual operating systems, the apparatus comprising:

means for maintaining at least a first list and a second list, wherein the first list containing pages requested only once since a last removal of a page from the first list and the second list containing pages requested at least twice since a last removal of pages from the second list, the list maintaining means comprising very large scale integration circuits, each list configured to store a plurality of pages and having a T portion and a B portion;

means for maintaining at least one cache memory module allocated to a virtual operating system and having an allocation of pages, the cache maintaining means comprising very large scale integration circuits; and

means for resizing the allocation by shrinking the allocation of the cache memory module by setting a size of the T portion of the first list to a new allocation, discarding pages from the T portions of the first and second lists until a sum of sizes of the T portions of the first and second lists is less than the new allocation, and if a sum of sizes of the T and B portions of the first list is greater than the new allocation, removing pages from the B portion of the first list until a sum of sizes of the B portions of the first and second lists is less than the new allocation else removing pages from the B portion of the second list until the sum of the sizes of the B portions of the first and second lists is less than the new allocation, the resizing means comprising computer instructions stored in a memory device and executing on a processor.