Preselect list using hidden pages

Disclosed is a computer implemented method, computer program product, and apparatus for maintaining a preselect list. The method comprises software components detecting a page fault of a memory page. In response to detecting a page fault, the software components determine whether the memory page is referenced in the preselect list and unhide the memory page. Upon determining whether the memory page is referenced in the preselect list, the software components remove an entry of the preselect list corresponding to the memory page to form at least one removed candidate page and skip paging-out of the at least one removed candidate page.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates generally to a computer implemented method, data processing system, and computer program product for caching disk data to memory. More specifically, the present invention relates to tracking potential candidate pages for paging-out and re-assessing their candidacy before a page-out occurs.

2. Description of the Related Art

In a computer system, Random Access Memory (RAM) contains the instructions or program to execute and the data necessary to execute those instructions. The resulting data from execution of the program code is also stored back into the RAM.

Modern computer systems use a Virtual Memory Manager (VMM) to provide on-demand paging to extend the size of memory. Such computer systems provide this feature because only the actual instructions and data required at a given point in time for execution need to reside in memory. The remaining portions of a program's instructions may be stored on disk until they are needed. The space where such instructions are stored is sometimes called paging space. Such a system can be complicated when there are multiple applications that run concurrently, or otherwise compete to use system resources.

System architects divide memory into units, often of equal sizes. These units are referred to as pages or frames. When a portion of a program's code or data is needed in RAM, it will be brought in one page at a time. Similarly, when a portion of a program or data is no longer needed in RAM it will be removed from the RAM to make room for other instructions or data. Thus, a memory page is a virtual block of storage, in either physical memory or persistent storage. Physical memory is volatile storage, such as, for example, RAM. Persistent storage is memory that requires no refreshing current to maintain data within the device.

The VMM manages the translation between the effective size of memory and the physical size of memory. The effective size of memory is also called the effective memory address range. The physical size of memory is also called the physical memory address range. The VMM maintains a map, which is used to translate the effective address of a page to the physical location of that page in RAM. This feature is known as a page translation. The entries in this map are called Page Translation Entries (PTE). When an effective memory address is accessed, which is not in physical memory, a page fault occurs. To satisfy the page fault and allow execution to continue, a memory page in physical memory will be selected for replacement if there are no free pages in physical memory. A page fault is an interrupt or an exception to the software raised by the undergirding hardware to indicate that a memory page mapped in address space is not resident in a particular place of physical memory. The reasons for the fault may vary. For example, the memory page may only be present in persistent storage and not found in physical memory. A page fault may also occur when a memory page is present in physical memory, but its status is not updated as present in hardware, at least with respect to the particular place of physical memory to which the memory page had primarily been assigned.

The VMM is responsible for steps such as selecting the memory page to replace, removing the contents of that page out of RAM, removing the PTE, loading the replacement memory page into physical memory, and adding a PTE. The data processing system continues program execution following these steps.

The VMM can use a variety of page replacement criteria when selecting memory pages in physical memory to be replaced with newly requested data. These criteria may be based on, for example, freshness of memory page access, and a number of times the memory page has been brought back into physical memory (re-paged). One example of a page replacement policy is based on a Least Recently Used (LRU) algorithm. Further examples may use LRU as a weighting factor in determining whether to remove a memory page as compared to other potential candidate pages. In some cases, many memory pages will need to be examined in RAM before suitable candidate pages for paging-out can be found. A candidate page is a memory page that is selected by a data processing system's page replacement software for paging-out to persistent storage when the next page-out cycle occurs. Paging-out is an operation where the contents of a physical memory corresponding to the memory page are copied to persistent storage, and optionally, a status bit is set to indicate that the physical memory is unused. Various user-tunable thresholds influence the operation of the page-replacement algorithm. Such thresholds include, for example, minfree, the minimum acceptable number of real memory page frames in the free list, and maxfree, the maximum size to which the free list will grow by VMM page stealing.

