首页OS

文件管理

Everything is a file

文件是存储在计算机持久性存储设备的信息集合。用户进行IO操作时，文件是逻辑操作的基本对象，而文件系统是操作系统面向用户的文件管理系统。

文件的定义与属性

文件是具有文件名的一组相关元素的集合，分为有结构文件与无结构文件。

  • 有结构文件由若干个格式相似的记录组成。而记录是一组相关数据项的组合，用于描述一个对象某一方面的完整属性。

  • 无结构文件则是连续的字节流，比如二进制文件或者普通文本文件。因此也称为流式文件。例如.lib、.dll、.o文件这样的已编译后的二进制文件，需要通过读/写指针的方式定位下一个操作的字节。进行特定区域的检索只能通过顺序查找，效率较低。

对于有结构文件，其由多个记录组成，因此称为记录式文件。根据记录的长度是否一致可以分为

  • 定长记录 -- 所有记录的长度相同，且各数据项在记录中的位置相对固定，系统可以直接通过偏移量定位记录。
  • 变长记录 -- 记录长度不一或者数据长度不一，只能通过顺序查找相应记录，速度较慢

有结构文件根据记录组织方式分为

  • 顺序文件
  • 索引文件
  • 索引顺序文件
  • 直接文件(散列文件)

顺序文件的记录按线性排列，可分为串结构与顺序结构。串结构的记录是时间先后顺序排列的，因此只能顺序扫描，效率低；而顺序结构的记录按键字排列，能通过偏移量直接定位记录。

类似于磁带这样物理限制的硬件，只能存储与使用顺序文件。

索引文件通常用于进行数据随机查询等任务。索引文件维护了一个索引表，索引表中包含了：索引号、文件长度于指针，指针指向相应的逻辑文件，但是逻辑文件对象是什么层度地址取决于程序员的逻辑。

|索引号idx|长度m|指针ptr|

对于定长记录，第 ii 条记录的首址是简单的 Ai=iLA_i = iL, 对于变长记录，第ii 条记录的首址是前序记录的后继

Ai=∑k=1iAk+1A_i = \sum_{k=1}^i A_k +1

索引顺序文件

将索引文件与顺序文件相结合。分组的组间通过索引建立，可以无序；但是组内通过顺序文件构成，需要键字有序才能进行偏移量定位。

索引顺序文件的查找逻辑和查找 中的分块查找相同。

对于NN条记录的普通顺序文件的普通顺序文件的查找需要 N2\frac{N}{2} 次。 分块最优查找下，假设分为MM块，则需要在块间和块内进行顺序查找，总共需要

M2+N2M≥2M2⋅N2M=N\frac{M}{2}+\frac{N}{2M}\geq 2\sqrt{\frac{M}{2}\cdot\frac{N}{2M}} = \sqrt{N}

当 M=NM = \sqrt{N} 时，查找效率最优

散列文件 通过Hash函数进行文件索引

文件的属性

文件的属性包括

  • 名称
  • 类型
  • 创建者
  • 所有者
  • 位置
  • 大小
  • 保护
  • 创建时间

文件系统结构

根据与硬件系统交互的自下至上的结构可分为

  • IO控制 -- 负责磁盘与内存交互，将磁盘文件写入写出内存，并实现IO与操作系统的交互
  • 基本文件系统 -- 负责读写磁盘中的物理块
  • 文件组织模块 -- 负责文件逻辑与物理块直接的映射
  • 逻辑文件系统 -- 负责管理文件系统的元数据，维护目录结构，不含有实际数据的内容。

文件目录

文件目录管理的目的是实现:

  • 按名存取
  • 提高检索速度
  • 支持文件共享 -- 允许多用户访问同一目录下的文件
  • 允许文件重名 -- 不同子目录下的文件可重名

文件控制块FCB

和PCB刻画进程信息类似，FCB用于确定文件的相关信息。FCB包含的信息有

  • 文件的基本信息 -- 文件名，物理地址、逻辑结构等
  • 存储控制信息 -- 访问权限等
  • 使用信息 -- 创建时间与最后修改时间等

为了避免在检索文件时将整个FCB全部调入内存，UNIX系统中将文件名和描述信息解耦，将文件描述信息组织位索引结点(inode)。通常inode就是FCB，在文件目录的目录项中，对应索引结点编号指向对应的inode，文件目录表建立的是文件名和索引节点编号的映射

|文件名|索引节点编号|

目录项大小相比FCB减小，每个盘块可以容纳更多的目录项，因此单次搜索可以降低平均磁盘启动的次数。

索引节点由两个部分构成，分别为磁盘索引节点与内存索引节点

