Journal of Computing Science and Engineering

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지
DOI QR코드

DOI QR Code

Page Replacement for Write References in NAND Flash Based Virtual Memory Systems

  • Lee, Hyejeong (Department of Computer Engineering, Ewha Womans University) ;
  • Bahn, Hyokyung (Department of Computer Engineering, Ewha Womans University) ;
  • Shin, Kang G. (Department of Computer Engineering, Ewha Womans University)
  • Received : 2014.06.19
  • Accepted : 2014.08.08
  • Published : 2014.09.30
Download PDF
⟨ Previous Next ⟩

Abstract

Contemporary embedded systems often use NAND flash memory instead of hard disks as their swap space of virtual memory. Since the read/write characteristics of NAND flash memory are very different from those of hard disks, an efficient page replacement algorithm is needed for this environment. Our analysis shows that temporal locality is dominant in virtual memory references but that is not the case for write references, when the read and write references are monitored separately. Based on this observation, we present a new page replacement algorithm that uses different strategies for read and write operations in predicting the re-reference likelihood of pages. For read operations, only temporal locality is used; but for write operations, both write frequency and temporal locality are used. The algorithm logically partitions the memory space into read and write areas to keep track of their reference patterns precisely, and then dynamically adjusts their size based on their reference patterns and I/O costs. Without requiring any external parameter to tune, the proposed algorithm outperforms CLOCK, CAR, and CFLRU by 20%-66%. It also supports optimized implementations for virtual memory systems.

Keywords

