Method for dynamically remapping a virtual address to a physical address to maintain an even distribution of cache page addresses in a virtual address space

In a computer system having a cache memory, a memory allocator comprising:

• a plurality of system counters, one for each of a plurality of cache page addresses for the cache memory, each one of the plurality of system counters identifying a number of unmapped pages of a physical memory wherein physical memory address includes the respective cache page address;
• a plurality of process counters corresponding to an associated process, each one of the plurality of process counters corresponding to a different cache page address and indicating the number of pages of the associated process that map to the cache page address;
• a plurality of activity counters, each one of the activity counters corresponding to a cache page address and indicating a number of times that a virtual address associated with the cache page address is detected in the computer system;
• and
• a page allocator for mapping a physical address to a virtual address in response to the values of the each one of the plurality of system counters, the values of each one of the plurality of process counters, and the values of each one of the plurality of activity counters, such that there is a substantially even distribution of cache page addresses included in physical memory addresses mapped to a plurality of virtual addresses in the virtual address space;
• means for faulting the computer system at random intervals;
• means for recording a virtual address being referenced when the computer is faulted;
• and
• means for incrementing one of the plurality of activity counters, where the one of the plurality of activity counters that is incremented corresponds to a cache page address related to the virtual address being referenced.

In a computer system having a cache memory, a method of re-mapping a virtual address to a physical address to improve performance of the computer system, comprising the steps of:

• (A) identifying at least one virtual address that is incurring delay in the computer system, said identifying including:
• (i) recording in a list, for each of a plurality of faults that occur during operation of the computer system, a virtual address that is being referenced in the computer system;
• (ii) maintaining for each of a plurality of cache page addresses, a count of the number of virtual addresses in the list that map to physical addresses substantially including the cache page address;
• and
• (iii) selecting as the at least one virtual address a virtual address in the list associated with the cache page address having the highest count;
• (B) determining a physical address of a memory page corresponding to the at least one virtual address, wherein the physical address substantially includes a cache page address for the cache memory;
• (C) selecting a new physical address for mapping the at least one virtual address, wherein the new physical address is selected to maintain a substantially even distribution of cache page addresses included in physical addresses of memory pages corresponding to a plurality of virtual addresses in the virtual address space;
• and
• (D) copying data located at the determined physical address to the memory page indicated by the new physical address.

In a computer system having a cache memory, a method of re-mapping a virtual address to a physical address to improve performance of the computer system, comprising the steps of:

• (A) identifying at least one virtual address that is incurring delay in the computer system, said identifying including:
• (B) determining a physical address of a memory page corresponding to the at least one virtual address, wherein the physical address substantially includes a cache page address for the cache memory;
• (C) selecting a new physical address for mapping the at least one virtual address, wherein the new physical address is selected to maintain a substantially even distribution of cache page addresses included in physical addresses of memory pages corresponding to a plurality of virtual addresses in the virtual address space, said selecting a new physical address including:
• maintaining, for each of a plurality of cache page addresses, a system counter indicating a number of physical addresses substantially including the respective cache page address that are available for mapping to virtual addresses;
• maintaining, for at least one process executing in the computer system, for each of said plurality of cache page addresses, a process counter indicating a number of virtual addresses of the at least one process that are mapped to physical addresses substantially including the respective cache page address;
• selecting, from a list of available physical addresses, a first physical address responsive to the system count;
• selecting, from the list of available physical addresses, a second physical address responsive to the process counts;
• and
• selecting either the first physical address or the second physical address as the new physical address responsive to a predetermined priority;
• and
• (D) copying data located at the determined physical address to the memory page indicated by the new physical address.

In a computer system having a cache memory, a memory allocator comprising:

• a plurality of system counters, one for each of a plurality of cache page addresses for the cache memory, each one of the plurality of system counters for identifying a number of free pages of a physical memory that map to the respective cache page address;
• at least one plurality of process counters corresponding to at least one associated process, each one of the plurality of process counters corresponding to a different cache page address and indicating the number of pages of the associated process that map to the cache page address;
• at least one plurality of activity counters, each one of the activity counters corresponding to a cache page address and indicating a number of times that a virtual address associated with the cache page address is detected in the computer system;
• a page allocator for assigning a physical address to a virtual address in response to the values of each one of the plurality of system counters, the values of each one of the at least one plurality of process counters, and the values of each of the plurality of activity counters, the page allocator assigning the physical address to the virtual address when one of the plurality of activity counters indicates that references to a virtual address mapped to a physical address substantially including the cache page address associated with that activity counter is incurring undesirable delay;
• means for faulting the computer system at random intervals;
• means for recording a virtual address being referenced when the computer is faulted;
• and
• means for incrementing one of the plurality of activity counters, where the one of the plurality of activity counters that is incremented corresponds to a cache page address related to the virtual address being referenced.