Method and apparatus for efficient virtual memory management

• US 6,886,085 B1
• Filed: 08/10/2000
• Issued: 04/26/2005
• Est. Priority Date: 04/19/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gupta, Manish, Franke, Hubertus, Snir, Marc, Shuf, Yefim
• Primary Examiner(s): Ellis, Kevin
• Assistant Examiner(s): HO, THANG H
• Application Number:
  US09/636,049
• Time in Patent Office: 1,720 Days
• Field of Search: 711/159, 711/143, 711/165, 711/128, 711/203, 711133-136, 709/315
• US Class Current: 711/159
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 2212/6028 Prefetching based on hints or prefetch instructions
• CPC Class Codes: G06F 2212/702 Conservative garbage collection
• CPC Class Codes: G06F 9/30047 Prefetch instructions; cache control instructions
• CPC Class Codes: G06F 9/3802 Instruction prefetching

Abstract

A method and an apparatus that improves virtual memory management. The proposed method and apparatus provides an application with an efficient channel for communicating information about future behavior of an application with respect to the use of memory and other resources to the OS, a paging daemon, and other system software. The state of hint bits, which are integrated into page table entries and TLB entries and are used for communicating information to the OS, can be changed explicitly with a special instruction or implicitly as a result of referencing the associated page. The latter is useful for canceling hints. The method and apparatus enables memory allocators, garbage collectors, and compilers (such as those used by the Java platform) to use a page-aligned heap and a page-aligned stack to assist the OS in effective management of memory resources. This mechanism can also be used in other system software.

Claims

1. A method of managing memory in a computer system, said method comprising:

a) maintaining at least one hint bit in an address translation table, said hint bit providing information to a first process about the future use of a corresponding memory portion in said memory by a second process associated with said memory portion; and

b) managing said memory portion in response to said information provided by said hint bit.

2. A method according to claim 1, wherein the state of said hint bit is controlled using a non-privileged instruction.

3. A method according to claim 1, wherein the translation table is comprised of at least one of the following:

a) a page table; and

b) a translation look-aside buffer.

4. A method according to claim 1, wherein a first process includes an operating system of the computer system.

5. A method according to claim 1, wherein said memory portion includes a memory page.

6. A method according to claim 1, further comprising:

a buffer comprised of at least one entry wherein said entry includes a memory portion identification for a memory portion having its corresponding hint bit set to a preselected state; and

wherein said buffer is used by a first process to identify said portion of memory with information provided by said hint bit.

7. A method according to claim 1, wherein:

said hint bit information indicates that said memory portion will never again be referenced by a second process currently associated with said memory portion; and

said managing step in response to the information in said hint bit includes disassociating said memory portion from a second process.

8. A method according to claim 1, wherein:

said hint bit information indicates that said memory portion is not likely to be referenced in the future by a second process currently associated with said memory portion; and

said managing step in response to the information in said hint bit includes disassociating said memory portion from a second process.

9. A method according to claim 1, wherein:

said hint bit information indicates that said memory portion is not likely to be referenced in the future by a second process currently associated with said memory portion; and

said managing step in response to the information in said hint bit includes disassociating said memory portion from a second process if available memory space is below a threshold.

10. A method according to claim 1, wherein:

said hint bit information indicates that said memory portion is likely to be referenced in the future by a second process currently associated with said memory portion; and

said managing step in response to the information in said hint bit includes not disassociating said memory portion from a second process unless available memory space is below a threshold.

11. A method according to claim 1, wherein:

said hint bit information indicates that said memory portion has no useful data for a second process currently associated with said memory portion; and

said managing step in response to the information in said hint bit includes;

disassociating of said memory portion assignment before disassociating of another memory portion assignment from a second process if the hint bit information for said other memory portion indicates that said other memory portion has useful data.

12. A method according to claim 1, wherein:

said hint bit information indicates that said memory portion has no useful data for a second process currently associated with said memory portion; and

said managing step in response to the information in said hint bit includes discarding the data in said memory portion even if said memory portion has been modified.

13. A method according to claim 1, wherein:

when a first process is disassociating said memory portion, checking whether said hint bit information indicates that said memory portion has no useful data for a second process currently associated with said memory portion; and

if said hint bit information indicates that said memory portion has no useful data for a second process currently associated with said memory portion;

then said managing step in response to the information in said hint bit includes discarding the data in said memory portion even if said memory portion has been modified.