Finding a suitable candidate page in physical memory to replace can be a lengthy process. In addition, paging-out of a memory page from physical memory can be a lengthy process since the contents of the memory page being paged-out are saved to persistent storage if its contents have changed since being loaded into the physical memory. Accordingly, process improvements may occur if a list of candidate pages were limited to a more compact set of better candidates for paging out.

SUMMARY OF THE INVENTION

The present invention provides a computer implemented method, data processing system, and computer program product for paging-out memory pages in a virtual memory system. The method comprises software components detecting a page fault of a memory page. In response to detecting a page fault, the software components determine whether the memory page is referenced in the preselect list and unhide the memory page. Upon determining whether the memory page is referenced in the preselect list, the software components remove an entry of the preselect list corresponding to the memory page to form at least one removed candidate page and skip paging-out of the at least one removed candidate page.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

With reference now to the figures and in particular with reference toFIG. 1, a block diagram of a data processing system is shown in which aspects of an illustrative embodiment may be implemented. Data processing system100is an example of a computer, in which code or instructions implementing the processes of the present invention may be located. In the depicted example, data processing system100employs a hub architecture including a north bridge and memory controller hub (NB/MCH)102and a south bridge and input/output (I/O) controller hub (SB/ICH)104. Processor106, main memory108, and graphics processor110connect to north bridge and memory controller hub102. Graphics processor110may connect to the NB/MCH through an accelerated graphics port (AGP), for example.

In the depicted example, local area network (LAN) adapter112connects to south bridge and I/O controller hub104and audio adapter116, keyboard and mouse adapter120, modem122, read only memory (ROM)124, hard disk drive (HDD)126, CD-ROM drive130, universal serial bus (USB) ports and other communications ports132, and PCI/PCIe devices134connect to south bridge and I/O controller hub104through bus138and bus140. PCI/PCIe devices may include, for example, Ethernet adapters, add-in cards, and PC cards for notebook computers. PCI uses a card bus controller, while PCIe does not. ROM124may be, for example, a flash binary input/output system (BIOS). Hard disk drive126and CD-ROM drive130may use, for example, an integrated drive electronics (IDE) or serial advanced technology attachment (SATA) interface. A super I/O (SIO) device136may be connected to south bridge and I/O controller hub104.

An operating system runs on processor106and coordinates and provides control of various components within data processing system100inFIG. 1. The operating system may be a commercially available operating system such as Microsoft® Windows® XP. Microsoft and Windows are trademarks of Microsoft Corporation in the United States, other countries, or both. An object oriented programming system, such as the Java™ programming system, may run in conjunction with the operating system and provides calls to the operating system from Java™ programs or applications executing on data processing system100. Java™ is a trademark of Sun Microsystems, Inc. in the United States, other countries, or both.

Instructions for the operating system, the object-oriented programming system, and applications or programs are located on storage devices, such as hard disk drive126, and may be loaded into main memory108for execution by processor106. The processes of the present invention can be performed by processor106using computer implemented instructions, which may be located in a memory such as, for example, main memory108, read only memory124, or in one or more peripheral devices.

Those of ordinary skill in the art will appreciate that the hardware inFIG. 1may vary depending on the implementation. Other internal hardware or peripheral devices, such as flash memory, equivalent non-volatile memory, and the like, may be used in addition to or in place of the hardware depicted inFIG. 1. In addition, the processes of the illustrative embodiments may be applied to a multiprocessor data processing system.

The aspects of the illustrative embodiments provide a computer implemented method, data processing system, and computer program product for reducing a number of memory pages that are paged-out during a replacement page cycle. Removed candidate pages that had been formerly available in a preselect list are ignored for purposes of paging-out.

FIG. 2Ashows a pair of data structures used to track memory pages for paging-out in accordance with an illustrative embodiment of the invention. The structures include a preselect list210, and virtual memory200. A preselect list is a list of page references that identify addresses in virtual memory. An entry of the preselect list may be a virtual memory page reference and may include a valid bit. A reference is an address that directly identifies a virtual memory address such that a processor may use the address to access the memory. The valid bit can indicate whether the entry continues reference a valid candidate page for re-paging. Accordingly, in some illustrative embodiments of the invention, the preselect list may contain a list of candidate pages that are marked for paging-out.

