一、文件存储空间管理

文件存储空间管理就是研究文件系统如何为一个文件分配空闲磁盘块的。管理方法包括：空闲表法，空闲链表法，位图法和成组链接法。

需要关注3个问题：

用什么方式记录、组织空闲块？

如何分配磁盘块？

如何回收磁盘块？

存储空间的划分和初始化

安装 Windows 操作系统的时候，一个必经步骤是——为磁盘分区（C: 盘、D: 盘、E: 盘等）。如C盘、D盘这样的逻辑分区就是文件卷（逻辑卷、逻辑盘）。

文件系统将一个物理磁盘划分 为多个文件卷：

每个文件卷划分为 目录区和文件区。目录区存放文件目录信息（FCB）、iNode节点和磁盘存储空 间管理的信息。

文件系统也可将多个物理磁盘合并 为一个逻辑上的文件卷：

1. 存储管理之空闲表法

空闲表法用一个空闲盘块表记录连续的多个空闲块的开始块号和空闲块数。该方法用于连续分配方式的盘块管理。

如何分配磁盘块：与内存管理中的动态分区分配很类似，为一个文件分配连续的k块存储空间同样可采用首次适应、最佳适应、最坏适应等 算法来决定要为文件分配哪个区间。

例如要分配3块空闲块，按照首次适应，应该选择分配表中第一个满足有3个空闲块的区域，因此应该分配 10、11、12这3块。

按照最佳适应则应该分配 18、19、20这3块，这样刚好用完这个连续区。

按照最坏适应则应该选择能满足3个空闲块（表中第3行）的最大区域，即10、12、13这3块。

如何回收磁盘块：与内存管理中的动态分区分配很类似，当回收某个 存储区时需要有四种情况——①回收区的前后都没有相邻空闲区；② 回收区的前后都是空闲区；③回收区前面是空闲区；④回收区后面是 空闲区。总之，回收时需要注意表项的合并问题。

2. 存储管理之空闲链表法

空闲链表法可以分为空闲盘块链和空闲盘区链。

空闲盘块链以盘块作为一个链表节点；空闲盘区链以多个连续的盘块（即一个盘区）作为一个节点。

对于空闲盘块链，系统保存着链头、链尾指针。每一个节点记录下一个物理块号（向后指针）。

如何分配：若某文件申请 K 个盘块，则从链头开始依次摘 下 K 个盘块分配，并修改空闲链的链头指针。

如何回收：回收的盘块依次挂到链尾，并修改空闲链的链 尾指针。

该方法适用于文件是链式存储的物理结构。

对于空闲盘块链，系统保存着链头、链尾指针。每一个节点记录本盘区的盘块数和下一个盘区的首个物理块号（向后指针）。

如何分配：若某文件申请 K 个盘块，则可以采用 首次适应、最佳适应等算法，从链头开始检索， 按照算法规则找到一个大小符合要求的空闲盘区， 分配给文件。若没有合适的连续空闲块，也可以 将不同盘区的盘块同时分配给一个文件，注意分 配后可能要修改相应的链指针、盘区大小等数据。

如何回收：若回收区和某个空闲盘区相邻，则需 要将回收区合并到空闲盘区中。若回收区没有和 任何空闲区相邻，将回收区作为单独的一个空闲 盘区节点挂到链尾。

该方法适用于文件是链式存储和连续存储的物理结构。

3. 存储管理之位图法

位示图一般用连续的“字”来表示，如本例中一 个字的字长是16位，字中的每一位对应一个盘块的状态。“0”代表盘块空闲， “1”代表盘块已分配。

因此可以用（字号，位号）对应一个盘块号。

如何分配：若文件需要K个块，①顺序扫描位示图，找到K个相邻或不相邻 的“0”；②根据字号、位号算出对应的盘块号，将相应盘块分配给文件； ③将相应位设置为“1”。

如何回收：①根据回收的盘块号计算出对应的字号、位号；②将相应二进 制位设为“0”。

上面这些空闲表，空闲链表和位示图都是存储在一个文件卷的目录区的磁盘空间中的。

4. 存储管理之成组链接法

空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。UNIX系统中采用了成 组链接法对磁盘空闲块进行管理。

文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。并且要保 证内存与外存中的“超级块”数据一致。

成组链接法是将空闲块划分为一组一组的，每组内的多个空闲块是可以不连续的。每一组空闲块的最后一块（或者第一块）记录着下一组空闲块的所有块号和块数，组内除了最后一块的其它块用于存数据。

超级块则记录了第一组空闲块的所有盘块号和块数。只有超级块是在目录区的。

这样一来，所有记录着下一组的空闲块号和块数的块就在逻辑上组成一个链表。

如何分配？（一个块内能记录的空闲块号是有限的，这里假设一个块能记录100个空闲块号）

如果文件需要1个空闲块

①从超级块中检查第一个分组的块数是否足够。1<100，因此是足够的。

②分配第一个分组中的1个空闲块，并修改相应数据。

如果文件需要100个空闲块

