CN102222046B - Abrasion equilibrium method and device - Google Patents

Abstract

The invention discloses a wear leveling method, which determines the pool mask of each physical block according to the erasing times of each physical block; wherein, for different times of erasing, the pool mask of the physical block is determined as a cold pool Mask CPM, normal pool mask NPM, or hot pool mask HPM; when the pool mask with physical blocks changes from NPM to HPM, copy the data in any physical block whose pool mask is CPM to said pool The physical block whose mask is HPM, and the physical block whose pool mask is CPM is used as a garbage block for garbage collection. The invention also discloses a wear leveling device, the method and the device can reduce the extra wear caused by the wear leveling.

Description

Wear leveling method and device

technical field

The invention relates to the field of storage technology, in particular to a wear leveling method and device.

Background technique

At present, non-volatile memory is widely used in computers, communications and consumer electronics products; for example, U disk, MP3, digital camera, mobile communication terminal, solid-state hard disk and other products Volatile memory as a storage medium. As the storage capacity requirements of these products continue to increase, the process size of non-volatile memory continues to shrink, causing the reliability of non-volatile memory to face more and more severe challenges, especially the erase operation of non-volatile memory The number of erasures of the smallest unit physical block is limited, which will have a serious impact on the service life of the non-volatile memory. For the problem that the number of erasures of physical blocks is limited, the existing technology is to perform wear leveling on physical blocks. By controlling the erasure of physical blocks, try to average the number of erasures of all physical blocks in the memory to avoid certain physical blocks. The number of erasures is too high, and the upper limit of erasure times is reached earlier than other physical blocks, causing the memory to fail as a whole when there are still many physical blocks that have not reached their service life.

Wear leveling includes controlling the physical blocks written during the data writing process, dynamically balancing the dynamic wear leveling of all physical block erasing times, and adjusting the data stored on the physical blocks (hot data that is often erased or infrequently written) There are two types of static wear leveling that statically balances the erasure times of all physical blocks. For these two types of wear leveling, many algorithms have been proposed in the prior art, but these algorithms have not been able to solve the contradiction between the effect of wear leveling and the reduction of additional wear caused by the wear leveling algorithm itself, and the existing The implementation of the wear leveling algorithm is based on saving the wear information of each physical block. As the memory capacity increases, the number of physical blocks that need to be wear leveled in the memory increases greatly. When the wear leveling algorithm is executed, the speed of searching for the wear information of the physical blocks also increases. become slower and slower.

The following is a detailed description of the prior art by taking a representative wear leveling algorithm "dual pool algorithm" which is widely used at present as an example.

As shown in Figure 1, this algorithm is a comprehensive algorithm that combines dynamic wear leveling and static wear leveling. The algorithm sets cold pool and hot pool attributes for physical blocks, and defines EC as the total number of erasures of physical blocks; EEC It is the number of erasing times accumulated after the hot and cold pool attributes of the physical block are changed (hereinafter referred to as the effective erasing times); PT is the hot and cold pool attribute mark of the physical block. Pool, the wear information that needs to be recorded for each physical block includes EC, EEC, and PT.

分别表示冷池中擦除次数队列，热池中擦除次数的队列，冷池中有效擦除次数的队列，热池中有效擦除次数的队列。定义H⁺(Q)和H^-(Q)分别为返回队列Q的最大值和最小值(具体物理块)的函数；EC(B)为返回物理块B的总擦除次数的函数；EEC(B)为返回物理块B的有效擦除次数的函数。In the algorithm, define

Respectively represent the queue of erasure times in the cold pool, the queue of the erasure times in the hot pool, the queue of the effective erasure times in the cold pool, and the queue of the effective erasure times in the hot pool. Define H ⁺ (Q) and ^H- (Q) to be the function of returning the maximum value and the minimum value (concrete physical block) of queue Q respectively; EC(B) is the function that returns the total erasing times of physical block B; EEC( B) is a function that returns the effective erasure count of physical block B.

The specific algorithm execution process is shown in Figure 1, including the following steps:

Step 101, obtain wear information; before executing the dual-pool algorithm, it is necessary to obtain wear information of all physical blocks before managing the physical blocks. This step of obtaining wear information is generally completed during the power-on initialization process of the memory. In two cases, if the memory is not used for the first time, the wear information will be recorded in the memory when the memory is unloaded normally last time (such as a backup area specially divided in the memory and invisible to the user for storing management information) , when the memory is powered on and initialized, you only need to read the data in the backup area of the memory to get the wear information; if the memory is used for the first time, there is no data in the backup area. Set to 0, and mark the hot and cold pool attributes on the physical block, and divide the physical block into the cold pool or the hot pool; the specific method of dividing the physical block into the cold pool and the hot pool can be arbitrary, such as random division.

Step 102, judge whether there is a write request, if yes, enter step 103, otherwise enter step 117;

Step 103, judging whether the write block assigned to the write request has been filled, if so, proceed to step 104, otherwise proceed to step 105;

Step 104, from the preset blank block queue, allocate a blank block for the write request according to the new allocation (FIFO) method (according to the order of entering the blank block queue, the blank block that first enters the queue will be allocated first), Go to step 105;

Step 105, responding to the write request, writing the data into the allocated write block;

之差是否超过设定的阈值TH，若是，则进入步骤107，否则进入步骤111；Step 106, judge and

Whether the difference exceeds the set threshold TH, if so, then enter step 107, otherwise enter step 111;

上保存的数据。Step 107, mandatory recycling Physical block, that is, to copy the valid data stored on this physical block to other physical blocks and erase

data saved on.

物理块上的数据复制到

物理块；Step 108, will

The data on the physical block is copied to

physical block;

物理块上的数据，使之变为空白块；Step 109, Erase

Data on the physical block, making it a blank block;

物理块的冷热池属性；因冷热池属性变化，和

物理块各自的EEC将清零，重新开始累计。Step 110, exchange and

The hot and cold pool properties of the physical block; due to the change of the hot and cold pool properties, and

The EEC of each physical block will be cleared to zero, and the accumulation will start again.

和

之差是否超过2倍阈值TH；若是，进入步骤112，否则进入步骤113；Step 111, judge

and

Whether the difference exceeds 2 times the threshold TH; if so, enter step 112, otherwise enter step 113;

物理块的PT从热池调整为冷池；Step 112, will

The PT of the physical block is adjusted from the hot pool to the cold pool;

和

之差是否超过阈值TH；若是，则进入步骤114，否则进入步骤115；Step 113, judge

and

Whether the difference exceeds the threshold TH; if so, then enter step 114, otherwise enter step 115;

物理块的PT从冷池调整为热池；Step 114, will

The PT of the physical block is adjusted from the cold pool to the hot pool;

Step 115, judging whether the available space of the memory is less than a preset threshold, if so, then enter step 116, otherwise return to step 102;

Step 116, garbage collection, return to step 102;

Step 117, determine whether the memory is unloaded, if so, enter step 118, otherwise return to step 102;

Step 118, save the wear information, and end the process.

Among the above steps, steps 102-103 and 105 are the normal data writing process, and step 104 is the dynamic balance part of the algorithm, that is, through the blank block queue, the allocation of blank blocks is controlled by FIFO to achieve the effect of dynamic wear balance .

上保存的冷热数据，以及交换

与

的冷热池属性，使得擦除次数多的物理块因保存冷数据并进入冷池而减缓磨损，擦除次数少的物理块因保存热数据并进入热池而加快磨损，从而达到磨损均衡的目的。Steps 106-114 are the static equalization part of the algorithm, by moving and

The hot and cold data saved on it, and the exchange

and

The properties of hot and cold pools make the physical blocks that have been erased more often slow down wear because they store cold data and enter the cold pool, and the physical blocks that have been erased less frequently because they store hot data and enter the hot pool to accelerate wear, thereby achieving wear balance. Purpose.

Step 115 is followed by garbage collection and unloading of the memory; wherein garbage collection includes data transfer and erasure. The so-called data transfer means that the data marked as valid must be copied to other blocks before erasing; the so-called erasing process refers to the physical block that has written data but all data has been marked as invalid, that is, the garbage block In the process of erasing to obtain blank blocks, in the existing garbage collection process, garbage blocks are generally randomly selected, and the dynamic balance part of the dual-pool algorithm does not improve the garbage collection process. In addition, during the unloading process, the memory will store the wear information (such as EC, EEC, PT and blank block queue) required by the dual-pool algorithm for use when the memory is started next time.

和

两个物理块的有效数据，并且擦除

和

两个块。这会产生较大的系统开销，并额外增加物理块的擦除次数，即额外的磨损，这对于磨损均衡的目的(增加存储器寿命)来说，是一个反效果。Obviously, in order to statically balance all physical block erase times, the dual-pool algorithm needs to move

and

two physical blocks of valid data, and erase

and

two blocks. This will generate a large system overhead and additionally increase the erasure times of the physical block, that is, additional wear, which is a counter-effect for the purpose of wear leveling (increasing the lifetime of the memory).

和

这需要遍历整个存储器的所有物理块，然后才能进一步地往下运行。然而随着存储容量的不断提高，物理块的数量也在不断地增加，搜索物理块的速度也会变得越来越慢。In addition, since the two-pool algorithm needs to calculate

and

This needs to traverse all physical blocks of the entire memory before it can be further run down. However, with the continuous improvement of storage capacity, the number of physical blocks is also increasing, and the speed of searching for physical blocks will also become slower and slower.

Contents of the invention

Embodiments of the present invention provide a wear leveling method, which can reduce extra wear caused by wear leveling.

An embodiment of the present invention provides a wear leveling device, which can reduce extra wear caused by wear leveling.

In order to achieve the above object, the technical solution of the present invention is specifically realized in the following way:

A wear leveling method, the method comprising:

Determine the pool mask of each physical block according to the erasure times of each physical block;

Wherein, for different times of erasing, the pool mask of the physical block is determined as a cold pool mask CPM, a common pool mask NPM or a hot pool mask HPM;

When the pool mask of a physical block changes from NPM to HPM, copy the data in any physical block whose pool mask is CPM to the physical block whose pool mask is HPM, and set the pool mask Physical blocks for CPM are garbage collected as garbage blocks.

Preferably, for different erasing times, the pool mask of the physical block is determined as a cold pool mask CPM, a common pool mask NPM or a hot pool mask HPM, including:

When the number of erasures of the physical block is equal to the value of RECC, the pool mask of the physical block is determined to be CPM; when the number of erasures is greater than or equal to the value of RECC+TH, the pool mask of the physical block is determined to be HPM; when the number of erasures is other values Determine the pool mask of the physical block as NPM;

Wherein, the RECC is a reference erasure count counter whose value is equal to the erasure count of the physical block with the minimum erasure count in all physical blocks;

The TH is a preset threshold, and its value is a positive integer greater than 1.

Preferably, the method further comprises:

Establishing a blank block linked list EBL for managing blank blocks, the blank blocks in the EBL are arranged in ascending order according to their erasure times;

When a blank block needs to be allocated for a write request, the first blank block in the EBL is allocated to the write request as a write block.

Preferably, the EBL does not allow blank blocks whose pool mask is HPM to enter.

Preferably, the method further comprises:

A garbage block linked list GBL for managing garbage blocks is established, and the garbage blocks in the GBL are arranged in ascending order of erasure times.

Preferably, the GBL does not allow garbage blocks whose pool mask is HPM to enter.

Preferably, when the number of blank blocks in the EBL is less than a preset threshold, the following garbage collection process is performed:

If the GBL is non-empty, then erase the data of the first garbage block in the GBL to make it a blank block, and insert the blank block into the EBL;

If the GBL is empty, write the effective data of the physical block with the largest amount of garbage data and the least number of erasures among all physical blocks masked as CPM and NPM to the currently allocated write block, and write the garbage data with the largest amount of garbage data. And the physical block with the least erasing times is inserted into the GBL; the data of the first garbage block in the GBL is erased to make it a blank block, and the blank block is inserted into the EBL.

