OS2013_UNIT9 文件系统的实现

1、Unit 9操作系统原理操作系统原理冯耀霖冯耀霖文件管理之二文件管理之二内容内容文件的物理组织文件的物理组织文件目录的实现文件目录的实现磁盘空间的管理磁盘空间的管理文件共享文件共享文件的访问控制文件的访问控制文件的注册与挂载文件的注册与挂载内核的文件管理机制内核的文件管理机制通过上一章的学习，我们对文件和文件系统已有了一通过上一章的学习，我们对文件和文件系统已有了一些感性认识。但对于操作系统的设计来说，光有感性认识些感性认识。但对于操作系统的设计来说，光有感性认识是不够的，需要进一步了解文件系统的实现细节，这些细是不够的，需要进一步了解文件系统的实现细节，这些细节问题包括：节问题包括：文件的物

2、理组织文件的物理组织文件目录的结构文件目录的结构文件的共享文件的共享磁盘空间的管理磁盘空间的管理文件的访问控制文件的访问控制文件系统的注册与挂载文件系统的注册与挂载内核的文件管理机制内核的文件管理机制1 连续结构连续结构链接结构链接结构索引结构索引结构一个文件的空间在逻辑上可看成是连续的，即一个文一个文件的空间在逻辑上可看成是连续的，即一个文件由若干连续的盘块所组成。但在磁盘上可以有多种方式件由若干连续的盘块所组成。但在磁盘上可以有多种方式来组成一个文件，换言之，文件有多种物理的存储结构，来组成一个文件，换言之，文件有多种物理的存储结构，常用的是：连续结构、链接结构、索引结构。常用的是：连续结

3、构、链接结构、索引结构。文件的物理存储结构决定了文件的逻辑地址空间到文文件的物理存储结构决定了文件的逻辑地址空间到文件的物理地址空间的映射方法。件的物理地址空间的映射方法。1.1 连续结构连续结构 又称顺序结构。指一个文件由若干相邻的盘块所组成。又称顺序结构。指一个文件由若干相邻的盘块所组成。称这种结构的文件为连续（顺序）文件。称这种结构的文件为连续（顺序）文件。这是一种最简单的文件物理结构，且读写效率很高，这是一种最简单的文件物理结构，且读写效率很高，因为一次寻道就可完成整个文件的读写。数据库文件就要因为一次寻道就可完成整个文件的读写。数据库文件就要求是连续结构，所以装数据库的话最好是在一个

4、空的卷上求是连续结构，所以装数据库的话最好是在一个空的卷上装，如果装在一个已装了很多文件的卷上，就会发现该数装，如果装在一个已装了很多文件的卷上，就会发现该数据库系统运行很慢。图据库系统运行很慢。图9-1为文件的连续结构示意图。为文件的连续结构示意图。连续结构的优点是保证了文件的逻辑块的顺序与物理连续结构的优点是保证了文件的逻辑块的顺序与物理块的顺序相一致，支持随机存取，读写速度快。缺点是：块的顺序相一致，支持随机存取，读写速度快。缺点是： 要求在建立文件时给定文件的最大长度，以便系要求在建立文件时给定文件的最大长度，以便系统分配足够的地址连续的盘块，显然这不利于文件的动态统分配足够的地址连续

5、的盘块，显然这不利于文件的动态增长；增长；在频繁的文件创建和删除之后，存在卷空间的外碎片在频繁的文件创建和删除之后，存在卷空间的外碎片问题，使得卷空间的利用率不高。问题，使得卷空间的利用率不高。首物理块号首物理块号8080 81 82 83 0 1 2 3物理块号：物理块号：逻辑块号：逻辑块号：FCB图图9-1 文件的连续结构示意图文件的连续结构示意图1.2 链接结构链接结构这是一种非连续结构。一个文件可由若干离散的盘块这是一种非连续结构。一个文件可由若干离散的盘块所组成，但需为每块设置一个链接字，用于指出下一块的所组成，但需为每块设置一个链接字，用于指出下一块的块号。称这种结构的文件为链接文

6、件。块号。称这种结构的文件为链接文件。其优点是：其优点是：一个文件不要求占用连续的卷空间，因此消除了外一个文件不要求占用连续的卷空间，因此消除了外碎片问题，文件卷的利用率较高；碎片问题，文件卷的利用率较高；一个文件可以以块为单位动态地增长和删除，易于一个文件可以以块为单位动态地增长和删除，易于文件的动态增删。文件的动态增删。链接结构又分为隐式链接和显式链接两种：链接结构又分为隐式链接和显式链接两种：(1)隐式链接隐式链接在文件的在文件的FCB中指明该文件的首块号，并在每个盘块中指明该文件的首块号，并在每个盘块内设置一个链接字内设置一个链接字next。 FCB首盘块首盘块号号8090100110

7、盘块盘块80盘块盘块90盘块盘块100盘块盘块110逻辑块逻辑块0逻辑块逻辑块1逻辑块逻辑块2逻辑块逻辑块3图图9-2 9-2 文件的隐式链接结构文件的隐式链接结构这种结构的缺点是：这种结构的缺点是：难于随机访问文件中的信息，为了读写文件中某逻难于随机访问文件中的信息，为了读写文件中某逻辑块的信息，必须从链头开始，逐一读取每个盘块，以取辑块的信息，必须从链头开始，逐一读取每个盘块，以取得下一逻辑块的盘块号；得下一逻辑块的盘块号；在每个盘块中都设置了一个链接字，破坏了盘块数在每个盘块中都设置了一个链接字，破坏了盘块数据的完整性。据的完整性。 (2)显式链接显式链接把一个文件系统中所有盘块的链接字

