Flash memory management method

专利摘要:
PURPOSE: A flash memory management method is provided to consistently restore the data at an emergency state, for example, an abrupt power shut-off, and to prevent a system performance from being lowered in an environment of a frequent data update on a specific page like a DOS file system based on a FAT(File Allocation Table). CONSTITUTION: The method comprises steps of receiving a request of a write operation on a page on which data has been recorded already, performing the write operation on a log block corresponding to a data block including the page, receiving again a request of a write operation on the same page, and performing the write operation on a free space within the log block. The log block is managed by a data structure of a log pointer table. Entries of the log pointer table include a logical address block, log_blk, a corresponding physical address block, phy_blk, of the data block, and logical addresses of corresponding pages within a corresponding log block in an order that the pages of the data block are recorded.
公开号:KR20020092487A
申请号:KR1020010031124
申请日:2001-06-04
公开日:2002-12-12
发明作者:김범수；조유근；민상렬；노삼혁；이귀영；김종민；인지현；정재용；이동희；김제성；최종무
申请人:삼성전자 주식회사；
IPC主号:

专利说明:

Flash memory management method
[16] The present invention relates to flash memory, and more particularly, to a flash memory management method in a flash memory based system.
[17] Flash memory is a nonvolatile memory device that can electrically erase or write data. Compared to magnetic disk memory-based storage devices, flash memory-based devices consume less power and are smaller in size, and are being actively researched and developed as an alternative to magnetic disk memory. In particular, flash memory is expected to be in the spotlight as storage for mobile computing devices such as digital cameras, mobile phones, and personal digital assistants (PDAs).
[18] However, unlike a magnetic disk memory in which a flash memory is free to overwrite data, the flash memory cannot be overwritten. To overwrite data in flash memory, you must first erase it. That is, the memory cells must be returned to the initial state in which they can be written. This is called erasing. Erasing generally takes much longer than writing. Moreover, since the erase is performed in units of blocks larger than the writes, the erase may be erased together where the write is not requested. Inevitable erasures must be restored by writing back, so in the worst case, a write request for one data requires one erase and one write for the erased unit. As a result of the mismatch between the execution units of erase and write, the performance of writing is significantly lower than that of reading, and even lower than that of magnetic disk-based storage, which inevitably incurs inevitable delays due to machine operation. Therefore, the improvement of write performance is a key technology in the design of storage devices based on flash memory.
[19] U.S. Patent No. 5,388,083 proposes a CAM structure that converts a user-requested logical address into a physical address in flash memory instead of performing an erase to write to empty space to avoid delays caused by the erase that must be preceded by the write. . However, implementing a cam structure requires an expensive circuit. U.S. Patent No. 5,485,595 proposes a method of writing a logical address in the additional area of each page and sequentially reading the logical address recorded in the additional area instead of writing to the empty space without writing the erase when a write is requested. However, such an address translation mechanism has a problem in that it takes a long time to read scattered stored address translation information when the unit of reading is large, such as a NAND type flash memory.
[20] U.S. Patent No. 5,845,313 proposes a method of constructing a linear address translation table that scans logical addresses stored in flash memory and initializes the address directly to a separate RAM when the storage device is initialized. However, a large amount of RAM is required to store the address translation table. For example, to store the address translation table of a flash memory-based storage device with a total storage capacity of 32MB and a page size of 512B, 2B per 65,536 pages is required, requiring a total of 128KB of RAM. This demand is too high for small systems with abundant resources such as mobile devices.
[21] U.S. Patent No. 5,404,485 proposes a method of allocating a new block (replacement block) for writing and writing to the allocated block. However, according to this, since a new block is continuously allocated for writing, there are a plurality of blocks of different versions in which the same page is written. In other words, implicitly requiring at least one replacement block for every block, the capacity of the flash memory is significantly reduced. Also, pages written to a new block should always be written in the same location as the previous block, so if frequent updates are made only for a particular page and the remaining pages are rarely updated, only the content of a particular page will be different and only The contents have a problem in that a plurality of identical replacement blocks exist so that the storage space of the flash memory is increased. Therefore, it is not suitable for small systems such as mobile devices.
[22] Accordingly, an object of the present invention is to provide a flash memory based system and a management method thereof that can improve the performance of the flash memory.
[23] Another object of the present invention is to provide a flash memory based system and a method of managing the same, which can restore data consistently in an emergency such as power failure.
[24] It is still another object of the present invention to provide a flash memory based system and a method of managing the same, which do not deteriorate the system performance even in an environment where data update for a specific page is frequent, such as in a DOS file system based on a FAT (File Allocation Table) will be.
[1] 1 is a block diagram of a flash memory based system according to a preferred embodiment of the present invention;
[2] 2 is a reference diagram for explaining blocks for storing general data provided in the flash memory 1 according to the present invention;
[3] 3 is a reference diagram for explaining reading of a log block and a data block;
[4] 4 is a reference diagram for describing region division of a flash memory 1 according to an exemplary embodiment of the present invention;
[5] 5 is a reference diagram for explaining a region division of a flash memory 1 according to another exemplary embodiment of the present invention;
[6] 6 is a reference diagram for explaining a log pointer table;
[7] 7 is a structural diagram of a log pointer table entry;
[8] 8 is a reference relationship diagram between a log pointer table and a flash memory 1;
[9] 9 is a reference diagram for explaining an erasable block;
[10] 10 is a conceptual diagram of a simple merge;
[11] 11 is a conceptual diagram of copy merging;
[12] 12 is a relationship diagram showing a transition relationship of blocks according to performing a block merging according to the present invention;
[13] 13 is a flowchart for explaining a reading method according to the present invention;
[14] 14 is a flowchart for explaining a writing method according to the present invention;
[15] FIG. 15 is a flowchart for explaining the block merging of FIG. 14.
[25] The above object is a method of writing predetermined data in a flash memory, the method comprising: (a) writing to be requested to write on a page in which predetermined data is written; (b) writing to a log block provided to correspond to the data block including the page; (c) receiving a request to write to the page again; And (d) writing to an empty free page in the log block.
[26] Step (b) includes (b11) writing to an empty free page, or (b21) allocating the log block; And (b22) writing to a free page at the same position as the position in the data block of the page for which the write is requested.
[27] A method of writing predetermined data in a flash memory, the method comprising: (a) receiving a request to write to a predetermined page; (b) allocating a 1-1 log block corresponding to the first data block including the page; (c) writing to an empty free page in the 1-1 log block; (d) receiving a request to write to the page again; And (e) writing to an empty free page in the 1-1 log block.
[28] Step (b) may include: (b1) performing a block merging to generate a third data block based on the second data block and the second log block corresponding thereto; And (b2) allocating the free block obtained by performing the erasing on the second data block to the first log block. The step (b1) may be performed when there is no free block for allocating the 1-1 log block, or when all existing log blocks corresponding to the first data block are in use.
[29] Also, in the step (b1), if the arrangement order of the pages of the second log block and the pages of the second data block are the same and correspond one-to-one, the second log block is transferred to the third data block. Performing an exchange merge, or
[30] (b12) copy merge to generate the third data block by copying the corresponding page of the second data block to a free page of the second log block when all pages existing in the second log block are requested to be written only once. Or performing the steps
[31] (b13) A simple method of generating the third data block by copying the latest pages existing in the second log block to a free block in which no data is recorded, and copying the corresponding page of the second data block to the remaining free pages. It is more preferred to include the step of performing the merge.
[32] Step (e) may include: (e1) allocating a new 1-2 log block when there is no free page in the 1-1 log block; And (e2) writing to a free page in the 1-2 log block, wherein (e1) includes (e11) a page of the 1-1 log block and a page of the first data block. Performing an exchange merging for transitioning the first-first log block to a second data block when the arrangement order of is identical and one-to-one correspondence; And (e12) allocating the free block obtained by performing the erase on the first data block to the 1-2 log block.
[33] (e21) When all pages present in the 1-1st log block are requested to be written only once, a second data block is generated by copying a corresponding page of the first data block to a free page of the 1-1st log block. Performing a copy merging; And (e22) allocating a free block obtained by performing an erase on the first data block to the 1-2 log block.
[34] (e31) performing a simple merge to copy the latest pages existing in the first-first log block to the free block and copy the corresponding page of the first data block to the remaining free pages to generate a second data block. ; And (e32) allocating a free block obtained by performing an erase on the first data block or the 1-1 log block to the 1-2 log block.
[35] The step (e2) preferably includes the step (e21) of writing to a free page at the same position as the position in the data block of the page requested to be written.
[36] On the other hand, according to another aspect of the present invention, the above object is a method for reading predetermined data from a flash memory, the method comprising the steps of: (a) searching for an entry in which the block address portion of the logical address of the page requested in the log pointer table; (b) checking whether a logical address of the requested page is recorded in the retrieved entry; And (c) accessing the corresponding page of the log block with reference to the physical address of the corresponding log block recorded in the retrieved entry and the write position in the retrieved entry of the retrieved logical address. It is also achieved by the reading method.
[37] In step (c), in accessing the corresponding page of the log block, it is preferable to access the page at the same position as the recording position in the searched entry of the searched logical address.
[38] According to another aspect of the present invention, the above object is a method of managing a flash memory including a data block and a log block for writing data for updating the data block, the method comprising: (a) a first data block; Transitioning the first log block to a second data block when a page of and a page of a first log block corresponding to the first data block are identical and have a one-to-one correspondence; And (b) updating the address translation information.
[39] A method of managing a flash memory including a data block and a log block for writing data for updating the data block, the method comprising: (a) a case where all pages present in the first log block are written once only; Generating a second data block by copying the corresponding page of the first data block to the free page of the first log block; And (b) updating the address translation information.
[40] A method of managing a flash memory including a data block and a log block for writing data for updating the data block, the method comprising: (a) existing in the first log block in a free block in which no data is recorded; Copying the latest pages and copying the corresponding page of the first data block corresponding to the remaining free pages to generate a second data block; And (b) updating the address translation information.
[41] It is preferable to further include the step of recording recovery information for recovering data when the system is interrupted during the execution of step (a) or step (b) before step (a).
[42] The flash memory management method may further include (c) restoring data with reference to the recovery information when the system is interrupted during the step (a) or (b).
[43] The recovery information includes a list of the free blocks, a list of log blocks, and a log pointer table, which is a data structure for managing the log blocks, wherein the log pointer table includes a number of log pointer table entries corresponding to log blocks. In each entry, the logical address of the corresponding data block is mapped to the physical address of the corresponding log block, and the logical address of the requested page of the corresponding data block is recorded according to the physical arrangement order of each page in the corresponding log block. .
[44] In addition, the object of the present invention is a method of managing a flash memory including a data block and a log block for writing data for updating the data block, the method comprising: (a) allocating a predetermined area of the flash memory to the allocated area; Recording the data block and the list of log blocks, and a data structure for managing the log blocks as recovery information; (b) checking whether the error has occurred by checking a state currently recorded in the flash memory based on the recovery information when the system is stopped; And (c) restoring data with reference to the recovery information when an error occurs.
[45] Hereinafter, exemplary embodiments of the present invention will be described with reference to the accompanying drawings.
[46] 1 is a block diagram of a flash memory based system according to a preferred embodiment of the present invention.
[47] Referring to FIG. 1, a system includes a flash memory 1, a ROM 2, a RAM 3, and a processor 4. The processor 4 is usually combined with the program code recorded in the ROM 2 to issue a series of read or write commands to the flash memory 1 or the RAM 2. The flash memory 1 is written and read according to the flash memory management method of the present invention. The ROM 2 and the RAM 3 store application program codes or related data structures executed by the processor 4.
[48] 2 is a reference diagram for explaining blocks for storing general data provided in the flash memory 1 according to the present invention.
[49] Referring to FIG. 2, the flash memory 1 includes a plurality of data blocks and log blocks provided to correspond to at least some data blocks. The "data block" refers to a block for storing general data, and the "log block" refers to a block that is allocated when a predetermined portion of the data block is to be modified and used for recording the modification. Thus, a log block corresponds to only one data block and stores modified pages of that data block. Pages stored in the log block are referenced before those pages stored in the data block. Such pages that are preferentially referred to are referred to as "valid pages" in this specification. In addition, a page whose contents are ignored by a valid page even though physically valid data is recorded is called a "invalid page" in a logical sense.
[50] 3 is a reference diagram for explaining reading of a log block and a data block.
[51] Referring to FIG. 3, when a read for a predetermined page is requested together with a logical address from a user, the processor 4 refers to a log pointer table recorded in the RAM 3 and whether the corresponding log block exists. Check if the requested page is validly stored in the log block if it exists. If the requested page is validly stored, the corresponding page of the log block is read. Otherwise, the corresponding page written to the data block is read. The log pointer table will be described later.
[52] 4 is a reference diagram for describing region division of the flash memory 1 according to an exemplary embodiment of the present invention. Referring to FIG. 4, the flash memory 1 may be divided into a map area, a log block area, a data block area, and a free block area. Address translation information is stored in the map area, the log block area is an area for allocating log blocks, the data block area is an area for general data recording, and the free block area is an area for allocating log blocks or data blocks. . Here, each area means a logically divided area. Thus, they may be physically intermingled and discontinuous. In particular, the data block area, log block area, and free block area are the same.
[53] 5 is a reference diagram for describing region division of the flash memory 1 according to another exemplary embodiment of the present invention. Referring to FIG. 5, the flash memory 1 may be divided into a map area, a check point area, a log block area, a data block area, and a free block area. In this embodiment, a checkpoint area is newly provided as compared with the area division of FIG. Recovery information necessary for data recovery is recorded in the check point area. On the other hand, as in the case of Fig. 4, address translation information is stored in the map area, the log block area is an area for allocating log blocks, the data block area is an area for recording general data, and the free block area is a log block. Or a free area for allocating data blocks. Detailed description of the address conversion information recorded in the map area and the recovery information recorded in the checkpoint area will be described later.
[54] The "Log Pointer Table" is a data structure for managing log blocks. The log pointer table records the offset of the updated page (the logical address of the requested page) in the corresponding data block according to the logical address of the corresponding data block, the physical address of the corresponding log block, and the physical order of the pages in the log block. do. Since the log pointer table must be built in the RAM 3 according to the present embodiment, the processor 4 scans and configures the log block area. Referring to FIG. 6, the log pointer table has a number of log pointer table entries corresponding to log blocks. When a write or read command is requested with the logical address of the page, the processor 4 refers to the log pointer table and accesses the log block or data block depending on the existence of the corresponding entry.
[55] 7 is a structural diagram of a log pointer table entry.
[56] Referring to FIG. 7, a logical address log_blk of a data block and a physical address phy_blk of a corresponding log block are recorded in a log pointer table entry. In addition, the logical addresses page # 0, page # 1, ..., page #N of the corresponding page in the log block are recorded in the order in which the pages of the data block are recorded.
[57] For example, if there are 16 pages in a block and the logical address is 02FF (hexadecimal), the first three digits 02F means the block address, and the last one digit F means the offset value of the page in the block. do. Therefore, it is possible to check whether there is a corresponding log block by searching whether there is 02F among log_blk of the log pointer table. If the corresponding log block exists, it is possible to determine whether the updated page in the log block is located by checking whether the logical address 02FF or the offset value F of the requested page is recorded. For example, if page # 0 is F, the requested page is written to the first physical page in the log block.
[58] As such, accessing the log block by checking the existence of the log block using only a part of the requested logical address, that is, the block address part, is defined as "block addressing," and the entire requested logical address (or offset value) is defined. Accessing the page of the log block by using the term "page addressing" is defined. As described above, the present invention employs block addressing and page addressing together to record all of them in one log block even when the same page is updated several times.
[59] 8 is a reference relationship diagram between the log pointer table and the flash memory 1.
[60] As illustrated in FIG. 8, it is possible to search for whether a log block for a corresponding data block exists by referring to log_blk, and to know the location where the corresponding log block is recorded by referring to phy_blk. In addition, in the log pointer table entry, logical addresses page # 0, page # 1, page # 15 of each page of the log block according to the present embodiment may be recorded. Each block in this embodiment includes 16 pages.
[61] In principle, updated pages are written in the same position as the corresponding page of the corresponding data block in the log block. In fact, when the updated page is first recorded in the log block, it may be written in the same position as the corresponding page of the data block. However, this is not necessarily the case afterwards. That is, if a predetermined page of the corresponding data block needs to be updated again before the remaining pages are updated once, it is written in the remaining empty space of the corresponding log block.
[62] 9 is a reference diagram for explaining an erasable block.
[63] When all the pages of the data block are updated only once, the pages of the log block correspond one-to-one to each page of the corresponding data block, as shown in FIG. In this case, since the log block contains all the contents of the data block, erasing the data block does not cause data loss. Such data blocks that no longer have valid data (fully shadowed) are called "erasable blocks". The erased block is called a "free block." Erasable-blocks can be erased at any time and free blocks can be allocated as data blocks or log blocks as needed.
[64] On the other hand, in the present invention, "block merge" is performed. Block merging occurs in principle when writes are repeated and there are no writable pages in the log block. In this case, block merging combines the log block with the corresponding data block to create a new data block, and erases the existing log block to make it a free block.
[65] In particular, a block merge that is performed when all the pages of the data block are updated only once and the log blocks and the page blocks of the data block are the same is called a "switch merge".
[66] If the arrangement of the pages of the log block and the page of the data block does not match, a "simple merge" is performed. Furthermore, because the log blocks are all in use, they are also performed when the log blocks must be reallocated to perform the newly requested write. In this case, the log block to be merged may have free pages not yet used.
[67] If the pages in the log block are updated only once, the log block can be transferred to the data block by filling the empty pages with the corresponding pages of the data block, and this block merge is called a "copy merge". I say. In summary, there are three block merges: exchange merge, simple merge, and copy merge.
[68] As described above with reference to FIG. 9, the exchange merging is performed by transferring a log block in which all pages of the data block are updated only once, as it is to the data block. The transition of the block is achieved by updating only the address translation information without copying the data recorded in the data block or log block. That is, the address conversion information recorded in the map area is updated so that the corresponding log block is mapped to the logical address requested by the user. In the map area, address conversion information for each block is recorded to enable block addressing. In this case, the invalid page is used to mean that a page whose contents are ignored due to a valid page as described above, and may be a physically valid page in an actual implementation.
[69] By simple merging, as shown in FIG. 10, a new data block is generated by writing the valid page of the data block and the valid page of the log block at the same position of the new free block. Therefore, the existing data block and the log block become erase-enabled blocks.
[70] Copy merging is performed by copying a valid page written in an existing data block to a free page of a log block, as shown in FIG. Existing data blocks are transitioned to erase-enabled blocks. The invalid page referred to in the block merging is used as a page not referred to first as described above, and may be a physically valid page in an actual implementation.
[71] 12 is a relationship diagram showing a transition relationship of blocks according to performing a block merging according to the present invention.
[72] Referring to FIG. 12, free blocks are transitioned to log blocks or data blocks. Log blocks are transitioned to data blocks through exchange merges or copy merges or to erase-enabled blocks through simple merges. The data block can be transitioned to an erasable block through exchange merging, simple merging, and copy merging. Erasable-blocks are transitioned back to free blocks by erasing.
[73] In order to perform block merging, a list of free blocks and eraseable blocks existing in the flash memory 1 must be kept. The list of free blocks and erasable-blocks is a data structure recorded in the RAM 3 together with the log pointer table, and can be recorded in a map area or a check point area.
[74] The list of free blocks, the list of eraseable blocks, and the log pointer table must be restored to RAM 3 when the system is initialized. Checkpoint areas are areas allocated according to one embodiment of the present invention in order to record the recovery information necessary for their quick and complete recovery. When the checkpoint area is set, the list of free blocks, the list of erasable-capable blocks, and the list of log blocks mentioned above are stored as recovery information. In particular, in the checkpoint area, in order to prevent information corruption due to congestion of the system or sudden power interruption, the block checkpoint area will perform some block merging before the block merging. A plan log describing whether to transition to the block is stored. The plan log contains the kind of block merging you want to perform, the block that transitions from the free block to the data block, the block that transitions from the free block to the log block, the block that transitions from the data block to the free block, and the block that transitions from the log block to the free block. The physical address of is recorded. The check point area also records information necessary for constructing address translation information (for example, a location where address translation information is stored). The position of the check point area itself is recorded in a predetermined block of the flash memory 1.
[75] Referring to the flash memory management method according to a preferred embodiment of the present invention by the above configuration as follows. Hereinafter, the flash memory management method according to the present invention will be described by dividing into a data structure construction and recovery method, a read method, and a write method accompanying system initialization.
[76] First, the flash memory management method involved in initializing the system means a method of building and restoring a data structure. That is, the data structure (list of free blocks, list of eraseable-capable blocks, list of log blocks, and log pointer table) and address translation information necessary for writing and reading are constructed, and the integrity check of the constructed information is performed. When a recovery task is required, it means to perform a recovery task based on the recovery information. When the system of FIG. 1 is initialized, the processor 4 must build a log pointer table, a list of free blocks, a list of eraseable blocks, and a list of log blocks in the RAM 3. To this end, the processor 4 reads recovery information from the most recently recorded page of the checkpoint area of the flash memory 1. This is because, when the recovery information is sequentially recorded, the latest recovery information is recorded in the page located immediately before the first free page (empty page) found in the checkpoint area. However, the recording order of the recovery information can be changed as necessary as long as the above-described most recently recorded page can be identified.
[77] The log pointer table can be constructed by scanning all pages of the log blocks specified in the recovery information and reading a logical address stored in an area added to each page. Since address translation information is sequentially recorded in the map area, address translation information can be constructed based on the last recorded page (the page located immediately before the first free page) as the last change. The free block list and the erasable-block list are also recoverable as is based on the recovery information.
[78] Next, the information constructed by referring to the plan log (list of free blocks, list of erasable-capable blocks, list of log blocks, and log pointer table) is verified. In other words, if the system operation is interrupted while the block merging is performed, it is necessary to check whether the constructed information matches the actual situation. Specifically, when the system operation is interrupted, it is classified into four types: first, writing recovery information in the checkpoint area, performing second block merging, updating address translation information in the third map area, and fourth erasing. In each case, the method of checking whether the constructed information matches the actual situation and recovering it if it does not match is as follows.
[79] 1. System operation was interrupted while writing recovery information to the checkpoint area: Find the first free page of the checkpoint area and read the data to see if this page is actually a free page or not. If the free page is not empty, it may be determined that the operation of the system was interrupted while writing the recovery information to the checkpoint area. In such a case, since the actual data is written before it is performed, there is no need to go through a separate recovery procedure. However, the finally recorded recovery information is ignored.
[80] 2. If the system operation is interrupted while performing a block merge: Check whether the data is properly recorded (valid) in all pages of the block that are stated to be transitioned to the data block in the plan log. If even one page is not valid, it may be determined that the system operation is interrupted during the block merging. In such a case, data can be recovered correctly by performing block merging again.
[81] 3. If the system operation is interrupted while updating the address translation information: Read the logical address from the block written to the data block in the plan log to see if it matches the information recorded in the map area. If they do not match, the system operation may be considered interrupted while updating the address translation information. In this case, it can be restored by modifying the address translation information based on the logical address and the corresponding physical address obtained from the data block.
[82] 4. If the system operation is interrupted during erasing: Check whether the blocks written to be transitioned to free blocks in the plan log are actually free blocks. If it is not a free block (if the page is not all empty), the erase operation is performed again on the non-empty block.
[83] As described above, the flash memory management method involved in initializing the system can establish a necessary data structure and read and write when the consistency check is completed.
[84] 13 is a flowchart illustrating a reading method according to the present invention.
[85] For the sake of understanding, the reading method is outlined, and the processor 4 searches whether the requested page exists in the log block, and reads the page from the retrieved log block.
[86] More specifically, first, the processor 4 sequentially searches the log pointer table based on the logical address of the requested page and checks whether there is a corresponding entry (step 1301). Since the logical address of the requested page is combined into the block addressing portion and the page addressing portion, the entry is searched by referring to the block addressing portion. If a matching entry is found (step 1302), the entry is searched to see if the requested page exists (step 1303).
[87] If the page is found, read it (step 1305). At this time, if two or more identical pages are found, the last one found is read as the latest one except that they have the same offset value, and the corresponding pages of the log block are read. If no matching entry is found (step 1302) or the corresponding page does not exist in the corresponding log block (step 1304), the corresponding page in the data block is read based on the requested logical address (step 1306).
[88] 14 is a flowchart for explaining a writing method according to the present invention.
[89] To understand the overview of the writing method, the processor 4 first searches whether the requested page exists in the log block, and if the log block exists, the page at the same position as the requested page in the log block is available. Check if it is. If it is available, it writes to the page. Otherwise, it writes to another available page of the log block. If there is no page available in the log block, it allocates a new log block and writes to the same location. do.
[90] More specifically, the processor 4 searches the log pointer table based on the logical address of the requested page (step 1401). If an entry is found (step 1402), it means that the corresponding log block exists, so the entry is searched to determine whether a page with the same offset value as the requested page is available (step 1403), and if it is available, Write (step 1404). Here, the usable page refers to an empty page (free page) because no writing has been performed on the corresponding page of the log block. Whether or not a free page exists can be determined by searching for an entry to determine whether the page is valid (priority reference, ie data is recorded). Next, the physical address corresponding to the logical address of the page on which writing is performed is written in the corresponding entry of the log pointer table. In this case, the user's write request is completed with just one write to the flash memory.
[91] If a corresponding log block is found but a page having the same offset value is already used (step 1403), it is checked whether another free page can be allocated in the log block (step 1406), and a write operation is performed on the allocated free page (step 1407). ). If there are two or more free pages, the nearest page can be allocated by searching sequentially from the start of the log block. Subsequently, the physical address of the allocated page is recorded in a corresponding entry of the log pointer table so as to correspond to the logical address of the requested page (step 1405).
[92] If a corresponding entry for the requested page is not found as a result of searching the log pointer table, it is checked whether a new log block is assignable (step 1408). If there are free blocks to be allocated as new log blocks, assign one of them to a new log block (step 1408). If there are no free blocks left, create a free block by merging blocks, and then create a new log. Allocates to blocks (step 1409). In operation 1410, the write operation is performed on the page having the same offset value as the page requested to be written in the allocated log block. Next, a corresponding entry is generated in the log pointer table (step 1405).
[93] FIG. 15 is a flowchart for explaining the block merging of FIG. 14.
[94] As described above, the block merging is performed in different ways according to the page arrangement in the log block. More specifically, the processor 4 checks whether all pages of the log block are at the same position as that of the corresponding data block (step 1501), and then checks whether all pages of the log block are valid (1502). step).
[95] If all pages of the log block are arranged identically to that of the data block and all are valid, an exchange merge is performed. On the other hand, the processor 4 records the recovery information in the checkpoint area before performing the exchange merging (step 1503). However, step 1503 may not be performed. Performance is a system designer's option. In order to exchange merging, the processor 4 updates address translation information of the map area to make the log block a new data block (step 1504). That is, when the log block is transferred to a new data block, the physical address corresponding to the logical address is changed from the user's point of view, and thus the address translation information needs to be updated. In fact, the updated address translation information may be recorded in the first free page of the map area. Similarly, the map area is recorded sequentially, and when there are no more free pages, the free block is allocated to the map area and recorded. The allocation method of the free block is the same as that described with reference to FIG. Accordingly, the data block is transferred to the erasable-capable block, and thus the data block is erased and the free block list recorded in the checkpoint area is updated (step 1505).
[96] If any page of the log block is not arranged identically to that of the data block, a simple merge is performed. Similarly, the processor 4 writes the recovery information in the checkpoint area before performing the simple merge (step 1506). Step 1506 is also a system designer's option. Subsequently, a free block is allocated and a valid page of the log block is copied thereto (step 1507), and the remaining part is written to the corresponding page of the data block (step 1508), and then the address of the map area so that the free block becomes a new data block. The conversion information is updated (step 1509). The allocation method of the free block is the same as that described with reference to FIG. Meanwhile, the log block and the data block are transferred to the erasable-capable block, and thus, the log block and the data block are deleted, and then the free block list recorded in the checkpoint area is updated (step 1510).
[97] If all pages of the log block are arranged identically to that of the data block, but some pages of the data block are not present in the log block, a copy merge is performed. Similarly, the processor 4 writes the recovery information to the checkpoint area before performing the copy merging (step 1511). Step 1511 is also a system designer's option. Next, the valid page of the data block is read and copied to the log block (step 1512). Next, the address translation information of the map area is updated to make the log block a new data block (step 1504), the data block is erased, and the free block list recorded in the checkpoint area is updated (step 1505).
[98] As such, when a log block for data update is not found, a free block is allocated, transferred to the log block, and a write is performed there. If there is only one free block to allocate a log block, it is necessary to select a random one among the existing log blocks and perform a block merge to obtain a new free block and then allocate the log block. In such a situation, an appropriate choice should be made, taking into account the cost of block merging and the future availability of the blocks. Future availability may depend on the characteristics of the application you want to run. In the present invention, the replacement algorithm is not particularly defined. It is therefore possible to use generalized replacement algorithms, such as LRUs, to implement the present invention.
[99] As described above, an object of the present invention is to provide a flash memory management method capable of improving the performance of a flash memory. Conventionally, in order to update a part of one data block, it is necessary to copy to the rest or to perform large-scale address translation information. However, according to the present invention, even if consecutive writes to the same page are requested, the data can be processed in one log block, thereby improving the efficiency of flash memory resources. In addition, consistent data restoration is possible even if the system is interrupted due to a power failure during block merging.

