System for maintaining a shared cache in a multi-threaded computer environment

• US 6,078,994 A
• Filed: 05/30/1997
• Issued: 06/20/2000
• Est. Priority Date: 05/30/1997
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Carey, James E.
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): Ellis, Kevin L.
• Application Number:
  US08/866,518
• Time in Patent Office: 1,117 Days
• Field of Search: 711/133, 711/134, 711/135, 711/136, 711/159, 711/160, 702/206
• US Class Current: 711/133
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 12/121 using replacement algorithms

Abstract

In a multi-threaded computing environment, a shared cache system reduces the amount of redundant information stored in memory. A cache memory area provides both global readable data and private writable data to processing threads. A collection mechanism monitors the amount of cache memory available to the processing threads. In particular, a collector thread is executed when needed to reclaim least recently used cache memory.

Claims

1. In a computer, a method of managing a cache memory area having a plurality of cache memory blocks, comprising:

storing data in a first subset of cache memory blocks including a shared memory block, the data in the shared memory block being accessible by a plurality of data accessor tasks;

storing a list of free cache memory blocks in the computer, the free cache memory blocks being cache memory blocks that are not included in the first subset of cache memory blocks;

satisfying a request for a cache memory block from a free cache memory block moved from the list of free cache memory blocks to the first subset of cache memory blocks;

from a data accessor task generating a triggering event in response to satisfying said request, based on the amount of free cache memory blocks;

after satisfying said request, triggering a dedicated collector task, separate from the data access tasks, to execute in the computer in response to the triggering event; and

from the collector task, reclaiming memory blocks from the first subset of cache memory blocks to the list of free cache memory blocks.

2. The method of claim 1 further comprising generating the triggering event based on a minimum threshold of a plurality of free cache memory blocks in the list of free cache memory blocks.

3. The method of claim 1 wherein reclaiming includes identifying a not recently used cache memory block.

4. The method of claim 1 wherein the at least one data accessor and the collector are executed among a plurality of processing units in the computer.

5. The method of claim 1 wherein suspending the execution of the collector in task responsive to a maximum threshold of free cache memory blocks.

6. The method of claim 1 whereby reclaiming comprises communicating to an owner data accessor task that an owned cache memory block is being reclaimed.

7. The method of claim 6 further comprising instructing, from the collector task, the owner data accessor task to write data out of the owned cache memory block.

8. The method of claim 1 wherein the at least one data accessor and the collector are processing threads in a multi-threaded computer system.

9. The method of claim 1 further comprising triggering a flusher task dependent on a periodic timer event to execute in the computer to reclaim modified cache memory blocks from the first subset of cache memory blocks to the list of free cache memory blocks.

30. The method of claim 1 wherein the collector operates to maintain a non-empty list of free cache memory blocks.

10. An apparatus for managing a cache memory area having a plurality of cache memory blocks in a computer, comprising:

a first subset of cache memory blocks having data stored therein, the data being accessible by at least one data accessor;

a list of free cache memory blocks stored in the computer, the free cache memory blocks being cache memory blocks that are not included in the first subset of cache memory blocks;

a request for a cache memory block satisfied from a free cache memory blocks to the first subset of cache memory blocks;

a triggering event generated from a data accessor task in response to satisfying said request based on the amount of free cache memory blocks; and

a collector executing in the computer, after satisfying said request, in response to the triggering event, the collector reclaiming cache memory blocks from the first subset of cache memory blocks to the list of free cache memory blocks.

11. The apparatus of claim 10 wherein the triggering event comprises a minimum threshold of a plurality of free cache memory blocks in the list of free cache memory blocks.

12. The apparatus of claim 10 wherein the collector reclaims cache memory blocks by identifying a not recently used cache memory block.

13. The apparatus of claim 10 further comprising a plurality of processing units in the computer to execute the at least one data accessor and the collector.

14. The apparatus of claim 10 further comprising a maximum threshold of free cache memory blocks to suspend the execution of the collector.

15. The apparatus of claim 10 further comprises comprising a message from the collector task to an owner data accessor task that an owned cache memory block is being reclaimed.

16. The apparatus of claim 15 further comprising an instruction from the collector to the owner data accessor to write data out of the owned cache memory block.

17. The apparatus of claim 10 wherein the at least one data accessor and the collector are processing threads in a multi-threaded computer system.

18. The apparatus of claim 10 further comprising a flusher task executing in the computer dependent on a periodic timer event to reclaim modified cache memory blocks from the first subset of cache memory blocks to the list of free cache memory blocks.

31. The apparatus of claim 11 wherein the threshold is a predetermined number of free cache memory blocks, the predetermined number being greater than 1.

