DE10227256C1 - Addressing blockwise erasable memories involves checking flag memory per address conversion in connection with sector write command leading to written sector to determine if block address present - Google Patents

Abstract

The method involves checking a flag memory for each address conversion in connection with a sector write command leading to a written sector to determine if the given block address is present. If not the contents of the sectors of the relevant blocks are written to unwritten sectors of blocks assigned according to the flag memory contents. The method involves, following each address conversion in an alternative memory block address, storing it with the associated sector address assigned to the logical block address in a flag memory (MS). The flag memory is checked for each address conversion in connection with a sector write command leading to a written sector to determine if the same block address is present. If not the contents of the sectors of the relevant blocks are written to unwritten sectors of blocks assigned according to the flag memory contents

Description

The invention relates to a method for addressing individual erasable real ones with memory block addresses addressable blocks of memory that are in with relative sector addresses addressable, individually writable memory sectors are structured, their deleted and described states stored can be made available for querying, by means of an address conversion of logical block addresses each in one of the real memory block addresses, where each time a sector write command was to be executed, the concerns a sector already described, by a changed address translation into an alternative Memory block address of a memory block whose relevant sector is deleted or blank, in this is written, and if it is, too alternatively addressed sector was already described that Address conversion another memory block address deleted memory block as a new alternative Provides memory block address and its corresponding Sector is described, and in the previous alternative addressed the still unrecorded sectors with the content of the corresponding sectors of the original allocated memory blocks are assigned, after which it is due for deletion and after a Deletion to another address conversion is available.

Such a method is known from US Pat. No. 6,145,051 A. Here, in an address transformation table for each logical block address a first physical, real Memory address of a block of memory held and then one further real memory block address set if a Sector of the first block of memory with new information should be described, which was already described,  which is why the information to be rewritten in the Alternative block with the further memory block address is enrolled because an immediate deletion is relative would be very time consuming and avoidable wear and tear on the Blocks of memory would cause the allowable Deletion frequency is limited. In addition, in the address Transformation table status information about the occupied / free sectors and the sectors with obsolete Contain content to be deleted. Such a thing Tables are very space-consuming and must because of the frequent and quick access and because of the constant Additions to the alternate block addresses and the necessary ones Restructuring of the address assignment when copying blocks or deleted, in the auxiliary memory of the Control processor are kept, its content at Power failure or shutdown in the non-volatile memory must be saved.

A method is also known from US Pat. No. 5,930,193 Classify blocks of memory in groups that already have the allocated memories were deleted in rough Specify ranges. The management of these groups requires other large tables that require space in the memory and which must be secured when the system is switched off.

Furthermore, WO 00/14641 describes a method for Addressing of such a memory is known, in which the Assignment of new memory blocks to be written in this way is that defective blocks are no longer used and the individual blocks evenly one by the deletion frequency are subject to wear and tear.

Enrolling new information into one already sector described requires a relocation of the remaining, still valid information from the rest  Sectors into a blank, pre-erased block, whose address is transferred to the assignor. Only if many pre-deleted blocks are described consecutively this procedure is effective in terms of time; Random changes of However, memory contents are relatively complex.

It is an object of the invention to disclose a method in which both have the benefits of uniform through deletions  caused memory wear and effective changes from especially randomly addressed memory contents by a Dodge block usage with minimal allocation memory usage space.

The solution is that after everyone, in particular wear-optimizing address conversion into an alternative Memory block address this together with the corresponding one Sector address assigned to the logical block address in one Memorized memory is saved and with each address conversion in Link to a sector write command that is on a leads sector described, the memory contents thereupon it is checked whether the same block address is present there and if not, the content of the sectors of the relevant blocks of memory in the as yet unwritten sectors of the memory block allocated in accordance with the memory content be written and then the memory block address of the copied memory blocks into an address list of to be deleted Memory blocks is entered and / or the block as too is deleted and then the pending Sector write command a memory block address of a deleted, allocated blank memory blocks and in the Memories are entered and with this Memory block address of the write command in the corresponding sector is performed.

Advantageous configurations are in the subclaims specified.

