基于嵌入式的文件系统研究

耿庆田, 赵宏伟, 常 亮

(1. 吉林大学 计算机科学与技术学院, 长春 130012； 2. 长春师范大学 计算机科学与技术学院, 长春 130032)

0 引 言

当前嵌入式技术发展日新月异, 在人们的生活中, 嵌入式产品无处不在。许多嵌入式产品装载了大容量的存储介质, 由于Flash存储器存储容量大, 载体体积小, 被大量应用在嵌入式设备中, 并且在这些Flash存储器中的信息量逐渐增多[1-3]。因此, 需要构建一种稳定的嵌入式文件系统实现对这些信息进行高效管理。

操作系统的重要组成部分是文件系统, 文件系统对存储数据的各种操作效率的高低关系到操作系统性能的好坏。嵌入式文件系统由于受到Flash存储介质容量和操作方式的局限, 实现对嵌入式数据高效操作并保证其稳定性对嵌入式文件系统至关重要。

1 嵌入式系统

1.1 嵌入式系统构成

1) 硬件。其核心部件是微处理器, 用来实现运算功能。存储器分为高速缓存RAM和辅助非易失性存储器NVRAM[4,5], RAM用来存放可执行程序代码和中间运算结果； NVRAM(NorFlash、 NandFlash)用来存放数据及程序代码。通用设备接口(如A/D、D/A、I/O等)负责嵌入式系统与外界应用的交互。

2) 应用软件。由单线程或多线程任务实现文件系统功能的各种应用程序。

3) 实时操作系统(RTOS: Real Time Operating System)[6]： 对外界事件实现快速处理, 分配管理CPU运算任务并支撑应用软件的正常运行。

1.2 嵌入式操作系统

嵌入式操作系统(EOS: Embedded Operating System)是负责嵌入式系统中管理全部资源分配、 任务调度、 控制、 协调并发活动的系统[7,8]。其基本功能相对专一, 能通过装卸各种模块实现相应功能。

嵌入式系统由于内存较小, 所以操作系统的内核也小。在开发嵌入式文件系统时要把一些必要的应用配置写入操作系统的内核程序中, 通过使用一些调度优化算法使操作系统保持其运行灵敏性及空间的小巧性。

2 嵌入式文件系统

2.1 系统架构

为方便文件系统在不同的操作系统与不同开发板上开发和移植。系统采用分层设计结构, 提供了多文件系统接口支持。系统充分考虑嵌入式文件系统功能扩展, 在软件架构设计方面没有采用传统的单一架构方式, 而是采取多模块的设计架构, 各模块之间功能独立, 通过接口可互相通信。

由于FAT文件系统存储机制是按序存取并与链表相结合的方式[9]。当文件目录下有大量数据时, I/O读写速度在很大程度上要低于RAM操作速度, 使整个文件系统的操作非常缓慢。但FAT文件系统有其历史性及广泛性, 考虑到系统兼容性, 需要保留FAT文件系统的架构。所以既解决了与FAT文件系统兼容, 又实现了大容量文件高效存储操作, 主要完成下面两点工作。

1) 保留传统的FAT顺序存储的机制, 设计的索引数据被看作普通数据存储, 在FAT的TABLE表中标注； 设置SUPER数据块记录文件系统索引信息。

2) 修改FAT的目录索引方式, 建立B+树的目录存取操作机制, 提高文件目录下大量数据的读写、 创建和删除等操作的效率。

2.2 采用技术

1) 损耗平衡算法。Flash的使用寿命是由Flash存储数据擦写域的擦写次数决定的。为避免某一擦写域因超过最大擦写次数成为坏块, 存储数据时需对擦写域均衡使用。使用磨损程度检测算法[10](The Wear-Leveling Algorithm)可以均衡使用Flash擦写域。该算法的关键在于以下两点：

① 使用擦除次数最少的擦写域；

