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
First Claim
1. In a computer system having a cache memory, a method of re-mapping a virtual address to a physical address to improve performance comprising the steps of:
- identifying a virtual address that is incurring delay in the computer system;
determining a physical address mapped to the virtual address, wherein the physical address includes a cache page address for the cache memory;
selecting an unmapped new physical address for mapping the 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 mapped to a plurality of virtual addresses in virtual address space;
copying data located at the physical memory page indicated by the determined physical address to the physical memory page indicated by the new physical address, and mapping the virtual address to the new physical address;
recording in a list, for each of plurality of faults that occur during operation of the computer system, virtual address that is being referenced in the computer system;
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 including the cache page address; and
selecting as the virtual address virtual address in the list associated with the cache page address having the highest count.
4 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus for dynamically updating virtual to physical address mappings in order to reduce cache thrashing is disclosed in an example computer system having a memory apportioned into a number of pages. A cache is included in the computer system to store a subset of the pages of memory. Each of the pages of memory is addressed by a physical address that includes a cache page address portion. The pages of cache memory are accessed using a cache page address, which corresponds to the cache page address portion of the physical address of a corresponding page of memory. The disclosed system monitors the activity of virtual addresses and uses the activity of virtual addresses to increment cache page address activity counters. The cache page address activity counters are monitored to identify those cache page addresses that are frequently being accessed within a process to identify potential performance problems, such as thrashing. When a cache page address activity count has exceeded a pre-determined threshold, a virtual address associated with that cache page address is mapped to a different physical address having a different cache page address. The new cache page address that is selected for remapping purposes is selected to maintain an even distribution of cache page addresses on a system and process level. The physical page formerly mapped to the virtual address that was associated with a highly active cache page address is returned to a free list of the system, for use by another process. With such an arrangement, adjustments may be made to the virtual to physical translations during execution of a given process in order to improve the overall performance of the process and the overall system.
-
Citations
13 Claims
-
1. In a computer system having a cache memory, a method of re-mapping a virtual address to a physical address to improve performance comprising the steps of:
-
identifying a virtual address that is incurring delay in the computer system; determining a physical address mapped to the virtual address, wherein the physical address includes a cache page address for the cache memory; selecting an unmapped new physical address for mapping the 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 mapped to a plurality of virtual addresses in virtual address space; copying data located at the physical memory page indicated by the determined physical address to the physical memory page indicated by the new physical address, and mapping the virtual address to the new physical address; recording in a list, for each of plurality of faults that occur during operation of the computer system, virtual address that is being referenced in the computer system; 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 including the cache page address; and selecting as the virtual address virtual address in the list associated with the cache page address having the highest count. - View Dependent Claims (2, 3, 4, 5)
-
-
6. 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. - View Dependent Claims (7, 8)
-
-
9. 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.
-
-
10. 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. - View Dependent Claims (11, 12)
-
-
13. 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.
-
Specification