METHOD FOR MANAGING THE COPYING AND STORING OF DATA IN GARBAGE COLLECTION, MEMORY STORAGE DEVICE AND MEMORY CONTROL CIRCUIT UNIT USING THE SAME

A memory management method, a memory storage device and a memory control circuit unit are provided. The method includes: receiving a first write command from a host system and writing a first data indicated by the first write command to a physical erasing unit which is currently served as a receiving physical erasing unit; and copying valid data from a first physical erasing unit and writing the valid data to a physical erasing unit which is currently served as a recycling physical erasing unit in a garbage collection operation, where the physical erasing unit currently served as the receiving physical erasing unit and the physical erasing unit currently served as the recycling physical erasing unit are two physical erasing units independent from each other.

BACKGROUND

Technology Field

The invention relates to a memory management mechanism, and more particularly, to a memory management method, a memory storage device and a memory control circuit unit for a rewritable non-volatile memory module.

Description of Related Art

The markets of digital cameras, cellular phones, and MP3 players have expanded rapidly in recent years, resulting in escalated demand for storage media by consumers. The characteristics of data non-volatility, low power consumption, and compact size make a rewritable non-volatile memory module (e.g., flash memory) ideal to be built in the portable multi-media devices as cited above.

Generally, after the rewritable non-volatile memory module is used for a period of time, the rewritable non-volatile memory module may automatically execute a garbage collection procedure to release memory spaces occupied by invalid data. However, the garbage collection procedure may result in confusion between old valid data being collected and newly written data, so as lower a data writing efficiency of the rewritable non-volatile memory module in executing a sequential write afterward.

SUMMARY

The invention is directed to a memory management method, a memory storage device and memory control circuit unit, capable of effectively solving the problem in which the data writing efficiency of the rewritable non-volatile memory module is lowered after being used for a long period of time.

The invention provides a memory management method for a rewritable non-volatile memory module having a plurality of physical erasing units, and the memory management method comprising: receiving a first write command from a host system and writing a first data indicated by the first write command to a physical erasing unit which is currently served as a receiving physical erasing unit among the physical erasing units; and copying valid data from a first physical erasing unit among the physical erasing units and writing the valid data to a physical erasing unit which is currently served as a recycling physical erasing unit among the physical erasing units in a garbage collection operation, wherein the physical erasing unit currently served as the receiving physical erasing unit and the physical erasing unit currently served as the recycling physical erasing unit are two physical erasing units independent from each other.

The invention also provides a memory storage device which comprises a connection interface unit, a rewritable non-volatile memory module and a memory control circuit unit. The connection interface unit is configured to couple to a host system. The rewritable non-volatile memory module comprises a plurality of physical erasing units. The memory control circuit unit is coupled to the connection interface unit and the rewritable non-volatile memory module, wherein the memory control circuit unit is configured to receive a first write command from the host system and issue a first write command sequence instructing to write a first data indicated by the first write command to a physical erasing unit which is currently served as a receiving physical erasing unit among the physical erasing units, wherein the memory control circuit unit is further configured to copy valid data from a first physical erasing unit among the physical erasing units and issue a second write command sequence instructing to writing the valid data to a physical erasing unit which is currently served as a recycling physical erasing unit among the physical erasing units in a garbage collection operation, wherein the physical erasing unit currently served as the receiving physical erasing unit and the physical erasing unit currently served as the recycling physical erasing unit are two physical erasing units independent from each other.

The invention also provides a memory control circuit unit configured to control a rewritable non-volatile memory module. The rewritable non-volatile memory module comprises a plurality of physical erasing units, and the memory control circuit unit comprises a host interface, a memory interface and a memory management circuit. The host interface is configured to couple to a host system. The memory interface is configured to couple to the rewritable non-volatile memory module. The memory management circuit is coupled to the host interface and the memory interface, wherein the memory management circuit is configured to receive a first write command from the host system and issue a first write command sequence instructing to write a first data indicated by the first write command to a physical erasing unit which is currently served as a receiving physical erasing unit among the physical erasing units, wherein the memory management circuit is further configured to copy valid data from a first physical erasing unit among the physical erasing units and issue a second write command sequence instructing to writing the valid data to a physical erasing unit which is currently served as a recycling physical erasing unit among the physical erasing units in a garbage collection operation, wherein the physical erasing unit currently served as the receiving physical erasing unit and the physical erasing unit currently served as the recycling physical erasing unit are two physical erasing units independent from each other.

Based on above, the invention is capable of writing the data from the host system into the receiving physical erasing unit, and writing the valid data collected from part of physical erasing units in the rewritable non-volatile memory module into the recycling physical erasing unit. Accordingly, the old valid data in the rewritable non-volatile memory module and the new data will not be stored in the same physical erasing unit, so as to effectively solve the problem in which the data writing efficiency of the rewritable non-volatile memory module is lowered after being used for a long period of time.

DESCRIPTION OF THE EMBODIMENTS

Generally, a memory storage device (also known as a memory storage system) includes a rewritable non-volatile memory module and a controller (also known as a control circuit). The memory storage device is usually configured together with a host system so that the host system may write data into or read data from the memory storage device.

