Memory system and a control method thereof

1. Field of the Invention

The present invention relates to a control method for a memory system, in particular, the present invention relates to a control method for the wear-leveling of a memory.

2. Description of the Related Art

Non-volatile memory is used for storing data, such as flash memory. The flash memory is usually used as a storage device, such as memory card, USB interface portable disk, and solid state disk, etc.

Reference is made to FIG. 1 , which shows a schematic diagram of the system structure of the memory system of the prior art. As shown in FIG. 1 , the memory system 13 is coupled with a host 11 so that the data can be accessed between the memory system 13 and the host 11 . The host 11 uses the logical address to represent the storage location of the data, and the memory system 11 uses the physical address to represent the storage location of the data. The memory system 13 includes a storage module 131 and a control module 133 . The storage module 131 is used for storing data. When the host 11 wants to access data in the storage module 131 , the control module 133 converts the logical address from the host 11 into the physical address for the storage module 131 to access data.

Because the ranges of the logical address and the physical address are very large, it is time-consuming to convert the logical address into the corresponding physical address. Therefore, the storage module 131 is divided into a plurality of physical blocks, and the storage space of the host 11 is also divided into a plurality of logical blocks. Each block includes a plurality of addresses. The block is used as a unit to convert the logical address into the physical address to improve the memory management. However, it is still time-consuming to convert the logical address into the corresponding physical address within a large memory space so that segment is developed to overcome the above problem.

In the memory system 13 used the segment as a unit, the storage module 131 is divided into a plurality of physical segments, and the storage space in the host 11 also is divided into a plurality of logical segments. Each of the logical segments respectively corresponds to one physical segment, and each segment includes a plurality of blocks. Reference is made to FIG. 2 , which is a schematic diagram of the segment logical to physical address conversion. As shown in FIG. 2 , after the logical addresses of the storage space in the host 11 is calculated, the addresses is divided into 8000 logical block addresses (LBA). 250 logical block addresses is used as a unit and is defined as a logical segment. Therefore, 32 logical segments LS 0 , LS 1 , . . . , LS 31 are obtained. The storage module 131 in the memory system 13 also is divided into 32 physical segments PS 0 , PS 1 , . . . , PS 31 by the same concept. Each physical segment has 256 continuous physical block addresses (PBA). Wherein, 250 physical blocks correspond to the logical blocks, and 6 physical blocks are used as free blocks for recording control data or replacing the damaged physical blocks.

In the memory system 13 , the free block stores the L2P mapping table that records the mapping relation between the physical blocks in each physical segment and the logical blocks. The logical segment LS 0 records the logical addresses 0 ˜ 63999 that are divided into 250 logical block (LBA 0 ˜ 249 ). The L2P mapping table records the mapping relation between the 250 logical blocks and the 256 physical blocks (PBA=0˜255). By referring to the L2P mapping table, the logical address can be rapidly and exactly mapped to the physical address.

By using the segment concept, the quantity of the memory conversion units is reduced and it does not need to provide a lot of storage space to store the L2P mapping table. However, the erase cycles of the flash memory is limited. The method for using the storage space and the different updating frequency for recording data in the host 11 both will affect the storage space location in the storage module 131 so that the erase cycles for each physical block are different. Moreover, each physical segment includes a fixed range physical blocks and a fixed mapping way. For example, logical blocks LBA=0˜249 in logical segment LS 0 is mapped to the physical blocks PBA=0˜255 in the physical segments PS 0 . Thereby, even through the erase cycles of the physical blocks in a single physical segment can be uniform, a specific physical segment still will be erased too much times and worn due to the fixed range physical segment structure. The usage life of the memory system 13 is shortened.

One particular aspect of the present invention is to provide a control method for memory system that changes the mapping relation between the logical segments and the physical segments according to the wear and loading of the physical segments. Thereby, the problem of the erase cycles of the physical segments being different due to the updating frequency is different is improved.

Another particular aspect of the present invention is to provide a memory system and a control method thereof. When data is allocated to the memory, the wear-leveling is achieved to increase the usage life of the memory system.