14. A method according to claim 1, wherein:

when a memory portion fault is generated, handling said memory portion fault includes checking whether said hint bit information indicates whether and how a memory portion is to be initialized on a memory portion fault; and

if said hint bit information indicates whether and how said memory portion is to be initialized on a memory portion fault;

then

said managing step in response to the information in said hint bit includes initializing a memory portion according to the information indicated by said hint bit.

15. A method according to claim 1, wherein:

when a second process references a memory portion, checking whether said hint bit information indicates that said memory portion has no useful data for said second process associated with said memory portion; and

if said hint bit information indicates that said memory portion has no useful data for said second process associated with said memory portion;

then changing the information in said hint bit to indicate that said memory portion has useful data.

16. A method according to claim 15, wherein said reference is a store operation.

17. A method according to claim 15, wherein said change is accomplished simply as a result of said second process referencing said memory portion and without involving a first process.

18. A method according to claim 1, wherein:

when a second process references a memory portion, checking whether said hint bit information indicates that

said memory portion is not likely to be referenced in the future by said second process associated with said memory portion; and

if said hint bit information indicates that said memory portion is not likely to be referenced in the future by said second process associated with said memory portion;

then changing the information in said hint bit to indicate that said memory portion is likely to be referenced in the future.

19. A method according to claim 18, wherein said change is accomplished simply as a result of said second process referencing said memory portion and without involving a first process.

20. A method according to claim 1, wherein:

when a second process references a memory portion, checking whether said hint bit information indicates that

said memory portion has no useful data for said second process associated with said memory portion; and

if said hint bit information indicates that said memory portion has no useful data for said second process associated with said memory portion;

then generating a memory portion fault and handling a memory portion fault according to claim 14.

21. A method according to claim 20, wherein said reference is a load operation.

22. A method according to claim 1, wherein for a memory portion that is a part of heap space and is identified as having only unreachable objects, a hint bit is set to indicate that said memory portion has no useful data.

23. A method according to claim 1, wherein for a memory portion that is a part of heap space and is identified by a garbage collector as having only unreachable objects, a hint bit is set by a garbage collector to indicate that said memory portion has no useful data.

24. A method according to claim 1, wherein upon deallocation of a memory portion that is a part of heap space, said hint bit is set (by a second process code) to indicate that said memory portion has no useful data.

25. A method according to claim 1, wherein upon reclamation of a memory portion that is a part of stack space said hint bit is set (by a second process code) to indicate that said memory portion has no useful data.

26. A method according to claims 1, wherein when the number of memory portions for which a hint bit is set to indicate that said memory portions have no useful data, exceed a certain threshold, then for a fraction of said memory portions a hint bit is set to indicate that said memory portions are likely to be referenced soon, while for the other fraction of said memory portions a hint bit is set to indicate that said other memory portions are not likely to be referenced soon.

27. A method according to claim 1, wherein when a second process references a memory portion in a first level of a memory hierarchy, and said memory portion is not available in said first level of a memory hierarchy, but is available in a second level of memory hierarchy;

and if said hint bit information indicates that said memory portion has no useful data;

then said managing step in response to the information in said hint bit includes

freeing said memory portion in said second level of memory hierarchy, and not transferring the content of said memory portion to said first level of memory hierarchy; and

wherein said first level of memory hierarchy is closer to a processor than said second level of a memory hierarchy; and

wherein the freeing step is comprised of at least one of the following

a) invalidating said memory portion,

b) deallocating a resource associated with said memory portion.

28. In a computer system having a hierarchical memory structure, with said structure having at least a first level of memory (closer to a processor) and a second level of memory (further away from a processor), a method of reducing write backs of data from said first level of memory to said second level of memory, and a method of reducing the number of reads, from said second level of memory to said first level of memory, said method comprising:

maintaining at least one hint bit in an address translation table of said memory structure, said hint bit for indicating that data in a corresponding memory portion is useless; and

discarding data in said memory portion in a first level of memory when said hint bit corresponding to said memory portion indicates that said data is useless, whereby said useless data is not written back to said second level of memory, discarding data in said memory portion in a second level of memory when said hint bit corresponding to said memory portion indicates that said data is useless, whereby said useless data is not read into said first level of memory and said data is invalidated in said second level of memory.

29. A method as recited in claim 28, wherein said first level of memory comprises a random access memory, and

