文件系统

前言

很久没写博客了,之前因为实习就没那个心思去写了,后面因为要准备期末考又拖了很长一段时间,等到考完发现自己主题版本太落后,于是重新更新了一次主题,再加上自己好久没怎么看八股文了,加上考完想休息一下,接下来全力准备秋招,所以自己摆烂了一段时间,现在重新“提笔”落座,重新开始写一些文章来巩固知识点,早早开始为秋招做准备。

文件系统

在Linux下面,有一句话叫做一切皆为文件,就连块设备,管道和Socket也都是文件,那么自然就会有一个文件系统来管理这些文件,其实不光是在Linux下会有这么一个系统,只要是操作系统都需要这么一个系统来帮助用户管理文件,因为大家都知道,我们所有的文件,想要永久存在,就会储存在磁盘上,那么,如何将用户创建的文件或者想要存储的数据存在磁盘上呢?我们用户肯定没办法去在磁盘上动手脚,所以只能依靠操作系统来实现,那么这就需要文件系统了,我们还是用Linux下的文件系统来讲解

Linux下的文件系统

文件系统下的基本单位是文件,它的目的是对磁盘上的文件进行组织管理,那组织的方式不同,就会形成不同的文件系统。

Linux文件系统会为其每个文件分配两个数据结构:索引节点和目录项,主要是用来记录文件的基本信息和目录层次结构

索引节点

1.索引节点(inode),用来记录文件的基本信息,例如inode编号,文件的大小,访问权限,创建时间,修改时间等等,最重要的是数据在磁盘的位置。
2.索引节点同样会被存放在磁盘中,所以也会占用磁盘空间。
每个文件的索引节点都是唯一对应的,也就是说索引是文件的唯一标识符

目录项

1.目录项(dentry),用来记录文件的名字,索引结点指针(指向索引节点在磁盘中的地址),其他目录项的层级关联关系
2.多个目录项关联起来,就会形成目录结构
3.目录项不存放在磁盘中,而是由内核维护的一个数据结构,缓存放内存中

因为目录项记录的文件的名字,而索引节点唯一标识一个文件,所以目录项和索引节点的关系就是多对一,就是说可以有多个目录项中的指向索引节点的指针指向同一个索引节点,也就是说一个文件可以有多个别名

Linux中的硬链接就是通过该关系来实现的,通过硬链接创建的文件,其目录项中指向索引节点的指针与源文件的目录项中是一样的,所以可以指向同一个索引节点,从而指向同一块磁盘上的数据

硬链接和软链接

目录项和索引节点的关系

索引节点存储在磁盘上,而为了提高磁盘读写效率,加速文件的访问,通常会将索引节点加载到内存中

如图所示,磁盘上分为3块区域,分别为:
1.超级块:用于存储文件系统的详细信息,例如块的个数,块的大小和空闲的块等等
2.索引节点区:用来存储索引节点
3.数据区:用来存储文件或者目录数据

我们不可能把超级块和索引节点区全部加载到内存,这样内存肯定撑不住,所以只有当需要使用的时候,才将其加载进内存,它们加载进内存的时机是不同的:
1.超级块:当文件系统挂载时进入内存
2.索引节点区:当文件被访问时进入内存

目录项和目录的关系

目录项和目录虽然只有一字之差,但是它们并不是一个东西,目录是个文件,持久化存储在磁盘中,而目录项是一个数据结构,由内核进行维护,缓存在内存中

如果查询目录频繁从磁盘读,效率会很低,所以内核会把已经读过的目录用目录项这个数据结构缓存在内存,下次再次读到相同的目录时,只需从内存读就可以,大大提高了文件系统的效率

目录项这个数据结构不只是表示目录,也是可以表示文件

文件是如何存储在磁盘中的?

磁盘读写的最小单位为扇区,大小只有512B,如果一次只能读取一个扇区的数据的话,效率太低了,所以文件系统就把多个扇区组合成一个逻辑块,所以每次读写的最小单位就为一个逻辑块,大小大概为4KB,也就是8个扇区,这样就提高了磁盘的读写效率

虚拟文件系统

文件系统的种类众多,而操作系统希望对用户提供一个统一的接口,于是在用户层与文件系统层引入了中间层,这个中间层就称为虚拟文件系统(Virtual File System,VFS)

VFS 定义了一组所有文件系统都支持的数据结构和标准接口,这样程序员不需要了解文件系统的工作原理,只需要了解 VFS 提供的统一接口即可

在 Linux 文件系统中,用户空间、系统调用、虚拟文件系统、缓存、文件系统以及存储之间的关系如下图:

文件的使用

当我们用电脑打开一个文件的时候,我们有没有考虑过,如果文件中的数据是存储在磁盘中的话,当我们打开一个文件的时候,操作系统是如何对这个文件进行跟踪的呢？

在C++中,在程序方面,我们都是先用open()函数,打开一个文件,然后利用read()函数读取文件数据或者write()函数对文件进行写操作,进行玩这一切后,调用close()函数关闭文件。

如果知道open()函数的返回值是一个叫做文件描述符的东西,就很容易理解了。

当我们打开一个文件的时候,操作系统会跟踪所有打开的文件,而所谓的跟踪,其实就是给每个打开的文件分配一个文件描述符,而每个进程都会被分配一个打开文件表,文件表里的每一项就是一个文件描述符。

操作系统在打开文件表中维护着打开文件的状态和信息:

1. 文件指针:系统跟踪上次读写位置作为当前文件位置指针,这种指针对打开文件的某个进程来说是唯一的
2. 文件打开计数器:文件关闭时,操作系统必须重用其打开文件表条目,否则表内空间不够用。因为多个进程可能打开同一个文件,所以系统在删除打开文件条目之前,必须等待最后一个进程关闭文件,该计数器跟踪打开和关闭的数量,当该计数为 0 时,系统关闭文件,删除该条目
3. 文件磁盘位置:绝大多数文件操作都要求系统修改文件数据,该信息保存在内存中,以免每个操作都从磁盘中读取
   访问权限:每个进程打开文件都需要有一个访问模式(创建、只读、读写、添加等),该信息保存在进程的打开文件表中,以便操作系统能允许或拒绝之后的 I/O 请求

我们用户和操作系统所关心的东西是截然不同的,操作系统只会关系如何将文件数据和磁盘块对应起来,也就是如何将用户修改后的文件数据写入磁盘？在什么时候写入？
所以,用户和操作系统对文件的读写操作是有差异的,用户习惯以字节的方式读写文件,而操作系统则是以数据块来读写文件,那屏蔽掉这种差异的工作就是文件系统了。

读文件和写文件的过程

当用户进程从文件读取 1 个字节大小的数据时,文件系统则需要获取字节所在的数据块,再返回数据块对应的用户进程所需的数据部分。
当用户进程把 1 个字节大小的数据写进文件时,文件系统则找到需要写入数据的数据块的位置,然后修改数据块中对应的部分,最后再把数据块写回磁盘。
所以说,文件系统的基本操作单位是数据块。

文件数据如何存放在磁盘上的？

文件在磁盘上的存储方式,其实和程序在内存中的存放方式一样,分为两种:

1. 连续空间存放
2. 非连续空间存放
   1. 链式存放
   2. 索引存放

连续空间存放

顾名思义,就是存放的数据块在磁盘上的位置是连续的。

优势

磁盘的读取效率很高,因为磁盘的一次寻道就可以读取出整个文件。
前提是必须先知道一个文件的大小,这样文件系统才能根据文件大小在磁盘中找到合适的一块连续空间分配
所以,在文件头里指定起始块的地址以及文件大小,有这两个信息才能很好的表示文件存放在一块连续空间

劣势

• 磁盘空间碎片
• 文件长度不易拓展

如图所示,如果文件 B 被删除,磁盘上就留下一块空缺,这时,如果新来的文件小于其中的一个空缺,我们就可以将其放在相应空缺里。但如果该文件的大小大于所有的空缺,但却小于空缺大小之和,则虽然磁盘上有足够的空缺,但该文件还是不能存放。当然了,我们可以通过将现有文件进行挪动来腾出空间以容纳新的文件,但是这个在磁盘挪动文件是非常耗时,所以这种方式不太现实

其实和虚拟内存中,分段方式所出现的问题是一样的,关于虚拟内存的文章可以看我之前写的
内存管理

如果你知道在C++中,数组如果想要拓展的话是多麻烦,那么在文件系统的连续空间存放方式中,也是一样的麻烦,这里就不多说了

为了解决这些问题,就可以利用非连续空间存储

