Methods and mechanisms for proactive memory management

• US 6,910,106 B2
• Filed: 12/20/2002
• Issued: 06/21/2005
• Est. Priority Date: 10/04/2002
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Fortin, Michael R., Ergan, Cenk, Iyigun, Mehmet, Sechrest, Stuart
• Primary Examiner(s): Anderson, Matthew D.
• Application Number:
  US10/325,591
• Publication Number:
  US 20040068627A1
• Time in Patent Office: 914 Days
• Field of Search: 711133-137, 711159-160
• US Class Current: 711/136
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 12/122 of the least frequently used [LFU] type, e.g. with individual count value

Abstract

A proactive, resilient and self-tuning memory management system and method that result in actual and perceived performance improvements in memory management, by loading and maintaining data that is likely to be needed into memory, before the data is actually needed. The system includes mechanisms directed towards historical memory usage monitoring, memory usage analysis, refreshing memory with highly-valued (e.g., highly utilized) pages, I/O pre-fetching efficiency, and aggressive disk management. Based on the memory usage information, pages are prioritized with relative values, and mechanisms work to pre-fetch and/or maintain the more valuable pages in memory. Pages are pre-fetched and maintained in a prioritized standby page set that includes a number of subsets, by which more valuable pages remain in memory over less valuable pages. Valuable data that is paged out may be automatically brought back, in a resilient manner. Benefits include significantly reducing or even eliminating disk I/O due to memory page faults.

Claims

1. A computer-implemented method, comprising:

identifying pages in a memory and pages maintained in secondary storage device based on page value data associated with each identified page; and

populating the memory with at least some pages from the secondary storage device, comprising replacing at least some of the pages in memory having relatively lower values with at least some pages from the secondary storage device having relatively higher values, before a demand for at least some of the pages having higher values is received.

2. The method of claim 1 wherein identifying values for pages comprises establishing a value based on a current context.

3. The method of claim 1 wherein identifying values for pages in a memory and values for pages maintained in secondary storage device comprises identifying low-value pages and high-value pages.

4. The method of claim 1 further comprising, compressing at least some of the pages in memory having relatively lower values to provide space for at least some pages from the secondary storage device having relatively higher values, before a demand for at least some of the pages having higher values is received.

5. The method of claim 1 further comprising determining the page value data.

6. The method of claim 5 wherein determining the page value data comprises reading at least part of the page value data from a file.

7. The method of claim 6 wherein the file comprises training data obtained from measuring page usage on another computer system.

8. The method of claim 5 wherein determining the page value data comprises tracing usage of pages to determine at least part of the page value data.

9. The method of claim 8 wherein tracing usage of pages comprises tracing access patterns.

10. The method of claim 8 wherein tracing usage of pages comprises tracing access frequency.

11. The method of claim 8 wherein tracing page usage comprises recording time data corresponding to a last page usage.

12. The method of claim 8 wherein tracing page usage comprises counting page usage in a time period.

13. The method of claim 8 wherein tracing page usage comprises maintaining data corresponding to a creation time of a page.

14. The method of claim 8 further comprising, saving, to a persistent store, data corresponding to the traced page usage for at least some of the pages.

15. The method of claim 8 wherein tracing page usage comprises evaluating page access information.

16. The method of claim 15 wherein evaluating page access information comprises, reading page table entry access bits.

17. The method of claim 15 wherein evaluating page access information comprises evaluating when the page access information is reset.

18. The method of claim 15 wherein evaluating page access information comprises determining a rate of resetting the page access information.

19. The method of claim 18 further comprising, logging the rate.

20. The method of claim 15 wherein evaluating page access information comprises determining a rate at which a page is accessed.

21. The method of claim 20 further comprising, logging the rate.

22. The method of claim 15 wherein evaluating page access information comprises detecting page faults.

23. The method of claim 8 wherein tracing usage of pages comprises detecting file read and write requests.

24. The method of claim 8 wherein tracing usage of pages comprises at least one of:

reading process working set information, recording data as pages are transferred out of memory, and recording data as pages are trimmed from working sets.

25. The method of claim 8 wherein tracing page usage comprises recording data in response to an event or context.

26. The method of claim 25 wherein the data is recorded in response to at least one of:

a switched task, a created window, a detected action, a change in which window has focus, a user input event, a hibernation-related event of the computer system, a standby-related event of the computer system, a system boot-related event of the computer system;

a program launch, a program shutdown, a change in a user of the system, a logon, and a network connection event, a media-related event.

27. The method of claim 26 wherein the data is recorded in response to a program-specified context.

