Scheduling of Housekeeping Operations in Flash Memory Systems

• US 20080091872A1
• Filed: 12/03/2007
• Published: 04/17/2008
• Est. Priority Date: 01/20/2005
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Alan Bennett, Andrew Tomlin, Charles Schroter, Sergey Gorobets
• Inventors: Gorobets, Sergey, Tomlin, Andrew, Bennett, Alan, Schroter, Charles
• Granted Patent: US 7,565,478 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G11C 16/349 Arrangements for evaluating degradation, retention or wearout, e.g. by counting erase cycles

Abstract

A re-programmable non-volatile memory system, such as a flash EEPROM system, having its memory cells grouped into blocks of cells that are simultaneously erasable is operated to perform memory system housekeeping operations in the foreground during execution of a host command, wherein the housekeeping operations are unrelated to execution of the host command. Both one or more such housekeeping operations and execution of the host command are performed within a time budget established for executing that particular command. One such command is to write data being received to the memory. One such housekeeping operation is to level out the wear of the individual blocks that accumulates through repetitive erasing and re-programming.

Claims

1. A method of operating an erasable and re-programmable non-volatile memory system, which comprises, in response to receiving a command from outside the memory system having a time budget for its execution:

perform any function necessary to execute the command,

assert a busy signal outside of the memory system for a time extending beyond that utilized to perform said any necessary function while remaining within the time budget, and

perform during the extended busy signal time at least a portion of one housekeeping operation within the memory system that is unnecessary to execute the received command.

2. The method of claim 1, wherein the received command includes a write command followed by one or more units of data to be written into the memory system.

3. The method of claim 2, wherein a plurality of units of data to be written into the memory system are received, and wherein the busy signal is asserted in at least two intervals between receipt the units of data, during which time said at least a portion of one housekeeping operation is performed by completing said at least one housekeeping operation.

4. The method of claim 3, wherein said at least one housekeeping operation is performed during more than one of said at least two intervals.

5. The method of claim 4, wherein said any function necessary to execute the command includes a garbage collection operation and writing the received data to the memory system.

6. The method of claim 1, wherein said one housekeeping operation includes transferring a quantity of data from one location to another location within the memory system, and wherein performing at least a portion of such a housekeeping operation includes transferring only a portion of the quantity of data.

7. The method of claim 6, wherein remaining portions of the quantity of data are subsequently transferred during execution of a garbage collection operation not directed specifically to perform said one housekeeping operation.

8. The method of claim 1, wherein said at least one housekeeping operation includes a wear leveling operation performed in a portion of the memory not involved in the execution of the command.

9. The method of claim 1, wherein said at least one housekeeping operation includes refreshing data stored in a portion of the memory not involved in the execution of the command.

10. The method of claim 1, wherein said at least one housekeeping operation includes a garbage collection operation performed in a portion of the memory not involved in the execution of the command.

11. A method of operating an erasable and re-programmable non-volatile memory system, comprising, in response to receiving a command to transfer one or more units of data within a given time budget:

determining whether any housekeeping operation is necessary to be able to transfer the one or more units of data,

if any housekeeping operation is necessary to be able to transfer the one or more units of data, performing at least the necessary housekeeping operation,

determining whether a housekeeping operation unnecessary to the transfer of one or more units of data is pending,

if a housekeeping operation unnecessary to the data transfer is pending, determining whether any remaining time within the time budget is sufficient for performing the pending housekeeping operation unnecessary to the data transfer,

if sufficient time remains within the time budget, performing at least a portion of the pending housekeeping operation unnecessary to the data transfer during execution of the received command, and

transferring the one or more units of data within the given time budget.

12. The method of claim 11, wherein determining whether any housekeeping operation is necessary to be able to write the one or more units of data includes determining whether data within two or more locations of the memory need to be consolidated into a single location, and, if so, consolidating such data within the given time budget.

13. The method of claim 11, wherein determining whether a housekeeping operation unnecessary to the data transfer is pending includes identifying a pending wear leveling exchange, and wherein performing the pending housekeeping operation unnecessary to the data transfer includes performing at least a portion of the pending wear leveling exchange within the given time budget.

14. The method of claim 13, wherein performing the pending housekeeping operation unnecessary to the data transfer includes performing all of the pending wear leveling exchange within the given time budget.

15. The method of claim 11, wherein determining whether a housekeeping operation unnecessary to the data transfer is pending includes identifying an operation to refresh specified data stored in a portion of the memory system different than a portion involved in executing the received data transfer command, and wherein performing the pending housekeeping operation unnecessary to the data transfer includes refreshing at least a portion of the specified data within the given time budget.

16. The method of claim 15, wherein performing the pending housekeeping operation unnecessary to the data transfer includes refreshing all of the specified data within the given time budget.

17. The method of claim 11, wherein determining whether a housekeeping operation unnecessary to the data transfer is pending includes identifying an operation perform garbage collection in a portion of the memory system different than a portion involved in executing the received write command, and thereafter performing at least a portion of such garbage collection within the given time budget.

18. The method of claim 17, wherein performing the pending housekeeping operation unnecessary to the data transfer includes performing all of such data transfer within the given time budget.

19. The method of claim 11, additionally comprising receiving two or more units of data in succession, and wherein determining any remaining amounts of time within the time budget for performing the housekeeping operation unnecessary to the data transfer results in determining that sufficient time remains, and additionally comprises asserting at least one busy period that is unnecessary to complete execution of the data transfer command.

20. The method of claim 11, wherein if a housekeeping operation unnecessary to the data transfer is pending and there is not time within the time budget sufficient for performing at least a portion of the pending housekeeping operation unnecessary to the data transfer, adding the unperformed housekeeping operation to a count of such unperformed operations.

21. The method of claim 20, in response to multiple unperformed housekeeping operations being included in the count, causing each in order to be rendered as pending for execution during execution of all subsequent data write commands until the count is zero.

22. The method of claim 20, wherein, in response to multiple unperformed housekeeping operations being included in the count, each unperformed housekeeping operation is caused to be rendered pending one at a time in order for execution during execution of all subsequent data transfer commands until the count is zero.

23. The method of claim 20, wherein housekeeping operations unrelated to execution of the data transfer command are normally rendered at a pre-defined interval, and wherein, in response to multiple unperformed housekeeping operations being included in the count, the unperformed housekeeping operations are caused to be rendered pending one at a time in order to be performed during execution of subsequent data transfer commands at intervals less than said pre-defined interval until the count is zero.

24. The method of claim 20, wherein housekeeping operations unrelated to execution of the data transfer command are normally rendered at a pre-defined interval, and wherein, in response to multiple unperformed housekeeping operations being included in the count, at least one of the unperformed housekeeping operations is caused to be rendered pending to be performed during execution of a subsequent data transfer command at an interval less than said pre-defined interval while at least one other of the unperformed housekeeping operations is not performed.

25. A method of operating a system of erasable and re-programmable non-volatile memory cells organized into a plurality of physical blocks of a number of memory cells that are simultaneously erasable and wherein data within logical group addresses are mapped into the physical blocks, comprising in response to receiving a command to write data to one of the logical groups and the data to be written:

determining whether data within the logical group is mapped to more than one of the physical blocks,

determining whether there is a wear leveling exchange pending between two of the plurality of blocks, and

(a) if data within the logical group are mapped to more than one of the physical blocks,

consolidating the data of the more than one of the physical blocks into a single block, and

writing the received data to an update block associated with the logical group, or

(b) if data within the logical group are not mapped to more than one of the physical blocks but there is a wear leveling exchange pending,

performing a wear leveling exchange between said two of the physical blocks, and

writing the received data to an update block associated with the logical group.

26. A method of operating a system of erasable and re-programmable non-volatile memory cells organized into a plurality of physical blocks of a number of memory cells that are simultaneously erasable and wherein incoming data within logical group addresses mapped to one of the physical blocks are programmed into an update physical block logically linked to said one block, comprising in response to receiving a write command and data to be written:

determining whether an update block is available to receive the data to be written,

(a) if an update block is not available,

consolidating data of one of a plurality of update blocks with data of a physical block to which data of the update block are logically linked, thereby making an update block available, and

thereafter writing data to the available update block, or

(b) if an update block is available,

performing a wear leveling exchange of data between two of the physical blocks, and

thereafter writing data to the available update block.

27. A method of operating a system of erasable and re-programmable non-volatile memory cells organized into a plurality of physical blocks of a number of memory cells that are simultaneously erasable and wherein incoming data within logical addresses mapped to one of the physical blocks are programmed into an update physical block logically linked to said one block, wherein a limited number of the plurality of blocks are specified to be update blocks and new update blocks are created by garbage collection that consolidates data from at least two blocks into one block, which comprises in response to receiving a write command and data to be written:

determining whether a housekeeping operation unnecessary to execution of the write command is pending and which includes the necessity to copy of a plurality of units of data from one of the plurality of blocks to an update block,

if so, copying one or more of the plurality of units of data but less than one-quarter of the units from said one block into one of the update blocks during execution of the write command,

identifying said one update block as the next in order to have its data consolidated, and

after execution of the write command, perform garbage collection on said one update block, whereby the remaining of the plurality of units of data within said one block are placed together with the one or more copied units into a common block.