linux 读写nand 智能座舱之存储篇第三篇---NAND Flash 一眼就看明白了-报价-上海羊羽卓进出口贸易有限公司

linux 读写nand 智能座舱之存储篇第三篇---NAND Flash 一眼就看明白了

发布时间 : 2024-10-07

作者 : 小编

访问数量 : 23

扫码分享至微信

智能座舱之存储篇第三篇---NAND Flash 一眼就看明白了

上期内容我们重点说了NAND FLASH本身的一些特殊性，比如写之前要进行擦除，而且存在坏块的可能性性，所以很多车厂在评估NAND FLASH的时候，会评估目前容量的冗余量是多少，要保障有足够多的空间去预防坏块的产生后的数据搬移。

这期内容重点说说NAND FLASH的一些操作特性，怎么进行控制和读取的。这期的内容有点硬核，需要有一些专业知识的人进行阅读，科普类的文章咱们下期继续。

NAND FLASH的硬件特性介绍

上图是镁光 NAND FLASH MT29F1G08ABAEAH4的引脚（Pin）所对应的功能，简单翻译如下：

1. I/O0 ~ I/O7：用于输入地址/数据/命令，输出数据

2. CLE：Command Latch Enable，命令锁存使能，在输入命令之前，要先在模式寄存器中，设置CLE使能

3. ALE：Address Latch Enable，地址锁存使能，在输入地址之前，要先在模式寄存器中，设置ALE使能

4. CE#：Chip Enable，芯片使能，在操作Nand Flash之前，要先选中此芯片，才能操作

5. RE#：Read Enable，读使能，在读取数据之前，要先使CE＃有效。

6. WE#：Write Enable，写使能,在写取数据之前，要先使WE＃有效。

7. WP#：Write Protect，写保护

8. R/B#:Ready/Busy Output,就绪/忙,主要用于在发送完编程/擦除命令后,检测这些操作是否完成,忙,表示编程/擦除操作仍在进行中,就绪表示操作完成.

9. Vcc：Power，电源

10. Vss：Ground，接地

11. N.C：Non-Connection,未定义，未连接。

实际项目的NAND FLASH原理图

上图中我们可以发现有两个地方需要上拉电阻R/B#:、WP#，其他都是CPU同nand flash直接相连接。通过查询flash 的datasheet可以发现，这两个引脚是开漏极输出，需要上拉电阻。

而且可以看到电路设计中WP#引脚一端接上拉电阻，一端通过二极管和0欧姆电阻连接到CPU复位引脚，CPU主芯片平台的复位是低电平复位，WP#引脚是低电平的时候写保护有效，这样做的目的就是，在复位期间，即CPU复位引脚为低电平期间此时WP#引脚也为二极管电压（0.7V）为低电平，为写保护状态，在复位期间，CPU引脚状态不定，容易对flash进行误操作。这样做的目的就是硬件实现在CPU复位期间，flash是写保护状态，不允许写入的。

很多时候掉电产生的擦除数据，导致数据丢失无法开机、无法保存掉电记忆等等问题都可以使用这个方案来对策解决问题。

为何需要ALE和CLE

比如命令锁存使能(Command Latch Enable,CLE)和地址锁存使能(Address Latch Enable，ALE)，那是因为，Nand Flash就8个I/O，而且是复用的，也就是，可以传数据，也可以传地址，也可以传命令，为了区分你当前传入的到底是啥，所以，先要用发一个CLE（或ALE）命令，告诉nand Flash的控制器一声，我下面要传的是命令（或地址），这样，里面才能根据传入的内容，进行对应的动作。否则,nand flash内部,怎么知道你传入的是数据,还是地址,还是命令啊,也就无法实现正确的操作了。

Nand Flash只有8个I/O引脚的好处

1. 减少外围引脚：相对于并口(Parellel)的Nor Flash的48或52个引脚来说，的确是大大减小了引脚数目，这样封装后的芯片体积，就小很多。现在芯片在向体积更小，功能更强，功耗更低发展，减小芯片体积，就是很大的优势。同时，减少芯片接口，也意味着使用此芯片的相关的外围电路会更简化，避免了繁琐的硬件连线。

2. 提高系统的可扩展性，因为没有像其他设备一样用物理大小对应的完全数目的addr引脚，在芯片内部换了芯片的大小等的改动，对于用全部的地址addr的引脚，那么就会引起这些引脚数目的增加，比如容量扩大一倍，地址空间/寻址空间扩大一倍，所以，地址线数目/addr引脚数目，就要多加一个，而对于统一用8个I/O的引脚的Nand Flash，由于对外提供的都是统一的8个引脚，内部的芯片大小的变化或者其他的变化，对于外部使用者(比如编写nand flash驱动的人)来说，不需要关心，只是保证新的芯片，还是遵循同样的接口，同样的时序，同样的命令，就可以了。这样就提高了系统的扩展性。