② 如果某一区域被数据长期占据, 则把该数据移到其他区域, 回收被占区域供擦写使用。

2) 位图(bitmap)。数据的位图存取方式有3点优势：

① 节约存储空间, 位图存储中的一位能包含一个数据块粒度的信息;

② 位图访问操作效率高, 位图的访问过程不需要遍历操作, 可直接通过计算方式实现定位;

③ 位图可为海量数据存取提供高效管理与信息统计。

在μC/OS-Ⅱ优先级位图、 B+树存储、 文件不等长目录名存储等多个功能模块用到位图技术。

3) 倒排索引存储。倒排索引存储用来存放在文件搜索中某关键词在一个或者一组文档中的存储位置的映射, 其过程根据数据属性查找记录。它反映了文件系统中某结点的键值与指针和链接地址的关系。在海量数据存储和数据搜索技术中, 倒排索引存储应用广泛。

4) B树。B树是一种平衡搜索树, 应用在数据存储技术中可减少磁盘I/O次数, 提高数据查找效率。很多数据库系统在存取各种数据信息时也用到B树算法或改进的B树算法。

2.3 功能设计

1) 层次模块划分。按照嵌入式文件系统的功能划分, 系统分为4个层次(见图1)。

图1 文件系统层次及系统结构

① 物理驱动层是利用对寄存器地址操作获得硬件底层数据同时为中间层提供访问接口。把32 M8位NandFlash存储器K9F2808U0C按地址划分成主存储区A和次存储区B。A区用来存储数据, B区用来存储控制信息及校验数据。

② 中间件层是承上启下层, 提供不同设备统一访问封装接口。文件系统所要完成的一系列初始化工作如存储部件初始化、 缓存构建、 分区参数读取和接口分配等都要经中间层进行优化处理。

③ 文件系统层提供文件格式化及通过调用相关文件系统接口实现文件访问功能。

④ API层处于文件系统最高层, 直接面对用户应用, 为用户提供访问接口。同时该层还对文件系统提供一些优化操作, 保证系统的稳定性。

2) 存储介质分区。存储介质的分区标准是由磁盘分区标准设计的。介质可预留一部分空间由系统设计者自由支配, 其他存储空间要进行分区格式化操作才能使用。

主引导扇区MBR的位置处在存储介质的0柱面0磁头1扇区, 其他扇区的空间位置可通过计算获得。当系统运行时, 首先执行BIOS(Basic Input Output System)中命令, 然后跳转到MBR扇区执行其首条命令。这时, 系统的运行由MBR掌握。

存储介质的其他分区称为扩展分区。其中每个逻辑分区都有相当于MBR的扩展引导记录(EBR： Extended Boot Record)。其中包含一个扩展分区表和这个扇区的记录标签。

2.4 文件系统初始化

图2 文件系统初始化

当文件系统启动时, 初始化索引(见图2)。这时要读取文件系统的第1个扇区----启动扇区BPB中的数据。数据的内容是存储介质的容量信息及FAT文件系统的数据信息。其过程如图2所示。

首先申请建立位图结构空间； 其次获取标定具体位置的B+树索引信息, 把获取的信息按类型划分为块信息(块信息主要包含文件系统根目录的初始位置、 位图信息、 系统记录)、 根节点位图信息等； 再次获取并初始化文件系统各分支位图信息； 最后初始化目录项管理的一二级位图信息。

2.5 目录操作

1) 目录创建。FAT文件系统的目录分别由长目录项和短目录项组成, 且长短目录项是成对相配。对于字符数较多的文件名, 一个目录项不能完全存放, 需要多个目录项存放。长短目录项成对使用, 排列有序并且在物理介质上也连续, 以提高目录项的利用率。在长目录项的第1个字节中存放其序号, 最后的长目录项标识为0x40。

