Mobile multimedia devices have become a primary product in the mobile embedded device market. Along with the mobile multimedia devices, NAND flash memory has become popular due to its outstanding characteristics such as small size, light weight, high density, low power dissipation, and solid state reliability. However, due to NAND flash’s erase-before-write and bulk-erase characteristics, NAND flash memory is often used with flash-aware file systems. In designing a flash file system for mobile multimedia devices, we confront two considerable issues. First one is scalability. As the computational resources such as memory and a processor in mobile devices is strictly limited because power budget and the mass production cost, the flash file system should be designed to use limited memory while supporting large scale flash memory. The other issue is real-time performance guarantee for recording. Although this issue was addressed in numerous disk-based systems, distinct problems arise due to the difference of the characteristics of NAND flash compared to those of disks.
In this thesis, we design and implement scalable flash file systems, called ScaleFFS and RTFFS, for mobile multimedia devices. ScaleFFS mainly addresses the scalability problem of conventional flash file systems related to the memory consumption and mount time. To resolve the problem, we borrow the basic architecture of LFS and modify data structures and policies for NAND flash memory. RTFFS is completely redesigned to provide the real-time performance guarantee as well as high scalability. To achieve this, we first design an index structure which has a constant update cost by combining μ-Tree and extent-based inode pages. Second, we suggest a space management scheme to alleviate the garbage collection cost of writing multimedia data. In this scheme, two different allocation units are used according to the type of data. For multimedia files, the unit is a block, and it is exclusively assigned to the file. In contrast, RTFFS uses a page for non-multimedia files and metadata. We also propose a scalable data structures to manage this scheme, which are μ-Bitmap and μ-Summary. μ-Bitmap is a hierarchical bitmap structure that manages flash block states, and μ-Summary is an in-memory data structure to deal with metadata and non-multimedia files. The measurement results show that RTFFS guarantees desired write latency, achieving comparable performance to an existing flash file system, According to the mathematical analysis, RTFFS can guarantee high write bandwidth close to the raw NAND write bandwidth. In addition, RTFFS only consumes small and constant memory space.
지난 수년간 이동형 멀티미디어 장치는 임베디드 시스템 시장에서 가장 대표적인 제품으로 자리 잡았다. 이와 함께, 낸드(NAND) 플래시 메모리는 전력 소모가 적다는 특징과 경량 고집적이 가능한 특성 및 안정성과 같은 여러 가지 장점으로 인하여, 이동형 멀티미디어 장비의 대표적인 저장장치로 부상했다. 하지만 낸드 플래시 메모리는 데이터를 쓰기전에 반드시 소거를 해야 하며, 소거할 때는 읽기 쓰기의 기본 단위인 페이지보다 월등히 큰 단위인 블록이라는 단위로 지워지는 특성이 있다. 이 특성으로 인해 낸드 플래시 메모리는 디스크 기반 파일시스템이 아닌 플래시에 특화된 파일 시스템을 쓰는 경우가 많다. 이러한 플래시 파일 시스템을 설계할 때, 이동형 멀티미디어의 특성을 감안하여 다음과 같은 두 가지 중요한 문제점을 다루어야 한다. 첫째, 멀티미디어 데이터를 충분히 담을 수 있는 설계가 필요하다. 이 때 이동형 저장장치는 제조 단가 및 전력 설계 목표에 따라 메모리 자원이 제한되는 경우가 많다. 따라서 플래시 파일 시스템은 매우 제한적인 메모리를 활용하여 동작할 수 있어야 한다. 둘째, 최근 멀티미디어 장치는 고화질 녹화 또는 녹음과 같은 기능을 탑재하고 있고, 이를 지원하기 위해 실시간 성능 보장이 필요하다. 비록 이러한 문제는 디스크 기반 파일시스템에서는 충분히 다뤄왔으나, 기존의 디스크와 플래시 메모리는 그 특성이 서로 다르기 때문에 플래시 메모리의 특성에 적합한 설계가 필요하다.
본 학위논문에서는, 이러한 문제를 다루는 이동형 멀티미디어 장치를 위한 대용량 실시간 낸드 플래시 파일시스템인 ScaleFFS와 RTFFS를 설계한다. ScaleFFS는 메모리 사용량과 마운트 시간에 관련된 대용량 지원에 대한 문제를 주로 다룬다. 이를 위해 ScaleFFS 에서는 LFS의 기본 설계를 본따 플래시 메모리에 적합하게 수정하여 적용한다. RTFFS는 대용량 지원 뿐만 아니라 실시간 성능까지 보장하는 파일 시스템이다. 이를 위해, 첫째, 본 논문에서는 파일의 색인 구조를 재 설계하여, 갱신할 때 드는 비용이 일정하다. 파일 색인 구조는 μ-Tree와 익스텐트 기반 아이노드 페이지로 구성되어, 대용량 파일을 지원하는 동시에, 갱신할 때 필요한 플래시 쓰기도 일정하다. 둘째, 실시간 기록 중 무효한 공간 수거에 의한 영향이 없도록 설계했다. 이는 각 데이터 종류에 따라 서로 다른 공간 관리 기법을 적용하여 달성할 수 있다. 멀티미디어 파일에 대해서는 플래시 메모리 공간을 통째로 할당하고, 그 이외 파일이나 메타데이터에 대해서는 페이지 단위로 관리하는 기법을 적용한다. 그리고 계층적 구조의 비트맵 구조인 μ-Bitmap과 페이지 단위로 관리 하기 위한 저장 구조인 μ-Summary를 설계하여 전체 플래시 메모리 공간을 적은 메모리로 관리한다. 끝으로 본 논문에서는 실험을 통해, RTFFS의 성능이 다른 파일시스템에 필적하면서, 실시간 쓰기 성능을 보장하며 메모리 사용량이 매우 제한적인 것을 확인한다. 수학적인 분석을 통해 RTFFS에서 보장할 수 있는 최대 대역폭이 플래시 메모리의 순수 쓰기 대역폭에 근접함을 보인다.
