1 Flash存储器结构及特性

Flash存储器是在EPROM和EEPROM的制造技术基础上发展起来的一种可擦除、非易失性存储元件。1983年，Intel公司提出了EPROM隧道氧化层ETOX（EPROM Tunnel Oxide）原理，1988年推出了第一块可快速擦写的非易失性“或非”（NOR）型Flash存储器。随后，Toshiba公司又推出了基于Fowler Nordheim的冷电子擦除原理和“与非”（NAND）型Flash存储器。

目前市场上流行的闪存结构主要有ETOX型、AND型、DiNOR型、NOR型、NAND型。其中，NOR型和NAND型是主流。可靠性高、读取操作快和具备随机访问能力的特点，使得NOR Flash非常适合用在代码存储方面，NOR Flash一般都用来存储相对少量的可执行代码;而高密度、低价格、较快速的写以及擦除次数、较长的复写寿命，使得NAND Flash特别适合那些连续的大量数据需要被快速载入到内存中,以及重复被新文件替换的消费媒体应用。

商品化的Flash存储器大都是CMOS工艺制成的，图1是它的一个存储单元的示意图。在浮栅和硅衬底之间有一层薄薄的氧化物质，当在控制栅极和漏极上加上高电压且源极接地时，沟道中电子由源极流向漏极。部分电子会在漏极附近被加速成为“热电子”，在控制栅极高电位的吸引下穿过氧化物质绝缘层，附着在浮栅上，使浮栅带电而引起阀值电压升高，使该元件处于高阀值电压状态。当要擦除浮栅上存储电荷使该元件返回到低阀值电压状态时，只需将控制栅极接地，在源极上加上高电压，浮栅上的电荷便会穿过氧化物薄层流向源极。由于一块集成块上所有单元的源极内部是连在一起的，所以Flash存储器只能是整片擦除，这是Flash存储器的特点。

图1 一个存储单元示意图

2 平均读写算法

平均读写算法（wear leveling algorithm）既可以直接在文件系统（file system）里实现（如图2所示）,也可以通过Flash存储器和文件系统之间的闪存转换层FTL（Flash Translation Layer）实现（如图3所示）。

图2 在文件系统里实现平均读写图3 在FTL里实现平均读写

本文主要讨论通过闪存转换层实现的平均读写算法。闪存转换层采用了一种页级地址转换机制（pagelevel address translation mechanism），允许操作系统像读写磁盘一样读写Flash存储器，并且提供从虚拟地址到物理地址的转换。另外，闪存转换层还提供例如碎片回收（garbage collection）等其他服务。

平均读写算法有两个级别： 第一级别为静态平均读写；第二级别为动态平均读写。

2.1 第一级别平均读写算法

第一级别平均读写算法就是在不考虑长期静态不动数据的情况下，新的数据写入最少使用的空闲块。这里主要有几种方法，下面逐一介绍。

2.1.1 链表方法

使用这种方法时，将所有空闲的物理块集中在一个缓冲池里。一个链表中的每一个物理块都对应着一个虚拟块，每当有数据要写入时，一个虚拟块便被分配，对应链中的一个物理块将会通过平均读写算法被选择。在形成这个链表时，可以按照年龄，即使用次数的多少来按顺序组织。这样，每次在链表中最“年轻”的一端的物理块被分配，而当有空闲块需要回收时，就加入到链表的另一端，这样就省去了每次分配需要比较使用次数的时间。这种方法也称“循环法（round robin method）”。

当平均读写池里没有空闲的物理块时，“最年轻”的链，也就是使用最少（擦写次数最少）的链将被合并，只有一个物理块留下合法的数据，其他物理块就被从链中去掉，并且成为平均读写池里的可用链。图4说明了一个空闲物理块的链表对应着一个虚拟块，块的年龄是按照增序排列的。

图4 物理块链

2.1.2 数组方式

在数组方式中，所有的物理块被组织进一个列表中。这个列表就是一个年龄的向量表，它包含所有块的年龄。年龄大小是以被擦写的次数多少来衡量的，被擦写次数越少，年龄就越小。系统启动时，这个向量表被放进内存储器中；平均读写算法使用这张表，通过把虚拟块映射到最年轻的块上来保证存储器设备被均衡使用。但是这种方法效率比较低。因为如果向量表不是年龄的有序表，则每次分配物理块时还要进行年龄的比较，找到最年轻的物理块将花费不少时间。如果向量表是有序的，那么当有空闲块回收时，需要将这个空闲块插入到合适的位置，需要移动不少的表项，也要增加不少系统开销。

2.1.3 静态链表方法

还可以使用链表和数组的结合体——静态链表来实现。这种方法与数组方法相似，也是维护一个年龄的向量表。每一个向量表示一个结点，但是用游标代替指针指示结点在数组中的位置。这样，当有物理块需要被分配时，根据年龄找到最年轻的块；当有空闲块需要回收时，只需要修改游标，而无需移动元素了。

2.2 第二级别平均读写算法

第二级别平均读写算法即动态平均读写方式。这种方式将考虑长期有效的静态数据所占据的存储单元。使用此算法时，长期有效的静态数据被拷贝到使用最多的块，以此来保证原来静态数据块被经常变更的数据使用，而原来使用最多的块可以得到一段时间的“休息”。这样，所有的块就可以被均衡使用，达到平均读写的目的。这种方法里，要设定一个临界值，当最大使用数和最小使用数的差值达到这个临界值时，第二级别平均读写算法将被激活。因为映射表是动态的，所以平均读写算法能够对文件系统以不可见的方式转移这些静态数据区域。由于绝对强制平均读写方式会对性能产生一些负面影响，所以可以采用一种非绝对平均读写算法。它可以保证所有空间的使用近似平等而不影响性能。通过这种特别的机制，存储器块的平均使用年龄将会趋于一个常数。

3 性能分析

为更好地说明问题，下面将使用了平均读写算法的Flash存储器的使用寿命与没有使用平均读写算法的Flash存储器进行对比。

（1） 没有使用平均读写算法

在没有使用平均读写算法的情况下，在一个基于文件分配表（file allacation table）的文件系统中，文件分配表总是存储在同一虚拟块中，写数据时需要时常更新文件分配表。这意味着需要经常对同一物理块进行擦写，缩短闪存的使用寿命。

假设闪存的可擦写次数为10万次。以一个FAT16格式的DOS文件系统为例，簇的大小是2 KB，如果要写一个8 MB的文件，共占用4K个簇。出于可靠性考虑，每写一个簇，FAT表就更新一次，写一个8 MB的文件，FAT表需要更新4 096次；而FAT表一直位于某个固定扇区中，所以8 MB的文件最多只能更新25次。

25×4 096=102 400

这个值大于可擦写次数的最大值，如果每天都需要备份一个8 MB的文件，则Flash的寿命只有25天。

(2)使用平均读写算法

使用平均读写算法后，因为平均读写算法不允许FAT表固定在某个扇区中，故损耗平均分配给所有物理扇区。期望的闪存寿命可以按下式计算：

式中： 0.7为文件系统和管理结构的额外消耗系数。

如果每天同样需要备份一个8 MB的文件，则

由此可见，平均读写算法可以极大地延长闪存的使用寿命。

4 结论

由以上的方法介绍及分析结果，可以得出结论： 在Flash存储器中，使用平均读写算法可以大大延长器件的使用寿命，对于实际应用具有重大的经济意义和安全意义。