Modification and Evaluation of CFLRU Page Replacement Algorithm for Flash Memory Based System
Date
2016
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Department of Computer Science and Information Technology
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
Description
Keywords
Page replacement algorithm, Flash memory, DCH-CFLRU, CFLRU