新增NAND写入算法：跳过坏块并重建坏块表

宝剑锋从磨砺出，梅花香自苦寒来；

博观而约取，厚积而薄发。

有心的小伙伴可能在最新的软件版本里会看到，写入NAND时增加了一个新的算法：跳过坏块并重建坏块表 。

以海信5079板，MSD6A801芯片方案为例，先给大家演示RT809H写入NAND新算法。

先找一片坏块较多的Nand芯片，按方向放入RT809H编程器，锁好锁紧座。

点智能识别，选择NAND Falsh，稍等会自动识别到相同ID的芯片型号。

识别出两个芯片型号，选择跟芯片型号一致的K9K8G08U0D@TSOP48。

我们先点一下坏块检测，看看此芯片的坏块分布（坏块检测会破坏NAND芯片内数据，谨慎使用）。

检测到23个坏块，严格来说，基本算是残次品。

点设置，出现三个选项，硬拷贝；跳过坏块并重组数据；跳过坏块并重建坏块表。此板请选择“跳过坏块并重建坏块表 ”。

点写入，选择备份文件，开始自动写入。

可以看到界面上已经显示算法为“跳过坏块并重建坏块表”。

开始写入，耐心等待。。。

写入完成，接下来对写入后的NAND芯片进行验证，先把NAND芯片装回电视板卡。

连接上串口，同时监控打印信息。

通电，看到正常进入系统。同时监控显示画面，直到启动完成。

操作遥控，各项功能正常！

由于NAND使用领域的多样性和NAND自身的特殊性，坏块管理都不尽相同，就拿电视主板来说，我们通过大量板卡测试，和大量时间做了深入研究，发现不同的电视厂家，使用的坏块管理算法都不同，我们特此汇总了三种不同的算法，经过测试已经解决了目前在中国能够见到的电视主板NAND写入问题 。

NAND_AUTO读写芯片时，符合ONFI标准的芯片，读写成功率较高，比如海力士、镁光、ST、华邦等，而三星、东芝等厂商未加入此标准化组织，所以有可能参数识别错误导致读写后不能用，请提交NAND_AUTO读取得到的ID给我们，添加对应的芯片型号即可解决问题 。

国外用户如果遇到NAND读写问题，请提供好的板卡给我们测试。

没有哪种算法可以解决所有NAND复制问题，只能是遇到问题再研究新算法来解决问题。iFix爱修一直致力于为维修行业解决难题。

最近发现大家都在问一个比较实际的问题：RT809H以后会不会想其他编程器厂家一样，相同封装、不同型号的NAND芯片，使用不同的转接座？转接座的写入次数是多少？

这里是正式回答：RT809H编程器写入所有TSOP48封装的NAND芯片，只需要TSOP48通用座就可以了，永远不会限制写入次数！

视频演示，腾讯视频网址： https://v.qq.com/x/page/h0737szc7xu.html

学习课程已更新，欢迎大家进入学习。

入口：公众号首页-精选-案例直播；

目前课程观看已使用专属APP，

支持苹果、安卓手机以及电脑，

微信授权登录即可，

详见微信及QQ通知。

一种基于逻辑页平均更新频率的NAND闪存垃圾回收算法

NAND闪存具有体积小、抗震性能好、功耗低、无运行噪声、存取速度快、便携性好等特点，同时还具有远超传统机械硬盘的读写速度。因此，NAND闪存在各种电子产品中被广泛应用，如手机、U盘、固态硬盘[1-5]。

NAND闪存具有如下特点：

(1)NAND闪存的读写操作以页(page)为单位，擦除操作以块(block)为单位。NAND闪存的写操作耗时远大于读操作，擦除操作耗时远大于写操作。

(2)NAND闪存具有“写前擦除”的特点，即在进行重复写操作之前，必须先对写入的存储区进行擦除操作。

(3)NAND闪存具有“异地更新”的特点。NAND闪存在对一个页进行数据更新时，需要先将要更新的数据写入新的空闲页，然后将原数据页标为无效页。

