Quantitative Evaluation of Buffer Replacement Algorithms for Flash Memory Based Systems

Abstract

The ever increasing requirement for high performance and high capacity memories of emerging handheld devices or applications has led to the widespread adoption of DRAM and NAND type flash memories. Thus, the buffering policy for flash based systems has to improve the overall performance. Hence, the use of flash memory requires new buffer replacement policies considering not only buffer hit and miss rates but also the number of read , write and erase operations. Most of the traditional buffer replacement algorithms focued on the hit ratio improvement alone, but not the number of write counts caused by dirty pages to be propagated to the flash memory, which is the main factor to be considered in flash memory based systems.

The dissertation is mainly focused initially to determine the optimal window size for Clean First LRU algorithm and then to evaluate the performance of LRU, CFLRU and ADLRU buffer replacement algorithms. Finally, the comaparative study based on quantitative analysis of those algorithms is performed based on the hit/miss rates and the number write counts. The evaluation is conducted in a simulation environment using three kinds of synthetic traces : random, read most, and write most. The dissertation finally concluded that the ADLRU is superior to LRU and CFLRU in most of the cases. Hence, for flash based systems, the ADLRU buffer replacement algorithm is the best option due to its high hit rates and at the same time low write counts.