片选无关(CE don’t-care)技术

Nand flash支持一个叫做CE don’t-care的技术，字面意思就是，不关心是否片选，那有人会问了，

如果不片选，那还能对其操作吗？答案就是，这个技术，主要用在当时是不需要选中芯片却还可以继续操作的这些情况：在某些应用，比如录音，音频播放等应用中，外部使用的微秒（us）级的时钟周期，此处假设是比较少的2us，在进行读取一页或者对页编程时，是对Nand Flash操作，这样的串行（Serial Access）访问的周期都是20/30/50ns，都是纳秒（ns）级的，此处假设是50ns，当你已经发了对应的读或写的命令之后，接下来只是需要Nand Flash内部去自己操作，将数据读取除了或写入进去到内部的数据寄存器中而已，此处，如果可以把片选取消，CE#是低电平有效，取消片选就是拉高电平，这样会在下一个外部命令发送过来之前，即微秒量级的时间里面，即2us－50ns≈2us，这段时间的取消片选，可以降低很少的系统功耗，但是多次的操作，就可以在很大程度上降低整体的功耗了。

总结起来简单解释就是：由于某些外部应用的频率比较低，而Nand Flash内部操作速度比较快，所以具体读写操作的大部分时间里面，都是在等待外部命令的输入，同时却选中芯片，产生了多余的功耗，此“不关心片选”技术，就是在Nand Flash的内部的相对快速的操作（读或写）完成之后，就取消片选，以节省系统功耗。待下次外部命令/数据/地址输入来的时候，再选中芯片，即可正常继续操作了。这样，整体上，就可以大大降低系统功耗了。

NAND FLASH 的读操作详细解读

以最简单的read操作为例，解释如何理解时序图，以及将时序图中的要求，转化为代码。解释时序图之前，让我们先要搞清楚，我们要做的事情：那就是，要从nand flash的某个页里面，读取我们要的数据。要实现此功能，会涉及到几部分的知识，至少很容易想到的就是：需要用到哪些命令，怎么发这些命令，怎么计算所需要的地址，怎么读取我们要的数据等等。

就好比你去图书馆借书，想想是一个什么样的流程，首先得告诉馆长你要要借书还是还书、然后把要借书的位置告诉馆长，最后是把图书卡或者借书证件给馆长，此时就耐心等待要借的书籍了。

下面，就一步步的解释，需要做什么，以及如何去做：

1.需要使用何种命令

首先，是要了解，对于读取数据，要用什么命令。

下面是datasheet中的命令集合：

很容易看出，我们要读取数据，要用到Read命令，该命令需要2个周期，第一个周期发0x00，第二个周期发0x30。

2.发送命令前的准备工作以及时序图各个信号的具体含义

知道了用何命令后，再去了解如何发送这些命令。

Nand Flash数据读取操作的时序图

注：此图来自镁光的型号MT29F1G08ABAEAH4:E的nand flash的数据手册(datasheet)。

我们来一起看看，我在图中的特意标注的①边上的红色竖线。

红色竖线所处的时刻，是在发送读操作的第一个周期的命令0x00之前的那一刻。让我们看看，在那一刻，其所穿过好几行都对应什么值，以及进一步理解，为何要那个值。

（1）红色竖线穿过的第一行，是CLE。还记得前面介绍命令所存使能（CLE）那个引脚吧？CLE，将CLE置1，就说明你将要通过I/O复用端口发送进入Nand Flash的，是命令，而不是地址或者其他类型的数据。只有这样将CLE置1，使其有效，才能去通知了内部硬件逻辑，你接下来将收到的是命令，内部硬件逻辑，才会将受到的命令，放到命令寄存器中，才能实现后面正确的操作，否则，不去将CLE置1使其有效，硬件会无所适从，不知道你传入的到底是数据还是命令了。

（2）而第二行，是CE#，那一刻的值是0。这个道理很简单，你既然要向Nand Flash发命令，那么先要选中它，所以，要保证CE#为低电平，使其有效，也就是片选有效。

（3）第三行是WE#，意思是写使能。因为接下来是往nand Flash里面写命令，所以，要使得WE#有效，所以设为低电平。