8、集中存放在一个把一个文件系统中所有盘块的链接字集中存放在一个专门设置的专门设置的“块链接表块链接表”中，表目数为该文件系统的盘块中，表目数为该文件系统的盘块总数，表目号对应盘块号，表目内容是该盘块的链接字。总数，表目号对应盘块号，表目内容是该盘块的链接字。显式链接较之隐式链接明显减少了访盘次数，因为对显式链接较之隐式链接明显减少了访盘次数，因为对盘块的寻址只需在块链接表上进行，故容易实现对文件的盘块的寻址只需在块链接表上进行，故容易实现对文件的随机存取，但块链接表本身相当大，调入内存后需占较大随机存取，但块链接表本身相当大，调入内存后需占较大的内存空间。例如，对于一个的内存空间。例如，对于一个

9、2GB的磁盘文件系统，设盘的磁盘文件系统，设盘块的大小为块的大小为2KB，则共有，则共有1M块，块号需用长整型数（块，块号需用长整型数（32位，占位，占4个字节）表示，于是一个盘块可存放个字节）表示，于是一个盘块可存放256个块号，个块号，而块链接表需占而块链接表需占4096个盘块，调入内存需占个盘块，调入内存需占4096个实页个实页面。面。显式链接结构，也称块链接表结构，是被广泛采用的显式链接结构，也称块链接表结构，是被广泛采用的文件物理结构之一。文件物理结构之一。DOS、Windows 2000/XP均支持均支持这种结构，并称块链接表为这种结构，并称块链接表为“文件分配表文件分配表”（FA

10、T），称），称采用这种结构的文件系统为采用这种结构的文件系统为FAT文件系统。文件系统。FAT文件系统又分为文件系统又分为FAT12、FAT16、FAT32三种。三种。它们的区别在于用来表示磁盘地址的内存字位数。如果用它们的区别在于用来表示磁盘地址的内存字位数。如果用12位来表示磁盘地址，则是位来表示磁盘地址，则是FAT12，用，用16位表示就是位表示就是FAT16。不过。不过FAT32却并不是使用却并不是使用32位来表示磁盘地址，位来表示磁盘地址，实际上是用了实际上是用了28位。位。8-11151201234567891011121314文件文件A起始地址起始地址物理盘块号物理盘块号图图9-

11、3 文件分配表文件分配表FAT示例示例FAT1.3 索引结构索引结构这也是一种非连续结构，通过这也是一种非连续结构，通过为每个文件建立一张索为每个文件建立一张索引表引表来实现文件的逻辑空间与物理空间之间的映射。来实现文件的逻辑空间与物理空间之间的映射。索引表的格式类似于内存管理中的页表。表目数为该索引表的格式类似于内存管理中的页表。表目数为该文件占用的盘块数，表目号对应文件自然排序的逻辑块号，文件占用的盘块数，表目号对应文件自然排序的逻辑块号，表目内容是盘块号。表目内容是盘块号。逻辑块号逻辑块号盘块号盘块号012n图图9-4 文件的索引表文件的索引表索引表是在文件建立时由文件系统动态建立的，且

12、与索引表是在文件建立时由文件系统动态建立的，且与该文件一起存储在同一文件卷上。在该文件一起存储在同一文件卷上。在FCB中指出索引表所中指出索引表所占用盘块的块号（索引块号）。对于一个较大的文件，其占用盘块的块号（索引块号）。对于一个较大的文件，其索引表可能要占用几个盘块，解决方案可采用二级索引，索引表可能要占用几个盘块，解决方案可采用二级索引，如图如图9-5所示。一级索引表占所示。一级索引表占1个盘块，它的每个表项的个盘块，它的每个表项的内容为一个二级索引表的指针，设内容为一个二级索引表的指针，设1个盘块可装有个盘块可装有n个索个索引表表项，于是一共可有引表表项，于是一共可有n个二级索引表，因

13、此，一个二个二级索引表，因此，一个二级索引文件最多可含有级索引文件最多可含有nn个盘块。个盘块。对于超大型文件，可进一步采用多级索引表。对于超大型文件，可进一步采用多级索引表。索引结构的优点是访问速度快，文件长度可以动态变索引结构的优点是访问速度快，文件长度可以动态变化。缺点是存储开销大，因为每个文件有一个索引表，而化。缺点是存储开销大，因为每个文件有一个索引表，而索引表亦由盘块存储，故需要占用额外的卷空间。另外，索引表亦由盘块存储，故需要占用额外的卷空间。另外，当文件被打开时，索引表需要读入内存，故又需要占用额当文件被打开时，索引表需要读入内存，故又需要占用额外的内存空间，当同时打开的文件很

14、多时，内存开销是可外的内存空间，当同时打开的文件很多时，内存开销是可观的。观的。索引表指针索引表指针FCB一级索引表一级索引表二级索引表二级索引表图图9-5 文件的二级索引结构文件的二级索引结构 2 目录项的内容目录项的内容目录结构目录结构文件目录是实现按名存取文件的关键机制，是文件系文件目录是实现按名存取文件的关键机制，是文件系统的核心，通过目录才能完成从抽象到现实的转换。文件统的核心，通过目录才能完成从抽象到现实的转换。文件目录的实现要解决两个问题：目录的实现要解决两个问题：目录项内容的设计目录项内容的设计目录结构的设计目录结构的设计2.1 目录项的内容目录项的内容一个目录由若干等长的目录

15、项（记录）组成，目录本一个目录由若干等长的目录项（记录）组成，目录本身也作为文件来处理，它是一种等长记录式文件。身也作为文件来处理，它是一种等长记录式文件。目录项的组成有两种方式：目录项的组成有两种方式：FCB目录项和名号目录项。目录项和名号目录项。1. FCB目录项目录项这是简单直观的目录项组成方式，目录项就是这是简单直观的目录项组成方式，目录项就是FCB，即一个目录由若干顺序排列的即一个目录由若干顺序排列的FCB所构成。当用路径名和所构成。当用路径名和文件名访问某个文件时，文件系统对目录进行线性检索，文件名访问某个文件时，文件系统对目录进行线性检索，找到文件名对应的找到文件名对应的FCB，