The memory system is suitable for a host to access user data. The host has a storage space with a plurality of logical units to store the user data. The memory system includes a storage module and a control module. The storage module includes a storage space with a plurality of physical units, and each physical unit includes a plurality of physical blocks. The storage module reserves at least one physical block to store a master table to record the mapping relation between the addresses of the logical units and the addresses of the physical units. The control unit which is coupled between the host and the storage module adjusts the mapping relation between the addresses of the logical units and the addresses of the physical units according to the erase cycles of the physical units. Thereby, the control module determines the corresponding physical unit of the user data according to the master table when the user accesses the user data.

In one embodiment, the logical unit is a logical segment, and the physical unit is a physical segment. Each physical unit has a segment table to indicate the allocation information of the physical blocks in the physical unit.

The master table records the starting address, the length and the address of the segment table for each physical unit.

The present invention also provides a control method for the memory system that is suitable for a memory system to process the user data transmitted form a host. The control module divides the storage space of the host for accessing the user data into a plurality of logical units. The memory system provides a storage space with a plurality of physical units to store the user data. Each physical unit includes a plurality of physical blocks, and each physical block is composed of a plurality of physical pages. The control method includes the following steps. First, a master table is provided in the physical block for recording the mapping relation between the addresses of the logical units and the addresses of the physical units. When the user data is accessed, the mapping relation between the addresses of the logical units and the addresses of the physical units is adjusted according to the wear of the physical units. Next, the adjusted mapping relation between the addresses of the logical units and the addresses of the physical units is updated in the master table. Finally, according to the master table, the user data is written to the corresponding physical unit.

The present invention can adjust the mapping relation between the logical storage space and the physical storage space to use the physical storage space in cycle and achieve the wear-leveling effect.

For further understanding of the present invention, reference is made to the following detailed description illustrating the embodiments and examples of the present invention. The description is for illustrative purpose only and is not intended to limit the scope of the claim.

The drawings included herein provide a further understanding of the present invention. A brief introduction of the drawings is as follows:

FIG. 1 is a schematic diagram of the system structure of the memory system of the prior art;

FIG. 2 is a schematic diagram of the segment logical to physical address conversion of the prior art;

FIG. 3 is a schematic diagram of the system structure of the memory system of the present invention;

FIG. 4 is a schematic diagram of the storage structure of the logical/physical segments mapping relation of the present invention;

FIG. 5 is a schematic diagram of the master table of the present invention;

FIG. 6 is a schematic diagram of the segment table of the present invention;

FIGS. 7A˜7C are schematic diagrams of the data process procedure of the present invention; and

FIGS. 8 - 1 ˜ 8 - 3 are flow charts of the control method for the memory system of the present invention.

The memory system and the control method thereof of the present invention can adjust the mapping relation between the logical segment and the physical segment. The length and the range of the physical segment can be changed. By writing data orderly and using the physical storage space cyclically, the wear-leveling of the memory is achieved, and the usage life of the memory device is increased.

The present invention provides a control method for the wear-leveling of the memory system and a memory system using the control method. The following merely discloses the main system structure and the operation flow chart. However, in addition to the disclosed elements, the person who skills in the field know the memory system still includes other elements. Therefore, the concept is not limited to the disclosed elements.

Reference is made to FIG. 3 , which shows a schematic diagram of the system structure of the memory system of the present invention. As shown in FIG. 3 , the memory system 33 is coupled with the host 31 , and accepts the instruction from the host 31 to read or write the corresponding user data.

The memory system 33 includes a storage module 331 and a control module 333 . The storage module 331 is composed of flash memory for storing the user data. The control module 333 is coupled between the host 31 and the storage module 333 for receiving an instruction from the host 31 . The instruction is a writing instruction or a reading instruction. The writing instruction is to write user data corresponded to a logical address into the storage module 331 . The reading instruction is to read user data corresponded to a logical address from the storage module 331 .

In one embodiment, the storage module 331 further includes one of non-volatile memories, including ReRAM, MRAM, PRAM.

