Method of controlling clean-up of a solid state memory disk storing floating sector data

• US 5,479,633 A
• Filed: 10/30/1992
• Issued: 12/26/1995
• Est. Priority Date: 10/30/1992
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Wells, Steven, Hasbun, Robert N.
• Primary Examiner(s): Robertson, David L.
• Application Number:
  US07/969,763
• Time in Patent Office: 1,152 Days
• Field of Search: 395/400, 395/425
• US Class Current: 711/103
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0634 by changing the state or mode of one or more devices
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0664 at device level, e.g. emulation of a storage device or system
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

A method of initiating and controlling background clean-up of a solid state memory disk is described. Background clean-up begins by enabling a clean-up state machine after completion of a write command. Next, a next state pointer is set to an initial state for evaluating whether clean-up is necessary. Actual execution of background clean-up begins when the processing unit allocates execution time for clean-up. As each state is executed, the next state pointer is reset so that it points to the next clean-up state to be executed. States pointed to by the next state pointer are executed until a block of the solid state memory disk is cleaned-up.

Also described is a method of automatically performing foreground clean-up of a solid state memory disk. A method of forcing clean-up is also described.

Claims

1. A method of initiating and controlling background clean-up of a solid state memory disk, the solid state memory disk including a processing unit, the processing unit allocating execution time for clean-up, the method comprising the steps of:

a) enabling a clean-up state machine after completion of a write command, the clean-up state machine having a multiplicity of states, each state controlling the execution of a portion of clean-up, each state resetting a next state pointer to point to a next state;

b) setting the next state pointer to an evaluation state for evaluating whether clean-up is necessary;

c) executing a state pointed to by the next state pointer when the processing unit allocates execution time for clean-up, execution of each state taking no more than a selected maximum amount of execution time; and

d) repeating step c) until a block of the solid state memory disk is cleaned-up.

2. The method of claim 1 wherein the states of the clean-up state machine comprise:

a) a selection state for selecting a first block to clean-up if clean-up is necessary;

b) an allocation state for allocating a sufficient amount of memory in a second block to store a valid sector from the first block;

c) a copy state for copying the valid sector of user data from the first block into the second block; and

d) an erase state for erasing the first block.

3. The method of claim 2 wherein the states of the clean-up state machine further comprise:

a) a postcopy update state for updating a database after the copy state, the database tracking an amount of free memory, and an amount of dirty memory in the solid state memory disk.

4. The method of claim 3 wherein the states of the clean-up state machine further comprise:

a) a posterase update state for updating the database after the erase state.

5. The method of claim 2 wherein the states of the clean-up state machine further comprise:

a) a wait for erase complete state for determining when erasure is complete.

6. The method of claim 2 wherein the states of the clean-up state machine further comprise:

a) an idle state for halting the clean-up state machine if it is determined clean-up of the solid state memory disk is not necessary.

7. The method of claim 1 wherein the solid state memory disk comprises nonvolatile semiconductor memory devices.

8. A method of initiating and controlling foreground clean-up of a solid state memory disk, the method comprising the steps of:

a) enabling a first clean-up state machine if sufficient memory within the solid state memory disk cannot be allocated in response to a write command, the first clean-up state machine having a multiplicity of first clean-up state machine states, each of the first clean-up state machine states controlling the execution of a portion of clean-up of a first block, each of the first clean-up state machine states resetting a first next state pointer to point to a next first clean-up state machine state;

b) enabling a second clean-up state machine if sufficient memory within the solid state memory disk cannot be allocated in response to a write command, the second clean-up state machine having a multiplicity of second clean-up state machine states, each of the second clean-up state machine states controlling the execution of a portion of clean-up of a second block, each of the second clean-up state machine states resetting a second next state pointer to point to a next second clean-up state machine state;

c) setting the first next state pointer to an initial first clean-up state machine state for choosing the first block within the solid state memory disk to clean-up;

d) setting the second next state pointer to an initial second clean-up state machine state for choosing the second block within the solid state memory disk to clean-up;

e) executing each state pointed to by the first next state pointer until erasure of the first block begins;

f) executing each state pointed to by the second next state pointer until erasure of the second block begins; and

g) executing each state pointed to by the first next state pointer until clean-up of the first block is complete.

9. The method of claim 8 wherein the first clean-up state machine states comprise:

a) an allocation state for allocating a sufficient amount of memory in a third block to store a valid sector within the first block;

b) a copy state for copying the valid sector from the first block into the third block; and

c) an erase state erasing the first block.