16、就可获取该文件的物理位置等信，就可获取该文件的物理位置等信息，完成文件名到文件物理位置的映射。息，完成文件名到文件物理位置的映射。这种方式对于小规模的文件系统还可以，但对于较大这种方式对于小规模的文件系统还可以，但对于较大规模的文件系统存在如下问题：规模的文件系统存在如下问题：目录跟普通文件一样也存放在文件系统中。对于较大的文目录跟普通文件一样也存放在文件系统中。对于较大的文件系统，当有很多文件时，目录需要占用大量的盘块。在件系统，当有很多文件时，目录需要占用大量的盘块。在检索目录的过程中，先将目录的第一个盘块调入内存，然检索目录的过程中，先将目录的第一个盘块调入内存，然后用给定的文件名逐一与

17、该盘块里的各后用给定的文件名逐一与该盘块里的各FCB中的文件名进中的文件名进行比较，若未找到指定文件的行比较，若未找到指定文件的FCB，便将目录的下一个盘，便将目录的下一个盘块调入内存，以此类推。设目录占用的盘块数为块调入内存，以此类推。设目录占用的盘块数为N，则查，则查找一个找一个FCB平均需要调入盘块平均需要调入盘块(N+1)/2次。次。假如一个假如一个FCB为为128字节，盘块大小为字节，盘块大小为1KB，则每个，则每个盘块只能存放盘块只能存放8个个FCB；另如果一个目录含有；另如果一个目录含有200个目录个目录项，它就需要占用项，它就需要占用25个盘块。于是，在该目录中线性查个盘块。于

18、是，在该目录中线性查找一个目录项平均需要启动磁盘找一个目录项平均需要启动磁盘1213次。次。2. 名号目录项名号目录项对对FCB目录项方式稍加分析可以发现，在检索目录的目录项方式稍加分析可以发现，在检索目录的过程中只用到了文件名，仅当找到一个过程中只用到了文件名，仅当找到一个FCB时才需要从时才需要从该该FCB中读出文件的物理地址，而中读出文件的物理地址，而FCB中的其他信息在检中的其他信息在检索目录时一概不用，显然，这些信息在检索目录时不需索目录时一概不用，显然，这些信息在检索目录时不需要调入内存。为此，要调入内存。为此，UNIX率先采用了名号目录项的目录率先采用了名号目录项的目录项组成方法

19、。项组成方法。UNIX把文件名从把文件名从FCB中分离出来，把这种不含文件中分离出来，把这种不含文件名的名的FCB称为称为i-Node，并把所有文件的，并把所有文件的i-Node集中顺序集中顺序存放在文件系统的固定区域（存放在文件系统的固定区域（i-Node区）中。这里的区）中。这里的i 意为索引（意为索引（index），故中文称），故中文称索引节点索引节点或或 i 节点节点。不过。不过也有人认为也有人认为i 是指是指information。UNIX最初定义的目录项如下：最初定义的目录项如下： 这种目录项仅占这种目录项仅占16个字节，其中，个字节，其中，“文件名文件名”字段字段占占14字节；字

20、节；“i 节点号节点号”指示该文件对应的指示该文件对应的i 节点在索引节点在索引节点区中的位置序号，即它是第节点区中的位置序号，即它是第 i 号索引节点，该字段号索引节点，该字段占占2字节。这种目录项就是名号目录项。于是在字节。这种目录项就是名号目录项。于是在1KB的盘的盘块中可存放块中可存放64个目录项，从而大大压缩了文件目录的规个目录项，从而大大压缩了文件目录的规模，加快了目录检索的速度。模，加快了目录检索的速度。例如，对于一个含有例如，对于一个含有200个名号目录项的目录文件，个名号目录项的目录文件，它需占用它需占用4个盘块。检索该目录中的一个文件时，需要个盘块。检索该目录中的一个文件时

21、，需要2个步骤：首先，在该目录中找出文件的个步骤：首先，在该目录中找出文件的i 节点号，平均需节点号，平均需文件名文件名i 节点号节点号要启动磁盘要启动磁盘2次；然后，根据得到的次；然后，根据得到的i 节点号可以直接计节点号可以直接计算出对应的算出对应的i 节点在索引节点区中的位置，即盘块号，于节点在索引节点区中的位置，即盘块号，于是，再一次读盘即可获取所需的是，再一次读盘即可获取所需的i 节点，从而完成文件名节点，从而完成文件名到文件物理位置的映射。即一次目录检索平均启动了磁盘到文件物理位置的映射。即一次目录检索平均启动了磁盘3次。次。较新版本的较新版本的UNIX和和Linux对名号目录项进

22、行了扩展：对名号目录项进行了扩展：增加了增加了“文件类型文件类型”，放宽了对文件名长度的限制。，放宽了对文件名长度的限制。当然，名号目录项方式也是要付出代价的，它是一种当然，名号目录项方式也是要付出代价的，它是一种空间换时间的方法。为什么？请同学们自己分析。空间换时间的方法。为什么？请同学们自己分析。2.2 目录结构目录结构除了目录项的组成方式外，目录结构的组织方式也直除了目录项的组成方式外，目录结构的组织方式也直接影响到文件的读写速度，并关系到文件的共享性和安全接影响到文件的读写速度，并关系到文件的共享性和安全性。因此组织好文件的目录是设计文件系统的重要环节。性。因此组织好文件的目录是设计文

