Demand-driven opportunistic garbage collection in memory components

• US 8,032,724 B1
• Filed: 04/03/2008
• Issued: 10/04/2011
• Est. Priority Date: 04/04/2007
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell International Limited (Marvell Technology Group Limited)
• Inventors: Smith, Ronald
• Primary Examiner(s): TSAI, SHENG JEN
• Application Number:
  US12/062,249
• Time in Patent Office: 1,279 Days
• Field of Search: 711/159, 711/E12.001
• US Class Current: 711/159
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence

Abstract

A method and system for performing garbage collection in a memory is disclosed. Aspects of the exemplary embodiment include dividing garbage collection into atomic operations, including read, write, and block erase; storing read cycle times, write cycle times, and block erase cycle times of the memory; receiving a communication from a processor indicating at least one idle period when an application executing on the processor will not make a request of the memory, wherein the communication indicates a time duration of the at least one idle period; and in response, performing at least one of the garbage collection atomic operations within the time duration, whereby garbage collection can be performed during the at least one idle period, rather than when the memory is substantially full.

Claims

1. A method comprising:

receiving an opportunistic garbage collection (OGC) command from a processor providing notification of an impending occurrence of a memory idle period;

the OGC command specifying a time duration of the idle period during which an application executing on the processor will not make a request of a memory;

selecting one or more garbage collection atomic operations based, at least in part, on expected durations of the garbage collection atomic operations relative to the specified time duration of the idle period; and

in response to the OGC command, performing the selected garbage collection atomic operations on the memory during the idle period.

2. The method of claim 1 wherein the OGC command comprises a real-time schedule that specifies when the application will have memory idle periods, and wherein the method comprises selecting and performing garbage collection operations based, at least in part, on the specified duration of the idle periods in the real-time schedule.

3. The method of claim 2 wherein the real-time schedule includes memory access time periods during which the application makes read/write requests of the memory for processing a real-time media stream.

4. The method of claim 3 wherein the real-time schedule further includes a time gap left over in each memory access time period during which at least one of two additional items are scheduled:

asynchronous read/write requests of the memory from asynchronous thread activity; and

the OGC command.

5. The method of claim 1 further comprising accessing stored read cycle times, write cycle times, and block erase cycle times of the memory to determine expected durations of garbage collection atomic operations.

6. The method of claim 1 further comprising providing an OGC threshold that is less than a first garbage collection threshold, wherein the OGC command is transmitted when the first OGC threshold is exceeded.

7. The method of claim 6 wherein the OGC threshold is at approximately 80% of memory volume full.

8. The method of claim 1 wherein selecting one or more garbage collection atomic operations further comprises comparing stored read cycle times, write cycle times, and block erase cycle times with the specified time duration of the at least one idle period to select which ones of the atomic operations can be performed within the time duration.

9. The method of claim 1 wherein the garbage collection atomic operations comprise a move phase comprising read and write cycles and a block erase phase.

10. An executable software product stored on a non-transitory computer-readable storage medium containing program instructions for performing garbage collection in a memory, the program instructions for:

receiving an opportunistic garbage collection (OGC) command from a processor providing notification of an impending occurrence of a memory idle period;

the OGC command specifying a time duration of the idle period during which an application executing on the processor will not make a request of a memory;

selecting one or more garbage collection atomic operations based, at least in part, on expected durations of the garbage collection atomic operations relative to the specified time duration of the idle period; and

in response to the OGC command, performing the selected garbage collection atomic operations on the memory during the idle period.

11. The executable software product of claim 10 wherein the OGC command comprises a real-time schedule that specifies when the application will have memory idle periods, and wherein the method comprises selecting and performing garbage collection operations based, at least in part, on the specified duration of the idle periods in the real-time schedule.

12. The executable software product of claim 11 wherein the real-time schedule includes memory access time periods during which the application makes read/write requests of the memory for processing a real-time media stream.

13. The executable software product of claim 12 wherein the real-time schedule further includes a time gap left over in each memory access time period during which at least one of two additional items are scheduled:

asynchronous read/write requests of the memory from asynchronous thread activity; and

the OGC command.

14. The executable software product of claim 11 wherein the program instructions further comprise accessing stored read cycle times, write cycle times, and block erase cycle times of the memory to determine expected durations of garbage collection atomic operations for receiving the OGC command from the processor.

15. The executable software product of claim 10 further comprising program instructions for providing an OGC threshold that is less than a normal garbage collection threshold, wherein the OGC command is transmitted when the first OGC threshold is exceeded.

16. The executable software product of claim 15 wherein the OGC threshold is at approximately 80% of memory volume full.

17. The executable software product of claim 10 wherein performing at least one of the garbage collection atomic operations further comprises program instructions for comparing stored read cycle times, write cycle times, and block erase cycle times with the specified time duration of the at least one idle period to select which ones of the atomic operations can be performed within the time duration.

18. The executable software product of claim 10 wherein the garbage collection atomic operations comprise a move phase comprising read and write cycles and a block erase phase.

19. A memory system, comprising:

a bus;

a processor;

a memory coupled to the processor via the bus, the memory including a memory array and a memory controller for performing memory management functions for the memory array, including;

receiving an opportunistic garbage collection (OGC) command from the processor providing notification of an impending occurrence of a memory idle period;

the OGC command specifying a time duration of the idle period during which an application executing on the processor will not make a request of a memory;

selecting one or more garbage collection atomic operations based, at least in part, on expected durations of the garbage collection atomic operations relative to the specified time duration of the idle period; and

in response to the OGC command, performing the selected garbage collection atomic operations on the memory during the idle period.

20. The memory system of claim 19 wherein the processor creates an OGC command that includes a real-time schedule that specifies when the executing application will have memory idle periods, and wherein the memory controller controls the memory to select and perform garbage collection operations based, at least in part, on the idle periods in the real-time schedule.

21. The memory system of claim 20 wherein the real-time schedule includes memory access time periods during which the executing application makes read/write requests of the memory for processing a real-time media stream.

22. The memory system of claim 21 wherein the real-time schedule further includes a time gap left over in each memory access time period during which at least one of two additional items are scheduled:

asynchronous read/write requests of the memory from asynchronous thread activity; and

the OGC command.

23. The memory system of claim 19 wherein the memory controller accesses stored read cycle times, write cycle times, and block erase cycle time of the memory to determine expected durations of garbage collection atomic operations.

24. The memory system of claim 19 wherein the processor provides an OGC threshold that is less than a first garbage collection threshold, wherein the OGC threshold is used to trigger issuance of the OGC command.

25. The memory system of claim 24 wherein the OGC threshold is at approximately 80% of memory volume full.

26. The memory system of claim 19 wherein the memory controller compares stored read cycle times, write cycle times, and block erase cycle times with the specified time duration of the at least one idle period to select which ones of the atomic operations can be performed within the time duration.

27. The memory system of claim 19 wherein the garbage collection atomic operations comprise a move phase comprising read and write cycles and a the block erase.

28. The memory system of claim 19 wherein the memory comprises a managed NAND having a NAND array and a NAND controller.