Abstract:
A method, system, and program for managing memory page requests in a multi-processor data processing system determines a threshold value of available memory, and dynamically adjusts an allocation time to fulfill a page request if the available memory is below a threshold value. The allocation time to fulfill the page request is based upon a percentage of available memory pages once a page stealer commences a scan for pages. An allocation wait time is inversely proportionally adjusted depending upon the percentage of available memory. The allocation wait time has a duration that increases in time as the percentage of available memory decreases and decreases in time as the percentage of available memory increases. More specifically, an average time per page to allocate a page including a scan time for the scan in computing the average time is determined. Then a tunable value is applied to the average time to determine a wait time. In a preferred embodiment, user defined values are received that would control the allocation wait time before fulfilling a page request.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Technical Field 
         [0002]    The field of this invention is data processing, or more specifically, methods, systems, and products for managing virtual memory in a multi-processor computer. 
         [0003]    2. Description of the Related Art 
         [0004]    In a computer system Random Access Memory (RAM) contains the instructions (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. 
         [0005]    Modern computer systems use Virtual Memory Management (VMM) with on demand paging to extend the size of memory. Modern computer systems can do this as only the actual instructions and data required at a given point in time for execution need to reside in memory. 
         [0006]    For efficiency, real memory is divided into units, often of equal sizes. These units are referred to herein as pages or frames. When a portion of a program&#39;s code or data is needed in RAM, it will be bought in one page at a time. Equally, when a portion of a program or data is no longer needed in RAM it will be removed from the RAM a page at a time to make room for other instructions or data. 
         [0007]    The VMM manages the translation between the effective size of memory (effective memory address range) and the physical size of memory (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 is known as a page translation, and 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 page in memory will be selected for replacement if there are no free pages in memory. 
         [0008]    The VMM is responsible for selecting the page to replace, removing the contents of that page out of RAM, removing the PTE, loading the new page into memory, and adding a PTE. Once this has been done execution of the faulting program is free to continue. 
         [0009]    The VMM can use a variety of page replacement policy considerations when selecting pages in memory to be replaced with newly requested data including how recently the page was last accessed, and the number of times it has been bought back into memory (repaged). The most common method employed in modern computer systems is some variant of a Least Recently Used (LRU) algorithm. Other considerations or policies are often tied into the LRU policy to weight the decision to remove a page either more or less favored against other potential candidates. In some cases many pages will need to be examined in RA before a suitable candidate can be found. 
         [0010]    Finding a suitable candidate page in memory to replace can be a lengthy process. In addition, removal of a page from memory can be a lengthy process as the contents of the page being removed will need to be save to physical storage if it&#39;s contents have been changed since being loaded into the RAM. 
         [0011]    For efficiency, the VMM always tries to keep free pages available in RAM. If free pages are available in RAM the page fault takes less time to satisfy as the VMM does not need to find a suitable candidate in memory to replace, nor does it need to save the contents of the page if changes have occurred to the page since being bought into RAM. For efficiency, pages which are available for immediate replacement (unallocated) are entered into a freelist. When the VMM needs to satisfy a page request it first checks for a free page on this list. 
         [0012]    In order to increase the chances that there will be free page on the free list when a page fault occurs, RAM is scanned and ideal candidates selected and removed from RAM prior to being needed. This is done by maintaining a count of the number of available free pages. If the number of free pages available drops below a predetermined and often tunable value, a scan of RAM using the VMM&#39;s page replacement policy is initiated to look for suitable pages to free and add to the freelist. When the frequency of page faults exceed the ability of the VMM to keep pages available on the freelist page faults must then wait to have their page fault satisfied until the VMM is able to free a page. Once pages become available, threads waiting on pages compete for page allocations. Some may get all the pages needed, while others may get only some or none of the pages requested. In the case that the thread only gets some of the needed pages, this can lead to fragmentation of follow-on requests such as I/O operations done in multiple smaller blocks instead of one larger operation. In addition, a thread with only a portion of it&#39;s required pages may remain blocked, thereby holding pages which could have been used to make further progress by another competing thread. 
         [0013]    Other known strategies for dealing with these problems are to regionalize memory. For example, only certain types of memory requests (for example requests for file pages) are allowed to utilize a percentage of memory. This however can cause memory request to fail and therefore wait even when there are free memory pages available. It also drives up the scan to free ratio as the number of candidate pages decreases (i.e. if only 20% of memory is allocated for file pages and a scan for file pages is commenced, statistically only one in 5 pages inspected will be of the right type). 
       SUMMARY OF THE INVENTION 
       [0014]    Methods, systems, and computer program products are provided for memory pacing. Embodiments include dynamically adjusting the allocation time to fulfill a page request based on the percentage of available memory frames once the page stealer has commenced a scan for pages. The allocation wait time is introduced into the page allocation algorithm, and is inversely proportionally adjusted depending of the percentage of free memory. A typical embodiment is to introduce a predetermined wait time once the page stealer begins a scan for stealable pages. The wait time is increased (for example doubled) as the percentage of available memory continues to fall, (for example doubled every time ten percent of the currently available frames are allocated below the point at which the page stealer commenced it&#39;s scan). Conversely, as the number of available pages increases the amount of wait time is reduced using the same concept. 
         [0015]    Many embodiments of this invention include allowing user defined values to control the initial wait time when the page stealer begins scanning for stealable pages, and the rate at which the wait time will be adjusted, including not adjusting the wait time. Many embodiments also include a dynamic adjustment of these values based on learned behavior, for example increasing the rate at which the wait time is adjusted based on history of the memory consumption rate. Many embodiments also allow the rate of increasing the wait time to be different to the rate of decreasing the wait time. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS  
         [0016]      FIG. 1  sets forth a block diagram of an exemplary multiprocessor computer system capable of allocating memory in accordance with the present invention. 
           [0017]      FIG. 2  sets forth a flow chart illustrating a exemplary method of satisfying a page allocation request. 
           [0018]      FIG. 3  sets forth a flow chart illustrating an exemplary method of satisfying a page allocation request using memory pacing. 
           [0019]      FIG. 4  sets forth a flow chart illustrating an exemplary method of tracking the page free rate when using memory pacing. 
           [0020]      FIG. 5  sets forth a flow chart illustrating an exemplary method of calculating the page wait time for a page allocation request when using memory pacing. 
           [0021]      FIG. 6  sets forth a table illustrating an exemplary method of calculating the page wait time for a page allocation request when using memory pacing. 
           [0022]      FIG. 7  sets forth a flow chart illustrating an exemplary method to input the user defined memory threshold and steal weight values, and to store these within the kernel when using memory pacing. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0023]    The present invention is described to a large extent in this specification in terms of methods for allocating memory within the context of a virtual memory manager. Persons skilled in the art, however, will recognize that any computer system that includes suitable programming means for operating in accordance with the disclosed methods also falls well within the scope of the present invention. Suitable programming means include any means for directing a computer system to execute the steps of the method of the invention, including for example, systems compromised of processing units and arithmetic-logic circuits could to computer memory, which systems have the capability of storing in computer memory, which computer memory includes electronic circuits configured to store data and program instructions, programmed steps of the method of the invention for execution by a processing unit. 
         [0024]    The invention also may be embodied in a computer program product, such as a diskette or other recording medium, for use with any suitable data processing system. Embodiments of a computer program product may be implemented by use of any recording medium for machine-readable information, including magnetic media, optical media, solid-state media, or other suitable media. Persons skilled in the art will immediately recognize that any computer system having suitable programming means will be capable of executing the steps of the method of the invention as embodied in a program product. Persons skilled in the art will recognize immediately that, although most of the exemplary embodiments described in this specification are orientated to software installed and executing on computer hardware, nevertheless, alternative embodiments implemented as firmware or as hardware are well within the scope of the present invention. 
         [0025]    Exemplary methods, system, and computer program products for pacing memory in a multiprocessor computer system according to embodiments of the present invention are described with reference to the accompanying drawings. 
         [0026]    Referring to  FIG. 1 , a block diagram of a data processing system is depicted in accordance with a preferred embodiment of the present invention. Data processing system  100  may be a symmetric multiprocessor (SMP) system including a plurality of processors  102  and  104  connected to system bus  106 . Also connected to system bus  106  is memory controller/cache  108 , which provides an interface to local memory  109 . I/O Bus Bridge  110  is connected to system bus  106  and provides an interface to I/O bus  112 . Memory controller/cache  108  and I/O Bus Bridge  110  may be integrated as depicted. 
         [0027]    Peripheral component interconnect (PCI) bus bridge  114  connected to I/O bus  112  provides an interface to PCI local bus  116 . A number of modems may be connected to PCI local bus  116 . Typical PCI bus implementations will support four PCI expansion slots or add-in connectors. Communications links to clients may be provided through modem  118  and network adapter  120  connected to PCI local bus  116  through add-in connectors. 
         [0028]    Additional PCI bus bridges  122  and  124  provide interfaces for additional PCI local buses  126  and  128 , from which additional modems or network adapters may be supported. In this manner, data processing system  100  allows connections to multiple network computers. A memory-mapped graphics adapter  130  and hard disk  132  may also be connected to I/O bus  112  as depicted, either directly or indirectly. 
         [0029]    Those of ordinary skill in the art will appreciate that the hardware depicted in  FIG. 1  may vary. For example, other peripheral devices, such as optical disk drives and the like, also may be used in addition to or in place of the hardware depicted. The depicted example is not meant to imply architectural limitations with respect to the present invention. 
         [0030]    The data processing system depicted in  FIG. 1  may be, for example, an IBM eServer pSeries system, a product of International Business Machines Corporation in Armonk, N.Y., running the Advanced Interactive Executive (AIX) operating system or LINUX operating system. The local operating system is stored in local memory  109 , which is often referred to as kernel memory. 
         [0031]    An object oriented programming system such as Java may run in conjunction with the operating system and provide calls to the operating system from Java programs or applications executing on data processing system  100 . “Java” is a trademark of Sun Microsystems, Inc. Instructions for the operating system, the object-oriented programming system, and applications or programs are located on storage devices, such as hard disk drive  126 , and may be loaded into main memory  104  for execution by processors  102 ,  104 . 
         [0032]    Those of ordinary skill in the art will appreciate that the hardware in  FIG. 1  may vary depending on the implementation. Other internal hardware or peripheral devices, such as flash read-only memory (ROM), equivalent nonvolatile memory, or optical disk drives and the like, may be used in addition to or in place of the hardware depicted in  FIG. 1 . 
         [0033]      FIG. 2  sets forth a flow chart illustrating a method of handling a page fault. When the page fault  201  occurs a check is made to determine how many free pages remain  202 . If the number of free pages remaining are at or below a minfree threshold value used to indicate a shortage of free pages, a process to free pages is initiated. Following on from the decision to initiate the process of freeing memory pages, a check is performed to see if the process of freeing pages is currently active  203 . If the process of finding and freeing pages is not active, it will be activated  204 . 
         [0034]    In the event that the number of free memory pages is at or below the memory threshold value for free pages  202  and the check to see if the process of freeing pages  203  has been made, a further check is performed to see if there are any free memory pages available  206 . If there are no free memory pages available the system needs to wait for a free page to become available  207  before a page can be allocated  205 . 
         [0035]    In the event that a free page is available  206 , or that the initial check that the number of free pages was greater than the threshold value to activate the process to free memory pages ( 202 ), a page from the list of free pages will be allocated  205  to satisfy the page fault  201 . 
         [0036]      FIG. 3  sets forth a flow chart illustrating a method of handling a page fault with the addition of memory pacing. When the page fault occurs  301  a check is made to determine how many free pages are remaining on the free page list  302 . If it is determined that the number of free pages on the free page list is at or below the minfree threshold value, a check is made to determine if the process of freeing pages has been started  303 . If the process of freeing memory pages has not been started  303 , but needs to be started according to the check performed  302 , the process of freeing pages is initiated  304 . 
         [0037]    With the checks done to confirm if the process to free pages is needed  302 ,  303 ,  304 , a check is done to see if the number of pages on the free list is at or below the memory pacing value  305 . This check is independent of the check to see if page replacement should be initiated  302 . The number of free pages remaining before initiating memory pacing  305  could therefore be set at, or below the number of pages free remaining before initiating the process to free memory pages. 
         [0038]    If the number of pages remaining on the free list is at or below the memory pacing threshold value  305  a memory pacing wait time is calculated  306 . The thread waits for the period of time  307  which was calculated  306 . 
         [0039]    If the number of free pages remaining is above the memory pacing threshold value  305 , or once the page fault handler has waited  307  the appropriate amount of time  306 , a check is made to see if there are any free pages available to satisfy the page fault  308 . If there are no free memory pages available  308 , the page fault handler must wait for a page to become free  309 . If there is a free memory page available  308 , or the page fault handler has waited until a free page becomes available  309 , the free memory page will be allocated  310 . 
         [0040]      FIG. 4  sets forth a flow chart illustrating a method of tracking the amount of time, on average per page, that it takes to free a page once the page stealer has been activated. 
         [0041]    When the page replacement process is started  401 , the start time is recorded  402 . As pages are freed during the scan and free phase of the page replacement process  403  a running count of the number of pages freed is kept. Once the page replacement process  401  has completed the completion time is recorded  404 . 
         [0042]    The page replacement process calculates the amount of time taken to complete it&#39;s work  405  by subtracting the recorded start time  402  from the recorded finish time  404 . Dividing the time taken to steal pages  405  by the number of pages freed during the scan and free cycle  403  a per page steal time is calculated  406  for this page replacement cycle. 
         [0043]    The per page steal time calculated  406  for this iteration of the page replacement processes is added to the sum of the previous page replacement cycles and divided by the total number of times the page replacement process has run to compute an average page steal time  407 . 
         [0044]    For simplification  FIG. 4  shows the average steal time as a running average since the last system boot. It is possible to only keep this running average for the last ‘n’ iterations of the page stealer where ‘n’ could be a user tunable value. This would allow fine tuning of the page steal average bases weighted in favor of the current workload. 
         [0045]      FIG. 5  sets forth a flow chart illustrating a method of computing the memory pacing wait time when the number of free pages is at or below the memory pacing threshold value. 
         [0046]    A calculation is performed to compute the percentage below the memory pacing threshold  501 . For example, if the memory pacing threshold value is 100 pages, and the current number of available pages is 90, the percentage below the memory pacing threshold would be 10%. 
         [0047]    A wait time multiplier is calculated  502  based on the percentage below the memory pacing value calculated  501 . In this exemplary example, the percentage below the memory pacing value calculated  501  was multiplied by 0.1. The result of which was added to 1. Taking the example given where the memory pacing threshold is 100 pages, and the number of pages available is 90, the calculated percentage below the memory pacing threshold is 10. This value 10 multiplied by 0.1 equals 1, which when added to 1 equals 2. The value 2 then becomes the calculated wait multiplier  502 . 
         [0048]    The average page steal time ( FIG. 4 ) is retrieved  503 . The average page steal time is multiplied by a user defined parameter which applies a weighting to the average page steal time. For example if this value is 50%, the calculated page free weight value will be 50% of the currently computed average page steal time as calculated in  FIG. 4 . The wait multiplier calculated  502  is multiplied by the weighted page free time  504  to calculate the wait time  505 . 
         [0049]      FIG. 6  sets forth an example table for illustrative purposes depicting the steps to calculate the memory pacing delay value. For illustrative purposes the user defined threshold value is assumed to be 100, the user defined steal weight is assumed to be 50%, and the average page steal time is assumed to be 2 us. In this example, when the available free pages  601  is 90,the percentage below the memory pacing value  602  is 10%, and the weight multiplier  603  is calculated to be 2 (10% below the threshold value, multiplied by 0.1 plus 1 equals 2). In this example the average page steal time is 2 us and the user defined weighting parameter is 50%, which gives a calculated steal weight  604  of 1 (50% of 2 us). The computed wait time  605  will be 1 us (weighted per-page steal time  604 ) multiplied by 2 (wait multiplier  603 ) which equals 2 us. As shown in  FIG. 6 , the wait time  605  increases as the amount of free pages  601  decreases. To achieve this, the weight multiplier  603  is designed to increase as the number of free pages decreases. The adjusted steal time  604  is used to adjust the sensitivity of memory pacing algorithm. This is achieved by adjusting the calculated average steal time to allow the delay to be less than the actual calculated page steal time. 
         [0050]      FIG. 7  sets forth a flow chart illustrating a method to input the user defined parameters for memory threshold and steal weight which are store in the kernel for purposes of calculating the memory pacing delay. 
         [0051]    The user is prompted to input a memory threshold value  701  which is stored in a kernel memory location  702 . The user is then prompted to provide a steal weight percentage  703  which is stored in a kernel memory location  704 . 
         [0052]    As described above, to minimize the occurrence of the scenario where a system generates page requests at a faster rate than can be handled without depleting the free pages from the free list, the time that it takes to satisfy a page request can be extended. This process of adding a wait time before allocating a free memory page in response to a page request is referred to herein as memory pacing. Memory pacing is initiated when the available pages on the free list falls below a threshold value. This threshold value can be set at a different value than that used for determining whether a page replacement process, in general, needs to be initiated. In other words, if the number of unallocated pages on a free list falls below a first threshold value, a page replacement policy may be initiated. Then if the number of unallocated pages on the free list falls yet further below a second threshold value, memory pacing may be initiated along with the initiated page replacement policy. In other embodiments, these threshold values may indeed be the same. As the number of pages on the free list continues to drop, the wait time will be further extended by an increasing amount. For example, the wait time can be doubled every time the number of memory free pages is halved. Likewise, as the number of free pages increases, but while still below the threshold value, the wait time can be decreased. As such, the wait time is inversely proportional to the percentage of free memory. Once the number of free pages has recovered above the threshold value, a wait time will no longer be taken into consideration before allocating a free page from the free list. In this way, page requests can be satisfied from the free list at a dynamically adjusting rate so that the free pages in the free list will not become depleted. This avoids encountering longer page fault processing that would otherwise be needed for page replacement when no free pages are available. 
         [0053]    It is important to note that while the present invention has been described in the context of a fully functioning data processing system, those of ordinary skill in the art will appreciate that the processes of the present invention are capable of being distributed in the form of a computer readable medium of instructions in a variety of forms, and that the present invention applies equally regardless of the particular type of signal bearing media actually used to carry out the distribution. Examples of computer readable media include recordable-type media, such as a floppy disk, a hard disk drive, a RAM, CD-ROMs, DVD-ROMs, and transmission-type media, such as digital and analog communications links, wired or wireless communications links using transmission forms, such as, for example, radio frequency and light wave transmissions. The computer readable media may take the form of coded formats that are decoded for actual use in a particular data processing system. 
         [0054]    The description of the present invention has been presented for purposes of illustration and description, and is not intended to be exhaustive or limited to the invention in the form disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art. The embodiment was chosen and described in order to best explain the principles of the invention, the practical application, and to enable others of ordinary skill in the art to understand the invention for various embodiments with various modifications as are suited to the particular use contemplated.