23、件系统的重要环节。常见的目录结构有三种：常见的目录结构有三种：单级目录结构单级目录结构二级目录结构二级目录结构多级目录结构多级目录结构1. 单级目录结构单级目录结构文件系统中只设置一个目录，它包含了该文件系统中文件系统中只设置一个目录，它包含了该文件系统中的所有文件的目录项，要查找任一文件都需要在该目录中的所有文件的目录项，要查找任一文件都需要在该目录中进行线性检索。进行线性检索。单级目录结构的特点是实现简单，但当目录中含有大单级目录结构的特点是实现简单，但当目录中含有大量目录项时，要查找一个文件相当费时，且它无法解决文量目录项时，要查找一个文件相当费时，且它无法解决文件重名问题，这对用户是很

24、不方便的。因此，这种目录结件重名问题，这对用户是很不方便的。因此，这种目录结构只用在单用户环境中。构只用在单用户环境中。2. 二级目录结构二级目录结构文件系统为每个用户建立一个目录，称为用户文件目文件系统为每个用户建立一个目录，称为用户文件目录录UFD。一个用户的所有文件的目录项都并列在该目录中。一个用户的所有文件的目录项都并列在该目录中。文件系统又设置一个根目录，也称主文件目录文件系统又设置一个根目录，也称主文件目录MFD，每个每个UFD在其中占有一个目录项，目录项的内容为：用户在其中占有一个目录项，目录项的内容为：用户名、名、UFD指针。指针。图图9-6 9-6 二级目录结构二级目录结构一

25、个一个MFD和若干并列的和若干并列的UFD便构成了二级目录结构。便构成了二级目录结构。当要访问一个文件时，先根据用户名检索当要访问一个文件时，先根据用户名检索MFD，找出相应，找出相应的的UFD；再用文件名检索；再用文件名检索UFD，找出对应的，找出对应的FCB，从而就，从而就可以得到文件的具体物理地址。可以得到文件的具体物理地址。二级目录结构基本上克服了单目录结构的缺点，其优二级目录结构基本上克服了单目录结构的缺点，其优点如下：点如下：提高了检索目录的速度提高了检索目录的速度假设在假设在MFD中有中有n个目录项，每个个目录项，每个UFD有有m个目录项，个目录项，则找到一指定的目录项，最多需要

26、检索则找到一指定的目录项，最多需要检索n+m个目录项，个目录项，平均检索次数为平均检索次数为n/2+m/2=(n+m)/2。但如果采用单级。但如果采用单级目录结构，则最多需检索目录结构，则最多需检索nm个目录项，平均检索次数个目录项，平均检索次数为为(nm)/2。不妨设。不妨设n=m，可见，采用二级目录，可见，采用二级目录结构可使检索效率提高约结构可使检索效率提高约n/2倍。倍。较好地解决了文件重名问题较好地解决了文件重名问题在不同的在不同的UFD中可以使用相同的文件名。中可以使用相同的文件名。缺点是不能对文件进行分类，当一用户的文件很多时，缺点是不能对文件进行分类，当一用户的文件很多时，文件

27、检索仍然较费时。文件检索仍然较费时。3. 多级目录结构多级目录结构也称树形目录结构，是被现代操作系统普遍采用的目也称树形目录结构，是被现代操作系统普遍采用的目录结构。它按照倒挂树的形式把目录构造成一棵目录树，录结构。它按照倒挂树的形式把目录构造成一棵目录树，如图如图9-7所示。所示。在目录树中，一个非终极节点（矩形）表示一个目录在目录树中，一个非终极节点（矩形）表示一个目录文件，一个叶节点（圆圈）表示一个非目录文件。从一个文件，一个叶节点（圆圈）表示一个非目录文件。从一个非终极节点出发的分支（直线）数表示一个目录所含的目非终极节点出发的分支（直线）数表示一个目录所含的目录项个数。任一目录项都可

28、以说明一个非目录文件，也可录项个数。任一目录项都可以说明一个非目录文件，也可以指向一个次一级的子目录。整个目录树有一个作为起始以指向一个次一级的子目录。整个目录树有一个作为起始点的点的根目录根目录（ROOT）。）。从根出发遍历若干非终极节点到某个指定节点而形成从根出发遍历若干非终极节点到某个指定节点而形成了一条检索路径，该路径中的所有节点的名字组合成了指了一条检索路径，该路径中的所有节点的名字组合成了指定节点的定节点的路径名路径名，路径名中的各节点名之间用一特殊符号，路径名中的各节点名之间用一特殊符号分隔（如分隔（如Windows中的中的“”，UNIX/Linux中的中的“/”）。）。在目录树

29、中查找一个文件需要按路径名逐层检索。检索时在目录树中查找一个文件需要按路径名逐层检索。检索时可以按绝对路径名进行，也可以按相对路径名进行。可以按绝对路径名进行，也可以按相对路径名进行。绝对绝对路径名路径名即从根开始的路径名，即从根开始的路径名，相对路径名相对路径名则是从工作目录则是从工作目录（当前目录）开始的路径名。（当前目录）开始的路径名。目录树使得对文件的管理和使用都十分方便。它支持目录树使得对文件的管理和使用都十分方便。它支持将文件按类型、用途等进行分类，建立多个分类目录，而将文件按类型、用途等进行分类，建立多个分类目录，而且可按需要随意扩展目录结构的层次。每个用户都可以在且可按需要随意

30、扩展目录结构的层次。每个用户都可以在目录树中建立自己的目录子树。路径名的引入完全解决了目录树中建立自己的目录子树。路径名的引入完全解决了文件重名问题。此外，目录树结构较之二级目录结构进一文件重名问题。此外，目录树结构较之二级目录结构进一步提高了检索目录的速度。步提高了检索目录的速度。例如，在图例如，在图9-7中，目录中，目录ABA下的文件下的文件a的路径名是的路径名是“(ROOT)/A/AB/ABA/a”（ROOT一般可缺省），目录一般可缺省），目录BA下也有一个文件下也有一个文件a，其路径名为，其路径名为“(ROOT)/B/BA/a”，虽然它们的文件名相同，但它们各自的路径不同，前者是虽然它