非连续空间存放

链式存放

如果知道链表在内存中是如何存放数据的话,那么链式存放其实也差不太多,所以链表就可以消除连续空间存放中磁盘空间碎片和不易拓展的劣势,因为在这种方式下,文件的长度是可以动态拓展的,而链表其实又分为两种:隐式链表和显式链表

• 隐式链表
• 显式链表

实现的方式是文件头要包含第一块和最后一块的位置,并且每个数据块里面留出一个指针空间,用来存放下一个数据块的位置,这样一个数据块连着一个数据块,从链头开始就可以顺着指针找到所有的数据块,所以存放的方式可以是不连续的

其缺陷就是:

1. 无法直接访问数据块,只能通过指针顺序访问文件,以及数据块指针消耗了一定的存储空间
2. 隐式链接分配的稳定性较差,系统在运行过程中由于软件或者硬件错误导致链表中的指针丢失或损坏,会导致文件数据的丢失*

显示链表就是取出每个磁盘块的指针,把它放在内存的一个表中,这样就可以解决隐式链表的两个不足,方法就是把用于链接文件各数据块的指针,显式地存放在内存的一张链接表中,该表在整个磁盘仅设置一张,每个表项中存放链接指针,指向下一个数据块号

举个栗子

对于显式链接的工作方式,我们举个例子,文件 A 依次使用了磁盘块 4、7、2、10 和 12 ,文件 B 依次使用了磁盘块 6、3、11 和 14 。利用下图中的表,可以从第 4 块开始,顺着链走到最后,找到文件 A 的全部磁盘块。同样,从第 6 块开始,顺着链走到最后,也能够找出文件 B 的全部磁盘块。最后,这两个链都以一个不属于有效磁盘编号的特殊标记(如 -1 )结束。内存中的这样一个表格称为文件分配表(File Allocation Table,FAT)。

当然了,这样做也有不足的:
当一个文件很大的时候,就需要创建一个很大的文件分配表,而文件分配表是存放在内存中的,所以这样做不适合应用于大文件

索引存放

链表的方式解决了连续分配的磁盘碎片和文件动态扩展的问题,但是不能有效支持直接访问(FAT除外),索引的方式可以解决这个问题。

索引的实现是为每个文件创建一个索引数据块,里面存放的是指向文件数据块的指针列表,说白了就像书的目录一样,要找哪个章节的内容,看目录查就可以。

另外,文件头需要包含指向索引数据块的指针,这样就可以通过文件头知道索引数据块的位置,再通过索引数据块里的索引信息找到对应的数据块。

创建文件时,索引块的所有指针都设为空。当首次写入第 i 块时,先从空闲空间中取得一个块,再将其地址写到索引块的第 i 个条目。

优点

1. 文件的创建、拓展、缩减很方便
2. 不会有碎片的问题
3. 支持顺序读写和随机读写

缺点

1. 由于索引数据块也是存放在磁盘块的,如果文件很小,明明只需一块就可以存放的下,但还是需要额外分配一块来存放索引数据,所以缺陷之一就是存储索引带来的开销。
2. 当文件很大的时候,一块索引数据块没办法一次性放下时,就需要通过别的方法来实现
   1. 链表+索引,这种组合称为链式索引块,它的实现方式是在索引数据块留出一个存放下一个索引数据块的指针,于是当一个索引数据块的索引信息用完了,就可以通过指针的方式,找到下一个索引数据块的信息。那这种方式也会出现前面提到的链表方式的问题,万一某个指针损坏了,后面的数据也就会无法读取了。
   2. 索引+索引,这种组合称为多级索引块,实现方式是通过一个索引块来存放多个索引数据块,一层套一层索引

空闲磁盘空间管理

前面说完了文件是如何在磁盘空间存放的,那么文件系统又是如何找出空闲磁盘空间用于存放文件数据呢？
其中又有3种方法:

1. 空闲表法
2. 空闲链表法
3. 位图法

空闲表法

空闲表法就是为所有空闲空间建立一张表,表内容包括空闲区的第一个块号和该空闲区的块个数,注意,这个方式是连续分配的。如下图:

当请求分配磁盘空间时,系统依次扫描空闲表里的内容,直到找到一个合适的空闲区域为止。当用户撤销一个文件时,系统回收文件空间。这时,也需顺序扫描空闲表,寻找一个空闲表条目并将释放空间的第一个物理块号及它占用的块数填到这个条目中。