①检查第一个分组的块数是否 足够。100=100，是足够的。

②分配第一个分组中的100个空闲块。但是由于300号块内 存放了再下一组的信息，如果把这一块分给文件，那这一块的下一组空闲块信息就会被文件数据覆盖，因此在分配前要把 300号块的数据需要复制到超 级块中。

如何回收？

假设每个分组最多为100 个空闲块，此时第一个分组已 有99个块，还要再回收一块，就把空闲块号往超级块后面追加即可。

如果此时第一个分组已 有100个块，还要再回收一块或者多块。

需要将超级块中的数据复制到 新回收的块中，并让新回收的块作为第一组，第一组中只有一个块，而且这个块不是数据块而是记录下一组信息的块。同时修改超级块 的内容记录新的第一个分组的信息。

二、文件共享

文件共享的方式分为 基于索引节点的共享（硬链接） 和 基于符号链的共享（软链接）。

1. 基于索引节点的共享（硬链接）

索引结点是一种文件目录瘦身策略。由于检索文件时只需用到文件名，因此可以将除 了文件名之外的其他信息放到索引结点中。这样目录项（FCB）就只需要包含文件名、索引结点指针。

同时索引节点也有共享文件的作用。通过让多个不同的目录项去记录同一个索引节点指针做到共享文件。共享同一文件的不同目录项的文件名可以不同。

索引结点中会设置一个链接计数变量 count，用于表示链接到本索引结点上的目录项数。

若 count = 2，说明此时有两个用户目录项链接到该索引结点上，或者说是有两个用户在共享此文件。

若某个用户决定“删除”该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引结点的 count值减 1。

若 count>0，说明还有别的用户要使用该文件，暂时不能把文件数据删除，否则会导致指针悬空。

当 count = 0 时系统负责删除文件。

2. 基于符号链的共享（软链接）

如果一个目录要对文件A使用软链接的共享，需要指明是对哪个文件路径进行共享（可能文件A有两个硬链接路径，此时需要选一个路径作为软链接的目标）。系统会为文件A创建一个link类型的文件，这个link文件B也有自己的索引节点，link文件B的内容是文件A的某一个路径。

通过软链接找文件A，需要根据link文件B的路径找到目录项中B文件的索引节点，再找到和读取B的磁盘块内容，得到文件A的路径，再根据A的路径找到A的目录项和索引节点最后找到A文件的开始地址。

如果图中两个硬链接都删掉，文件1也会被删除，但软链接文件2不会被删除，只是无法通过文件2找到文件1而已。

需要注意的是，使用软链接找目标文件会比硬链接要多若干次磁盘IO，因此软链接共享比硬链接共享慢。

三、文件保护

文件保护有 口令保护、加密保护 和 访问控制 3种方式。

口令保护其实就是为文件设置一个密码，打开文件需要输入密码。口令保存在索引节点中。

加密保护也是用户为文件设置一个密码，而且系统会用这个密码对文件进行加密。以最简单的异或加密算法为例：

假设密码是 01001，则将文件内容的每一个位和密码的位进行异或运算得到加密后的内容，文件实际存储的是加密后的内容。

用户打开文件时需要输入密码，并用密码进行解密（是对密文进行异或运算）。

相比口令保护，加密保护无需在系统中存储密码，因此更安全。缺点是加密和解密要花费一定时间。

访问控制在每个文件的FCB（或索引结点）中增加一个访问控制列表（Access-Control List, ACL），该表中记 录了各个用户可以对该文件执行哪些操作。

最后回顾文件系统整个框架再对文件系统的层次结构做一次小结

用户接口层负责向上层的用户进程提供 操作文件的系统调用；

目录系统层负责通过文件路径来访问文件的， 需要根据用户给出的文件 路径找到相应FCB或索引结点；目录相关的管理工作都在 本层完成，如：管理活跃的文件目录 表（已打开的当前目录）、管理打开文件表等；

权限控制层验 证用户是否有访问权限；

逻辑文件系统与 文件信息缓冲区负责把逻辑上有结构的文件将记录号转换为对应 的逻辑地址。

物理文件系统把上一层提供的文件逻 辑地址转为物理地址。

辅助分配模块负责分配和回收物理块。

设备管理模块负责直接与硬件交互，如：分 配设备释放设备、分配设备缓冲区、磁盘 调度、中断处理等。

用一个例子来辅助记忆文件系统的层次结构：

假设某用户请求删除文件 “D:/工作目录/学生信息.xlsx” 的最后100条记录。

1. 用户需要通过write系统调用向文件系统发出IO请求——用户接口

2. 用户提供文件路径找到对应的目录项——文件目录系统

3. 检查用户是否有访问权限——权限控制层

4. 把用户提供的“记录号”转变为对应的逻辑地址——逻辑文件系统与文件信息缓冲区

5. 逻辑地址后转换成实际的物理地址——物理文件系统

6. 要删除这条记录，必定要对磁盘设备发出请求——设备管理程序模块

7. 删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收——辅助分配模块

更多内容请关注微信公众号