第十二章 文件系统实现

CHAPTER12:文件系统实现文件系统结构文件系统实现目录实现分配算法空闲分区管理效率和性能恢复基于日志结构的文件系统文件系统结构磁盘提供大量的外存空间来维持文件系统可写数据在磁盘上可顺序和随机访问I/O转移以块为单位文件系统在磁盘上方便的存储、定位、检索数据定义文件系统和用户接口创建数据结构和算法将逻辑文件系统映射到物理外存设备上文件系统结构:分层结构文件系统结构:文件系统实例Windows:FAT(FileAllocationTable)(12,16,32)NTFS(WindowsNTFileSystem)UNIX:UFS(UnixFilesystem)ext2ext3文件系统实现文件系统中数据结构的实现在磁盘上的数据结构在内存中的数据结构分区和挂载虚拟文件系统VFS文件系统实现磁盘上的结构引导控制块(引导扇区)用于引导操作系统的分区分区控制块块数量、块大小、空闲块计数文件目录结构线性表/hash表FCB文件系统实现内存中的结构内存分区表：包括每个挂载分区的信息内存目录结构：包括最近访问过的目录信息系统打开文件表：包括当前每个打开文件的FCB的备份和其他信息进程打开文件表：包括指向系统打开文件表中适当条目，及其他信息文件系统实现创建新文件应用程序调用逻辑文件系统逻辑文件系统分配一个新的FCB读入一个适当的目录–UNIX处理目录如同一个文件–WindowsNT处理目录如同在主控文件表中插入一条记录.增加一个新条目在条目中填入文件名和新的FCB写入磁盘文件系统实现打开文件传送文件名到逻辑文件系统在目录在搜索给定文件名读入该文件的FCB将FCB添加到系统打开文件表中在进程打开文件表中增加一条目，在条目中填入指向系统打开文件表的指针及其他信息返回进程打开文件表中的相关指针(文件描述符；文件句柄）文件系统实现关闭文件删除进程打开文件表中的相关条目系统打开文件表对应条目的打开记数减1如果打开记数为0,基于目录结构，将修改后的文件信息拷贝到磁盘上，后删除该条目文件系统实现文件系统实现:分区和挂载分区vs磁盘一个磁盘可以分成多个分区一个分区可以包含多个磁盘每个分区可装入一个文件系统“raw”或“cooked”生盘分区:没有文件系统交换空间,数据库熟盘分区：装有文件系统引导区引导操作系统（双引导）超级块（UNIX）文件系统实现:VFS如何支持多个文件系统？如何将多个文件系统整合到一个目录结构?如何在多个文件系统间无缝移动的访问?TouseVFS(VFS应用面向对象技术来简化、组织和模块化实现过程)文件系统实现:VFS最高层:文件系统接口Open,read,write,andclose中间层:VFS能过一个清晰的VFS接口，将文件系统的通用操作和具体实现分开VFS是基于称作vnode的文件表示结构,该结构包括一个数值——指定整个网络范围内的惟一文件最低层各种文件系统实现Ext3NFS文件系统实现:VFS目录实现：线性表以线性表的方式组织目录项查找文件线性搜索创建文件搜索目录，确认没有同名文件存在在目录尾增加一目录项删除文件搜索目录，查找文件删除目录项释放分配给该文件的空间实现简单，搜索花费时间长二分搜索法要存储目录排序目录实现：Hash表用线性表来存储目录，用hash表在目录中快速查找给定文件名不允许冲突(每个hash条目有一个唯一的值)用hash函数将文件名映射到一个值Hash函数需动态调整速度最快允许冲突(每个hash条目由多个值构成一个列表)用hash函数将文件名映射到一个值，然后用这个值在hash表中索引，找到列表中的目录项速度比较快分配方法如何将磁盘空间分配给文件连续分配链接分配索引分配文件的物理组织分配方法:连续分配连续分配方法要求给文件分配一给连续的磁盘块目录中记录文件的起始地址（块号）和长度（块数量）分配方法:连续分配讨论:支持顺序访问和随机访问.实现简单有外碎片(类似动态内存分配)创建新文件时如何确定其大小小于估计值大于估计值扩展的连续空间文件目录中除了起始地址、长度外，还要加上指向下一扩展的指针连续分配方法可结合其他方法一起使用小文件采用连续分配方法大文件采用其他方法分配方法:链接分配采用链接分配方法每个文件是一个磁盘块的链表链表中的磁盘块可以在磁盘上任何位置目录中包含指向第一块的指针和最后一块的指针pointerBlock=分配方法:链接分配简单–只需要一个起始地址有效利用空闲空间不可随机访问指针浪费空间:盘块用簇（clusters）而不是用扇区（sectors）提高空间利用率加速访问（更少移动磁头）可靠性差指针出错MSDOS和OS/2系统采用的文件分配表（FAT）是一种变种的链接分配方法分配方法:链接分配FAT(FileAllocationTable)两个镜像，互为备份。文件卷中的每个簇均对应一个FAT表项文件分配采用链式分配方法支持随机访问FAT1FAT2RootDirectoryData(File&Directory)BootRecordVolumeStructureinMSDOSSector#0N12N分配方法:链接分配每个FAT表项所占位数是簇编号的位数，其值是（以FAT12为例）：0：表示该簇空闲FF7h：物理坏扇区FF8h~FFFh：表示该簇是文件的最后一个簇其他值：表示该簇被文件占用，而且表项中的值是文件下一个簇的编号。分配方法:索引分配问题:连续分配中有外部碎片及估计文件大小的问题链接分配不能直接存取索引分配将一个文件的所有磁盘块的指针集中放在一个块中（索引表），目录中指出索引表的地址索引表的逻辑视图indextable分配方法:索引分配分配方法:索引分配需要索引块可顺序访问和随机访问索引块要占用空间比较小的文件也需要一个索引块（浪费空间）文件较大时索引要占用多个块链接方案多层索引组合方案分配方法:索引分配链接方案索引块的最后一项指向下一个索引块多层索引1-levelindexblock:1024*4KB2-levelindexblock:1024x1024*4KB3-levelindexblock:1024x1024*1024*4KB(类似内存分页管理)分配方法:索引分配outer-indexindextablefile分配方法:索引分配组合方案（用于UFS）12个直接指针1个一级间接指针1个二级间接指针1个三级间接指针分配方法:索引分配空闲空间管理位向量（位示图）链表组计数空闲空间管理:位向量Anexample01234567891011121314150011110011111100讨论:实现简单方便查找连续空闲块方便查找第一个空闲块块号的计算（每次从位向量中读一个字）位向量需要额外的空间。如:blocksize=212bytesdisksize=230bytes(1gigabyte)n=230/212=218bits(or32Kbytes)空闲空间管理:链表空闲块链表不浪费空间不方便获得一个连续空间空闲空间管理:其他方法组对空闲链表的一个改进可以很快找到大量连续的空闲块计数对于连续的空闲分区，只需记录第一块地址和其后连续空闲块的数量效率与性能效率性能增加磁盘Cache预先读取恢复一致性检查备份和恢复备份计划Day1:完全备份Day2,3,4,…n:增量备份备份保存在不同的地方基于日志结构的文件系统一个文件操作可能被中断，则导致不一致性，恢复困难所有元数据都按顺序写到日志上事务（DBMS）执行一个特殊任务的一组操作日志记录文件系统中将文件系统的每次更新都看作是一个事务所有事务都写入一个日志，一个事务写入日志后就已经提交当一个完整提交事务已完成，那么就可从日志文件中删除LogStructuredFileSystemHomework12.112.412.512.6