操作系统课件：第11章 文件系统实现

Chapter11:文件系统实现文件系统结构文件系统实现目录实现分配方法空闲空间管理效率与性能恢复基于日志结构的文件系统网络文件系统文件系统结构文件结构逻辑存储单元相关信息的集合文件系统驻留在二级存储器（磁盘）上。文件系统按层组织。文件控制块(FCB)

－包含了文件的信息。分层设计的文件系统一个典型的文件控制块内存中文件系统结构下图显示了在操作系统中看到的文件系统结构。图11-3(a)显示了打开一个文件。图11-3(b)显示了读文件。内存中文件系统结构虚拟文件系统虚拟文件系统(VFS)提供了一种面向对象的方法来实现文件系统。VFS为不同类型的文件系统提供了统一的系统调用接口(API)。API是VFS的接口，而不属于某个特定类型的文件系统。虚拟文件系统示意图目录实现线性列表，存储文件名和数据块指针。编程简单运行费时

哈希表－使用线性列表存储哈希数据结构。降低目录搜索时间冲突－两个文件名哈希到相同的位置固定的大小分配方法一种分配方法指的是如何为文件分配磁盘块：连续分配链接分配索引分配连续分配每个文件在磁盘上占用一组连续的块。

简单－仅需要起始块号和长度。支持随机访问。浪费空间（动态存储分配的问题）。

文件不能增长。磁盘空间的连续分配基于扩展(extent)的系统有些新的文件系统(I.e.VeritasFileSystem)采用了改进的连续分配方案。基于扩展的文件系统在某个范围内分配磁盘块。一个扩展是一组连续的磁盘块。扩展在文件分配时被分配。一个文件可能包含一个或多个范围。链接分配每个文件是一个磁盘块的链表；磁盘块分布在磁盘的任何位置。pointerblock=链接分配（续）简单－仅需要起始地址空闲空间管理系统－没有浪费的空间无法实现随机访问映射在用链表块表示的文件中，被访问的块为第Q块替换=R+1文件分配表(FAT)－用于MS-DOS和OS/2系统的磁盘空间分配。LA/511QR链接分配（续）文件分配表索引分配把所有的指针放在一起：索引块。逻辑形式索引表索引分配的例子索引分配（续）需要索引表支持随机访问动态存取没有外碎片，但索引块的负担较重。为了实现文件逻辑地址到物理地址的映射，一个256K的文件，每块大小512字，需要1块作为索引块。LA/512QRQ=索引表中的替换块R=替换块索引分配－映射（续）无限长度文件的映射链接策略－把索引块链接起来（没有长度限制）。LA/(512x511)Q1R1Q1

=索引块R1

isusedasfollows:R1/512Q2R2Q2=displacementintoblockofindextableR2displacementintoblockoffile:索引分配－映射（续）两级索引(最大文件长度为5123)LA/(512x512)Q1R1Q1=displacementintoouter-indexR1isusedasfollows:R1/512Q2R2Q2=displacementintoblockofindextableR2displacementintoblockoffile:索引分配－映射（续）外层索引索引表文件联合策略：UNIX（每块4KB）空闲空间管理位向量（n块）…012n-1bit[i]=0block[i]free1

block[i]occupied块号计算(一个字的位数)*(值为0的字数)+第一个值为1的偏移空闲空间管理（续）位图需要额外的空间。例如 blocksize=212bytes disksize=230bytes(1gigabyte)

n=230/212=218bits(or32Kbytes)比较容易得到连续的文件链表（空闲空间表）得到连续空间难没有浪费的空间组计数空闲空间管理（续）需要保护:指向空闲空间链表的指针位图必须保存在磁盘上内存中的拷贝可能与磁盘上不同。对block[i]不允许有下列情形发生：在内存中bit[i]=1而在磁盘上bit[i]=0。磁盘上的值必须与内存中的值一致。解决方案:在磁盘上设置bit[i]=1分配block[i]在内存中设置bit[i]=1采用链接方式的磁盘空闲空间链表效率与性能效率取决于:磁盘分配和目录管理算法保留在文件目录结构中的数据类型性能磁盘缓存－存在于内存中的独立区域，其中的数据频繁被访问。马上释放-预先读取－优化顺序存取的技术。用于PC上的改善性能的方法：留出一块内存作为虚拟磁盘，或RAM磁盘。不同的磁盘缓存位置页缓存使用虚拟内存技术，将文件数据作为页而不是块来缓存。页缓存实现缓冲缓存和内存映像I/O的交互。缓冲缓存实现文件系统和标准I/O调用的交互。缺少统一缓冲缓存的I/O统一缓冲缓存统一缓冲缓存，内存映射和I/O系统调用都使用同样的页缓存。恢复一致性检查－将目录结构数据与磁盘数据块相比较，试图纠正所发现的不一致利用系统程序将磁盘数据备份到另一存储设备，如软盘、磁带或光盘完全备份增量备份恢复丢失文件或整个磁盘时，只需要从备份中恢复就可以系统还原例子基于日志结构的文件系统以事务的方式记录对系统的每一次更新所有的事务都会被写入到日志中日志中的事务异步的被写入文件系统。当文件系统更新完成后，事务就可从日志中删除。如果文件系统崩溃，所有留在日志中的事务都必须继续执行网络文件系统(NFS)NFS：NetworkFileSystem用于通过LAN（或WAN）访问远程文