操作系统如何组织电脑中的文件？——OS的文件管理

一、文件的物理结构

经常买二手机械盘的朋友都知道，某鱼上淘来一个来路不明的盘后要做的第一件事，便是用软件扫盘，检查磁盘是否有坏道。通常来讲，扫盘软件将磁盘划为一个一个的小区块，通过往区块中读写数据来检测其对应的硬件是否正常。

操作系统在组织文件时也是类似的思想。它将磁盘物理上划为若干磁盘块，所有对磁盘的读写操作均以磁盘块为单位。磁盘块的大小一般与内存页面一致。_{👉拓展：内存分页的实现原理。}

有学识渊博的朋友可能注意到，机械盘会被划分成很多扇区，磁盘块一般由多个逻辑地址连续的扇区组成。

换言之，你保存的文件会被切割成一小块一小块，放入磁盘中对应的磁盘块中。那么我们该如何分配这些盘块呢？

1.连续分配

直觉上最显而易见的，我们可以在磁盘上找一块连续的空间，直接把文件塞进去。假设我们有一块如下图所示的磁盘：

^{其中橙色表示已使用，白色表示空盘块}

而你有一个长约4个盘块的文件需要存储。那不难看出，之需要简单地把它放在第5～8个盘块处即可，很简单。

^{绿色表示分配给这个文件的盘块}

但这样会带来一个问题：如果我们要存的文件大多在4个盘块以上，存到后面我们会发现，虽然磁盘中仍有很多空闲的盘块，我们却没法存入新的文件了，换言之，采用连续存储的方法会产生大量的外部碎片。并且，如果我们想要修改这个文件（例如在文件中见新加一个盘块的内容），我们需要复制一整个文件下来，加入新内容后，重新找一个更大的连续区域放进去——这样子性能就太差了。

2. 链接分配

继承数据结构的思想，我们可以把文件以类似链表的方式存储。这样就可以把文件离散地存在磁盘中。

1) 隐式链接

我们可以在每个盘块中划出一部分，用于存储指向下一个盘块的指针。如下图所示。

这些指针由操作系统管理，对用户完全透明。

透明指的是：用户无法感知到服务的存在。

在此处即代表，用户看到的是一个完整的连续文件，而操作系统在存储时会自动把它分块并离散存储。

隐式链接的缺点同样明显。

1. 如果我们需要访问文件中间或尾部的一个盘块，我们需要从第一个盘块逐个遍历道目标盘块，随机访问的效率较低。
2. 它的可靠性较差，如果中间任意一个指针损坏了，则后续所有的数据都无法访问。
3. 盘块中存储的指针会占用存储空间，降低存储效率。

为了一定程度上缓解这些问题，人们把若干连续的盘块合成一个簇，规定文件的分配与链接以簇为单位。这样可以大幅度减少指针数量，提升I/O性能。但如果文件大小不是簇的整数倍时，最后一个簇的空间会有浪费，产生内部碎片。

2) 显式链接

显式链接使用大名鼎鼎的FAT表(File Allocation Table)。它不把指针存在盘块中，而是在内存中维护一张文件分配表，在表内标注下一个盘块。

如上图所示，盘块2的下一块是5，5的下一块是6，6的下一块是3，而3是最后一块了，故标注为-1。空闲的盘块则标注-2。没错，FAT表不仅记录了文件的链式结构，还标识了空闲的盘块，这意味着操作系统可以直接用FAT管理磁盘的空闲空间。

试想有个进程想要存储2个盘块的数据，操作系统仅需在FAT表中找到两个值为-2的表项，并将对应的盘块分给进程即可。

相较于隐式链接，显式链接支持直接访问文件中/末尾的盘块，不再需要依次从头遍历文件。并且FAT表在系统启动时便被载入内存，可以显著提升查找/存取性能。唯一不好的是，在磁盘越大的时候，FAT表也越大，会带来内存开销。

3. 索引分配

但实际上，我们通常只会同时使用硬盘的很小一部分。没有人会同时打开4TB的文件放在屏幕上处理。所以，我们可以优化一下FAT的思路——仅把打开的文件编号调入内存。这就是索引分配的思想。

1) 单级索引分配

系统给每个文件分配一个专用的索引块（或索引表），并将文件的所有盘号记录在表中。在需要访问文件时，先将索引表调入内存，随后根据索引表中记录的盘号寻找文件的盘块。

^{紫色表示存放索引表的盘块（索引块）}

