PR-LRU: A Novel Buffer Replacement Algorithm Based on the Probability of Reference for Flash Memory

Abstract

NAND flash memory has many advantages, including a small form factor, non-volatility, and high reliability. However, problems caused by physical limitations, such as asymmetric I/O latencies and outof-place updates, still need to be resolved. By using a probability of reference (PR) to select a candidate page as the victim page, this paper presents a novel buffer replacement algorithm called PR least recently used to enhance the flash memory performance. To predict whether a page may be referenced in the future, three variables are used to calculate a page's PR. In addition, we improve the performance overhead of the number of write operations, the hit ratio, and the runtime using a novel PR strategy. The algorithm is implemented and tested on the flash simulation platform Flash-DBSim. The results indicate that our algorithm provides improvements of up to 7% for the hit ratio with an improvement of up to 36.7% for the overall runtime compared with other approaches.

Keywords

• Buffer replacement algorithm
• flash memory
• flash-based DBMS
• probability of reference