Preferably, the garbage collection includes:

Insert garbage blocks with pool masks CPM and NPM into the GBL.

Preferably, if the memory is used for the first time, before performing the step of determining the pool mask of each physical block according to the erasing times of each physical block, set the current erasing times of all physical blocks as 0; the current pool mask of all physical blocks is CPM.

Preferably, if the memory is not used for the first time and is normally unloaded after the last use, before performing the step of determining the pool mask of each physical block according to the number of erasing times of each physical block, from the memory Read the backup area of all physical blocks to get the current erasure count, pool mask, EBL, GBL.

Preferably, if the memory is not used for the first time and has not been normally unloaded after the last use, before performing the step of determining the pool mask of each physical block according to the number of erasures of each physical block,

Load the erasure count, pool mask, EBL, GBL of all physical blocks backed up during the last normal unload from the backup area of the memory;

Starting from the first physical block in the EBL, check the storage status of the physical blocks in the EBL one by one. If the physical block is not a blank block, delete the physical block from the EBL; the detection continues until the physical block is detected as a blank block or the EBL is empty. until;

Starting from the first physical block in the GBL, check the storage status of the physical blocks in the GBL one by one. If the physical block is already a blank block, delete the physical block from the GBL and insert the physical block into the EBL; the detection continues until the physical block is detected. until the block is a garbage block or the GBL is empty.

Preferably, if the pool masks of all physical blocks are no longer CPM; then modify the value of RECC according to the erasure times of the physical block with the smallest erasure times in all current physical blocks, and re-determine all Pool mask for physical blocks.

Preferably, the method further includes: when the memory is normally unloaded, saving the current erasure times, pool masks, and current EBL and GBL of all physical blocks to the backup area of the memory.

Preferably, the erasure count of each physical block is also stored in the physical page of the physical block in real time.

A wear leveling device, the device comprising:

The pool maintenance module is used to determine the pool mask of each physical block according to the number of erasing times of each physical block; wherein, for different times of erasing, the pool mask of the physical block is a cold pool mask CPM, a common pool mask code NPM or hotpool mask HPM;

A static balance module, connected to the pool maintenance module, is used to copy the data in any physical block whose pool mask is CPM to the pool mask when the pool mask of the physical block changes from NPM to HPM On the physical block coded as HPM;

The garbage collection module is connected with the static balancing module, and is used for performing garbage collection on the physical block whose pool mask is CPM as a garbage block.

Preferably, the pool maintenance module includes:

The determination unit is used to determine that the pool mask of the physical block is CPM when the number of erasing times of the physical block is equal to the value of RECC; it is HPM when the number of erasing times is greater than or equal to the value of RECC+TH; it is NPM when the number of times of erasing is other values;

Wherein, the RECC is a reference erasure count counter, whose value is equal to the erasure count of the physical block with the smallest erasure count among all physical blocks; the TH is a preset threshold, and its value is a positive integer greater than 1.

Preferably, the device further includes:

The EBL module maintains the blank block linked list EBL for managing blank blocks; arranges the blank blocks in the EBL in ascending order according to the number of erasures; when it is necessary to allocate a blank block for a write request, the first blank in the EBL is allocated A block is allocated to the write request as a write block.

Preferably, the EBL module does not allow blank blocks whose pool mask is HPM to enter.

Preferably, the device further includes:

The GBL module is connected to the garbage collection module and the EBL module respectively, maintains a garbage block linked list GBL for managing garbage blocks, and arranges the garbage blocks in the GBL in ascending order according to the number of erasures.

Preferably, the GBL module does not allow garbage blocks whose pool mask is HPM to enter.

Preferably, the GBL module is further used, when the available space in the memory is less than a preset threshold;

If GBL is non-empty, then erase the data of the first garbage block in the GBL to make it a blank block; and insert the blank block into the EBL maintained by the EBL module;

If the GBL is empty, first write the valid data in the physical block with the most garbage data and the least number of erasures among the physical blocks whose pool masks are CPM and NPM to the currently allocated write block, and write the garbage Insert the physical block with the most data and the least erasure times into the GBL; then erase the data of the first garbage block in the GBL to make it a blank block; and insert the blank block into the EBL.

Preferably, the garbage collection module is specifically configured to insert garbage blocks whose pool masks are CPM and NPM into the GBL maintained by the GBL module.

Preferably, said pool maintenance module further comprises:

The current value determining unit is connected with the determining unit, and is used to set the current erasure times of all physical blocks to 0 when the memory is used for the first time; the current pool mask of all physical blocks is CPM.

Preferably, said pool maintenance module further comprises:

The current value determination unit is connected with the determination unit, and is used to read the current erasure times and pool mask of all physical blocks from the backup area of the memory when the memory is not used for the first time and is normally unloaded after the last use. Code, and EBL, GBL.

Preferably, said pool maintenance module further comprises:

The current value determination unit is connected to the determination unit, and is used for when the memory is not used for the first time and has not been unloaded normally after the last use,

Load the current erasure count, pool mask, EBL, GBL of all physical blocks backed up during the last normal unload from the backup area of the memory;

Described EBL module starts from the first physical block in the EBL, detects the storage status of the physical block in the EBL one by one, if the physical block is not a blank block, then deletes this physical block from the EBL; detection continues until the physical block is detected as a blank block Or until the EBL is empty;

The GBL module starts from the first physical block in the GBL, checks the storage status of the physical blocks in the GBL one by one, if the physical block is already a blank block, deletes the physical block from the GBL, and inserts the physical block into the EBL for maintenance EBL; the detection continues until the physical block is detected as a garbage block or the GBL is empty.

Preferably, said pool maintenance module further comprises:

The reconstruction unit is connected with the determination unit, and when the pool masks of all physical blocks are no longer CPM; the value of RECC is corrected according to the erasure count of the physical block with the smallest erasure count among all current physical blocks, and according to the correction The post-RECC re-determines the pool mask for all physical blocks.

