劉邦鋒臺灣大學：資訊工程學研究所莊中豪Chuang, Chung-HaoChung-HaoChuang2007-11-262018-07-052007-11-262018-07-052006http://ntur.lib.ntu.edu.tw//handle/246246/53878Embedded 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.Contents 1 Introduction 4 2 Flash Memory Allocation Model 6 2.1 Flash Memory Systems 6 2.2 Page Access Sequence 7 2.3 Flash Memory Allocation 7 3 Algorithms 9 3.1 The Online Problem 9 3.1.1 First-Come-First-Serve Algorithm 10 3.2 The Offline Problem 10 3.2.1 First-Rearrival-First-Serve 10 3.2.2 Best Match 12 4 Experimental Results 17 4.1 Implementation Issues 17 4.1.1 Intersected Intervals 17 4.1.2 Contained Intervals 18 4.1.3 Disjoint Intervals 18 4.1.4 Time Complexity 19 4.2 Experimental Settings 19 4.3 Effect of The Length of Page Access Sequence 20 4.4 The Effects of Cell Number 20 5 Conclusion 24178358 bytesapplication/pdfen-US快閃記憶體線上演算法配置adversaryonlineofflineallocationFlash memorythesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53878/1/ntu-95-R93922130-1.pdf