The address conversion from a logical to a real address takes place preferably in a previously known manner so that a uniform erase frequency for all blocks is achieved. The provision of an alternative block is superimposed, if a write command for a sector already described in occurs in an originally allocated memory block, and in  this alternative block will be the one to be written Information and other sector contents to be rewritten of the same block, including the alternative block address and a sector status of the alternative block for logical Block address are kept in a small memory.

As soon as in another than the original of a logical address allocated memory block a sector already described new to be described, the alternative memory block from the the content of the original memory block and its Storage address of a future original address translation fed, and it is the previous memory block with the outdated content released for deletion. The formation of a new alternate block address is used with the wear equalizing algorithm, and the deletion of the originally used and free memory blocks evaluated as its wear process.

As there are often several sectors in a logical block are to be changed, e.g. B. if a video or audio file is processed by creating the alternative block and completing the same and releasing the original Memory blocks only when there are write commands to another Block of memory significantly reduced the number of erases and the response time when writing is reduced. The reduction in Deletions complete the effect of address translation, one provides uniform erase frequency of the memory blocks, so that significantly increases the overall life of the memory is.

An advantageous further development is that if you work in parallel in several files, so alternately to a corresponding number of memory blocks is accessed, such a maximum number of alternate blocks is provided by the controlling processor in time  can be edited side by side. Accordingly, the number as set up in common operating systems, e.g. B. maximum four. The memo memory contains a corresponding number Address assignments and sector status flags in one Sector mask. At the beginning of each address determination, the few Addresses in the memory are checked for identity and only if if none is determined, the one described above takes place Address Translation. This leaves free space for created a new address assignment and the released one Memory block is marked for deletion. The storage and Time required for pre-checking the address with the Memory content is low, and the reduction in deletion frequency and the time saved as a result are very considerable.

In an advantageous embodiment, the previously described Search for a block of memory recorded in the memory the memory block selected for deletion, the next Logical block address to the new block to be written because there is a high probability that this block is further described with new sectors.

In an alternative embodiment, the one described above Search for a block of memory recorded in the memory the longest selected memory block for deletion was no longer described. For this purpose, in Merk store a counter for each alternate block, which at Write to this block initialized to an initial value and counted down when writing to the other alternate blocks becomes. The block with the lowest count was thus on no longer described. With this method one even distribution of the delete operations on the blocks achieves what the lifespan of the entire storage system elevated.  

The deletions are expedient in a background program executed. The completed by the address translation Blocks that are not marked are identified by the background program transferred to a table of the memory blocks to be deleted and the deletion was carried out. After deletion, the blocks marked as free or in the list of deleted blocks managed, which can be used for further address conversion.

The time saved is increased by the fact that Background program for deleting and releasing the memory blocks is executed at times when no writing or Read command pending.

The assignment of the logical block addresses to the real ones Memory blocks are advantageously carried out via a table in the real memory blocks over the logical block address is indexed. The sector share of the addresses is at Indexing not taken into account as the sectors in the logical blocks are numbered the same as in the real ones Memory blocks. With this table structure becomes a compact Form reached and storage space for management minimized.

This also makes compact management of the memory blocks achieved that a sector mask with the bit-by-bit identification of the described or free / deleted Sectors of directly writable memory blocks is performed. Similarly, a sector mask with the bitwise identification of the state of the sectors in the Dodge block currently managed. Then these bit lists controlled the memory operations.

A further simplification of the management of the memory blocks results if the logical to the in the assignment table real memory addresses one bit for each memory block  will result in the erased state of all memory blocks indicates. In blocks marked like this, a sector can can be written directly without the procedure with an off soft block to use. After writing the first sector in such a block is reset this bit.

It is for fast processing of memory operations advantageous to first check whether the memory in question block address has already been recorded in the memory. If this is the case, is based on the bit list in the sector mask determines whether the current content of the sector concerned located in the original memory block or in the alternative block. at a read operation is carried out directly on the determined sector content accessed. If the sector is to be rewritten, if the sector is in the alternate block, this alternate pad filled with the sectors of the original block and the Assignment table updated so that the alternate block to the The place of the original memory block occurs. The previous Memory block is released for deletion. From the stock on deleted memory blocks becomes a new backup block provided and the content of the memory accordingly updated. Now the sector content is in the new alternative block written and the sector mask updated. If the memory block was not previously stored in the memory, it is checked whether the sector is still deleted. If so If this is the case, the original memory block is scanned directly ben and reset the clear bit in the map table. Otherwise, a data record is searched in the memory, such as dissolved above and a new alternative block in Memories memory managed, in which is then written.

