The optimal structure of algorithms for α-paging

• Structure of the optimal offline algorithm OPT for an existing paging model for Flash memory devices.
• An online characterization of OPT is provided.
• OPTMark, a class of online algorithms based on OPT is proposed.
• Empirical results show that algorithms from OPTMark can outperform LRU.

Paging is an important part of data management between two memory hierarchies, a fast cache and a slow disk. Its main application areas are modern operating systems and databases. Paging algorithms need to take decisions without precisely knowing the future behavior of the system, therefore paging is one of the most studied problems in the field of online-algorithms. In this paper we consider α-paging [13], a variation of the classical paging problem. It models the asymmetry between reading and writing data when the slow disk is implemented by means of flash memory. We develop an online structure that keeps track of the cache contents of the optimal offline algorithm. Based on this structure we design the algorithm class OPTMark which has the best possible competitive ratio and performs well on real-world traces.