Patent ID: 8296539

Claim:
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.