(4)NAND闪存具有有限的块擦除次数。当某个块的擦除次数超过一定值时，该块将无法进行数据存储，成为“坏块”。

NAND闪存中，会根据情况启动回收块选择策略，对满足回收块选择策略要求的块进行擦除操作，用以回收无效页所占的存储空间，得到足够的空闲空间来进行数据更新操作。

在设计垃圾回收算法时应将减少垃圾回收代价、提高垃圾回收效率作为主要考虑点。同时，还要尽可能使每个物理块均衡地参与到擦除操作中，从而提升闪存磨损均衡程度、延长使用寿命。

MICHAEL W等提出了GR(Greedy)算法[6]。GR算法选择有效页最少的块进行回收。该算法的拷贝代价小，可回收较多的无效页空间。其特点是算法实现简单，回收效率较高。然而，当且仅当文件更新频率均匀时，磨损均衡效果较好。若数据更新频率相差较大，块之间的擦除次数差别较大，磨损均衡效果较差。

KAWAGUCHI A等提出了CB(Cost-Benefit)算法[7]。该算法采用age×(1-u)/2u公式进行回收块选择，其值最大的块将被选择成为回收块。其中u表示有效页在单个块中的比例，即物理块更新的时间差，age表示块的年龄。该算法考虑了块的年龄，因此获得比GR算法更好的效果。

CHIANG M L等提出了CAT(Cost-Age-Times)算法[8]。该算法采用age×(1-u)/(2u×n)公式进行回收块选择。其中u表示单个块中的有效页比例，age表示块的年龄，n表示块擦除次数。该算法在CB基础上考虑了块擦除次数，比CB具有更好的磨损均衡效果。

Yan Hua等提出了FaGC(File-aware Garbage Collection)算法[9]。该算法沿用GR算法的回收块选择策略，且根据逻辑页更新频率进行冷热数据的划分。数据冷热分离时，冷数据分配到擦除次数最多的块，而热数据则分配到擦除次数最少的块。

石乐健等提出了一种基于物理块年龄和逻辑页热度的磨损均衡算法GCbAH(GC based Age and Hot)[10]。该算法选择无效页年龄和最大的块作为回收块。同时，采用了与FaGC不同的热度计算公式来进行冷热数据的划分。在回收时，使用热数据回收策略回收热块，使用冷数据回收策略回收冷块。

综上所述，相较于GR、CB、CAT等经典算法，FaGC和GCbAH考虑了逻辑页的冷热分离，进一步减少了垃圾回收代价，取得了更好的磨损均衡效果。但是，FaGC和GCbAH均采用固定的预设阈值来作为判定冷热数据的标准，并不能准确反映逻辑页的冷热程度。针对这个问题，本文提出了一种基于逻辑页平均更新频率的闪存垃圾回收算法AUFbGC(Average Update Frequency based Garbage Collection Algorithm)。该算法采用了一种新的热度计算公式，并采用逻辑页平均更新频率取代固定阈值作为冷热数据的判定依据，取得了更好的效果。

1 算法描述

1.1 算法原理

NAND闪存进行垃圾回收时有如下操作：

(1)根据回收块选择策略，进行回收块选择；

(2)拷贝回收块中的有效数据至空闲块；

(3)将被拷贝的有效数据所对应的原数据页标记为无效页；

(4)对选中的回收块进行擦除操作；

(5)回收块被擦除后成为空闲块。

如图1所示，AUFbGC算法选择无效页年龄和最大的块作为回收块，根据热度计算公式和新的冷热判定依据，对回收块的有效数据进行冷热分离，并将有效数据存入擦除次数最少的空闲块中。

和垃圾回收过程类似，AUFbGC算法在进行数据异地更新时也采用了冷热分离策略以获得更好的磨损均衡效果。

AUFbGC算法主要包括三种策略：回收块选择策略、冷热数据分离策略和空闲块分配策略。

1.2 回收块选择策略

AUFbGC算法在挑选回收块时有两种策略：采用无效页年龄和选择策略[10-11]和自适应最冷块选择策略[9]。

其中，n为物理块中的无效页数目，agei为物理块中第i页变为无效页的时长。CwA即物理块中无效页的年龄和。CwA值最大的块将被选择成为回收块。采用年龄和进行选择可以兼顾无效页比例高的块和有少量无效页但长期未被回收的块，可获得更好的磨损均衡效果。

同时，算法采用一种自适应策略对最冷块进行回收。自适应最冷块回收策略启动条件如下：

其中，Twl是先前被设置好用于控制磨损均衡程度的阈值，emax是所有块的最大擦除次数，emin是所有块的最小擦除次数。当emax和emin之间的差值增大，Terase值越小，冷块选择策略越容易被调用。若Terase值小于零，则将Terase置零。当一个块的擦除次数超过Terase值时，最冷块回收策略被调用。该策略将选择有最小擦除次数的块作为回收块，以增加选中有较低更新频率的逻辑页的块的几率。如果有多个块具有最小擦除次数，则选择其中含有最少有效页的块作为回收块。在每次冷块回收策略被调用时，Terase值会被计算和更新。

1.3 数据热度定义

在热度判定上，FaGC以更新频率作为判定数据热度的标准，大于预先设置的特定阈值则为热数据，反之则为冷数据。

GCbAH通过上一次判定的热度与热度调节因子相乘作为本次热度的计算标准。当逻辑页两次更新操作的时间差值大于特定值时，逻辑页热度被强制归零，因此不能细分部分数据的冷热程度。此外，GCbAH也采用预先设置的特定阈值作为判断冷热数据的标准。

AUFbGC算法采用更新频率作为衡量冷热数据的指标[12]，每个逻辑页的更新频率可通过如下公式进行计算。

其中，CurrentT是当前时间，IWTi是该逻辑页i的初始写入时间。UPDCi是逻辑页i的更新次数。因此，FREQi代表逻辑页i写操作的更新间隔。

衡量冷热数据的标准如下：

其中，n是物理块的总数，CurrentT是当前时间，AllocT是编号为i的块被分配使用时的时间，ui是该块中有效页的百分比。因此AverFi代表有效页的平均更新频率。而每当回收块选择策略选中回收块后，平均更新频率AverFi会被立刻计算。

当逻辑页的更新频率FREQi小于平均更新频率AverFi，则该逻辑页包含的数据是为热数据；当逻辑页更新频率时间FREQi大于平均更新频率时间AverFi，则为冷数据。

1.4 算法步骤

使用无效页年龄和与自适应最冷块回收策略选择到回收块之后，根据回收块中有效页对应的热度对数据进行冷热分离，具体步骤如下：

(1)根据逻辑页i的当前更新时间CurrentT和初始写入时间IWTi及更新次数UPDCi，根据式(3)得到该逻辑页的更新频率FREQi。

(2)若逻辑页的更新频率FREQi小于平均更新频率AverFi，则该逻辑页包含的数据为热数据；反之则为冷数据；

(3)将数据根据热度进行冷热分离，具有相似热度的有效页将会被存入同一个物理块；

(4)修改更新次数UPDCi，用于下一次热度的计算和更新操作。

2 实验及分析

2.1 实验环境

实验中使用VMware和Ubuntu 12.04平台，使用QEMU搭建嵌入式Linux仿真环境，使用NANDSim来模拟NAND闪存，基于NAND闪存专用文件系统YAFFS2进行测试。

测试程序随机生成16 KB到1 024 KB大小的测试文件，所有测试文件总量占NAND闪存容量的90%。创建文件后，按照齐夫分布[13]对其中15%的文件进行更新操作。