权利要求:
Claims (28)
[1" claim-type="Currently amended] In a method of writing predetermined data to a flash memory,
(a) writing to perform a write request on a page on which predetermined data is recorded;
(b) writing to a log block provided to correspond to the data block including the page;
(c) receiving a request to write to the page again; And
(d) writing to an empty free page in the log block.
[2" claim-type="Currently amended] The method of claim 1,
Step (b) is
and (b11) writing to an empty free page.
[3" claim-type="Currently amended] The method of claim 1,
Step (b) is
(b21) allocating the log block; And
(b22) writing to the free page at the same position as the position in the data block of the page for which the write is requested.
[4" claim-type="Currently amended] In a method of writing predetermined data to a flash memory,
(a) receiving a request to write to a predetermined page;
(b) allocating a 1-1 log block corresponding to the first data block including the page;
(c) writing to an empty free page in the 1-1 log block;
(d) receiving a request to write to the page again; And
and (e) writing to an empty free page in said 1-1 log block.
[5" claim-type="Currently amended] The method of claim 4, wherein
Step (b) is
(b1) performing block merging to generate a third data block based on the second data block and the second log block corresponding thereto; And
and (b2) allocating a free block obtained by performing an erase on the second data block to the first log block.
[6" claim-type="Currently amended] The method of claim 5,
The step (b1) is performed when there is no free block for allocating the 1-1 log block.
[7" claim-type="Currently amended] The method of claim 5,
The step (b1) is performed when all existing log blocks corresponding to the first data block are in use.
[8" claim-type="Currently amended] The method of claim 5,
Step (b1)
(b11) performing an exchange merging transitioning the second log block to the third data block when the page order of the second log block and the page order of the second data block are the same and correspond one-to-one. Flash memory writing method characterized in that.
[9" claim-type="Currently amended] The method of claim 5,
Step (b1)
(b12) copy merge to generate the third data block by copying the corresponding page of the second data block to a free page of the second log block when all pages existing in the second log block are requested to be written only once. Flash memory writing method comprising the step of performing.
[10" claim-type="Currently amended] The method of claim 5,
Step (b1)
(b13) A simple method of generating the third data block by copying the latest pages existing in the second log block to a free block in which no data is recorded and copying the corresponding page of the second data block to the remaining free pages. And performing a merge.
[11" claim-type="Currently amended] The method of claim 4, wherein
Step (e) is
(e1) allocating a new 1-2 log block when there is no free page in the 1-1 log block; And
and (e2) writing to a free page in the 1-2 log block.
[12" claim-type="Currently amended] The method of claim 11,
Step (e1)
(e11) performing an exchange merge to transfer the first-first log block to the second data block when the page order of the first-first log block and the page order of the first data block are the same and correspond one-to-one. step; And
and (e12) allocating the free block obtained by performing the erasing on the first data block to the 1-2 log block.
[13" claim-type="Currently amended] The method of claim 11,
Step (e1)
(e21) When all pages present in the 1-1st log block are requested to be written only once, a second data block is generated by copying a corresponding page of the first data block to a free page of the 1-1st log block. Performing a copy merging; And
and (e22) allocating the free block obtained by performing the erase on the first data block to the 1-2 log block.
[14" claim-type="Currently amended] The method of claim 11,
Step (e1)
(e31) performing a simple merge to copy the latest pages existing in the first-first log block to the free block and copy the corresponding page of the first data block to the remaining free pages to generate a second data block. ; And
(e32) allocating a free block obtained by performing an erase on the first data block or the 1-1 log block to the 1-2 log block.
[15" claim-type="Currently amended] The method of claim 11,
Step (e2) is
and (e21) writing to the free page at the same position as the position in the data block of the page for which write is requested.
[16" claim-type="Currently amended] In a method of reading predetermined data from a flash memory,
(a) retrieving an entry in which the block address portion of the logical addresses of the requested pages is recorded in the log pointer table;
(b) checking whether a logical address of the requested page is recorded in the retrieved entry; And
(c) accessing the corresponding page of the log block with reference to the physical address of the corresponding log block written to the retrieved entry and the write position in the retrieved entry of the retrieved logical address. Way.
[17" claim-type="Currently amended] The method of claim 16,
Step (c) is
And accessing the page at the same position as the write position in the retrieved entry of the retrieved logical address in accessing the corresponding page of the log block.
[18" claim-type="Currently amended] A method of managing a flash memory including a data block and a log block for writing data for updating the data block, the method comprising:
(a) transitioning the first log block to a second data block when the arrangement order of the pages of the first data block and the pages of the first log block corresponding to the first data block are the same and correspond one-to-one; And
and (b) updating the address translation information.
[19" claim-type="Currently amended] A method of managing a flash memory including a data block and a log block for writing data for updating the data block, the method comprising:
(a) generating a second data block by copying the corresponding page of the first data block corresponding to the free page of the first log block when all pages existing in the first log block are written once only; And
and (b) updating the address translation information.
[20" claim-type="Currently amended] A method of managing a flash memory including a data block and a log block for writing data for updating the data block, the method comprising:
(a) copying the latest pages existing in the first log block to a free block in which no data is recorded, and copying the corresponding page of the first data block to the remaining free pages to generate a second data block; And
and (b) updating the address translation information.
[21" claim-type="Currently amended] The method according to any one of claims 18 to 20,
Before step (a) above
and (a0) recording recovery information for restoring data when the system is interrupted during the step (a) or (b).
[22" claim-type="Currently amended] The method of claim 21,
and (c) restoring data by referring to the recovery information when the system is interrupted during the step (a) or (b).
[23" claim-type="Currently amended] The method of claim 22,
And the recovery information comprises a log pointer table, which is a list of the free blocks, a list of log blocks, and a data structure for managing the log blocks.
[24" claim-type="Currently amended] The method of claim 23, wherein
The number of log pointer table entries corresponding to the log block is configured in the log pointer table, and each entry is mapped with a logical address of the corresponding data block and a physical address of the corresponding log block. Flash memory management method characterized in that the logical address of the requested page of the data block is recorded in the arrangement order.
[25" claim-type="Currently amended] The method of claim 23, wherein
And the log pointer table is configured to scan a log block area in which the log blocks are recorded to obtain necessary information.
[26" claim-type="Currently amended] A method of managing a flash memory including a data block and a log block for writing data for updating the data block, the method comprising:
(a) allocating a predetermined area of a flash memory and recording a list of the data block and the log block as recovery information and a data structure for managing the log block in the allocated area;
(b) checking whether the error has occurred by checking a state currently recorded in the flash memory based on the recovery information when the system is stopped; And
and (c) restoring data with reference to the recovery information when an error occurs.
[27" claim-type="Currently amended] The method of claim 26,
The recovery information further comprises a list of free blocks.
[28" claim-type="Currently amended] The method of claim 27,
The number of log pointer table entries corresponding to the log block is configured in the log pointer table, and each entry is mapped with a logical address of the corresponding data block and a physical address of the corresponding log block. Flash memory management method characterized in that the logical address of the requested page of the data block is recorded in the arrangement order.