Preferably, the device further includes:

The backup module is connected to the pool maintenance module, EBL module, and GBL module respectively, and is used to save the current erasure times, masks, and current EBL and GBL of all physical blocks to the backup area of the memory when the memory is unloaded normally.

Preferably, the backup module is further configured to store the erasure count of each physical block in the physical page of the physical block in real time.

It can be seen from the above technical solution that the wear leveling method and device of the present invention divide the physical block into three pools, and improve the existing static equalization part, so that the wear leveling method of the present invention only divides the cold pool When the physical block of the mask is garbage collected, an additional wear is generated, which reduces the additional wear compared with the existing technology. In addition, the present invention controls garbage collection, write block allocation, etc. through the EBL and GBL linked lists, and the dynamic part of wear leveling obtains a better wear leveling effect than the prior art, and further prohibits the physical Blocks enter EBL and GBL, so that the physical blocks with more wear will not continue to wear, and while better wear leveling effects are obtained, the speed when the wear leveling method of the present invention is searched for physical blocks is also reduced, so that the overall execution of the present invention Efficiency and speed are also improved compared to the prior art.

Description of drawings

FIG. 1 is a flowchart of an existing wear leveling method;

FIG. 2 is an overall flowchart of a wear leveling method according to an embodiment of the present invention;

FIG. 3 is a flowchart of a garbage collection method according to an embodiment of the present invention;

Fig. 4 is a flow chart of the static equalization part in the wear leveling method of the embodiment of the present invention;

FIG. 5 is a flow chart of the general thought of the wear leveling method according to the embodiment of the present invention;

6 is a schematic structural diagram of a wear leveling device according to an embodiment of the present invention;

Fig. 7 is a schematic structural diagram of a pool maintenance module according to an embodiment of the present invention.

Detailed ways

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below with reference to the accompanying drawings and examples.

The present invention mainly determines the pool mask of each physical block according to the erasing times of each physical block; wherein, for different times of erasing, the mask of the physical block is a cold pool mask CPM, a common pool mask NPM or Hot pool mask HPM (for convenience of description, physical blocks with cold pool masks are called cold pool blocks, physical blocks with common pool masks are called normal pool blocks, and physical blocks with hot pool masks are called The block is called a hot pool block); during static balancing, when the pool mask of a physical block with a pool mask of NPM changes to HPM, copy the data in a physical block with a pool mask of CPM to the pool The mask becomes the physical block of the HPM, and the physical block whose pool mask is the CPM is used as a garbage block for garbage collection. Since the present invention improves the static balance part of the existing wear leveling, only one additional wear is generated, that is, when the physical block whose pool mask is CPM is garbage collected, an erasure action will be generated, so compared with the prior art Additional wear is reduced.

In addition, the present invention can further improve the dynamic part of the existing wear leveling, and control the garbage collection process and the allocation process of written blocks according to the erasure times of physical blocks, and the hot pool blocks do not participate in the allocation of written blocks and the recovery of garbage blocks , so that when the wear leveling method of the present invention is executed, the required search range of physical blocks is smaller and the speed is faster.

Specifically, the general idea of the present invention is shown in Figure 5, including the following steps:

Step 501, determine the pool mask of each physical block according to the number of erasing times of each physical block; where, for different times of erasing, the pool mask of the physical block can be determined as cold pool mask CPM, common pool mask NPM or Hot Pool Mask HPM.

In the wear leveling method of the present invention, for each physical block (hereinafter referred to as block) that needs to be wear leveled, three block attributes of cold pool, common pool and hot pool are set, and the pool mask is used to identify and distinguish, The pool mask can be in the form of a two-digit binary code. For example, 00 indicates that the block belongs to the cold pool, 01 indicates that the block belongs to the normal pool, and 11 indicates that the block belongs to the hot pool. In addition, each block records its erasure count, and determines a reference erasure count RECC (the value of RECC is equal to the erase count of the block with the smallest erasure count among all blocks) and a preset threshold representing the distance between hot and cold pools (TH) is used to determine which pool mask the physical block should correspond to, where TH is an integer greater than 1, the block whose erasure times is equal to RECC is a cold pool mask, and the block whose erasure times is greater than or equal to RECC+TH is a hot pool mask code, blocks with erasure counts of other values are common pool masks. The pool mask will be modified in real time according to the change of the number of erase times of the physical block. The specific modification method is: after each change of the number of erase times, compare the changed number of erase times with RECC. If the result is 1, modify the current The pool mask is the normal pool mask NPM, if the result is TH, modify the current pool mask to the hot pool mask HPM, and keep the current pool mask unchanged for other results.

Step 502, when the pool mask of the physical block is changed from NPM to HPM, copy the data in the physical block whose pool mask is CPM to the physical block whose pool mask is HPM; and Physical blocks whose pool mask is CPM are garbage collected as garbage blocks.

This step is the static balancing part of the wear leveling of the present invention, when the erasing times of the common pool blocks reach the standard for entering the hot pool, that is, when the times of erasing is greater than or equal to RECC+TH (for example, data erased by the garbage collection process When the ordinary pool block becomes a hot pool block), select a block from the cold pool, move the data on the cold pool block to the block that enters the hot pool, and recycle the cold pool block (the garbage collection process can use the current Some garbage collection methods can also adopt the improved method of the present invention, and the improved garbage collection method of the present invention will be described in detail later). Through this process, the cold pool block can be released from the cold data, so that it can be rewritten to speed up the wear of the cold pool block and achieve a better wear leveling effect. At the same time, this static balancing process only An additional wear is generated, that is, the blocks selected from the cold pool are erased to generate an additional wear, while the blocks entering the hot pool are blocks in the normal garbage collection process, and their data erasure is not caused by this method, so the comparison of double The pool algorithm requires one less additional wear.

