Wear-leveling in non-volatile storage systems
First Claim
1. A method for allocating non-volatile memory, the non-volatile memory being substantially divided into elements, the method comprising:
- grouping the elements into at least a first group, a second group, and a third group, wherein the first group includes erased elements with relatively low wear and the second group includes erased elements with relatively high wear;
determining when a first element included in the third group is to be replaced by a second element included in the first group;
copying contents associated with the first element into the second element obtained from the first group when it is determined that the first element is to be substantially replaced by the second element;
erasing contents of the first element from the first element; and
associating the second element with the third group, wherein associating the second element with the third group includes disassociating the second element from the first group.
11 Assignments
0 Petitions
Accused Products
Abstract
Methods and apparatus for performing wear leveling in a non-volatile memory system are disclosed. According to one aspect of the present invention, a method for allocating non-volatile memory that is divided into elements includes grouping the elements into a first group, a second group, and a third group. The first group includes erased elements with relatively low wear and the second group includes erased elements with relatively high wear. The method also includes determining when a first element included in the third group is to be replaced by a second element included in the first group. Contents of the first element are copied into the second element obtained from the first group. The contents are then erased from the first element, and the second element is associated with the third group. Associating the second element with the third group includes substantially disassociating the second element from the first group.
-
Citations
64 Claims
-
1. A method for allocating non-volatile memory, the non-volatile memory being substantially divided into elements, the method comprising:
-
grouping the elements into at least a first group, a second group, and a third group, wherein the first group includes erased elements with relatively low wear and the second group includes erased elements with relatively high wear; determining when a first element included in the third group is to be replaced by a second element included in the first group; copying contents associated with the first element into the second element obtained from the first group when it is determined that the first element is to be substantially replaced by the second element; erasing contents of the first element from the first element; and associating the second element with the third group, wherein associating the second element with the third group includes disassociating the second element from the first group. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A method for allocating non-volatile memory, the non-volatile memory being substantially divided into elements, the method comprising:
-
grouping the elements into at least a first group, a second group, and a third group, wherein the first group includes erased elements with erase counts that are approximately less than an average erase count and the second group includes erased elements with erase counts that are approximately greater than the average erase count; determining when a first element included in the third group is to be replaced by a second element included in the second group; copying contents associated with the first element into the second element obtained from the second group when it is determined that the first element is to be substantially replaced by the second element; erasing contents of the first element from the first element; and associating the second element with the third group, wherein associating the second element with the third group includes disassociating the second element from the second group. - View Dependent Claims (11, 12, 13, 14, 15)
-
-
16. A memory management system, the memory management system being arranged to non-volatile memory, the non-volatile memory being substantially divided into elements, the memory management system comprising:
-
a first manager, the first manager being arranged to group the elements into at least a first group, a second group, and a third group, wherein the first group includes elements with relatively low wear and the second group includes elements with relatively high wear; and a second manager, the second manager being arranged to determine when a first element included in the third group is to be replaced by a second element included in the first group, the second manager further being arranged to copy contents associated with the first element into the second element obtained from the first group and to erase contents of the first element from the first element, wherein the second manager is still further arranged to associate the second element with the third group and to disassociating the second element from the first group. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23)
-
-
24. A memory management system for allocating non-volatile memory, the non-volatile memory being substantially divided into elements, the memory management system comprising:
-
a first manager, the first manager being arranged to group the erased elements into at least a first group, a second group, and a third group, wherein the first group includes elements with erase counts that are approximately less than an average erase count and the second group includes erased elements with erase counts that are approximately greater than the average erase count; and a second manager, the second manager being arranged to determine when a first element included in the third group is to be replaced by a second element included in the second group, the second manager further being arranged to copy contents associated with the first element into the second element obtained from the second group and to erase contents of the first element from the first element, the second manager still further being arranged to associate the second element with the third group and to disassociate the second element from the second group. - View Dependent Claims (25, 26, 27, 28)
-
-
29. A method for performing wear leveling in a system which includes a non-volatile memory, the method comprising:
-
copying one of contents associated with a first storage element and new contents arranged to replace the contents associated with the first storage element into a second storage element, the second storage element having an erase count that is less than an erase count associated with the first storage element, the second storage element being associated with a first data structure, the first data structure being arranged to contain a first set of storage elements; associating the second storage element with a second data structure, the second data structure being arranged to contain a second set of storage elements, wherein associating the second storage element with the second data structure includes disassociating the second storage element from the first data structure; erasing the contents associated with the first storage element from the first storage element; determining when to associate the first storage element with the first data structure; associating the first storage element with the first data structure when it is determined that the first storage element is to be associated with the first data structure, wherein associating the first storage element with the first data structure includes disassociating the first storage element from the second data structure; and associating the first storage element with a third data structure when it is determined that the first storage element is not to be associated with the first data structure, the third data structure being arranged to contain a third set of storage elements. - View Dependent Claims (30, 31, 32, 33, 34, 35, 36, 37)
-
-
38. A method for performing wear leveling in a system which includes a non-volatile memory, the method comprising:
-
copying at least one of contents associated with a first storage element and new contents arranged to replaced the contents associated with the first storage element into a second storage element, the second storage element having an erase count that is greater than an erase count associated with the first storage element, the second storage element being associated with a first data structure, the first data structure being arranged to contain a first set of storage elements; associating the second storage element with a second data structure, the second data structure being arranged to contain a second set of storage elements, wherein associating the second storage element with the first data structure includes disassociating the second storage element from the first data structure; erasing the contents associated with the first storage element from the first storage element; associating the first storage element with a third data structure, the third data structure being arranged to contain a third set of storage elements; obtaining a third storage element from the third data structure; and associating the third storage element with the first data structure, wherein associating the third storage element with the first data structure includes disassociating the third storage element from the third data structure. - View Dependent Claims (39, 40, 41)
-
-
42. A memory management system, the memory management system being arranged to manage an allocation of non-volatile storage elements, the memory management system comprising:
-
means for maintaining a first data structure, the first data structure being associated with storage elements which have each been erased substantially less than a particular amount; means for maintaining a second data structure, the second data structure being associated with storage elements which have each been erased substantially more than a particular amount; means for maintaining a third data structure, the third data structure being associated with storage elements which are not associated with the first data structure or the second data structure, wherein at least a plurality of the storage elements associated with the third data structure contain data; means for determining when a first storage element of the third data structure is to be replaced; and means for associating a second storage element selected from one of the first data structure and the second data structure with the third data structure when it is determined that the first storage element of the third data structure is to be replaced. - View Dependent Claims (43, 44, 45, 46, 47, 48, 49, 50)
-
-
51. A memory management system, the memory management system being arranged to manage an allocation of non-volatile storage elements, the memory management system comprising:
-
code devices for copying one of contents associated with a first storage element and new contents arranged to replace the contents associated with the first storage element into a second storage element, the second storage element having an erase count that is less than an erase count associated with the first storage element, the second storage element being associated with a first data structure, the first data structure being arranged to contain a first set of storage elements; code device for associating the second storage element with a second data structure, the second data structure being arranged to contain a second set of storage elements, wherein the code devices for associating the second storage element with the first data structure include code devices for disassociating the second storage element from the first data structure; code devices for erasing the contents associated with the first storage element from the first storage element; code devices for determining when to associate the first storage element with the first data structure; code devices for associating the first storage element with the first data structure when it is determined that the first storage element is to be associated with the first data structure, wherein the code devices for associating the first storage element with the first data structure include code devices for disassociating the first storage element from the second data structure; code devices for associating the first storage element with a third data structure when it is determined that the first storage element is not to be associated with the first data structure, the third data structure being arranged to contain a third set of storage elements; a memory for storing the code devices; and a processor arranged to access the code devices. - View Dependent Claims (52, 53, 54, 55, 56, 57, 58, 59)
-
-
60. A memory management system, the memory management system being arranged to manage an allocation of non-volatile storage elements, the memory management system comprising:
-
code devices for copying contents associated with a first storage element into a second storage element, the second storage element having an erase count that is greater than an erase count associated with the first storage element, the second storage element being associated with a first data structure, the first data structure being arranged to contain a first set of storage elements; code devices for associating the second storage element with a second data structure, the second data structure being arranged to contain a second set of storage elements, wherein the code devices for associating the second storage element with the first data structure include code devices for disassociating the second storage element from the first data structure; code devices for erasing the contents associated with the first storage element from the first storage element; code devices for associating the first storage element with a third data structure, the third data structure being arranged to contain a third set of storage elements; code devices for obtaining a third storage element from the third data structure; code devices for associating the third storage element with the first data structure, wherein the code devices for associating the third storage element with the first data structure include code devices for disassociating the third storage element from the third data structure; a storage area for storing the code devices; and a processor for accessing the code devices. - View Dependent Claims (61, 62, 63, 64)
-
Specification