这种方法仅当有少量的空闲区时才有较好的效果。因为,如果存储空间中有着大量的小的空闲区,则空闲表变得很大,这样查询效率会很低。另外,这种分配技术适用于建立连续文件。

空闲链表法

我们也可以使用链表的方式来管理空闲空间,每一个空闲块里有一个指针指向下一个空闲块,这样也能很方便的找到空闲块并管理起来。如下图:

当创建文件需要一块或几块时,就从链头上依次取下一块或几块。反之,当回收空间时,把这些空闲块依次接到链头上。
这种技术只要在主存中保存一个指针,令它指向第一个空闲块。其特点是简单,但不能随机访问,工作效率低,因为每当在链上增加或移动空闲块时需要做很多 I/O 操作,同时数据块的指针消耗了一定的存储空间。

空闲表法和空闲链表法都不适合用于大型文件系统,因为这会使空闲表或空闲链表太大。

位图法

位图是利用二进制的一位来表示磁盘中一个盘块的使用情况,磁盘上所有的盘块都有一个二进制位与之对应。

当值为0时,表示对应的盘块空闲,值为1时,表示对应的盘块已分配。

在 Linux 文件系统就采用了位图的方式来管理空闲空间,不仅用于数据空闲块的管理,还用于 inode 空闲块的管理,因为 inode 也是存储在磁盘的,自然也要有对其管理

文件系统的结构

用户在创建一个新文件时,Linux 内核会通过 inode 的位图找到空闲可用的 inode,并进行分配。要存储数据时,会通过块的位图找到空闲的块,并分配

但是!因为数据块的位图其实还是存放在磁盘块中的,我们算一下:
一个磁盘块是4KB,每一位代表一个数据块,所以可以表示4*024*8=2^15个空闲块,由于每个数据块也是在磁盘上,也为4KB,那么一个位图最多可以表示2^15*4*1024=2^27byte,也就是128M,也就是说,如果采用一个块的位图 + 一系列的块,外加一个块的 inode 的位图 + 一系列的 inode 的结构能表示的最大空间也就 128M,这太少了,现在很多文件都比这个大。

在 Linux 文件系统,把这个结构称为一个块组,那么有N多的块组,就能够表示N大的文件。

下图给出了 Linux Ext2 整个文件系统的结构和块组的内容,文件系统都由大量块组组成,在硬盘上相继排布:

最前面的第一个块是引导块,在系统启动时用于启用引导,接着后面就是一个一个连续的块组了,块组的内容如下:

1. 超级块,包含的是文件系统的重要信息,比如 inode 总个数、块总个数、每个块组的 inode 个数、每个块组的块个数等等。

2. 块组描述符,包含文件系统中各个块组的状态,比如块组中空闲块和 inode 的数目等,每个块组都包含了文件系统中所有块组的组描述符信息。

3. 数据位图和 inode 位图, 用于表示对应的数据块或 inode 是空闲的,还是被使用中。

4. inode 列表,包含了块组中所有的 inode,inode 用于保存文件系统中与各个文件和目录相关的所有元数据。

5. 数据块,包含文件的有用数据。
   你可以会发现每个块组里有很多重复的信息,比如超级块和块组描述符表,这两个都是全局信息,而且非常的重要,这么做是有两个原因:

6. 如果系统崩溃破坏了超级块或块组描述符,有关文件系统结构和内容的所有信息都会丢失。如果有冗余的副本,该信息是可能恢复的。

7. 通过使文件和管理数据尽可能接近,减少了磁头寻道和旋转,这可以提高文件系统的性能。

不过,Ext2 的后续版本采用了稀疏技术。该做法是,超级块和块组描述符表不再存储到文件系统的每个块组中,而是只写入到块组 0、块组 1 和其他 ID 可以表示为 3、 5、7 的幂的块组中。

结语

本文图片均来自小林Coding(https://xiaolincoding.com/os/6_file_system/file_system.html#%E6%96%87%E4%BB%B6%E7%B3%BB%E7%BB%9F%E7%9A%84%E7%BB%93%E6%9E%84 )
虽然本人是有样学样地将小林地这篇文章写了下来,好记忆不如烂笔头,每次写完都能学到很多