10. The method of claim 9 wherein the first clean-up state machine states further comprise:

a) a postcopy update state for updating a database after the copy state, the database tracking an amount of free memory, and an amount of dirty memory in the solid state disk.

11. The method of claim 10 wherein the first clean-up state machine states further comprise:

a) a posterase update state for updating the database after the erase state.

12. The method of claim 11, wherein the first clean-up state machine states further comprise:

a) a wait for erase complete state for determining when erasure is complete.

13. The method of claim 12, wherein the first clean-up state machine states further comprise:

a) an idle state for halting the clean-up of the solid state memory disk if clean-up is not necessary.

14. The method of claim 8 wherein the solid state memory disk comprises nonvolatile semiconductor memory devices.

15. The method of claim 8 wherein the second clean-up state machine states comprise:

a) an allocation state for allocating a sufficient amount of memory in a fourth block to store a valid sector from the second block;

b) copying the valid sector from the second block into the fourth block; and

c) erasing the second block.

16. The method of claim 15 wherein the second clean-up state machine states comprise:

a) an allocation state for allocating a sufficient amount of memory in a second block to store a valid sector from the first block;

b) a copy state for copying the valid sector from the first block into the second block; and

c) an erase state for erasing the first block.

17. The method of claim 16 wherein the second clean-up state machine states further comprise:

a) a postcopy update state for updating a database after the copy state the database tracking an amount of free memory, and an amount of dirty memory in the solid state disk.

18. The method of claim 17 wherein the second clean-up state machine states further comprise:

a) a posterase update state for updating the database after the erase state.

19. The method of claim 18 wherein the second clean-up state machine states further comprise:

a) a wait for erase complete state for determining when erasure is complete.

20. The method of claim 19 wherein the second clean-up state machine states further comprise:

a) an idle state for halting the clean-up state machine if it is determined clean-up of the solid state memory disk is not necessary.

21. A method of forcing and controlling clean-up of a solid state memory disk, the solid state memory disk including a processing unit, the processing unit allocating execution time for clean-up, the method comprising the steps of:

a) enabling a clean-up state machine in response to a force clean-up command, the clean-up state machine having a multiplicity of states, each state controlling the execution of a portion of clean-up, each state resetting a next state pointer to point to a next state;

b) setting the next state pointer to an initial state for choosing a first block to clean-up;

c) executing a state pointed to by the next state pointer when the processing unit allocates execution time for clean-up, execution of each state taking no more than a selected maximum amount of execution time; and

d) repeating step c) until all states have been executed.

22. A method of forcing and controlling clean-up of a solid state memory disk, the solid state memory disk including a processing unit, the processing unit allocating execution time for clean-up, the method comprising the steps of:

a) enabling a first clean-up state machine in response to a force clean-up command, the first clean-up state machine having a multiplicity of first clean-up state machine states, each of the first clean-up state machine states controlling the execution of a portion of clean-up of a first block, each of the first clean-up state machine states resetting a first next state pointer to point to a next first clean-up state machine state;

b) enabling a second clean-up state machine in response to the force clean-up command, the second clean-up state machine having a multiplicity of second clean-up state machine states, each of the second clean-up state machine states controlling the execution of a portion of clean-up of a second block, each of the second clean-up state machine states resetting a second next state pointer to point to a next second clean-up state machine state;

c) setting the first next state pointer to an initial first clean-up state machine state for choosing the first block within the solid state memory disk to clean-up;

d) setting the second next state pointer to an initial second clean-up state machine state for choosing the second block within the solid state memory disk to clean-up;

e) executing each of the first clean-up state machine states as it is pointed to by the first clean-up state machine next state pointer until a first erase state is reached;

f) executing each of the second clean-up state machine states as it is pointed to by the second clean-up state machine next state pointer until a second erase state is reached; and

g) executing each of the first clean-up state machine states as it is pointed to by the first clean-Up state machine next state pointer until the first block is cleaned up.

23. The method of claim 22 wherein the first clean-up state machine states comprise:

a) an allocation state for allocating a sufficient amount of memory in a third block to store a valid sector from the first block;

b) a copy state for copying the valid sector from the first block into the third block; and

c) an erase state for erasing the first block.

24. The method of claim 22 wherein the second clean-up state machine states comprise:

a) an allocation state for allocating a sufficient amount of memory in a fourth block to store a valid sector from the second block;

b) a copy state for copying the valid sector from the second block into the fourth block; and

c) erasing the second block.

25. The method of claim 22 wherein the solid state memory disk comprises a multiplicity of nonvolatile semiconductor memory devices.