title: 文件系统
tags: 现代操作系统

长期存储信息的三个要求：
（1）能够存放大量的信息。
（2）进程终止后，信息不会丢失。
（3）多进程可并发的访问。
文件是进程创建的信息逻辑单元，是对磁盘的抽象。（进程是对CPU的抽象，地址空间是对内存的抽象）

1 文件

文件命名：不同系统不同规则。Unix区分大小写，DOS不区分大小写。文件名包括基本名、“.”、扩展名。Unix中扩展名只是一种约定。
文件结构：字节序列、记录序列、树。

无结构字节序列：OS看到的全都是字节，具体内容由用户程序解释。

记录序列：文件是具有固定长度记录的序列。

树：文件按照键组成一个树，以进行快速查找。

普通文件类型：二进制文件和ASCII文件。
文件属性：OS保存的与文件相关的信息。包括保护与权限、标志、大小、创建时间、最大长度等。
文件操作：create、delete、open、close、read、write、append、seek、get attributes、setattributes、rename。

2 目录

Unix中目录也是一种文件。
一级目录系统：所有文件都在一个目录中。
层次目录系统：文件存放在不同层级的目录中，便于分组。
路径名：绝对路径、相对路径。

绝对路径：从根目录开始。
相对路径：从当前工作目录开始。

目录操作：create、delete、opendir、closedir、readdir、rename、link（硬链接：一个文件有多个文件名）、unlink、symbol link（一个指向源文件的小文件）。

3 文件系统的实现

3.1 文件系统布局

文件系统存放在磁盘上。多数磁盘划分为一个或多个分区，每个分区中有一个独立的文件系统.计算机被引导时，BIOS读入并执行MBR。MBR做的第一件事是确定活动分区，读入引导块，并执行之。引导块中的程序将装在该分区中的操作系统。

文件系统

MBR:磁盘的0号扇区称为主引导记录（MBR），用来引导计算机。

分区表:在MBR的结尾是分区表。该表给出了每个分区的起始地址和结束地址。表中的一个分区被标记为活动分区。

引导块：活动分区的第一个块。引导块中的程序将装在该分区中的操作系统。

超级块：包含文件系统的所有关键参数。

空闲空间管理：空闲块的信息，可以用位图或指针表形式给出。

i节点：数据结构数组，每个文件一个，说明文件的方方面面。

根目录：目录树的根部。

目录和文件：存放其他所有目录和文件

3.2 文件的实现

连续分配：每个文件存放在连续的磁盘块上。优点：实现简单，读性能好。缺点：产生较多磁盘碎片。解决办法：压缩磁盘或重用碎片，但代价都高。
链表分配：为每个文件构建一个磁盘块的链表。优点：不会产生较多的磁盘碎片，顺序读快。缺点：随机读慢，指针占用额外空间。
采用内存中的表进行链表分配：把每个磁盘块的指针放在内存中的一个表中，叫做文件分配表（FAT）。缺点：磁盘大时占用太多内存。
i节点：为每个文件赋予一个叫i节点的数据结构，记录了文件属性和磁盘地址。

3.3 目录的实现

目录系统的作用：将ASCII文件名映射为定位文件数据所需的信息。
简单目录：目录中有一个固定大小目录项的列表，每个文件对应一项，其中包含一个文件名、一个文件属性的结构体以及说明磁盘块位置的一个或多个磁盘地址。
对于采用i节点的系统：采用i节点的系统，把文件属性存放在i节点中，目录项更短，只有文件名和i节点号。
可变长度的长文件名的处理：

给文件名一个长度限制，为文件名预留固定大小的空间。缺点：浪费空间。

目录项前面是固定的格式（其中记录了文件名的长度），后面是可变长度的文件名。缺点：磁盘碎片和缺页中断。

目录项由文件属性和指向文件名的指针组成，文件名存放在其它地方。

加快文件查找速度的办法：在每个目录中使用散列表或将查找结果存放到高速缓存中。

3.4 共享文件

共享文件时，如果目录项包含地址，并且采取硬链接的方式，则一个用户修改用户文件后，其它用户并不知道。
解决办法：一是采用i节点，磁盘地址不放在目录项中而是放在特有的结构中，缺点：当一个文件删除，而硬链接未删除，当i节点重新分配时，链接的文件错误，查找时多次定位。二是采用符号链接，缺点：额外开销，查找时多次定位。

3.5 日志结构文件系统

