计算机应用   2017, Vol. 37 Issue (4): 1149-1152,1197  DOI: 10.11772/j.issn.1001-9081.2017.04.1149 0

### 引用本文

LEI Bingbing, YAN Hua. Garbage collection algorithm for NAND flash memory based on logical region heat[J]. Journal of Computer Applications, 2017, 37(4): 1149-1152,1197. DOI: 10.11772/j.issn.1001-9081.2017.04.1149.

### 文章历史

Garbage collection algorithm for NAND flash memory based on logical region heat
LEI Bingbing, YAN Hua
College of Electronics and Information Engineering, Sichuan University, Chengdu Sichuan 610065, China
Abstract: To solve the problems of low collection performance, poor wear leveling effect, and high memory overhead in the existing NAND flash memory garbage collection algorithms, a new garbage collection algorithm based on logical region heat was proposed. The heat calculation formula was redefined, the NAND memory of continuous logical address was defined as a heat range which was used to replace the heat of logical page, then the data with different heat was separated into the corresponding flash blocks with different erase counts. The cold and hot data were effectively separated, and the memory space was also saved. Meanwhile, a new collection cost function was constructed to improve the collection efficiency and wear leveling effect. The experimental results showed that compared with the excellent File-aware Garbage Collection (FaGC) algorithm, the total number of erase operations was reduced by 11%, the total number of copy operations was reduced by 13%, the maximum difference of erase counts was reduced by 42%, and the memory consumption was reduced by 75%. Therefore, the available flash memory space can be increased, the read and write performance of flash memory can be improved, and the flash memory life can be also extended by using the proposed algorithm.
Key words: NAND flash memory    wear leveling    garbage collection    logical region    collection block
0 引言

1 算法描述 1.1 基本原理

 图 1 NAND Flash存储系统结构 Figure 1 Storage system architecture for NAND Flash

NAND闪存具有基于日志结构的专有文件系统, 如JFFS、YAFFS文件系统, 它们都提供了逻辑地址到物理地址之间的映射。根据映射粒度的不同, 可以分为页级映射、块级映射和混合映射[10]。虽然页级映射对数据热度的判断最为准确, 但是在内存容量有限的电子产品中, 页级映射并不适用。在本文中, 采用一种新的映射方式——逻辑区间映射, 和页级映射相比, 它可以在保证较为准确识别数据热度的前提下, 减少系统的内存消耗。

1.2 逻辑区间定义

 ${{H}_{n}}=[la/M]$ (1)
1.3 逻辑区间热度定义

 {{T}_{i+1}}=\left\{ \begin{align} & \ {{T}_{\min }}, \ \ \ \ \ {{T}_{i+1}}<{{T}_{\min }} \\ & \alpha *{{T}_{i}}, \ \ \ {{T}_{\min }}\le {{T}_{i+1}}\le {{T}_{\text{max}}} \\ & \ {{T}_{\max }}, \ \ \ {{T}_{i+1}}>{{T}_{\max }} \\ \end{align} \right. (2)
 \alpha =\left\{ \begin{align} & 2-t/{{N}_{t}}, \ \ \ \ \ \ 0\le \left\lfloor t/{{N}_{t}} \right\rfloor <2 \\ & 0\, \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left\lfloor t/{{N}_{t}} \right\rfloor \ge 2 \\ \end{align} \right. (3)

1.4 回收块选择策略

 $C=(1-\lambda ).\frac{1-\mu }{1+\mu }+\lambda \frac{{{\varepsilon }_{\max }}-{{\varepsilon }_{i}}}{{{\varepsilon }_{\text{max}}}-{{\varepsilon }_{\min }}}$ (4)

 {{S}_{e}}=\left\{ \begin{align} & {{S}_{th}}-\varepsilon, \ \ \ \ \ \ \ \ \varepsilon \le {{S}_{th}} \\ & 0, \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \varepsilon >{{S}_{th}} \\ \end{align} \right. (5)
 $\varepsilon ={{\varepsilon }_{\max }}-{{\varepsilon }_{\min }}$ (6)

 $SC=\left( {{B}_{\text{f}}}\cdot {{N}_{\text{p}}} \right)/{{p}_{\text{f}}}$ (7)

1) 当满足SCTSC时, 启动垃圾回收;

2) 根据式 (4) 计算, 选择使回收代价C值最大的块作为回收块;

3) 根据式 (1) 确定逻辑区间编号, 通过式 (2)~(3) 计算逻辑区间的热度, 并判断该逻辑区间内所对应的有效页冷热情况;