FIG. 1Aillustrates a host system and a memory storage device according to an exemplary embodiment of the invention.FIG. 1Bis a schematic diagram of a computer, an input/output device, and a memory storage device according to an exemplary embodiment of the invention.FIG. 1Cis a schematic diagram of a host system and a memory storage device according to an exemplary embodiment of the invention.

Referring toFIG. 1A, a host system1000includes a computer1100and an input/output (I/O) device1106. The computer1100includes a microprocessor1102, a random access memory (RAM)1104, a system bus1108, and a data transmission interface1110. The I/O device1106includes a mouse1202, a keyboard1204, a display1206and a printer1208as shown inFIG. 1B. It should be understood that the devices illustrated inFIG. 2are not intended to limit the I/O device1106, and the I/O device1106may further include other devices.

In the present embodiment of the invention, the memory storage device100is coupled to other devices of the host system1000through the data transmission interface1110. By using the microprocessor1102, the random access memory1104and the Input/Output (I/O) device1106, data may be written into the memory storage device100or may be read from the memory storage device100. For example, the memory storage device100may be a rewritable non-volatile memory storage device such as a flash drive1212, a memory card1214, or a solid state drive (SSD)1216as shown inFIG. 2.

Generally, the host system1000may substantially be any system capable of storing data with the memory storage device100. Although the host system1000is described as a computer system in the present exemplary embodiment, in another exemplary embodiment of the invention, the host system1000may be a digital camera, a video camera, a telecommunication device, an audio player, or a video player. For example, if the host system is a digital camera (video camera)1310, the rewritable non-volatile memory storage device may be a SD card1312, a MMC card1314, a memory stick1316, a CF card1318or an embedded storage device1320(as shown inFIG. 1C). The embedded storage device1320includes an embedded MMC (eMMC). It should be mentioned that the eMMC is directly coupled to a substrate of the host system.

FIG. 2is a schematic block diagram illustrating the memory storage device depicted inFIG. 1A.

Referring toFIG. 2, the memory storage device100includes a connection interface unit102, a memory control circuit unit104and a rewritable non-volatile memory storage module106.

In the present exemplary embodiment, the connection interface unit102is compatible with a serial advanced technology attachment (SATA) standard. However, the invention is not limited thereto, and the connection interface unit102may also be compatible to Parallel Advanced Technology Attachment (PATA) standard, Institute of Electrical and Electronic Engineers (IEEE) 1394 standard, Peripheral Component Interconnect (PCI) Express interface standard, Universal Serial Bus (USB) standard, Ultra High Speed-I (UHS-I) interface standard, Ultra High Speed-II (UHS-II) interface standard, Secure Digital (SD) interface standard, Memory Stick (MS) interface standard, Multi Media Card (MMC) interface standard, Compact Flash (CF) interface standard, Integrated Device Electronics (IDE) interface standard or other suitable standards. In the present exemplary embodiment, the connection interface unit and the memory control circuit unit may be packaged into one chip, or distributed outside of a chip containing the memory control circuit unit.

The memory control circuit unit104is configured to execute a plurality of logic gates or control commands which are implemented in a hardware form or in a firmware form, so as to perform operations of writing, reading or erasing data in the rewritable non-volatile memory storage module106according to the commands of the host system1000.

The rewritable non-volatile memory storage module106is coupled to the memory control circuit unit104and configured to store data written from the host system1000. The rewritable non-volatile memory storage module106has multiple physical erasing units304(0) to304(R). For example, the physical erasing units304(0) to304(R) may belong to the same memory die or belong to different memory dies. Each physical erasing unit has a plurality of physical programming units, and the physical programming units of the same physical erasing unit may be written separately and erased simultaneously. For example, each physical erasing unit is composed by 128 physical programming units. Nevertheless, it should be understood that the invention is not limited thereto. Each physical erasing unit is composed by 64 physical programming units, 256 physical programming units or any amount of the physical programming units.

More specifically, each of the physical programming units includes a plurality of word lines and a plurality of bit lines, and a memory cell is disposed at an intersection of each of the word lines and each of the data lines. Each memory cell can store one or more bits. All of the memory cells in the same physical erasing unit are erased together. In the present exemplary embodiment, the physical erasing unit is a minimum unit for erasing. Namely, each physical erasing unit contains the least number of memory cells to be erased together. For instance, the physical erasing unit is a physical block. Furthermore, the memory cells on the same word line can be grouped into one or more of the physical programming units. In case each of the memory cells may store two or more bits, the physical programming units on the same word line may be classified into a lower physical programming unit and an upper physical programming unit. Generally, a writing speed of the lower physical programming unit is faster than a writing speed of the upper physical programming unit. In the present exemplary embodiment, the physical programming unit is a minimum unit for programming. That is, the physical programming unit is the minimum unit for writing data. For example, the physical programming unit is a physical page or a physical sector. In case the physical programming unit is the physical page, each physical programming unit usually includes a data bit area and a redundancy bit area. The data bit area has multiple physical sectors configured to store user data, and the redundant bit area is configured to store system data (e.g., an error correcting code). In the present exemplary embodiment, each of the data bit areas contains 32 physical sectors, and a size of each physical sector is 512-byte (B). However, in other exemplary embodiments, the data bit area may also include 8, 16, or more or less of the physical sectors, and amount and sizes of the physical sectors are not limited in the invention.

