Evaluation of Write Sequence Reordering Based Buffer Replacement Algorithms for Flash Memory Based Systems

Authors

  • Arjun Singh Saud
  • Hari Sharan Bhatt

Keywords:

Flash memory, storage system, page replacement algorithms

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.

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.

Downloads

Published

2023-09-19

Issue

Vol. 14 No. 2 (2023)

Section

Articles

License

Declaration and Copyright Transfer Form

(to be completed by authors)

I/ We, the undersigned author(s) of the submitted manuscript, hereby declare, that the above manuscript which is submitted for publication in the STM Journals(s), is not published already in part or whole (except in the form of abstract) in any journal or magazine for private or public circulation, and, is not under consideration of publication elsewhere.

  • I/We will not withdraw the manuscript after 1 week of submission as I have read the Author Guidelines and will adhere to the guidelines.
  • I/We Author(s ) have niether given nor will give this manuscript elsewhere for publishing after submitting in STM Journal(s).
  • I/ We have read the original version of the manuscript and am/ are responsible for the thought contents embodied in it. The work dealt in the manuscript is my/ our own, and my/ our individual contribution to this work is significant enough to qualify for authorship.
  •  I/We also agree to the authorship of the article in the following order:

Author’s name                                    

 

1. ________________

2. ________________

3. ________________

4. ________________

 

We  Author(s) tick this box and would request you to consider it as our signature as we agree to the terms of this Copyright Notice, which will apply to this submission if and when it is published by this journal.