31、们的文件名相同，但它们各自的路径不同，前者是“/A/AB/ABA/”，后者是，后者是“/B/BA/”，故它们是两个不，故它们是两个不同的文件。同的文件。 又如，假设又如，假设ROOT中有中有n1个目录项，目录个目录项，目录A中有中有n2个个目录项，目录目录项，目录AA中有中有n3个目录项，目录个目录项，目录AB中有中有n4个目录个目录项，目录项，目录AC中有中有n5个目录项，目录个目录项，目录ABA中有中有n6个目录项，个目录项，目录目录ABB中有中有n7个目录项。则检索文件个目录项。则检索文件a的平均检索次数的平均检索次数为为(n1+n2+n4+n6)/2。而如果采用二级目录结构，则。而如果

32、采用二级目录结构，则检索目录检索目录A下的文件下的文件a，平均检索次数需要，平均检索次数需要(n1+n2+n3+n4+n5+n6+n7)/2。图图9-7 多级目录结构多级目录结构ROOTABCAAABACBACACBABAABBCAACABCBAaabcCABA 3 空闲分区表空闲分区表空闲块链空闲块链位示图位示图空闲块的成组链接空闲块的成组链接文件系统要解决的重要问题之一是如何为新创建的文文件系统要解决的重要问题之一是如何为新创建的文件分配磁盘空间，其解决方法与内存的分配情况有许多相件分配磁盘空间，其解决方法与内存的分配情况有许多相似之处，即同样可以采取连续分配方式或离散分配方式。似之处，即

33、同样可以采取连续分配方式或离散分配方式。前者可提供较高的文件访问速度，但可能产生较多的外碎前者可提供较高的文件访问速度，但可能产生较多的外碎片；后者能有效地利用磁盘空间，但文件的访问速度较慢。片；后者能有效地利用磁盘空间，但文件的访问速度较慢。不论哪种分配方式，磁盘空间的基本分配单位都是块不论哪种分配方式，磁盘空间的基本分配单位都是块（block）而非字节，）而非字节，Windows称这种块为簇。块或者称这种块为簇。块或者簇的大小在超级块中定义。簇的大小在超级块中定义。为了实现磁盘空间的分配，文件系统首先必须能保持为了实现磁盘空间的分配，文件系统首先必须能保持磁盘空间使用情况的记录，即哪些空间

34、被占用，哪些空间磁盘空间使用情况的记录，即哪些空间被占用，哪些空间为闲置。下面是几种常用的磁盘空间的管理方法。为闲置。下面是几种常用的磁盘空间的管理方法。3.1 空闲分区表空闲分区表该方法属于连续分配方式。它与内存的可变分区方式该方法属于连续分配方式。它与内存的可变分区方式雷同，它为每个文件分配一个包含有若干编号连续的盘块雷同，它为每个文件分配一个包含有若干编号连续的盘块所组成的所组成的“盘分区盘分区”。为此，文件系统须建立一个空闲分。为此，文件系统须建立一个空闲分区表，通常采用链表形式，每个空闲盘分区对应一个表结区表，通常采用链表形式，每个空闲盘分区对应一个表结点，表结点内容包括：首盘块号、

35、盘块数、点，表结点内容包括：首盘块号、盘块数、next。空闲盘分区的分配与内存的可变分区分配类似，同样空闲盘分区的分配与内存的可变分区分配类似，同样是采用最先适配法等。回收盘分区时同样要考虑回收区是是采用最先适配法等。回收盘分区时同样要考虑回收区是否有前邻分区或后邻分区，若有的话则需进行合并。否有前邻分区或后邻分区，若有的话则需进行合并。3.2 空闲块链空闲块链该方法属于离散分配方式，它将卷上的所有空闲盘块该方法属于离散分配方式，它将卷上的所有空闲盘块链接起来。当为文件分配磁盘空间时，系统从空闲块链的链接起来。当为文件分配磁盘空间时，系统从空闲块链的链首开始，依次摘下所需数目的盘块分配之。当因

36、删除文链首开始，依次摘下所需数目的盘块分配之。当因删除文件而释放文件空间时，系统将回收的盘块依次插入空闲块件而释放文件空间时，系统将回收的盘块依次插入空闲块链的链首或链尾。链的链首或链尾。空闲块链法的优点是节省内存，但分配和回收速度较空闲块链法的优点是节省内存，但分配和回收速度较慢，实现效率较低。慢，实现效率较低。3.3 位示图位示图位示图，也称盘图。这是一种简单和低开销的方案，位示图，也称盘图。这是一种简单和低开销的方案，它只利用一个二进制位它只利用一个二进制位(bit)来表示一个盘块的分配状态：来表示一个盘块的分配状态：0 表示空闲块，表示空闲块，1 表示占用块。表示占用块。系统将一文件系

37、统中的每一个盘块都用一个对应的二系统将一文件系统中的每一个盘块都用一个对应的二进制位来标记它，所有这些二进制位组成的序列称为该文进制位来标记它，所有这些二进制位组成的序列称为该文件系统的位示图。一个二进制位在图中的坐标位置对应于件系统的位示图。一个二进制位在图中的坐标位置对应于自然线性排序的盘块块号。自然线性排序的盘块块号。位示图的大小依文件系统的大小和盘块的长度而定。位示图的大小依文件系统的大小和盘块的长度而定。例如，对于一个例如，对于一个2GB的磁盘文件系统，如盘块的长度为的磁盘文件系统，如盘块的长度为1KB，则该文件系统共有，则该文件系统共有2M（2,097,152）个盘块，因）个盘块，