原因：CPU速度越来越快，内存容量越来越大，磁盘高速缓存也越来越大，但寻道时间并没有很大改善。
基本思想：将整个磁盘结构化为一个日志。每隔一段时间，或是有特殊需要时，被缓冲在内存中的所有未决的写操作都被放到一个单独的段中，作为在日志末尾的一个邻接段写入磁盘。
LFS中，i节点分散在整个日志中，因而要维护一个i节点的索引图，保存在磁盘上也保存在高速缓存中。
问题：日志越来越大。解决办法：设置一个清理线程。周期性的扫描日志进行磁盘压缩。先检查段摘要，然后查看i节点图，判断i节点是否有效，以及文件块是否在使用，如果没有使用则该信息被丢弃，如果在使用，i节点和块进入内存等待写入下一个段中，然后将原来的段标记为空闲，以便下次使用。

3.6 日志文件系统

保存一个用于记录系统下一步将要做什么的日志。这样当系统在完成它们即将完成的任务前崩溃时，重新启动之后，可以通过查看日志，获取崩溃前计划完成的任务，并完成它们。这样的文件系统称为日志文件系统。要求：写入日志的操作可以重复多次而不会带来破坏。
引入原子事务的慨念。

3.7 虚拟文件系统

windows使用盘符来处理不同的文件系统，所谓不需要将不同的文件系统整合，而大多数UNIX操作系统都使用虚拟文件系统概念尝试将多种文件系统统一成一个有序的框架。
关键思想:抽象出所有文件系统的共有部分，并且将这部分代码放在单独的一层，该层调用底层的实际文件系统来具体管理数据。

VFS有对用户进程的上层接口（POSIX接口），对实际文件系统的下层接口。只要实际文件系统提供VFS所需的功能，VFS就不需要知道或者关心数据具体存放在什么地方或者底层实际文件系统是什么的样子。
实际文件系统在使用前必须先注册，即提供一个包含VFS所需函数的地址的列表。
设计实际文件系统时只需要先获得VFS期待的功能，然后再实现这些功能即可，如果文件系统已经存在，则只需提供VFS所需功能即可。

4 文件系统管理和优化

4.1 磁盘空间管理

存放文件的两种方式：为一个文件分配连续的字节或者将一个文件分成多块。

4.1.1 块大小

块太大，浪费空间；块太小，寻道浪费时间。

4.1.2 记录空闲块

两种方法：链表、位图。
比较：当空闲快较多时，位图占空间小;当磁盘碎片多时，记录连续分块比记录单独块效率低。
对于链表，在内存中保留一个指针快，分配磁盘空间时取出，现有指针用完时，读入新的块；释放磁盘时，加入内存的指针块中，指针填满块时，写入磁盘。问题：不必要的磁盘IO，如释放的磁盘使指针块满，将指针快写入磁盘，之后有创建了一个相同大小的文件，又需要读入指针块。解决办法：拆分满了的指针块，保证磁盘上的指针块大多数是满的，而内存中的指针块是半满的。
对于位图，也只在内存保留一块，只有当其满了或空了，才从磁盘取另一块。优点：减小磁盘臂移动，若内核分页则可以放入虚拟内存。

4.1.3 磁盘配额

思想：为防止贪心占用太多的磁盘空间，多用户操作系统由系统管理员分配给每个用户拥有文件和块的最大数量，OS确保。
实现：每个用户有磁盘配额文件，当打开文件时，OS从文件属性中获得文件所有者，读入对应配额表，并在打开文件表中创建一个指向配额表的指针，任何关于文件大小的改变都记到所有者的配额中,每次往文件中添加块时都会引发配额检查。当所有文件关闭时，配额表重新写回配额文件。
用户登录时，检查配额文件，如果文件数或块数超过软限制，就发出警告，然后警告计数减1，直到为0时禁止登录。因而，用户只要在退出前消除超过限制部分，就可以会话期间超过软限制，但无论什么情况不得超过硬限制。

4.2 文件系统备份

备份原因：
（1）意外灾难，如磁盘损坏
（2）错误操作，用户误操作
需要考虑的问题：
（1）备份整个文件系统或者只备份部分？——备份特定目录及其下的全部文件。
（2）每次都全面备份还是增量备份？——周期性全面备份，每次做增量备份。
（3）是否要压缩？
（4）怎么对活动文件系统备份？——记录文件系统的瞬时快照。
（5）其它非技术问题？——数据安全。
备份方式：物理转储和逻辑转储。

物理转储：从磁盘0块开始备份整个磁盘。
（1）未使用的磁盘块无需备份。
（2）关注坏块的转储。
逻辑转储：从指定目录开始，递归转储其自给定日期后所有修改过的全部文件和目录。

典型的逻辑转储过程：
（1）递归检查目录和文件。在i节点的位图中标记出修改过的文件和所有的目录。
（2）遍历目录树，在位图中清除文件和子目录未发生任何变化的目录的标记，
（3）转储标记的目录。
（4）转储标记的文件。

文件系统恢复过程：
（1）创建空文件系统。
（2）恢复最近的完整备份。先恢复目录，在恢复文件。
（3）依次恢复增量转储。
文件恢复中的问题：
（1）需要重新构造空闲快列表。
（2）对于链接，同一文件只应该恢复一次。
（3）文件空洞不应该转储和恢复。
（4）特殊文件、管道等不应该转储和恢复。

4.3 文件系统的一致性

原因：修改过的磁盘块全部写回之前系统崩溃。
解决工具：Unix中fsck，windows中scandisk。
fsck：检查分为块的一致性、文件的一致性两方面。

块一致性检查：构建两张表，第一张用于跟踪每个块在文件中的出现次数，第二张表用于跟踪每个快在空闲表或空闲位图中出现的次数。初始计数器置为0.

如果一致，则每个块或在第一张表，或在第二张表中为1。

如果不一致：

两张表中都为0，则块丢失。解决办法：从新添加到空闲块的记录表中。

在第一张表中为0，在第二张表中大于1。解决办法：重建空闲块链表。

在第一张表中大于1，在第二张表中为0。解决办法：将该块内容复制一份，然后插入到其中一个文件。

文件一致性检查：建立一张表用于记录每个文件在所有目录中出现的次数。符号链接不计数。然后与i节点的链接计数比较。

如果一致，则相等。
如果不一致：
i节点的链接计数大于目录数。导致所有文件删除后，仍无法杀删除i节点，从而浪费磁盘空间。解决办法：将链接计数设置为正确值。
i节点的链接计数小于目录数。导致删除i节点后，剩余的链接指向错误文件。解决办法：将链接计数设置为正确值。

4.4 文件系统的性能

机械硬盘的访问速度非常慢。极大的影响了文件系统的性能。对于SSD，由于写入次数限制，所以要保证均匀分散磨损。

4.4.1 高速缓存

分为块高速缓存和缓冲区高速缓存。目的是减少磁盘访问。原理：对所有的读请求，先查看块是否在高速缓存中，若在，则直接读取，若不在，则先从磁盘装入高速缓存，再从高速缓存中读取。

相关的问题：
（1）如何快速确定所需块是否在高速缓存中？——构造设备和磁盘地址的散列表。
（2）高速缓存的换入换出？——类似页面置换算法。
（3）如何确保文件系统一致性？——写入高速缓存的数据立即写入磁盘或者用守护进程周期性的将写入缓冲区的数据写入磁盘。缺点：前者较多的磁盘IO，后者系统崩溃时可能丢失一个周期的数据。

4.4.2 块提前读

对于顺序读取，当从高速缓冲区中读入块K时，若块k+1不在高速缓存中，则读入。
对于随机读取，不适用。
如果不能确定访问方式，则设置一个顺序访问位，默认顺序访问，然后清除该位，如果再次顺序访问，就再次设置。

4.4.3 减少磁盘臂运动

思想：把可能顺序访问的块放在一起，最好在同一柱面上。
对于空闲位图则比较容易，对于空闲链表则需使用块簇技术。
使用i节点的文件系统，访问一个文件要产生两次磁盘访问。解决办法：在磁盘中部存放i节点，或者，将磁盘分为多个柱面组，每个组有自己的i节点、数据块和空闲表。

4.5 磁盘碎片整理

随着文件的删除与创建，文件碎片增加，创建新文件时，块散布在整个磁盘上，使得性能降低。SSD不需要碎片整理。

5 文件系统实例

5.1 MS-DOS的FAT文件系统

MS-DOS 使用32位固定大小的目录项。

文件名：基本名8B，扩展名3B。左对齐，右边补空格。
属性：共1B，包括只读位、存档位、隐藏位、系统文件位。
只读位：该文件是否只读。
存档位：文件修改后设置，文件备份后清除。
隐藏位：不出现在目录列表中。
系统文件位：隐藏该文件，且不可用哪个del命令删除。
保留：10B，未使用
时间：2B，秒占5bit，分占6bit，时占5bit。
日期：2B，日占5bit，月占4bit，年占7bit。
第一块块号：2B，记录文件的第一个磁盘块的块号。也是FAT表的索引。
文件大小：4B，理论大小为4GB，实际限制为2GB。

FAT文件系统根据磁盘地址的长度分为FAT12、FAT16、FAT32（实际为FAT28）

</tr>
<tr>
    <td>块大小</td>
    <td>FAT-12</td>
    <td>FAT-16</td>
    <td>FAT-32</td>
</tr>
<tr>
    <td>0.5KB</td>
    <td>2<sup>12</sup>x512B=2MB</td>
    <td></td>
    <td></td>
<tr>
<tr>
    <td>1KB</td>
    <td>2<sup>12</sup>x1KB=4MB</td>
    <td></td>
    <td></td>
