Modification and Evaluation of CFLRU Page Replacement Algorithm for Flash Memory Based System

Abstract

Flash disks are becoming an important alternative to conventional magnetic disks because of its positive sides, like more energy-efficient, have no mechanical parts and, therefore, hardly any perceptible latency. Classical buffer replacement policies, like LRU, are not optimal for database systems having flash disks for persistence, because they are not well aware of the distinguished characteristics of those storage devices. CFLRU is one of the page replacement algorithm which partially addresses the flash memory properties. But it has limitations that it cannot reduce the write count when write most reference type pattern occur in real problem. This dissertation work addresses this limitation of CFLRU algorithm and designs modified page replacement algorithm based on CFLRU, named DCH-CFLRU, where second chance is given to hot pages both clean and dirty and replaced cold pages when replacement occurs. This strategy balances and preserves hit ratio and reduce write count. Afterward, the newly designed algorithm is compared and evaluated with basic CFLRU. And based on this experiment the analysis and conclusion have been drawn out.

Experiment and evaluation of this work shows that DCH-CFLRU preserve hit ratio and reduces the write count up to 14% in three workloads. In one workload, read most access, CFLRU gives less write count only when there is large cache size, because large cache can accommodate small number of dirty pages. But this is very rare case in real database system.

Keywords: Page Replacement Algorithm, DCH-CFLRU, CFLRU, Flash Memory