Skip-list 為基礎的nor 快閃記憶體之檔案系統

Abstract

在快閃記憶體大量用於嵌入式系統的同時，嵌入式系統上的應用程式強大的資料管理需求和快閃記憶體的大容量皆反應需要有一個好的資料管理方。目前在快閃記憶體上的檔案系統或索引結構大都使用邏輯位址的方式，不僅掃描時間長且系統資訊需要佔用掉大量的記憶體。這篇論文試著使用實體參照的方式實作一個skip list 為基礎的索引結構，克服實體參照在nor 快閃記憶體上獨特的議題，如指標更新傳遞、垃圾回收死結等，提供一個有效率的資料管理方案。而文末將demo 如何在skip list 為索引結構的資料管理前提下，簡單的在上面疊架一個檔案系統。

Flash memory has become a crucial component in building embedded computing systems. To manage a massive amount of data, index structures or file systems are needed. The physical characteristics of flash memory, write once and bulk erase in particular, impose many difficulties on realizing structured data. In past work, the notion of logical address space is introduce to decouple changes to data and to the physical addresses of them. To map between logical addresses and physical addresses, RAM-resident translation tables are needed, it may require lengthy initialization scan procedure. In this work, a skip-list implementation based on physical pointers is proposed. It is to investigate the feasibility of organizing data with physical pointers over flash memory. The benefits are that no translation tables and initialization scan are needed. It is also demonstrated that a file system can be easily realized based on the proposed skip-list implementation