首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Solution for wear-leveling

Solution for wear-leveling

作者头像
瓜大三哥
发布2018-02-24 16:22:00
4200
发布2018-02-24 16:22:00
举报
文章被收录于专栏:瓜大三哥瓜大三哥

Flash is a type of electrically-erasable

programmable read-only memory (EEPROM) which is

non-volatile. There are three operations on it: read,

write and erase. Flash chips are divided into erase

units, sometimes called erase blocks. During a write

operation, a bit can be changed from logical one to

logical zero. To change a bit from zero to one, the

whole erase unit has to be erased. The lifetime of an

erase unit depends on the number of erase cycles.

Manufacturers guarantee the number of cycles range

from 10,000 to 1,000,000 per erase unit, after which an

erase unit could wear out and becomes unreliable. To

avoid this, a flash file system has to distribute the erase

cycles around the medium, so-called wear-leveling.

YAFFS2 does not implement any wear-leveling.

For most part, the designer thinks it’s not a problem for

a log-structured file system like YAFFS2 because

usage cycles tend to clear out and reuse areas. But for

small-sized NAND device, it’s still necessary to avoid

heavily uneven using of the blocks. The below is the

algorithm for wear-leveling designed for YAFFS2.

Before garbage collection, we iterate the whole

device to get the dirtiest N blocks.

dirtiest_blocks[i (1<= i <= N)] = { block id };

The smaller the variable i is, the more invalid pages

the block will have, or the dirter. For example,

dirtiest_blocks[1] should be the block which has the

maximum invalid pages. The block that we will select

as garbage collection is:

N - [logM(rand_based_on_current_time%MN)]

The probability of i is:

P(i) = (M(N-i+1)-M(N-i))/MN = (M-1)/Mi

It can guarantee that the probability of each block

selected will depend on “the degree of dirtiness” or the

number of invalid pages. It’s not liner relationship. The

dirter is, the far higher the probability of this block will

be. Even the block N in the array dirtiest_blocks still

has the chance to be selected with the very low

probability.

M and N can be customized by the size of the

NAND device and the limited number of erase cycles.

Suppose M = 1 on the 64M NAND device with

512-byte pages, there are total 32 pages in one block,

so the dirtiest may have 31 invalid pages. If all of them

are invalid pages, it absolutely will be the target as

garbage collection firstly. It is assumed that a NAND

has all the blocks whose invalid pages range from 31 to

1, the probability for each block as the next garbage

collection are:

P[block with 31 invalid pages] = 1/2

P[block with 30 invalid pages] = 1/4

P[block with n invalid pages] = 1/2(32-n)

where P means probability. Any block with invalid

pages may be selected as garbage collection but its

chance depends on how many invalid pages are.

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2016-04-26,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 瓜大三哥 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档