搜索
第6章文件系统实现（补充）21文件系统结构操作系统通过文件系统来存储、定位、提取数据，文件系统存在于辅助存储器中—磁盘文件系统设计的两个问题如何定义对用户的接口。如定义文件及其属性、文件所允许的操作、组织文件的目录结构创建数据结构和算法来将逻辑文件系统映射到物理外存设备上文件系统按层组织文件控制块FCB：由一个文件的相关信息组成的存储结构，如拥有者、许可、文件内容的位置3分层设计的文件系统设备驱动程序,中断处理程序，实现内存与磁盘之间的信息转移向设备驱动程序发送命令以对磁盘上的物理块进行读写逻辑地址=物理地址管理元数据(目录结构,FCB)4二、文件系统的类型FAT文件系统（MS-DOS文件系统、msdos）它是MS-DOS操作系统使用的文件系统，它也能由Windows98/NT、linux、SCOUNIX等操作系统访问。文件地址以FAT表结构存放，文件目录32B，文件名为8个基本名加上一个“.”和3个字符扩展名。FAT32文件系统（vfat）它是Windows98使用的扩展的DOS文件系统，它在MS-DOS文件系统基础上增加了对长文件名（最多到256B）支持。NTFS（NT文件系统）它是WindowsNT操作系统使用的文件系统，它具有很强的安全特性和文件系统恢复功能，可以处理巨大的存储媒体，支持多种文件系统。S51K/S52K（sysv）它是AT&TUNIXSV操作系统使用的1KB/2KB文件系统。5文件系统的类型ext2（二级扩展文件系统）它是Linux操作系统使用的高性能磁盘文件系统，它是对Minux操作系统中使用的文件系统扩展（ext）的扩展。它支持256字符的文件名，最大可支持到4TB的文件系统大小。HPFS（高性能文件系统、hpfs）它是OS/2操作系统使用的文件系统。CD-ROM文件系统(iso9660)它是符合ISO9660标准的支持CD-ROM的文件系统，它有HighsierraCD-ROM和RockRidgeCD-ROM二种类型。UDF通用磁盘格式文件系统UDF(UniversalDiskFormat)文件系统是依据光学储存技术协会（OpticalStorageTechnologyAssociation,OSTA）的通用磁盘格式文件系统规格1.02版所制定的。它提供了对UDF格式媒体的只读访问（例如DVD光盘）。Windows98提供对UDF文件系统支持。6三、操作系统(Windows98/NT、Linux)对多种文件系统的支持WindowsNT多重文件系统WindowsNT支持FAT文件系统、NTFS、HPFS、CD-ROM文件系统等多种文件系统。WindowsNT执行体内I/O系统分成I/O管理程序、文件系统驱动程序和磁盘驱动程序三层，不同的文件系统采用不同的文件系统驱动程序，系统用动态连接库对这些文件系统进行装入和卸出并适宜于将来的扩展，WindowsNT分层驱动程序如下图所示。WindowsNT磁盘管理器窗口显示某台微机硬盘各分区安装的多种文件系统如下图所示，图中所示硬盘有二个分区，C盘是FAT文件系统，D盘是NTFS文件系统，E盘是CD-ROM文件系统。7WindowsNT多重文件系统-1WindowsNT分层驱动程序I/O管理程序FAT驱动程序NTFS驱动程序HPFS驱动程序软盘驱动程序硬盘驱动程序8WindowsNT多重文件系统-29Linux虚拟文件系统VFSLinux采用虚拟文件系统VFS支持许多不同类型的文件系统，VFS是物理系统与服务之间的一个接口层，它屏蔽各类文件系统的差异，给用户和程序提供一个统一的接口。Linux支持ext、ext2、msdos、vfat、iso9660、hpfs等多种文件系统。使用命令mkfs创建各类文件系统。VFS是物理文件系统与服务之间的一个接口，它对Linux的每一个文件系统的所有细节进行抽象，使得不同的文件系统在Linux内核以及系统中运行的其它进程看来都是相同的，严格说来VFS并不是一种实际的文件系统，它只存在于内存中，不存在于任何外存空间，VFS在系统启动时建立，在系统关闭时消亡。VSF使Linux同时安装支持不同类型的文件系统成为可能。102文件系统实现磁盘结构如何启动所存储的操作系统、总的块数、空闲块的数目和位置、目录结构以及各个具体文件等。内存结构用于文件系统管理和通过缓存来提高性能11磁盘结构引导控制块,包括系统从该分区引导操作系统所需要的信息引导块（UFS）,分区引导扇区（NTFS）分区控制块包括分区详细信息(如块数,块的大小，空闲块的数量和指针，空闲FCB的数量和指针等)超级块（UFS）,主控文件表（NTFS）目录结构：用来组织文件FCB结构索引结点（UFS）12一个典型的FCB13内存结构内存分区表：包含所有安装分区的信息内存目录结构：用来保存近来访问过的目录信息系统范围的打开文件表,包括每个打开文件的FCB拷贝打开数单个进程的打开文件表,包括指向系统范围打开文件表的指针读写位置14open系统调用调用open将文件名传给文件系统，当打开文件时，根据给定文件名来搜索目录结构一旦找到文件，其FCB就复制到系统范围的打开文件表在单个进程的打开文件表中会增加一个条目调用open返回一个指向单个进程的打开文件表中合适条目的指针文件描述符（UNIX）,文件句柄（Windows）15close系统调用关闭文件时，删除一个相应的单个进程打开文件表的条目系统范围内打开文件表的打开数也会递减当打开数为0时，更新的文件信息会复制到磁盘的目录结构中，系统范围的打开文件表的条目也将删除16内存中的文件系统结构a打开文件b读文件17分区与安装一个磁盘可以分成多个分区引导信息包括如何启动一个特定操作系统可以装多个操作系统双启动引导装入程序,位于引导区,可理解多个文件系统和多个操作系统•bootmanagerinOS/2•GRUB,LILOinLinux18安装根分区：包括操作系统内核或其它系统文件，在引导时装入内存。其它分区根据不同操作系统可以在引导时自动装入或在此之后手动装入装入表：注明文件系统已装入和该文件系统的类型。Windows系统将分区装入在独立名称空间中，名称用字母和冒号表示逻辑磁盘(e.g.“F:”)Linux可以将文件系统装在任何目录上。19虚拟文件系统虚拟文件系统（VFS)提供一个面向对象的文件系统实现方法，以允许不同文件系统类型可以通过同样结构来实现VFS允许不同类型的文件系统使用相同的系统调用接口API作为VFS接口要好于规定的文件系统类型20VFS示意图第一层文件系统接口，包括open，read，write和close调用及文件描述符第二层VFS层，目的：1将文件系统通用操作和具体实现分开2VFS是基于称为vnode的文件表示结构，该结构包括一个数值指定者以表示位于整个网络范围内的唯一文件。因此，VFS区分本地文件和远程文件213目录实现为了实现用户对文件的按名存取，系统必须首先利用用户提供的文件名，对文件目录进行查询，找出该文件的文件控制块FCB，然后根据找到的FCB中所记录的文件物理地址，并根据文件物理组织方式找出文件的盘块号，进而换算出文件在磁盘上的物理位置（柱面号、磁头号、扇区号），最后启动磁盘驱动程序，将所需文件读入内存。对目录查询的技术有两种：线性检索法和Hash法。22目录实现线性列表—包括存储文件名、指向数据块的指针采用线性搜索来查找特定条目，容易编程耗CPU的执行时间许多操作系统采用软件缓存来存储最近访问过的目录信息，缓存命中避免不断地从磁盘读取信息哈希表—有着哈希数据结构的线性表减少目录的搜索时间冲突：两个名字映射到同样的位置固定大小和哈希函数对大小的依赖性234分配方法分配方法指出如何为文件分配磁盘块常用的方法有：连续分配链接分配索引分配24磁盘空间的连续分配25一、连续分配每一个文件占用一个连续的磁盘块的集合简单：只需要起始块号和长度支持顺序访问和直接访问为新文件找到空间，动态存储分配问题首次适应和最佳适应外部碎片文件不能扩展文件需要多少空间比较难估计26许多新的文件系统使用一种修正的连续分配方法首先分配一块连续空间，当空间不够时，另一块被称为扩展的连续空间会添加到原来的分配中。文件块的位置就成为开始地址、块数、加上一个指向下一扩展的指针扩展太大内部碎片不同大小的扩展的分配和删除外部碎片27二、链接分配每个文件是磁盘块的链表：磁盘块可以分散在磁盘的任何地方目录包括文件第一块的指针和最后一块的指针pointerblock=28链接分配简单：只需要起始地址优点没有外部碎片，没有磁盘空间浪费，无需合并磁盘空间缺点无法随机存取，只能有效的用于文件的顺序访问指针需要空间•将多个块组成簇，并按簇分配。增加了内部碎片指针分布在整个磁盘上，可能失去或损坏29链接分配文件分配表(FAT)是链接分配方法的一个变种FAT–用于MS-DOSandOS/2操作系统每个分区的开始部分用于存储该FAT表。每块都在该表中有一项，该表可通过块号码来索引。FAT的使用与链表类似FAT可能导致大量的磁头寻道时间通常对FAT采用缓存(在内存中)改善了随机访问时间通过读入FAT信息，磁头能找到任何块的位置30文件分配表31三、索引分配将所有指针放在索引块中逻辑形式索引表块32索引分配指针目录条目包括索引块的地址支持随机访问，且没有外部碎片问题浪费空间:必须分配一个完整的索引块索引块应为多大？太大会浪费空间，太小不能为大文件存储足够多的指针链接方案•为了处理大文件，可以将多个索引块链接起来。多层索引•用第一层索引块指向一组第二层的索引块，第二层索引块再指向文件块组合方案•用于UFS，将索引块的前15个指针存在文件的inode中。前12个指针指向直接块，其它3个指针指向间接块33多层索引outer-indexindextablefiledirectory34组合方案:UNIXinode(4Kbytesperblock)35性能性能依据存储效率数据块访问时间考虑因素大部分是顺序访问还是随机访问?文件大小固定还是可变?filesizevarytoagreatdegree?（文件大小不一）由于CPU和磁盘速度的不等，就是花费操作系统数千条指令以节省一些磁头移动都是值得的36顺序访问直接访问不同文件大小空间利用连续goodgoodbad外部碎片链接goodbadgood索引???somewaste索引分配的性能依赖于索引结构文件大小所需块的位置375空闲空间管理空闲空间链表记录了所有空闲磁盘空间，将删除文件的空间用于新文件不同的实现方法位向量链表组计数385.1位向量空闲空间表实现为位图,或位向量n块，每块用一位表示…012n-1bit[k]=1block[k]空闲0block[k]已分配395.2链表空闲空间链表很难获得连续空间没有空间浪费FAT有助于提高性能405.3组对空闲链表的一个改进是将n个空闲块的地址存在第一个空闲块中。这些块中的前n－1个为空。而最后一块包含另外n个空闲块的地址415.4计数通常有多个连续块需要同时分配或释放，尤其是在使用连续分配和采用簇时更是如此可以记录第一块的地址和紧跟第一块的连续的空闲块的数量n。空闲空间表的每个条目包括磁盘地址和数量。426效率和性能效率取决于磁盘分配和目录管理算法保留在文件目录条目中的数据类型性能磁盘缓存–一块独立内存，位于其中的块假设马上需要使用页缓存,将文件数据作为页而不是块来缓存.也称为统一虚拟内存43页缓存页缓存使用虚拟内存技术，将文件数据作为页来缓存，比采用物理磁盘块来缓存更高效内存映像I/O使用页缓冲子程序I/O通过文件系统使用磁盘缓冲区这种结果如下图所示.44无统一缓冲缓存的I/O双缓存问题45I/OWithoutaUnifiedBufferCache46统一缓冲缓存统一缓冲缓存使用相同页缓存去缓