文件系统实现PPT课件

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