(PICTURE)(PICTURE) (PICTURE)Europäis hes Patentamt
(1 9) (PICTURE) European Patent Offi_e
(PICTURE) Offi_e euroPéen des brevets (1 1 ) E _ O 688 45O B_
(1 2) EUROPEAN PATENT _PECl FICATlON
(45) Date of pUbliCation and mention (51 ) Int CI.6_. _O6F _ 2JO2, _O6F 3/O6
of the grant of the patent_.
11 _11 _1998 BUlletin 1998l46 (86) InternationaI appIication number_.
PCTIUS94lO1848
(21 ) Application number_. 9491 O145.5 (87) International publication number_.
(PICTURE)(22) Date of filing_. 28.O2.1994 wo g4l2ogo6 (15.og.1gg4 _azette 1gg4l21)
(54) FLA_H FILE _Y_TEM
SCHN ELL LOESCHBARE DATEl
(PICTURE)(PICTURE)
SYSTEME DE MEMOlRE FLASH
__
O
_
_
OO
OO N w. h. . h f h bI. . f h . f h f h E .
_ Ote'_ It In nIne mOnt S rOm t e PU ICatIOn O t e mentIOn O t e 9rant O t e UrOPean Patent_ anY PerSOn maY 9IVe
o nOtiCe tO the EUrOpean Patent OffiCe Of OppOSitiOn tO the EUrOpean patent granted. NOtiCe Of OppOSitiOn Shall be filed in
ii a written reasoned statement. It shall not be deemed to have been filed until the opposition fee has been paid. (Art.
w (PICTURE)99(1 ) European Patent Convention). Printed by Jouve, 75OO1 PARIS (FR)
1 EP O 688 45O B1 2
Des_ription of an allocation unit to a physical address of a sector
(allocation unit) within the memory. A further table is
BACKG ROUND OF TH E I NVENTION present for providing information whether a block is an
(PICTURE) active or a reserve block, and whether the block is free
FieId of the Invention 5 or in use. A clean-up operation involves a reallocation
(PICTURE) operation. Thereby all currently active files are moved
This invention relates to an improved system for out of blocks that will eventually be erased. The mapping
storing and retrieving information in flash memories, and table is a linked list, each linked-list chain within the
more particularly to a system that organizes and man- mapping table representing a historical record of the
ages data written to a flash memoy. 1O creation and removal of dirty sectors.
(PICTURE) (PICTURE)SUMMARY OF TH E I NVENTION
As will be appreciated by those skilled in the art, An object of this invention is the provision of a meth-
electrically erasable and programmable read-only 15 od (i.e. , software, firmware of hardware) to control and
memories (E EPROMs) comprised of flash-type, float- manage access to a flash memoy so that the flash
ing-gate transistors have been described in the art and memoy appears to the computer operating system as
are presently commercially available. These so-called a data storage device in which it is possible to read data
flash memories are non-volatile memories similar in from, and write data to, any flash memoy location. A
functionality and performance to EPROM memories, 2O method that allows flash memory to emulate random ac-
with an additional functionality that allows an in-circuit, cess memories and allows existing computer operating
programmable, operation to erase blocks of the memo- systems to provide all other required support in the
ry. In a flash memory, it is not practical to rewrite a pre- same manner provided by standard random access
viously written area of the memory without a preceding memories and independent of the emulation method.
block erase of the area. While this invention will be de- 25 Briefly, this invention contemplates the provision of
scribed in the context of a flash memoy, those skilled a flash memory, virtual mapping system that allows data
in the art will understand that its teachings are also ap- to be continuously written to unwritten physical address
plicable to data storage devices with the same write, locations. The virtual memoy map relates flash memory
read, and block erase before write characteristics as physical location addresses in order to track the location
flash memories. 3O of data in the memory.
In a typical computer system, the operating system The flash memory physical locations are organized
program is responsible for data management of the data as an array of bytes. Each of the bytes in the array is
storage devices that are a part of the system. A neces- assigned a number of address by means of which the
sary, and usually sufficient, attribute of a data storage byte is physically accessible, referred to herein as the
device to achieve compatibility with the operating sys- 35 physical address space. Each of the bytes in the array
tem program is that it can read data from, and write data has a second address, called the virtual address space.
to, any location in the data storage medium. Thus, flash A table, called a virtual map, converts virtual addresses
memories are not compatible with typical existing oper- to physical addresses. Here it should be noted, the vir-
ating system programs, since data cannot be written to tual address space is not necessarily the same size as
an area of flash memory in which data has previously 4O the physical address space.
been written, unless the area is first erased. A contiguous, fixed-length group of physical byte
Software products have been proposed in the prior addresses from a block. For example, assuming a block
art to allow a flash memoy to be managed by existing size of 51 2 bytes, a byte with a physical address of
computer operating programs without modification of 25621 1 is bytes number 21 1 in block 5OO (25621 1 _. 51 2
the operating system program. However, these prior art 45 -- 5OO + 21 1 ). One or more physically contiguous flash
programs operate the flash memory as a ''write once memoy areas (called zones) that can be physically
read many'' device. This prior art software product can- erased using suitable prior art flash memoy technology
not recycle previously written memory locations. When comprise a unit and each unit contains an integral
all locations are eventually written the memoy cannot number of blocks.
be fu_her used without specific user intervention. 5O The virtual memory map is a table in which the first
G B-A-2 251 323 discloses a flash memory that is enty belongs to virtual block O, the second to virtual
block erasable and that includes an active blockfor stor- block 1 , and so on. Associated in the table with each
ing first data and a reserve blockfor storing second data virtual block address there is a corresponding physical
which is a copy of the first data made during a clean-up address. In a read from the flash memoy operation, a
operation prior to erasure of the active block. The re- 55 computer generated address is decoded as a virtual
serve blocks are blocks that provide temporary file back- block address and a byte location within the block. The
up during said clean-up operation. The flash memory virtual memory map is used to convert the virtual block
includes a mapping table for mapping a logical address address to a physical block address; the byte location
2
3 EP O 688 45O B1 4
is the same in the virtual address space and the physical flect the change in the primary map location. The re-
address space. placed block is marked as deleted.
In a write operation, the computer generated ad-
dress is again interpreted as a virtual block address and BRIEF DESCRIPTION OF THE DRAWINGS
a byte location within the block. The virtual memory map 5 (PICTURE)
converts this to physical memory block address. If the The foregoing and other objects, aspects and ad-
flash memory block corresponding to the physical ad- vantages will be better understood from the following
dress is then currently written, it is generally not possible detailed description of a preferred embodiment of the
to write to this physical address. An unwritten block is invention with reference to the drawings, in which_.
therefore located and written to. The virtual memory 1O Figure 1 is a block diagram illustrating functional
map is changed so that the unwritten physical block ad- components of a system in accordance with one em-
dress is mapped to the original virtual address and orig- bodiment of a system in accordance with the teachings
inal physical address is denoted as unusable and re- of this invention.
mains unusable until there is a zone erase operation that Figure 2 is a pictorial illustration of one level of flash
erases the unit that includes that block. lt will be noted 15 memoy organization in accordance with the teachings
that a write operation assumes that an entire block will of this invention.
be rewritten. This is the manner in which computer sys- Figure 3 is a pictorial illustration of how a unit is for-
tems usually access data in a storage media. However, matted.
it will be appreciatedthat in general, anydesired number Figure 4 is a pictorial representation illustrating how
of bytes could be written to the new storage location. 2O the computer generated addresses are mapped to
In a preferred embodiment of the invention, each physical addresses.
unit is assigned a logical unit address that remains un- Figure 5 is a flow diagram illustrating a read opera-
changed as the unit is rewritten into a new physical ad- tion.
dress location in flash memory. The virtual map contains Figure 6 is a flow diagram illustrating a write oper-
references to the logical unit addresses rather than the 25 ation.
physical unit addresses so that data movement during Figure 7 is a pictorial diagram illustrating the status
unit transfers has no effect on the virtual map. of a unit before and after a transfer operation.
Each unit has a usage map of all the blocks within Figure 8 is a flow diagram of a transfer operation.
the unit; the virtual address of a block, if it is mapped, Figure 9 is a flow diagram illustrating the operation
and special characters to denote free blocks and to de- 3O where a major portion of the virtual to physical map is
note unusable blocks. stored in flash memoy.
Unusable blocks of previously written flash memory
are reclaimed by transferring memoy units that include DETAILED DESCRIPTION OF A PREFERRED
the unusable blocks to a reserved unwritten space in the (PICTURE)EMBODIME T
flash memoy. Only the usable blocks are written in the 35 (PICTURE)
transfer operation so that, as rewritten, the locations Referring now to Figure 1 of the drawings, in a typ-
where the unusable blocks were, are not rewritten in the ical system a processor 1 O, in combination with its op-
reserved space and are thus usable. After having been erating system software, issues a series of read and
rewritten, the original memory unit space is flash erased write commands to read from, and write data to, specific
as a unit and thus becomes an unwritten reserved space 4O address locations in a random access memory. As will
to which a subsequent transfer can be made. be appreciated by those skilled in the art, in a random
Also, in a preferred embodiment of the invention, access storage device, such as a disk memoy, data can
the virtual map is stored primarily in the flash memory be written to, or read from, any address location. In the
with only a small seconday virtual map in random ac- system of Figure 1 , the processor 1 O writes data to, and
cess memoy. The virtual map in flash memory is stored 45 reads data from, a flash memory 1 2 in blocks at specific
in blocks and organized into pages whose size is equal address locations. Although zones of the flash memory
to the product of the number of bytes in a block times 1 2 can be erased, currently written address locations
the number of physical block addresses this number of cannot be rewritten until the entire zone is erased. In
bytes represents. A seconday random access memory accordance with the teachings of this invention, a flash
contains the page addresses. ln reading datafor a given 5O memoy controller 1 4 provides a fully rewritable virtual
virtual address, the page number is determined by di- address space so that the flash memory 1 2 emulates a
viding address by the page size. The result indexes the random access memory, such as a disk memory, and
seconday virtual map to find the correct primary virtual the processor operating system software provides all
map block, the remainder is used to calculate the re- other required operating support (such as a file system)
quired physical address for the vi_ual map stored in 55 in the same manner as it provides fora standard random
flash memory. To alter the virtual map in flash memoy, access memoy, and in a manner that is independent of
the altered map is written into a free block and the sec- the flash memory 1 2 and its controller 1 4. A typical sys-
onday map in random access memory is altered to re- tem also includes a conventional random access mem-
3
5 EP O 688 45O B1 6
ory 1 6. It will be appreciated that controller 1 4 functions be written into.
may be carried out in software, firmware of hardware, Since the data moves physically during a unit trans-
and would not necessarily exist as a physically separate fer to an unwritten unit space, the units are assigned
unit as the drawing suggests. Iogical unit numbers that do not change with changes in
Referring now to Figure 2, it illustrates in part the 5 the physical location of the unit in the memory. A virtual
organization of the flash memory. The flash memory has map 31 maps block numbers in the virtual address to
a number of zones labeled here as zone A, zone B, etc. Iogical block address in the first step of a two level ad-
Each zone is comprised of a number of contiguous dress translation. The logical unit address is an address
physical memory locations that can be block erased us- relative to a logical unit number, similar to a physical ad-
ing conventional, well known, flash memoy technology. 1O dress, which is an address relative to a physical unit
The zones are organized as units only four of which are number. The logical unit number is the high order binay
shown, labeled in the drawing as; UNIT #1 , UNIT #6, digits of the logical address and may be derived from
UNIT N-1 and TRANSFER UNIT. Each unit is comprised the logical address by a bit shift operation. The logical
of at least one zone, of a plurality of contiguous zones. address 33 obtained from map 31 includes a logical unit
Here illustrated, each unit is comprised of two zones (i. 15 number along with the offset of the block within the unit.
e., UNIT #1 - zone A and zone B; UNIT #2 - zone C and A logical unit table 35 translates the logical unit
zone D, TRANSFER UNIT - zone x2 and 2x). number to a physical unit number for the logical unit.
Each unit is comprised of an integral number of ad- This two-step address translation procedure obviates
dressable blocks and each block, in turn, is comprised the need to change block addresses in the map when a
of a contiguous, fixed length group of bytes. At all times, 2O unit is moved to a new physical location.
there will be a unit in the memory 1 2 that is unwritten (i. In a read operation thevirtual address 29 comprised
e., TRANSFER UNIT), sothat active blocks in a unit that of a block address, for example, initially is mapped to a
is to be erased can be written to this unwritten unit prior logical unit number and a block offset within the unit in
to erasing the unit. the addressed block. Map 35 maps the unit number 33
Referring now to Figure 3, each unit contains an in- 25 to a physical address 37 for the unit along with the offset
tegral number of contiguous data blocks 21 that are in of the addressed 37 block within the unit, and the ad-
turn comprised of contiguous byte addresses, that can dressed data block is read from this physical location.
be addressed as a block number and offset within the Here it is assumed that data is read and written on a
block. Each block in a unit has a unit can be addressed block basis as is typically done. Of course, data could
by block number and offset with the unit. Each unit has 3O be written and read on a byte basis using the same prin-
a unit header 23 and a map 25 of the allocation status ciple, if desired. Figure 5 is a flow diagram illustrating
of each block in the unit. The unit header 23 includes a this read operation. As previously explained, the virtual
format identifier, and the logical unit number of the unit. address 29 is mapped to a logical address (block 4O) in
Because data must move physically during a unit trans- the first step of a two-step address translation. In the
fer, the unit number preferably remains unchanged even 35 second step, the logical address is mapped to a physical
as the physical location of the unit in the flash memory address in the flash memory, block41 . Data at this phys-
1 2 changes. In addition, the header may also include ical address is read, block 42, which terminates this op-
system-wide information. The block allocation map 25 eration.
has a word for each block that denotes its status and its In a write operation, the virtual address 29 is again
offset in the unit. The status indications are_. ''block free 4O mapped initially to a logic unit number and a block offset
and writable''; ''block deleted and not writable''; ''block within the unit. The controller 1 4 algorithm examines the
allocates and contains user data''; and virtual address block allocation map 25 for this unit. If the block corre-
of the block (back pointer). sponding to this address has been written, a write com-
As previously mentioned, preferably each unit is as- mand cannot be executed at the corresponding physical
signed a logical unit number that does not change, even 45 address. The control algorithm scans the block alloca-
though the physical location in the memory of the unit tion maps 25 for each unit until a free block is located.
change. As illustrated in Figure 4, the computer 1 O gen- The status of the block in the block map 25 atthe original
erated addresses 29 are comprised of a block number unit address is changed to deleted in the block in the
and a block offset. These address are interpreted by the allocation map, and the status of the free block is
flash controller 1 4 as virtual addresses, and a vi_ual 5O changed to written. The virtual map 31 is update so that
map is used to establish a correspondence between the the original virtual address now points to the new logical
virtual address space and physical address space. The address where the write operation is to take place. This
virtual map changes as blocks are rewritten an the vir- logical address is mapped to a physical address, in the
tual address space is therefore dynamic. It should be manner previously described, and the block is written to
noted also that, at any given time, a block or blocks in 55 this address. Figure 6 is a flow diagram illustrating this
the virtual address space may be unmapped to the write operation. In a write operation the virtual address
physical address space, and that blocks in the physical 29 is mapped to a logical unit address, block 45, and the
address space may be unwritten and, therefore, free to unit allocation for the unit is examined, block 46. If in
4
7 EP O 688 45O B1 8
decision block 47 the unit address is free, the unit ad- virtual map identical to the procedures for reading and
dress is mapped to a physical address, block 48, and writing ordinary data explained earlier. The virtual map
data is written to this physical address, block 49, and itself treated in a manner equivalent to the user data in
the operation ends. If the logical address is not free the foregoing description and the virtual map stored in
(block 47), the unit tables are scanned to locate a free 5 random access memory (i.e., secondary virtual map) is
address in the unit allocation tables, block 5O. This new the equivalent of the virtual map in the previous descrip-
Iogical address is mapped to a physical address, block tion.
51 , and the data is written to this physical address, block In this embodiment, the virtual map resides in the
52. The unit allocation tables are updated (block 53) to flash memory 1 2 at negative virtual addresses; ordinay
indicate that the original block is deleted and not writa- 1O space starts at virtual address zero. The virtual map
ble, and that the new block is allocated and contains us- maps the negative address used by itself, so that the
er data. The virtual to logical address map is then up- virtual map residing in flash memory can be read and
dated to point to the new physical address of the data written like ordinay user data, and only the portion of
corresponding to the original virtual address, blocks 54 the virtual map that maps itself (i.e., the secondary vir-
and 55. 15 tual map) resides in random access memory.
To enable reading and writing operations to contin- In a simplified example, assume a virtual map of
ue without limitation, physical memory space is re- 6OOO bytes stored in twelve virtual map blocks, each of
claimed periodically. As explained previously, at least 51 2 bytes. Assuming a four-byte address, each map
one unit of the memory is reserved at all times so that it block can store 1 28 physical addresses. Thus, each
consists entirely of free blocks and serves as a TRANS- 2O block contains the addresses of 64 Kbytes of virtual
FER UNIT. flash memory. Each block of virtual flash memory ad-
Referring now to figure 7, an active unit is selected dresses is considered as a page and the random access
(here, UNIT #M) and all of its currently-mapped active memoy stores the page addresses; (in this example,
blocks are read and then written to the TRANSFER only 48 bytes) mapped to the address blocks. In reading
UNlT. The selected unit #M is then block erased, and it 25 data from a given virtual address, the address is divided
becomes the TRANSFER UNIT while the transfer unit by the page size (64 Kbytes) to obtain a page number
to which the active blocks have been written becomes, in the secondayvirtual map that maps tothe page block
in this example, unit #M. Figure 7 illustrates the status of the primary virtual map where the address is stored.
of the units before and after a transfer operation. Figure With the virtual memoy page block, the procedure to
8 is aflowdiagram ofthistransfer operation. In atransfer 3O map to a specific flash memoy physical address can
operation a unit is selected for transfer, block 6O, and proceed in the manner already described. For example,
the active data blocks in the selected unit are read, block after the virtual address is divided by the page size, the
61 . These active data blocks are then written to the remainder can be divided by the virtual memory block
transfer unit at positions in the transfer unit correspond- size (e.g., 51 2) to obtain an indextothe array of address
ing to the positions at which they were located in the 35 read from flash memory.
original unit, block 62. The original unit selected is then In writing data to a given virtual address, the com-
flash erased, block 63, and the logical to physical ad- puter generated address is also divided bythe page size
dress map is changed so that the selected unit becomes to obtain an index to the seconday virtual map in ran-
the transfer unit and the transfer unit is assigned the unit dom access memory. The secondary virtual map maps
number of the selected unit, block 64. 4O tothe primaryvirtual map, where the primaryvirtual map
The system thus far described requires a virtual block is read; and this is used to map to the physical
map whose contents is freely updated, and such a map block that has been addressed where it is read. As this
may be stored in a conventional random access mem- blockcannot be rewritten, an unwritten block is identified
ory. However, assuming, for example, a block size of and written into in the manner previously described, with
51 2 bytes, since the virtual map contains a enty for 45 the original data block marked as deleted. To update the
each block, and each entry may be, for example, 4 bytes virtual map residing in the flash memoy, essentially the
Iong (i.e., capable of addressing up to 4 Gigabytes of same procedure is followed. The virtual map block, in
memory), a flash memoy of 8O Mbytes would require a its modified form to reflect the new physical location of
memory of 64O Kbytes to store the map tables. In order the address data, is written to an unwritten block in the
to limit the amount of random access memory required 5O flash memoy and the old block is marked as deleted.
to store the virtual map, in a preferred embodiment of The seconday virtual memoy in random access mem-
the invention, a major portion of the map data is stored ory is changed, as needed, to reflect the change in the
in the flash memoy 1 2 itself, and a seconday virtual primay virtual memory block locations.
map that maps virtual addresses from the computer to Figure 9 is a flow diagram of this operation. The first
the primay virtual map is stored in a random access 55 step in this process is to convert a vi_ual address to a
memory, such as memoy 1 6. An important point to be page number, block 7O, and to use the page number to
made here is that the secondary virtual map arrange- locate in RAM 1 6 the address, in flash memory 1 2, of
ment makes the procedure for reading and writing the the relevant page block of the virtual map stored in the
5
9 EP O 688 45O B1 1 O
flash memory, block 21 . The page block of the virtual dress is in a written status_.
map atthis address is readfrom theflash memory (block
72) and used in the manner previously described to a (1 ) examining the blockallocation map
Iocate physical address corresponding to the virtual ad- (25) of at least another one of said
dress for a data read or data write operation. In a data 5 units to identify an unwritten block ad-
write operation, the virtual map page block must be up- dress;
dated, block 73, and the updated page blockvirtual map (2) writing said data into said memory
is written to a free flash memoy physical address loca- (1 2) to said unwritten block address;
tion, block 74. The original flash memory address at (3) changing said block allocation map
which the page blockvirtual map was located is marked 1O (25) for a block in said unit to which
as deleted, block 75, and the RAM memory 1 6 is updat- said virtual address (29) has been
ed to point to the virtual to physical map address for the mapped in step (a) to indicate as de-
updated map, block 76. Ieted said physical block address;
The virtual map can be readily reconstructed upon (4) changing said block allocation map
system startup. The virtual maps residing in flash mem- 15 (25) for a block in the unit in which said
ory are non-volatile and do not require reconstruction. data has been written in step (c)(2) to
The secondary virtual map residing in volatile random indicate as written said previously un-
access memoy can be reconstructed by scanning, at written block address where said data
startup, the block usage map that resides at the top of has been written;
each unit. Blocks marked as mappedtoavirtual address 2O (5) changing said virtual map (31 ) to
are identified, and the seconday virtual map is con- map virtual addresses (29) to physical
structed accordingly. addresses (37) within a unit so that
said virtual map (31 ) maps said virtual
address (29) to the physical address
Claims 25 (37) of said previously unwritten block
in which said data has been written in
1 . Memory management method for a memory (1 2) in step (c) (2), such that said virtual ad-
which data can be written only in unwritten physical dress is not mapped tothe physical ad-
memory locations and in which a zone of contigu- dress (37) of said written block of step
ous memory locations can be simultaneously 3O (c).
erased, comprising the steps of_. 2. Memoy management method according to claim 1 ,
organizing the data in the memory (1 2) into a comprising the steps of_.
plurality of units with each of the units encom-
passing at least one zone; 35 storing in said memory (1 2) a first virtual map
organizing each unit into an integral number of that maps virtual addresses (29) to physical ad-
addressable blocks, each of said blocks being dresses (37) within a unit;
comprised of a plurality of contiguous physical organizing said first virtual map stored in said
memory locations; memoy (1 2) in segments of page addressable
establishing a block allocation map (25) for 4O blocks;
each unit that indicates the status of each block storing in a random access memory (1 6) a sec-
in a unit as either written, or unwritten or delet- ond virtual map that maps page addresses to
ed; physical addresses of said page addressable
establishing a virtual map (31 ) to map virtual blocks in said memory (1 2),
block addresses to physical block addresses 45 changing a page addressable block in said first
within a unit; virtual stored in said memory (1 2) by writing a
in writing data to said memory (1 2) at a virtual changed page addressable block in an unwrit-
address (29)_. ten physical block location; and
updating said second virtual map stored in said
(a) mapping said virtual address (29) to a 5O random access memory (1 6) sothat it maps the
physical block address in a unit; page address of the changed page addressa-
(b) examining said block allocation map ble block to the unwritten physical block loca-
(25) for said unit to which said virtual ad- tion in which said changed page addressable
dress (29) has been mapped in subpara- block has been written.
graph (a) to determine whether the status 55
of a block at said physical block address is 3. Memoy management method according to claim 2
written, or unwritten, or deleted comprising the steps of _.
(c) if said block at said physical block ad- in writing data to said memory (1 2) at a virtual
6
1 1 EP O 688 45O B1 1 2
address (29) by_. allocation map;
periodically identifying a selected unit, other
(a) deriving a page address from said virtual ad- than said transfer unit, to be erased;
dress (29); reading each written block in said selected unit;
(b) mapping said page address to page ad- 5 writing each written block in said selected unit
dressable block in said memoy (1 2); into said transfer unit;
(c) reading a segment of said first virtual map updating said transfer unit allocation map (25)
that maps virtual address (29) to physical ad- to indicate as written the status of blocks that
dress (37); have been written in the just previous writing
(d) mapping said virtual address (29) to a phys- 1O step;
ical address (37) ; erasing said selected unit;
(e) if said block at said physical block address updating said virtual map of virtual addresses
is in a written or deleted status_. (29) to physical addresses (37) to reflect the
movement of written blocks.
(1 ) writing said data into said memoy (1 2) 15
to an unwritten block address_,
(2) changing said first virtual map segment Patentansprü_he
so that said first virtual map maps said vir-
tual address (29) to the physical address 1 . Speicherverwaltungsverfahren für einen Speicher
(37) of the unwritten block in which said da- 2O (1 2), in welchen Daten nur in unbeschriebene phy-
ta has been written in step (e) (1 ); sikalische Speicherplätze geschrieben werden
(3) writing the changed first virtual map können und in welchen eine Zone von benachbar-
segment from step (e) (2) in an unwritten ten Speicherplätzen gleichzeitig gelöscht werden
physical block location in said memoy können, umfassend die Schritte_.
(1 2); 25
(4) updating said second table stored in Organisieren der Daten in dem Speicher (1 2)
said random access memory (1 6) so that it in eine Vielzahl von Einheiten, wobei jede der
maps the page address of the changed first Einheiten wenigstens eine Zone einschließt,
virtual map segment of said unwritten Organisieren jeder Einheit in eine integrale An-
physical block location. 3O zahl von adressierbaren Blöcken, wobei jeder
Block eine Vielzahl von benachbarten physika-
4. Memory management method according to any of lischen Speicherplätzen umfaßt,
claims 1 to 3, wherein the mapping said virtual ad- Errichten eines Blockzuordnungsverzeichnis-
dress (29) to a physical address (37) includes a two- ses (25) für jede Einheit, welches den Zustand
step address translation comprising_. 35 jedes Blockes in einer Einheit als entweder be-
schrieben oder unbeschrieben oder gelöscht
translating the virtual address (29) to a logical anzeigt,
unit address (33) by said virtual map (31 ), and Errichten eines virtuellen Verzeichnisses (31 ),
translating the logical address (33) to said um virtuelle Blockadressen in physikalischen
physical address (37) by a logical unit table 4O Blockadressen innerhalb einer Einheit zu ver-
(35). zeichnen,
Schreiben von Daten in den Speicher (1 2) an
5. A memoy management method according to any einer virtuellen Adresse (29) _.
of claims 1 to 4, comprising of_.
in reading data to said memoy at a virtual ad- 45 (a) Verzeichnen dervirtuellen Adresse (29)
dress by_. in einer physikalischen Blockadresse in ei-
ner Einheit,
(a) mapping said virtual address (29) to a phys- (b) Untersuchen des Blockzuordnungsver-
ical block address in a unit; zeichnisses (25) für die Einheit, in welche
(b) reading said data from said memoy (1 2) at 5O die virtuelle Adresse (29) in Unterabschnitt
said physical address (37). (a) verzeichnet worden ist, um zu bestim-
men, ob der Zustand eines Blockes an ei-
6. Memory management method according to any of ner physikalischen Blockadresse be-
claims 1 to 5, including the further steps of_. schrieben oder unbeschrieben oder ge-
55 löscht ist,
establishing a transfer unit in said memory (1 2) (c) wenn sich der Block an der physikali-
in which all blocks of said unit are unwritten, schen Blockadresse in beschriebenem Zu-
said transfer unit including a transfer unit block stand befindet_.
7
1 3 EP O 688 45O B1 1 4
(1 ) Untersuchen des Blockzuord- Aktualisieren des zweiten virtuellen Verzeich-
nungsverzeichnisses (25) von wenig- nisses, das in dem Direktzugriffsspeicher (1 6)
stens einer anderen der Einheiten, um gespeichert ist, derart, daß es die Seitenadres-
eine unbeschriebene Blockadresse zu se des geänderten seitenadressierbaren Blok-
identifizieren, 5 kes in der unbeschriebenen physikalischen
(2) Schreiben der Daten in den Spei- Blockzuordnung, in welche der geänderte sei-
cher (1 2) zu der unbeschriebenen tenadressierbare Block geschrieben worden
Blockadresse, ist, verzeichnet.
(3) Ändern des Blockzuordnungsver-
zeichnisses (25) für einen Block in der 1O 3. Speicherverwaltungsverfahren nach Anspruch 2,
Einheit, in welchem die virtuelle Adres- umfassend die Schritte_.
se (29) in Schritt (a) verzeichnet wor- Einschreiben von Daten in den Speicher (1 2) an ei-
den ist, um sie als gelöschte physika- ner virtuellen Adresse (29) durch_.
lische Blockadresse anzuzeigen,
(4) Ändern des Blockzuordnungsver- 15 (a) Ableiten einer Seitenadresse aus einer vir-
zeichnisses (25) für einen Block in der tuellen Adresse (29),
Einheit, in welche die Daten in Schritt (b) Verzeichnen der Seitenadresse in einem
(c) (2) geschrieben worden sind, um seitenadressierbaren Block in dem Speicher
sie als geschriebene, zuvor unbe- (1 2),
schriebene Blockadresse, an welcher 2O (c) Lesen eines Segmentes des ersten virtuel-
die Daten geschrieben worden sind, len Verzeichnisses, das eine virtuelle Adresse
anzuzeigen, (29) in einer physikalischen Adresse (37) ver-
(5) Ändern des virtuellen Verzeichnis- zeichnet,
ses (31 ), um virtuelle Adressen (29) in (d) Verzeichnen der virtuellen Adresse (29) in
physikalische Adressen (37) in einer 25 einer physikalischen Adresse (37),
Einheit zu verzeichnen, derart, daß (e) wenn sich der Block an der physikalischen
das virtuelle Verzeichnis (31 ) die virtu- Blockadresse in einem geschriebenen oder ge-
elle Adresse (29) in die physikalische löschten Zustand befindet_.
Adresse (37) des zuvor unbeschriebe-
nen Blockes, in welchen die Daten in 3O (1 ) Schreiben der Daten in den Speicher
Schritt (c) (2) geschrieben worden (1 2) an einer unbeschriebenen Block-
sind, zu verzeichnen, derart, daß die adresse,
virtuelle Adresse nicht in der physika- (2) Ändern des ersten virtuellen Verzeich-
lischen Adresse (37) des geschriebe- nissegmentes, derart, daß das erste virtu-
nen Blockes des Schrittes (c) ver- 35 elle Verzeichnis die virtuelle Adresse (29)
zeichnet wird. in der physikalischen Adresse (37) des un-
beschriebenen Blockes, in welchem die
2. Speicherverwaltungsverfahren nach Anspruch 1 , Daten in Schritt (e) (1 ) geschrieben worden
umfassend die Schritte_. sind, verzeichnet,
4O (3) Schreiben des geänderten ersten virtu-
Speichern eines ersten virtuellen Verzeichnis- ellen Verzeichnissegments aus Schritt (e)
ses in dem Speicher (1 2), das virtuelle Adres- (2) in einen unbeschriebenen physikali-
sen (29) in physikalische Adressen (37) in einer schen Blockplatz in dem Speicher (1 2),
Einheit abbildet, (4) Aktualisieren der in dem Direktzugriffs-
Organisieren des in dem Speicher (1 2) gespei- 45 speicher (1 6) gespeicherten zweiten Ta-
cherten ersten virtuellen Verzeichnisses in belle, derart, daß sie die Seitenadresse
Segmente von seitenadressierbaren Blöcken, des geänderten ersten virtuellen Verzeich-
Speichern eines zweiten virtuellen Verzeichnis- nissegmentes des unbeschriebenen phy-
ses in einem Direktzugriffsspeicher (1 6), das sikalischen Blockplatzes verzeichnet.
Seitenadressen in physikalische Adressen der 5O
seitenadressierbaren Blöcke in dem Speicher 4. Speicherverwaltungsverfahren nach einem der An-
(1 2) abbildet, sprüche 1 bis 3, bei welchem das Verzeichnen der
Ändern eines seitenadressierbaren Blockes in virtuellen Adresse (29) in einer physikalischen
dem ersten virtuellen Verzeichnis, das in dem Adresse (37) eine Zwei-Schritt-Adressenüberset-
Speicher (1 2) gespeichert ist, durch Schreiben 55 zung umfaßt_.
eines geänderten seitenadressierbaren Blok-
kes in eine unbeschriebene physikalische übersetzen der virtuellen Adresse (29) in eine
Blockzuordnung, und logische Einheitsadresse (33) durch das virtu-
8
1 5 EP O 688 45O B1 1 6
elle Verzeichnis (31 ), und organiser chaque ensemble en un nombre en-
übersetzen der logischen Adresse (33) in die tier de blocs adressables, chacun desdits blocs
physikalische Adresse (37) durch eine logische étant formé d'une pluralité d'emplacements
Einheitstabelle (35). contigus de mémoire physique ;
5 établir une carte (25) d'attribution de blocs pour
5. Speicherverwaltungsverfahren nach einem der An- chaque ensemble qui indique l'état de chaque
sprüche 1 bis 4, umfassend_. bloc dans un ensemble comme étant soit écrit,
Einlesen von Daten in den Speicher an einer virtu- soit non écrit, soit supprimé ;
ellen Adresse_. établir une carte virtuelle (31 ) faire correspon-
1O dre des adresses vi_uelles de blocs aux adres-
(a) Verzeichnen der virtuellen Adresse (29) in ses physiques de blocs à l'intérieur d'un
einer physikalischen Blockadresse in einer Ein- ensemble ;
heit, quand on écrit des données dans ladite mémoi-
(b) Lesen der Daten aus dem Speicher (1 2) an re (1 2) à une adresse virtuelle (29) _.
der physikalischen Adresse (37). 15 (a) faire correspondre ladite adresse vir-
6. Speicherverwaltungsverfahren nach einem der An- tuelle (29) à une adresse physique de bloc
sprüche 1 bis 5, umfassend die weiteren Schritte_. dans un ensemble ;
(b) examiner ladite carte (25) d'attribution
Errichten einer übertragungseinheit in dem 2O de blocs pour ledit ensemble auquel on a
Speicher (1 2), in welchem sämtliche Blöcke der fait correspondre, dans le sous paragraphe
Einheit unbeschrieben sind, (a), ladite adresse virtuelle (29), afin de dé-
wobei die übertragungseinheit ein terminer si l'état d'un bloc à ladite adresse
übertragungseinheitsblockzu- physique de bloc est écrit, non écrit, ou
ordnungsverzeichnis beinhaltet, 25 supprimé,
periodisches Identifizieren einer zu löschen- (c) si ledit bloc à ladite adresse physique
den, zu der übertragungseinheit unterschiedli- de bloc est dans un état écrit _.
chen ausgewählten Einheit, Lesen jedes ge-
schriebenen Blockes in die ausgewählte Ein- (1 ) examiner la carte (25) d'attribution
heit, 3O de bloc d'au moins un autre desdits en-
Schreiben jedes geschriebenen Blockes in der sembles pour identifier une adresse
ausgewählten Einheit in die übertragungsein- de bloc non écrit ;
heit, (2) écrire lesdites données dans la dite
Aktualisieren des übertragungseinheitezuord- mémoire (1 2) à ladite adresse de bloc
nungsverzeichnisses (25), um den Zustand der 35 non écrit ;
Blöcke, die in dem gerade vorhergehenden (3) modifier ladite carte (25) d'attribu-
Schritt zum Schreiben geschrieben worden tion de blocs pour un bloc dans ledit
sind, als geschrieben anzuzeigen, ensemble auquel on a fait correspon-
Löschen der ausgewählten Einheit, dre ladite adresse virtuelle (29) à l'éta-
Aktualisieren des virtuellen Verzeichnisses der 4O pe (a) pour indiquer comme étant sup-
virtuellen Adressen (29) in physikalische primée ladite adresse physique de
Adressen (37), um die Bewegung der geschrie- bloc ;
bene Blöcke zu reflektieren. (4) modifier ladite carte (25) d'attribu-
tion de blocs pour un bloc dans l'en-
45 semble dans lequel lesdites données
Revendi_ations ont été écrites à l'étape (c) (2) pour in-
diquer comme écrite ladite adresse de
1 . Procédé de gestion de mémoire pour une mémoire bloc précédemment non écrite où les-
(1 2) dans laquelle les données peuvent être inscri- dites données ont été écrites ;
tes seulement dans des emplacements de mémoire 5O (5) modifier ladite carte (31 ) virtuelle
physique non inscrits et dans laquelle une zone pour faire correspondre des adresses
d'emplacements contigus de la mémoire peut être virtuelles (29) à des adresses physi-
simultanément effacée, comprenant les étapes ques (37) à l'intérieur d'un ensemble
consistant à _. de sorte que ladite carte virtuelle (31 )
55 fait correspondre ladite adresse vir-
organiser les données dans la mémoire (1 2) en tuelle (29) à l'adresse physique (37)
une pluralité d'ensembles, chacun des ensem- dudit bloc précédemment non écrit
bles englobant au moins une zone ; dans lequel lesdites données ont été
9
1 7 EP O 688 45O B1 1 8
écrites à l'étape (c) (2), de sorte que ont été écrites à l'étape (e) (1 ) ;
l'adresse virtuelle ne corresponde pas (3) écrire le premier segment de carte vir-
à l'adresse physique (37) dudit bloc tuelle modifié à partir de l'étape (e)(2) dans
écrit de l'étape (c). un emplacement de bloc physique non
5 écrit dans ladite mémoire (1 2) ;
2. Procédé de gestion de mémoire selon la revendi- (4) mettre à jour ladite seconde table stoc-
cation 1 comprenant les étapes consistant à _. kée dans ladite mémoire (1 6) à accès aléa-
toire de sorte qu'elle établit une correspon-
stocker dans ladite mémoire (1 2) une première dance pour l'adresse de page du premier
carte virtuelle qui fait correspondre des adres- 1O segment de carte virtuelle modifié dudit
ses virtuelles (29) à des adresses physiques emplacement de bloc physique non écrit.
(37) à l'intérieur d'un ensemble ;
organiser ladite première carte virtuelle stoc- 4. Procédé de gestion de mémoire selon l'une des re-
kée dans ladite mémoire (1 2) en segments de vendications 1 à 3 dans lequel la correspondance
blocs adressables par page ; 15 entre ladite adresse virtuelle (29) et une adresse
stocker dans une mémoire (1 6) à accès aléa- physique (37) comporte une translation d'adresse
toire une seconde carte virtuelle qui fait corres- à deux étapes comprenant _.
pondre des adresses de page à des adresses
physiques desdits blocs adressables de page la translation de l'adresse virtuelle (29) vers
dans ladite mémoire (1 2), 2O une adresse (33) d'ensemble logique à l'aide
modifier un bloc adressable par page dans la- de ladite carte virtuelle (31 ), et
dite première carte virtuelle stockée dans ladite la translation de l'adresse logique (33) vers la-
mémoire (1 2) en écrivant un bloc adressable dite adresse physique (37) par une table (35)
par page modifié dans un emplacement de bloc d'ensemble logique.
physique non écrit _, et 25
mettre à jour ladite seconde carte virtuelle stoc- 5. Procédé de gestion de mémoire selon l'une des re-
kée dans la dite mémoire (1 6) à accès aléatoire vendications 1 à 4 consistant à _.
de sorte qu'elle fait correspondre l'adresse de quand on lit des données dans ladite mémoire
page du bloc adressable par page modifié à à une adresse virtuelle _.
l'emplacement de bloc physique non écrit dans 3O
Iequel ledit bloc adressable par page modifié a (a) faire correspondre ladite adresse virtuelle
été écrit. (29) à une adresse de bloc physique dans un
ensemble _,
3. Procédé de gestion de mémoire selon la revendi- (b) lire lesdites données dans ladite mémoire
cation 2 comprenant les étapes consistant à _. 35 (1 2) à ladite adresse physique (37).
quand on écrit des données dans ladite mé-
moire (1 2) à une adresse virtuelle (29) _. 6. Procédé de gestion de mémoire selon l'une des re-
vendications 1 à 5 comprenant les étapes supplé-
(a) déduire une adresse de page de ladite mentaires consistant à _.
adresse virtuelle (29) ; 4O
(b) faire correspondre ladite adresse de page établir un ensemble de transfert dans ladite mé-
à un bloc adressable par page dans ladite mé- moire (1 2) dans lequel tous les blocs dudit en-
moire (1 2) ; semble ne sont pas écrits, cet ensemble de
(c) lire un segment de ladite première carte vir- transfert comportant une carte d'attribution de
tuelle qui fait correspondre une adresse virtuel- 45 blocs d'ensemble de transfert _,
Ie (29) à une adresse physique (37) ; identifier périodiquement un ensemble sélec-
(d) faire correspondre ladite adresse virtuelle tionné, autre que ledit ensemble de transfert,
(29) à une adresse physique (37) ; qui doit être effacé ;
(e) si ledit bloc à ladite adresse de bloc physi- lire chaque bloc écrit dans ledit ensemble
que est dans un état écrit ou supprimé _. 5O sélectionné _,
écrire dans ledit ensemble de transfert chaque
(1 ) écrire lesdites données dans ladite mé- bloc écrit dans ledit ensemble sélectionné ;
moire (1 2) à une adresse de bloc non écrit ; mettre à jour ladite carte (25) d'attribution d'en-
(2) modifier ledit premier segment de carte semble de transfert pour indiquer comme étant
virtuelle de sorte que ladite première carte 55 écrit l'état des blocs qui ont été écrits dans l'éta-
virtuelle fait correspondre ladite adresse pe d'écriture immédiatement précédente ;
virtuelle (29) à l'adresse physique (37) du effacer ledit ensemble sélectionné ;
bloc non écrit dans lequel lesdites données mettre à jour ladite carte virtuelle d'adresses
1 O
1 9 EP O 688 45O B1 2O
virtuelles (29) à des adresses physiques (37)
pour représenter le mouvement des blocs
écrits. 5
1O
15
2O
25
3O
35
4O
45
5O
55
(PICTURE)_ _ _ _ _ + _ _ _ _ _
EP O 688 45O B1
Fl G . 1
Fl G . 2
F__H
ME(PICTURE)(PICTURE)
(PICTURE)
_1 _, z_N-E -xx 1 -z__-__-_I
1,, '_,_ '- I_ UNIT N- 1
_6 ''i,,
''i,,
'',,,,
Ill_ Ill_ tl_ T_AN_FE_
i,, ZONE XZ i,, lONE Z __i,, uN_T
12
(PICTURE) (PICTURE)
EPO68845O B1
(PICTURE)
2_
25 _
F__ _ 21
' 21
21
FIG.7
_EFORE AFTER
LOGICAL UNIT TRANSFER UNIT TRANSFER UNIT LOGICAL UNIT
(PICTURE)
_ _ (PICTURE) (PICTURE)
_ _
(PICTURE)
EP O 688 45O B1
29 \
(PICTURE)
\_ . _ __O_K OFFSET S
FIG.4 4O
(PICTURE)' 41
(PICTURE)
FIG.5
_ 42
14
(PICTURE)
EP O 688 45O B1
__ _ . 6 (PICTURE)
_ 45
(PICTURE)
46
4
49 15
(PICTURE)
EP O 688 45O B1
_
_
_ OO
_
(PICTURE)_
(PICTURE)O O O O o
16