一种基于预搜索的自适应闪存垃圾回收算法

An Adaptive Garbage Collection Algorithm for Flash Based on Pre-search

闪存(Flash memory)普遍采取异地更新机制来提高写数据的效率,因此必须设计垃圾回收算法回收因数据更新产生的无效数据页,针对YAFFS2文件系统中垃圾回收算法搜索效率低,且未能较好地兼顾闪存磨损均衡度的问题,提出基于预搜索的自适应垃圾回收算法.该算法采用重叠的段搜索方式对闪存进行预搜索,根据预搜索确定的回收次数与写入数据量之比,自适应地采取不同的目标块选择策略进行回收.实验表明,算法能及时发现并回收符合条件的脏块,减少无效数据页长期占用闪存空间的现象,在提高垃圾回收效率的同时,提高了闪存磨损均衡度.

Flash memory adopts out-of-place update scheme to improve the efficiency of the write operation , therefore , garbage collection algorithm must be designed to recycle invalid data pages generated by data update. For some drawbacks of existing garbage collection algorithms of YAFFS2, such as the search efficiency is needed to be further improved, and wear-leveling is not drawn enough attention, we propose an adaptive algorithm based on pre-searching. Based on the ratio of recycling times to the amount of data to be written to the flash, the algorithm uses overlapping segments pre-search mode for searching, and adaptively selects different victim block selecting strategy for garbage collection. Experimental results show that the algorithm can detect and recycle qualified dirty blocks in time, and reduce the number of long-term occupations by invalid data pages. The algorithm improves the wear-leveling degree of flash memory with high recycle efficiency.