Further, the present invention can also improve the dynamic balance part of the prior art, construct a blank block linked list EBL for managing blank blocks and a garbage block linked list GBL for managing garbage blocks, and allocate write operations for write operations through the EBL. The queue of blank blocks in the process of entering blocks is controlled by GBL in the queue of garbage blocks in the process of garbage block recovery; among them, EBL and GBL are arranged in ascending order according to the number of erasures (blocks with a small number of erasures are arranged in the front, and vice versa, for Blocks with the same number of erasures can come first, or can be arranged at will;) elements in the linked list (blank blocks in EBL, garbage blocks in GBL), so as to ensure that garbage blocks with less erasure times are recycled first, And priority is given to assigning blank blocks with fewer erase times as write blocks to write requests to achieve a good wear leveling effect; and EBL and GBL will exclude hot pool blocks, and no hot pool blocks will enter EBL and GBL, thus It can keep the hot pool block from being erased, further improve the effect of wear leveling, reduce the range of physical blocks to be searched, and improve the search speed.

Some specific examples will be given below to illustrate the wear leveling algorithm of the present invention. The following are examples of improving the dynamic part and the static part of the prior art at the same time:

Fig. 2 is an overall flowchart of a wear leveling method according to an embodiment of the present invention. As shown in Fig. 2, the method includes the following steps:

Step 201, obtain wear information; wear information refers to the information required for wear leveling, including the erasure times of each physical block, the pool mask of each physical block, and EBL, GBL; if the memory is not used for the first time , the current value of these wear information can be directly read from the backup area of the memory. If it is used for the first time, you need to create the wear information first, such as setting the erasure times of all blocks to 0, and marking the pool mask for all physical blocks , Establish EBL, GBL, etc. The method of determining the pool mask has been described in detail above, and will not be repeated here; among them, when it is used for the first time, the erasure times of all blocks is 0, so RECC is also 0, that is, all blocks are in It will be determined as the cold pool mask CPM when it is used for the first time.

Whether it is used for the first time can be judged by checking whether there is backup data in the backup area of the memory, if there is no backup data, it means it is the first use, otherwise it is not the first time use.

In addition, it should be noted that if the memory is used for the first time, the initialization process will also include the search and processing of bad blocks, that is, to find out all the initial bad blocks; while looking for bad blocks, you can detect each block. state, if there is data, the data is invalid for the user due to the first use, then when establishing GBL and EBL, the block can be put into GBL and wait for erasure; if there is no data, then the block can be put into EBL for waiting use. Wherein, bad blocks are not included in the range of all physical blocks described in the present invention because they cannot be used.

If the memory is not used for the first time and was not unloaded normally when it was used last time, the GBL and EBL obtained may be incorrect when obtaining the wear information, and the GBL and EBL need to be corrected; specifically, it can be obtained from the backup area Load the wear information backed up during the last normal unload, and then check the storage status of each block in the EBL starting from the head of the linked list in the EBL. If a block is not empty, it indicates that the block has been allocated before the last unload, so This block should be removed from the EBL. This checking process continues until the first blank block is encountered or the EBL is empty. Similarly, it is necessary to check the status of the GBL, starting from the head of the GBL linked list to detect the storage status of each block in the GBL. If a block is a blank block, it means that the block has been recycled before the last unloading, so it should be deleted from the GBL and placed in the GBL. into the EBL; this check continues until the first non-blank block is encountered or the GBL is empty.

Step 202, determine whether there is a write request, if so, enter step 203, otherwise enter step 213;

Step 203, judging whether the write block is full? If so, then enter step 204, otherwise enter step 205;

Step 204, assigning the first element in the EBL linked list as a write block;

Step 205, responding to the write request;

Step 206, judging whether the available memory space is less than a preset threshold, if so, proceed to step 207, otherwise return to step 202;

Step 207, garbage collection, the specific process will be described in detail later;

Step 208, judging whether the recovered garbage block is a cold pool block before recycling, if so, then enter step 211, otherwise enter step 209;

Step 209; Judging whether the reclaimed garbage block becomes a hot pool block after reclaiming (the original data will be erased when the garbage block is reclaimed, and the number of times of erasing will be increased by 1, if the number of times of erasing after adding 1 reaches RECC+TH, then think that the block becomes a hot pool block after recycling), if so, enter step 210, otherwise return to step 202;

Step 210, static equalization, enter step 211;

Step 211, judge whether the cold pool is empty, if so, then enter step 212, otherwise return to step 202;

Step 212, reconstruct the three pools, and return to step 202. If the cold pool is empty, the wear leveling algorithm of the present invention will not be able to continue, so it is necessary to re-determine the new RECC according to the erasure count value of the block with the smallest erasure times among all the blocks at present, and then re-determine the physical pool according to the new RECC. The pool mask of the block, thus maintaining the three-pool structure.

Step 213, determine whether the memory is unloaded, if so, enter step 214, otherwise return to step 202;

Step 214, save the wear information, and end the process.

Wherein, steps 202～207 are the dynamic balancing part of the present invention, wherein 202, 203, 205 and 206 are the same as the prior art, and are not repeated here; in step 204, the mode of distributing write blocks from the EBL is from the The header elements are allocated sequentially, so it can be guaranteed that blocks with a small number of erasures can be allocated to write requests first, and step 207 is the key to the dynamic balance part of the present invention. By improving the existing garbage collection process, the present invention can be used in garbage collection. The process can also produce a wear leveling effect, so that the present invention is much better than the prior art in terms of the dynamic wear leveling effect; the specific garbage collection process will be described in detail later.

Steps 208-210 are the static equalization part, in which steps 208 and 209 are used to determine whether static equalization is required. In fact, the trigger of static equalization in the present invention is that the pool mask of the physical block of the normal pool mask changes to the hot pool mask. When coding, steps 208 and 209 are used to judge the pool mask of the physical block before the pool mask change and the pool mask after the change respectively. The order of these two steps can be exchanged without affecting the final As a result of the judgment, the specific process of static equalization in step 210 will be described in detail later.

Steps 213 and 214 are similar to the existing normal unloading process and are not repeated here. The difference is that when storing wear information, EBL and GBL, erasure times of all blocks and SLWM information are stored. In addition, each physical block also saves the erasing times of the physical block in the redundant area of its physical page.

The garbage collection process of the dynamic balancing part of the present invention will be described in detail below:

In fact, garbage collection includes two parts, namely ordinary garbage collection and mandatory garbage collection; ordinary garbage collection refers to when a garbage block is detected (if a data is updated, then its old version is marked as garbage, when a When all the data on the block is marked as garbage, the block is a garbage block) the process of reclaiming the garbage block, this process is to directly erase the data on the garbage block and add it to the end of the blank block queue in the prior art, but in this In the invention, instead of immediately erasing the data on the garbage block, it is first inserted into the GBL for use. Only when the number of blank blocks in the EBL is less than the preset threshold, a garbage block is selected from the GBL and erased. Insert into EBL after removing data; in EBL, elements are arranged in ascending order of erasure times, and when allocating write blocks, always allocate head elements; GBL arranges and allocates garbage blocks in the same way as EBL, thus ensuring erasure Blocks with fewer times can be erased and utilized first, and for physical blocks marked as hot pools, even if they have become garbage blocks, they will not be recycled, that is, the garbage blocks will not be inserted into the GBL. The action of detecting garbage blocks in ordinary garbage collection can be performed repeatedly at certain time intervals, or can be performed after a certain action, for example, after the response write request in step 205 is completed. And mandatory garbage collection (such as step 207) is only carried out when the available space of the memory is less than the preset threshold (non-threshold TH), and the specific process is as shown in Figure 3, including the following steps:

Step 301, determine whether the GBL is non-empty, if so, enter step 302, otherwise enter step 303;

Step 302, recover the first element in the GBL, and enter step 306;

Step 303, find the block with the most garbage and the least number of erasures in the cold pool and the common pool;

Step 304, writing the valid data on the block into the currently allocated write block;

Step 305, insert the block into the GBL, and return to step 302.

Step 306, insert the recovered garbage block into the EBL, and end the process.

With the progress of the above dynamic balance, some blocks leave the cold pool, and some blocks stay in the cold pool because the written data is cold data (such as system files) and are not updated for a long time. For these blocks that stay in the cold pool for a long time The block of the pool can accelerate its wear through the static equalization process of the present invention, thereby improving the effect of wear equalization. The specific method is shown in Figure 4, including the following steps:

Step 401, find a cold pool block; this cold pool block can be any cold pool block found at random; it can also be the earliest cold pool block with the earliest last modification time of the data stored on the cold pool block according to certain rules. pool block.

Step 402, copying the data of the cold pool block to the garbage block entering the hot pool;

Step 403, insert the cold pool block found above into the GBL linked list, which can be inserted into the first position of the GBL, or inserted according to the arrangement rules of the GBL.

The above-described embodiment of the wear leveling method of the present invention is only a preferred embodiment of the present invention. If only the above-mentioned static part is implemented, EBL and GBL do not need to be established, and operations related to EBL and GBL do not need to be executed. The existing blank block queue and garbage collection process are used; however, if the above dynamic part and static part are implemented at the same time, in addition to speeding up the physical block search speed when executing the algorithm, a better wear leveling effect can be obtained. After experiments, this When the invention implements the above-mentioned static part and dynamic part at the same time, the unbalanced degree of wear can be strictly controlled within TH ² /4 (that is, the value of the square of the preset threshold TH divided by 4), effectively extending the non-volatile The lifespan of the memory.

In addition, the present invention also provides a wear leveling device, as shown in Figure 6, the device includes:

The pool maintenance module 601 is used to determine the pool mask of each physical block according to the erasing times of each physical block; wherein, for different times of erasing, the pool mask of the physical block is cold pool mask CPM, common pool mask NPM or hotpool mask HPM;

Static balancing module 602, connected to the pool maintenance module 601, is used to copy the data in the physical block whose pool mask is CPM to the pool when the pool mask of the physical block changes from NPM to HPM On the physical block masked as HPM;

The garbage collection module 603 is connected to the static balance module 602, and is configured to use the physical block whose pool mask is CPM as a garbage block for garbage collection.

Wherein, the pool maintenance module is as shown in Figure 7, including:

Determining unit 701 is used to determine that the pool mask is a cold pool mask when the number of erasing times of the physical block is equal to the value of RECC; it is a hot pool mask when the number of erasing times is greater than or equal to the value of RECC+TH; the number of times of erasing Normal pool mask for other values;

Wherein, the RECC is a reference erasure count counter, whose value is equal to the erasure count of the physical block with the smallest erasure count among all physical blocks; the TH is a preset threshold, and its value is a positive integer greater than 1, It represents the distance between the cold pool and the hot pool.

Preferably, the device may further include:

The EBL module 604 maintains a blank block linked list EBL for managing blank blocks; arranges the blank blocks in the EBL in ascending order according to the number of erasures; when it is necessary to allocate a blank block for a write request, the first A blank block is allocated to the write request as a write block.

In addition, the EBL module 604 can further prohibit the entry of the blank blocks whose pool mask is HPM, so as to protect the hot pool blocks from being further worn out.

Preferably, the device can further include:

The GBL module 605 is connected to the garbage collection module 603 and the EBL module 604 respectively, and maintains a garbage block linked list GBL for managing garbage blocks; arranges the garbage blocks in the GBL in ascending order according to the number of erasures.

In addition, the GBL module 605 may further prohibit the entry of garbage blocks whose pool mask is HPM, so as to protect the hot pool blocks from further wear.

When the number of blank blocks in the EBL maintained by the EBL module 604 is less than a preset threshold, the GBL module 605 can further be used to determine whether the GBL is not empty;

If the GBL is not empty, then erase the data of the first garbage block in the GBL to make it a blank block; and insert the blank block into the EBL maintained by the EBL module 604;