In an advantageous embodiment of the method, at a write operation for a sector based on the sector mask Checks in the memory whether it has been in the memory block so far Sector and only a small number of other sectors, e.g. B.  up to a quarter of the sectors of a block in which Alternative block were written. In this case, a new one Dodge block set up in which the changed sector ge wrote and the previously described sectors from the old Alternative block can be copied. The old alternate block becomes Delete released. Copying the unchanged sectors eliminated. This will increase the speed of the Write operation reached.

Advantageously, in a non-volatile memory block a reconstruction table is made out of which the condition the memory can be reconstructed after a power failure. For this purpose, all write and delete operations in the memory corresponding blocks in the table one after the other written. By tracing the table entries in Merk memory when the system starts up, the memory is stored on the brought current status of the write and delete operations. In particular, this determines which memory blocks are in use as alternative blocks and where are current Sectors are located in the alternate blocks.

Appropriately, a for the reconstruction table Memory block used and has a defined number, z. B. 127, from entries. As soon as the table becomes so long that this Limit is reached, all memory allocations in the Memories are resolved according to the procedure described above and cleared the records and the basic state manufactured. Then the reconstruction table is deleted and set up for new writing. During the time of dissolving and deleting the table will not create new orders for Storage operations of the parent operating system accepted.

The limit on the size of the entire memory array using a controller can be managed results from the  Size of the address pointers for the 16-bit and the memory blocks Number of memory chip select signals from the controller to be provided. It is now advantageous to have several Provide memory chip groups, each with like sectors and 16 bit address pointers for the Memory blocks can be addressed. The number of Memory chip groups correspond to a binary number, for Example 4. According to this number, the size of the with multiplied by a controller manageable memory arrangement. The lowest binary digits of the logical sector address are decoded and used to select the memory chip group used. This part of the sector address is also used as an index for the array of administrative structures used. With that, the Administrative structures with address pointers, alternate memory blocks etc., as previously described, continue to be used. The Organizationally, memory turns out to be a large memory arrangement with a multiple of sectors. By this Mapping successive logical addresses to parallel ones Memory blocks can make the memory operations quasi parallel expire, and with that becomes a significant speed advantage reached.

If there are several memory chip groups, it is advantageous to erase the blocks in the memory chips to stagger that parallel to the different storage building stone delete commands are loaded and then a block type total deletion time is waited for before the blocks be asked again if they are ready for more storage operations are. The memory modules show the end of the Processing of a command also by an end of memory signal. If the controller only has one input for evaluating the Has end times, the signals of the blocks on Controller merged into an end signal and a direct one It is not possible to evaluate the individual times. If all Blocks are ready for new storage operations  the signal on the controller is set accordingly. By waiting there is a constant interrogation of the blocks or the memory end Avoided signals, which lead to increased power consumption would.

Just like when deleting, it is also advantageous when writing, that write in parallel to the various memory modules commands are loaded and then a block-typical time one waits before the blocks again, just like with Delete, will be asked if they are for more memory operations are ready. In addition to saving electricity, there will also be a achieved higher speed of the storage system because of a corresponding number of sectors is written in parallel.

It is also advantageous if the controller waits for that End of the write or delete operation in the power saving mode is offset and the write end signal as an interrupt to Exiting this mode is used. This will make another one Energy saving effect.

If the controller has enough inputs for the end The controller has signals from the storage groups in the Power saving mode offset and at the write end signal everyone Storage group become active again. Overall, this shortens the Response time and saves on power consumption because querying the Building blocks are completely eliminated.

The embodiment of the invention is exemplary in the figures described. It shows:

Fig. 1 address assignment structure of the memory

Fig. 2 use of the alternate data blocks

Fig. 3 use of an additional alternate data block

Fig. 4 sequence of the write operation

Fig. 5 mapping to parallel storage groups

FIG. 1 shows the implementation of the provided by the hypervisor logical address LA in the real memory address RA. The logical address LA is divided into a logical block address LBA and a logical sector address LSA. An assignment table ZT is kept for the implementation, which specifies which real memory block address SBA is assigned to which logical block address LBA. There is one data record in the table for each memory block address SBA. The logical block address LBA serves as an index in the assignment table ZT. The logical sector address LSA corresponds to the real sector address RSA and therefore does not need to be stored in the table. For each real address RA, a block erase bit BLB is optionally carried, which indicates the erase state of the complete memory block. Using this bit, the memory block can be managed more quickly and easily.

The structure of the memory MS is also shown. For every possible memory address assignment occurs Data record with the fields memory block address SBA, alternative block address ABA, sector mask SM and the usage time counter LRU to disposal. For the memory block addresses listed here SBA is showing that for write operations Dodge block AB was set up, whose block address ABA is specified. The sector mask SM gives for each sector of memory blocks SB addressed by the address SBA indicate whether a changed content was written in the alternative block AB. The usage counter LRU is used for a write operation at the  initialized affected data record to a default value and counted down for all other records. The record with the lowest LRU was not the longest for one Write operation used.

In Fig. 2 the use of the alternate block AB is shown, which is managed with the sector mask SM. For each of the numbered sectors from 0 to 31 of the memory block SB and the alternative block AB, the value 1 in the 32-bit sector mask SM indicates that the respective sector is still unchanged in the memory block SB at the corresponding bit position. A value of 0 indicates that the corresponding sector has been rewritten in the alternative block AB. This is marked with N in the figure. The sector in the memory block SB is therefore no longer valid, identified by an X. When a new alternative block is requested, the pair is dissolved by copying the valid sectors of the memory block SB into the alternative block AB, identified by the arrow AL. The alternative block AB then contains only valid and current sectors and the memory block SB can be deleted. The associated data record in the memory MS is free again and can be used for new write operations.

Fig. 3 shows the use of an additional alternate block NB. If only a few sectors, in this example two, have been written into the alternative block AB and one of these sectors, in this example sector 30 , is to be changed again, the sector is written into the new alternative block NB with the sector write command SS. Then the other sectors marked with a 0 in the sector mask SM, here the sector 29 , are copied with the copy command K into the new soft block NB. The new alternative block NB has thus taken over the function of the old alternative block AB and the block AB can be released and deleted. When this combination is dissolved, the sectors marked with 1 in the sector mask SM are copied into the block NB, represented here by the arrow AL.

In FIG. 4, the flow of a write operation is shown for a sector. First, it is checked whether a data record has been created in the memory for the addressed memory block. If this is not the case, reading the memory block checks whether the sector to be written is still deleted. If this is the case, the block is written directly to and the block clear bit may be reset.

If a data record in the mem is created, the sector mask is used to check whether already a changed sector content in the alternative block was written. If not, it will go straight in the alternative block is written and the sector mask is updated Siert.

If the sector has already been written in the alternative block, is using the sector mask to check whether there are a few sectors z. B. a maximum of a quarter of the number of sectors of a memory blocks, are written in the alternate block. If not Case is, the written sectors are from the original Memory block copied into the alternative block and the allocators table updated so that the previous alternative block is now on the place of the original memory block occurs. The original Memory block is now released for deletion. From the stock deleted memory blocks, a new alternate block is ready posed. If no deleted memory block is available a released memory block is deleted. With this new alternative block, the data record is saved in the memory updated. Now the addressed sector is in the new one Dodge block written and the sector mask in the memory updated.

If the sector to be rewritten is only one of a few sectors was in the alternate block, will be another  Dodge block provided. The sectors written so far from the old alternate block to the new alternate block copied, the old alternative block is released and the Memories updated accordingly. The new sector is now written in the alternative block and the associated sector mask updated.

If there is no data record in the memory block in the memory block so far was assigned but the addressed sector is not deleted, a data record is searched for in the memory, its memory block address is closest to the addressed memory block or has not been described for a long time. This memory Record is resolved by the sectors of the original Memory blocks are copied into the corresponding alternative block, the mapping table is updated and the original Memory block is released. Via a new alternate block and the update of the data record in the memory can now the sector will be written in the new alternate block. The sector mask is then updated.