</tr>
<tr>
    <td>2KB</td>
    <td>2<sup>12</sup>x2KB=8MB</td>
    <td>2<sup>16</sup>x2KB=128MB</td>
    <td></td>
</tr>
<tr>
    <td>4KB</td>
    <td>2<sup>12</sup>x4KB=16MB</td>
    <td>2<sup>16</sup>x4KB=256MB</td>
    <td>2<sup>28</sup>x4KB=1TB</td>
</tr>
<tr>
    <td>8KB</td>
    <td></td>
    <td>2<sup>16</sup>x8KB=512MB</td>
    <td>2<sup>16</sup>x4KB=512Bx2<sup>32</sup>=2TB</td>
</tr>
<tr>
    <td>16KB</td>
    <td></td>
    <td>2<sup>16</sup>x16KB=1024MB</td>
    <td>2TB</td>
    
</tr>
<tr>
    <td>32KB</td>
    <td></td>
    <td>2<sup>16</sup>x32KB=2048MB</td>
    <td>512Bx2<sup>32</sup>=2TB（扇区数最多为2<sup>32</sup>）</td>
</tr>

	文件系统

5.2 Unix v7 文件系统

有向无环图：顶点间的边是有方向的，并且从任一顶点出发都不能再回到该点。
Unix文件系统使用i节点，因此目录项只有两项。当文件太大时可以使用一次、二次或者三次间接块。

i节点号：2B，因此文件数最多为64K。

文件名：14B。

查找绝对路径：首先定位根目录，根目录的i节点存放在磁盘固定位置。然后在根目录中查找下一级目录或文件。
查找相对路径：类似。只不过从当前工作目录开始查找。每个目录中都有.和…两个文件项。.是当前目录，…是当前目录的父目录。根目录中…指向自身。

5.3 CD-ROM文件系统

CD-ROM只能写一次，无序记录空闲块。CD-R可以写多次，但只能添加不能删除。

5.3.1 ISO 9660 文件系统

目标：使CD-ROM独立与机器字节序和操作系统。
CD-ROM用螺旋线来顺序存储信息。每个逻辑块包含2352字节位序。逻辑块按照每秒75块进行分配。支持的CD-ROM集可以有2¹⁶-1个CD。每个CD-ROM可分为多个逻辑分区。
文件系统布局：CD-ROM起始的16块为自定义用途。第17块存放基本卷描述符：包括系统标识符（32B）、卷标识符（32B）、发布标识符（128B）、数据预备标识符（128B）、三个文件名（存储概述、版权声明、文献信息）、关键数字信息（逻辑块大小、总块数、创建日期、过期日期）、根目录的目录项（定位根目录）。CD-ROM还包含一个补充卷描述符，类似基本卷描述符。
目录项：目录项长度可变，由10到12个域组成。

目录项长度：记录这个目录项的长度。因为目录项长度可变。

扩展属性记录长度：如果使用了扩展属性，则说明扩展属性的长度。

文件起始位置：文件的第一块块号。

文件大小：说明文件的大小。

日期和时间：年、月、日、时、分、秒、时区。

标志位：

隐藏位：该目录项不出现在目录列表。

目录位：区分该项是文件还是目录。

扩展属性位：是否使用扩展属性。

最后一项位：该目录项是否是该目录的最后一项。

文件分隔块：是否使用文件分隔块。

CD号：该文件存放在哪一个CD-ROM中。

L域：文件名的长度。

文件名：格式为“基本名（8B）.扩展名（3B）;版本号（2B）”。只能用字母、数字、下划线。

填充：确保每个目录项为偶数字节。填充0。

系统使用：自定义，但要求为偶数字节。

目录中第一项为当前目录，第二项为父目录。其余按字母顺序拍了。最大目录嵌套深度为8。
限制级别：级别1，文件使用8+3命名，必须连续。目录名为8字符。级别2，允许31字符的目录名和文件名。级别3，在级别2的基础上，不在要求文件连续。

5.3.2 Rock Ridge扩展

目标：在CD-ROM上实现Unix文件系统。
方法：使用系统使用域。不识别Rock ridge扩展的系统可忽略。

PX——POSIX属性。标准Unix的模式字。

PN——主设备号和次设备号。

SL——符号链接。

NM——替代名。不受ISO 9660长度限制和字符集限制。

CL——子位置。与父位置、重定位一起消除对ISO 9660对目录嵌套深度的限制。

PL——父位置。

RE——重定位。

TF——时间戳。最后访问时间，最后修改时间，创建时间。

5.3.3 Joliet扩展

目标：在CD-ROM上实现windows文件系统。主要包括：

文件名最多64字符。

文件名可以使用Unicode字符集。

任意深度的目录嵌套。

目录可带扩展名。

秒客网