``Lofgren at al. patented a simple wear-leveling technique that is triggered by eraseunit

reclamation [Lofgren et al. 2000; 2003]. In this technique, the header of each

erase unit includes an erase counter. Also, the system sets aside one erase unit as a

spare. When one of the most worn-out units is reclaimed, its counter is compared

to that of the least worn-out unit. If the difference exceeds a threshold, say 15,000,

a wear-leveling relocation is used instead of a simple reclamation. The contents of

the least-worn out unit (or one of the least-worn out units) are relocated to the

spare unit, and the contents of the most worn out unit, the one whose reclamation

triggered the event, are copied to the just-erased least-worn out unit. The most

worn-out unit that was reclaimed becomes the new spare. This technique attempts

to identify worn-out sectors and static blocks, and to relocate static blocks to

worn-out sectors. In the next wear-leveling event it will be used to store the blocks

from the least-worn out units. Presumably, the data in the least-worn out unit

are relatively static; storing them on a worn-out unit reduces the chances that the

worn-out unit will soon undergo further rapid wear. Also, by removing the static

data from the least worn-out unit, we usually bring its future erase rate close to

the average of the other units.``

=========================================================

``At about the same time, Ban patented a more robust technique [Ban 2004]. His

technique, like the one of Lofgren et al., relies on a spare unit. Every certain number

of reclamations, an erase unit is selected at random, its contents relocated to the

spare unit, and is marked as the new spare. The trigger for this wear-leveling event

can be deterministic, say the 1000th erase since the last event, or random. Using a

random trigger ensures that wear leveling is triggered even if every session is short

and encompasses only a few erase operations. The aim of this technique is to have

ACM Journal Name, Vol. TBD, No. TBD, TBD 20TBD.

12

·

S. Toledo and E. Gal

every unit undergo a fairly large number of random swaps, say 100, during the

lifetime of the flash device. The large number of swaps is supposed to diminish the

likelihood that an erase unit stores static data for much of the device’s lifetime. In

addition, the total overhead of wear leveling in this technique is predictable and

evenly spread in time.

It appears that the idea behind this technique was used in earlier software. M-

Systems developed and marketed software called TrueFFS, a block-mapping device

driver that implements the ftl. The M-Systems literature [Dan and Williams 1997]

states that TrueFFS uses a wear-leveling technique that combines randomness with

erase counts. Their literature claimed that the use of randomness eliminates the

need to protect the exact erase counts stored in each erase unit. The details of the

wear-leveling algorithm of TrueFFS are not described in the open literature or in

patents.``

spare unit(free space) is not mentioned either.

=========================================================

Daberko utilized a similar described free space technique patented in 98....e.Digital may want to look into these 2000; 2003; 2004 developments of free space.

doni