当建立文件时, 如果当前目录项没有配给入口位图, 则可到一级位图中申请入口位图, 并把该目录项的位图位置信息记录在相应的叶子节点中; 然后在位图中搜索空闲空间, 设置标记为使用状态, 并记录该位置的起始信息和空间大小。

2) 目录删除。删除键值时, 要根据键值的性质在目录项的物理介质位置做标识。若要删除系统中文件或目录项, 则把其入口位图标识在B+树相应结点； 如果目录项的位图位置标识为空, 则应对其一级入口位图做标识。具体过程如下：

① 使用具体的路径名搜索到相应的位置, 如果该位置是目录项, 记下子目录项B+树地址；

② 把字符串0xE5填写到短目录项第1个字节, 表明该目录被删除；

③ 判断B+树节点是否应删除, 若需要删除, 则修改B+树目录索引并删除节点位图, 修改入口表位置及父节点指针；

④ 删除存储节点信息, 更新二级位图信息。若二级位图为空, 则把一级位图相应位置标识为0；

⑤ 保留当前FAT目录项链表结构, 对FAT表对应字段标注相应信息。

2.6 中间件层

中间件层主要是管理NandFlash存储介质中的Flash设备, 包括设备分区块、 地址转化、 读写动态平衡以及垃圾文件的回收处理。本层又细化分为：

1) 驱动接口层, 主要检索并标记存储介质的坏块区域, 记录设备层的相关信息, 实现对介质自身的扇区和接口的各种调用操作;

2) 设备层, 完成对不同的存储介质访问接口的统一封装, 对设备的调用进行管理;

3) 卷区层, 实现对不同分区的整合管理, 为不同设备的不同分区分配相应盘符, 以便用户读取不同设备的数据信息。

2.7 物理驱动层

为不同存储设备实现常规的数据访问驱动接口, 中间件层把由本层实现的接口进行封装, 提供给上层进行访问。文中使用MagicARM2410开发板, 其芯片是K9F2808U0C型号NandFlash芯片, NandFlash模拟图如图3所示。

图3 NandFlash模拟图

所采用的NandFlash芯片规格如下[11,12]：

存储单元阵列：(16 M+512 K)位×8位;

数据寄存器：(512+16)位×8位;

自动编程和擦除： 页编程, (512+16)Byte； 域擦除, (16K+512)Byte;

页面读操作： 页面规格, (512+16)Byte, 随机访问, 10 μs(最大)。

I/O管脚可用作地址线、 数据输入/输出以及命令入口, 片内写控制自动实现所有编程和擦除功能, 包括脉冲周、 内部校验和数据冗余。

3 系统测试

笔者所采用的测试方法是通过模拟器进行模拟测试, 使用开发板JTAG进行实验测试。

在实验测试时需要开发板JTAG调用NandFlash存储介质物理层的扇区驱动接口, 模拟器通过建立一个二进制映像文件对NandFlash进行仿真, 所建立的文件结构应与MagicARM2200开发板中NandFlash同样标准, 并提供与NandFlash物理扇区驱动相同标准的扇区访问接口。由于中间件层和文件系统层的结构一致, 因此其运行效果一致。

文件查询对比测试：

对嵌入式文件系统相同目录下1 000个随机文件数据随机进行100个文件的访问, 使用微机模拟器进行模拟实验, 对所得数据进行对比分析(其中对比参数是Windows时钟节拍和对扇区访问次数), 结果如表1所示。

在实验测试过程中, 不使用中间件层的页缓存机制, 直接访问磁盘底层扇区数据, 微机中Windows操作系统会自动提供对磁盘文件读取的高速缓存, 虽然产生一些误差, 但不影响实验数据的对比性分析。

表1 模拟器读写对比测试

4 结 语

笔者在嵌入式环境中对文件系统的系统程序进行设计开发, 提出了对嵌入式文件系统开发的具体方法。分析了嵌入式文件系统采用的关键技术, 通过对FAT文件系统的研究, 结合存储介质的使用情况, 采用位图存储技术, 实现了对嵌入式文件系统的索引存储和对空闲目录项的管理操作。采用模拟器进行模拟仿真开发, 并在MagicARM2410开发板上实现了该文件系统的功能模块测试, 验证了其可行性。