（4）第四行，是ALE是低电平，而ALE是高电平有效，此时意思就是使其无效。而对应地，前面介绍的，使CLE有效，因为将要数据的是命令，而不是地址。如果在其他某些场合，比如接下来的要输入地址的时候，就要使其有效，而使CLE无效了。

（5）第五行，RE#，此时是高电平，无效。可以看到，知道后面低6阶段，才变成低电平，才有效，因为那时候，要发生读取命令，去读取数据。

（6）第六行，就是我们重点要介绍的，复用的输入输出I/O端口了，此刻，还没有输入数据，接下来，在不同的阶段，会输入或输出不同的数据/地址。

（7）第七行，R/B#,高电平，表示R（Ready）/就绪，因为到了后面的第5阶段，硬件内部，在第四阶段，接受了外界的读取命令后，把该页的数据一点点送到页寄存器中，这段时间，属于系统在忙着干活，属于忙的阶段，所以，R/B#才变成低，表示Busy忙的状态的。

介绍了时刻①的各个信号的值，以及为何是这个值之后，相信，后面的各个时刻，对应的不同信号的各个值，大家就会自己慢慢分析了，也就容易理解具体的操作顺序和原理了。

3.如何计算出，我们要传入的地址

在介绍具体读取数据的详细流程之前，还要做一件事，那就是，先要搞懂我们要访问的地址，以及这些地址，如何分解后，一点点传入进去，使得硬件能识别才行。

此处还是以MT29F1G08ABAEAH4:E为例，此nand flash，一共有1024个块，每个块内有64页，每个页是2K+64 Bytes，假设，我们要访问其中的第1000个块中的第25页中的1208字节处的地址，此时，我们就要先把具体的地址算出来：

物理地址=块大小×块号+页大小×页号+页内地址=1000×128K+2K×25+1208=0x7D0CCB8,接下来，我们就看看，怎么才能把这个实际的物理地址，转化为nand Flash所要求的格式。

在解释地址组成之前，先要来看看其datasheet中关于地址周期的介绍：

图 Nand Flash的地址周期组成

结合时序图的2，3阶段，我们可以看出，此nand flash地址周期共有4个，2个列(Column)周期，2个行（Row）周期。

而对于对应的，我们可以看出，实际上，列地址CA0~CA10，就是页内地址，11位地址范围是从0到2047，即2K,而多出的A11，理论上可以表示2048～4095，但是实际上，上述规格书中说明当CA11为1时，CA【10：6】都必须为0，所以我们最多也只用到了2048～2112，用于表示页内的oob区域，其大小是64字节。

PA0～PA5，称作页号，页的号码，可以定位到具体是哪一个页。由6个位控制，最多寻址64页，符合规格书中的一块有64页。

而其中，BA6～BA15，表示对应的块号，即属于哪个块,有10个位控制，寻址范围为1024个块。

// 可见：地址的传输顺序是是页内地址，页号，块号。从小到大。

简单解释完了地址组成，那么就很容易分析上面例子中的地址了：

0x7D0CCB8 = 0111 1101 0000 1100 0000 1100 1011 1000，分别分配到4个地址周期就是：

1st 周期，CA7～CA0 ：1011 1000 = 0x B8

2nd周期，CA11～CA8 ：0000 1100 = 0x 0C

3rd周期，BA7～PA0 ：0000 1100 = 0x 0C

4th周期，A27～A20 ：0111 1101 = 0x 7D

注意，上图图中对应的，*L，意思是低电平，由于未用到那些位，datasheet中强制要求设为0，所以，才有上面的2nd周期中的高4位是0000.。因此，接下来要介绍的，我们要访问第1000个块中的第25页中的1208字节处的话，所要传入的地址就是分4个周期，分别传入2个列地址的：0xB8，0x0C，然后再传2个行地址的：0x0C，0x7D，这样硬件才能识别。

4.读操作过程的解释

准备工作终于完了，下面就可以开始解释说明，对于读操作的，上面图中标出来的，1-6个阶段，具体是什么含义。

（1）操作准备阶段：此处是读（Read）操作，所以，先发一个图5中读命令的第一个阶段的0x00,表示，让硬件先准备一下，接下来的操作是读。

（2）发送两个周期的列地址。也就是页内地址，表示，我要从一个页的什么位置开始读取数据。

（3）接下来再传入三个行地址。对应的也就是页号。

（4）然后再发一个读操作的第二个周期的命令0x30。接下来，就是硬件内部自己的事情了。