和FAT相比，我们不再需要把整个磁盘的所有盘块都放在一张表中，显著减少了内存开销。并且它和FAT一样支持随机存取、没有外部碎片。但缺点也和FAT表类似，存储的文件占用盘块越多，我们就需要越多的索引表项，也就是索引表的大小会随着文件增大，虽然可以通过链接将多个索引表串在一起，这样却会回退到类似隐式链接，读取效率低下。相反，如果文件很小，只占几个盘块，这时索引表的大小可能只有十几字节，但操作系统仍会给文件分配一个完整的索引块，导致利用率不高。

2) 多级索引

我们说计算机的本质是套娃，既然大文件的索引块太多，我们可以建立索引块的索引表！

^{二级索引分配}

类似内存管理中的多级页表，访问数据时，我们先查询主索引，找到盘块所属的范围后，去查询下一级的索引表，直到获取到准确的盘块号，并从磁盘中取出该盘块。

假设一个盘块大小事4KB，一个盘块号是4B，那么一个索引块可以容纳1024个盘块号。如果是2级索引的话，支持的最大文件大小就是$1024^2\times4KB=4GB$。

采用多级索引可以显著提升文件的查找效率，但随之而来的是，为了拿到一个盘块要进行的磁盘I/O次数增多，对于小文件来说查找效率明显降低，如果系统中有很多小文件需要访问，查找效率反而不如单级索引。

3) 混合索引

我们说计算机总是折中的，为了兼顾大文件和小文件，我们可以同时使用单级索引和多级索引，并根据需要选择最合适的分配策略。

UNIX系统的inode(索引节点index node)就是一个很好的例子。

^{inode示例图}

inode中一共有13个地址项，其中前10个为直接块，后3个分别为一级、二级、三级索引地址。如果每个盘块为4KB，那么在文件不超过40KB的情况下可以直接从索引节点取出全部盘号。在四种索引方式全部使用的情况下，inode最大可表示的文件长度为$4KB\times(10+1024+1024^2+1024^3)=40KB+4MB+4GB+4TB$。

二、目录

在我们实际使用计算机的时候，我们不可能记住每个文件索引节点的盘号（天啊那简直是超人），经常用电脑的朋友肯定知道，我们会给文件命名，放在电脑中，每次访问文件时仅需找到对应文件名的文件打开即可。

^{我电脑的家目录}

0. 目录文件

在操作系统中，“目录”本身也是一个特殊的文件。它存放的是目录内的文件结构。

1. 文件控制块

那么，为了方便管理文件，我们引入FCB(File Control Block)这一数据结构。

类似于内存中的进程控制块PCB，FCB用于存放控制文件所需要的信息，通过FCB我们可以实现对文件的按名存取。每个文件对应一个FCB，所有FCB的集合构成目录文件。

FCB中主要包含：

• 基本信息：文件名、物理位置等
• 存取控制信息：文件主、用户访问权限
• 使用信息：创建、修改时间等

^{文件的详细信息}

• 对于连续分配的文件系统，FCB会记录文件起始块的块号及占用的总块数
• 对于隐式链接分配，会记录指向文件第一块和最后一块的指针
• 显式链接仅需记录文件的起始块号

2. 索引节点

FCB吗？那其实是老掉牙的东西了。想想，当你的电脑中有海量学习资料的时候，FCB会变得巨大，而查找文件时系统需要逐个盘块读入目录项，检索性能大幅下降。

人们给出的解决办法是：将文件名和文件基本信息分开来存储，文件目录中每一项有一个指针指向基本信息所在盘块。检索文件时仅需把文件名和对应指针调入内存，这大大降低了目录文件体积，减少了磁盘I/O次数。

UNIX系统就如同之前提到的，使用inode存放文件的基本信息，而目录文件中只放文件名和索引节点的编号。当系统要访问一个文件时，可根据对应的inode将文件数据调入内存。为了实现持久存储和高效访问，文件系统中有两种索引节点。

1) 磁盘索引节点

顾名思义，它存储在磁盘中。每个文件都有唯一的磁盘索引节点。

类型	注释
文件主标识符	标识文件所属的用户或用户组
文件类型	指明是普通文件、目录文件还是一些特殊文件
文件存取权限	规定文件主、核准用户及一般用户的访问权限
文件物理地址	通过13个地址项获取记录所在盘块编号
文件长度	以字节为单位，表示文件实际大小
文件链接计数	统计文件系统中有多少个硬链接指向该文件
文件存取时间	文件被访问/修改的时间、inode修改时间

硬链接：将两个文件目录项指向一个inode，实现文件共享，详细会在后面讲解。

2) 内存索引节点

当文件被打开时，操作系统将对应的磁盘索引节点调入内存，并且附加一些运行时状态信息。因此，在磁盘索引节点的基础上，额外新增了：

