Article

CFLRU: a replacement algorithm for flash memory

Authors:

Seon-yeong Park,

Joonwon LeeAuthors Info & Claims

CASES '06: Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems

Pages 234 - 241

https://doi.org/10.1145/1176760.1176789

Published: 22 October 2006 Publication History

Abstract

In most operating systems which are customized for disk-based storage system, the replacement algorithm concerns only the number of memory hits. However, flash memory has different read and write cost in the aspects of time and energy so the replacement algorithm with flash memory should consider not only the hit count but also the replacement cost caused by selecting dirty victims. The replacement cost of dirty page is higher than that of clean page with regard to both access time and energy consumption. In this paper, we propose the Clean-First LRU (CFLRU) replacement algorithm that exploits the characteristics of flash memory. CFLRU splits the LRU list into the working region and the clean-first region and adopts a policy that evicts clean pages preferentially in the clean-first region until the number of page hits in the working region is preserved in a suitable level. Using the trace-driven simulation, the proposed algorithm reduces the average replacement cost by 28.4% in swap system and by 26.2% in buffer cache, compared with LRU algorithm. We also implement the CFLRU algorithm in the Linux kernel and present some optimization issues.

References

[1]

R. Cáceres, F. Douglis, K. Li, and B. Marsh, "Operating System Implications of Solid-State Mobile Computers," Proc. of the 4th IEEE Workshop on Workstation Operating Systems, October 1993.

[2]

Samsung Flash memory, http://www.samsung.com/Products/Semiconductor/Flash/.

[3]

M-systems Fast Flash Disks, http://www.m-sys.com/site/en-US/Products/IDESCSIFFD/IDESCSIFFD.

[4]

Memory Technology Devices, http://www.linux-mtd.infradead.org/doc/nand.html.

[5]

D. Jung, J. Kim, S. Park, J. Kang, and J. Lee, "FASS: A Flash-Aware Swap System", Proc. of International Workshop on Software Support for Portable Storage (IWSSPS), Mar. 2005.

[6]

Yet Another Flash Filing System (YAFFS), Aleph One Company.

[7]

D. Woodhouse, "JFFS: The Journaling Flash File System", Proc. of Ottawa Linux Symposium, 2001.

[8]

L. Belady, "A Study of Replacement Algorithms for a Virtual-Storage Computer," IBM Systems Journal, vol.5, no.2, pp.78--101, 1966.

Digital Library

[9]

N. Nethercote and J. Seward, "Valgrind: A program supervision framework," Electronic Notes in Theoretical Computer Science, vol.89, no.2, 2003.

[10]

D. P. Bovet and M. Cesati, Understanding the Linux Kernel, Second edition, Oreilly & Associates, 2003.

Digital Library

[11]

P. J. Denning, "The Working Set Model for Program Behavior," Communications of the ACM, vol.11, no.5, May 1968.

Digital Library

[12]

R. L. Mattson, J. Gecsei, D. R. Slutz, and I. L. Traiger, "Evaluation Techniques for Storage Hierarchies," IBM Systems Journal, vol.9, no.2, pp.78--117, 1970.

Digital Library

[13]

T. Johnson and D. Shasha, "2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm," Proc. of 20th International Conference Very Large Data Bases, pp.439--450, 1994.

Digital Library

[14]

P. E. O'Neil and G. Weikum, "The LRU-K Page Replacement Algorithm for Database Disk Buffering," Proc. of ACM SIGMOD Conference, May 1993.

Digital Library

[15]

Y. Smaragdakis, S. Kaplan, and P. Wilson, "EELRU: Simple and Effective Adaptive Page Replacement," Proc. of ACM SIGMETRICS Conference, 1999.

Digital Library

[16]

D. Lee, J. Choi, J. Kim, S. Noh, S. Min, Y. Cho, and C. Kim, "LRFU: A Spectrum of Policies that Subsumes the LRU and LFU Policies", IEEE Transactions on Computers, vol. 50, no. 12, pp.1352--1361, Dec. 2001.

Digital Library

[17]

N. Megiddo and D.S. Modha, "ARC: A Self-Tuning, Low Overhead Replacement Cache," Proc. of USENIX Conference File and Storage Technologies (FAST), 2003.

Digital Library

[18]

N. Young, "The k-server Dual and Loose Competitiveness for Paging," Algorithmica, vol.11, no. 6, pp. 525--541, June 1994.

Digital Library

[19]

J. Jeong and M. Dubois, "Optimal Replacements in Caches with Two Miss Costs," Proc. of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures, 1999.

Digital Library

[20]

J. Jeong and M. Dubois, "Cost-sensitive Cache Replacement Algorithms," Proc. of the Symposium on High-Performance Computer Architecture (HPCA), Jan. 2003.

Digital Library

[21]

H. Lee and N. Chang, "Low-Energy Heterogeneous Non-volatile Memory Systems for Mobile Systems," Journal of Low Power Electronics, vol.1, no.1, pp.52--62, Apr. 2005.

Cited By