32. The apparatus of claim 11 wherein the threshold is dynamically determined based on usage of the cache memory area.

33. The apparatus of claim 10 wherein the collector operates to maintain a non-empty list of free cache memory blocks.

19. An article of manufacture comprising:

a computer-readable medium for use in a computer having a memory;

a computer-implementable program recorded on the medium to manage a cache memory having a plurality of cache memory blocks, the program comprising the steps of;

storing data in a first subset of cache memory blocks, the data being accessible by at least one data accessor;

storing a list of free cache memory blocks in the computer, the free cache memory blocks being cache memory blocks that are not included in the first subset of cache memory blocks;

satisfying a request for a cache memory block from a free cache memory block moved from the list of free cache memory blocks to the first subset of cache memory blocks;

from a data accessor task generating a triggering event in response to satisfying said request, based on the amount of free cache memory blocks;

after satisfying said request, triggering a collector to execute in the computer in response to the triggering event; and

from the collector, reclaiming cache memory blocks from the first subset of cache memory blocks to the list of free cache memory blocks.

20. The article of claim 19 wherein the program further comprises the step of generating the triggering event based on a minimum threshold of a plurality free cache memory blocks in the list of free cache memory blocks.

21. The article of claim 19 wherein the step of reclaiming includes identifying a not recently used cache memory block.

22. The article of claim 19 wherein the at least one data accessor and the collector are programmed to execute among a plurality of processing units in the computer.

23. The article of claim 19 wherein the program further comprises the step of suspending the execution of the collector in response to a maximum threshold of free cache memory blocks.

24. The article of claim 19 whereby the step of reclaiming comprises communicating to an owner data accessor that an owned cache memory block is being reclaimed.

25. The article of claim 24 wherein the program further comprises the step of instructing, from the collector, the owner data accessor to write data out of the owned cache memory block.

26. The article of claim 19 wherein the at least one data accessor and the collector are programmed as processing threads in a multi-threaded computer system.

27. The article of claim 19 wherein the program further comprises instructions for triggering a flusher task dependent on a periodic timer event to execute in the computer to reclaim modified cache memory blocks from the first subset of cache memory blocks to the list of free cache memory blocks.

28. The method of claim 19 wherein the program further comprises instructions for determining the threshold based on a predetermined number of free cache memory blocks, the predetermined number being greater than 1.

29. The method of claim 19 wherein the program further comprises instructions for dynamically determining the threshold based on usage of the cache memory area over time.

34. The article of claim 20 wherein the program further comprises the step of determining the threshold based on a predetermined number of free cache memory blocks, the predetermined number being greater than 1.

35. The article of claim 20 wherein the program further comprises the step of dynamically determining the threshold based on usage of the cache memory area over time.

36. The article of claim 19 wherein the program further comprises the step of operating the collector to maintain a non-empty list of free cache memory blocks.

37. In a computer, a method of managing a cache memory area having a plurality of cache memory blocks, comprising:

storing data in a first subset of cache memory blocks, the data being accessible by at least one data accessor;

storing a list of free cache memory blocks in the computer, the free cache memory blocks being cache memory blocks that are not included in the first subset of cache memory blocks;

from a data accessor, generating a triggering event based on the amount of free cache memory blocks;

triggering a collector to execute n the computer in response to the triggering event; and

from the collector, reclaiming cache memory blocks from the first subset of cache memory blocks to the list of free cache memory blocks.

38. The method of claim 37 further comprising generating the triggering event based on a minimum threshold of free cache memory blocks.

39. The method of claim 38 further comprising determining the threshold based on a predetermined number of free cache memory blocks, the predetermined number being greater than 1.

40. The method of claim 38 further comprising dynamically determining the threshold based on usage of the cache memory area over time.

41. The method of claim 37 further comprising operating the collector to maintain a non-empty list of free cache memory blocks.

42. The method of claim 37 wherein reclaiming includes identifying a not recently used cache memory block.

43. The method of claim 37 wherein the at least one data accessor and the collector are processing threads in a multi-threaded computer system.

44. The method of claim 37 further comprising suspending the execution of the collector in response to a maximum threshold of free cache memory blocks.

45. The method of claim 37 whereby reclaiming comprises communicating to an owner data accessor that an owned cache memory block is being reclaimed.

46. The method of claim 45 further comprising instructing, from the collector, the owner data accessor to write data out of the owned cache memory block.

47. The method of claim 37 wherein the at least one data accessor and the collector are executed among a plurality of processing units in the computer.

48. The method of claim 37 further comprising triggering a flusher to execute in the computer to reclaim modified cache memory blocks from the first subset of cache memory blocks.

49. An apparatus for managing a cache memory area having a plurality of cache memory blocks in a computer, comprising:

a first subset of cache memory blocks having data stored therein, the data being accessible by at least one data accessor;

a list of free cache memory blocks that are not included in the first subset of cache memory blocks; and

a triggering event generated by a data accessor based on the amount of free cache memory blocks;

a collector executing in the computer in response to the triggering event, the collector reclaiming cache memory blocks from the first subset of cache memory blocks to the list of free cache memory blocks.

50. The apparatus of claim 49 wherein the triggering event comprises a minimum threshold of free cache memory blocks.

51. The apparatus of claim 50 wherein the threshold is a predetermined number of free cache memory blocks, the predetermined number being greater than 1.

52. The apparatus of claim 50 wherein the threshold is dynamically determined based on usage of the cache memory area over time.

53. The apparatus of claim 49 wherein the collector operates to maintain a non-empty list of free cache memory blocks.

54. The apparatus of claim 49 wherein the collector reclaims cache memory blocks by identifying a not recently used cache memory block.

55. The apparatus of claim 49 further comprising a plurality of processing units in the computer to execute the at least one data accessor and the collector.

56. The apparatus of claim 49 further comprising a maximum threshold of free cache memory blocks to suspend the execution of the collector.

57. The apparatus of claim 49 further comprising a message from the collector to an owner data accessor that an owned cache memory block is being reclaimed.

58. The apparatus of claim 57 further comprising an instruction from the collector to the owner data accessor to write data out of the owned cache memory block.

59. The apparatus of claim 49 wherein the at least one data accessor and the collector are processing threads in a multi-threaded computer system.

60. The apparatus of claim 49 further comprising a flusher executing in the computer to reclaim modified cache memory blocks from the first subset of cache memory blocks to the list of free cache memory blocks.

61. An article of manufacture comprising:

a computer-readable medium for use in a computer having a memory;

a computer-implementable program recorded on the medium to manage a cache memory having a plurality of cache memory blocks, the program comprising;

storing data in a first subset of cache memory blocks, the data being accessible by at least one data accessor;

storing a list of free cache memory blocks in the computer, the free cache memory blocks being cache memory blocks that are not included in the first subset of cache memory blocks;

from a data accessor, generating a triggering event, based on the amount of free cache memory blocks;

triggering a collector to execute in the computer in response to the triggering event; and

from the collector, reclaiming cache memory blocks from the first subset of cache memory blocks to the list of free cache memory blocks.

62. The article of claim 61 wherein the program further comprises instructions for generating the triggering event based on a minimum threshold of free cache memory blocks.

63. The article of claim 62 wherein the program further comprises instructions for determining the threshold based on a predetermined number of free cache memory blocks, the predetermined number being greater than 1.

64. The article of claim 62 wherein the program further comprises instructions for dynamically determining the threshold based on usage of the cache memory area over time.

65. The article of claim 61 wherein the program further comprises instructions for operating the collector to maintain a non-empty list of free cache memory blocks.

66. The article of claim 61 wherein the instructions for reclaiming includes identifying a not recently used cache memory block.

67. The article of claim 61 wherein the at least one data accessor and the collector are programmed to execute among a plurality of processing units in the computer.

68. The article of claim 61 wherein the program further comprises instructions for suspending the execution of the collector in response to a maximum threshold of free cache memory blocks.

69. The article of claim 61 whereby the instructions for reclaiming comprises communicating to an owner data accessor that an owned cache memory block is being reclaimed.

70. The article of claim 69 wherein the program further comprises instructions for instructing, from the collector, the owner data accessor to write data out of the owned cache memory block.

71. The article of claim 61 wherein the at least one data accessor and the collector are programmed as processing threads in a multi-threaded computer system.

72. The article of claim 61 wherein the program further comprises instructions for triggering a flusher to execute in the computer to reclaim modified cache memory blocks from the first subset of cache memory blocks to the list of free cache memory blocks.

73. In a computer, a method of managing a cache memory area having a plurality of cache memory blocks, comprising:

storing data in a first subset of cache memory blocks, the data being accessible by at least one data accessor;

storing a list of free cache memory blocks in the computer, the free cache memory blocks being cache memory blocks that are not included in the first subset of cache memory blocks;

triggering a collector to execute in the computer in response to a triggering event; and

from the collector, reclaiming cache memory blocks from the first subset of cache memory blocks to the list of free cache memory blocks, wherein an owner data accessor is informed that an owned cache memory block is being reclaimed.

74. The method of claim 73 further comprising generating the triggering event based on a minimum threshold of free cache memory blocks.

75. The method of claim 74 further comprising determining the threshold based on a predetermined number of free cache memory blocks, the predetermined number being greater than 1.

