Call for Papers
About the Journal
Editorial Board
Publication Ethics
Instructions for Authors
Current Issue
Back Issues
Search for Articles
Back Issues

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


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:   175 Downloads, 1703 View

ⓒ Copyright 2010 KIISE – All Rights Reserved.    
Korean Institute of Information Scientists and Engineers (KIISE)   #401 Meorijae Bldg., 984-1 Bangbae 3-dong, Seo-cho-gu, Seoul 137-849, Korea
Phone: +82-2-588-9240    Fax: +82-2-521-1352    Homepage:    Email: