陈 琳， 严 华

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

伴随发展迅猛的信息化技术，存储数据所需介质在容量、种类等方面不断增长。与传统机械硬盘相比，NAND闪存具有体积小、无噪声、功耗低、访问速度快、防震抗摔性好等诸多优点，因此得到广泛应用，逐渐成为主要的存储介质[1-2]。NAND闪存由一定数量的物理块(block)构成，而每个物理块又由一定数量的物理页(page)构成。闪存的读取操作与写入操作以页为单位进行，但擦除操作只能在包含了多个页的块上来完成[3]。当系统请求页重写时，NAND闪存不能在同一物理页上进行“本地更新”，通常采用“异地更新”策略以满足写前擦除的特性，即新数据不能直接在旧页上改动，而需写入另一空闲物理页，并将旧页标记为无效页[4-5]。当无效页积累到一定数量时，就形成了无用的垃圾(garbage)。为充分利用闪存的存储空间，需要选择回收块(victim block)进行垃圾回收将无效页擦除。但由于NAND闪存擦除的基本单位是块，因此在擦除前需要将回收块中的全部有效页复制到另一空闲块。对闪存而言，擦除操作的速度比读写操作慢很多，且需要更大的功耗[6]。此外，闪存可支持的每个块的擦除次数具有上限。因此，在考虑减少物理块的擦除次数与回收代价的同时，提高闪存磨损均衡程度，是提高闪存读写性能并延长使用寿命的研究重点。

为了提升NAND闪存垃圾回收的效率与性能，中外学者们提出了诸多垃圾回收算法，这些算法的管理粒度主要分为块、页。

GR(GReedy)算法……