said second level of memory comprises a hard drive.

30. A method as recited in claim 28, wherein said first level of memory comprises a random access memory, and said second level of memory comprises a random access memory.

31. Apparatus for managing memory in a computer system, said apparatus comprising:

a) an address translation table for maintaining at least one hint bit, said hint bit providing information to a first process about the future use of a corresponding memory portion in said memory by a second process associated with said memory portion; and

b) means for managing said memory portion in response to said information provided by said hint bit.

32. Apparatus according to claim 31, wherein the state of said hint bit is controlled using a non-privileged instruction.

33. Apparatus according to claim 31, wherein the translation table is comprised of at least one of the following:

a) a page table; and

b) a translation look-aside buffer.

34. Apparatus according to claim 31, further comprising:

a buffer comprised of at least one entry wherein said entry includes a memory portion identification for a memory portion having its corresponding hint bit set to a preselected state; and

wherein said buffer is used by a first process to identify said portion of memory with information provided by said hint bit.

35. Apparatus according to claim 31, wherein:

when a memory portion fault is generated, handling said memory portion fault includes checking whether said hint bit information indicates whether and how a memory portion is to be initialized on a memory portion fault; and

if said hint bit information indicates whether and how said memory portion is to be initialized on a memory portion fault;

then said managing means includes means for initializing a memory portion according to the information indicated by said hint bit.

36. Apparatus according to claim 31, further comprising:

means for checking, when a second process references a memory portion, whether said hint bit information indicates that said memory portion has no useful data for said second process associated with said memory portion; and

means for changing the information in said hint bit to indicate that said memory portion has useful data, if said hint bit information indicates that said memory portion.

37. Apparatus according to claim 31, further comprising:

means for checking, when a second process references a memory portion, whether said hint bit information indicates that said memory portion is not likely to be referenced in the future by said second process associated with said memory portion; and

means for changing the information in said hint bit to indicate that said memory portion is likely to be referenced in the future, if said hint bit information indicates that said memory portion is not likely to be referenced in the fixture by said second process associated with said memory portion.

38. Apparatus according to claim 31, further comprising:

means for checking, when a second process references a memory portion, whether said hint bit information indicates that said memory portion has no useful data for said second process associated with said memory portion; and

means for generating a memory portion fault and handling a memory portion fault according to claim 35, if said hint bit information indicates that said memory portion has no useful data for said second process associated with said memory portion.

39. Apparatus according to claim 31, wherein when the number of memory portions for which a hint bit is set to indicate that said memory portions have no useful data, exceed a certain threshold, then for a fraction of said memory portions a hint bit is set to indicate that said memory portions are likely to be referenced soon, while for the other fraction of said memory portions a hint bit is set to indicate that said other memory portions are not likely to be referenced soon.

40. Apparatus according to claim 31, wherein when a second process references a memory portion in a first level of a memory hierarchy, and said memory portion is not available in said first level of a memory hierarchy, but is available in a second level of memory hierarchy, and if said hint bit information indicates that said memory portion has no useful data;

then said managing means includes

means for freeing said memory portion in said second level of memory hierarchy, and not transferring the content of said memory portion to said first level of memory hierarchy; and

wherein said first level of memory hierarchy is closer to a processor than said second level of a memory hierarchy; and

wherein the freeing means is comprised of at least one of the following

a) means for invalidating said memory portion,

b) means for deallocating a resource associated with said memory portion.

41. In a computer system having a hierarchical memory structure, with said structure having at least a first level of memory (closer to a processor) and a second level of memory (further away from a processor), apparatus for reducing write backs of data from said first level of memory to said second level of memory, and for reducing the number of reads, from said second level of memory to said first level of memory, said apparatus comprising:

means for maintaining at least one hint bit in an address translation table of said memory structure, said hint bit for indicating that data in a corresponding memory portion is useless; and

means for discarding data in said memory portion in a first level of memory when said hint bit corresponding to said memory portion indicates that said data is useless, whereby said useless data is not written back to said second level of memory.

42. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for managing memory in a computer system, said method steps comprising:

a) maintaining at least one hint bit in an address translation table, said hint bit providing information to a first process to about future use of a corresponding memory portion in said memory by a second process associated with said memory portion; and

b) managing said memory portion in response to said information provided by said hint bit.

43. A program storage device according to claim 42, wherein the state of said hint bit is controlled using a non-privileged instruction.