Fig. 5 shows the conversion of the logical address, consisting of the logical block address LBA and the logical sector address LSA into the real memory address, consisting of the memory block address SBA, the real sector address RSA and the bits for the group number GNx. The letter x is used here as a running index. Here are shown as an example 2 bits, GN0 and GN1, which are used by means of the decoding DEC to select the 4 memory groups SG0-SG3. The number of digits of the real sector address RSA corresponds to the number of sectors in the memory blocks SGn-x. The sectors within a memory block SBn-x are addressed with the real sector address RSA. The most significant bits of the real memory address form the memory block address SBA, which is used to address the memory blocks in all memory groups simultaneously. A memory block with a multiple of sectors is thus represented. This mapping of successive logical addresses to the sectors of a plurality of memory blocks SBn-x means that memory operations which relate to successive logical sectors are mapped to parallel memory groups and the memory operations can quasi in the memory groups SGx run in parallel.

When the storage system is initialized, it is determined how many parallel storage groups are formed. The maximal Number is the number of memory chips used. The Decoder DEC is used accordingly by the memory controller set.

The memory modules generate write end signals SESx that indicate the end of a write or delete operation. This In an execution, signals are in an OR function summarized and as the interrupt signal INT the Storage controller fed. In this way, the Controllers can be activated from the power-saving state or in Program of the controller can be determined by queries when the storage operations expired.

In another embodiment, the memory end signals SESx led directly to the storage controller and can be there queried or used for a specialized interrupt become.  

LIST OF REFERENCE NUMBERS

AB alternative block (twin)
ABA alternate block address
AL resolution
BLB block clear bit
DEC decoder for storage groups
GNx group number x
INT interrupt for writers
K Copy
LA Logical address
LBA Logical block address
LRU counter for age of the sector
LSA Logical sector address
MS memory
N New sector content
NB New alternative block (triplet)
RA Real address
RSA Real sector address
RT reconstruction table (logbook)
SB memory block
SBA memory block address
SBn-x memory block nx
SESx write end signal x
SGx storage group x
SM sector mask
SS sector write
WR write job for a sector
x outdated sector content
ZT allocation table

Claims (18)