In the present exemplary embodiment, a rewritable non-volatile memory module106is a Multi Level Cell (MLC) NAND flash memory module which stores at least 2 bits in one cell. The rewritable non-volatile memory module106may also be a Single Level Cell (SLC) NAND flash memory module, a Trinary Level Cell (TLC) NAND flash memory module, other flash memory modules or any memory module having the same features.

FIG. 3is a schematic block diagram illustrating a memory control circuit unit according to an exemplary embodiment.

Referring toFIG. 3, the memory control circuit unit104includes a memory management circuit202, a host interface204and a memory interface206.

The memory management circuit202is configured to control overall operations of the memory control circuit unit104. Specifically, the memory management circuit202has a plurality of control commands. When the memory storage device100operates, the control commands are executed to perform various operations such as data writing, data reading and data erasing. Operations of the memory management circuit202are similar to the operations of the memory control circuit unit104, thus related description is omitted hereinafter.

In the present exemplary embodiment, the control commands of the memory management circuit202are implemented in a form of a firmware. For instance, the memory management circuit202has a microprocessor unit (not illustrated) and a ROM (not illustrated), and the control commands are burned into the ROM. When the memory storage device100operates, the control commands are executed by the microprocessor to perform operations of writing, reading or erasing data.

In another exemplary embodiment of the invention, the control commands of the memory management circuit202may also be stored as program codes in a specific area (for example, the system area in a memory exclusively used for storing system data) of the rewritable non-volatile memory module106. In addition, the memory management circuit202has a microprocessor unit (not illustrated), a ROM (not illustrated) and a RAM (not illustrated). More particularly, the ROM has a boot code, which is executed by the microprocessor unit to load the control commands stored in the rewritable non-volatile memory module106to the RAM of the memory management circuit202when the memory control circuit unit104is enabled. Next, the control commands are executed by the microprocessor unit to perform operations of writing, reading or erasing data.

Further, in another exemplary embodiment of the invention, the control commands of the memory management circuit202may also be implemented in a form of hardware. For example, the memory management circuit220includes a microcontroller, a memory management unit, a memory writing unit, a memory reading unit, a memory erasing unit and a data processing unit. The memory management unit, the memory writing unit, the memory reading unit, the memory erasing unit and the data processing unit are coupled to the microprocessor. The memory management unit is configured to manage the physical erasing units of the rewritable non-volatile memory module106; the memory writing unit is configured to issue a write command to the rewritable non-volatile memory module106in order to write data to the rewritable non-volatile memory module; the memory reading unit is configured to issue a read command to the rewritable non-volatile memory module106in order to read data from the rewritable non-volatile memory module106; the memory erasing unit is configured to issue an erase command to the rewritable non-volatile memory module106in order to erase data from the rewritable non-volatile memory module106; the data processing unit is configured to process both the data to be written to the rewritable non-volatile memory module106and the data to be read from the rewritable non-volatile memory module106.

The host interface204is coupled to the memory management circuit202and configured to receive and identify commands and data sent from the host system1000. Namely, the commands and data sent from the host system1000are passed to the memory management circuit202through the host interface204. In the present exemplary embodiment, the host interface204is compatible to a SATA standard. However, it should be understood that the present invention is not limited thereto, and the host interface204may also be compatible with a PATA standard, an IEEE 1394 standard, a PCI Express standard, a USB standard, a SD standard, a UHS-I standard, a UHS-II standard, a MS standard, a MMC standard, a eMMC standard, a UFS standard, a CF standard, an IDE standard, or other suitable standards for data transmission.

The memory interface206is coupled to the memory management circuit202and configured to access the rewritable non-volatile memory module106. That is, data to be written to the rewritable non-volatile memory module106is converted to a format acceptable to the rewritable non-volatile memory module106through the memory interface206.

In an exemplary embodiment of the invention, the memory control circuit unit104further includes a buffer memory252, a power management circuit254and an error checking and correcting circuit256.

The buffer memory252is coupled to the memory management circuit202and configured to temporarily store data and commands from the host system1000or data from the rewritable non-volatile memory module106.

The power management unit254is coupled to the memory management circuit202and configured to control a power of the memory storage device100.

The error checking and correcting circuit256is coupled to the memory management circuit202and configured to perform an error checking and correcting process to ensure the correctness of data. Specifically, when the memory management circuit202receives a write command from the host system1000, the error checking and correcting circuit256generates an error correcting code (ECC code) for data corresponding to the write command, and the memory management circuit202writes data and the ECC code corresponding to the write command to the rewritable non-volatile memory module106. Subsequently, when the memory management circuit202reads the data from the rewritable non-volatile memory module106, the ECC code corresponding to the data is also read, and the error checking and correcting circuit256may execute the error checking and correcting procedure for the read data according to the ECC code.

FIG. 4is a schematic diagram illustrating an example for a management under a memory storage device according to an exemplary embodiment.

It should be understood that terms, such as “select”, “group”, “divide”, “associate” and so forth, are logical concepts which describe operations in the physical erasing units of the rewritable non-volatile memory module106. That is, the physical erasing units of the rewritable non-volatile memory module are logically operated, but actual positions of the physical units of the rewritable non-volatile memory module are not changed.

Referring toFIG. 4, the memory management circuit202may logically divide the physical erasing units304(0) to304(R) of the rewritable non-volatile memory module106into a plurality of areas such as a storage area402and a system area406.

The physical erasing units in the storage area402are configured to store data from the host system1000. The storage area402stores valid data and invalid data. For example, when the host system intends to delete one valid data, the data being deleted may still be stored in the storage area402but marked as the invalid data. The physical erasing unit not storing the valid data may also be referred to as a spare physical erasing unit. The physical programming unit not storing the valid data may also be referred to as a spare physical programming unit. For example, the physical erasing unit being erased may become the spare physical erasing unit. In case there are damaged physical erasing units in the storage area402or the system area406, the physical erasing units in the storage area402may also be used to replace the damaged physical erasing units. If there are no available physical erase units in the storage area402for replacing the damaged physical erasing units, the memory storage device100is announced by the memory management circuit202as being in a write protect status, and data cannot be written therein.

The physical erasing units in the system area406are configured to record system information including information related to manufacturer and model of a memory chip, a number of physical erasing units in the memory chip, a number of the physical programming unit in each physical erasing unit, and so forth.

Amounts of the physical erasing units in the storage area402and the system area406may be different to each other based on the different memory specifications. In addition, it should be understood that, during operations of the memory storage device100, grouping relations of the physical erasing units associated to the storage area402and the system area406may be dynamically changed. For example, when damaged physical erasing units in the system area406are replaced by the physical erasing units in the storage area402, the physical erasing units originally from the storage area402are then associated to the system area406.

The memory management circuit202may also be configured with logical addresses410(0) to410(D) for mapping to part of the physical erasing units304(0) to304(A) in the storage area402. The host system1000may access the data in the storage area402through the logical addresses410(0) to410(D). In the present exemplary embodiment, one logical address is mapped to one physical sector, a logical programming unit is constituted by multiple logical addresses, and a logical erasing unit is constituted by multiple logical programming units. One logical programming unit is mapped to one or more physical programming units, and one logical erasing unit is mapped to one or more physical erasing units. In the present exemplary embodiment, the memory management circuit202uses the logical programming units to manage the corresponding physical erasing unit. Further, the memory management circuit202establishes a logical address-physical erasing unit mapping table to record a mapping relation between the logical addresses and the physical erasing units. The logical address-physical erasing unit mapping table may also record, for example, various corresponding relation between logical and physical entities, such as a mapping relation between the logical addresses and the physical programming units, a mapping relation between the logical programming units and the physical programming units and/or a mapping relation between the logical programming units and the physical erasing units, which are not particularly limited by the invention.

The memory management circuit202may select one or more physical erasing units from the spare physical erasing units in the storage area402to be used (i.e., served) as a receiving physical erasing unit. The memory management circuit202may select one or more physical erasing units from the spare physical erasing units in the storage area402to be used (i.e., served) as a recycling physical erasing unit. For example, the memory management circuit202may number the physical erasing unit currently served as the receiving physical erasing unit (also referred to as a first spare physical erasing unit) and the physical erasing unit currently served as the recycling physical erasing unit (also referred to as a second spare physical erasing unit), and identify the first spare physical erasing unit currently used as the receiving physical erasing unit and the second spare physical erasing unit currently used as the recycling physical erasing unit by way of utilizing a look up table. The physical erasing unit used as the receiving physical erasing unit is only used for writing the data from the host system100, whereas the physical erasing unit used as the recycling physical erasing unit is only used for writing the valid data from part of the physical erasing units in the storage area402in a garbage collection procedure. Further, in an exemplary embodiment, none of the physical erasing units will be used as the receiving physical erasing unit and the recycling physical erasing unit at the same time.

The memory management circuit202may receive a first write command from the host system1000. The first write command instructs to write a first data into at least one first logical address among the logical addresses410(0) to410(D). The memory management circuit202may write the first data into the receiving physical erasing unit. For example, it is assumed that the physical erasing unit currently used as the receiving physical erasing unit is the first spare physical erasing unit, thus the memory management circuit202may write the first data into the first spare physical erasing unit.

