郭大維臺灣大學：資訊工程學研究所徐秉毅Hsu, Ping-YiPing-YiHsu2007-11-262018-07-052007-11-262018-07-052007http://ntur.lib.ntu.edu.tw//handle/246246/54115隨著可攜式儲存裝置的普及，檔案系統在可攜式儲存裝置上的效能是個逐漸受到重視的課題。本論文的動機起於作業系統中模組化的驅動程式架構，如匯流排驅動程式(Bus Driver)與裝置驅動程式(Device Driver)。本論文根據常見的可攜式儲存裝置儲存媒體─快閃記憶體(Flash Memory)的特性，提出一個過濾式驅動程式層(Filter-Driver-Layered)之快取策略，解決其在不同檔案系統之間的效能差異。並於快取設計中，提出一最近最少使用區間樹(LRU-Interval Tree)來組織及操作快取內的資料，論文中亦提出數個演算法來合併寫入資料。在論文中以檔案系統到通用序列介面(USB Interface)的分析，充分展現出此策略的效能。此論文所提出的快取策略，以系統驅動程式模組方式實作，並安裝在視窗作業系統中(Windows XP/Vista)。於實驗中，某些真實的檔案傳輸上可以改善十倍，甚至更多的傳輸效能。例如，在只使用64KB記憶體空間作為快取的狀況下，於複製Linux核心源代碼時，若使用FAT或NTFS檔案系統，分別可以節省其90% 及50% 的傳輸時間。The popularity of flash memory will soon bring much attention to the criticism of file-system performance over flash memory. This work is motivated by the modularity designs in operating system components, such as bus and device drivers. We propose a filter-driver-layered caching design to resolve the performance gap among file systems and to improve their performance with the considerations of flash memory characteristics. An efficient hybrid tree structure is presented to organize and manipulate the intervals of cached writes. Algorithms are proposed in the merging, padding, and removing of the data of writes. The effectiveness of the proposed approach is shown with some analysis study of FAT-formatted and NTFS-formatted USB flash disks. The proposed cohesive caching policy was implemented as a filter driver in Windows XP/Vista for performance evaluation. In the experiments, more than 10 times of performance improvement was achieved in many cases, when the cache size was only 64KB. Much more substantial improvement was also observed in the experiments. For example, more than 90% and 50% of the file copying times were eliminated for FAT and NTFS formatted flash-memories, respectively, in the copying of Linux image files, when the cache size was only 64KB.List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii List of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Chapter 2 System Architecture and Motivation . . . . . . . . . . . . . . . . . 4 Chapter 3 A Driver-Layer Caching Policy - Cohesive Caching . . . . . . . . 8 3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 An LRU-Interval Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.3 Cohesive Cache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3.1 The Caching Procedure . . . . . . . . . . . . . . . . . . . . . . . 13 3.3.2 The Trimming and Merging Procedure . . . . . . . . . . . . . . 15 3.3.3 The Padding and Merging Procedure . . . . . . . . . . . . . . . . 17 Chapter 4 Behavior Analysis: FAT and the USB Mass Storage Device Driver 21 Chapter 5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . 26 5.1 Performance Metrics and Experiment Setup . . . . . . . . . . . . . . . . 26 5.2 Performance Improvement for the FAT File System: Case Studies . . . . 28 5.2.1 The Number of Write Requests . . . . . . . . . . . . . . . . . . 29 5.2.2 The Data Transmission Time . . . . . . . . . . . . . . . . . . . . 30 5.2.3 The Amount of Transmitted Data . . . . . . . . . . . . . . . . . 33 5.3 Performance Improvement for FAT File Systems: Realistic Cases . . . . . 34 5.4 Benchmark Evaluation: FAT File Systems . . . . . . . . . . . . . . . . . 36 5.5 The Ideal Cache Size for FAT File Systems . . . . . . . . . . . . . . . . 37 5.6 Performance Remarks for NTFS File Systems . . . . . . . . . . . . . . . 39 5.6.1 Performance Improvement for NTFS File Systems: Case Studies . 40 5.6.2 Performance Improvement for NTFS File Systems: Realistic Cases 42 5.6.3 Benchmark Evaluation: NTFS File Systems . . . . . . . . . . . . 43 5.6.4 The Ideal Cache Size for NTFS File Systems . . . . . . . . . . . 43 Chapter 6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 521134665 bytesapplication/pdfen-US快取驅動程式檔案系統快閃記憶體可攜式儲存裝置CachingDriverFile systemFlash memoryRemovable storagethesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/54115/1/ntu-96-R94922007-1.pdf