28. The method of claim 5 wherein determining the page value data includes determining a cost of an I/O transfer for at least one page.

29. The method of claim 5 wherein determining the page value data includes calculating the priority value for a selected page based on a plurality of page usage factors.

30. The method of claim 29 wherein calculating the priority value based on a plurality of page usage factors comprises weighing one page usage factor relative to another factor.

31. The method of claim 5 wherein determining the page value data includes mathematically combining page usage frequency data with time of last page usage information for the selected page.

32. The method of claim 5 wherein identifying pages in a memory comprises, selecting a subset of pages available to the computer system.

33. The method of claim 32 wherein the subset of pages comprises pages corresponding to a particular file.

34. The method of claim 33 wherein the subset of pages comprises pages corresponding to a particular section in memory.

35. The method of claim 33 wherein the subset of pages comprises pages corresponding to a particular section in storage.

36. The method of claim 1 further comprising, grouping selected pages together into a page group, and maintaining the page value data in association with the group.

37. The method of claim 36 wherein grouping selected pages together comprises grouping pages based on their times of last access.

38. The method of claim 36 wherein grouping selected pages together comprises grouping pages based on usage patterns.

39. The method of claim 36 wherein grouping selected pages together comprises grouping pages based on frequency of usage.

40. The method of claim 36 wherein grouping selected pages together comprises grouping pages based on a virtual location.

41. The method of claim 36 wherein grouping selected pages together comprises grouping pages based on a time of usage.

42. The method of claim 36 wherein time of usage comprises day of week information.

43. The method of claim 36 wherein time of usage time of day information.

44. The method of claim 36 wherein grouping selected pages together comprises grouping pages based on a physical location.

45. The method of claim 36 wherein grouping selected pages together comprises grouping pages based on times that the pages were trimmed from memory.

46. The method of claim 36 wherein grouping selected pages together comprises grouping pages based on I/O transfer efficiency.

47. The method of claim 36 wherein grouping selected pages together comprises grouping pages based on which processes use the pages.

48. The method of claim 36 wherein grouping selected pages together comprises grouping pages based on process lifetime information.

49. The method of claim 36 wherein grouping selected pages together comprises grouping pages based on fault information.

50. The method of claim 36 wherein grouping selected pages together comprises grouping pages based on at least one event.

51. The method of claim 36 wherein grouping selected pages together comprises grouping pages based on a specific user'"'"'s processes.

52. The method of claim 36 wherein grouping selected pages together comprises grouping pages based on context data.

53. The method of claim 52 further comprising, receiving the context data from an application program.

54. The method of claim 52 further comprising recording context data in association with usage of a page.

55. The method of claim 54 wherein recording context data comprises recording power state information.

56. The method of claim 54 wherein recording context data comprises recording disk state information.

57. The method of claim 54 wherein recording context data comprises recording event information.

58. The method of claim 57 wherein recording event information comprises recording a memory-related event.

59. The method of claim 1 further comprising, ranking the identified pages based on their respective page value data, and wherein populating the memory comprises loading pages to memory in an order based on the ranking.

60. The method of claim 1 wherein populating the memory comprises loading selected pages from the secondary storage into a standby page set in memory.

61. The method of claim 60 wherein the standby page set comprises a plurality of subsets, and further comprising, logically moving a page from one subset of the standby page set to another subset based on usage data detected for the page.

62. The method of claim 61 wherein logically moving the page comprises moving the page from a frequency-based subset to a time-of-last-usage based subset.

63. The method of claim 61 wherein logically moving the page comprises moving the page from a time-of-last-usage based subset to a frequency-based subset.

64. The method of claim 1 further comprising, saving the page value data associated with at least some of the pages to a persistent store.

65. The method of claim 1 wherein populating the memory comprises loading the pages to the memory in a background operation.

66. The method of claim 65 wherein loading the pages to the memory in a background operation comprises obtaining idle priority data.

67. The method of claim 65 wherein loading the pages to the memory in a background operation comprises observing I/O patterns to determine a transfer time.

68. The method of claim 67 wherein the transfer time is determined based on a likelihood that the transfer will not overlap with a foreground I/O transfer.

69. The method of claim 67 wherein the transfer time is determined based on a likelihood that the transfer will not cause a seek that will slow down a foreground I/O transfer.

70. The method of claim 65 wherein loading the pages to the memory in a background operation comprises evaluating current processor usage and current disk usage.

71. The method of claim 1 wherein populating the memory comprises loading the pages to the memory in a foreground operation.

72. A computer-readable medium having computer-executable instructions for performing the method of claim 1.