类型	注释
索引节点号	用于在内存中唯一标识该节点
状态	标识inode是否上锁/修改
访问计数	有多少个进程在访问节点，只有访问计数为0才可释放节点
逻辑设备号	标识文件所属文件系统的逻辑设备号，用于多文件系统环境
链接指针	指向空闲链表与散列队列，用于内核调度与回收

3. 目录结构

当下操作系统普遍采用树形目录结构。

^{某一目录的结构图}

使用如macOS或Linux等系统等朋友应该很熟悉。在树形结构中，用户通过文件路径名来表示文件。文件路径分为绝对路径和相对路径，绝对路径指的是从根目录开始的路径，如/Users/cloverta/Projects/cellpose-web/backend/config.yaml，而相对路径则是从用户当前所在的目录开始的路径，假设用户此时在cellpose-web目录中，则该文件的相对路径是backend/config.yaml。

系统中每一个文件具有唯一的绝对路径。UNIX系统规定由/开头的路径为绝对路径，/代表根目录。

三、文件共享

文件共享允许多个用户访问同一个文件，但是系统中仅保存一个副本。

1) 软链接（符号链接）

大家最熟悉的应该就是软链接了，为什么呢？我们每天都在使用的Windows“快捷方式”功能就属于软链接。

在软链接时，系统会创建一个LINK类型的新文件，其中仅包含被链接文件的路径名。当用户访问该文件时，操作系统会识别出它是LINK类型文件，便会根据文件中记录的路径名逐级查找，在查找到目标文件后对其进行读写操作。

在符号连接中，只有文件所在目录拥有指向其索引节点的指针，其他共享目录仅保存该文件的路径名。当原文件被删除后，其他目录中仍能看见共享文件，但当用户尝试通过符号链接访问文件时，系统会返回访问失败。删除符号链接不会影响原文件的索引节点。

由于系统会沿着目录遍历，可能会涉及多次磁盘存取，从而增加访问开销，并且符号链接本身也是一个独立文件，它和它的索引节点同样占用一定的磁盘空间。

如果是通过网络实现符号链接共享，之需要记录文件所在机器的网络地址和文件路径。

2) 硬链接

硬链接基于索引节点，也就是B目录的目录项直接指向文件的inode。

当A目录需要删除文件时，系统并不会立即删除其物理文件，而是会首先将count计数器减1，在计数器减为0的时候才能删除文件。换言之，只要计数器大于0，则系统就不会释放文件及其索引节点。

四、文件操作

我想，99%的人打开操作系统都是为了（登陆一些用户）（点击一些光标）（操作一些文件），接下来我们就要来探讨操作系统是如何操作文件的。

1.文件的打开与关闭

这里指的打开与关闭并非我们双击打开文件，而是指进程进行的open()与close()系统调用。

1) 打开文件

如果用户要对某个文件连续进行多次读/写操作，如果每次都需要从头开始检索目录，未免效率也太差。为了避免重复查找，大多数操作系统规定：用户首次访问文件时，必须先通过open()系统调用将其打开。

系统在内存中维护一个打开文件表，用于记录当前活跃信息。打开表一般分两级：

• 系统打开文件表：全局共享。存储一些与进程无关，与文件相关的内容。如文件在磁盘中的位置、文件大小、访问时间等。系统打开表中每项包含一个打开计数器，记录有多少进程打开了该文件。
• 进程打开文件表：单个进程独有。记录进程私有的访问状态，如读/写指针、访问权限、文件打开方式等。该表中每一项均指向系统打开表的对应项。

打开操作也就是指，系统根据文件路径定位到目录项后，将关键信息载入内存，在打开表中创建一个表目，并将该表目的索引号（fd）返回给用户。具体操作如下：

1. 进程发出系统调用：进程执行 open()，向操作系统提供文件路径、打开方式等信息。
2. 查找目录：操作系统沿着进程提供的路径逐级查找，找到对应的FCB或inode。如果inode不在内存中，则需从磁盘读入。
3. 检查权限：检查文件（或路径）是否存在，用户是否有访问权限，打开方式是否合法。
4. 建立打开文件表项：先后创建该文件在系统打开文件表和进程打开文件表中的表项。如果系统打开表的表项已存在，则将其打开计数加1。
5. 返回文件描述符fd：向进程返回一个描述符（File Discriptor），用于标识该打开的文件

此后用户再次操作该文件时，仅需提供文件描述符，那么系统就能直接从内存中获取需要的信息。

^{用户通过两级打开表读文件}

2) 关闭文件

进程调用close()系统调用关闭文件。操作系统随后从该进程的打开文件表中删除对应项，并将系统打开表中相应项的打开计数器减1。

