CHAPTER12:文件系统实现文件系统结构文件系统实现目录实现分配算法空闲分区管理效率和性能恢复基于日志结构的文件系统文件系统结构磁盘提供大量的外存空间来维持文件系统可写数据在磁盘上可顺序和随机访问I/O转移以块为单位文件系统在磁盘上方便的存储、定位、检索数据定义文件系统和用户接口创建数据结构和算法将逻辑文件系统映射到物理外存设备上文件系统结构:分层结构文件系统结构:文件系统实例Windows:FAT(FileAllocationTable)(12,16,32)NTFS(WindowsNTFileSystem)UNIX:UFS(UnixFilesystem)ext2ext3文件系统实现文件系统中数据结构的实现在磁盘上的数据结构在内存中的数据结构分区和挂载虚拟文件系统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的文件表示结构,该结构包括一个数值——指定整个网络范围内的惟一文件最低层各种文件系统实现Ext3NFS文件系统实现: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*4KB2-levelindexblock:1024x1024*4KB3-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)执行一个特殊任务的一组操作日志记录文件系统中将文件系统的每次更新都看作是一个事务所有事务都写入一个日志,一个事务写入日志后就已经提交当一个完整提交事务已完成,那么就可从日志文件中删除LogStructuredFileSystemHomework12.112.412.512.6