实验中，NAND闪存容量被设置为64 MB，包含512个物理块，由512×64个页组成，其中每个页为2 048 B。为了公平对比不同算法，实验时YAFFS2文件系统的缓存功能被关闭，且都采用aggressive模式以完成垃圾回收。自适应最冷块回收策略采用的阈值和FaGC、GCbAH算法完全一样。

2.2 算法性能分析

本文将AUFbGC算法与GR、CB、CAT、FaGC及GCbAH算法在垃圾回收代价和磨损均衡效果两个方面进行了比对。其中，垃圾回收代价主要考虑块总擦除次数、页总拷贝次数这两个指标，磨损均衡效果主要考虑块最大最小擦除次数差值、块擦除次数标准差这两个指标。同时，通过擦除次数分布图也可直观地观察不同算法的磨损均衡效果。

从图2和图3中可以看出FaGC、GCbAH和AUFbGC算法获得了相对更小的块总擦除次数和页总拷贝次数。这是由于GR、CB、CAT算法中未考虑冷热数据分离，而FaGC、GCbAH和AUFbGC考虑了较为准确的基于逻辑页的冷热分离。在这三种算法当中，FaGC和GCbAH在数据热度进行定义时，均通过与事先设定的阈值进行比较，以划分冷热数据。AUFbGC算法有更准确的热度计算公式和判据，可将热度相近的逻辑页更加准确地放在同一个空闲块中。由于热度相近，这些逻辑页有更大可能同时被更新而变为无效，从而使该数据块有尽可能少的有效页，最终减少有效页拷贝次数和块擦除次数。

在磨损均衡方面，从图4对比中不难看出，GR算法的物理块擦除次数最为分散，CB、CAT算法次之。FaGC、GCbAH和AUFbGC算法相对集中地分布在一个较小区域。其中，AUFbGC算法得到了较为良好的磨损均衡效果，擦除次数分布集中，且分布在较低值。

不同算法的块最大最小擦除次数差值如图5所示，不同算法的擦除次数标准差如图6所示。从图5和图6中可以得出，FaGC、GCbAH和AUFbGC算法在磨损均衡方面相对GR、CB、CAT有更优异的表现。一方面，FaGC、GCbAH和AUFbGC算法获得了远小于GR、CB、CAT算法的块最大最小擦除次数差值；另一方面，这三种算法的擦除次数标准差呈收敛趋势。这是因为GR算法仅考虑回收有效页最少的物理块，未考虑磨损均衡。尽管CB算法考虑了物理块的年龄和有效页的比例，CAT算法在CB算法的基础上增添了块擦除次数的考量，但CB、CAT算法既没有考虑冷热数据分离，对最冷块的回收也不及时。FaGC、GCbAH和AUFbGC算法均采用了冷热数据分离和自适应最冷块回收策略，因此取得了更好的磨损均衡效果。同时，在这三种算法中，FaGC在回收块选择策略上沿用了GR算法，而GCbAH和AUFbGC算法的无效页年龄和回收块选择策略可兼顾对无效页比例高及无效页比例不高但是很长时间未被回收的物理块的回收，让回收块的选择更加均衡。相较于GCbAH算法，AUFbGC算法在定义数据热度时采用动态变化的平均更新频率取代固定阈值作为比较标准，对冷热数据的划分更准确，分类效果更好，且AUFbGC算法不断地将有效数据分配至擦除次数最少的块，以减少不同块擦除次数的差异。因此，AUFbGC算法的磨损均衡效果最好。

3 结论

针对NAND闪存的特点，提出一种基于逻辑页平均更新频率的NAND闪存垃圾回收算法AUFbGC。该算法在FaGC和GCbAH算法基础之上，重新定义了数据热度计算公式和冷热判断依据。实验结果表明，相较于GR、CB、CAT、FaGC和GCbAH算法，AUFbGC算法在NAND闪存垃圾回收代价和磨损均衡方面均取得了更好的效果。

参考文献