38、因此它需要用此它需要用262144个字节（个字节（256KB)来构建位示图，即来构建位示图，即该图需占用该图需占用256个盘块。（较之个盘块。（较之FAT需要需要4096个盘块，个盘块，其存储开销要小的多）。其存储开销要小的多）。当分配一个盘块时，从图中找出一个值为当分配一个盘块时，从图中找出一个值为0的二进制的二进制位，如果该二进制位在图中的位置为第位，如果该二进制位在图中的位置为第 i 个字（或字节）个字（或字节）的第的第 j 列，则它对应的盘块号列，则它对应的盘块号 b ，可由以下公式求出：，可由以下公式求出：b = w * i + j /* w是字长是字长 */同时将该二进制位置同时将

39、该二进制位置“1”，表示第，表示第 b 号盘块已分配。号盘块已分配。当回收一个盘块时，将该块的块号当回收一个盘块时，将该块的块号 b 转换成字序号转换成字序号i 和列序号和列序号 j ，即有：，即有：i = b / w j = b % w然后将坐标为（然后将坐标为（i , j）的该二进制位置为）的该二进制位置为“0”，表示空闲。，表示空闲。的第的第 j 列，则它对应的盘块号列，则它对应的盘块号 b ，可由以下公式求出：，可由以下公式求出：b = w * i + j /* w是字长是字长 */同时将该二进制位置同时将该二进制位置“1”，表示第，表示第 b 号盘块已分配。号盘块已分配。当回收一个盘

40、块时，将该块的块号当回收一个盘块时，将该块的块号 b 转换成字序号转换成字序号i 和列序号和列序号 j ，即有：，即有：i = b / w j = b % w然后将坐标为（然后将坐标为（i , j）的该二进制位置为）的该二进制位置为“0”，表示空闲。，表示空闲。3.4 空闲块的成组链接空闲块的成组链接这是这是UNIX率先使用的一种方法。它把文件系统中的率先使用的一种方法。它把文件系统中的所有空闲盘块按固定数量分组，例如：每所有空闲盘块按固定数量分组，例如：每50个空闲盘块个空闲盘块为一组。第一组的盘块数和为一组。第一组的盘块数和50个盘块号放在第二组的最个盘块号放在第二组的最末一块中，第二组的

41、盘块数和末一块中，第二组的盘块数和50个盘块号又放在第三组个盘块号又放在第三组的最末一块中，以此类推，由各组的最后一个盘块可链接的最末一块中，以此类推，由各组的最后一个盘块可链接成一条链。最后一组的盘块数（可能不足成一条链。最后一组的盘块数（可能不足50）和盘块号）和盘块号放在内存的一个盘块栈中。如图放在内存的一个盘块栈中。如图9-8所示。所示。当系统要为文件分配所需的盘块时，须调用当系统要为文件分配所需的盘块时，须调用“文件分文件分配配”系统调用来完成。该系统调用首先检查盘块栈是否上系统调用来完成。该系统调用首先检查盘块栈是否上锁（盘块栈是临界资源），如未上锁，则对盘块栈执行锁（盘块栈是临界

42、资源），如未上锁，则对盘块栈执行pop操作，获取一个空闲盘块的块号并分配之；如果该盘操作，获取一个空闲盘块的块号并分配之；如果该盘块号已是栈底，这是当前栈中最后一个可分配的盘块号，块号已是栈底，这是当前栈中最后一个可分配的盘块号，由于该盘块中记有下一组可用的盘块数和盘块号，因此须由于该盘块中记有下一组可用的盘块数和盘块号，因此须将该盘块的内容读入块号栈中，作为新的块号栈的内容，将该盘块的内容读入块号栈中，作为新的块号栈的内容，并把原栈底对应的盘块分配之。并把原栈底对应的盘块分配之。在系统回收空闲盘块时，须调用在系统回收空闲盘块时，须调用“文件回收文件回收”系统调系统调用进行回收。它是将回收块的

43、块号用进行回收。它是将回收块的块号push入块号栈。当栈入块号栈。当栈已满时，先将现有栈中的已满时，先将现有栈中的50个盘块号记入回收块中，再个盘块号记入回收块中，再将该回收块的块号将该回收块的块号push入栈中，作为新栈底。入栈中，作为新栈底。 盘块栈盘块栈size变量变量栈顶栈顶栈底栈底注：注：size变量记录变量记录盘块栈的当前长度盘块栈的当前长度 图图9-8 空闲盘块的成组链接法空闲盘块的成组链接法 4 符号链接符号链接软链接软链接实现文件共享是文件系统的重要功能。文件共享是指实现文件共享是文件系统的重要功能。文件共享是指允许多个的用户使用同一个文件，这样，在系统中只需保允许多个的用户

44、使用同一个文件，这样，在系统中只需保留该文件共享的一个副本，这既可以节省大量的存储空间，留该文件共享的一个副本，这既可以节省大量的存储空间，又可减少输入输出操作从而提高文件访问速度，也为用户又可减少输入输出操作从而提高文件访问速度，也为用户之间的合作提供了便利条件。之间的合作提供了便利条件。文件共享的方法较多，如绕弯路法、连访法、基本文文件共享的方法较多，如绕弯路法、连访法、基本文件法等。这里介绍当今流行的件法等。这里介绍当今流行的链接法链接法，这是由，这是由UNIX率先率先提出的，并称之为提出的，并称之为“符号链接符号链接”，后又引入了，后又引入了“软链接软链接”。 4.1 符号链接硬链接符

