Open Access
Subscription Access
Evaluation of Write Sequence Reordering Based Buffer Replacement Algorithms for Flash Memory Based Systems
Abstract
Many page replacement algorithms have been developed for disk-based systems. All of them consider the hit rate as a key performance measure. Flash memory has different characteristics than hard disks, such as asymmetric I/O latency among read, write, and erase operations. The read operation is faster than the write and erase operation, and it does not support in-place updates. Besides, write operations shorten the life of flash memories. Therefore, the number of write counts is also an important factor to be considered for flash-based systems. This research work studied WSR-based algorithms, namely the LRU-WSR and LIRS-WSR, in terms of both hit rate and write count. The trace-driven simulation is performed with four different workloads: random, read-most, write-most, and Zipf traces. The simulation result showed that LIRS-WSR is better than LRU-WSR when locality is not too strong; otherwise, the performance of LRU-WSR is better.
Keywords
References
Tal A. (2003). Two Technologies Compared: NOR vs. NAND White Paper (2003). M-Systems: Flash Disk Pioneers. [Online]. Retrieved from https://www.maltiel-consulting.com/Nonvolatile_
Memory_NOR_vs_NAND.pdf.
Assar M, Nemazie S, Estakhri P. (1995). Flash memory mass storage architecture incorporation wear leveling technique. [Online]. Retrieved from https://patentimages.storage.googleapis.com/
/7a/9f/f5050b1288023b/US5479638.pd f.
Bez R, Camerlenghi E, Modelli A, Visconti A. Introduction to flash memory. Proc IEEE. 2003; 91(4): 489–502. DOI: 10.1109/JPROC.2003. 811702.
Jung H, Shim H, Park S, Kang S, Cha J. LRU-WSR: integration of LRU and writes sequence reordering for flash memory. IEEE Trans Consumer Electron. 2008; 54(3): 1215–1223. DOI: 10.1109/TCE.2008.4637609
Jung H, Yoon K, Shim H, Park S, Kang S, Cha J. LIRS-WSR: Integration of LIRS and writes sequence reordering for flash memory. In Proceedings of the International Conference on Computational Science and Its Applications. 2007 Aug; 224–237. Springer, Berlin, Heidelberg. DOI: https://doi.org/10.1007/978-3-540-74472- 6_18.
Park SY, Jung D, Kang JU, Kim JS, Lee J. CFLRU: a replacement algorithm for flash memory. In Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems; ACM, Seoul, Korea. 2006 Oct; 234–241. DOI: https://doi.org/10.1145/
1176789.
Jiang S, Zhang X. LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance. ACM SIGMETRICS Performance Evaluation Review (PER). 2002; 30(1): 31–42. DOI: https://doi.org/10.1145/511399. 511340.
Ou Y, Härder T, Jin P. CFDC: a flash-aware replacement policy for database buffer management. In Proceedings of the 5th international workshop on data management on new hardware. 2009; 15–20. Springer, Berlin, Heidelberg. DOI: https://doi.org/10.1007/978-3-642-15576-5_33.
Tanenbaum A, Bos H. Modern Operating Systems. 4th Edn. London, UK: Pearson; 2014.
Li Z, Jin P, Su X, Cui K, Yue L. CCF-LRU: A new buffer replacement algorithm for flash memory. IEEE Trans Consumer Electron. 2009; 55(3): 1351–1359. DOI: 10.1109/TCE.2009.5277999.
Jin P, Ou Y, Härder T, Li Z. AD-LRU: An efficient buffer replacement algorithm for flash-based databases. Data Knowl Eng. 2012; 72: 83–102. DOI: https://doi.org/10.1016/j.datak.2011.09.007.
Yao Y, Kong X, Zhou J, Xu X, Feng W, Liu Z. An advanced adaptive least recently used buffer management algorithm for SSD. IEEE Access. 2019; 7: 33494–33505. DOI: 10.1109/ACCESS.2019.2904639
Huang Q, Chen R, Lin M, Yang C, Chen Q, Li X. Clean-First Adaptive Buffer Replacement Algorithm for NAND Flash-based Consumer Electronics. In proceedings of the 2019 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking, Xiamen, China. 2019; 1217–1223. DOI: 10.1109/ISPA-BDCloud-SustainCom-SocialCom48970.2019. 00173.
Wang F, Jiang X, Huang J, Chen F. Pa-LIRS: An adaptive page replacement algorithm for NAND flash memory. Electronics. 2020; 9(12): 2172. DOI: https://doi.org/10.3390/electronics9122172.
Refbacks
- There are currently no refbacks.
Copyright (c) 2023 Journal of Computer Technology & Applications