专栏首页瓜大三哥Solution for wear-leveling

Solution for wear-leveling

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.

本文分享自微信公众号 - 瓜大三哥(xiguazai_tortoise),作者:xiguazaitortoise

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2016-04-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • How do I reset my FPGA?

    Editor’s Note: This article first appeared in the Summer 2011 issue of Xcell Jou...

    瓜大三哥
  • Zynq中PS端XADC

    XADC内嵌在PS端,允许CPU或其他主机连接XADC,而不用使用PL端。XADC最大采样率为1MSPS,精度为12bits,内置电压和温度传感器,可监测芯片的...

    瓜大三哥
  • 视频压缩编码技术(H.264) 之结构

    视频的一场或一帧可用来产生一个编码图像。通常,视频帧可分成两种类型:连续或隔行视频帧。在电视中,为减少大面积闪烁现象,把一帧分成两个隔行的场。显然,这时场内邻行...

    瓜大三哥
  • Codeforce-CodeCraft-20 (Div. 2)-B. String Modification (找规律+模拟)

    Vasya has a string s of length n. He decides to make the following modification ...

    风骨散人Chiam
  • 多语言姿态检测:加泰罗尼亚独立语料库(CS.CL)

    姿态检测旨在确定给定文本相对于特定主题或主张的态度。尽管最近几年对姿势检测进行了很好的研究,但大多数工作都集中在英语上。这主要是由于其他语言中相对缺少带注释的数...

    蔡小雪7100294
  • 机器人控制器编程课程-教案02-基础

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    zhangrelay
  • Hyperledger Fabric中的零知识证明

    Fabric 1.3中的新增的idemixer(Identity Mixer)以前不大懂zero-knowledge proof(零知识证明),原本觉得PKI基...

    Zeal
  • SPINNING单车你需要知道的一些事(一)单车怎么调整

    • If toe cages and straps are used, be sure to align the ball of your foot over ...

    小飞侠xp
  • Ceph用户邮件列表Vol45-Issue3

    https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=af5e5...

    用户2772802
  • 低观测分配系统中状态估计的联合矩阵完成和压缩感知(CS)

    配电网有限的测量可用性对状态估计和态势感知提出了挑战。本文结合了最近提出的两种基于稀疏性的状态估计方法(矩阵完成和压缩感测)的优势,以应对不可观测性的挑战。所提...

    Alfred_Yip

扫码关注云+社区

领取腾讯云代金券