In order to understand the logical/physical address mapping relation, reference is made to FIG. 4 that is schematic diagram of the storage structure of the logical/physical segments mapping relation of the present invention. As shown in FIG. 4 , the host 31 and the storage module 331 respectively provides a logical storage space 41 and a physical storage space 43 for the user data. The logical storage space 41 is divided into 32 logical segments LS 0 ˜LS 31 . The physical storage space 43 also is divided into 32 physical segments PS 0 ˜PS 31 to correspond to the logical segments LS 0 ˜LS 31 . In one embodiment, each logical segment LS i is composed of 250 logical blocks, and each physical segment PS i is composed of 256 physical blocks. Wherein, 250 physical blocks are used for corresponding to the logical blocks, and 6 physical blocks are free blocks.

The storage module 331 reserves at least two physical blocks to store a boot file 431 and a master table 433 . The boot file 431 records the required information to boot up the memory system 33 , such as firmware image, vendor information, etc. The master table 433 records the mapping relation between logical segment LS i and the physical segment PS i . Reference is also made to FIG. 5 , which is a schematic diagram of the master table of the present invention.

As shown in FIG. 5 , the storage module 331 reserves two physical blocks PBA 1 , PBA 2 to store the master table 433 . The master table 433 includes a physical segment field 51 , a logical segment field 52 , a start block field 53 , a length field 54 , a segment table offset field 55 , and information, including wear rate 56 and relative segment 57 . The physical segment field 51 and logical segment field 52 indicate the mapping relationship for each segment. In one embodiment, the physical segment PS i is mapped to the logical segment LS i , and i=j.

The start block field 53 and the length field 54 respectively indicate the start block address and the segment length for each physical segment PS i . The start block address and the segment length can be changed according to the data process situation of the physical storage space 43 so that each physical segment PS i has adequate free blocks. For example, physical storage space 43 has 8192 physical blocks PBA i . Three physical blocks PBA 0 , PBA 1 , PBA 2 are used for storing the boot file 431 and the master table 433 , and the physical segment PS 0 has three bad physical blocks. Therefore, after the other physical blocks PBA i are averagely divided into 32 physical segments, each physical segment PS i has 255 or 256 physical blocks PBA i . Because the physical blocks PBA 0 , PBA i , PBA 2 are reserved, the start block of the physical segment PS 0 is PBA 3 . In order to reserve 6 free blocks, three physical blocks PBA i are added to the physical segment PS 0 . Therefore, the range of the physical segment PS 0 is from PBA 3 to PBA 261 . By using the same way, the physical blocks for PS i are determined.

The physical segment PS 0 still has 256 physical blocks PBA i to be mapped with the 250 logical blocks in logical segment LS 0 , and has 6 free blocks.

Each physical segment PS i has a segment table for indicating the physical blocks PBA i included in the physical segment PS i , and the mapping relation with the logical blocks and the allocation information. The content in the segment table offset field 55 is used for indicating the physical block address for each segment table.

The wear rate field 56 is used for recording the wear of the physical segment PS i . The control module 333 adjusts the mapping relation between the physical segment PS i and the logical segment LS i according to wear of the physical segment PS i , and records the adjusted information in the relative segment field 57 .

In one embodiment, the storage module 331 reserves two physical blocks PBA 1 , PBA 2 to store the master table 433 , and physical block is divided into 64 physical pages Page 0 ˜Page 63 . Initially, the master table 433 is stored in the physical page Page 0 of the physical block PBA 1 , and uses the physical page Page i as a unit. When the content of the master table 433 is updated, the updated master table 433 is orderly stored in the physical page Page 1 until physical page Page 63 . Next, the updated master table 433 is stored in physical page Page 0 of the physical block PBA 2 , and erases the physical block PBA 1 . When the updated master table 433 is stored in physical page Page 63 of the physical block PBA 2 , the next updated master table 433 is stored in physical block PBA 1 . By repeating the above steps, the content of the master table 433 is maintained by using the cycle storage algorithm.

Reference is made to FIG. 6 , which is a schematic diagram of the segment table of the present invention. The system structure is referred to FIGS. 3˜5 . As shown in FIG. 6 , the segment table 6 includes an identification field 61 , a plurality of allocation information fields E 0 ˜E 249 , a head pointer register 63 , and a tail pointer register 65 . The identification field 61 is used for checking whether the data structure is the content of the segment table 6 . The allocation information fields E i is the mapping information between the logical blocks and the physical blocks, and includes an allocated flag field 62 , an alternate segment flag field 64 , and a PBA offset field 66 .