Lyons SRangaswami R(2024)To Cache or Not to CacheAlgorithms10.3390/a1707030117:7(301)Online publication date: 7-Jul-2024
https://doi.org/10.3390/a17070301
Wang PJiang HLiu YZhao ZZhou KHuang Z(2024)Beyond Belady to Attain a Seemingly Unattainable Byte Miss Ratio for Content Delivery NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.345209635:11(1949-1963)Online publication date: Nov-2024
https://doi.org/10.1109/TPDS.2024.3452096
Sun HTong HYue YQin X(2024)LAC: A Workload Intensity-Aware Caching Scheme for High-Performance SSDsIEEE Transactions on Computers10.1109/TC.2024.338529073:7(1738-1752)Online publication date: Jul-2024
https://doi.org/10.1109/TC.2024.3385290
Show More Cited By

Index Terms

CFLRU: a replacement algorithm for flash memory
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Secondary storage

Recommendations

Recently-evicted-first buffer replacement policy for flash storage devices

Flash memory has been widely used as a storage device for consumer devices. Recently, applications using flash memory are becoming complex and diverse. One of obstacles to its wide use is the slow write performance of flash memory caused by its erase-...
ComboFTL: Improving performance and lifespan of MLC flash memory using SLC flash buffer

Multi-level cell (MLC) flash memory has lower bit cost compared to single-level cell (SLC) flash memory. However, there are several obstacles to the wide use of MLC flash memory, including slow write performance and shorter lifespan. To improve the ...
MRU-Tour-based Replacement Algorithms for Last-Level Caches
SBAC-PAD '11: Proceedings of the 2011 23rd International Symposium on Computer Architecture and High Performance Computing

Memory hierarchy design is a major concern in current microprocessors. Many research work focuses on the Last-Level Cache (LLC), which is designed to hide the long miss penalty of accessing to main memory. To reduce both capacity and conflict misses, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CASES '06: Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems

October 2006

448 pages

ISBN:1595935436

DOI:10.1145/1176760

General Chairs:
Seongsoo Hong
Seoul National University
,
Wayne Wolf
Princeton University
,
Program Chairs:
Krisztian Flautner
ARM Ltd.
,
Taewhan Kim
Seoul National University

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 October 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ESWEEK06

Sponsor:

ESWEEK06: Second Embedded Systems Week 2006

October 22 - 25, 2006

Seoul, Korea

Acceptance Rates

Overall Acceptance Rate 52 of 230 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

293
Total Citations
View Citations
3,214
Total Downloads

Downloads (Last 12 months)153
Downloads (Last 6 weeks)12

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lyons SRangaswami R(2024)To Cache or Not to CacheAlgorithms10.3390/a1707030117:7(301)Online publication date: 7-Jul-2024
https://doi.org/10.3390/a17070301
Wang PJiang HLiu YZhao ZZhou KHuang Z(2024)Beyond Belady to Attain a Seemingly Unattainable Byte Miss Ratio for Content Delivery NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.345209635:11(1949-1963)Online publication date: Nov-2024
https://doi.org/10.1109/TPDS.2024.3452096
Sun HTong HYue YQin X(2024)LAC: A Workload Intensity-Aware Caching Scheme for High-Performance SSDsIEEE Transactions on Computers10.1109/TC.2024.338529073:7(1738-1752)Online publication date: Jul-2024
https://doi.org/10.1109/TC.2024.3385290
Papon T(2024)Enhancing Data Systems Performance by Exploiting SSD Concurrency & Asymmetry2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00454(5644-5648)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00454
Cha HKim IKim T(2024)Using a random forest to predict quantized reuse distance in an SSD write bufferComputing10.1007/s00607-024-01343-5Online publication date: 5-Sep-2024
https://doi.org/10.1007/s00607-024-01343-5
Shin I(2023)Early Dirty Buffer Flush with Second Chance for SSDsMicromachines10.3390/mi1404079614:4(796)Online publication date: 31-Mar-2023
https://doi.org/10.3390/mi14040796
Lee BAn MLee S(2023)LRU-C: Parallelizing Database I/Os for Flash SSDsProceedings of the VLDB Endowment10.14778/3598581.359860516:9(2364-2376)Online publication date: 10-Jul-2023
https://dl.acm.org/doi/10.14778/3598581.3598605
Sha ZLi JZhang FHuang MCai ZTrahay FLiao J(2023)Visibility Graph-based Cache Management for DRAM Buffer Inside Solid-state DrivesACM Transactions on Storage10.1145/358657619:3(1-21)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3586576
Zhong KCui WChen XLi QYang ZLu YYan XLuo SYuan QHuang K(2023)Revisiting Swapping in User-Space With Lightweight ThreadingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.327495342:11(4205-4218)Online publication date: Nov-2023
https://doi.org/10.1109/TCAD.2023.3274953
Lin HLi JSha ZCai ZShi YGerofi BLiao J(2023)Adaptive Management With Request Granularity for DRAM Cache Inside nand-Based SSDsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.322929342:8(2475-2487)Online publication date: Aug-2023
https://doi.org/10.1109/TCAD.2022.3229293
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents