Flash memory management system and method utilizing multiple block list windows

• US 6,895,464 B2
• Filed: 06/03/2002
• Issued: 05/17/2005
• Est. Priority Date: 06/03/2002
• Status: Active Grant

• Current Assignee: III Holdings 12, LLC (Intellectual Ventures LLC)
• Original Assignee: Honeywell International Inc.
• Inventors: Chow, James, Gender, Thomas K.
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): THOMAS, SHANE M
• Application Number:
  US10/161,373
• Publication Number:
  US 20030225961A1
• Time in Patent Office: 1,079 Days
• Field of Search: 711/103, 711/202, 711170-173, 365/185.33, 365/185.11
• US Class Current: 711/103
• CPC Class Codes: G06F 11/076 by exceeding a count or rate limit, e.g. word- or bit count limit
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

The present invention provides a flash memory management system and method with increased performance. The flash memory management system provides the ability to efficiently manage and allocate flash memory use in a way that improves reliability and longevity, while maintaining good performance levels. The flash memory management system includes a free block mechanism, a disk maintenance mechanism, and a bad block detection mechanism. The free block mechanism provides efficient sorting of free blocks to facilitate selecting low use blocks for writing. The disk maintenance mechanism provides for the ability to efficiently clean flash memory blocks during processor idle times. The bad block detection mechanism provides the ability to better detect when a block of flash memory is likely to go bad. The flash status mechanism stores information in fast access memory that describes the content and status of the data in the flash disk. The new bank detection mechanism provides the ability to automatically detect when new banks of flash memory are added to the system. Together, these mechanisms provide a flash memory management system that can improve the operational efficiency of systems that utilize flash memory.

Claims

1. An apparatus comprising:

a) a processor;

b) a memory coupled to the processor;

c) a flash memory management system residing in the memory and being executed by the processor, the flash memory management system including;

a free block mechanism for locating free blocks of flash memory for writing, the free block mechanism including a free block list of flash memory blocks, and further including a free block list window defining a subset plurality of the flash memory blocks in the free block list, the free block mechanism searching the subset plurality of flash memory blocks in the free block list for a flash memory block having a lowest erase count of flash memory blocks in the subset plurality of flash memory blocks in the free block list;

a disk maintenance mechanism for locating blocks of flash memory for cleaning, the disk maintenance mechanism including a block list of flash memory blocks, and further including a block list window defining a subset plurality of flash memory blocks in the block list, the disk maintenance mechanism evaluating the subset plurality of flash memory blocks in the block list to determine if any flash memory blocks in the subset plurality of flash memory blocks in the block list are candidates for cleaning.

2. The apparatus of claim 1 wherein the free block mechanism further moves the free block list window to a different location on the free block list to select a different subset plurality of flash memory blocks in the free block list for searching of the different subset plurality of flash memory blocks in the free block list.

3. The apparatus of claim 1 wherein the disk maintenance mechanism further moves the block list window to a different location on the block list to select a different subset plurality of flash memory blocks in the block list for evaluating the different subset plurality of flash memory blocks in the block list.

4. The apparatus of claim 1 wherein the free block mechanism adjusts the size of the free block list window to change a number of flash memory blocks searched according to performance requirements.

5. The apparatus of claim 1 wherein the disk maintenance mechanism evaluates the portion of the flash memory blocks in the block list window using a cost age times formula.

6. The apparatus of claim 1 wherein the flash memory management system further comprises a new bank detection mechanism for determining when a new bank of flash memory has been added, the new bank detection mechanism adding blocks from the new banks to the block list and the free block list.

7. The apparatus of claim 1 wherein the flash memory management system further comprises a flash status mechanism, the flash status mechanism storing status information in the memory on startup of the flash memory management system.

8. The apparatus of claim 1 wherein the flash memory management system further comprises a bad block detection mechanism for locating blocks of flash memory likely to become bad, the bad block detection mechanism monitoring the flash memory blocks for error activity and designating a block as bad when the error activity rises above a predefined threshold.

9. A method for managing a flash memory system comprising a plurality of flash memory blocks, the method comprising the steps of:

a) locating free blocks of the flash memory for writing by defining a free block list of flash memory blocks and defining a free block list window defining a subset plurality of the flash memory blocks in the free black list, and by searching the subset plurality of the flash memory blocks in the free block list for a flash memory block having a lowest erase count of flash memory blocks in the subset plurality of flash memory blocks in the free block list;

b) locating blocks of the flash memory for cleaning by defining a block list of flash memory blocks and defining a block list window defining a subset plurality of the flash memory blocks in the block list, and by evaluating the subset plurality of the flash memory blocks in the block list to determine if any flash memory blocks in the subset plurality of flash memory blocks in the block list are candidates for cleaning.

10. The method of claim 9 further comprising the step of moving the free block list window to a different location on the free block list to select a different subset plurality of flash memory blocks in the free block list and searching a portion of the flash memory blocks defined by the free block list window in the different location.

11. The method of claim 9 further comprising the step of moving the block list window to a different location on the free block list to select a different subset plurality of flash memory blocks in the block list and evaluating a portion of the flash memory blocks defined by the block list window in the different location.

12. The method of claim 9 further comprising the step of adjusting the size of the free block list window to change a number of flash memory blocks searched according to performance requirements.

13. The method of claim 9 wherein the step of locating blocks of flash memory likely to become bad comprises evaluating the portion of the flash memory blocks in the block list window using a cost age times formula.

14. The method of claim 9 further comprising the step of determining when a new bank of flash memory has been added.

15. The method of claim 9 further comprising the step of storing status information on startup of the flash memory system.

16. The method of claim 9 further comprising the step of locating blocks of flash memory likely to become bad by monitoring the flash memory blocks for error activity and designating a block as bad when the error activity rises above a predefined threshold.

17. A program product comprising:

a) a flash memory management program, the flash memory management program including;

a free block mechanism for locating free blocks of flash memory for writing, the free block mechanism including a free block list of flash memory blocks, and further including a free block list window defining a subset plurality of the flash memory blocks in the free block list, the free block mechanism searching the subset plurality of flash memory blocks in a free block list for a flash memory block having a lowest erase count of flash memory blocks in the subset plurality of flash memory blocks in the free block list;

a disk maintenance mechanism for locating blocks of flash memory for cleaning, the disk maintenance mechanism including a block list of flash memory blocks, and further including a block list window defining a subset plurality of the flash memory blocks in the block list, the disk maintenance mechanism evaluating the subset plurality of flash memory blocks in a block list to determine if any flash memory blocks in the subset plurality of flash memory blocks in the block list are candidates for cleaning;

b) a computer-readable signal bearing media bearing said program.

18. The program product of claim 17 wherein said signal bearing media comprises recordable media.

19. The program product of claim 17 wherein said signal bearing media comprises transmission media.

20. The program product of claim 17 wherein the free block mechanism further moves the free block list window to a different location on the free block list to select a different subset plurality of flash memory blocks in the free block list for searching of the different subset plurality of flash memory blocks in the free block list.

21. The program product of claim 17 wherein the disk maintenance mechanism further moves the block list window to a different location on the block list to select a different subset plurality of flash memory blocks in the block list for evaluating the different subset plurality of flash memory blocks in the block list.

22. The program product of claim 17 wherein the free block mechanism adjusts the size of the free block list window to change a number of flash memory blocks searched according to performance requirements.

23. The program product of claim 17 wherein the disk maintenance mechanism evaluates the portion of the flash memory blocks in the block list window using a cost age times formula.

24. The program product of claim 17 wherein the flash memory management program further comprises a new bank detection mechanism for determining when a new bank of flash memory has been added, the new bank detection mechanism adding blocks from the new banks to the block list and the free block list.

25. The program product of claim 17 wherein the flash memory management program further comprises a flash status mechanism, the flash status mechanism storing status information in a random access memory on startup of the flash memory program.

26. The program product of claim 17 wherein the flash memory management program further comprises a bad block detection mechanism for locating blocks of flash memory likely to become bad, the bad block detection mechanism monitoring the flash memory blocks for error activity and designating a block as bad when the error activity rises above a predefined threshold.