（5）Nand Flash内部硬件逻辑，负责去按照你的要求，根据传入的地址，找到哪个块中的哪个页，然后把整个这一页的数据，都一点点搬运到页缓存中去。而在此期间，你所能做的事，也就只需要去读取状态寄存器，看看对应的位的值，也就是R/B#那一位，是1还是0，0的话，就表示，系统是busy，仍在”忙“（着读取数据），如果是1，就说系统活干完了，忙清了，已经把整个页的数据都搬运到页缓存里去了，你可以接下来读取你要的数据了。

对于这里。估计有人会问了，这一个页一共2048+64字节，如果我传入的页内地址，就像上面给的1028一类的值，只是想读取1028到2011这部分数据，而不是页开始的0地址整个页的数据，那么内部硬件却读取整个页的数据出来，岂不是很浪费吗？答案是，的确很浪费，效率看起来不高，但是实际就是这么做的，而且本身读取整个页的数据，相对时间并不长，而且读出来之后，内部数据指针会定位到你刚才所制定的1208的那个位置。

（6）接下来，就是“窃取“系统忙了半天之后的劳动成果的时候了，呵呵。通过先去Nand Flash的控制器中的数据寄存器中写入你要读取多少个字节(byte)/字(word)，然后就可以去Nand Flash的控制器的FIFO中，一点点读取你要的数据了。

至此，整个Nand Flash的读操作就完成了。

对于其他操作，可以根据上面的分析，一点点自己去看datasheet，根据里面的时序图去分析具体的操作过程，然后对照代码，会更加清楚具体是如何实现的。

NAND FLASH 搭配NOR FLASH的优缺点

常见的应用组合就是，用小容量的Nor Flash存储启动代码，比如uboot，系统启动后,初始化对应的硬件，包括SDRAM等，然后将Nand Flash上的Linux 内核读取到内存中，做好该做的事情后，就跳转到SDRAM中去执行内核了。

这样的好处是由于NAND 本身有坏块的可能性，所以为了保障启动万无一失，很多要求高级安全的产品，标注必须从NOR Flash启动uboot，而且从NOR启动还有一个好处就是启动速度快，NAND Flash的优点是容量大，但是读取速度不快，比不上NOR Flash，比如一些对于开机速度有要求的产品应用，比如车载液晶仪表，这类产品为了快速启动一般都是NOR FLASH+EMMC的配置，当然像赛普拉斯平台直接上hyperflash那就更快了。

NAND Flash的ECC校验简单说明

我们先来说说为什么需要ECC校验这个事情，其实上一篇文章我们说过由于NAND flash的自身的不稳定性，存在位翻转的现象，所以就存在写入到flash中的数据和读出来的数据不一样的情况发生，此时就需要有一个检验的机制，防止读出来的不正确，还可以纠正过来。

其实这个就类似于去银行存钱，你存了1W，过几天去银行去取钱的时候发现只有9000了，这个时候你就会拿出存条找银行理论，上次明明存的就是1W啊，你少的1000必须跟我纠正过来，其实这个就是NAND flash的ECC检验原理，发现有读出来的数据和存进去的数据不正确，此时就需要去纠正回来，当然这里的纠正的数据是有限制的，不是所有数据出错都能纠正过来。

ECC 校验是在奇偶校验的基础上发展而来的，它将数据块看作一个矩阵，利用矩阵的行、列奇偶信息生成 ECC 校验码。它能够检测并纠正单比特错误和检测双比特错误，但对双比特以上的错误不能保证检测。它克服了传统奇偶校验只能检出奇数位出错、校验码冗长、不能纠错的局限性。每 nbit 的 Ecc 数值可满足 2的n次方bit 数据包的校验要求。

当往Nand Flash 的Page 中写入数据的时候，每256字节我们生成一个ECC 校验和，称之为原ECC校验和，保存到 PAGE 的OOB数据区中。当从Nand Flash 中读取数据的时候，每 256 字节我们生成一个ECC校验和，称之为新 ECC 校验和。

校验的时候，根据上述ECC生成原理不难推断：将从 OOB 区中读出的原 ECC校验和新ECC校验和按位异或，若结果为0，则表示不存在错（或是出现了ECC无法检测的错误）：若3个字节异或结果中存在11个比特位为1，表示存在一个比特错误，且可纠正；若3个字节异或结果中只存在1个比特位为1，表示OOB区出错：其他情况均表示出现了无法纠正的错误。

这两期我们基本上把NAND FLASH的相关设计和使用都完整讲了一遍，下期会讲讲车载DRAM和EMMC的相关内容，敬请期待。

一种基于逻辑页平均更新频率的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)

智能座舱之存储篇第三篇---NAND Flash 一眼就看明白了

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

关于我们

产品中心

服务与支持