Journal of KIISE:Computer Systems and Theory (한국정보과학회논문지:시스템및이론)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

Analyzing Virtual Memory Write Characteristics and Designing Page Replacement Algorithms for NAND Flash Memory

NAND 플래시메모리를 위한 가상메모리의 쓰기 참조 분석 및 페이지 교체 알고리즘 설계

  • 이혜정 (이화여자대학교 컴퓨터공학과) ;
  • 반효경 (이화여자대학교 컴퓨터공학과)
  • Published : 2009.12.15
Download PDF
⟨ Previous Next ⟩

Abstract

Recently, NAND flash memory is being used as the swap device of virtual memory as well as the file storage of mobile systems. Since temporal locality is dominant in page references of virtual memory, LRU and its approximated CLOCK algorithms are widely used. However, cost of a write operation in flash memory is much larger than that of a read operation, and thus a page replacement algorithm should consider this factor. This paper analyzes virtual memory read/write reference patterns individually, and observes the ranking inversion problem of temporal locality in write references which is not observed in read references. With this observation, we present a new page replacement algorithm considering write frequency as well as temporal locality in estimating write reference behaviors. This new algorithm dynamically allocates memory space to read/write operations based on their reference patterns and I/O costs. Though the algorithm has no external parameter to tune, it supports optimized implementations for virtual memory systems, and also performs 20-66% better than CLOCK, CAR, and CFLRU algorithms.

최근 NAND 플래시메모리를 모바일시스템의 파일저장용 뿐 아니라 가상메모리의 스왑장치용으로 사용하려는 시도가 늘고 있다. 가상메모리의 페이지 참조는 시간지역성이 지배적이어서 LRU 및 이를 근사시킨 CLOCK 알고리즘이 널리 사용된다. 한편, NAND 플래시메모리는 읽기 연산에 비해 쓰기 연산의 비용이 높아 이를 고려한 페이지 교체 알고리즘이 필요하다. 본 논문에서는 가살메모리의 읽기/쓰기 참조 패턴을 독립적으로 분석하여 시간지역성이 강한 읽기 참조와 달리 쓰기 참조의 경우 시간지역성의 순위 역전 현상이 발생함을 발견하였다. 이에 근거하여 본 논문은 쓰기의 재참조 성향 예측을 위해 시간지역성뿐 아니라 쓰기 연산의 빈도를 함께 고려하는 페이지 교체 알고리즘을 제안한다. 새로운 알고리즘은 연산별 I/O 비용을 고려해서 메모리 공간을 읽기 연산과 쓰기 연산에 독립적으로 할당하고 참조 패턴의 변화에 적응해 할당 공간을 동적으로 변화시킨다. 알고리즘의 시간 오버헤드가 매우 적어 가상메모리 시스템에서 사용될 최적의 조건을 갖추고 있으며 파라미터 설정이 필요 없음에도 CLOCK, CAR, CFLRU 알고리즘에 비해 20-66% 정도의 I/O 성능을 향상시킴을 보였다.

Keywords

References

  1. C. Park, J. Seo, S. Bae, H. Kim, S. Kim, B. Kim, "A low-cost memory architecture with NAND XIP for mobile embeddie systems," Proceedigns of CODES+ISSS, 2003.
  2. C. Park, J. Kang, S. Park, J. Kim, "Energy-Aware Demand PAging on NAND Flash-based Embedded Storages," Proceedings of International Symposium on Low Power Electronics and Design, 2004.
  3. S. Park, D. Jung, J. Kang, J. Kim, J. Lee, "CFLRU: replacement algorithm for flash memory," Proceedings of the 2006 intermational conference on Compilers, architecture and symthesis for embedded systems, 2006.
  4. R. van Riel, "Page replacement in Linux 2.4 memory management," Proceedings of the 2001 USENIX Annual Technical conference, 2001
  5. E. G. Coffman, P. J. Denning, Operating Systems Theory, Prentice-Hall, Ch.6, pp.241-283, 1973.
  6. http://www.samsung.com/Products/Semiconductor/NANDFlash/SLC_LargeBlock/4Gbit/K9F4G08U0A/ds_k9xxg08uxa_rev10.pdf
  7. D. Bovet, M. Cesati, "Understanding the Linux Kenel," O'Reilly, 2002.
  8. T. Johnson, D. Shasha, "2Q: A low overhead high performance buffer management repiacement algorithm," Proceedings of the VLDB conferenect, 1994.
  9. Y. Zhou, J. F. Phibin, "The multi-queue replacement algorithm for second level buffer caches," Proceedings of the 2001 USENIX Annual Technical conference, 2001.
  10. S. Jing, X. Zhang, "LIRS: An efficient low interreference recency set replacement policy to improve buffer cache performance," Proceedings of the ACM SIGMETRICS conference, 2002.
  11. N. Megiddo, DS. Modha, "ARC: A Self-tuning, Low Overhead Replacement Cache," Proceedings of the 2nd USENIX Conference on File and Storage Technologies, 2003.
  12. http://valgrind.org/
  13. N. Nethercote, J. Seward, "Valgrind: A Program Supervision Framework," Electronic Notes in Theoretical Computer Science, 2003.
  14. S. Bansal, DS. Modha, "CAR: Clock with Adaptive Replacement," Proceedings of 3rd USENIX Conference on File and Storage Technologies,2004.