Method of performing clean-up of a solid state disk while executing a read command

• US 5,553,261 A
• Filed: 04/01/1994
• Issued: 09/03/1996
• Est. Priority Date: 04/01/1994
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Hasbun, Robert N., Garner, Richard P.
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US08/221,802
• Time in Patent Office: 886 Days
• Field of Search: 395/425, 395/800, 395/430, 365/218
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/0664 at device level, e.g. emulation of a storage device or system

Abstract

A method of executing states of a clean-up state machine while executing a command from a host CPU to read a sector of data stored within a memory array. First, a number of sectors of data are copied from the memory array into a sector buffer. Then, while the host CPU is reading sectors from the sector buffer, a number of states of a clean-up state machine are executed to aid in the conversion of invalid user data into free memory. Also described is a solid state memory disk that converts invalid sectors of data to free memory while executing a read command from a host CPU.

Claims

1. A solid state memory disk comprising:

a) a flash memory array storing valid sectors of data, free memory, and invalid sectors of data;

b) a buffer for storing sectors of data;

c) a counter having a count, the count being incremented when a sector of data is written into the buffer and the count being decremented when a sector of data is read from the buffer; and

d) a memory array controller for controlling the reading and clean-up of the flash memory array, the memory array controller performing clean-up of the flash memory array while executing a command from the host to read a first number of sectors of data, the memory array controller including;

1) a clean-up state machine for converting invalid sectors of data into free memory, the clean-up state machine including a multiplicity of states, each state of the clean-up state machine modifying a next state pointer so that the next state pointer points to a next state to be executed; and

2) a read controller for executing the read command, the read controller writing the first number of sectors of data into the sector buffer and enabling execution of the next state of the clean-up state machine while the host is reading a sector of data from the buffer.

2. A computer system including:

a) a central processing unit generating a command to read a first number of sectors of data; and

b) a solid state memory disk responsive to the command to read the first number of sectors of data, the solid state memory disk including;

1) a flash memory array storing valid sectors of data, free memory and invalid sectors of data;

2) a buffer for storing sectors of data, the buffer being coupled to the central processing unit;

3) a counter having a count, the count being incremented when a sector of data is written into the buffer and the count being decremented when a sector of data is read from the buffer; and

4) a memory array controller for controlling the reading, and clean-up of the flash memory array, the memory array controller including;

A) a clean-up state machine for converting invalid sectors of data into free memory, the clean-up state machine including a multiplicity of states, each state modifying a next state pointer so that the next state pointer points to a next state to be executed; and

B) a read controller for executing the read command, the read controller writing the first number of sectors of data into the sector buffer and enabling execution of the next state of the clean-up state machine while the central processing unit is reading a sector of data from the sector buffer.

3. A method of performing a clean-up operation for a solid state disk, wherein the clean-up operation comprises a plurality of states, comprising the steps of:

a) receiving a read command from a host processor, the read command requesting a first number of sectors of data from the solid state disk wherein the solid state disk comprises nonvolatile semiconductor memory;

b) writing a second number of sectors of data from the nonvolatile semiconductor memory to a sector buffer; and

c) executing at least one state of the plurality of states of the clean-up operation while the host processor is reading the sector buffer.

4. The method of claim 3 wherein the nonvolatile semiconductor memory includes FLASH memory.

5. The method of claim 3 wherein the clean-up operation comprises the steps:

a) determining a focus block to clean-up, wherein the focus block includes a valid sector of data and an invalid sector of data;

b) relocating the valid sector of data into at least one destination block; and

c) erasing the focus block.

6. The method of claim 5 wherein step b) further comprises the steps of:

b1) allocating free memory in the destination block;

b2) copying the valid sector of data from the focus block to the sector buffer; and

b3) copying at least a portion of the valid sector from the sector buffer to the destination block.

7. A method of performing a clean-up operation for a solid state disk, wherein the clean-up operation comprises a plurality of states, comprising the steps of:

a) receiving a read command from a host processor, the read command requesting a first number of sectors of data from the solid state disk, wherein the solid state disk comprises nonvolatile semiconductor memory;

b) writing a second number of sectors of data from the nonvolatile semiconductor memory to a sector buffer;

c) determining an available number of sectors of data within the sector buffer wherein the available number represents sectors available to be read by the host processor;

d) compare the available number to a threshold number; and

e) executing at least one state of the plurality of states of the clean-up operation while the host processor is reading the sector buffer if the available number exceeds the threshold number.

8. The method of claim 7 wherein the nonvolatile semiconductor memory includes FLASH memory.

9. The method of claim 7 wherein the clean-up operation comprises the steps:

a) determining a focus block to clean-up, wherein the focus block includes a valid sector of data and an invalid sector of data;

b) relocating the valid sector of data into at least one destination block; and

c) erasing the focus block.

10. The method of claim 9 wherein step b) further comprises the steps of:

b1) allocating free memory in the destination block;

b2) copying the valid sector of data from the focus block to the sector buffer; and

b3) copying at least a portion of the valid sector from the sector buffer to the destination block.

11. A method of performing a clean-up operation for a solid state disk, wherein the clean-up operation comprises a plurality of states, comprising the steps of:

a) receiving a read command from a host processor, the read command requesting a first number of sectors of data from the solid state disk wherein the solid state disk comprises nonvolatile semiconductor memory;

b) writing a second number of sectors of data from the nonvolatile semiconductor memory to a sector buffer;

c) determining a number left representing the number of sectors yet to be read by the host processor from the sector buffer;

d) compare the number left to a minimum number; and

e) executing at least one state of the plurality of states of the clean-up operation while the host processor is reading the sector buffer if the number left exceeds the minimum number.

12. The method of claim 11 wherein the nonvolatile semiconductor memory includes FLASH memory.

13. The method of claim 11 wherein the clean-up operation comprises the steps:

a) determining a focus block to clean-up, wherein the focus block includes a valid sector of data and an invalid sector of data;

b) relocating the valid sector of data into at least one destination block; and

c) erasing the focus block.

14. The method of claim 13 wherein step b) further comprises the steps of:

b1) allocating free memory in the destination block;

b2) copying the valid sector of data from the focus block to the sector buffer; and

b3) copying at least a portion of the valid sector from the sector buffer to the destination block.

15. A method of performing a clean-up operation for a solid state disk, wherein the clean-up operation comprises a plurality of states, comprising the steps of:

a) receiving a read command from a host processor, the read command requesting a requested number of sectors of data from the solid state disk, wherein the solid state disk comprises nonvolatile semiconductor memory;

b) write a sector of data from the nonvolatile semiconductor memory to a sector buffer;

c) increment a counter, wherein the counter is decremented in accordance with a number of sectors read by the host processor from the sector buffer;

d) returning to step b) if a value of the counter is less than a threshold number;

e) performing the following steps if the value of the counter is equal to or greater than the threshold number;

d1) executing at least one state of the plurality of states of the clean-up operation while the host processor is reading the sector buffer;

d2) comparing the value of the counter with a minimum number,

d3) returning to step d1) if the value of the counter is greater than or equal to a minimum number; and

d4) returning to step b) if the value of the counter is less than the minimum number and a number of sectors written into the sector buffer is less than the requested number.

16. The method of claim 15 wherein the nonvolatile semiconductor memory includes FLASH memory.

17. The method of claim 15 wherein the clean-up operation comprises the steps:

a) determining a focus block to clean-up, wherein the focus block includes a valid sector of data and an invalid sector of data;

b) relocating the valid sector of data into at least one destination block; and

c) erasing the focus block.

18. The method of claim 17 wherein step b) further comprises the steps of:

b1) allocating free memory in the destination block;

b2) copying the valid sector of data from the focus block to the sector buffer; and

b3) copying at least a portion of the valid sector from the sector buffer to the destination block.