Method and apparatus for performing wear leveling in memory

1. A method for performing wear leveling in a memory, comprising:

dividing life cycle of the memory comprising more than one Physical Blocks into at least one sampling interval;

for each sampling interval, getting a first Physical Block by taking statistics of degree of wear of each Physical Block in the memory in the current sampling interval;

getting a second Physical Block by taking statistics of update times of each logical address in the current sampling interval; and

exchanging the logical address and data of the first Physical Block and the second Physical Block,

wherein getting the second Physical Block by taking statistics of update times of each logical address in the current sampling interval includes:

sampling a logical mapping table of the memory in the current sampling interval, the logical mapping table recording a mapping relation between logical address and physical address of each Physical Block in the memory,

taking statistics of the change times of the physical address mapped to each logical address from the sample obtained by the sampling, and

selecting a Physical Block corresponding to a logical address with the least change times as the second Physical Block,

wherein getting the first Physical Block by taking statistics of the degree of wear of each Physical Block in the memory in the current sampling interval includes:

taking statistics of the change times of the logical address mapped to the physical address of each Physical Block from the sample obtained by the sampling, and

selecting the Physical Block with the most change times of the logical address as the first Physical Block, and

wherein taking statistics of the change times of the logical address mapped to the physical address of each Physical Block from the sample obtained by the sampling includes:

for each sample, traversing each physical address and corresponding logical address recorded in the sample of the logical mapping table according to the increasing order of physical address, and, for each physical address traversed, deciding whether the logical address corresponding to the Physical Block has changed compared to the last sample of the logical mapping table, and

taking statistics of the change times of the logical address corresponding to each Physical Block in the memory in the current sampling interval.

2. The method of claim 1 , wherein, getting the first Physical Block by taking statistics of the degree of wear of each Physical Block in the memory in the current sampling interval comprises:

recording the change times of the logical address mapped to the physical address of each Physical Block in the current sampling interval in the memory; and

selecting a Physical Block with the most change times of the logical address as the first Physical Block.

3. The method of claim 1 , wherein, getting the first Physical Block by taking statistics the degree of wear of each Physical Block in the memory in the current sampling interval comprises: taking statistics of the change times of the logical address mapped to the physical address of each Physical Block from the sample obtained by the sampling, and selecting at least one Physical Block, the number of change times of the logical address of which reaches a threshold, as the first Physical Block;

getting the second Physical Block by taking statistics of update times of each logical address in the current sampling interval comprises: sampling logical mapping table of the memory in the current sampling interval, wherein the logical mapping table is used for recording mapping relation between logical address and physical address of each Physical Block in the memory; taking statistics of the change times of the physical address mapped to each logical address from the sample obtained by the sampling; and selecting at least one Physical Block corresponding to at least one logical address with the least change times of the physical address respectively as the second Physical Block, wherein the number of Physical Blocks included in the second Physical Block and the number of Physical Blocks included in the first Physical Block are the same; and

wherein exchanging the logical address and data of the first Physical Block and the second Physical Block comprises: matching the at least one first Physical Block with the at least one second Physical Block to obtain at least one pair of Physical Blocks comprising one first Physical Block and one second Physical Block, and exchanging the logical address and data of the first Physical Block and the second Physical Block of the same pair of Physical Blocks.

4. The method of claim 1 , wherein, getting the first Physical Block by taking statistics of the degree of wear of each Physical Block in the memory in the current sampling interval comprises: recording the change times of the logical address mapped to the physical address of each Physical Block in the current sampling interval, and selecting at least one Physical Block, the number of change times of the logical address of which reaches a threshold, as the first Physical Block;

getting the second Physical Block by taking of update times of each logical address in the current sampling interval comprises: sampling logical mapping table of the memory in the current sampling interval, wherein the logical mapping table is used for recording mapping relation between logical address and physical address of each Physical Block in the memory; taking statistics of the change times of the physical address mapped to each logical address from the sample obtained by the sampling; and selecting at least one Physical Block corresponding to at least one logical address with the least change times of the physical address respectively as the second Physical Block, wherein the number of Physical Blocks included in the second Physical Block and the number of Physical Blocks included in the first Physical Block are the same; and

wherein exchanging the logical address and data of the first Physical Block and the second Physical Block comprises: matching the at least one first Physical Block with the at least one second Physical Block to obtain at least one pair of Physical Blocks comprising one first Physical Block and one second Physical Block, and exchanging the logical address and data of the first Physical Block and the second Physical Block of the same pair of Physical Blocks.

5. The method of claim 3 , wherein, matching the at least one first Physical Block with the at least one second Physical Block to obtain at least one pair of Physical Blocks comprising one first Physical Block and one second Physical Block comprises:

arranging the at least one first Physical Block according to the decreasing change times of the logical address mapped to each physical address of the at least one first Physical Block;

arranging the at least one second Physical Block according to the increasing change times of the physical address mapped to each second Physical Block;

matching one first Physical Block and one second Physical Block of the same order to obtain a pair of Physical Blocks.

6. The method of claim 3 , wherein, the method further comprises:

detecting whether the first Physical Block and the second Physical Block are the same Physical Block, before exchanging the logical address and data of the first Physical Block and the second Physical Block of the same pair; and

if yes, the logical address and data of the first Physical Block and the second Physical Block are not exchanged.

7. The method of claim 3 , wherein, the method further comprises:

detecting whether the logical address and data of the first Physical Block and the second Physical Block has been exchanged in the current wear leveling process, before exchanging the logical address and data of the first Physical Block and the second Physical Block of the same pair; and

if yes, the logical address and data of the first Physical Block and the second Physical Block are not exchanged.

8. An apparatus for performing wear leveling in a memory, comprising:

a first unit, for dividing life cycle of the memory into at least one sampling interval;

a second unit, for getting a first Physical Block by taking statistics of degree of wear of each Physical Block in the memory in the current sampling interval, and getting a second Physical Block by taking statistics of update times of each logical address in the current sampling interval, with respect to each sampling interval divided by the first unit; and

a third unit, for exchanging the logical address and data of the first Physical Block and the second Physical Block gotten by the second unit,

wherein the second unit samples a logical mapping table of the memory in the current sampling interval, the logical mapping table recording a mapping relation between logical address and physical address of each Physical Block in the memory, takes statistics of the change times of the physical address mapped to each logical address from the sample obtained by the sampling, and selects a Physical Block corresponding to a logical address with the least change times as the second Physical Block,

wherein the second unit takes statistics of the change times of the logical address mapped to the physical address of each Physical Block from the sample obtained by the sampling, and selects the Physical Block with the most change times of the logical address as the first Physical Block, and

wherein, for each sample, the second unit traverses each physical address and corresponding logical address recorded in the sample of the logical mapping table according to the increasing order of physical address, and, for each physical address traversed, decides whether the logical address corresponding to the Physical Block has changed compared to the last sample of the logical mapping table, and takes statistics of the change times of the logical address corresponding to each Physical Block in the memory in the current sampling interval.

9. The apparatus of claim 8 , wherein, the apparatus further comprises:

a fourth unit, for recording the change times of the logical address mapped to the physical address of each Physical Block in the current sampling interval;

the second unit is further used for taking statistics of the degree of wear based on the change times recorded by the fourth unit.

10. The apparatus of claim 8 , wherein, the first Physical Block is the Physical Block with the highest degree of wear, and the second Physical Block is the Physical block corresponding to the logical address with the least update times.

11. The apparatus of claim 8 , wherein, the first Physical Block comprises at least one Physical Block, the degree of wear of which reaches a threshold, and the second Physical Block comprises at least one Physical Block corresponding to at least one logical address with the least update times respectively, the number of Physical Blocks included in the second Physical Block and the number of Physical Blocks included in the first Physical Block are the same;

the third unit is further used for composing at least one pair of Physical Blocks through matching the at least one first Physical Block with the at least one second Physical Block, and exchanging the logical address and data of one first Physical Block and one second Physical Block of the same pair.

12. The apparatus of claim 8 , wherein, the memory is a Flash memory.