낸드 플래시 메모리를 위한 적응형 가비지 컬렉션 정책 = An Adaptive Garbage Collection Policy for NAND Flash Memory

국문 초록 (Abstract)

제자리 덮어쓰기가 불가능하고 블록의 지움 횟수가 제한되는 낸드 플래시 메모리를 저장매체로 사용하기 위해서 지움 횟수 평준화를 지원하는 다양한 가비지 컬렉션 정책들이 연구되고 있다. 기존정책들은 지움 횟수 평준화를 지원하기 위해 가비지 컬렉션이 수행될 때마다 전체 블록에 대해 지움 대상블록을 선정하기 위한 클리닉 지표를 구하는 연산을 수행하여야 하고 이 연산들은 시스템의 성능을 저하시킨다. 본 논문에서 제안하는 가비지 컬렉션 정책은 지움 횟수의 분산(variance)과 블록들의 최대 지움 횟수에 따라 변경되는 임계값을 이용하여 전체 블록에 대한 클리닉 지표를 구하는 연산을 수행하지 않으면서 지움 횟수 평준화를 제공한다. 가비지 컬렉션 시 분산이 임계값 보다 작을 때는 Greedy 정책을 이용하여 지움 비용을 최소화하고, 분산이 임계값 보다 클 때는 최대 지움 횟수를 가진 블록을 지움 대상에서 제외하여 지움 횟수를 평준화한다. 본 논문에서 제안하는 방법으로 가비지 컬렉션을 수행 하였을 때, 블록들의 지움 횟수가 지움 횟수 상한에 가까워질수록 블록들의 지움 횟수 표준 편차가 0에 근접하며, 기존의 지움 횟수 평준화를 지원하는 알고리즘과 비교하여 두 배 이상 빠른 가비지 컬렉션 속도를 보였다.

다국어 초록 (Multilingual Abstract)

In order to utilize NAND flash memory as storage media which does not allow update-in-place and limits the number of block erase count, various garbage collection policies supporting wear-leveling have been investigated. Conventional garbage collection policies require cleaning-index calculation for the entire blocks to choose a block to be garbage-collected to support wear-leveling whenever a garbage collection is required, which results in performance degradation of system. This paper proposes a garbage collection policy which supports wear-leveling using a threshold value, which is in fact a variance of erase counts and by the maximum erase count of all blocks, without calculating the cleaning-index. During garbage collection, the erase cost is minimized by using the Greedy Policy if the variance is less than the threshold value. It achieves wear-leveling by excluding the block with the largest erase count from erase target blocks if the variance is larger than threshold value. The proposed scheme shows that a standard deviation approaches to zero as the erase count of blocks approaches to its upper limit and the measured speed of garbage collection is two times faster than the conventional schemes.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구
• 3. 적응적 가비지 컬렉션 정책
• 4. 성능평가
• 5. 결론 및 향후 연구 과제
• 참고문헌

참고문헌 (Reference)

1 국형준, "적응형 웹 서핑 지원을 위한 에이전트 시스템" 한국정보처리학회 9 (9): 399-406, 2002

2 이태훈, "임베디드 플래시 파일 시스템을 위한 플레인 지움 정책" 778-780, 2005

3 민용기, "이동컴퓨터를 위한 플래시메모리 클리닝정책" 24 (24): 657-666, 1999

4 한준영, "낸드 플래시 메모리 기반 멀티미디어 파일 시스템에서의 효율적인 페이지 할당 및 회수 기법" 34 (34): 680-682, 2007

5 "http://www.linux-mtd.infradead.org/faq/nand.html"

6 박상오, "NAND 플래시 메모리 기반 파일 시스템을 위한 빠른 마운트 및 안정성 기법" 한국정보과학회 34 (34): 683-695, 2007

7 Samsung Electronics Co., "NAND Flash"

8 M.L.Chang, "Managing Flash Memory in Personal Communicati on Devices" 177-182, 1997

9 T. Blackwell, "Heuristic Cleaning Algorithms in Log-Structured File Systems" 1995

10 Atsuo Kawaguchi, "A Flash-Memory based File System" 155-164, 1995