If the GBL is empty, first write the valid data in the physical block with the most garbage data and the least number of erasures among the physical blocks whose pool mask is cold pool mask and normal pool mask to the currently allocated write block on, and insert the physical block with the most garbage data and the least number of times of erasure into the GBL; then erase the data of the first garbage block in the GBL to make it a blank block; and insert the blank block into the EBL.

The garbage collection module 603 is specifically configured to insert garbage blocks masked as cold pool masks and common pool masks into the GBL maintained by the GBL module.

Preferably, the pool maintenance module 601 may further include:

The current value determining unit 702 is connected with the determining unit 701, and is used to set the current erasure times of all physical blocks to 0 when the memory is used for the first time; the current pool mask of all physical blocks is a cold pool mask code.

Alternatively, the pool maintenance module 601 may further include:

The current value determination unit 702 is connected with the determination unit 701, and is used to read the current erasure times, the current erasure times, Pool mask, and EBL, GBL.

Alternatively, the pool maintenance module 601 may further include:

The current value determining unit 702 is connected to the determining unit 701, and is used for when the memory is not used for the first time and has not been unloaded normally after the last use,

Load the current erasure count, pool mask, EBL, GBL of all physical blocks backed up during the last normal unload from the backup area of the memory;

Described EBL module 604 starts from the first physical block in the EBL, detects the storage status of the physical blocks in the EBL one by one, if the physical block is not a blank block, then deletes this physical block from the EBL; detection continues until the physical block is detected to be blank until the block or EBL is empty;

The GBL module 605 starts from the first physical block in the GBL, checks the storage status of the physical blocks in the GBL one by one, if the physical block is a blank block, deletes the physical block from the GBL, and inserts the physical block into the EBL Maintained EBL; detection continues until either the physical block is detected as a garbage block or the GBL is empty.

Preferably, the pool maintenance module 601 may further include:

Reconstruction unit 703, connected to the determination unit 701, when the pool masks of all physical blocks are no longer cold pool masks; correct the RECC according to the erasure count of the physical block with the smallest erasure count among all current physical blocks value, and re-determine the pool mask of all physical blocks according to the revised RECC.

In addition, the device may further include:

The backup module 606 is connected to the pool maintenance module 601, the EBL module 604, and the GBL module 605 respectively, and is used to save the current erasure times, masks, and current EBL and GBL of all physical blocks to the memory when the memory is unloaded normally backup area.

Preferably, the backup module 606 can be further configured to store the erasure count of each physical block in the physical page of the physical block in real time.

It can be seen from the above-mentioned embodiments that the wear leveling method and device of the present invention divide the physical block into three pools and improve the existing static equalization part, so that the wear leveling method of the present invention only has cold When the physical block of the pool mask is garbage collected, an additional wear is generated, which reduces the additional wear compared with the existing technology.

Claims (26)

