AML: A Novel Page Replacement Algorithm for Solid State Disks

Traditional page replacement algorithms such as LRU have been optimized in various ways on the assumption of magnetic disks based storage system. The proposed algorithms for solid state disks based storage system, such as CFLRU and APRA, show better performance than LRU by some tests and experiments. However, these algorithms have several deficiencies, evicting less frequent clean page is too slow, the grain of implementation is coarse, and experiments are not very comprehensive. We suggest a novel algorithm called AML which means Adaptively Mixed List. AML prefers to evict the cold clean page and changes the window size adaptively according to the history of access patterns. We conduct an overall trace-driven simulation. The runtime of AML is reduced at most by 18% compared to APRA, and on average by 14% compared to CFLRU.