[1] KIM J，KIM J M，NOH S H，et al.A space-efficient flash translation layer for CompactFlash systems[J].IEEE Transactions on Consumer Electronics，2002，48(2)：366-375.

[2] 白石，廖学良，胡事民.HFB:一种闪存上的块页混合缓存管理方法[J].清华大学学报(自然科学版)，2012(5)：688-693.

[3] CHEN R，LIN M.Energy-aware buffer management scheme for NAND and flash-based consumer electronics[J].IEEE Transactions on Consumer Electronics，2015，61(4)：484-490.

[4] JIN X，JUNG S，SONG Y H.Write-aware buffer management policy for performance and durability enhancement in NAND flash memory[J].IEEE Transactions on Consumer Electronics，2010，56(4)：2393-2399.

[5] LEE S，JUNG S，SONG Y H.An efficient use of PRAM for an enhancement in the performance and durability of NAND storage systems[J].IEEE Transactions on Consumer Electronics，2012，58(3)：825-833.

[6] WU M.The architecture of eNVy，a non-volatile, main memory storage system[C].The Workshop on Workstation Operating Systems.IEEE，1994：116-118.

[7] KAWAGUCHI A，NISHIOKA S，MOTODA H.A flash-memory based file system[C].USENIX 1995 Technical Conference Proceedings.USENIX Association，1994：13-13.

[8] CHIANG M L，CHANG R C.Cleaning policies in mobile computers using flash memory[J].Journal of Systems & Software，1999，48(3)：213-231.

[9] Yan Hua，Yao Qian.An efficient file-aware garbage collection algorithm for NAND Flash-based consumer[J].IEEE Transactions on Consumer Electronics，2014，60(4)：623-627.

[10] 石乐健，严华.考虑物理块年龄和逻辑页热度的NAND闪存磨损均衡算法[J].小型微型计算机系统，2015，36(11)：2618-2621.

[11] KWON O，KOH K，LEE J，et al.FeGC：an efficient garbage collection scheme for flash memory based storage systems[J].Journal of Systems & Software，2011，84(9)：1507-1523.

[12] HWANG S H，CHOI J H，KWAK J W.Migration cost sensitive garbage collection technique for non-volatile memory systems[J].IEICE Transactions on Information & Systems，2016，99(12)：3177-3180.

[13] LIN M，CHEN S.Efficient and intelligent garbage collection policy for NAND flash-based consumer electronics[J].IEEE Transactions on Consumer Electronics，2013，59(3)：538-543.

作者信息：

黄敏媛，严 华

(四川大学 电子信息学院，四川 成都610065)

相关问答

如何根据u盘固件相关主控参数对译码表修复u盘，提取数据 - 15...

U盘数据恢复软件的详细步骤如下:1)准备:先将U盘通过数据线连接电脑,显示可移动硬盘。2)打开【互盾数据恢复软件】,选择逗U盘手机相机卡恢复地功能按...

如何根据u盘固件相关主控参数对译码表修复u盘，提取数据 - YG...

如果是闪存芯片的主控区域出现坏块导致的故障,换主控板也不行,那么就需要取下flash芯片,用设备读取芯片内容,由于flash数据格式不一,各种主控的算法...

固态硬盘是否会有坏道?

因此,固态硬盘相对而言是更加可靠的硬件设备之一。然而,并不是说固态硬盘就完全不会有坏道。虽然固态硬盘没有磁头和盘片等机械结构,但是NAND闪存。从物理角...

英特尔slc固态硬盘-ZOL问答

现在Intel与镁光研发新的3DNAND堆叠技术,使储存密度大大增加了,闪存也从TLC升...国外有过极限测试,3000PE的MLCSSD,能实际写到6000PE以上才用光坏块重映射。...

你好，win7安装系统下240G固态硬盘分区怎么分，谢谢?

240G固态硬盘装win764位系统,硬盘分区遵循“小分区、少分区”的原则。固态分区不会影响开机速度和性能,固态会使开机速度变快和软件加载速度变快。所谓“小...