76. The method of claim 74 further comprising dynamically determining the threshold based on usage of the cache memory area over time.

77. The method of claim 73 further comprising operating the collector to maintain a non-empty list of free cache memory blocks.

78. The method of claim 73 wherein reclaiming includes identifying a not recently used cache memory block.

79. The method of claim 73 wherein the at least one data accessor and the collector are executed among a plurality of processing units in the computer.

80. The method of claim 73 further comprising suspending the execution of the collector in response to a maximum threshold of free cache memory blocks.

81. The method of claim 73 further comprising instructing, from the collector, the owner data accessor to write data out of the owned cache memory block.

82. The method of claim 73 wherein the at least one data accessor and the collector are processing threads in a multi-threaded computer system.

83. The method of claim 73 further comprising triggering a flusher to execute in the computer to reclaim modified cache memory blocks from the first subset of cache memory blocks to the list of free cache memory blocks.

84. An apparatus for managing a cache memory area having a plurality of cache memory blocks in a computer, comprising:

a first subset of cache memory blocks having data stored therein, the data being accessible by at least one data accessor;

a list of free cache memory blocks stored in the computer, the free cache memory blocks being cache memory blocks that are not included in the first subset of cache memory blocks; and

a collector executing in the computer in response to a triggering event, the collector reclaiming cache memory blocks from the first subset of cache memory blocks to the list of free cache memory blocks, wherein an owner data accessor is informed that an owned cache memory block is being reclaimed.

85. The apparatus of claim 84 wherein the triggering event comprises a minimum threshold of free cache memory blocks.

86. The apparatus of claim 85 wherein the threshold is a predetermined number of free cache memory blocks, the predetermined number being greater than 1.

87. The apparatus of claim 85 wherein the threshold is dynamically determined based on usage of the cache memory area over time.

88. The apparatus of claim 84 wherein the collector operates to maintain a non-empty list of free cache memory blocks.

89. The apparatus of claim 84 wherein the collector reclaims cache memory blocks by identifying a not recently used cache memory block.

90. The apparatus of claim 84 further comprising a plurality of processing units in the computer to execute the at least one data accessor and the collector.

91. The apparatus of claim 84 further comprising a maximum threshold of free cache memory blocks to suspend the execution of the collector.

92. The apparatus of claim 84 further comprising an instruction from the collector to the owner data accessor to write data out of the owned cache memory block.

93. The apparatus of claim 84 wherein the at least one data accessor and the collector are processing threads in a multi-threaded computer system.

94. The apparatus of claim 84 further comprising a flusher executing in the computer to reclaim modified cache memory blocks from the first subset of cache memory blocks to the list of free cache memory blocks.

95. An article of manufacture comprising:

a computer-readable medium for use in a computer having a memory;

a computer-implementable program recorded on the medium to manage a cache memory having a plurality of cache memory blocks, the program comprising instructions for;

storing data in a first subset of cache memory blocks, the data being accessible by at least one data accessor;

storing a list of free cache memory blocks in the computer, the free cache memory blocks being cache memory blocks that are not included in the first subset of cache memory blocks;

triggering a collector to execute in the computer in response to a triggering event; and

from the collector, reclaiming cache memory blocks from the first subset of cache memory blocks to the list of free cache memory blocks, wherein an owner data accessor is informed that an owned cache memory block is being reclaimed.

96. The article of claim 95 wherein the program further comprises instructions for generating the triggering event based on a minimum threshold of free cache memory blocks.

97. The article of claim 96 wherein the program further comprises instructions for determining the threshold based on a predetermined number of free cache memory blocks, the predetermined number being greater than 1.

98. The article of claim 96 wherein the program further comprises instructions for dynamically determining the threshold based on usage of the cache memory area over time.

99. The article of claim 95 wherein the program further comprises instructions for operating the collector to maintain a non-empty list of free cache memory blocks.

100. The article of claim 95 wherein the instructions for reclaiming includes identifying a not recently used cache memory block.

101. The article of claim 95 wherein the at least one data accessor and the collector are programmed to execute among a plurality of processing units in the computer.

102. The article of claim 95 wherein the program further comprises instructions for suspending the execution of the collector in response to a maximum threshold of free cache memory blocks.

103. The article of claim 95 wherein the program further comprises instructions for instructing, from the collector, the owner data accessor to write data out of the owned cache memory block.

104. The article of claim 95 wherein the at least one data accessor and the collector are programmed as processing threads in a multi-threaded computer system.

105. The article of claim 95 wherein the program further comprises instructions for triggering a flusher to execute In the computer to reclaim modified cache memory blocks from the first subset of cache memory blocks to the list of free cache memory blocks.