The memory management circuit202may select one or more physical erasing units (also referred to as first physical erasing unit) from the physical erasing units in the storage area402. The first physical erasing unit mentioned herein stores a plurality of data in which at least two data belong to different logical erasing units. At a specific time point, the memory management circuit202may execute a garbage collection procedure to copy the valid data from the data stored in the first physical erasing unit, and write the copied valid data into the recycling physical erasing unit (e.g., the second spare physical erasing unit). The specific time point as mentioned herein may be, for example, times when a quantity of the spare physical erasing units in the storage area402reaches a quantity threshold. The quantity threshold may be, for example, 1, 2 or more. For examples, each time the memory management circuit202selects one of the spare physical erasing units from the storage area402to be used as the receiving physical erasing unit or the recycling physical erasing unit, the memory management circuit202may determine whether the quantity of remaining spare physical erasing units reaches the quantity threshold. Once the quantity of the remaining physical erasing units reaches the quantity threshold, the memory management circuit202may then execute the garbage collection procedure. Further, the memory management circuit202may also execute the garbage collection procedure after idle for a preset time period (e.g., when none of write commands is received from the host system1000within the preset time period) or at any time points. Moreover, the memory management circuit202may also execute the garbage collection procedure each time the data is written into the receiving physical erasing unit. In other words, the memory management circuit202is capable of executing part of the garbage collection procedure for the first physical erasing unit, and when the physical erasing unit currently used as the receiving physical erasing units is fully written, the memory management circuit202may synchronously release at least one spare physical erasing unit, so as to ensure that the spare physical erasing units in the storage area402are maintained at a preset amount.

It should be noted that, the physical erasing unit used as the receiving physical erasing unit and the physical erasing unit used as the recycling physical erasing unit are not fixed and independent from each other. For example, while writing the first data into the first spare physical erasing unit, the memory management circuit202may determine whether the first spare physical erasing unit is fully written. When the first spare physical erasing unit is fully written, the memory management circuit202may select one or more another spare physical erasing units from the spare physical erasing units in the storage area402for replacing the first spare physical erasing unit being fully written as the new receiving physical erasing unit, and then the entire or part of the first data (not being written completely into the first spare physical erasing unit) is written into the newly selected spare physical erasing unit which is currently served as the receiving physical erasing unit. Similarly, while writing the copied valid data into the second spare physical erasing unit, the memory management circuit202may determine whether the second spare physical erasing unit is fully written. When the second spare physical erasing unit is fully written, the memory management circuit202may select one or more another spare physical erasing units from the spare physical erasing units in the storage area402for replacing the second spare physical erasing unit being fully written as the new recycling physical erasing unit, and then the entire or part of the valid data (not being written completely into the second spare physical erasing unit) is written into the newly selected spare physical erasing unit which is currently served as the recycling physical erasing unit.

It should be noted that, the first physical erasing unit does not include the physical erasing unit currently used as the receiving physical erasing unit and the physical erasing unit currently used as the recycling physical erasing unit. For example, in case the physical erasing unit used as the receiving physical erasing unit is the first spare physical erasing unit, then the first physical erasing unit does not include the first spare physical erasing unit. In case the physical erasing unit used as the recycling physical erasing unit is the second spare physical erasing unit, then the first physical erasing unit does not include the second spare physical erasing unit. In other words, if a specific physical erasing unit is currently used as the receiving physical erasing unit or the physical erasing unit, then the specific physical erasing unit is not selected to be used as the first physical erasing unit for copying valid data therefrom. Similarly, if a specific physical erasing unit is currently used as the receiving physical erasing unit, then the specific physical erasing unit is not selected to be used as the recycling physical erasing unit at the same time; if a specific physical erasing unit is currently used as the recycling physical erasing unit, then the specific physical erasing unit is not selected to be used as the receiving physical erasing unit at the same time.

In an exemplary embodiment, the valid data copied from the first physical erasing unit at least includes a first valid data and a second valid data, and the logical erasing unit (also known as a first logical erasing unit) to which the first valid data belongs is different from the logical erasing unit (also known as a second logical erasing unit) to which the second valid data belongs. In other words, for the host system1000, the first valid data is stored in the first logical erasing unit to which one or more first logical addresses belongs, and the second valid data is stored in the second logical erasing unit to which one or more second logical addresses belongs. Further, aforesaid operation of writing the copied valid data into the recycling physical erasing unit may also be considered as moving of the valid data by the memory management circuit202. After writing the copied valid data into the recycling physical erasing unit, the memory management circuit202may erase the first physical erasing unit. The erased first physical erasing unit may then be considered as the spare physical erasing unit.

In the present exemplary embodiment, the memory management circuit202considers all of the physical erasing units in the storage area402as the first physical erasing unit, except the physical erasing unit currently used as the receiving physical erasing unit and the physical erasing unit currently used as the recycling physical erasing unit. However, in another exemplary embodiment, the memory management circuit202only considers one or more physical erasing units which satisfy a specific condition among the physical erasing units as the first physical erasing unit. For example, the specific condition may be related to an amount and/or a written time of the valid data stored in each physical erasing unit in the storage area402. In the present exemplary embodiment, expect the physical erasing unit currently used as the receiving physical erasing unit and the physical erasing unit currently used as the recycling physical erasing unit, the memory management circuit202may consider one or more physical erasing units stored with the valid data having a least amount and/or an earliest written time among all the physical erasing units in the storage area402as the first physical erasing unit. Further, in other exemplary embodiments, the memory management circuit202may also select the first physical erasing unit according to any conditions (e.g., based on whether a proportion between the valid data and the invalid data in the physical erasing unit matches a preset proportion), but the invention is not limited thereto.

FIG. 5AandFIG. 5Bare schematic diagrams illustrating management of a memory storage device according to an exemplary embodiment.