45、号链接硬链接符号（符号（i节点号）链接允许一个文件可以从多个路径节点号）链接允许一个文件可以从多个路径进行访问，即一个文件可有多个路径名，从多个路径都可进行访问，即一个文件可有多个路径名，从多个路径都可以找到该文件的物理地址，也就是说，该文件的映射情况以找到该文件的物理地址，也就是说，该文件的映射情况被保存在多个目录（文件夹）里。具体来说，就是当用户被保存在多个目录（文件夹）里。具体来说，就是当用户将一个文件链接到一个目录中时，该目录里面会增加一个将一个文件链接到一个目录中时，该目录里面会增加一个目录项，用来保存该文件到文件物理地址的映射。而为了目录项，用来保存该文件到文件物理地址的映射。而为

46、了保持系统的一致性，此时在该文件的保持系统的一致性，此时在该文件的i节点里面记录被链节点里面记录被链接的次数。图接的次数。图9-9描述的是从目录描述的是从目录/home/wang链接文链接文件件test后的情况。后的情况。图中，用户图中，用户Feng创建了文件创建了文件test，他是该文件的文，他是该文件的文件主，在件主，在Feng的用户目录中有的用户目录中有test的一个目录项，该目的一个目录项，该目录项中的录项中的“i节点号节点号”指向了指向了test的的i 节点。用户节点。用户Wang是是文文件件test的授权共享用户。当的授权共享用户。当Wang为要访问为要访问test而而“打开打开”

47、 test文件时，系统为文件时，系统为test文件建立了一个符号链接，即在文件建立了一个符号链接，即在Wang的用户目录中也建立了的用户目录中也建立了test的一个目录项，该目录的一个目录项，该目录项中的项中的“i节点号节点号”同样指向了同样指向了test的的 i 节点；同时，在节点；同时，在test的的 i 节点中对节点中对链接（共享）计数器链接（共享）计数器count 值进行加值进行加1。于是，路径名于是，路径名”/home/Feng/test”和和”/home/Wang/test”对应的是同一个对应的是同一个i 节点号，指向的是同一个节点号，指向的是同一个i 节点，因而节点，因而使用这两

48、个不同的路径名访问的是同一个文件使用这两个不同的路径名访问的是同一个文件test。有了链接，需要对文件删除操作进行修改。当删除一有了链接，需要对文件删除操作进行修改。当删除一个文件时，首先对链接计数器个文件时，首先对链接计数器count进行减进行减1，然后根据，然后根据count的值决定是执行的值决定是执行“假删除假删除”还是还是“真删除真删除”。如果。如果count0，并不删除该文件的，并不删除该文件的i节点和文件体节点和文件体假删除假删除目录目录: /home/Feng test目录目录: /home/Wang testcount=2addresstest 的的i 节点节点test 图图9

49、-9 基于名号目录项的符号链接基于名号目录项的符号链接符号链接符号链接，其他链接仍然有效。只有当，其他链接仍然有效。只有当count=0，该文件的，该文件的i节点和节点和文件体才会被实际删除文件体才会被实际删除真删除。真删除。可见，这种文件共享方法的好处是，只需在文件系统可见，这种文件共享方法的好处是，只需在文件系统中保存共享文件的一个中保存共享文件的一个i 节点和一个文件体，既能节省磁盘节点和一个文件体，既能节省磁盘空间，又可保持文件数据的一致性。空间，又可保持文件数据的一致性。 符号链接也称符号链接也称硬链接硬链接（真链接可靠链接），这是因（真链接可靠链接），这是因为在若干链接中删除一个链

50、接，其他的链接不会受到影响。为在若干链接中删除一个链接，其他的链接不会受到影响。但硬链接存在一个问题。如图但硬链接存在一个问题。如图9-10所示。文件主所示。文件主Feng先于先于Wang删除了删除了test文件，这同样也是文件，这同样也是“假删除假删除” ，用，用户户Wang还可以继续使用还可以继续使用test文件。文件。但请注意：但请注意：test的文件主依然是的文件主依然是Feng，如果系统进行，如果系统进行成本记账或配额，成本记账或配额，Feng将继续为将继续为test付账，直到付账，直到Wang不不再需要而将再需要而将test删除删除Feng岂不成了冤大头了吗？这岂不成了冤大头了吗？

51、这显然会令文件主不爽。而且，文件主没有权利断开其他显然会令文件主不爽。而且，文件主没有权利断开其他用户的链接。用户的链接。 /home/Feng/home/Feng/home/Wang/home/Wangowner=Fengcount=1owner=Fengcount=2owner=Fengcount=1链接前链接前建立链接后建立链接后文件主删除文件后文件主删除文件后图图9-10 建立硬链接时的前后情况建立硬链接时的前后情况4.2 软链接软链接所谓软链接，就是不可靠链接。当文件主将文件删除所谓软链接，就是不可靠链接。当文件主将文件删除后，链接用户将无法再访问该文件。后，链接用户将无法再访问该文

52、件。与硬链接不同的是，软链接是一种类型为与硬链接不同的是，软链接是一种类型为link的特殊的特殊文件。例如，用户文件。例如，用户Feng创建了文件创建了文件test。授权用户。授权用户Wang需要共享需要共享test，并请求在自己的目录下建立，并请求在自己的目录下建立test的的软链接软链接testlink。系统将为。系统将为testlink创建一个类型为创建一个类型为link的文件，它有自己的的文件，它有自己的i 节点和文件体，但其文件体中的数节点和文件体，但其文件体中的数据只是被链接文件据只是被链接文件test的的i 节点的原始路径名而已。当节点的原始路径名而已。当Wang要访问要访问te