The allocated flag field 62 is used for indicating whether the physical block is allocated to access the user data or not. When the content of the allocated flag field 62 is set to 1, it means that the physical block is allocated. The alternate segment flag field 64 is used for indicating whether the mapping relation between the logical block and the physical block is adjusted or not. When the content of the alternate segment flag field 64 is set to 1, it means that the physical block is switched with another physical block. When the content of the alternate segment flag field 64 is set to 0, it means that the physical block is not switched with another physical block. The PBA offset field 66 is used for indicating the physical block address, and is the offset address from the start physical block of the physical segment For example, when the user data on the logical block of the logical segment LS 0 will be written to the physical block of the physical segment PS 0 , the information on the allocation information field E 0 is checked. When the allocated flag field 62 is 1, the alternate segment flag field 64 is 0 and the PBA offset field 66 is 1, the user data will be written to the physical block with offset 1 from the start block of the physical segment PS 0 , PBA 3 +1=PBA 4 . When the allocated flag field 62 is 1, the alternate segment flag field 64 is 1 and the PBA offset field 66 is 1, the relative segment field of the master table 433 is checked. If the relative segment of the physical segment PS 0 is physical segment PS 31 and the start physical block of the physical segment PS 31 is physical block PBA 7937 , the user data will be written to the physical block with offset 1 from the start block of the physical segment PS 31 , PBA 7937 +1=PBA 7938 .

The head pointer register 63 and the tail pointer register 65 are used for bounding a range of the valid physical blocks in the physical segment for accessing the user data in the physical blocks.

In order to illustrate the process of the access of the user data for the storage module 331 , reference is made to FIGS. 7A˜7C , which are the schematic diagrams of the data process procedure of the present invention. In the physical blocks provided by the storage module 331 , the address stored in the head pointer register 63 is pointed to the valid physical block for the user data, and the address on the tail pointer register 65 is the last physical block that has been stored with the user data. The range between the head pointer register 63 and the tail pointer register 65 is the physical blocks that are allocated and have the valid user data in the segment. The storage module 331 can be treated as a cycle storage space. The new user data is written to the physical block indicated by the head pointer register 63 , and the physical block indicated by the tail pointer register 65 is adjusted according to the situation. When the user data is written to one end of the physical segment, the content of the register is set to indicate to another end of the physical block. Thereby, the physical blocks can be cyclically and orderly allocated to achieve the wear-leveling effect.

As shown in FIG. 7A , the storage module 331 includes a plurality of physical blocks PBA i , and defines a threshold value to limit the quantity of the allocation physical blocks. For example, maximum 7 physical blocks can be used for storing the user data. The user data A˜G is written into the physical blocks PBA 0 ˜PBA 6 . Wherein, the physical block PBA 4 stored the data E was erased previously. The data A in the physical block PBA 0 is the oldest data, and the data G in the physical block PBA 6 is the newest data. At this time, the tail pointer register 65 indicates to the physical block PBA 0 , and the head pointer register 63 indicates to the physical block PBA 6 to represent that the physical blocks PBA 0 ˜PBA 6 are the range of the allocation physical blocks.

As shown in FIG. 7B , when a user data B′ is written, the head pointer register 63 is pointed to the physical block PBA 7 to allocate the user data B′, and erases the physical block PBA 1 . However, the range of the allocation physical block is PBA 0 ˜PBA 7 , and the blocks will surpass the threshold value. In order to control the quantity of the free blocks, the block-recycling procedure is performed.

As shown in FIG. 7C , the block-recycling procedure determines whether the data A stored in the physical block PBA 0 indicated by the tail pointer register 65 is erased or not. Because the data A is not erased and valid, the data A will be stored in the available physical block that is nearest the physical block indicated by the head pointer register 63 . Wherein the nearest physical block is between the physical block indicated by the head pointer register 63 and the physical block indicated by the tail pointer register 65 . That means that the data A is allocated to the PBA 4 . Next, the data A in the physical block PBA 0 indicated by the tail pointer register 65 is erased, and the tail pointer register 65 is indicated to the physical block PBA 1 . On the other side, when the data stored in the physical block indicated by the tail pointer register 65 is erased, the tail pointer register 65 is indicated to the next available physical block. That means that the physical block PBA 1 indicated by the tail pointer register 65 is erased, and the tail pointer register 65 is indicated to the physical block PBA 2 . By using the same procedures, the data is cyclically allocated.