Each entry of preselect list210can be organized according to virtual page reference215. The virtual memory200and preselect list210are empty inFIG. 2A.

Virtual memory200comprises virtual memory pages, for example, virtual memory page221. Each memory page has reference bit223associated with it. A reference bit is a bit that is set by the Virtual Memory Manager (VMM) or other software component whenever the page is accessed. Reference bits may indicate a status for the virtual memory page concerning whether the virtual memory page has been referenced in a recent period, or whether the physical memory page has been modified in a recent period. When a software component hides a memory page, it omits associated translations for the memory page. Accordingly, hiding the memory page may force an address translation to occur when accessing the memory page. Memory pages referenced by the preselect list can be hidden in this manner.

FIG. 2Bis a preselect list and virtual memory occupied by memory pages in accordance with an illustrative embodiment of the invention. As such,FIG. 2Brepresents a condition of memory after a time illustrated inFIG. 2A. Virtual memory pages may be in use, but hidden. Such physical memory pages include virtual memory page 1251, virtual memory page 2252, virtual memory page 3253, and virtual memory page 4254. Such pages are not tracked by the VMM, but instead are locatable by using a page fault handler and corresponding references in preselect list210. Arrows provided inFIG. 2Bsignal the manner in which a virtual page reference actually refers to a virtual page.

Illustrative embodiments of the invention may establish the preselect list to include four candidate pages for paging-out, namely candidate page A261, candidate page B262, candidate page C263, and candidate page D264. Each candidate page references virtual memory page 1251, virtual memory page 2252, virtual memory page 3253, and virtual memory page 4254, respectively.

FIG. 2Cshows a state of the preselect list and page frame table at a time afterFIG. 2Bin accordance with an illustrative embodiment of the invention. At this time, the page fault handler has recently accessed virtual memory page 2252. The absence of a valid candidate page B pointing to virtual memory is represented in a dashed arrow.

For embodiments that track valid preselect entries by setting or resetting valid bits, a software component can reset such a bit to binary ‘0’. Thus, the entry in the preselect list210entry corresponding virtual memory page 2252, that is, the entry holding candidate page B262, can have a corresponding valid bit reset to “not valid”. Resetting may involve setting a bit to a binary ‘0’, which, accordingly, may represent a state of “not valid”. In effect, the resetting of the entry of candidate page B262removes the preselect list entry containing the reference to virtual memory page 2252. Those skilled in the art will appreciate that additional ways to remove a preselect list may be used. Accordingly, the embodiments of the invention are not limited by the manner in which a preselect list entry is removed.

The process steps, described below, may be performed by two or more processes operating asynchronously but cooperatively. One process may be a process that runs continuously for as long as a system operates without rebooting. This process may be, for example, a daemon used to add virtual memory pages to a preselect list. In addition, the process steps below may be in part performed by one or more applications that signal or otherwise identify candidate pages not suitable for paging out. The steps ofFIGS. 3A and 3B, below, may be prefaced by a page replacement daemon adding candidate pages to a preselect list.

FIG. 3Ais a flowchart performed by software components to maintain the preselect list in accordance with an illustrative embodiment of the invention. The software components may include a daemon running in the operating system of, for example, data processing system100ofFIG. 1. The daemon can be, for example, a page replacement daemon. Initially the data processing system accesses a virtual memory page (step311). Next, the data processing system determines whether a page fault has occurred (step313). If no page fault occurred, the data processing system may continue to access memory pages at step311. However, if a page fault occurred, the data processing system may determine whether the memory page corresponding to the page fault has a counterpart physical page that continues to hold valid data of the memory page. The data processing system determines if a hidden page is still in physical memory (step315) such that the hidden page is the backing store of the page-faulting memory page. This step may be performed by a process that runs on the data processing system. Nevertheless, this step is distinct from the process that determines a page fault in step313.