Referring toFIG. 5A, it is assumed that the physical erasing unit304(0) is currently used as the receiving physical erasing unit and the physical erasing unit304(1) is currently used as the recycling physical erasing unit. When the memory management circuit202receives a write command, the memory management circuit202may write a data501(also referred to as first data) indicated by the write command into the physical erasing unit304(0) currently served as the receiving physical erasing unit. Assuming that the memory management circuit202selects the physical erasing units304(4) and304(6) to be the first physical erasing units, the memory management circuit202may execute the garbage collection procedure for the physical erasing units304(4) and304(6) at the specific time point, so as to copy the valid data503from the physical erasing units304(4) and304(6) to the physical erasing unit304(1) currently served as the recycling physical erasing unit, as shown inFIG. 5A. After all the valid data503in the physical erasing units304(4) and304(6) are copied to the physical erasing unit304(1), the memory management circuit202may erase the physical erasing units304(4) and304(6) to make the physical erasing units304(4) and304(6) become the spare physical erasing units.

Referring toFIG. 5B, after the physical erasing unit304(0) and the physical erasing unit304(1) are fully written, it is assumed that the memory management circuit202selects the physical erasing unit304(2) to be used as the receiving physical erasing unit and selects the physical erasing unit304(3) to be used as the recycling physical erasing unit. Namely, the physical erasing unit currently served as the receiving physical erasing unit is changed from the physical erasing unit304(0), which is fully written, to the physical erasing unit304(2), and the physical erasing unit currently served as the recycling physical erasing unit is changed from the physical erasing unit304(1), which is fully written, to the physical erasing unit304(3). When the memory management circuit202receives another write command, the memory management circuit202may write a data502indicated by said another write command into the physical erasing unit304(2) currently served as the receiving physical erasing unit. Assuming that the memory management circuit202selects the physical erasing units304(5) and304(7) to be the first physical erasing units, the memory management circuit202may execute the garbage collection procedure for the physical erasing units304(5) and304(7) at the specific time point, so as to copy the valid data504from the physical erasing units304(5) and304(7) to the physical erasing unit304(3) currently served as the recycling physical erasing unit, as shown inFIG. 5B. After all the valid data504in the physical erasing units304(5) and304(7) are copied to the physical erasing unit304(3), the memory management circuit202may erase the physical erasing units304(5) and304(7) to make the physical erasing units304(5) and304(7) become the spare physical erasing units.

In other words, any data that is from the host system1000and intended to be written into the rewritable non-volatile memory module106is firstly written into the receiving physical erasing unit, and any data that is collected due to the garbage collection procedure is written into the recycling physical erasing unit, thus the old valid data of the rewritable non-volatile memory module106and the new data from the host system1000will not be written into the same physical erasing unit. In addition, the spare physical erasing unit is also continuously released with execution of the garbage collection procedure, a writing speed of the memory management circuit202for the rewritable non-volatile memory module106will not be decreased owing to the cross storage of the new and old data in the same physical erasing unit and/or insufficient spare physical erasing unit, even after the rewritable non-volatile memory module106has been used for a long period of time.

In an exemplary embodiment, as in response to the memory management circuit202writing the valid data from the first physical erasing unit into the recycling physical erasing unit, the memory management circuit202may also record a moving information of the valid data written into the recycling physical erasing unit. However, temporarily, the memory management circuit202does not update the logical address-physical erasing unit mapping table according to the valid data written into the recycling physical erasing unit. The reason is that, while the memory management circuit202is writing the valid data into the recycling physical erasing unit, it is possible that other data belonging to the same logical programming unit to which the valid data belongs may be written into the receiving physical erasing unit at the same time. Under such circumstance, the data originally considered as the valid data and moved to the recycling physical erasing unit may become the invalid data. Therefore, if a mapping relation between the logical address of the valid data and the recycling physical erasing unit is already updated to the logical address-physical erasing unit mapping table, such mapping relation may become invalid accordingly.

In this exemplary embodiment, it is assumed that the memory management circuit202receives a second write command while the memory management circuit202is moving the valid data to the recycling physical erasing unit or at any time points. The second write command instructs to write a second data into at least one second logical address among the logical addresses410(0) to410(D). The memory management circuit202may write the second data into the receiving physical erasing unit. The memory management circuit202may determine whether the logical programming unit (also known as a first logical programming unit) to which any one of the at least one valid data written into the recycling physical erasing unit belongs is identical to the logical programming unit (also known as a second logical programming unit) to which the second data belongs. The memory management circuit202updates the logical address-physical erasing unit mapping table according to the moving information only when the first logical programming unit and the second logical programming unit are not identical. Otherwise, when the first logical programming unit and the second logical programming unit are identical, the memory management circuit202may mark the valid data written into the recycling physical erasing unit as the invalid data.

FIG. 6is a schematic diagram illustrating management of a rewritable non-volatile memory module according to an exemplary embodiment of the invention.