磁盘索引节点是文件的相关信息，包括文件标识符、文件类型、权限、地址、长度等信息。文件加载进内存后，相应的内存索引节点则相比磁盘索引节点多了运行时信息，包括索引节点号、状态、访问计数器、链接指针等。

文件目录的结构

文件目录分为

  • 单级目录
  • 两级目录
  • 树形目录
  • 有向无环图目录

单级目录将FCB线性排列，满足了基本的按名存取的需求，但是其无法实现文件重名存储且查找效率低，文件无法共享。

两级目录分为主文件目录(MFD)和用户文件目录(UFD)，满足了多用户的需求，主文件目录下放置多个文件名和用户目录的存储位置, 用户目录下放置用户私有文件。

用户文件目录内是单级目录排列的，因此灵活性与查找效率仍然较差。

树状目录是现代的文件目录结构，从根结点/出发，到若干个子目录。用户的专有目录在/usr/*

树状目录的路径分为绝对路径与相对路径。绝对路径就是从根结点出发的完整路径，比如/var/root. 相对路径则是从进程当前路径为基准，其他文件的路径。比如这篇文章的相对路径为./source/_posts/OS/文件管理.md

有向无环图的目录结构的形成逻辑和图 中的m叉树和DAG的转换相同，即将目录间共享的文件作为共同结点商去，就构成了有向无环图。但是有向无环图的目录结构带来了更复杂的文件用户权限管理和文件增删的逻辑，增加了管理的开销。

文件目录的实现

文件目录基于 线性列表/哈希表 实现

  • 线性列表 通过线性表管理文件名与数据块指针，但是查找效率较低，时间复杂度为 O(n)\mathcal{O}(n)
  • 哈希表 查找效率高但是存在Hash冲突，且目录查询依赖磁盘IO，需要动态加载活跃的目录进内存以提高响应速度。

文件目录的操作

和日常使用计算机相同，文件目录的操作包含

  • 搜索文件
  • 创建/删除文件
  • 创建/删除目录
  • 移动/显示/改变目录

文件的物理结构

文件的物理结构是指操作系统中抽象的文件对象与磁盘中的存储块之间的对应方式。

文件的物理结构分为两个互补的核心部分

  • 文件分配方式 -- 管理已使用的磁盘非空闲块
  • 文件存储空间管理方式 -- 管理未使用的磁盘空闲块

连续分配方式

根据磁盘连续的存储块进行分配。比如文件长度为nn块，从第bb块开始存放，则分配给该文件的块就是 b,b+1,⋯ ,b+n−1b,b+1,\cdots , b+n-1

连续分配方式可以在 O(1)\mathcal{O}(1) 时间内读取指定块，但是它和内存连续分配类似，可能产生大量的外部碎片。文件长度也需要预先知道，难以支持文件大小的动态拓展。

和线性表插入的问题相同，对于连续分配方式的文件，需要增删新的文件需要整体移动文件，性能开销大。

链接分配方式

隐式链接

磁盘块内存储指向下一个磁盘块的指针，用户无法管理内部指针。当磁盘块链断开时，后续磁盘块内的数据都无法访问。

磁盘块能合并为簇对象，减少了指针存储的开销。簇内的块是连续分配的块，而簇间的指针序仍然存在。

显式链接

显式链接会维护一张文件分配表(FAT), 其在整个文件系统只有一张。FAT记录盘块的盘块号与其指向的下一个块的盘块号。这其实就是盘块的静态链表结构。

FAT需要始终加载在内存中，内存开销较大，但是支持顺序访问也支持随机访问，性能效率高。

索引分配

索引表相当于将单个文件分配的硬盘块使用一个表进行维护，访问文件时只需要根据索引表的内容加载硬盘块。

如果文件过大可以使用多级索引表进行硬盘块的索引。类似于 内存管理 中关于多级页表的形式，多级索引表也是将块号进行离散分表映射以节省存储开销。但是相应会增加磁盘IO的开销。

混合索引方式

混合索引方式则是对于大文件与小文件使用不同的文件索引方式。inode结构中可以存入多个直接块以及若干层索引间址，对应多级索引的管理方式。这样对于不同大小的文件使用不同的索引方式可以降低整体的性能开销。

文件的操作

文件的基本操作包括创建文件、删除文件、读/写文件

创建文件的过程包括

  • 文件名合法检验和权限检验
  • 分配inode并创建inode中的信息
  • 分配磁盘块
  • 建立目录项
  • 更新文件系统的元数据

删除文件的过程包括

  • 定位删除文件，按路径名检索文件目录找到目录项并获得inode
  • 检查使用状态、硬链接计数， 如果文件被打开，则延迟删除(Windows 系统会直接终止删除，Linux/Macos会等待文件关闭后完全删除)；如果硬链接计数大于1则不回收inode和磁盘块
  • 移除目录项
  • 释放inode、磁盘块与内存资源 -- 内存临时资源的释放要晚于磁盘信息的释放
  • 更新文件系统元数据

读文件与写文件前都需要将文件从磁盘加载入内存中，这个过程称为打开文件，对应open()系统调用(这个操作会切换用户态至内核态，因为设计磁盘IO操作)

打开文件的实现为：通过目录找到inode, 并根据inode维护一个打开文件表，用于记录当前活跃的文件信息。

打开文件表有两层

  • 系统打开文件表 -- 全局活跃的文件属性，每一个项中有一个打开计数器，用于记录多少进程打开了这个文件
  • 进程打开文件表 -- 进程独有的打开文件表，用于记录私有文件的打开状态

读文件的过程: 打开文件，如果文件不在内存中就将文件磁盘块加载进内存并更新读指针

写文件的过程: 打开文件，如果文件不在内存中就将文件磁盘块加载进内存并更新写指针

文件关闭时，通过系统调用close()关闭文件。对应的打开计数器减1，当计数器减到0，就释放打开文件表中关于这个文件的项并释放相关资源。

文件加载入内存后，包含额外的信息有

  • 文件指针 -- 在打开文件表中，多个进程对文件多开的时候需要在打开文件表中维护多个文件指针，这是在文件在内存中的指针
  • 文件打开计数 -- 内存inode会管理多少个打开文件项使用了这个inode； 打开文件表会管理多少个进程打开了这个inode
  • 文件磁盘位置 -- 在内存inode中
  • 访问权限 -- 在内存inode中

总结: 内存inode的信息是对于磁盘文件在内存的对象的信息管理；打开文件表是进程面/文件多开场景下的信息管理

文件的共享

文件的共享分为两个视角:

  • 用户对文件的共享
  • 进程对文件的共享

进程对于文件共享管理的方式就是打开文件表以及相应的打开计数器与指针的管理

用户侧的共享分为硬链接与软链接

硬链接是基于索引结点的共享方式。文件加载进内存后，文件的物理地址与属性信息加载在内存inode中，用户目录项只维护文件名与指向inode的指针。

文件内存inode维护了一个链接计数count，用于标记指向该文件的用户文件表个数。当用户A不再使用该文件时，将count减1，并删除A私有文件表中的目录项，只有当count等于0才真正从内存中释放该文件与inode。

软链接是Namespace层面的链接，对于形成软链接的文件，分配一个Link类型的文件，里面只存储文件实际目录的字符串，直接存储在inode中。

当原始文件被删除时，不会影响另外一个用户访问Link文件本身，但是会出现访问失败的错误。同时，软链接建立的只是文件目录的映射而不是指针的映射，所以并不会改变原始文件内存inode的链接计数器

文件保护

文件保护机制包括

  • 口令保护
  • 加密保护
  • 访问控制

口令与加密防止其他用户的非法获取文件内容，访问控制用于管理用户对文件的权限。

Linux/Macos中的chmod实现了对于三种用户类型的文件访问权限控制的方式。这是一种访问控制列表(Access-Control List,ACL)控制方式

  • u -- file owner
  • g -- group users
  • o -- other users

对于三种权限进行赋权:

  • r -- read
  • w -- write
  • x -- execute

使用三位十进制数转二进制权限，每一个十进制位代表user类型，比如chmod 712 <file> 表示file user 具有rwx(111)， group users具有x(001), other users具有w(010)

文件系统

文件系统是整体文件管理逻辑在硬盘与IO侧的实现。

FS -- 文件系统

File System 是在硬盘中真实管理硬盘的系统。硬盘通常被划分为若干个分区，每一个分区包括一个FS用于管理分区内的块信息。

FS的构成可以分为

  • 主引导部分(MBR) -- 位于磁盘的0号分区，经由BIOS加载进内存并执行用于识别活动分区并读取分区的第一个扇区 -- 引导块
  • 引导块 -- 分区的引导部分，也是分区的，用于加载当前分区的操作系统的文件部分。
  • 超级块(Super Block) -- 包含分区的全局信息，比如分区的总分块、块大小、空闲块数量和指针、空闲i节点数量和指针
  • 空闲块信息

对于不同品牌/设别类型的外存，文件系统不尽相同，存在如ext4/NTFS/FAT等类型。

操作系统在内存中维护与VS相关的信息：

  • 内存中的挂载表 -- 挂载文件系统分区的信息，包括设备标识、挂载点与文件系统类型等
  • 内存中的目录表缓存 -- 根据局部性原理缓存最近访问的目录内容，减少磁盘的读取
  • 系统级打开文件表
  • 进程级打开文件表

这些内存中信息在文件系统挂载时加载，在文件打开且运行时更新，卸载时释放。

文件存储空间管理

文件存储空间管理是面向磁盘空闲块的管理方式。

空闲表法 和磁盘块分配中的连续分配方式类似，都是基于磁盘的连续磁盘空间进行分配。FS维护了一张空闲表用于记录空闲块的序号、起始盘块号、空闲盘块数等。

空闲链表法 使用一个链表链接所有空闲盘区组织

空闲链表法的基本单位可以是盘块/盘区，和簇结构类似，空闲盘区链就是将一块块连续空闲盘块区域使用链表链接，满足区内连续，区间链表序的关系。

成组链接法
通过分组方法进一步拓展了空闲链表法的指示空间。通过每一组的第一个盘块作为索引块记录下一组的空闲表块的块号与数目。

这是经典的离散映射拓展指示空间的方式，第一级空闲表块信息被加载到专门的内存栈中，称为空闲盘块号栈，通过盘块栈弹出表示顺序分配空闲盘块。

位示图法

通过一个二维二进制表维护磁盘盘块的使用情况。

{ai,j=0(i,j)盘块空闲ai,j=1(i,j)盘块正在使用\begin{dcases} a_{i,j} = 0 & \text{(i,j)盘块空闲}\\ a_{i,j} = 1 & \text{(i,j)盘块正在使用} \end{dcases}

盘块的序号是横向顺序数下去的，因此对于一个m×nm\times n 的位示图表，坐标为(i,j)(i,j) 的磁盘块的盘块号为

b=m(i−1)+jb = m(i - 1)+j

盘块的回收则是根据盘块值反解二维坐标的过程。即

{i=⌈bm⌉j=(b−1)%m++1\begin{dcases} i = \left\lceil\frac{b}{m}\right\rceil \\ j = (b-1) \% m ++1 \end{dcases}

VFS -- 虚拟文件系统

VFS 是 操作系统层与FS的中间层。由于现代操作系统会面对多种不同的FS，VFS统一化了面向操作系统的API，以保证系统能更加统一化的IO。

VFS存在四种基础对象

  • 超级块 -- 与FS中的超级块对象相对应。当文件系统挂载时，将超级块加载入内存
  • Vnode -- vnode与每一个FS下的inode相对应，本质是对各个FS的元数据进行封装，通过指针索引FS中的私有元数据并向上暴露给OS。这体现了封装的同一性理念
  • 目录表对象与文件对象

文件系统的挂载

Windows 的单个盘，比如C:\表示分区/卷，比如可以在一个机械硬盘中进行多个分区
disk

每一个卷作为独立的根目录 ，OS根据相应的驱动器定位对应的文件系统，再从其目录中查找

Unix以单一根目录为挂载点进行挂载，挂载点只能挂载单一设备，但是同一个设备可以使用多个挂载点。

WSL中的挂载

(base) asuna@Asuna:~$ df -h
Filesystem      Size  Used Avail Use% Mounted on
none            3.9G     0  3.9G   0% /usr/lib/modules/6.6.114.1-microsoft-standard-WSL2
none            3.9G  4.0K  3.9G   1% /mnt/wsl
drivers         201G  198G  3.0G  99% /usr/lib/wsl/drivers
/dev/sdd       1007G   71G  885G   8% /
none            3.9G   84K  3.9G   1% /mnt/wslg
none            3.9G     0  3.9G   0% /usr/lib/wsl/lib
rootfs          3.9G  2.7M  3.9G   1% /init
none            3.9G  604K  3.9G   1% /run
none            3.9G     0  3.9G   0% /run/lock
none            3.9G     0  3.9G   0% /run/shm
none            3.9G   76K  3.9G   1% /mnt/wslg/versions.txt
none            3.9G   76K  3.9G   1% /mnt/wslg/doc
C:\             201G  198G  3.0G  99% /mnt/c
D:\             753G  626G  128G  84% /mnt/d
E:\             954G  837G  118G  88% /mnt/e
tmpfs           781M   20K  781M   1% /run/user/1000

WSL 可以访问宿主Windows机器的卷，挂载在/mnt/*上，因此也可以查看宿主机的硬盘挂载情况

Macos的挂载方式与Linux类似
mount