（计算机应用技术专业论文）基于car构件的嵌入式文件系统ktfs的研究.pdf

摘要 随着嵌入式技术的不断发展，嵌入式应用中出现越来越复杂的数 据资源需要管理，因此嵌入式文件系统的重要性显得更加突出。和普 通的文件系统不同，嵌入式文件系统设计不仅要求满足数据存储的各 种需要，而且要尽量降低因文件系统的加入对整个系统性能的负面影 响。这些影响主要体现在实时响应、可移植性、可裁剪性和可配置性 等方面。本文所研究的k t f s 文件系统是基于e l a s t o s 嵌入式操作系统 “灵活志核技术，采用f a t 存储结构和f l a s h 设备存储，以c a r 构件 实现的嵌入式文件系统。 本文首先在研究k t f s 文件系统相关理论知识的基础上，详细分 析了以构件实现文件系统的优缺点，并给出了构件化文件系统的理论 模型和体系结构，同时将文件系统自底向上依次分为四个层次：存储 设备驱动、高速缓存管理、文件系统内核以及文件系统接口层。针对 传统文件系统只能加载到内核态或用户态的不足，采用e l a s t o s 的“灵 活内核技术，构件化的k t f s 根据需要可动态的加载内核态或用户 态，以确保系统的稳定性和高效性；再依据k t f s 的接暖设计原则， 抽象出套文件系统接口并在e l a s t o s 2 1 上实现；最后，将k t f s 文件 系统加载至l j e l a s t o s 系统中，从整体上对其进行功能和性能的测试，测 试结果验证了k t f s 接豳集的完备性和可靠性。 本文的主要研究成果包括以下几方面： 1 论证了以构件形式实现文件系统的可行性和必要性，并指出 了构件化文件系统要解决的关键问题； 2 依据k t f s 接酲设计原则，在e l a s t o s 操作系统上设计并实现了 文件系统接口； 3 对k t f s 文件系统中缓存块替换算法l r u 做了相关改进，采 用h a s h 表与l r u 链表相结合的办法来解决l r u 算法的效率问题； 关键词： c a r ，嵌入式，k t f s ，构件，e l a s t o s i i a b s t r a c t e m b e d d e df i l es y s t e mb e c o m sm o r ea n dm o r ei m p o r t a n t ，b e c a u s e m a n yd a t ar e s o u r c e ss h o u l db em a n a g e di ne m b e d d e da p p l i c a t i o n sa l o n g w i t ht h ed e v e l o p m e n to fe m b e d d e dt e c h n o l o g y t h ed i f f e r e n c eb e t w e e n n o r m a lf i l es y s t e ma n de m b e d d e df i l es y s t e mi st h a td e s i g no ft h el a t t e r s h o u l dn o to n l ys a t i s f yt h ev a r i o u sr e q u e s t sf o rd a t as t o r a g eb u ta l s o r e d u c et h en e g a t i v ee f f e c tt oe n t i r es y s t e m t h en e g a t i v ee f f e c tm a i n l y e x p r e s s e s a tt h e a s p e c t s o fr e a l - t i m e r e s p o n s e ，p o r t a b i l i t y a n d c o n f i g u r a b i l i t y k t f si se m b e d d e df i l es y s t e mb a s e do nt h ee l a s t o s a g i l e c o r et e c h n o l o g y , u s i n gf a ta ss t o r a g es t r u c t u r ea n df l a s ha s s t o r a g ee q u i p m e n ta n di m p l e m e n t i n gi nc a rc o m p o n e n t i nt h i sp a p e r , w ef i r s tr e s e a r c ht h er e l e v a n tt h e o r e t i c a lk n o w l e d g eo f t h ek t f s ，t h e na n a l y s et h ea d v a n t a g ea n dd i s a d v a n t a g eo ft h ec o m p o n e n t f i l es y s t e ma n ds e tu pt h et h e o r e t i c a lm o d e la n d a r c h i t e c t u r e ，d i v i d i n gt h e f i l es y s t e mi n t of o u rl e v e l s ：f l a s hb l o c kd e v i c ed r i v e r , c a c h em a n a g e m e n t ， f i l e s y s t e m k e m e la n df i l e s y s t e mi n t e r f a c e1 a y e r k t f sc a nb e d y n a m i c a l l yl o a d e di n t ot h ek e r n e lo r u s e rs t a t ef o rs y s t e ms t a b i l i t ya n d e f f i c i e n c yt h r o u g hu s i n gt h ee l a s t o s a g i l e ”c o r et e c h n o l o g yw h e r e a s t r a d i t i o n a lf i l es y s t e mc a no n l yb el o a d e di n t ot h ek e r n e lo ru s e rs t a t e i n t h em e a n t i m e ，a b s t r a c ta n di m p l e m e n tf i l es y s t e mi n t e r f a c ea c c o r d i n gt o t h ep r i n c i p l eo fi n t e r f a c ed e s i g n f i n a l l y , r e s u l t sv a l i d a t et h ec o m p l e t i o n a n dr e l i a b i l i t yo fi n t e r f a c es e ta c c o r d i n gt ot h et e s t i n go nf u n c t i o n a l i t ya n d p e r f o r m a n c ea f t e rk t f si sa t t a c h e dt ot h ee l a s t o ss y s t e m t h em a i nr e s e a r c ha c h i e v e m e n t sa r es u m a r r i z e da sf o l l o w s ： 1 d e m o n s t r a t ef e a s i b i l i t ya n d n e c e s s i t yo fc o m p o n e n tf i l es y s t e m ， a n dp o i n to u tt h ek e yp r o b l e mt os o l v e ； 2 d e s i g na n di m p l e m e n tt h ei n t e r f a c es e to fk t f sb a s e do nt h e p r i n c i p l eo fd e s i g na te l a s t o s ； 3 i m p r o v el r ub l o c kr e p l a c e m e n ta l g o r i t h mo ft h ef i l es y s t e m c a c h et h r o u g hu s i n gt h ec o m b i n a t i o no fh a s ht a b l ea n dl r ul i s tt o e n h a n c et h ee f f i c i e n c yo fl r u ； k e y w o r d s ： c a r , e m b e d d e ds y s t e m ，k t f s ，c o m p o n e n t ，e l a s t o s i i i 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不合任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名：筠隐lc 泐7 年厶月 i o 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 研究生在校攻读学位期间论文工作的知识产权单位属湖南师范大学。 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“ ) 作者签名：捌日期：f 年 月口 日 导师签名：己豸嘭，日期：叫年1 月f 口日 基于c a r 翰付的嵌入式文件系统k t f s 熬曩舅究 1引言 1 1 “和欣”嵌入式操作系统概述 对于操作系统的概念，一些较权威的教程中将操作系统定义为 “用以控制和管理计算机系统资源，方便用户的程序和数据结构的集 合 。从资源管理的角度来看，操作系统是计算机硬件和软件资源的 管理者。从使用者的角度来看，操作系统是计算机与用户之闻进行交 互的接口，用户通过这种接口使用计算机 1 1 。其作用类似于城市交通 的决策、指挥、控制和调度中心，它组织和管理整个计算机系统的软、 硬件资源，在用户和程序之间分配系统资源，使之协调一致、高效地 完成各种复杂的任务。 1 1 。1 嵌入式操作系统 图1 1 操作系统 嵌入式操作系统与嵌入式系统密不可分。嵌入式系统( e m b e d d e d s y s t e m ) ，是以应用为中心，以计算机技术为基础，并且软硬件可定制， 适用于各种应用场合，对功能、可靠性、成本、体积、功耗有严格要 求的专用计算机系统【2 1 。它一般由嵌入式微处理器、外围硬件设备、 硕十学佩论文 嵌入式操作系统以及用户的应用程序等四个部分组成，用于实现对其 他设备的控制、监视或管理等功能。嵌入式系统几乎包括了生活中 的所有电器设备，如掌上p d a 、移动计算设备、电视机顶盒、手机 上网、数字电视等。 嵌入式操作系统是一种支持嵌入式系统应用的操作系统软件，它 是嵌入式系统( 包括硬、软件系统) 极为重要的组成部分，通常包括与 硬件相关的底层驱动软件、系统内核、设备驱动接髓、通信协议、图 形界面、标准化浏览器等【3 1 。嵌入式操作系统具有通用操作系统的基 本特点，如能够有效管理越来越复杂的系统资源；能够把硬件虚拟化， 使得开发人员从繁忙的驱动程序移植和维护中解脱出来；能够提供库 函数、驱动程序、工具集以及应用程序。 与通用操作系统相比较，一个典型的嵌入式操作系统还应该具备 以下一些特点鸭 1 。体积小。嵌入式系统不具备像硬盘那样大容量的存储介质， 而大多使用闪存( h a s hm e m o r y ) 作为存储介质。这就要求政入式操 作系统结构紧凑，体积微小。 2 实时性。大多数嵌入式系统都是实时系统，而且多是强实时 多任务系统，要求相应的嵌入式操作系统也必须是实时操作系统。 3 注重稳定性。嵌入式系统一旦开始运行就不需要用户过多的 干预，这就要求负责系统管理的o s 具有较强的稳定性。 嵌入式操作系统伴隧着嵌入式系统的发展经历了四个比较明显 的阶段【5 j ： 第一阶段：无操作系统的嵌入式算法阶段，以单芯片为核心的可 编程控制器形式的系统。应用于一些专业性极强的工业控制系统中， 通过汇编语言编程对系统进行直接控制，运行结束后清除内存。系统 结构和功能都相对单一，处理效率较低，存储容量较小，几乎没有用 户接口。 基，c a 爻构识：戆嵌入式文件系统k t f s 的研究 第二阶段：以嵌入式c p u 为基础、简单操作系统为核心的嵌入 式系统。c p u 种类繁多，通用性比较差；系统开销小，效率高；一 般配备系统仿真器，操作系统具有一定的兼容性和扩展性；应用软件 较专业，用户界面不够友好；系统主要用来控制系统负载以及监控应 用程序运行。 第三阶段：通用的嵌入式实时操作系统阶段，以嵌入式操作系统 为核心的嵌入式系统。能运行于各种类型的微处理器上，兼容性好； 内核精小、效率高，具有高度的模块化和扩展性；具备文件和目录管 理、设备支持、多任务、网络支持、图形窗翻以及用户界面等功能； 具有大量的应用程序接口( 肿i ) ；嵌入式应用软件丰富。 第四阶段：与i n t e r n e t 相结合的嵌入式系统。这是一个正在迅速 发展的阶段。目前大多数嵌入式系统还孤立于i n t e r n e t 之外，但随着 i n t e r n e t 的发展以及i n t e r n e t 技术与信息家电、工业控制技术等结合网 益密切，嵌入式设备与i n t e r n e t 的结合将代表着嵌入式技术的真正未 来。 目前，嵌入式操作系统已经从简单走向成熟，主要有v x w o r k 、p a l m o s 、w i n d o w sc e 、l i n u x 等。国内的嵌入式操作系统研究开发有 两种类型，类是基于国外操作系统二次开发完成的，如海信的基于 w i n d o w sc e 的机顶盒系统；另一类是中国自主开发的嵌入式操作系 统，如凯思集团公司自主研制开发的嵌入式操作系统h o p e no s ( 女 娲计划) 等。 1 1 。2 和欣嵌入式操作系统 e l a s t o s 即和欣嵌入式操作系统是3 2 位、微内核，基于构件、中 间件技术的面向智能手机应用的新代嵌入式网络操作系统，其功能 模块全部是可拆卸的构件，按需动态裁剪或运行时动态加载构件【6 1 。 操作系统提供的功能模块全部基于c a r 构件技术实现，应用系统可 硕十学位论文 以按照需要裁剪组装，或在运行时动态加载必要的构件。e l a s t o s 提供 了套完整的系统服务构件及系统a p i 、功能全面的动态链接构件 库、函数库。“和欣 操作系统的体系结构如图董2 ： 。| i “豳 紧三二= = 二型一一 特权态r ! 一嬲 图1 2e l a s t o s 体系结构图 e l a s t o s 区别于其他嵌入式操作系统的特点是【7 1 ： 1 全面的面向构件技术，在操作系统层提供了对构件运行环境 的支持，用构件技术实现了“灵活 的操作系统。基于e l a s t o s 技术， 可实现软件“用户零维护 、“瞬间肩动 ，各类应用软件无需安装， 可“点击运行、“滚动下载 ，不同厂家的软件以髫标代码形式实现 “无缝链接 ，支持应用软件跨平台运行。 2 体积小，高效率，面向网络时代的嵌入式信息设备应用。提 供w i n 2 0 0 0 x p 仿真技术，支持二进制代码兼容；可动态加载构件， 在网络时代，软件构件就相当于零件，零件可以随时装配。c a r 技 术实现了构件动态加载，使用户可以随时从网络得到最新功能的构 件。 3 易于利用第三方软件丰富的系统功能。c a r 技术的软件互 操作性，保证了系统开发人员可以利用第三方开发的，符合c a r 规 范构件，共享软件资源，缩短产品开发周期( t i m et om a r k e t ) 。同 4 基于c a r 构忭的嵌入式文件系统k t f s 酶研究 时用户也可以通过动态加载第三方软件扩展系统的功能。 4 支持软件复用。软件复用是软件工程长期以来追求的目标， c a r 技术提供了构件的标准，二进制构件可以被不同的应用程序使 用，使软件构件真正能够成为“工业零件 。充分利用“久经考验 的软件零件，避免重复性开发，是提高软件生产效率和软件产品质量 的关键。 5 提高系统的可靠性、容错性。由于构件运行环境可控制，可 以避免因个别构件的崩溃而波及到整个系统，提高系统的可靠性。同 时，系统可以自动重新启动运行中意外停止的构件，实现系统的容错。 1 2 嵌入式文件系统概述 1 2 1 文件系统 文件系统是操作系统的重要组成部分，用于控制对数据、文件及 设备的存取。它提供对文件和目录的分层组织形式、数据缓冲以及对 文件存取权限的控制【羽。 文件系统必须提供必要的用来创建文件、删除文件、读写文件等 相应的系统调用。文件的存放通过目录完成，所以对目录的操作是文 件系统功能的一部分。一个完善的文件系统必须具备以下功能f 9 】： 提供对文件和嚣录的分层组织形式 实现按名存取 文件的查找 文件的共享和保护 辅助存储空间的管理 文件系统作为操作系统中的一个重要模块，不但对用户提供文件 操作调用，也对系统中的其它模块提供功能支持。同时，它也需要调 用其它系统模块的功能。 硕+ 学位论文 文件系统在操作系统中所处的位置如图1 3 。 图1 3 文件系统在操作系统所处的位置 1 2 2 嵌入式文件系统 冒前在通用计算机上已经有很多成熟的文件系统，但是这些文件 系统并不适合直接用到嵌入式系统中进行数据信息的存储：第一，嵌 入式系统的应用条件远比计算机恶劣，电源电压的不稳定以及突发性 断电可能会使数据不一致甚至威胁到物理存储设备的可用性，通用文 件系统对于可靠性的设计考虑不足；第二，通用文件系统是针对系统 资源非常丰富的计算机平台并基于速度较慢的磁盘驱动器设计的，它 们常常大量使用数据缓存技术，为了提高文件系统整体数据处理的速 度，通常要耗费比较多的系统资源雒o l 。这与嵌入式系统中系统资源十 分有限的情况不同；第三，嵌入式系统中的存储设备往往是f l a s h ， 由于f l a s h 设备的物理特性，例如在同一个数据块上进行重复写操作 前一定要进行擦除操作，通用文件系统不能对其进行良好的支持。因 此，在嵌入式系统中一般需要针对不同软硬件平台以及应用环境，开 发专门的嵌入式文件系统，嵌入式文件系统除了满足一般文件系统的 基于c a r 构件的嵌入式文件系统k t f s 的研究 基本要求外，还具有如下一些特性： 1 存储介质的特殊性 嵌入式设备一般具有体积小、可移动等特点，它的这些特点决定 了其存储没备的特殊性：容量适中、功耗小、易拆卸、抗机械振动等。 典型的存储设备有r a m ，n o rf l a s h ，n a n df l a s h 等。 2 文件系统快速恢复的特殊要求 嵌入式设备的另一特点就是电源供给的不稳定性，不可预知的断 电随时有可能发生。对于传统的文件系统而言，忽然的断电会带来文 件系统的不一致，严重的可能导致整个文件系统的崩溃。l i n u x 所使 用的主要文件系统e x t 2 在每次非正常关机后都要用特定的工具，花 费较长的开寸问来检查和修复文件系统的错误1 1 1 】。而且严重的时候文件 系统无法恢复到断电前的状态，可能导致很多关键信息的丢失。这对 于可能频繁断电的嵌入式设备而言，是件让人无法忍受的事情。于是 需要有一种特殊的防断电的文件系统来保证系统的稳定性和数据的 安全性。 3 跨平台的安全性 由于嵌入式存储设备比较方便，嵌入式文件系统的跨平台安全性 必须考虑。存储设备上存放用户文件和一些重要信息，当在不同的嵌 入式设备上使用这个存储设备时，有必要对用户的身份进行识别后， 才能进行常规的文件操作。 4 实时响应 嵌入式系统一般具有实时性的要求，即使是软实时的要求，也要 求嵌入式操作系统对内部和外部的响应时间确定。嵌入式文件系统应 该能满足实时系统实时性的要求，提供相应缩短时间的机制和策略， 为文件的管理和操作提供较短的时间响应。 5 接口标准的开放性和可移植性 嵌入式应用的领域非常广泛，所采用的实时操作系统和硬件环境 硕十学能论文 也千差万别。为了适应这种差异性，文件系统组件应该不依赖于具体 的硬件环境和操作系统，使其能够比较容易的移植到各种应用环境 中。 1 3 两种常见的嵌入式文件系统 1 3 1 可扩展文件系统 e x t 2 ( e x t e n d e d2f i l es y s t e m ) 是l i n u x 中使用最普遍的文件系统， 已成为l i n u x 事实上的标准文件系统【1 2 】，它已经取代了它的前任一扩 展文件系统( 或e x t ) 。与其它文件系统一样，e x t 2 文件系统中的文 件保存在数据块中。对同一个e x t 2 文件系统而言，其上所有的数据 块大小都是一样的。与某些文件系统不同的是，不同的e x t 2 文件系 统的数据块大小可以不一样，数据块大小可以在建立e x t 2 文件系统 时指定，并且作为文件系统的基本参数保存在文件系统中，单个文件 所占用的空闻便按照这个指定大小的数据块为单位分配。块设备上的 大多数数据块用来保存文件的实际数据，而部分数据块则用来定义文 件系统的结构。e x t 2 文件系统中引入了一个非常重要的概念，即虚拟 文件系统( v f s ) 。v f s 作为实际文件系统( e x t 2 ) 署h 操作系统之间的接 口，将实际的文件系统署瑟操作系统隔离开来。e x t 支持的文件最大为 2g b ，支持的最长文件名为2 5 5 个字符【1 3 1 ，但它不支持索引节点( 包 括数据修改时间标记) 。e x t 2 对e x t 进行了改进，它的优点是： 1 e x t 2 支持达4 t b 的内存。 2 。e x t 2 文件名称最长可以到1 0 1 2 个字符。 3 当创建文件系统时，管理员可以选择逻辑块的大小( 通常大 小可选择1 0 2 4 、2 0 4 8 和4 0 9 6 字节) 。 4 。e x t 2 实现了快速符号链接。不需要为此而分配数据块，并且 将图标名称直接存储在索引节点表中。 纂于c a r 构件舱嵌入式文钟系统k t f s 的磺究 因为e x t 2 文件系统的稳定性、可靠性和健壮性，所以几乎在所 有基于l i n u x 的系统( 包括台式机、服务器和工作站甚至一些嵌入 式设备) 上都使用e x t 2 文件系统【1 4 1 。然而，当在嵌入式设备中使用 e x t 2 时，它有一些不足： 1 。e x t 2 是为象i d e 那样的块设备设计的，这些设备的逻辑块大 小是5 1 2 字节，1k 字节等这样的倍数。当有多种存储设备而扇区大 小不一致的情况下，e x t 2 显然不太适合。 2 e x t 2 没有提供对基于扇区的擦除写操作的良好管理。在 e x t 2 中，为了在一个扇区中擦除单个字节，必须将整个扇区复制到 r a m ，然后擦除，然后重写入【1 5 】。考虑到f l a s h 设备具有有限的擦除 次数，超过该限度就不能使用它们，所以频繁的擦除将导致其些数据 不可用。 3 在出现电源故障时，e x t 2 不是防崩溃的。 1 3 。2 霉志闪存文件系统 瑞典的a x i sc o m m u n i c a t i o n s 开发了最初的j f f s ( j o u r n a l i n gf l a s h f i l es y s t e m ) ，r e dh a t 的d a v i dw o o d h o u s e 对它进行了改进。第二个 版本，j f f s 2 ，作为用于微型嵌入式设备的原始闪存芯片的实际文件 系统而出现。j f f s 2 闪存文件系统中闪存管理大致包含3 个功能模块， 分别足：块分配模块、垃圾收集模块、耗损平衡模块【辐l 。相对于e x t 2 ， j f f s 2 有以下这些优点： 1 j f f s 2 在扇区上直接执行闪存擦除写读操作，比e x t 2 文 件系统效率更高。 2 j f f s 2 提供了比e x t 2 更好的崩溃掉电安全保护。当需要更 改少量数据时，e x t 2 文件系统将整个扇区复制到内存( d r a m ) 中， 在内存中合并新数据，并写圈整个扇区。这意味着为了更改单个字， 必须对整个扇区( 6 4k b ) 执行读擦除写例程，这样做的效率非 硕十学位论文 常低。在极端情况下，当正在d r a m 中合并数据只寸，发生了电源故 障或其它事故，那么将丢失整个数据集合，因为在将数据读入d r a m 后就擦除了闪存扇区。j f f s 2 附加文件而不是重写整个扇区，并且具 有崩溃掉电安全保护这一功能。 3 j f f s 2 是专门为象闪存芯片那样的嵌入式设备创建的，所以 它的整个设计提供了更好的闪存管理。 j f f s 结合闪存的特殊属性，对标准的日志文件系统结构进行了 简化，它保证当系统非正常关闭时操作的可靠性，是闪存设备上保存 经常修改数据的文件系统的理想选择。 改进的j f f s 2 的组织更加复杂，有别于简单的循环日志格式，从 而避免了严格按顺序清除机制带来的过多的不必要的擦除【17 1 。在改进 的j f f s 中，每个擦除块都被单独处理。这意味着清除机制在一个块 执行之后，可以作出智能决策，选择执行的下一个块，从而提高了效 率。每个擦除块都处在一定的状态。它的状态首先取决于它的内容。 改进的j f f s 保存一定数量的链表( 1 i n k e dl i s t ) 。链表的每个结构代 表一个单独的擦除块。在j f f s 文件系统正常运行时，大多数的擦除 块会在c l e a nl i s t 或者d i r t yl i s t 中出现，他们分别代表了存满有效节 点的块和至少包含一个被抛弃节点的块。在一个新的文件系统中，多 数的擦除块在f r e el i s t 上，这些擦除块只包含一个有效节点，作为该 擦除块被完全并且正确擦除的标志。 虽然不断有新的补丁程序来提高j f f s 2 的性能，但是不可扩展 性是它最大的问题，但是这是它自身设计的先天缺陷，是没有办法靠 后天来弥补的。因此我们需要一个全新的文件系统，而j f f s 3 就是 这样的一个文件系统，j f f s 3 的设计目标是支持大容量闪存( i t b ) 的文件系统。j f f s 3 与j f f s 2 在设计上根本的区别在于，j f f s 3 将 索引信息存放在闪存上，而j f f s 2 将索引信息保存在内存中。比如 说，由给定的文件内的偏移定位到存储介质上的物理偏移地址所需的 基于c a r 构譬强冬歉入式文件系统k t f s 舱研究 信息，查找某个冒录下所有的目录项所需的信息都是索引信息的一 种。j f f s 3 现在还处于设计阶段，文件系统的基本结构借鉴了r e i s e r 4 的设计思想，整个文件系统就是一个b + 树【1 8 1 。 1 4 本文主要研究内容及组织结构 1 4 王课题的来源和选题依据 本课题来源于上海科泰世纪科技有限公司的国家8 6 3 项目“基于 中闻件技术的因特网嵌入式操作系统及跨操作系统中闻件运行平 台，该项目的目标足建立一套基予中间件组件技术的嵌入式操作系 统及组件运行平台。 文件系统在传统的嵌入式系统应用中不是必要的部分，主要是因 为目前嵌入式系统涉及到的大多是要求效率的小型应用( 如信息家 电、终端设备等) ，对数据的存储和处理没有过高的要求，在这种情 况下加入文件系统提供的功能显得没有必要。但是作为完整的、面向 i n t e r n e t 的嵌入式系统，不但应有成熟的应用，还应该提供给用户不 同层次的解决方案，可按用户需要定制的系统模块以及可进行二次开 发的开发环境，这些对文件系统都有较高的要求。同时，随着硬件设 备价格的不断降低，嵌入式系统也能拥有丰富的资源，势必对完整的、 高性能的嵌入式操作系统提出新的要求，像普通的桌面操作系统一 样，需具备强大的文件处理能力。 嵌入式设备一般具有体积小、可移动的特点，这些特性决定了其 存储设备的特殊性：容量合适，体积小，抗机械震动等。传统的磁盘 设备显然是不合适的，而f l a s h 存储设备集成在很小的芯片上，具有 体积小、功耗低、存取速度块、抗震动等优点，且能够提供1 m 至 1 g 或者更大的存储容量，所以f l a s h 存储设备是嵌入式系统的存储设 备的一个十分理想的选择。 硕十学位论文 目前，嵌入式文件系统研究还处在不是很成熟的阶段，很多文件 系统都是从微机文件系统移植过来的 1 鲥，不可避免的带来一些不适合 嵌入式系统的弊端。因此，各公司和科研机构都研发自己的文件系统， 如三星公司就专门针对其生产的f l a s h 设备开发文件系统。可以说， 现在还没有得到广泛认可并使用的嵌入式文件系统。因此，开发嵌入 式文件系统充满了机遇与挑战。 本文研究的k t f s 文件系统是一种基于e l a s t o s 嵌入式操作系统的 构件定义标准的，可以在多种存储设备上存储并访问数据的文件系统 2 0 1 。该设计基于以下目标：一是采用通用逻辑文件系统标准；二是为 方便移植到其它系统中，k t f s 尽量与e l a s t o s 保持松耦合关系；三是 将存储设备抽象为一个i d r i v e r 接团。 王a 2 论文的主要内容和组织结构 本文根据其内容分为六章： 第一章引言简要介绍了e l a s t o s 嵌入式操作系统；并对其研究的 内容进行了总体的概括。 第二章主要是对k t f s 文件系统相关的理论知识的探讨，即 c a r ，f a t 存储结构，f l a s h 存储器相关知识；并分析了构件实现文 件系统的可行性和可能性及需要解决的关键闻题。 第三章是全文的中心环节。首先依据k t f s 接口设计原则，在 e l a s t o s 2 1 操作系统上设计并实现了k t f s 对外接口；其次详细分析了 文件系统中高速缓存块替换算法l r u 效率不高的问题，提出并实现 了采用h a s h 表与l r u 链表相结合的办法来解决l r u 算法的效率问 题。 第四章着重展示了k t f s 在硬盘和f l a s h 存储器上的测试结果。 最后一章进行了工作总结及提出了后续改进方向。 基于c a r 构什的嵌入式文件系统k t f s 的研究 2 k - i f s 文件系统理论基础 在嵌入式应用领域，f l a s h 存储器的特点使其在数据存储领域得 到比较广泛的应用：构件化编程特别是中间件的兴起，已逐步取代传 统编程模式，成为网络时代编程的重要技术。考虑到本文件系统会和 桌面系统频繁交互，因此k t f s 采用了m i c r o s o f t 公司提出的汀( f i l e a l l o c a t i o nt a b l e ) 存储结构，以c a r 构件实现的嵌入式文件系统， 并针对f l a s h 存储器实现相关驱动。本章在探讨k t f s 涉及到的相关 理论知识基础上，论证了用构件实现文件系统的可能性和可行性，同 时指出了构件化文件系统要解决的关键问题。 2 1c a r 相关技术 c a r ( c o m p o n e n ta s s e m b l yr u n t i m e ) 构件技术是面向构件的编 程模型，它规定了一组构件间相互调用的标准，使得二进制构件能够 自描述，能够在运行时动态加载【2 。c a r 的编程思想是e l a s t o s 技术 的精髓，它贯穿于整个技术体系的实现中。 2 1 1c a r 技术产生的背景 8 0 年代以来，目标指向型软件编程技术有了很大的发展，为大 规模的软件协同开发以及软件标准化、软件共享、软件运行安全机制 等提供了理论基础。其发展可大致分为以下几个阶段。 1 面向对象编程 通过对软件模块的封装，使其相对独立，从而使复杂的问题简单 化。面向对象编程强调的是对象的封装，但模块( 对象) 之间的关系 在编译的时候被固定，模块之间的关系是静态的，在程序运行时不可 改变模块之间的关系【2 2 1 ，就是说在运行时不能换用零件。其代表是 硕士学何论文 c + + 语言所代表的面向对象编程。 图2 1 面向对象的编程模型 2 面向构件编程 为了解决不同软件开发商提供的构件模块能相互操作使用的闻 题，构件之间的连接和调用要使用标准的协议。构件化编程模型强调 协议标准，需要提供各厂商都能遵守的协议体系。就像公制螺丝的标 准一样，所有符合标准的螺丝和螺母都可以相互装配。构件化编程模 型建立在殛向对象技术的基础之上，是完全面向对象的，提供了动态 构造部件模块( 运行中可以构造部件) 的机制。构件在运行时动态装 入，是可换的。其代表是c o m 技术。 圈2 。2 蘧向构件的编程模型 3 面向中间件编程 由于因特网的普及，构件可来自于网络，系统要解决自动下载， 安全等问题。因此，系统中需要根据构件的自描述信息自动生成构件 的运行环境，生成代理构件即中间件，通过系统自动生成的中间件对 构件的运行状态进行干预或控制，或自动提供针对不同网络协议、输 入输出设备的服务( 即运行环境) 。中间件编程更加强调构件的自描 述和构件运行环境的透明性，是网络时代编程的重要技术【2 3 】。其代表 是c a r 、j 趟厂a 和n e t ( c 舞语言) 。 1 4 基于c a r 构件的嵌入式文件系统k t f s 的研究 缫 ，7 二：o 拣理构 牛 、i 零件j 、： 图2 3 两向中阅件的编程模型 在这样的发展过程中，人们逐步深化了对大规模软件开发所需的 科学模型、网络环境下软件运行必要机制的理解，使软件技术达到了 更高的境界。c a r 技术技术就是在总结面向对象编程、面向构件编 程技术的发展历史和经验，为更好地支持面向以w e bs e r v i c e 为代表 的下一代网络应用软件开发而发明的。 2 1 2c a r 构件技术及对软件工程的作用 c a r 构件技术是面向构件编程的编程模型，它规定了一组构件 闻相互调用的标准，使得二进制构件能够自描述，能够在运行时动态 链接。c a r 兼容微软的c o m ，但是和微软c o m 相比，删除了c o m 中过时的约定，禁止用户定义c o m 的非自描述接口；完备了构件及 其接口的自描述功能，实现了对c o m 的扩展。 为了在资源有限的嵌入式系统中实现面向中间件编程技术，同时 又能得到c c + + 的运行效率，c a r 没有使用j a 、，a 和n e t 的基于中 间代码一虚拟机的机制，而是采用了用c + + 编程，用和欣s d k 提供 的工具直接生成运行于和欣构件运行平台的二进制代码的机制。用 c + + 编程实现构件技术，使得更多的程序员能够充分运用自己熟悉的 编程语言知识和开发经验，很容易掌握面向构件、中间件编程的技术。 在不同操作系统上实现的和欣构件运行平台，使得c a r 构件的二进 制代码可以实现跨操作系统平台兼容。 对于面向w e b 服务的应用软件开发，以及开发操作系统这样的 大型系统软件而言，采用c a r 构件技术具有以下的意义： 硕十学f 7 ：论文 不同软件开发商开发的具有独特功能的构件，可以确保与其 他人开发的构件实现互操作。 提供一个简单、统一的编程模型，使得构件可以在进程内、 跨进程甚至于跨网络运行。同时提供系统运行的安全、保护 机制。 c a r 构件与微软的c o m 构件二迸制兼容，但是c a r 的开发 工具自动实现构件的封装，简化了构件编程的复杂性，有利 于构件化编程技术的推广普及。 软件工厂化生产需要有零件的标准，c a r 构件技术为建立软 件标准提供了参考，有利于建立企业、行业的软件标准和构 件库。 大型软件的生产，已经不是传统的手工作坊式的开发所能够胜任 的。软件工厂化生产，是软件工程研究几十年来追求的理想，为实现 这样的圈标，需要有一个科学的编程模型。开发的软件可以是由一个 公司的不同部门提供，也可以是不同企业，不同地点、不同时间生产 的。汲取了c o m 技术的精华，并对其进行了扩展和简易包装的c a r 技术，将成为软件工厂化生产的利器。 2 2f a t 存储结构理论 f a t 存储结构是由m i c r o s o f t 提出并应用在m s d o s 操作系统中， 而后在w i n d o w s 操作系统中也使用了它。早期的f a t 文件系统采用1 2 位或1 6 位的文件分配表( 也称为f a t l 2 、f a t l 6 文件系统) ，主要使用 于d o s 、w i n d o w s 3 x 9 5 中。由于其在硬盘分区太大时所分配的簇的 容量不科学，只能管理2 g b 以下的硬盘。在w i n d o w s9 8 中除可以采用 f a t l 6 文件系统外，新增了对f a t l 6 文件系统的增强版本f a t 3 2 文件 系统的支持，它采用3 2 位的文件分配表，能有效地管理2 g b 以上的硬 盘，最多可以支持2 t b 的磁盘容量。 基于c a r 搦钟的嵌入式文件系统麟的研究 副汀文件系统主要依靠w 汀文件分配表( f i l ea l l o c a t i o nt a b l e ) 来 实现对文件的检索，是文件管理系统用来给每个文件分配磁盘物理空 间的表格，它告诉操作系统，文件存放在磁盘的什么地方，文件分配 表是实现磁盘分配和管理的最关键设计渊。文件分配表存放在每个磁 盘的开始的部分，是一张采用链接定位技术的链表。在表2 1 中，莱 文件的起始存储块号为2 ，从第2 号单元开始，顺着链指针可以找出存 储该文件的存储块分别为2 ，5 ，3 ，6 。第6 个单元的内容为0 x f f ，表 明它所代表的存储块是存放该文件的最后一块。f a t 存储结构就是按 照这种方法来进行存储块的分配和管理。 012 3 456 oo5603o x f f 表2 1 文件分配表 在f a t 存储结构巾采用树形多级目录结构，在多级目录下，一个 文件属于哪个圈录是该文件的属性之一，因此目录表区需要有一项 来进行描述。但是如果把所有的文件信息都集中在一张目录表来表 示，随着文件个数的增加，这张表会变得很大而不易维护，比如当你 想统计一个目录下总共有哪些文件时，就必须遍历整张国录表进行蠢 找，这显然时不合理的。f a t 存储结构提供的解决办法是诖每个墨录 都有自已的张文件目录表，该目录下的每个直属下级文件或子目录 在该表中都占一行，称为一个目录项。f a t 存储结构包含4 个基本区 域，它们分别是：保留区域，f a t 表区域，根冒录区域，数据存储区 域。其结构如表2 。2 ： 保馨区域 按实际情况取大小第2 簇 胡i 足l 簇 圈 f a t 表及域根基录区域数据区 表2 2f a t 存储结构 硕十学位论文 2 2 1 雕汀表结构 f a t 存储结构用一个表格结构来描述存储设备上各个存储单元 的状态，并把这个表格保存在物理设备的指定位置上，这个表格就叫 做文件分配表。表格中的每一个单元对应一个物理存储单元，单元中 的内容代表了对应物理存储单元的状态。对于空闲存储块，文件分配 表中相应单元内容为o ；对于那些保存了数据信息的存储块来说，它 在文件分配表中同时也指出了下一文件的存储块号，如果某存储单元 没有了后续单元，则此单元的内容为一个结束标志。这样，这个文件 的所有存储块可以链接在一起。 按照这种方法管理存储空间时，要考虑存储块大小的划分。如果 存储介质是磁盘，容量为4 g b ，磁盘块的大小为1 k b ，文件分配表每 一个单元占用4 字节的话，则磁盘的文件分配表将占用1 6 m b ，如果存 储介质采用3 2 m b 的n a n df l a s h ，存储块单元按照5 1 2 b 大小的簇来划 分，那么会有6 5 5 3 6 个单元，采用f a t l 6 存储结构的话，每个f a t 单 元将占用2 个字节，f a t 表的大小为6 5 5 3 6 * 2 1 0 2 4 = 1 2 8 k b 。 2 2 2f a t 目录结构 在黝汀存储结构中，冒录中存储的是一系y l j 3 2 个字节大小的目录 项。不过根目录就比较特殊了，在f a t l 2 和f a t l 6 中根目录是位于f a t 表后的固定位置的并且占固定数目的扇区，它的大小由b p b ( b o i s p a r a m e t e rb l o c k ) 结构中的b p br o o t e n t c n t 域指定；f a t 3 2 存储结构 中，根圈录的第一个簇是由b p b 结构中的b p br o o t c l u s 来指定的。 8 3 命名规范对用户使用文件带来了极大的不便，为了解决这个 问题，长文件名方案被提出；在长文件名环境下，一个文件将拥有一 份长文件名目录项和一份短文件名隧录项。长文件名西录项的存在是 为了以长文件名方式操作文件，短文件名数据是为了在使用低版本的 鏊于c a r 构件的嵌入式文件系统k t f s 靛磷究 文件系统时的需要而设立，器i 达到对 露版本文件系统的兼容性。短文