Referring toFIG. 6, it is assumed that the physical erasing unit304(0) is currently used as the receiving physical erasing unit, and the physical erasing unit304(1) is currently used as the recycling physical erasing unit. In this case, when the memory management circuit202receives a write command which instructs to write a data601into the logical address belonging to the logical programming unit610(0), the memory management circuit202may write the data601into the logical programming unit610(0), map the logical programming unit610(0) to the physical erasing unit304(0), and write the data601into the physical erasing unit304(0). Assuming that the memory management circuit202selects the physical erasing units304(2) and304(3) to be the first physical erasing unit, the memory management circuit202may execute the garbage collection procedure for the physical erasing units304(2) and304(3) at the specific time point, so as to write the valid data (i.e., data602and603) from the physical erasing units304(2) and304(3) into the physical erasing unit304(1) which is currently served as the recycling physical erasing unit, and record the moving information of the data602and603being written into the physical erasing unit304(1). After the data602and603are written into the physical erasing unit304(1), the memory management circuit202may determine whether the logical programming unit610(0) to which the data601belongs is identical to the logical programming unit to which any one of the data602and603belongs. In case the logical programming unit610(0) to which the data601belongs is not identical to the logical programming unit to which any one of the data602and the data603belongs (e.g., the logical programming unit to which the data602belongs is the logical programming unit610(1) and the logical programming unit to which the data603belongs is the logical programming unit610(2)), the memory management circuit202may update the mapping relation between the logical programming unit610(1) to which the data602belongs and the physical erasing unit304(1) and the mapping relation between the logical programming unit610(2) to which the data603belongs and the physical erasing unit304(1) to the logical address-physical erasing unit mapping table according to the moving information of the data602and the data603previously recorded. On the contrary, in case the logical programming unit610(0) to which the data601is identical to the logical programming unit to which any one of the data602and the data603belongs (e.g., the logical programming unit to which the data602belongs is also the logical programming unit610(0)), the memory management circuit202may mark the data602as invalid, and only update the mapping relation between the logical programming unit to which the data603belongs and the physical erasing unit304(1) to the logical address-physical erasing unit mapping table, so as to improve a updating efficiency of the logical address-physical erasing unit mapping table.

Further, in another exemplary embodiment ofFIG. 6, the memory management circuit202may pre-determine whether the logical programming unit610(0) to which the data601belongs is identical to the logical programming unit to which the data602or the data603belongs before or while writing the data602and603into the physical erasing unit304(1). In case the logical programming unit610(0) to which the data601belongs is identical to the logical programming unit to which any one of the data602and the data603belongs, the memory management circuit202stops the operation of writing or moving the data602and/or603into the physical erasing unit304(1). For example, assuming that a write command that instructs to write the data601into the logical programming unit610(0) is received, the memory management circuit202is then informed that the garbage collection procedure for the physical erasing units304(2) and304(3) is about to be executed. In this case, the memory management circuit202may determine whether the logical programming unit610(0) to which the data601belongs is identical to the logical programming unit to which the data602or the data603belongs. For example, assuming that the logical programming unit to which the data602belongs is also the logical programming unit610(0), the memory management circuit202may then mark the data602from the valid data to the invalid data, and stop the operations of copying and writing the data602, so as to reduce chances for the physical erasing unit304(1) to be written with the invalid data. On the contrary, if the logical programming unit610(0) to which the data601belongs is not identical to the logical programming unit to which any one of the data602and the data603belongs, the memory management circuit202will not stop the operations of copying and writing the data602and the data603.

FIG. 7is a flowchart illustrating a memory management method according to an exemplary embodiment of the invention.

Referring toFIG. 7, in step S701, a first write command is received from a host system and first data indicated by the first write command is written to a physical erasing unit which is currently served as a receiving physical erasing unit. In step S702, valid data is copied from a first physical erasing unit and the valid data is written to a physical erasing unit which is currently served as a recycling physical erasing unit in a garbage collection operation. It is noted that, the physical erasing unit currently served as the receiving physical erasing unit and the physical erasing unit currently served as the recycling physical erasing unit are two physical erasing units independent from each other. For example, in an exemplary embodiment ofFIG. 5A, the physical erasing unit currently served as the receiving physical erasing unit is the physical erasing unit304(0), the physical erasing unit currently served as the recycling physical erasing unit is the physical erasing unit304(1), and the first physical erasing units from which the valid data is copied are the physical erasing units304(4) and304(6). Alternatively, in an exemplary embodiment ofFIG. 5B, the physical erasing unit currently served as the receiving physical erasing unit is the physical erasing unit304(2), the physical erasing unit currently served as the recycling physical erasing unit is the physical erasing unit304(3), and the first physical erasing units from which the valid data is copied are the physical erasing units304(5) and304(7).

FIG. 8is a flowchart illustrating a memory management method according to an exemplary embodiment of the invention.

Referring toFIG. 8, in step S801, in the garbage collection operation, a physical erasing unit is selected, in order to determine the first physical erasing unit. In step S802, it is determined whether the selected physical erasing unit is the physical erasing unit currently served as the receiving physical erasing unit in the garbage collection operation. If the selected physical erasing unit is the physical erasing unit currently served as the receiving physical erasing unit, in step S803, the selected physical erasing unit is not served as the first physical erasing unit, and step S801is repeated to select another physical erasing unit.