1. Method for addressing individual erasable real memory blocks (SB) which are addressable with memory block addresses (SBA) and which are divided into individually writable memory sectors addressable with relative sector addresses (RSA), the erased and described states of which are stored and can be queried in each case, provided by means of a Address conversion of logical block addresses (LBA) in each case into one of the memory block addresses (SBA). whose corresponding sector is erased or unwritten, is written into it and if, however, this alternatively addressed sector has already been described, the address implementation addresses another memory block address (SBA) of a deleted memory block (SB) as a new alternative memory block provides address (ABA) and its corresponding sector is described and in the previous alternatively addressed memory block (AB) the as yet unwritten sectors are written with the contents of the corresponding sectors of the originally assigned addressed memory block (SB), after which this is due for deletion and after a deletion to another address conversion is available, characterized in that after each, in particular wear-optimizing, address conversion into an alternative memory block address (ABA), this is stored together with the associated sector address in a memory (MS) and associated with the logical block address (LBA) each address conversion in connection with a sector write command which leads to a written sector, the memory content is checked to determine whether the same block address is present there and, if this is not the case, the contents of the sectors of the memory concerned erblocks (SB) are written into the sectors of the memory block (ABA) allocated according to the memory content, and then the memory block address (SBA) of the copied memory block is entered in an address list of memory blocks to be deleted and / or the block is marked as to be deleted and thereafter, a memory block address (ABA) of a deleted, blank memory block is assigned to the still pending sector write command and is entered in the memory and the write command is executed in this sector with this memory block address (ABA). 2. The method according to claim 1, characterized in that the Memories (MS) only have as many memory address assignments contains how to store data in parallel, and whenever there is a sector write command Address conversion leads to a described sector, all assignments in the memory to an identity the block addresses (SBA) are checked and if none identical block address (SBA) is present, the sectors one Blocks (SB) in the sectors of the allocated memory blocks (AB) are transferred and then the memory block address (SBA) of the copied block (SB) in an address list of memory blocks to be deleted is entered and / or the block is to be deleted is marked and then the pending Sector write command a memory block address (ABA) deleted, blank memory blocks (AB) assigned and is entered in the memory (MS) and with this block address (ABA) the write command in corresponding sector is running.   3. The method according to claim 2, characterized in that for a new address translation in the memory (MS) ver signed block (SB) is cleared, the next has the logical block address (LBA). 4. The method according to claim 2, characterized in that for a new address translation in the memory (MS) ver signed block (SB) is cleared, in which a write counter (LRU) indicates that it has not been written to for a long time has been. 5. The method according to any one of the preceding claims, characterized characterized that in a background program the Address list of the memory blocks to be deleted processed and the deletions are made and the addresses of the deleted blocks of memory in a list of deleted Memory blocks are entered and / or these blocks as deleted blocks are marked. 6. The method according to claim 5, characterized in that the Background program then the deletions carries out if there is no write or read command. 7. The method according to any one of the preceding claims, characterized characterized in that the memory address assignment via a to be addressed with the logical block address Assignment table (ZT) is done. 8. The method according to claim 7, characterized in that in the memory (MS) for each block address in one sector mask (SM) assigned to individual sectors the sectors described are currently managed. 9. The method according to claim 8, characterized in that in the assignor table (ZT) one bit for each block address  (BLB) that the "deleted state" of the Indicates memory blocks. 10. The method according to any one of the preceding claims, characterized characterized in that at the beginning of each write operation the Memo memory content is then checked whether the logical block and sector address are contained therein and in which of the memory blocks (SB) a current one Sector content exists, which is to be written by a Information in the free sector of each assigned or memory block still to be allocated (AB) is replaced. 11. The method according to claim 10, characterized in that, if so far only a few sectors in a memory block (AB) were changed and one of these sectors subsequently to be changed again, this sector into a new one allocated memory block (NB) is written and the other changed sectors in this new block of memory (NB) are copied from the previous memory block (AB), and this new memory block (NB) in place of the previous one allocated memory block (AB) occurs. 12. The method according to any one of the preceding claims, characterized characterized in that a Recon structure table (RT) for each write or erase scope ration is led, from which the state of the Memory (MS) after a power failure at Reconstruction of the system can be reconstructed. 13. The method according to claim 12, characterized in that when a predefined fill level is reached Reconstruction table (RT) a defined basic state the memory (MS) and the reconstruction table (RT) is brought about.   14. The method according to any one of the preceding claims, characterized characterized in that in a memory array several can be selected and deleted independently of one another Memory block groups (SGx) the logical Memory addresses (LA), memory block addresses (SBA) and the sector addresses (LSA) of the memory chip groups (SGx) be assigned such that the number of Memory chip groups correspond to a binary number and that the lowest binary digits of the logical Sector address (LSA) is decoded by the memory Serve group selection and the next higher-order binary Set the logical sector address (LSA) and higher subsequent logical block address (LBA) as the Real sector address (RSA) of all memory modules in the Memory block groups (SGx) serve in parallel and the most significant digits of the logical block addresses (LBA) in the address converter of the real memory block address (SBA) each parallel to all memory chip groups (SGx) allocated, creating the associated memory blocks (SBn-x) organizationally as a single memory block with a corresponding multiple of sectors be treated. 15. The method according to claim 14, characterized in that deleting the blocks of the individual memory modules with a block addressing staggered in time and Memory module selection takes place that the respective Block addresses (SBA) and a delete command continuously in the individual blocks are adopted and then a block-specific deletion time according to the program waiting in total until another storage op ration is executed. 16. The method according to claim 14, characterized in that the writing of the blocks of the individual memory modules  with such a staggered block and Sector addressing and memory module selection are carried out, that in each case a transfer of information to be written, the addresses of the memory module selection and a write commands are carried out continuously in the individual blocks and then a typical block writing time is waited until further storage operations take place. 17. The method according to claim 14 or 16, characterized in that that after a write or delete operation the controller is put into "powerdown mode" and this mode by an interrupt (INT) after the end of the operation in all memory block groups (SGx) is left again. 18. The method according to claim 17, characterized in that a separate one for each memory module group (SGx) Interrupt signal (SESx) is available.