参考文献：

[1]崔建华, 孙红胜, 王保进. 硬件实时操作系统的设计与实现 [J]. 电子技术应用, 2008(5): 34-37.

CUI Jian-hua, SUN Hong-sheng, WANG Bao-jin. The Design and Realization of Hardware RTOS [J]. Application of Electronic Technique, 2008(5): 34-37.

[2]DANIELP BOVET, MARCO CESATI. Understanding the Linux Kernel [M]. 3 rd ed. USA: O’REILY Press, 2006: 126-128.

[3]郑文静, 李明强, 舒继武. Flash存储技术 [J]. 计算机研究与发展, 2010, 47(4): 716-726.

ZHEN Wen-jing, LI Ming-qiang, SHU Ji-wu. Flash Storage Technology [J]. Journal of Computer Research and Development, 2010, 47(4): 716-726.

[4]何先波. 嵌入式软件开发平台中的文件系统封装机制 [J]. 计算机应用, 2010, 30(1): 118-120,123.

HE Xian-bo. File System Encapsulation Mechanism in Embedded Software Development Platform [J]. Journal of Computer Applications, 2010, 30(1): 118-120,123.

[5]STEPHEN TWEEDIE, THEODORE TS’O. Design and Implementation of the Second Extended Filesystem [EB/OL]. (2013-05-21). Http://e2fsprogs.sourceforge.net/ext2intro.html.

[6]潘沁, 周新志, 魏刚. 磨损均衡算法在NAND Flash管理中的改进 [J]. 微计算机信息, 2007, 23(1/3)： 301-302.

PAN Qin, ZHOU Xin-zhi, WEI Gang. The Improvement of Wear-Leveling Algorithm in NAND Flash Management [J]. Microcomputer Information, 2007, 23(1/3)： 301-302.

[7]JAKE WIRES, PMICHAEL J FEELEY. Secure File System Versioning at the Block Level [D]. Vancover: College of Computer Science and Technology, The University of British Columbia, 2006： 55-58.

[8]张继珂, 谷青范. 基于Flash的嵌入式文件系统设计与实现 [J]. 工业控制计算机, 2011, 24(4)： 84-86.

ZHANG Ji-ke, GU Qing-fan. Design and Implementation of Embedded File System Based on Flash Memory [J]. Industrial Control Computer, 2011, 24(4)： 84-86.

[9]田莉. 嵌入式系统中USB接口的设计与实现 [J]. 自动化与仪器仪表, 2011(1): 33-34.

TIAN Li. Design and Implementation of Embedded USB Interface [J]. Automation & Instrumentation, 2011(1)： 33-34.

[10]孙晓荣, 时兴. 基于嵌入式Linux的Flash文件系统的实时性能研究 [J]. 微计算机信息, 2012(9): 175-176, 243.

SUN Xiao-rong, SHI Xing. Performance Evaluation about Flash File System on Embedded Linux [J]. Microcomputer Information, 2012(9): 175-176,243.

[11]王培进, 李晓路. 嵌入式系统集成开发平台的设计与实现 [J]. 计算机应用与软件, 2012, 29(5): 109-113.

WANG Pei-jin, LI Xiao-lu. Design and Implementation of Embedded System [J]. Computer Applications and Software, 2012, 29(5): 109-113.

[12]张云, 惠晓威, 肖迎杰. 基于ARM的嵌入式文件系统研究与设计 [J]. 计算机系统应用, 2010, 19(3): 229-232.

ZHANG Yun, HUI Xiao-wei, XIAO Ying-jie. Design and Implementation of an Embedded File System Based on ARM [J]. Computer Systems & Applications, 2010, 19(3): 229-232.