If the selected physical erasing unit is not the physical erasing unit currently served as the receiving physical erasing unit, in step S804, the selected physical erasing unit may be served as the first physical erasing unit. TakingFIG. 5Aas an example, if the physical erasing unit304(0) which is currently served as the receiving physical erasing unit is selected in step S801, the physical erasing unit304(0) is not determined to be the first physical erasing unit and the valid data is not copied from the physical erasing unit304(0). Alternatively, if the physical erasing unit304(4) which is not currently served as the receiving physical erasing unit is selected in step S801, the physical erasing unit304(4) could be determined to be the first physical erasing unit and the valid data could be copied from the physical erasing unit304(4).

FIG. 9is a flowchart illustrating a memory management method according to an exemplary embodiment of the invention.

Referring toFIG. 9, in step S901, in the garbage collection operation, a physical erasing unit is selected, in order to determine the recycling physical erasing unit. In step S902, it is determined whether the selected physical erasing unit is the physical erasing unit currently served as the receiving physical erasing unit. If the selected physical erasing unit is the physical erasing unit currently served as the receiving physical erasing unit, in step S903, another physical erasing unit which is not the physical erasing unit currently served as the receiving physical erasing unit is selected. In step904, the selected another physical erasing unit may be served as the recycling physical erasing unit. Alternatively, in step S902, if it is determined that the selected physical erasing unit is not the physical erasing unit currently served as the receiving physical erasing unit, then the selected physical erasing unit may be served as the recycling physical erasing unit in step S904.

FIG. 10is a flowchart illustrating a memory management method according to an exemplary embodiment of the invention.

Referring toFIG. 10, in step S1001, in the garbage collection operation, a physical erasing unit is selected, in order to determine the receiving physical erasing unit. In step S1002, it is determined whether the selected physical erasing unit is the physical erasing unit currently served as the recycling physical erasing unit. If the selected physical erasing unit is the physical erasing unit currently served as the recycling physical erasing unit, in step S1003, another physical erasing unit which is not the physical erasing unit currently served as the recycling physical erasing unit is selected. In step1004, the selected another physical erasing unit may be served as the receiving physical erasing unit. Alternatively, in step S1002, if it is determined that the selected physical erasing unit is not the physical erasing unit currently served as the recycling physical erasing unit, then the selected physical erasing unit may be served as the receiving physical erasing unit in step S1004.

FIG. 11is a flowchart illustrating a memory management method for updating a logical address-physical erasing unit mapping table according to an embodiment of the invention.

In step S1101, a write command (e.g. the second write command) is received after another write command (e.g., the first write command), wherein the second write command instructs to write a second data into at least one second logical address among the logical addresses. In step S1102, it is determined whether a logical programming unit to which the second data belongs is identical to the logical programming unit to which the copied valid data belongs. In step S1103, if it is determined that the logical programming unit to which the second data belongs is not identical to the logical programming unit to which the valid data belongs, a logical address-physical erasing unit mapping table is updated according to a corresponding relation between the valid data and the physical erasing unit currently served as the recycling physical erasing unit. In step S1104, if it is determined that the logical programming unit to which the second data belongs is identical to the logical programming unit to which the valid data belongs, at least part of the valid data is marks as invalid data. Detailed description ofFIG. 11may be obtained with reference to the exemplary embodiment ofFIG. 6.

Nevertheless, steps depicted inFIG. 7toFIG. 11are described in detail as above, thus related description is omitted hereinafter. It should be noted that, the steps depicted inFIG. 7toFIG. 11may be implemented as a plurality of program codes or circuits. For example, the steps depicted inFIG. 7toFIG. 11may be performed by the memory management circuit202ofFIG. 3. Also, a sequence for executing the steps depicted inFIG. 7toFIG. 11respectively may be adjusted according to practical demands, and the invention is not limited thereto. The method disclosed in FIG.FIG. 7toFIG. 11may be implemented with reference to the foregoing embodiments or may be implemented separately, and the invention is not limited thereto.

In addition, control commands of the memory management circuit202corresponding to the operations of “select”, “write”, “move”, “read”, “garbage collection” and “erase” for the rewritable non-volatile memory module106may be implemented as various command sequences each may include one or more commands (e.g., command codes). For example, in case the memory management circuit202is executing a select operation to the rewritable non-volatile memory module106, the memory management circuit202may send a command sequence in which the command sequence is configured to instruct to select one or more physical erasing units from the physical erasing units of the storage area402. The rest of operating instructions may be deduced by analogy. The rewritable non-volatile memory module106may execute the operations corresponding to the command sequences issued by the memory management circuit202.

In summary, the memory management method, the memory storage device and the memory control circuit unit of the invention are capable of writing the data from the host system into the receiving physical erasing unit, and writing the valid data collected from part of physical erasing units in the rewritable non-volatile memory module into the recycling physical erasing unit. Accordingly, the new data and the old valid data in the rewritable non-volatile memory module will not be stored in the same physical erasing unit, so as to effectively solve the problem in which the data writing efficiency of the rewritable non-volatile memory module is lowered after being used for a long period of time. In particular, the problem of the writing efficiency in the sequential write being lowered due to the new and old data being stored together may be effectively solved.

The previously described exemplary embodiments of the present invention have the advantages aforementioned, wherein the advantages aforementioned not required in all versions of the invention.