A negative determination at step315causes processing to terminate. However, a positive determination may cause the data processing system to unhide the memory page (step317). Next, the data processing system determines whether the physical page is referenced in the preselect list (step319). The preselect list can be, for example, and indexed array, a linked list, or the like. If the memory page is not referenced by the preselect list, then the data processing system stops processing the steps of the flowchart. Generally, the data processing system performs a remove operation on the entry of the preselect list that references the physical page as determined in step319. For example, a positive result at step319can cause the data processing system to remove the virtual address entry from the preselect list (step321). Step321may be performed in a number of different ways. For example, the data processing system may be using a linked list as a preselect list. Accordingly, an entry stored by a node in the linked list may be removed by adjusting pointer references of neighboring nodes to the list to skip the removed node. Alternatives to this housekeeping function can include adjusting entries in an array to remove the selected entry. Removed entries are skipped over or otherwise not considered when determining candidate pages for paging out, as explained further in the flowchart ofFIG. 3B, below. It is appreciated that steps317through321can be performed by an application that uses the memory page. In effect, the application shortens the list of pages to be paged-out. As a result, I/O efficiency can be improved by causing fewer pages to page out than otherwise would occur. In addition, since pages removed from the preselect list are themselves highly likely to be used again by an associated process or application, the I/O subsystem is also protected from having to page-in pages removed from the list by step321. Importantly, though the flowchart above shows continuity from one step to the next, each step can be separated periods of varying lengths based on availability of system resources and number of processes competing for such resources. Various schemes to provide for parallelism or cooperation between processes can make each step occur asynchronously and in response to signals sent between and among several processes.

FIG. 3Bis a flowchart of steps to page-out candidate pages found in the preselect list in accordance with an illustrative embodiment of the invention. The data processing system may begin by determining whether one or more entries exist in a preselect list (step329). A negative outcome results in the process terminating thereafter. If the data processing system determines one or more entries exist, the data processing system determines if an event or other indication triggers the time to page-out a block of candidate pages (step331). If not, the data processing system may repeatedly check for the time to page-out blocks in accordance with user-tuned thresholds. The determination made at step331can determine that it is time to page-out a block of candidate pages, that is, the data processing system reaches a positive determination. This determination may be because sufficient processing bandwidth exists on an I/O subsystem to perform paging. Next, the data processing system may obtain the next candidate page in the preselect list (step333). The data processing system may determine that entries for candidate pages are exhausted (step335). If so, processing terminates thereafter. If not, the data processing system may remove the candidate page reference from the preselect list (step341). A removed candidate page is a candidate page removed in this manner. Next, the data processing system may page-out remaining candidate page references from the preselect list (step343). Accordingly, the data processing system may skip paging-out removed candidate pages. Processing terminates thereafter.

Steps329through341may be performed by a software component that cooperates with a virtual memory manager. The actual page-out step, step343, can be performed by the virtual memory manager.

In addition, a software component may prepare the preselect list by determining if the memory page is a candidate page for paging-out. Such a process can be described as preselection. Responsive to that determination, the software component may hide or otherwise mark as hidden the memory page. The software component can add a virtual page reference entry to the preselect list as a reference to the memory page.

It is appreciated that the preselect list may be formed from a linked list that includes a page reference at each node of the linked list. Nodes that are to be removed can be unlinked from such a linked list embodiment. Similarly, the addition of a new node or entry to the preselect list may involve adding an additional node to one end of the underlying linked list data structure. It is appreciated that the embodiments are not limited merely to arrays and linked lists, and that other suitable data structures known in the art may be used as alternatives to these implementations of a preselect list.

The illustrative embodiments of the invention permit a software component to efficiently begin paging-out pages by relying on a preselect list. A preselect list may be prepared ahead of a page-out so that rescanning may be minimized. Scanning and rescanning is the process of looking for candidate pages in order to replace such pages in physical memory. The illustrative embodiments of the invention create a preselect list of such candidate pages so that further evaluation is limited only to such candidate pages prior to paging-out one or more such candidate pages. Accordingly, since candidate pages can be already referenced via the preselect list, scanning is no longer required. The embodiments of the invention may reduce the occurrence of paging-out pages that are still needed.