The threshold value is a user setting value, or is determined by the quantity of the free physical blocks reserved by the memory system 33 . For example, when 6 physical blocks of 256 physical blocks are reserved as the free physical block, the threshold value is set to 250. When the range of the valid physical blocks surpasses 250 physical blocks, the block-recycling procedure is performed.

In one embodiment, the segment table 6 is stored in one physical block for each physical segment. Similar to the updating procedure of the master table 433 , the segment table 6 uses the physical page as a unit to be written in the physical block. When the physical block is full, one available physical block of the physical segment is found to write the segment table 6 , and the original physical block is erased. In other words, the content of the segment table 6 can be treated as user data, and is cyclically allocated in the physical storage space 43 with the other user data.

Finally, reference is made to FIGS. 8 - 1 ˜ 8 - 3 , which are the flow chart of the control method of the memory system. The system structure and the table are also referred to FIGS. 3˜7 . As shown in FIG. 8 - 1 ˜ 8 - 3 , the control method includes the following steps.

Firstly, the master table 433 is provided into the physical block (step S 101 ). A logical address of storing user data is transferred into a logical segment (represented by LS i , step S 102 ). Next, the control module 333 finds a physical segment (represented by PS i ) corresponded by the logical segment LS i from the master table, and finds the physical block address stored by the segment table 6 of the physical segment PS i from the segment table offset field 55 (S 103 ). The information for allocating the physical block is found from the segment table 6 (S 105 ). During accessing the user data, the mapping relation between the logical segment LS i and the physical block is adjusted according to the wear rate of the physical segment PS i (step S 106 ).

The value of the relative segment field 57 is checked to determine whether the physical segment PS i is relative to other physical block or not (step S 107 ). If no, the allocated flag field 62 is checked to determine whether the physical segment PS i is allocated with physical blocks to access the user data (step S 109 ). If no physical blocks are allocated, a non-allocation process procedure is performed (step S 111 ). In one embodiment, the non-allocation process procedure is implemented by the control module 333 to response a default value (such as 0xFF) to represent no storage space being allocated.

If the result of step S 109 is yes, a data process procedure is perform that make the head pointer register 63 of the physical segment PS i indicate to next physical block (step S 113 ). The user data is stored into the physical block indicated by the head pointer register 63 (step S 115 ). Next, the changed parameter from the above procedure (such as the value of the head pointer register 63 ) is used for updating the content of the segment table 6 and the master table 433 (step S 117 ). Finally, whether the range of the allocation physical blocks in the physical segment PS i surpasses a threshold value is determined (step S 119 ). If no, the step S 102 is executed to access the next user data. If the result of step S 119 is yes, a block-recycling procedure is executed (step S 120 ).

After the value of the relative segment field 57 is checked in step S 107 and the physical segment PS i is relative to another physical block (represented by PS j , i≠j), the allocated flag field 62 of the segment table of the physical segment PS j is checked to determine whether the physical segment PS j is allocated with physical blocks to access the user data (step S 121 ). If no physical blocks are allocated, a non-allocation process procedure is performed (step S 123 ). In one embodiment, the non-allocation process procedure is implemented by the control module 333 to response a default value to represent no storage space being allocated.

If the result of step S 121 is yes, a data process procedure is perform that make the head pointer register 63 of the physical segment PS j indicate to next physical block (step S 125 ). The user data is stored into the physical block indicated by the head pointer register 63 (step S 127 ). Next, the changed parameter from the above procedure (such as the value of the head pointer register 63 ) is used for updating the content of the segment table 6 and the master table 433 (step S 129 ). Finally, whether the range of the allocation physical blocks in the physical segment PS j surpasses a threshold value is determined (step S 141 ). If no, the step S 102 is executed to access the next user data. If the result of step S 141 is yes, a block-recycling procedure is executed (step S 120 ).

