Options
Block Allocation Algorithms for FLASH File Systems
Date Issued
2006
Date
2006
Author(s)
Chuang, Chung-Hao
DOI
en-US
Abstract
Embedded systems have been developing rapidly in recent years, and flash memory technology has become a major part of embedded systems because of its shock-resistance, low power consumption, and non-volatile nature. Since flash memory has write-once and bulk-erase properties, an intelligent allocation algorithm is essential to providing applications efficient storage service. In this paper, we first demonstrate that the online version of FLASH allocation problem is difficult, since we can find an adversary that makes every online algorithm to use as many number of blocks as a naive and inefficient algorithm.
As a result this paper will focus on the offline version of the FLASH allocation problem, and we propose an allocation algorithm called Best Match (BestM) for allocating blocks in FLASH file systems. The performance of the proposed BestM algorithm is compared with a previously proposed First Re-arrival First Serve (FRFS) method through a series of experiments. The experimental results indicate that BestM deliver better performance than FRFS, especially when the length of the page access sequence scales up, or when the number of cells in every block increases.
As a result this paper will focus on the offline version of the FLASH allocation problem, and we propose an allocation algorithm called Best Match (BestM) for allocating blocks in FLASH file systems. The performance of the proposed BestM algorithm is compared with a previously proposed First Re-arrival First Serve (FRFS) method through a series of experiments. The experimental results indicate that BestM deliver better performance than FRFS, especially when the length of the page access sequence scales up, or when the number of cells in every block increases.
Subjects
快閃記憶體
線上演算法
配置
adversary
online
offline
allocation
Flash memory
Type
thesis
File(s)
No Thumbnail Available
Name
ntu-95-R93922130-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):682896d32d7aeffdabc00c782f0c02a8