类似技术:

---

公开号 | 公开日 | 专利标题

---

US9329995B2|2016-05-03|Memory device and operating method thereof

---

KR101948381B1|2019-02-14|Methods, data storage devices and systems for fragmented firmware table rebuild in a solid state drive

---

US9343153B2|2016-05-17|De-duplication in flash memory module

---

JP2016026346A|2016-02-12|Hybrid solid-state memory system having volatile memory and non-volatile memory

---

US8417882B2|2013-04-09|Storage device and deduplication method

---

US8051258B2|2011-11-01|Apparatus and methods using invalidity indicators for buffered memory

---

US8510500B2|2013-08-13|Device driver including a flash memory file system and method thereof and a flash memory device and method thereof

---

US7962687B2|2011-06-14|Flash memory allocation for improved performance and endurance

---

KR101638061B1|2016-07-08|Flash memory system and flash defrag method thereof

---

US8291155B2|2012-10-16|Data access method, memory controller and memory storage system

---

US8321652B2|2012-11-27|Process and method for logical-to-physical address mapping using a volatile memory device in solid state disks

---

TWI657338B|2019-04-21|Method for managing a memory apparatus

---

Chung et al.2006|System software for flash memory: a survey

---

US8392690B2|2013-03-05|Management method for reducing utilization rate of random access memory | used in flash memory

---

US8041878B2|2011-10-18|Flash file system

---

US7769945B2|2010-08-03|Method and system for facilitating fast wake-up of a flash memory system

---

CN100485641C|2009-05-06|Non-volatile memory system and method for programming and reading update data

---

EP1197868B1|2006-07-26|Method of driving remapping in flash memory and flash memory architecture suitable therefor

---

JP3590381B2|2004-11-17|Disk array device and data updating method in the device

---

US7840617B2|2010-11-23|Host device and memory system

---

JP4611024B2|2011-01-12|Method and apparatus for grouping pages in a block

---

CN102693184B|2015-06-03|Handling dynamic and static data for a system having a non-volatile memory

---

US8166233B2|2012-04-24|Garbage collection for solid state disks

---

US7433993B2|2008-10-07|Adaptive metablocks

---

US7475185B2|2009-01-06|Nonvolatile memory system, nonvolatile memory device, memory controller, access device, and method for controlling nonvolatile memory device

同族专利:

---

公开号 | 公开日

---

JP2002366423A|2002-12-20|

---

USRE45222E1|2014-10-28|

---

USRE46404E1|2017-05-16|

---

CN1389790A|2003-01-08|

---

CN1322428C|2007-06-20|

---

US6938116B2|2005-08-30|

---

USRE44052E1|2013-03-05|

---

JP3708047B2|2005-10-19|

---

USRE45577E1|2015-06-23|

---

US20020184436A1|2002-12-05|

---

KR100389867B1|2003-07-04|

引用文献:

---

公开号 | 申请日 | 公开日 | 申请人 | 专利标题

---

法律状态:
2001-06-04|Application filed by 삼성전자 주식회사

---

2001-06-04|Priority to KR10-2001-0031124A

---

2002-12-12|Publication of KR20020092487A

---

2003-07-04|Application granted

---

2003-07-04|Publication of KR100389867B1

优先权:

---

申请号 | 申请日 | 专利标题

---

KR10-2001-0031124A|KR100389867B1|2001-06-04|2001-06-04|Flash memory management method|