JCSE, vol. 8, no. 3, pp.157-172, 2014

DOI: http://dx.doi.org/10.5626/JCSE.2014.8.3.157

Page Replacement for Write References in NAND Flash Based Virtual Memory Systems

Hyejeong Lee, Hyokyung Bahn, and Kang G. Shin
Department of Computer Engineering, Ewha Womans University, Seoul, Korea / Department of Electrical Engineering and Computer Science, The University of Michigan, MI, USA

Abstract: Contemporary embedded systems often use NAND flash memory instead of hard disks as their swap space of virtual memory. Since the read/write characteristics of NAND flash memory are very different from those of hard disks, an efficient page replacement algorithm is needed for this environment. Our analysis shows that temporal locality is dominant in virtual memory references but that is not the case for write references, when the read and write references are monitored separately. Based on this observation, we present a new page replacement algorithm that uses different strategies for read and write operations in predicting the re-reference likelihood of pages. For read operations, only temporal locality is used; but for write operations, both write frequency and temporal locality are used. The algorithm logically partitions the memory space into read and write areas to keep track of their reference patterns precisely, and then dynamically adjusts their size based on their reference patterns and I/O costs. Without requiring any external parameter to tune, the proposed algorithm outperforms CLOCK, CAR, and CFLRU by 20%-66%. It also supports optimized implementations for virtual memory systems.

Keyword: Memory; Secondary storage; Storage hierarchies; Swapping; Virtual memory; Flash memory

Full Paper:   248 Downloads, 2200 View