References

  1. J. W. Hsieh, C. H. Wu, and G. M. Chiu, "MFTL: a design and implementation for MLC flash memory storage systems," ACM Transactions on Storage, vol. 8, no. 2, article no. 7, 2012.
  2. Intel Corporation, Understanding the Flash Translation Layer (FTL) Specification, Denver: Intel Corporation, 1998.
  3. W. K. Josephson, L. A. Bongo, K. Li, and D. Flynn, "DFS: a file system for virtualized flash storage," ACM Transactions on Storage, vol. 6, no. 3, article no. 14, 2010.
  4. A. Kawaguchi, S. Nishioka, and H. Motoda, "A flash-memory based file system," in Proceedings of USENIX Technical Conference, New Orleans, LA, 1995.
  5. J. Kim, J. M. Kim, S. H. Noh, S. L. Min, and Y. Cho, "A space-efficient flash translation layer for CompactFlash systems," IEEE Transaction on Consumer Electronics, vol. 48, no. 2, pp. 366-375, 2002. https://doi.org/10.1109/TCE.2002.1010143
  6. O. Kwon, K. Koh, J. Lee, and H. Bahn, "FeGC: an efficient garbage collection scheme for flash memory based storage systems," Journal of Systems and Software, vol. 84, no. 9, pp. 1507-1523, 2011. https://doi.org/10.1016/j.jss.2011.02.042
  7. D. Woodhouse, "JFFS: the journaling flash file system," in Proceedings of Ottawa Linux Symposium, Ottawa, Canada, 2001.
  8. YAFFS: Yet Another Flash File System, http://www.yaffs.net/.
  9. C. Park, J. U. Kang, S. Y. Park, and J. S. Kim, "Energyaware demand paging on NAND flash-based embedded storages," in Proceedings of International Symposium on Low Power Electronics and Design, New Port, CA, 2004, pp. 338-343.
  10. S. Y. Park, D. Jung, J. U. Kang, J. S. Kim, and J. Lee, "CFLRU: replacement algorithm for flash memory," in Proceedings of the International Conference on Compilers, Architecture and Synthesis for Embedded Systems, Seoul, Korea, 2006, pp. 234-241.
  11. L. Shi, C. J. Xue, and X. Zhou, "Cooperating write buffer cache and virtual memory management for flash memory based systems," in Proceedings of the 17th IEEE Real-Time and Embedded Technology and Applications Symposium, Chicago, IL, 2011, pp. 147-156.
  12. J. Park, H. Bahn, and K. Koh, "Buffer cache management for combined MLC and SLC flash memories using both volatile and nonvolatile RAMs," in Proceedings of the IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, Beijing, China, 2009, pp. 228-235.
  13. Intel Corporation, "Intel X-18M/X-25M SATA Solid State Drive (product manual)," http://download.intel.com/design/flash/nand/mainstream/mainstream-sata-ssd-datasheet.pdf.
  14. E. G. Coffman and P. J. Denning, Operating Systems Theory, Englewood Cliffs: Prentice-Hall, 1973.
  15. F. J. Corbato, A Paging Experiment with the Multics System (MAC-M-384), Cambridge: MIT Press, 1969.
  16. R. W. Carr and J. L. Hennessy, "WSCLOCK-a simple and effective algorithm for virtual memory management," in Proceedings of the 8th ACM Symposium on Operating Systems Principles, Pacific Grove, CA, 1981, pp. 87-95.
  17. H. Jung, H. Shim, S. Park, S. Kang, and J. Cha, "LRUWSR: integration of LRU and writes sequence reordering for flash memory," IEEE Transactions on Consumer Electronics, vol. 54, no. 3, pp. 1215-1223, 2008. https://doi.org/10.1109/TCE.2008.4637609
  18. H. Jo, J. U. Kang, S. Y. Park, J. S. Kim, and J. Lee, "FAB: flash-aware buffer management policy for portable media players," IEEE Transactions on Consumer Electronics, vol. 52, no. 2, pp. 485-493, 2006. https://doi.org/10.1109/TCE.2006.1649669
  19. S. W. Lee, D. J. Park, T. S. Chung, D. H. Lee, S. Park, and H. J. Song, "A log buffer-based flash translation layer using fully-associative sector translation," ACM Transactions on Embedded Computing Systems, vol. 6, no. 3, article no. 18, 2007.
  20. H. Kim and S. Ahn, "BPLRU: a buffer management scheme for improving random writes in flash storage," in Proceedings of the 6th USENIX Conference on File and Storage Technologies, San Jose, CA, 2008, pp. 239-252.
  21. S. Kang, S. Park, H. Jung, H. Shim, and J. Cha, "Performance trade-offs in using NVRAM write buffer for flash memory-based storage devices," IEEE Transactions on Computers, vol. 58, no. 6, pp. 744-758, 2009. https://doi.org/10.1109/TC.2008.224
  22. S. Bansal and D. S. Modha, "CAR: clock with adaptive replacement," in Proceedings of the 3rd USENIX Conference on File and Storage Technologies, San Francisco, CA, 2004, pp. 187-200.
  23. T. Johnson and D. Shasha, "2Q: A low overhead high performance buffer management replacement algorithm," in Proceedings of the 20th International Conference on Very Large Data Bases, Santiago de Chile, Chile, 1994, pp. 439-450.
  24. Y. Zhou, J. F. Philbin, and K. Li, "The multi-queue replacement algorithm for second level buffer caches," in Proceedings of the USENIX Annual Technical Conference, Boston, MA, 2001, pp. 91-404.
  25. N. Megiddo, and D. S. Modha, "ARC: a self-tuning, low overhead replacement cache," in Proceedings of the 2nd USENIX Conference on File and Storage Technologies, San Francisco, CA, 2003, pp. 115-130.
  26. E. J. O'Neil, P. E. O'Neil, and G. Weikum, "The LRU-K page replacement algorithm for database disk buffering," in Proceedings of ACM SIGMOD International Conference on Management of Data, Washington, DC, 1993, pp. 297-306.
  27. N. Nethercote and J. Seward, "Valgrind: a program supervision framework," Electronic Notes in Theoretical Computer Science, vol. 89, no. 2, pp. 44-66, 2003. https://doi.org/10.1016/S1571-0661(04)81042-9
  28. Valgrind, http://valgrind.org/.
  29. ARM, "Cortex-A series: programmer's guide," http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.den0013b.
  30. S. Jiang, F. Chen, and X. Zhang, "CLOCK-Pro: an effective improvement of the CLOCK replacement," in Proceedings of the USENIX Annual Technical Conference, Anaheim, CA, 2005, pp. 323-336.

Cited by

  1. History-aware page replacement algorithm for NAND flash-based consumer electronics vol.62, pp.1, 2016, https://doi.org/10.1109/TCE.2016.7448559
  2. An effective pre-store/pre-load method exploiting intra-request idle time of NAND flash-based storage devices vol.50, 2017, https://doi.org/10.1016/j.micpro.2017.03.007
  3. Exploiting write-only-once characteristics of file data in smartphone buffer cache management vol.40, 2017, https://doi.org/10.1016/j.pmcj.2017.01.004
  4. Energy-aware buffer management scheme for NAND and flash-based consumer electronics vol.61, pp.4, 2015, https://doi.org/10.1109/TCE.2015.7389803