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

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

Design and Implementation of MODA Allocation Scheme based on Analysis of Block Cleaning Cost

블록 클리닝 비용 분석에 기초한 MODA할당 정책 설계 및 구현

  • 백승재 (단국대학교 정보컴퓨터과학과) ;
  • 최종무 (단국대학교 정보컴퓨터과학과)
  • Published : 2007.12.15
Download PDF
⟨ Previous Next ⟩

Abstract

Due to the restrictions of Flash memory such as overwrite limitation and write/erase operational unit differences, block cleaning is required in Flash memory based file systems and known as a key factor on the performance of file systems. In this paper, we identify three parameters, namely utilization, invalidity and uniformity, and analyze how the parameters affect the cost of block cleaning. The analysis show that as uniformity degrades, the cost of block cleaning increases drastically. To overcome this problem, we design a new modification-aware(MODA) page allocation scheme that strives to keep uniformity high by separating frequently-updating data from infrequently-updating data. Real implementation experiments conducted on an embedded system show that the MODA scheme can actually enhance uniformity of Flash memory, which consequently leads to reduce the cost of block cleaning with an average of 123%, compared to the traditional sequential allocation scheme that is used in YAFFS.

플래시 메모리는 덮어 쓰기 제약이나, 쓰기와 삭제 연산의 단위가 다르다는 등의 특징을 가지고 있다. 따라서 플래시 메모리를 저장장치로 사용하는 파일 시스템은 블록 클리닝을 필요로 하며 이는 파일 시스템의 주된 병목으로 작용한다. 이에 따라 본 논문에서는 플래시 메모리 기반 파일 시스템의 병목 요소인 블록 클리닝에 따른 성능향상에 대해 연구한다. 우선 블록 클리닝에 영향을 끼치는 성능 인자로서 이용률, 무효율, 순수도를 정의하였다. 이 세 가지 인자를 통해 블록 클리닝 비용을 분석한 결과, 파일 시스템 수준에서 제어 가능한 인자인 순수도가 블록 클리닝 비용에 많은 영향을 끼침을 확인할 수 있었다. 따라서 순수도를 높게 유지하여 블록 클리닝 비용을 최소화함으로서 파일시스템의 성능을 향상 시킬 수 있는 MODA 할당 정책(modification-aware)을 설계하였고, 이를 내장형 보드와 YAFFS(Yet Another Flash File System)상에 구현하였다. 실험 결과 MODA는 YAFFS의 순차 할당 기법에 비해 블록 클리닝 시간을 평균 123% 단축 시켰다.

Keywords

References

  1. M. Rosenblum and J. K. Ousterhout, 'The design and implementation of a log-structured file system,' ACM Transactions on Computer Systems, Vol.10, No.1, pp. 26-52, 1992 https://doi.org/10.1145/146941.146943
  2. J. Matthews, D. Roselli, A. Costello, R. Wang, and T. anderson, 'Improving the performance of logstructured file system with adaptive methods,' ACM Symposiums on Operating System Principles (SOSP), pp. 238-251, 1997
  3. T. Blackwell, J. Harris, and M. Selzer, 'Heuristic cleaning algorithms in log-structured file systems,' Proceedings of the 1995 Annual Technical Conference, pp. 277-288, 1993
  4. J. Wang and Y. Hu, 'WOLF - a novel reordering write buffer to boost the performance of logstructured file system,' Proceedings of the USENIX Conference on File and Storage Technologies (FAST), pp. 46-60, 2002
  5. W. Wang, Y. Zhao, and R. Bunt, 'HyLog: A High Performance Approach to Managing Disk Layout,' Proceedings of the USENIX Conference on File and Storage Technologies (FAST), pp. 145-158 2004
  6. M-L. Chiang, P. C. H. Lee, and R-C. Chang, 'Using data clustering to improve cleaning performance for flash memory,' Software: Practice and Experience, Vol.29, No.3, pp. 267-290, 1999 https://doi.org/10.1002/(SICI)1097-024X(199903)29:3<267::AID-SPE233>3.0.CO;2-T
  7. M. Wu and W. Zwaenepoel, 'eNVy: a non-volatile, main memory storage system,' Proceeding of the 6th international conference on Architectural Support for Programming languages and operation systems, pp. 86-97, 1994
  8. L. P. Chang, T. W. Kuo and S. W. Lo, 'Real-time garbage collection for flash memory storage systems of real time embedded systems,' ACM Transactions on Embedded Computing Systems, Vol.3, No.4, pp. 837-863, 2004 https://doi.org/10.1145/1027794.1027801
  9. E. Gal and S. Toledo, 'Algorithms and Data Structures for Flash Memories,' ACM Computing Surveys, Vol.37, No.2, pp. 138-163, 2005 https://doi.org/10.1145/1089733.1089735
  10. M. Mckusick, W. Joy, S. Leffler, and R. Fabry, 'A Fast File System for UNIX,' ACM Transactions on Computer Systems, 2(3), pp. 181-197, Aug., 1984 https://doi.org/10.1145/989.990
  11. William Stalling, 'Operating Systems: Internals and Design Principles,' 5th Edition, Pearson Prentice Hall, 200
  12. EZ-X5, FALINUX Inc., http://www.falinux.com/zproducts/ez-x5.php
  13. Samsung Inc., http://www.samsung.com/Products/ Semoconductor/NANDFlash
  14. Samsung Inc., http://www.samsung.com/Products/ Semiconductor/NANDFlash/SLC_LargeBlock/32Gbit /K9NBG08U5M/ds_k9xxg08uxm_rev10.pdf
  15. Aleph One, 'YAFFS: Yet Another Flash File System,' http://www.aleph1.co.uk/yaffs/
  16. MTD subsystem for Linux, http://www.linux-mtd.infradead.org/archive/index.html
  17. Y. Zhou, P. M. Chen, and K. Li, 'The Multi-Queue Replacement Algorithm for Second-Level Buffer Cache,' Proceeding of the 2001 USENIX Annual Technical Conference, June, 2001
  18. J. Kim, J. M. Kim, S. H. Noh, S. L. Min, Y. Cho, 'A space-efficient Flash translation layer for CompactFlash systems,' IEEE Transactions on Consumer Electronics, Vol.48, No.2, pp. 366-375, 2002 https://doi.org/10.1109/TCE.2002.1010143
  19. H. Jo, J. Kang, S. Park, J. Kim, and J. Lee, 'FAB: Flash-Aware Buffer Management Poicy for Portable Media Players,' IEEE Transactions on Consumer Electronics, Vol.52, No.2, May, 2006
  20. E. Gal and S. Toledo, 'A Transactions Flash File System for Microcontrollers,' Proceedings of the 2005 USENIX Annual Technical Conference, pp. 89-104, 2005on
  21. J. Katcher, 'PostMark: A New File System Benchmark,' Technical Report TR3002, Network Appliance Inc., 1997
  22. J. H. Howard, M. L. Kazar, S. G. Menees, D. A. Nichols, M. Satyanarayanan, R. N. Sidebotham, M. J. West, 'Scale and Performance in a distributed file system,' ACM Transactions on Computer Systems, 6(1), Feb., 1988
  23. Kawaguchi, S. Nishioka and H. Motoda, 'A flashmemory based file system,' Proceedings of the 1995 USENIX Annual Technical Conference, pp. 155-164, 1995
  24. 배영현, 최종무, 이동희, 노삼혁, 민상렬, '플래시 메모 리 파일 시스템을 위한 효율적인 소거 평준화 기법', 한국정보과학회 가을 학술발표논문집, pp. 580-582, 2004
  25. M. L. Chiang and R. C. Chang, 'Cleaning Policies in Mobile Computers using Flash Memory,' Journal of systems and software, pp. 213-231, Vol. 48, No, 3, 1999 https://doi.org/10.1016/S0164-1212(99)00059-X
  26. 백승재, 최종무, '플래시 메모리 파일 시스템을 위한 순수도 기반 페이지 할당 기법에 대한 연구,' 정보처리 학회논문지 A 제 13-A권 제 5호, pp. 387-398, 2006 https://doi.org/10.3745/KIPSTA.2006.13A.5.387