4) 将步骤3) 中判断的热数据拷贝到擦除次数最少的块上, 冷数据拷贝到擦除次数最大的块上;

5) 当按照步骤2) 回收物理块的次数大于Se时, 对最冷块进行一次回收。

2 实验与分析 2.1 实验环境及实验参数

2.2 性能比较

FaGC算法的各项性能指标均明显优于GR算法、CB算法和CAT算法, 为了验证本文算法的有效性, 选取FaGC算法作为比较。

 图 2 总的擦除次数对比 Figure 2 Total number of erase operations
 图 3 总的拷贝次数对比 Figure 3 Total number of copy operations

 图 4 擦除次数的最大差值对比 Figure 4 Maximum difference of erase counts
 图 5 擦除次数的标准差对比 Figure 5 Standard deviation of erase counts
2.3 内存消耗

 图 6 内存消耗对比 Figure 6 Memery consumption comparison
3 结语

 [1] LEE S, KIM J. Effective lifetime-aware dynamic throttling for NAND flash-based SSDs[J]. IEEE Transactions on Computers, 2016, 65 (4) : 1075-1089. doi: 10.1109/TC.2014.2349517 [2] CHANG Y, CHANG Y, CHEN J, et al. On trading wear-leveling with heal-leveling[C]//DAC 2014: Proceedings of the 51st Annual Design Automation Conference. New York: ACM, 2014:1-6. [3] LEE J, KIM Y, SHIPMAN G M, et al. Preemptible I/O scheduling of garbage collection for solid state drives[J]. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 2013, 32 (2) : 247-260. doi: 10.1109/TCAD.2012.2227479 [4] LAM K Y, ZHU C J, CHANG Y H, et al. Garbage collection of multi-version indexed data on flash memory[J]. Journal of Systems Architecture, 2014, 60 (8) : 630-643. doi: 10.1016/j.sysarc.2014.06.004 [5] KIM S H, CHOI J H, KWAK J W. HaWL: hidden cold block-aware wear leveling using bit-set threshold for NAND flash memory[J]. IEICE Transactions on Information and Systems, 2016, E99-D (4) : 1242-1245. doi: 10.1587/transinf.2015EDL8198 [6] WU M, ZWAENEPOEL W. eNVy: a non-volatile main memory storage system[C]//ASPLOS Ⅵ: Proceedings of the Sixth International Conference on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 1994:86-97. [7] KAWAGUCHI A, NISHIOKA S, MOTODA H A. Flash memory based file system[C]//Proceedings of the USENIX 1995 Technical Conference. Berkeley: USENIX Association, 1995:155-164. [8] CHIANG M L, CHANG R C. Cleaning policies inmobile computers using flash memory[J]. Journal of Systems and Software, 1999, 48 (3) : 213-231. doi: 10.1016/S0164-1212(99)00059-X [9] YAN H, YAO Q. An efficient file-aware garbage collection algorithm for NAND flash based consumer electronics[J]. IEEE Transactions on Consumer Electronics, 2014, 60 (4) : 623-627. doi: 10.1109/TCE.2014.7027335 [10] 陈金忠, 姚念民, 蔡绍滨, 等. 基于页面写相关的闪存转换层策略[J]. 通信学报, 2013, 34 (6) : 76-84. ( CHEN J Z, YAO N M, CAI S B, et al. Page write-related scheme for flash translation layer[J]. Journal on Communications, 2013, 34 (6) : 76-84. ) [11] CHANG L-P, KUO T-K. Efficient management for large-scale flash memory storage systems with resource conservation[J]. ACM Transactions on Storage, 2005, 1 (4) : 381-418. doi: 10.1145/1111609 [12] KIM H, SHIN D. Clustered page-level mapping for flash memory based storage devices[J]. IEEE Transactions on Consumer Electronics, 2015, 61 (1) : 47-55. doi: 10.1109/TCE.2015.7064110 [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. doi: 10.1109/TCE.2013.6626235