53、st文件时，系统先找到文件时，系统先找到testlink的的i 节点，节点，进而读出进而读出testlink的文件体，从中获取的文件体，从中获取test文件的原始路文件的原始路径名；然后根据该路径名进行检索，找到径名；然后根据该路径名进行检索，找到test的的i 节点和节点和文件体。从而实现了用户文件体。从而实现了用户Wang对对test文件的共享。文件的共享。利用软链接实现文件共享时，因为只有文件主拥有目利用软链接实现文件共享时，因为只有文件主拥有目的文件（被共享文件）的的文件（被共享文件）的i 节点号，而授权用户只有目的节点号，而授权用户只有目的文件的路径名而无其文件的路径名而无其i 节点

54、号。当文件主删除目的文件时节点号。当文件主删除目的文件时是是“真删除真删除”，此后其他用户试图通过软链接访问目的文，此后其他用户试图通过软链接访问目的文件时将遭致失败，因为该目的文件的件时将遭致失败，因为该目的文件的i 节点和文件体都已节点和文件体都已不存在了。不存在了。哈哈，文件主不会成为冤大头了！哈哈，文件主不会成为冤大头了！软链接的不足是需要额外的时间开销，访问软链接的软链接的不足是需要额外的时间开销，访问软链接的共享文件比访问硬链接的共享文件需要更多的访盘操作。共享文件比访问硬链接的共享文件需要更多的访盘操作。另外软链接需要配置额外的另外软链接需要配置额外的i 节点和文件体。节点和文件

55、体。软链接从严格意义上不是链接，因为它并没有直接连软链接从严格意义上不是链接，因为它并没有直接连到文件上，而只是保存了文件的原始访问路径而已。正因到文件上，而只是保存了文件的原始访问路径而已。正因为如此，为如此，Windows的的“快捷快捷”方式其实不是链接，因为方式其实不是链接，因为快捷方式保存的就是路径名，而且快捷方式保存的就是路径名，而且快捷方式本质上并不快快捷方式本质上并不快。那么那么Windows为什么不用硬链接呢？这是因为为什么不用硬链接呢？这是因为Windows上经常使用的是上经常使用的是FAT文件系统，而文件系统，而FAT文件系文件系统采用的是统采用的是FCB目录项，而非名号目

56、录项，故没有地方设目录项，而非名号目录项，故没有地方设置文件的链接计数器置文件的链接计数器count，硬链接无法实现。，硬链接无法实现。 5 文件的保护层次文件的保护层次文件保护的实现机制文件保护的实现机制文件的访问控制也称文件的保护，就是要确文件的访问控制也称文件的保护，就是要确保非授权用户不能随意访问某些文件，以防文件保非授权用户不能随意访问某些文件，以防文件内容被窃取或破坏。内容被窃取或破坏。 5.1 文件保护层次文件保护层次现代操作系统一般从两个层次（级别）上对文件进行现代操作系统一般从两个层次（级别）上对文件进行保护：访问级和操作级。保护：访问级和操作级。1. 访问级保护访问级保护访

57、问级保护也称用户级保护，解决的是文件的访问权访问级保护也称用户级保护，解决的是文件的访问权限，即限，即“哪些用户可以访问文件哪些用户可以访问文件”。这有两种方法来实现：。这有两种方法来实现：(1)用户名单法用户名单法这种方法需要文件主为其每个文件这种方法需要文件主为其每个文件各自提供一个授权用户名单或各自提供一个授权用户名单或“黑名单黑名单”，该名单被存放，该名单被存放在在FCB中，当某用户访问该文件时，系统将利用该名单进中，当某用户访问该文件时，系统将利用该名单进行用户身份的合法性检查，若合法则允许访问，否则拒绝行用户身份的合法性检查，若合法则允许访问，否则拒绝访问。问题是，该名单允许有多长

58、？由于名单是存放在访问。问题是，该名单允许有多长？由于名单是存放在FCB中的，其长度必然受到限制。另外，如果名单过长，输入中的，其长度必然受到限制。另外，如果名单过长，输入名单也烦了点。名单也烦了点。(2)用户分类法用户分类法较之用户名单法，这是一种低开销较之用户名单法，这是一种低开销的方法。系统将将所有用户分成若干类别，文件主只需指的方法。系统将将所有用户分成若干类别，文件主只需指定其文件允许哪个些类用户访问即可。定其文件允许哪个些类用户访问即可。例如，在例如，在UNIX和和Linux 中将用户简单地分为三类：中将用户简单地分为三类：文件主文件主同组用户同组用户其他用户其他用户2. 操作级保

59、护操作级保护如果对授权用户在对文件的具体操作上不加以限制的如果对授权用户在对文件的具体操作上不加以限制的话，对文件仍然是不安全的。因此在访问级保护的基础上话，对文件仍然是不安全的。因此在访问级保护的基础上还必须进行文件的操作级保护。还必须进行文件的操作级保护。操作级保护解决的是授权用户对文件的操作权限，即操作级保护解决的是授权用户对文件的操作权限，即“授权用户可对该文件执行何种操作授权用户可对该文件执行何种操作”。文件操作有许多，要为不同类型的授权用户指定不同文件操作有许多，要为不同类型的授权用户指定不同的文件操作是不现实的。通常的做法是，系统设置了若干的文件操作是不现实的。通常的做法是，系统

60、设置了若干文件操作类型，并用它们给用户授权。例如，文件操作类型，并用它们给用户授权。例如，UNIX和和Linux 采用了一种低开销的方法，它只设置了三种文件操采用了一种低开销的方法，它只设置了三种文件操作类型：读、写、执行。作类型：读、写、执行。读读（read）：对普通文件而言，允许授权用户可打）：对普通文件而言，允许授权用户可打开并读取文件的内容；对目录文件而言，允许授权用户可开并读取文件的内容；对目录文件而言，允许授权用户可浏览目录的内容；对特殊文件而言，则指授权用户可使用浏览目录的内容；对特殊文件而言，则指授权用户可使用设备进行数据的输入。设备进行数据的输入。写写（write）：对普通文