OS2013_UNIT9文件系统的实现

Unit9文件系统的实现操作系统原理——冯耀霖文件管理之二内容●文件的物理组织●文件目录的实现●磁盘空间的管理●文件共享●文件的访问控制●文件的注册与挂载●内核的文件管理机制通过上一章的学习，我们对文件和文件系统已有了一些感性认识。但对于操作系统的设计来说，光有感性认识是不够的，需要进一步了解文件系统的实现细节，这些细节问题包括：文件的物理组织文件目录的结构文件的共享磁盘空间的管理文件的访问控制文件系统的注册与挂载内核的文件管理机制§1文件的物理组织◆连续结构◆链接结构◆索引结构一个文件的空间在逻辑上可看成是连续的，即一个文件由若干连续的盘块所组成。但在磁盘上可以有多种方式来组成一个文件，换言之，文件有多种物理的存储结构，常用的是：连续结构、链接结构、索引结构。文件的物理存储结构决定了文件的逻辑地址空间到文件的物理地址空间的映射方法。1.1连续结构又称顺序结构。指一个文件由若干相邻的盘块所组成。称这种结构的文件为连续（顺序）文件。这是一种最简单的文件物理结构，且读写效率很高，因为一次寻道就可完成整个文件的读写。数据库文件就要求是连续结构，所以装数据库的话最好是在一个空的卷上装，如果装在一个已装了很多文件的卷上，就会发现该数据库系统运行很慢。图9-1为文件的连续结构示意图。连续结构的优点是保证了文件的逻辑块的顺序与物理块的顺序相一致，支持随机存取，读写速度快。缺点是：①要求在建立文件时给定文件的最大长度，以便系统分配足够的地址连续的盘块，显然这不利于文件的动态增长；②在频繁的文件创建和删除之后，存在卷空间的外碎片问题，使得卷空间的利用率不高。……首物理块号80………808182830123物理块号：逻辑块号：FCB图9-1文件的连续结构示意图1.2链接结构这是一种非连续结构。一个文件可由若干离散的盘块所组成，但需为每块设置一个链接字，用于指出下一块的块号。称这种结构的文件为链接文件。其优点是：①一个文件不要求占用连续的卷空间，因此消除了外碎片问题，文件卷的利用率较高；②一个文件可以以块为单位动态地增长和删除，易于文件的动态增删。链接结构又分为隐式链接和显式链接两种：(1)隐式链接在文件的FCB中指明该文件的首块号，并在每个盘块内设置一个链接字next。FCB首盘块号8090100110∧盘块80盘块90盘块100盘块110逻辑块0逻辑块1逻辑块2逻辑块3图9-2文件的隐式链接结构这种结构的缺点是：①难于随机访问文件中的信息，为了读写文件中某逻辑块的信息，必须从链头开始，逐一读取每个盘块，以取得下一逻辑块的盘块号；②在每个盘块中都设置了一个链接字，破坏了盘块数据的完整性。(2)显式链接把一个文件系统中所有盘块的链接字集中存放在一个专门设置的“块链接表”中，表目数为该文件系统的盘块总数，表目号对应盘块号，表目内容是该盘块的链接字。显式链接较之隐式链接明显减少了访盘次数，因为对盘块的寻址只需在块链接表上进行，故容易实现对文件的随机存取，但块链接表本身相当大，调入内存后需占较大的内存空间。例如，对于一个2GB的磁盘文件系统，设盘块的大小为2KB，则共有1M块，块号需用长整型数（32位，占4个字节）表示，于是一个盘块可存放256个块号，而块链接表需占4096个盘块，调入内存需占4096个实页面。显式链接结构，也称块链接表结构，是被广泛采用的文件物理结构之一。DOS、Windows2000/XP均支持这种结构，并称块链接表为“文件分配表”（FAT），称采用这种结构的文件系统为FAT文件系统。FAT文件系统又分为FAT12、FAT16、FAT32三种。它们的区别在于用来表示磁盘地址的内存字位数。如果用12位来表示磁盘地址，则是FAT12，用16位表示就是FAT16。不过FAT32却并不是使用32位来表示磁盘地址，实际上是用了28位。8-11151201234567891011121314文件A起始地址物理盘块号图9-3文件分配表FAT示例FAT1.3索引结构这也是一种非连续结构，通过为每个文件建立一张索引表来实现文件的逻辑空间与物理空间之间的映射。索引表的格式类似于内存管理中的页表。表目数为该文件占用的盘块数，表目号对应文件自然排序的逻辑块号，表目内容是盘块号。逻辑块号盘块号012n图9-4文件的索引表索引表是在文件建立时由文件系统动态建立的，且与该文件一起存储在同一文件卷上。在FCB中指出索引表所占用盘块的块号（索引块号）。对于一个较大的文件，其索引表可能要占用几个盘块，解决方案可采用二级索引，如图9-5所示。一级索引表占1个盘块，它的每个表项的内容为一个二级索引表的指针，设1个盘块可装有n个索引表表项，于是一共可有n个二级索引表，因此，一个二级索引文件最多可含有n×n个盘块。对于超大型文件，可进一步采用多级索引表。索引结构的优点是访问速度快，文件长度可以动态变化。缺点是存储开销大，因为每个文件有一个索引表，而索引表亦由盘块存储，故需要占用额外的卷空间。另外，当文件被打开时，索引表需要读入内存，故又需要占用额外的内存空间，当同时打开的文件很多时，内存开销是可观的。索引表指针…………FCB一级索引表二级索引表………………图9-5文件的二级索引结构§2文件目录的实现◆目录项的内容◆目录结构文件目录是实现按名存取文件的关键机制，是文件系统的核心，通过目录才能完成从抽象到现实的转换。文件目录的实现要解决两个问题：■目录项内容的设计■目录结构的设计2.1目录项的内容一个目录由若干等长的目录项（记录）组成，目录本身也作为文件来处理，它是一种等长记录式文件。目录项的组成有两种方式：FCB目录项和名号目录项。1.FCB目录项这是简单直观的目录项组成方式，目录项就是FCB，即一个目录由若干顺序排列的FCB所构成。当用路径名和文件名访问某个文件时，文件系统对目录进行线性检索，找到文件名对应的FCB，就可获取该文件的物理位置等信息，完成文件名到文件物理位置的映射。这种方式对于小规模的文件系统还可以，但对于较大规模的文件系统存在如下问题：目录跟普通文件一样也存放在文件系统中。对于较大的文件系统，当有很多文件时，目录需要占用大量的盘块。在检索目录的过程中，先将目录的第一个盘块调入内存，然后用给定的文件名逐一与该盘块里的各FCB中的文件名进行比较，若未找到指定文件的FCB，便将目录的下一个盘块调入内存，以此类推。设目录占用的盘块数为N，则查找一个FCB平均需要调入盘块(N+1)/2次。假如一个FCB为128字节，盘块大小为1KB，则每个盘块只能存放8个FCB；另如果一个目录含有200个目录项，它就需要占用25个盘块。于是，在该目录中线性查找一个目录项平均需要启动磁盘12~13次。2.名号目录项对FCB目录项方式稍加分析可以发现，在检索目录的过程中只用到了文件名，仅当找到一个FCB时才需要从该FCB中读出文件的物理地址，而FCB中的其他信息在检索目录时一概不用，显然，这些信息在检索目录时不需要调入内存。为此，UNIX率先采用了名号目录项的目录项组成方法。UNIX把文件名从FCB中分离出来，把这种不含文件名的FCB称为i-Node，并把所有文件的i-Node集中顺序存放在文件系统的固定区域（i-Node区）中。这里的i意为索引（index），故中文称索引节点或i节点。不过也有人认为i是指information。UNIX最初定义的目录项如下：这种目录项仅占16个字节，其中，“文件名”字段占14字节；“i节点号”指示该文件对应的i节点在索引节点区中的位置序号，即它是第i号索引节点，该字段占2字节。这种目录项就是名号目录项。于是在1KB的盘块中可存放64个目录项，从而大大压缩了文件目录的规模，加快了目录检索的速度。例如，对于一个含有200个名号目录项的目录文件，它需占用4个盘块。检索该目录中的一个文件时，需要2个步骤：首先，在该目录中找出文件的i节点号，平均需文件名i节点号要启动磁盘2次；然后，根据得到的i节点号可以直接计算出对应的i节点在索引节点区中的位置，即盘块号，于是，再一次读盘即可获取所需的i节点，从而完成文件名到文件物理位置的映射。即一次目录检索平均启动了磁盘3次。较新版本的UNIX和Linux对名号目录项进行了扩展：增加了“文件类型”，放宽了对文件名长度的限制。当然，名号目录项方式也是要付出代价的，它是一种空间换时间的方法。为什么？请同学们自己分析。2.2目录结构除了目录项的组成方式外，目录结构的组织方式也直接影响到文件的读写速度，并关系到文件的共享性和安全性。因此组织好文件的目录是设计文件系统的重要环节。常见的目录结构有三种：单级目录结构二级目录结构多级目录结构1.单级目录结构文件系统中只设置一个目录，它包含了该文件系统中的所有文件的目录项，要查找任一文件都需要在该目录中进行线性检索。单级目录结构的特点是实现简单，但当目录中含有大量目录项时，要查找一个文件相当费时，且它无法解决文件重名问题，这对用户是很不方便的。因此，这种目录结构只用在单用户环境中。2.二级目录结构文件系统为每个用户建立一个目录，称为用户文件目录UFD。一个用户的所有文件的目录项都并列在该目录中。文件系统又设置一个根目录，也称主文件目录MFD，每个UFD在其中占有一个目录项，目录项的内容为：用户名、UFD指针。…USER2的UFD普通文件USER1的UFDMFD用户名UFD指针USER1USER2………………图9-6二级目录结构一个MFD和若干并列的UFD便构成了二级目录结构。当要访问一个文件时，先根据用户名检索MFD，找出相应的UFD；再用文件名检索UFD，找出对应的FCB，从而就可以得到文件的具体物理地址。二级目录结构基本上克服了单目录结构的缺点，其优点如下：①提高了检索目录的速度假设在MFD中有n个目录项，每个UFD有m个目录项，则找到一指定的目录项，最多需要检索n+m个目录项，平均检索次数为n/2+m/2=(n+m)/2。但如果采用单级目录结构，则最多需检索n×m个目录项，平均检索次数为(n×m)/2。不妨设n=m，可见，采用二级目录结构可使检索效率提高约n/2倍。②较好地解决了文件重名问题在不同的UFD中可以使用相同的文件名。缺点是不能对文件进行分类，当一用户的文件很多时，文件检索仍然较费时。3.多级目录结构也称树形目录结构，是被现代操作系统普遍采用的目录结构。它按照倒挂树的形式把目录构造成一棵目录树，如图9-7所示。在目录树中，一个非终极节点（矩形）表示一个目录文件，一个叶节点（圆圈）表示一个非目录文件。从一个非终极节点出发的分支（直线）数表示一个目录所含的目录项个数。任一目录项都可以说明一个非目录文件，也可以指向一个次一级的子目录。整个目录树有一个作为起始点的根目录（ROOT）。从根出发遍历若干非终极节点到某个指定节点而形成了一条检索路径，该路径中的所有节点的名字组合成了指定节点的路径名，路径名中的各节点名之间用一特殊符号分隔（如Windows中的“\”，UNIX/Linux中的“/”）。在目录树中查找一个文件需要按路径名逐层检索。检索时可以按绝对路径名进行，也可以按相对路径名进行。绝对路径名即从根开始的路径名，相对路径名则是从工作目录（当前目录）开始的路径名。目录树使得对文件的管理和使用都十分方便。它支持将文件按类型、用途等进行分类，建立多个分类目录，而且可按需要随意扩展目录结构的层次。每个用户都可以在目录树中建立自己的目录子树。路径名的引入完全解决了文件重名问题。此外，目录树结构较之二级目录结构进一步提高了检索目录的速度。例如，在图9-7中，目录ABA下的文件a的路径名是“(ROOT)/A/AB/ABA/a”（ROOT一般可缺省），目录BA下也有一个文件a，其路径名为“(ROOT)/B/BA/a”，虽然它们的文件名相同，但它们各自的路径不同，前者是“/A/AB/ABA/”，后者是“/B/BA/”，故它们是两个不同的文件。又如，假设ROOT中有n1个目录项，目录A中有n2个目录项，目录AA中有n3个目录项，目录AB中有n4个目录项，目录AC中有n5个目录项，目录A