若计数器减至0，代表没有进程在使用文件，此时可以删除其在系统打开表的项，并释放占用资源。

文件名不是打开文件表的组成部分，比较当进程打开文件后，后续操作均通过索引号完成。

2. 文件基本操作

从直觉上来讲，我们对文件要做的事情无非就是：创建文件、删除文件、读文件、写文件。

1) 创建文件

创建文件的大体思路是：检验、分配、预留、注册。

1. 合法性与权限校验：操作系统首先会检查文件名是否合法（如文件名中有没有/），是否与同目录下已有文件重名。随后验证用户对目标目录是否有写权限。如果有任意一条不满足，则终止文件创建。
2. 分配索引节点：从空闲inode池中分配一个空闲项并初始化元数据，包括文件类型、初始大小、访问权限、时间戳、物理块指针等。同时将该inode标记为已占用。
3. 分配磁盘块：根据文件预估大小，从空闲磁盘块管理结构中分配相应数量的物理块，并将块地址记录在inode中。
4. 更新文件系统元数据：inode表、空闲磁盘块结构、目录大小等
5. 打开并返回描述符：如果创建后立即打开，则会执行文件打开相应操作。

2) 删除文件

删除思路为：撤销、回收、释放。

1. 路径解析定位：操作系统按照路径名在文件树中逐级查找，在定位到目标文件的目录项后，根据目录项中的inode编号获取该文件的inode，并验证用户对文件所在目录的写权限。
2. 检查使用状态和硬链接计数：在部分操作系统中，若文件正被打开，会延迟物理删除。若硬链接计数大于1，则仅删去当前目录项，并将文件链接计数减1。
3. 移除目录中的目录项：这样用户在目录中就看不到文件了，完成逻辑删除。
4. 释放索引节点：如果文件链接计数降至0，将inode标记为空闲，并归还至空闲管理机构
5. 释放磁盘块：根据inode中的块指针，将所有数据块和索引块归还空闲磁盘管理机构
6. 释放内存临时资源：包括缓冲区，打开文件表项、内核文件对象等
7. 更新文件系统元数据

3) 读文件

操作流程可参考前面的图。首先通过文件名查找对应目录项，获取索引节点号。通过两级打开表定位文件在外存的数据块。随后根据读指针的位置从指定块中读取数据，并更新读指针。

4) 写文件

和读指针类似，通过打开表定位数据块后，根据写指针的位置将数据写入相应块，并更新写指针。若超出当前分配空间，系统会动态分配新的磁盘块，并更新inode中的指针。

五、文件保护

如果家里人略懂些电脑，想必小时候一定有过为了偷玩电脑和家里人斗智斗勇的经历。那么，为了防止小孩误食，操作系统需要对文件提供保护。

1. 内容保护

当你想分享一个学习资料给其他用户，但又不想部分人知道，最简单的方法是通过口令保护。这种方法是用户在创建文件时设定一个口令，系统将口令存入FCB，用户访问时需要提供正确的口令。这种方法开销小，但是文件本身并未加密，只能说防君子不防小人。

于是更常见的是使用加密保护，在访问时需要使用密钥进行解密。一个最简单的例子就是将文件二进制数据和密钥的二进制码进行逐位取反。这种方法不占用额外空间，但是加解密过程会有一定计算开销。

2. 访问控制

设想你亲戚家的熊孩子来借你的电脑玩，而他刚刚从某音符站得知删除C:\Windows\System32\下的所有文件就可以破解米哈游的抽卡概率！怎么办，你的电脑危在旦夕！

操作系统为你提供了访问控制方法，你可以精细地管理用户对文件的访问权限。

实现访问控制最常用的方法是基于用户身份进行权限管理。最普遍的机制是为每个文件和目录附加一个访问控制列表（Access-Control List, ASL），在其中指定用户名及被允许的访问类型。

精简的ACL通常将用户划为以下三类：

• 拥有者：创建文件的用户
• 组：一组需要共享该文件且有相似访问需求的用户
• 其他：不是拥有者也不在组内的其他用户

用户类型	读取	写入	删除	执行
拥有者	1	1	1	1
组	1	0	0	1
其他	0	0	0	0

当一个用户尝试访问文件时，系统会按照上述表中的优先级顺序匹配身份，当匹配到身份后便不会再匹配下一组。例如，如果你把熊孩子的用户放在“组”中，则系统会：

1. 匹配用户是否为拥有者：否，匹配下一项。
2. 匹配是否为组内成员：是，用户可以读、执行，但不可以写、删除。
3. 由于上一项匹配成功，“其他”类型匹配略过。