吉林大学学报(工学版) ›› 2017, Vol. 47 ›› Issue (2): 632-638.doi: 10.13229/j.cnki.jdxbgxb201702039
王力玉, 陈岚, 郝晓冉, 王强, 倪茂
WANG Li-yu, CHEN Lan, HAO Xiao-ran, WANG Qiang, NI Mao
摘要: 针对现有面向闪存的缓冲区替换算法的不足,提出了一种基于生命值敏感的闪存数据库缓冲区替换算法LAB-LRU。该算法把缓冲区分为3个LRU链表来管理,为缓冲区中每个活跃页定义生命值,使高生命值的数据页在缓存中停留更久。生命值的定义充分结合了数据页的访问频度、新颖度(recency)和闪存的读写代价,并采用多线程技术和双阈值控制实现并行高效替换。采用符合Zipf分布的不同用例进行测试,实验结果表明:在缓存命中率、闪存读写次数和系统运行时间方面,本文提出的LAB-LRU算法与现有缓存算法相比性能得到了明显提高。
中图分类号:
[1] Koltsidas I, Viglas S D. Flashing up the storage layer[J].Proc of the VLDB Endowment, 2008,1(1):514-525. [2] Gal E, Sivan T. Algorithms and data structures for flash memories[J]. ACM Computing Surveys, 2005, 37(2): 138-163. [3] Jiang S, Zhang X D. Making LRU friendly to weak locality workloads: a novel replacement algorithm to improve buffer cache performance[J]. IEEE Trans on Computers, 2005,54(8): 939-952. [4] Park Seon-Yeong, Jung Dawoon, Kang Jeong-Uk, et al. CFLRU: a replacement algorithm for flash memory[C]∥Proceedings of the CASES'06, Seoul, Korea, 2006: 234-241. [5] Jung H, Shim H, Park S, et al. LRU-WSR: intergration of LRU and writes sequence reordering for flash memory[J]. IEEE Transactions on Consumer Electronics, 2007, 54(3): 1215-1223. [6] Li Zhi, Jin Pei-quan, Su Xuan, et al. CCF-LRU: a new buffer replacement algorithm for flash memory[J]. IEEE Transactions on Consumer Electronics, 2009, 55(3): 1351-1359. [7] Jin Pei-quan, Ou Yi, Harder Theo, et al. AD-LRU: an efficient buffer replacement algorithm for flash-based databases[J]. Data & Knowledge Engineering, 2012, 72:73-102. [8] 林子雨,赖明星,邹权,等. 基于替换概率的闪存数据库缓冲区替换算法[J]. 计算机学报, 2013, 36(8): 1568-1581. Lin Zi-yu, Lai Ming-xing, Zou Quan, et al. Probability-based buffer replacement algorithm for flash-based databases[J]. Chinese Journal of Computers, 2013, 36(8): 1568-1581. [9] Cui Jin-hua, Wu Wei-guo, Wang Yin-feng, et al. PT-LRU: a probabilistic page replacement algorithm for NAND flash-based consumer electronics[J]. IEEE Transactions on Consumer Electronics, 2014, 60(4): 614-622. [10] 汤显,孟小峰,梁智超,等.基于代价的闪存数据库缓冲区置换算法[J]. 软件学报,2011, 22(12): 2951-2964. Tang Xian, Meng Xiao-feng, Liang Zhi-chao, et al. Cost-based buffer management algorithm for flash database systems[J]. Journal of Software, 2011, 22(12): 2951-2964. [11] Jin P Q, Su X, Li Z, et al. A flexible simulation environment for flash-aware algorithms[C]∥Proc 18th ACM Conference on Information and Knowledge Management, Hong Kong, China, 2009: 2093-2094. |
[1] | 刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850. |
[2] | 王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858. |
[3] | 金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866. |
[4] | 赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872. |
[5] | 刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878. |
[6] | 欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570. |
[7] | 刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599. |
[8] | 桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605. |
[9] | 刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613. |
[10] | 车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628. |
[11] | 赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223. |
[12] | 黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230. |
[13] | 傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236. |
[14] | 曹洁, 苏哲, 李晓旭. 基于Corr-LDA模型的图像标注方法[J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243. |
[15] | 侯永宏, 王利伟, 邢家明. 基于HTTP的动态自适应流媒体传输算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253. |
|