1. A wear leveling method, characterized in that the method comprises: Determine the pool mask of each physical block according to the erasure times of each physical block; Wherein, for different erasing times, the pool mask of the physical block is determined as a cold pool mask CPM, a common pool mask NPM or a hot pool mask HPM, specifically including: when the erasing times of the physical block is equal to the value of RECC, determine The pool mask of the physical block is CPM; the pool mask of the physical block is determined to be HPM when the number of erasures is greater than or equal to the value of RECC+TH; the pool mask of the physical block is determined to be NPM when the number of erasures is other values; The RECC is a reference erasure count counter, whose value is equal to the erasure count of the physical block with the smallest erasure count among all physical blocks; the TH is a preset threshold, and its value is a positive integer greater than 1; When the pool mask of a physical block changes from NPM to HPM, copy the data in any physical block whose pool mask is CPM to the physical block whose pool mask is HPM, and set the pool mask Physical blocks for CPM are garbage collected as garbage blocks. the 2. The wear leveling method according to claim 1, characterized in that the method further comprises: Establish a blank block chain list EBL for managing blank blocks, and the blank blocks in the EBL are arranged in ascending order according to their erasure times; When a blank block needs to be allocated for a write request, the first blank block in the EBL is allocated to the write request as a write block. the 3. The wear leveling method according to claim 2, wherein the EBL does not allow a blank block whose pool mask is HPM to enter. the 4. The wear leveling method according to claim 2, characterized in that the method further comprises: A garbage block linked list GBL for managing garbage blocks is established, and the garbage blocks in the GBL are arranged in ascending order of erasure times. the 5. wear leveling method as claimed in claim 4, is characterized in that, described GBL does not allow pool mask to enter for the garbage piece of HPM. the 6. The wear leveling method according to claim 5, wherein when the number of blank blocks in the EBL is less than a preset threshold, the following garbage collection process is performed: If the GBL is non-empty, then erase the data of the first garbage block in the GBL to make it a blank block, and insert the blank block into the EBL; If the GBL is empty, write the effective data of the physical block with the largest amount of garbage data and the least number of erasures among all physical blocks masked as CPM and NPM to the currently allocated write block, and write the garbage data with the largest amount of garbage data. And the physical block with the least erasing times is inserted into the GBL; the data of the first garbage block in the GBL is erased to make it a blank block, and the blank block is inserted into the EBL. the 7. The wear leveling method according to claim 5, wherein the garbage collection comprises: Insert garbage blocks with pool masks CPM and NPM into the GBL. the 8. The wear leveling method according to claim 1, wherein, if the memory is used for the first time, the step of determining the pool mask of each physical block according to the erasure times of each physical block is performed Before, set the current erasure count of all physical blocks to 0; the current pool mask of all physical blocks is CPM. the 9. The wear leveling method according to claim 4, wherein if the memory is not used for the first time and is normally unloaded after the last use, when performing the erasing times according to each physical block, determine Before the step of the pool mask of a physical block, the current erasure times, pool mask, EBL, and GBL of all physical blocks are read from the backup area of the memory. the 10. The wear leveling method according to claim 4, wherein, if the memory is not used for the first time and has not been unloaded normally after the last use, when performing the erasing times according to each physical block, determine Before the step of the pool mask of each physical block, Load the erasure times, pool mask, and EBL, GBL of all physical blocks backed up during the latest normal unloading from the backup area of the memory; Starting from the first physical block in the EBL, check the storage status of the physical blocks in the EBL one by one. If the physical block is not a blank block, delete the physical block from the EBL; the detection continues until the physical block is detected as a blank block or the EBL is empty. so far; Starting from the first physical block in the GBL, check the storage status of the physical blocks in the GBL one by one. If the physical block is already a blank block, delete the physical block from the GBL and insert the physical block into the EBL; the detection continues until the physical block is detected. until the block is a garbage block or the GBL is empty. the 11. The wear leveling method according to claim 1, wherein, if the pool masks of all physical blocks are no longer CPM; then correct according to the number of erasures of the physical block with the smallest number of erasures in all current physical blocks RECC value, and re-determine the pool mask of all physical blocks according to the revised RECC. the 12. The wear leveling method according to claim 4, characterized in that the method further comprises: when the memory is unloaded normally, saving the current erasure times, pool masks, and current EBL and GBL of all physical blocks to the memory backup area. the 13. The wear leveling method according to claim 12, wherein the erasure count of each physical block is also stored in a physical page of the physical block in real time. the 14. A wear leveling device, characterized in that the device comprises: The pool maintenance module is used to determine the pool mask of each physical block according to the number of erasing times of each physical block; wherein, for different times of erasing, the pool mask of the physical block is a cold pool mask CPM, a common pool mask Code NPM or hot pool mask HPM; The pool maintenance module includes: a determination unit, used to determine that the pool mask is CPM when the number of erasing times of the physical block is equal to the value of RECC; the number of times of erasing is greater than or equal to RECC+TH When the value is HPM; when the number of erasures is other values, it is NPM; wherein, the RECC is a reference erasure count counter, and its value is equal to the number of erasures of the physical block with the smallest number of erasures in all physical blocks; the TH is a preset threshold, and its value is a positive integer greater than 1; A static balance module, connected to the pool maintenance module, is used to copy the data in any physical block whose pool mask is CPM to the pool mask when the pool mask of the physical block changes from NPM to HPM On the physical block coded as HPM; The garbage collection module is connected with the static balance module, and is used for performing garbage collection on the physical block whose pool mask is CPM as a garbage block. the 15. The wear leveling device of claim 14, wherein the device further comprises: The EBL module maintains the blank block linked list EBL for managing blank blocks; arranges the blank blocks in the EBL in ascending order according to the number of erasures; when it is necessary to allocate a blank block for a write request, the first blank in the EBL is allocated A block is allocated to the write request as a write block. the 16 . The wear leveling device according to claim 15 , wherein the EBL module does not allow blank blocks whose pool mask is HPM to enter. the 17. The wear leveling device of claim 15, further comprising: The GBL module is connected to the garbage collection module and the EBL module respectively, maintains a garbage block linked list GBL for managing garbage blocks, and arranges the garbage blocks in the GBL in ascending order according to the number of erasures. the 18. The wear leveling device according to claim 17, wherein the GBL module does not allow garbage blocks whose pool mask is HPM to enter. the 19. The wear leveling device according to claim 18, wherein the GBL module is further configured to, when the available space in the memory is less than a preset threshold; If GBL is non-empty, then erase the data of the first garbage block in the GBL to make it a blank block; and insert this blank block into the EBL maintained by the EBL module; If the GBL is empty, first write the valid data in the physical block with the most garbage data and the least number of erasures among the physical blocks whose pool masks are CPM and NPM to the currently allocated write block, and write the garbage Insert the physical block with the most data and the least erasure times into the GBL; then erase the data of the first garbage block in the GBL to make it a blank block; and insert the blank block into the EBL. the 20. The wear leveling device according to claim 17, wherein the garbage collection module is specifically configured to insert the garbage blocks whose pool masks are CPM and NPM into the GBL maintained by the GBL module. the 21. The wear leveling device of claim 14, wherein the pool maintenance module further comprises: The current value determining unit is connected with the determining unit, and is used to set the current erasure times of all physical blocks to 0 when the memory is used for the first time; the current pool mask of all physical blocks is CPM. the 22. The wear leveling device of claim 17, wherein the pool maintenance module further comprises: The current value determination unit is connected with the determination unit, and is used to read the current erasure times and pool mask of all physical blocks from the backup area of the memory when the memory is not used for the first time and is normally unloaded after the last use. Code, and EBL, GBL. the 23. The wear leveling device of claim 17, wherein the pool maintenance module further comprises: The current value determination unit is connected to the determination unit, and is used for when the memory is not used for the first time and has not been unloaded normally after the last use, Load the current erasure count, pool mask, EBL, GBL of all physical blocks backed up during the last normal unload from the backup area of the memory; Described EBL module starts from the first physical block in the EBL, detects the storage situation of the physical block in the EBL one by one, if the physical block is not a blank block, then deletes this physical block from the EBL; detection continues until the physical block is detected as a blank block Or until the EBL is empty; The GBL module starts from the first physical block in the GBL, checks the storage status of the physical blocks in the GBL one by one, if the physical block is already a blank block, deletes the physical block from the GBL, and inserts the physical block into the EBL for maintenance EBL; the detection continues until the physical block is detected as a garbage block or the GBL is empty. the 24. The wear leveling device of claim 14, wherein the pool maintenance module further comprises: The reconstruction unit is connected with the determination unit, and when the pool masks of all physical blocks are no longer CPM; the value of RECC is corrected according to the erasure count of the physical block with the smallest erasure count among all current physical blocks, and according to the correction The post-RECC re-determines the pool mask for all physical blocks. the 25. The wear leveling device of claim 17, further comprising: The backup module is connected to the pool maintenance module, EBL module, and GBL module respectively, and is used to save the current erasure times, masks, and current EBL and GBL of all physical blocks to the backup area of the memory when the memory is unloaded normally. the 26. The wear leveling device according to claim 25, wherein the backup module is further configured to store the erasure count of each physical block in a physical page of the physical block in real time. the

Images