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

• US 6,026,475 A
• Filed: 11/26/1997
• Issued: 02/15/2000
• Est. Priority Date: 11/26/1997
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd. (Samsung Group)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Woodman, Larry William
• Primary Examiner(s): Thai, Tuan V.
• Application Number:
  US08/978,932
• Time in Patent Office: 811 Days
• Field of Search: 711/3, 711/154, 711/200, 711/202, 711/203, 711/204, 711/209, 711/210, 711/118
• US Class Current: 711/202
• CPC Class Codes: G06F 11/3452 Performance evaluation by statistical analysis
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 12/1054 the data cache being concurrently physically addressed
• CPC Class Codes: G06F 2201/81 Threshold
• CPC Class Codes: G06F 2201/815 Virtual middleware or OS functionality using virtual machines to implement generic software techniques for error detection or fault masking G06F11/1484
• CPC Class Codes: G06F 2201/835 Timestamp
• CPC Class Codes: G06F 2201/88 Monitoring involving counting
• CPC Class Codes: G06F 2201/885 Monitoring specific for caches
• CPC Class Codes: G06F 2212/653 Page colouring

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.

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.

2. The method according to claim 1, wherein the step of determining the physical address corresponding to the at least one virtual address further comprises the steps of:

storing, in a table, a physical address for each of the virtual addresses of the computer system; and

retrieving the physical address from the table responsive to value of the at least one virtual address.

3. The method according to claim 1, wherein the step of selecting a new physical address for mapping the virtual address further comprises the steps of:

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 a 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 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.

4. The method according to claim 2, wherein the step of selecting the first physical address selects the physical address substantially including the cache page address associated with the system counter having the highest count.

5. The method according to claim 2, wherein the step of selecting the second physical address selects the physical address substantially including the cache page address associated with the process counter having the lowest count.

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.

7. The memory allocator according to claim 6, wherein the page allocator maps a physical address to a 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.

8. The memory allocator according to claim 6 further comprising:

a list of all of the unmapped pages of physical memory in the computer system; and

a plurality of available lists, one for each one of the plurality of cache page addresses, wherein each one of the plurality of available lists maintains a list of unmapped pages of physical memory having physical addresses substantially including a corresponding cache page address.

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.

11. The method according to claim 10, wherein the step of selecting, from the list of available physical addresses, the first physical address selects the physical address substantially including the cache page address associated with the system counter having the highest count.

12. The method according to claim 10, wherein the step of selecting, from the list, the second physical address selects the physical address substantially including the cache page address associated with the process counter having the lowest count.

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.