The block-recycling procedures for the physical segment is relative or is not relative to another physical segment are different. After the block-recycling procedure is executed (step S 120 ), whether the processed physical segment PS i is relative to another physical segment is firstly determined (step S 201 ). Because the step S 107 has the same procedure, the step S 201 can be omitted. If the physical segment PS i is not relative to another physical segment, whether the tail pointer register 65 of the physical segment PS i is stored with valid data or not is determined (step S 203 ). If no, it means that the physical block is erased. The tail pointer register 65 is indicated to next physical block (step S 205 ), and the changed parameter from the above procedures (such as the value of the tail pointer register 65 ) is used for updating the content of the segment table 6 and the master table 433 (step S 215 ).

If the result of the step S 203 is yes, find the erased physical block which is the nearest physical block from the physical block indicated by the head pointer register 63 , wherein the nearest physical block is between the physical block indicated by the head pointer register 63 and the physical block indicated by the tail pointer register 65 (step S 207 ), and the valid data stored in the physical block indicated by the tail pointer register 65 is written (step S 209 ). Then, the physical block indicated by the tail pointer register 65 is erased (step S 211 ), and the tail pointer register 65 is indicated to next physical block (step S 213 ). Finally, the changed parameter from the above procedures is used for updating the content of the segment table 6 and the master table 433 (step S 215 ).

However, when the physical segment PS i is relative to physical segment PS j (the result of the step S 201 is yes), whether the physical block indicated by the tail pointer register 65 of the physical segment PS j is stored with valid data or not is determined (S 217 ). If no, it means that the physical block has been erased. The tail pointer register 65 is indicated to next physical block (step S 219 ), and the changed parameter from the above procedures is used for updating the master table 433 , the segment table 6 of physical segment PS i and the segment table 6 of the physical segment PS j (step S 215 ).

If the result of the step S 217 is yes, find the erased physical block which is the nearest physical block from the physical block indicated by the head pointer register 63 , wherein the nearest physical block is between the physical block indicated by the head pointer register 63 and the physical block indicated by the tail pointer register 65 (step S 221 ), and the valid data stored in the physical block indicated by the tail pointer register 65 is written (step S 223 ). Then, the physical block indicated by the tail pointer register 65 is erased (step S 225 ), and the tail pointer register 65 is indicated to next physical block (step S 227 ). Finally, the changed parameter from the above procedures is used for updating the content of the segment table 6 and the master table 433 (step S 229 ).

Thereby, part of the user data in the logical segment LS i can be accessed in the physical segment PS i and part of the user data in the logical segment LS i can be accessed in the physical segment PS j , and the master table 433 and the segment table 6 are used for recording the exact location for the user data. Therefore, the logical segment LS i that originally is mapped to the physical segment PS i can be adjusted to the physical segment PS j that its access frequency is less to achieve the wear-leveling effect.

The memory system and the control method thereof of the present invention utilizes the master table to record the mapping relation between the logical segment and the physical segment, and provides the data process method to control the user data to be accessed in different physical blocks. The present invention has the following characteristics.

1. The range and the length of the physical segment can be changed according the usage status of the physical storage space, and the mapping relation between the physical segment and the logical segment can be adjusted according to the wear rate of the physical segment to average the usage of physical segment.

2. The segment table is used for recording the allocation for each physical segment, and the head pointer register and the tail pointer register are utilized so that the user data can be orderly and cyclically accessed in any physical segment and the wear rate for each physical block in the physical segment is the same.

3. The static old data can be moved to another physical block by the block-recycling procedure so that the physical block stored with the static old data can be released to access the other user data.

4. By utilizing the data structure of the segment table, the head pointer register always is indicated to the last user data, and the tail pointer register always is indicated to the oldest user data. Even though the least recently used (LRU) or the least frequently used (LFU) algorithm is not adapted, the data can be effectively processed.

The description above only illustrates specific embodiments and examples of the present invention. The present invention should therefore cover various modifications and variations made to the herein-described structure and operations of the present invention, provided they fall within the scope of the present invention as defined in the following appended claims.