操作系统之文件管理

操作系统之文件管理，一切皆文件!!! (qq.com) (opens new window)

❝ 学习文件系统的时候主要从三个方面进行理解：1. 用什么方式记录、组织文件数据块? 2. 如何分配磁盘块？ 3.如何回收磁盘块 ❞

一、磁盘的结构

1、磁盘原理

• 上一篇讲操作系统内存管理的时候提到，内存和硬盘速度差距大的原因，如下：

• 内存速度比硬盘速度快的原理: 内存的速度之所以比硬盘的速度快（不是快一点，而是快很多），是因为它们的存储原理和读取方式不一样。

  • 硬盘是机械结构，通过磁头的转动读取数据。一般情况下台式机的硬盘为每分钟 7200 转，而笔记本的硬盘为每分钟 5400 转。

  • 而内存是没有机械结构的，内存是通过电存取数据的。

• 内存通过电存取数据，本质上就是因为 RAM 存储器是通过电存储数据的。但也正因为它们是通过电存储数据的，所以一旦断电数据就都丢失了。因此内存只是供数据暂时逗留的空间，而硬盘是永久的，断电后数据也不会消失。

• 磁记录原理，简单来说是磁表面存储器通过磁头和记录介质的相对运动完成读写操作。以读数据为例，磁表面存储器上面具有磁感线，但是磁感线的方向不一样，磁头相当于一个线圈，当他划过磁表面的时候，就有一个切割磁感线的运动，由于磁感线的方向在磁表面各个位置不同，因此当磁头划过的时候，就可以产生不同方向的电流，就可以发送 0，1 这样的信号，也就读出了磁盘上存储的 0，1 这样的二进制码。

• 为了不学的那么抽象，我们先来了解一点存储文件的磁盘硬件构造，知道电脑怎么存怎么取文件数据的。

• 从主机到磁盘： 主机 -> 磁盘控制器 -> 磁盘驱动器 -> 磁盘

• 磁盘驱动器主要是接受主机的命令，将它换成磁盘驱动器的控制命令，实现主机和驱动器之间的数据格式转换和数据传送，从而控制驱动器的读写。电脑也可以挂载多个磁盘，那么就会有多个磁盘驱动器。

2、磁盘、磁道、扇区

• 磁盘的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据，这个圆圆的东西就是盘片，磁头臂带动磁头进行转动，可以去到不同的磁道上面，磁道的概念如下：

• 磁盘的盘面被划分成一个个磁道，这样的一个“圈”就是一个磁道， 一个磁道（一圈）又被划分成一个个扇区，每个扇区就是一个“磁盘块”。

• 各个扇区存放的数据量相同(如1KB)，最内侧磁道上的扇区面积最小，因此其数据密度最大。

3、读取数据

• 需要先把“磁头”移动到想要读/写的扇区所在的磁道。磁盘会转起来，让目标扇区从磁头下面划过，才能完成对扇区的读/写操作。

• 因此整个的机械原理还是挺简单的，不是很复杂。

4、柱面号，盘面号，扇区号定位一个块

• 上面只是一个盘面的结构，实际上磁盘是有很多个这种盘面累计累积起来的，如下：

• 

• 每个盘面都有磁头，磁头被磁臂带动着往里或者往外移动，以读取到不同盘面的扇区。

  • 磁头数：等于记录面数；
  • 柱面数：表示硬盘每一面盘面上有多个磁道；
  • 扇区数：表示每一条磁道上有多少个扇区；

• 可用 (柱面号，盘面号，扇区号)来定位任意一个“磁盘块”，可根据文件地址读取到一个“块”号，

• 读写数据过程：

  1. 根据“柱面号”移动磁臂，让磁头指向指定柱面;
  2. 激活指定盘面对应的磁头;
  3. 磁盘旋转的过程中，指定的扇区会从磁头下面划过，这样就完成了对指定扇区的读/写。

• 值得注意，10张碟片只有18个磁头，因为最上面那个面和最下面那个面不记录任何信息，因此没有磁头。

5、磁盘分类

• 1. ​ 磁头可以移动的称为活动头磁盘，磁臂可以来回伸缩来带动磁头定位磁道。
  2. 不可移动的称为固定这种磁盘中每个磁道有一个磁头。
  3. 磁片可以更换的称为可换盘磁盘。
  4. 磁片不可以更换的称为不可换盘磁盘。

• 老式的留声机上使用的唱片和我们的磁盘盘片非常相似，只不过留声机只有一个磁头，而硬盘是上下双磁头，盘片在两个磁头中间高速旋转，如下：

• 也就是说，机械硬盘是上下盘面同时进数据读取的。而且机械硬盘的旋转速度要远高于唱片（目前机械硬盘的常见转速是 7200 r/min），所以机械硬盘在读取或写入数据时，非常害怕晃动和磕碰。另外，因为机械硬盘的超高转速，如果内部有灰尘，则会造成磁头或盘片的损坏，所以机械硬盘内部是封闭的，如果不是在无尘环境下，则禁止拆开机械硬盘。

6、磁盘小结

二、磁盘初始化

1、磁盘初始化

• 进行低级格式化(物理格式化)，将磁盘的各个磁道划分为扇区。一个扇区通常可分为 头、数据区域(如512B大小)、尾 三个部分组成。 管理扇区所需要的各种数据结构一般 存放在头、尾两个部分，包括扇区校验码(如奇偶校验、CRC 循环冗余校验码等，校验码用于校验扇区中的数据是否发生错误)

• 将磁盘分区，每个分区由若干柱面组成（即分为我们 熟悉的 C盘、D盘、E盘）

• 进行逻辑格式化，创建文件系统。包括创建文件系统的根目录、初始化存储空间管理所用的数据结构(如 位示图、 空闲分区表)

2、引导块

• 计算机开机时需要进行一系列初始化的工作，这些初始化工作是通过执行初始化程序(自举程序)完成的。

• 完整的自举程序放在磁盘的启动块(即**引导块/启动分区**)上，启动块位于磁盘的固定位置，拥有启动分区的磁盘称为 启动磁盘或 系统磁盘(C:盘)

• ROM寄存器中只存放很小的“自举装入程序”，开机时计算机先运行“自举装入程序”，通过执行该程序就可找到引导块，并将完整的“自举程序”读入内存，完成初始化。

三、磁盘调度算法

1、一次磁盘读/写操作需要的时间

• 寻找时间(寻道时间)TS：在读/写数据前，将磁头移动到指定磁道所花的时间。

  1. 启动磁头臂是需要时间的。假设耗时为 s;

  2. 移动磁头也是需要时间的。假设磁头匀速移动，每跨越一个磁道耗时为 m，总共需要跨越 n 条磁道。则:寻道时间 TS = s + m*n

• 延迟时间TR：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。 设磁盘转速为 r (单位:转/秒，或 转/分)，则 平均所需的延迟时间 TR = (1/2)*(1/r) = 1/2r

• 传输时间Tt：从磁盘读出或向磁盘写入数据所经历的时间，假设磁盘转速为 r，此次读/写的字节数为 b，每个磁道上的字节数为 N。则: 传输时间Tt = (1/r) * (b/N) = b/(rN)

2、内存管理请求分页五种置换算法回顾

• 在上一篇讲内存管理，请求分页的时候，在请求分页的时候我说了五种置换算法 ，如下：

• 内存分页，页面的换入、换出需要磁盘 I/O，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率。

• 再来看看磁盘分页，也有五种，先来先服务算法(FCFS)，最短寻找时间优先(SSTF)，都以假设磁头的初始位置是100号磁道，有多个进程先后陆续地请求访问 55、58、39、18、90、160、 150、38、184 号磁道为例，来看看各种方法的所需寻址时间。

3、先来先服务算法(FCFS)

• 根据进程请求访问磁盘的先后顺序进行调度。

• 按照 FCFS 的规则，按照请求到达的顺序，最开始磁头在100号位置，磁头需要依次移动到 55、58、39、18、90、160、150、 38、184 号磁道。

  1. 100-55=45 从第100号移动到55号需要移动的数量

  2. 58-55=3 从第55号移动到58号需要移动的数量

  3. 58-39=19 .....

  4. 39-18=21

  5. 90-18=72

• 磁头总共移动了 45+3+19+21+72+70+10+112+146 = 498 个磁道。

• 响应一个请求平均需要移动 498/9 = 55.3 个磁道(平均寻找长度)

• 优点：公平;如果请求访问的磁道比较集中的话，算法性能还算过的去

• 缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能上很差，寻道时间长。

4、最短寻找时间优先(SSTF)

• SSTF 算法会优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。(其实就是贪心算法的思想，只是选择眼前最优，但是总体未必最优)

• 磁头总共移动了 (100-18) + (184-18) = 248 个磁道， 响应一个请求平均需要移动 248/9 = 27.5 个磁道(平均寻找长度)

• 优点：性能较好，平均寻道时间短

• 缺点：可能产生“饥饿”现象

• Eg：本例中，如果在处理18号磁道的访问请求时又来了一个38号磁道的访问请求，处理38号磁道 的访问请求时又来了一个18号磁道的访问请求。如果有源源不断的 18号、38号磁道的访问请求 到来的话，150、160、184 号磁道的访问请求就永远得不到满足，从而产生“饥饿”现象。

产生饥饿的原因在于:磁头在一个小区域内来回来去地移动

5、扫描算法(SCAN)

• SSTF 算法会产生饥饿的原因在于:磁头有可能在一个小区域内来回来去地移动。为了防止这个问题，可以规定，只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。这就是扫描算法(SCAN)的思想。由于磁头移动的方式很像电梯，因此也叫电梯算法。

• 假设某磁盘的磁道为 0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。

• 磁头总共移动了 (200-100) + (200-18) = 282 个磁道， 响应一个请求平均需要移动 282/9 = 31.3 个磁道(平均寻找长度)

• 优点:性能较好，平均寻道时间较短，不会产生饥饿现象

• 缺点:

  1. 只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了。

  2. SCAN算法对于各个位置磁道的响应频率不平均(如:假设此时磁头正在往右移动，且刚处理过 90号磁道，那么下次处理90号磁道的请求就需要等磁头移动很长一段距离;而响应了184号磁道的请求之后，很快又可以再次响应184 号磁道的请求了)

6、LOOK 调度算法

• 扫描算法(SCAN)中，只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了。LOOK 调度算法就是为了解决这个问题，如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向。(边移动边观察，因此叫 LOOK)

• 假设某磁盘的磁道为 0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向 移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道.

• 磁头总共移动了 (184-100) + (184-18) = 250 个磁道, 响应一个请求平均需要移动 250/9 = 27.5 个磁道(平均寻找长度)

• 优点：比起 SCAN 算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短.

7、循环扫描算法(C-SCAN)

• SCAN算法对于各个位置磁道的响应频率不平均，而 C-SCAN 算法就是为了解决这个问题。规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。

• 假设某磁盘的磁道为 0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。

• 磁头总共移动了 (200-100) + (200-0) + (90-0)= 390 个磁道, 响应一个请求平均需要移动 390/9 = 43.3 个磁道(平均寻找长度)。

• 优点：比起SCAN 来，对于各个位置磁道的响应频率很平均。

• 缺点：只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求后就不需要再往右移动磁头了;并且，磁头返回时其实只需要返回到18号磁道即可，不需要返回到最边缘的磁道。另外，比起SCAN算法来，平均寻道时间更长。

8、C-LOOK 调度算法

• C-SCAN 算法的主要缺点是只有到达最边上的磁道时才能改变磁头移动方向，并且磁头返回时不一定需要返回到最边缘的磁道上。C-LOOK 算法就是为了解决这个问题。如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。

• 还是上面的例子：

• 磁头总共移动了 (184-100) + (184-18) + (90-18)= 322 个磁道 响应一个请求平均需要移动 322/9 = 35.8 个磁道(平均寻找长度)

• 优点：比起 C-SCAN 算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间 进一步缩短。

四、文件分配方式

上一篇在讲操作系统内存管理的时候，也从内存空间的连续分配讲到了非连续分配的段页式分配，一步一步优化之后才有段页式分配。历史又在重演，文件系统也有连续分配和非连续分配方式。

1、连续分配

• 连续分配方式要求每个文件在磁盘上占有一组连续的块，类似于数组。

• 特点：读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长。

• 若此时文件A要拓展，需要再增加一个磁盘块(总共需要连续的4个磁盘块)。 由于采用连续结构，因此文件A占用的磁盘块必须是连续的。 因此只能将文件A全部“迁 移”到绿色区域。

• 优点: 支持顺序访问和直接访问(即随机访问)；连续分配的文件在顺序访问时速度最快；

• 缺点: 不方便文件拓展;存储空间利用率低，会产生磁盘碎片；

这个优缺点，在内存管理使用这种方式也会出现，只不过是针对内存的问题，感兴趣的可以去看看我的上一篇文章。

2、非连续分配

2.1 隐式链接

• 通过在每个盘快上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表。

• 读数据过程： 用户给出要访问的逻辑块号 i，操作系统找到该文件对应的目录项(FCB，即文件控制块，下面会说)。 从目录项中找到起始块号(即0号块)，将0 号逻辑块读入内存，由此知道1号逻辑块存放的物理块号，于是读入1号逻辑块，再找 到2号逻辑块的存放位置......以此类推。 因此，读入i号逻辑块，总共需要 i+1 次磁盘 I/O。

• 缺点：采用链式分配(隐式链接)方式的文件，只支持顺序访问，不支持随机访问，查找效率低。另外，指向下一个盘块的指针也需要耗费少量的存储空间。

• 优点：此时要拓展文件，则可以随便找一个空闲磁盘块，挂到文件的磁盘块链尾，并修改文件的FCB即可，方便扩展，并且所有的空闲盘块都可以被利用，没有内存碎片。

2.2 显示链接

• 把用于链接文件各物理块的指针显式地存放在一张表中。即 文件分配表(FAT，File Allocation Table)

• 注意：一个磁盘仅设置一张FAT。 开机时，将FAT读入内存，并常驻内存。FAT 的各个表项在物理上连续存储，且每一个表项长度相同，因此“物理块号”字段可以是隐含的。

• 读取磁盘：用户给出要访问的逻辑块号 i，操作系统找到该文件对应的目录项 (FCB)。 从目录项中找到起始块号，若i>0，则查询内存中的文件分配表FAT， 往后找到 i 号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作。

• 相较于隐式分配的优点：采用链式分配(显式链接)方式的文件，支持顺序访问，也支持随机访问(想访问 i 号逻辑块时，并不需要依次访问之前的 0 ~ i-1 号逻辑块)，**由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多。**其他的隐式分配具有的优点他都有。

• 缺点就是：文件分配表的需要占用一定的存储空间。

3、索引分配

• 索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块(索引表的功能类似于内存管理中的页表——建立逻辑页面到物理页之间的映射关系)。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

​ 其实上篇内存管理看懂了，理解文件管理很容易，内存段页式的管理也就是索引方式，内存管理和文件管理是很相似的，因为CPU不可以直接操作外存文件系统，都要通过先进行 IO 把数据读入内存，然后再操作文件，因此文件系统和内存管理系统越相似，读取的时候效率越高越方便，所以为了减少难度，操作系统的设计者在设计的时候肯定都是考量过的，尽量多抽象，设计成相似的管理模式。

• 读取数据： 用户给出要访问的逻辑块号 i，操作系统找到该文件对应的目录项(FCB)... 从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可查询到 i 号 逻辑块在外存中的存放位置。

• 可见，索引分配方式可以支持随机访问。文件拓展也很容易实现(只需要给文件分配 一个空闲块，并增加一个索引表项即可)，但是索引表需要占用一定的存储空间。

3.1 链接方式

• 链接方案:如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。
• 

• 问题： 假设磁盘块大小为1KB=1024B，一个索引表项占4B，则一个磁盘块只能存放 256 个索引项。 若一个文件大小为 256*256KB = 65536 KB = 64MB，该文件共有 256*256 个块，也就对应 256*256个索引项，也就需要 256 个索引块来存储，这些索引块用链接方链接起来。

若想要访问文件的最后一个逻辑块， 就必须找到最后一个索引块(第256 个索引块)，而各个索引块之间是用指针链接起来的，因此必须先顺序地读入前 255 个索引块。

显然，在文件很大的时候，非常的低效，需要一直遍历链表。于是引申出来了下面的多级链表。

3.2 多级索引

• 多层索引：建立多层索引(原理类似于多级页表)。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。

• 扩展： 一个UNIX系统使用1KB磁盘块和4字节磁盘地址。如果每个i节点中有10个直接表项以及一个一次间接块、一个二次间接块和一个三次间接块，文件的最大尺寸是多少？

• 答：一个一次间接块指向1KB/4B=256个磁盘块，则对于每个i节点，直接表项记录（第四级）10个磁盘块，一级索引记录256个磁盘块，二级索引记录256^2个磁盘块，三级索引记录(256^2)^2个磁盘块，文件最大尺寸为(10+2^8+2^16+2^32)×1KB ≈ 4TB

3.3 混和索引

• 混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引(直接指向数据块)，又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表) 。

4、小结

五、文件存储空间管理

• 前面花了很多篇幅说的都是文件分配，这里就说说回收和空闲块的管理。

• 不知道有没有朋友关注到，这里的空闲块怎么管理？

• 安装 Windows 操作系统的时候，一个必经步骤是——为磁盘分区(C: 盘、D: 盘、E: 盘等)

1、空闲表法

• 适用于“连续分配方式”。

• 假设此时删除了某文件， 系统回收了它占用的 15、16、17号块

2、空闲链表法

空闲盘块链：

• 操作系统保存着链头、链尾指针。

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

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

空闲盘区链：

• 操作系统保存着链头、链尾指针。

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

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

3、位示图法😣

• 连续分配、离散分配都适用。

• 说明：每个二进制位对应一个盘块。“0”代表盘块空闲， “1”代表盘块已分配。

• 分配；若文件需要K个块，先顺序扫描位示图，找到K个相邻或不相邻 的“0”;再根据字号、位号算出对应的盘块号，将相应盘块分配给文件; 最后将相应位设置为“1”。

• 回收：先根据回收的盘块号计算出对应的字号、位号;再将相应二进制位设为“0”。

4、成组链接法😣

• 空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。

• UNIX系统中采用了成组链接法对磁盘空闲块进行管理。

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

• 分配： 需要100个空闲块

  • 1. 检查第一个分组的块数是否足够。100=100，是足够的。
    2. 分配第一个分组中的100个 空闲块。但是由于300号块内存放了再下一组的信息，因此 300号块的数据需要复制到超级块中。

• 回收： 假设每个分组最多为 100 个空闲块，此时第一个分组已有99个块，还要再回收一块。

• 需要将超级块中的数据复制到新回收的块中，并修改超级块的内容，让新回收的块成为第一个分组。

六、文件分类

• 按文件是否有结构分类，可以分为无结构文件、有结构文件两种。

1、无结构文件

• 文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”。如: Windows 操作系统中的 .txt 文件。

2、有结构文件

• 由一组相似的记录组成，又称“记录式文件”。每条记录由若干个数据项组成。如: 数据库表文件，mysql表里面存的就都是有结构数据。

七、文件目录

文件控制块

• 操作系统在对进程管理的时候有个进程控制块 PCB， 操作系统在文件管理的时候也引入了文件控制块 FCB， 如上图所示，里面是一个个目录项。

  • 为了能对一个文件进行正确的存取，操作系统必须为文件设置用于描述和控制文件的数据结构，称之为“文件控制块（FCB）”。

• 目录操作：

  1. 搜索：当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项

  2. 创建文件：创建一个新文件时，需要在其所属的目录中增加一个目录项

  3. 删除文件：当删除一个文件时，需要在目录中删除相应的目录项

  4. 显示目录：用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性

  5. 修改目录：某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项(如:文件重命名)

当我们双击“电子书”后，操作系统会在这个目录表中找到关键字“电子书”对应的目录项(也就是记录)，然后从外存中将“电子书”目录的信息读入内存，于是，“电子书”目录中的内容就可以显示出来了。

八、文件系统的层次结构

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

  1. 用户需要通过操作系统提供的接口发出上述请求——用户接口

  2. 由于用户提供的是文件的存放路径，因此需要操作系统一层一层地查找目录，找到对应的目录项——文件目录系统

  3. 不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限——存取控制模块(存取控制验证层)

  4. 验证了用户的访问权限之后，需要把用户提供的**“记录号”转变为对应的逻辑地址**——逻辑文件系统与文件信息缓冲区

  5. 知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址——物理文件系统

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

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

九、目录结构

1、单级目录结构

• 早期操作系统并不支持多级目录，整个系统中只建立一张目录表，每个文件占一个目录项。

• **单级目录实现了“按名存取”，但是不允许文件重名。**在创建一个文件时，需要先检查目录表中有没有重名文件，确定不重名后才能允许建立文件，并将新文件对应的目录项插入目录表中。
• 显然，单级目录结构不适用于多用户操作系统。

2、两级目录结构

• 早期的多用户操作系统，采用两级目录结构。分为主文件目录(MFD，Master File Directory)和用户文件目录(UFD，User Flie Directory)。

两级目录结构允许不同用户的文件重名，也可以在目录上实现实现访问限制（检查此时登录的用户名是否匹配 ),但是两级目录结构依然缺乏灵活性，用户不能对自己的文件进行分类

3、多级目录结构

• 又称为树形结构。

• 用户(或用户进程)要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。各级目录之间 用“/”隔开。从根目录出发的路径称为绝对路径。

例如：自拍.jpg 的绝对路径是 “/照片/2015-08/自拍.jpg” 系统根据绝对路径一层一层地找到下一级目录。

• 刚开始从外存读入根目录的目录表;找到“照片”目录的存放位置后，从外存读入对应的目录表;

• 再找到“2015-08”目录的存放位置，再从外存读入对应目录表;

• 最后才找到文件“自拍.jpg”的存放位置。整个过程需要3次读磁盘I/O操作。

• 很多时候，用户会连续访问同一目录内的多个文件(比如:接连查看“2015-08”目录内的多个照片文件)，显然，每次都从根目录开始查找，是很低效的。因此可以设置一个“当前目录”。

1. 例如，此时已经打开了“照片”的目录文件，也就是说，这张目录表已调入内存，那么可以把它设置为 “当前目录”。当用户想要访问某个文件时，可以使用从当前目录出发的“相对路径” 。

2. 在 Linux 中，“.”表示当前目录，因此如果“照片”是当前目录，则”自拍.jpg”的相对路径为: “./2015-08/自拍.jpg”。从当前路径出发，只需要查询内存中的“照片”目录表，即可知道”2015-08”目录 表的存放位置，从外存调入该目录，即可知道“自拍.jpg”存放的位置了。 可见，引入“当前目录”和“相对路径”后，磁盘I/O的次数减少了。这就提升了访问文件的效率。

3. 这个地方可以想一下著名面试题为什么mysql索引使用b+树结构，而不使用红黑树结构？

• 优缺点：树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。但是，树形结构不便于实现文件的共享。为此，提出了“无环图目录结构”。

4、无环图目录结构

• 可以用不同的文件名指向同一个文件，甚至可以指向同一个目录(共享同一目录下的所有内容)。

• 需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点。 只有共享计数器减为0时，才删除结点。

• 注意:共享文件不同于复制文件。在共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化。

5、索引结点 FCB 的改进

• 除了文件名之外的文件描述信息都放到索引节点里。

• 假设一个FCB是64B，磁盘块的大小为1KB，则每个盘块中只能存放 16个FCB。若一个文件目录中共有 640个目录项，则共需要占用 640/16 = 40 个盘块。因此按照某文件名检索该目录，平均需要查询320个目录项，平均需要启动磁盘20次(每次磁盘I/O读入一块)。

• 若使用索引结点机制，文件名占14B，索引结点指针站2B，则每个盘块可存放64个目录项，那么按文件名检索目录平均只需要 读入 320/64 = 5 个磁盘块。显然，这将大大提升文件检索速度。

十、虚拟文件系统

（linux 文件系统源码实现）

• 通常我们使用的磁盘和光盘都属于块设备，也就是说它们都是按照数据块来进行读写的，可以把磁盘和光盘想象成一个由数据块组成的巨大数组。但这样的读写方式对于人类来说不太友好，所以一般要在磁盘或者光盘上面挂载文件系统才能使用。

• 那么什么是文件系统呢？

  • 文件系统是一种存储和组织数据的方法，它使得对其访问和查找变得容易。通过挂载文件系统后，我们可以使用如 /home/docs/test.txt 的方式来访问磁盘中的数据，而不用使用数据块编号来进行访问。

• 在Linux系统中，可以使用多种文件系统来挂载不同的设备，如 ext2、ext3、nfs等等。但提供给用户的文件处理接口是一致的，也就是说不管使用 ext2 文件系统还是使用 ext3 文件系统，处理文件的接口都是一样的。这样的好处是，用户不用关心使用了什么文件系统，只需要使用统一的方式去处理文件即可。那么Linux是如何做到的呢？这就得益于 虚拟文件系统(Virtual File System，简称 VFS)。

• **虚拟文件系统，**为不同的文件系统定义了一套规范，各个文件系统必须按照 虚拟文件系统的规范 编写才能接入到 虚拟文件系统 中。这有点像面向对象语言里面的 "接口"，当一个类实现了某个接口的所有方法时，便可以把这个类当做成此接口。VFS 主要为用户和内核架起一道桥梁，用户可以通过 VFS 提供的接口访问不同的文件系统。

• NFS文件系统：NFS文件系统**，是一个分布式的网络文件系统**，集群模式下各台机器只需要挂载这个NFS都可以访问数据。

• 如下看看原文章作者公司NFS磁盘占用情况：

1、虚拟文件系统的数据结构

• 因为要为不同类型的文件系统定义统一的接口层，所以 VFS 定义了一系列的规范，真实的文件系统必现按照 VFS 的规范来编写程序。VFS 抽象了几个数据结构来组织和管理不同的文件系统，分别为：超级块（super_block）、索引节点（inode）、目录结构（dentry） 和 文件结构（file），要理解 VFS 就必须先了解这些数据结构的定义和作用。

2、超级块（spuer block）

• 因为Linux支持多文件系统，所以在内核中必须通过一个数据结构来描述具体文件系统的信息和相关的操作等，VFS 定义了一个名为 超级块（super_block） 的数据结构来描述具体的文件系统，也就是说内核是通过超级块来认知具体的文件系统的，一个具体的文件系统会对应一个超级块结构，其定义如下（由于super_block的成员比较多，所以这里只列出部分）：

struct file_system_type {
    const char *name;
    int fs_flags;
    struct super_block *(*read_super) (struct super_block *, void *, int); // 读取设备中文件系统超级块的方法
    ...
};

struct super_operations {
    void (*read_inode) (struct inode *);        // 把磁盘中的inode数据读取入到内存中
    void (*write_inode) (struct inode *, int);  // 把inode的数据写入到磁盘中
    void (*put_inode) (struct inode *);         // 释放inode占用的内存
    void (*delete_inode) (struct inode *);      // 删除磁盘中的一个inode
    void (*put_super) (struct super_block *);   // 释放超级块占用的内存
    void (*write_super) (struct super_block *); // 把超级块写入到磁盘中
    ...
};

struct super_block {
    struct list_head    s_list;     /* Keep this first */
    kdev_t              s_dev;         // 设备号
    unsigned long       s_blocksize;   // 数据块大小
    unsigned char       s_blocksize_bits;
    unsigned char       s_lock;
    unsigned char       s_dirt;       // 是否脏
    struct file_system_type *s_type;  // 文件系统类型
    struct super_operations *s_op;    // 超级块相关的操作列表
    struct dquot_operations *dq_op;
    unsigned long       s_flags;
    unsigned long       s_magic;
    struct dentry       *s_root;      // 挂载的根目录
    wait_queue_head_t   s_wait;

    struct list_head    s_dirty;    /* dirty inodes */
    struct list_head    s_files;

    struct block_device *s_bdev;
    struct list_head    s_mounts;
    struct quota_mount_options s_dquot;

    union {
        struct minix_sb_info    minix_sb;
        struct ext2_sb_info ext2_sb;
        ...
    } u;
    ...
};

一些重要的成员：

• s_dev：用于保存设备的设备号

• s_blocksize：用于保存文件系统的数据块大小（文件系统是以数据块为单位的）

• s_type：文件系统的类型（提供了读取设备中文件系统超级块的方法）

• s_op：超级块相关的操作列表

• s_root：挂载的根目录

3、索引节点（inode）

• 分析上面的超级块操作方法 struct super_operations 中，大部分都是对 inode 索引节点的操作，索引节点（inode） 是 VFS 中最为重要的一个结构，用于描述一个文件的 meta（元）信息，==其包含的是诸如文件的大小、拥有者、创建时间、磁盘位置等和文件相关的信息，所有文件都有一个对应的 inode 结构==。

  inode 的定义如下（由于inode的成员也是非常多，所以这里也只列出部分成员，具体可以参考Linux源码）：

struct inode_operations {
    int (*create) (struct inode *,struct dentry *,int);
    struct dentry * (*lookup) (struct inode *,struct dentry *);
    int (*link) (struct dentry *,struct inode *,struct dentry *);
    int (*unlink) (struct inode *,struct dentry *);
    int (*symlink) (struct inode *,struct dentry *,const char *);
    ...
};

struct file_operations {
    struct module *owner;
    loff_t (*llseek) (struct file *, loff_t, int);
    ssize_t (*read) (struct file *, char *, size_t, loff_t *);
    ssize_t (*write) (struct file *, const char *, size_t, loff_t *);
    ...
};

struct inode {
    ...
    unsigned long       i_ino;
    atomic_t            i_count;
    kdev_t              i_dev;
    umode_t             i_mode;
    nlink_t             i_nlink;
    uid_t               i_uid;
    gid_t               i_gid;
    kdev_t              i_rdev;
    loff_t              i_size;
    time_t              i_atime;
    time_t              i_mtime;
    time_t              i_ctime;
    ...
    struct inode_operations *i_op;
    struct file_operations  *i_fop;
    struct super_block      *i_sb;
    ...
    union {
        struct minix_inode_info     minix_i;
        struct ext2_inode_info      ext2_i;
        ...
    } u;
};

inode 中几个比较重要的成员：

• i_uid：文件所属的用户

• i_gid：文件所属的组

• i_rdev：文件所在的设备号

• i_size：文件的大小

• i_atime：文件的最后访问时间

• i_mtime：文件的最后修改时间

• i_ctime：文件的创建时间

• i_op：inode相关的操作列表

• i_fop：文件相关的操作列表

• i_sb：文件所在文件系统的超级块

• 我们应该重点关注 i_op 和 i_fop 这两个成员。
  • i_op 成员定义对目录相关的操作方法列表，譬如 mkdir()系统调用会触发 inode->i_op->mkdir() 方法，而 link() 系统调用会触发 inode->i_op->link() 方法。
  • 而 i_fop 成员则定义了对打开文件后对文件的操作方法列表，譬如 read() 系统调用会触发 inode->i_fop->read() 方法，而 write() 系统调用会触发 inode->i_fop->write() 方法。

4、目录项（dentry）

• 目录项是由内核维护的一个数据结构，不存放于磁盘，而是缓存在内存。
• 目录项的主要作用是方便查找文件。一个路径的各个组成部分，不管是目录还是普通的文件，都是一个目录项对象。如，在路径 /home/liexusong/example.c 中，目录 /, home/, liexusong/ 和文件 example.c 都对应一个目录项对象。不同于前面的两个对象(索引节点和超级块)，目录项对象没有对应的磁盘数据结构，==VFS 在遍历路径名的过程中现场将它们逐个地解析成目录项对象==。其定义如下：

struct dentry_operations {
    int (*d_revalidate)(struct dentry *, int);
    int (*d_hash) (struct dentry *, struct qstr *);
    int (*d_compare) (struct dentry *, struct qstr *, struct qstr *);
    int (*d_delete)(struct dentry *);
    void (*d_release)(struct dentry *);
    void (*d_iput)(struct dentry *, struct inode *);
};

struct dentry {
    ...
    struct inode  * d_inode;    // 目录项对应的inode
    struct dentry * d_parent;   // 当前目录项对应的父目录
    ...
    struct qstr d_name;         // 目录的名字
    unsigned long d_time;
    struct dentry_operations  *d_op; // 目录项的辅助方法
    struct super_block * d_sb;       // 所在文件系统的超级块对象
    ...
    unsigned char d_iname[DNAME_INLINE_LEN]; // 当目录名不超过16个字符时使用
};

5、文件结构（file）

• 文件结构用于描述一个已打开的文件，其包含文件当前的读写偏移量，文件打开模式和文件操作函数列表等，文件结构定义如下：

  struct file {
      struct list_head         f_list;
      struct dentry           *f_dentry;  // 文件所属的dentry结构
      struct file_operations  *f_op;      // 文件的操作列表
      atomic_t                 f_count;   // 计数器（表示有多少个用户打开此文件）
      unsigned int             f_flags;   // 标识位  
      mode_t                   f_mode;    // 打开模式
      loff_t                   f_pos;     // 读写偏移量
      unsigned long            f_reada, f_ramax, f_raend, f_ralen, f_rawin;
      struct fown_struct       f_owner;   // 所属者信息
      unsigned int             f_uid, f_gid;  // 打开的用户id和组id
      int                      f_error;
      unsigned long            f_version;
  
      /* needed for tty driver, and maybe others */
      void                    *private_data;
  };
  

6、数据结构之间的关系表

7、虚拟文件系统的实现

• 这一个小节涉及到很多具体实现，可看可不看。

• 注册文件系统 Linux为了支持不同的文件系统而创造了虚拟文件系统，虚拟文件系统更像一个规范(或者说接口)，真实的文件系统需要实现虚拟文件系统的规范(接口)才能接入到Linux内核中。

  要让Linux内核能够发现真实的文件系统，那么必须先使用 register_filesystem() 函数注册文件系统。

  register_filesystem() 函数的实现很简单，就是把类型为 struct file_system_type 的 fs 添加到 file_systems 全局链表中。

  当安装Linux系统时，需要把磁盘格式化为指定的文件系统，其实格式化就是把文件系统超级块信息写入到磁盘中。但Linux系统启动时，就会遍历所有注册过的文件系统，然后调用其 read_super() 接口来尝试读取超级块信息，因为每种文件系统的超级块都有不同的魔数，用于识别不同的文件系统，所以当调用 read_super() 接口返回成功时，表示读取超级块成功，而且识别出磁盘所使用的文件系统。

  成功读取超级块信息后，会把根目录的 dentry 结构保存到当前进程的 root 和 pwd 字段中，root 表示根目录，pwd 表示当前工作目录。

8、打开文件

• 要使用一个文件前必须打开文件，打开文件使用 open() 系统调用来实现，而 open() 系统调用最终会调用内核的 sys_open() 函数。

• sys_open() 函数的主要流程是：

  • 通过调用 get_unused_fd() 函数获取一个空闲的文件描述符。
  • 调用 filp_open() 函数打开文件，返回打开文件的file结构。
  • 调用 fd_install() 函数把文件描述符与file结构关联起来。
  • 返回文件描述符，也就是 open() 系统调用的返回值。

最终会调用 inode结构 的 create() 方法来创建文件。这个方法由真实的文件系统提供，所以真实文件系统只需要把创建文件的方法挂载到 inode结构上即可，虚拟文件系统不需要知道真实文件系统的实现过程，这就是虚拟文件系统可以支持多种文件系统的真正原因。

9、读写文件

• 读取文件内容通过 read() 系统调用完成，而 read() 系统调用最终会调用 sys_read() 内核函数。

  • sys_read() 函数首先会调用 fget() 函数把文件描述符转换成 file结构，然后再通过调用 file结构 的 read() 方法来读取文件内容，read() 方法是由真实文件系统提供的，所以最终的过程会根据不同的文件系统而进行不同的操作，比如ext2文件系统最终会调用 generic_file_read() 函数来读取文件的内容。

• 把内容写入到文件是通过调用 write() 系统调用实现，而 write() 系统调用最终会调用 sys_write() 内核函数。

  • sys_write() 函数的实现与 sys_read() 类似，首先会调用 fget() 函数把文件描述符转换成 file结构，然后再通过调用 file结构 的 write() 方法来把内容写入到文件中，对于ext2文件系统，write() 方法对应的是 ext2_file_write() 函数。

十一、缓存 I/O && 直接 I/O

• 缓存I/O 的引入是为了减少对块设备的 I/O 操作，但是由于读写操作都先要经过缓存，然后再从缓存复制到用户空间，所以多了一次内存复制操作。

• 缓存 I/O 的优点是减少对块设备的 I/O 操作，而缺点就是需要多一次的内存复制。另外，有些应用程序需要自己管理 I/O 缓存的（如数据库系统），那么就需要使用直接 I/O 了。

• 上图中红色框部分就是 缓存I/O 所在位置，位于 虚拟文件系统 与 真实文件系统 中间。

• 也就是说，当虚拟文件系统读文件时，首先从缓存中查找要读取的文件内容是否存在缓存中，如果存在就直接从缓存中读取。对文件进行写操作时也一样，首先写入到缓存中，然后由操作系统同步到块设备（如磁盘）中。

• 其实内存管理里面，为了解决CPU速度和磁盘IO速度差距不匹配的问题，也引入了三级高速缓存设备，其中为了解决多核CPU并发引起的各个CPU缓存的数据不一致问题，引入了缓存一致性协议 MESI，这个协议是高并发安全访问内存实现的基础。

十二、 docker 镜像的实现

• Docker 底层有三驾马车，Namespace、CGroup 和 UnionFS（联合文件系统），UnionFS 是 Docker 镜像的基础。（Linux 的这三个设计，也被认为是 Linux 最美丽的设计，有了这个基础，才能实现docker，才有了后来的 k8s）。

• UnionFS（联合文件系统）是一种分层、轻量级并且高性能的文件系统，它支持对文件系统的修改作为一次提交来一层层的叠加，同时可以将不同目录挂载到同一个虚拟文件系统下。
• UnionFS 是 Docker 镜像的基础，镜像可以通过分层来进行继承，基于基础镜像（没有父镜像），可以制作各种具体的应用镜像。由于 Linux 下有多种的 UnionFS （如 AUFS、OverlayFS 和 Btrfs 等），所以我们以实现相对简单的 OverlayFS 作为分析对象。

1、UnionFS - OverlayFS

• 从上图可知，OverlayFS 文件系统主要有三个角色，lowerdir、upperdir 和 merged。

  • lowerdir 是只读层，用户不能修改这个层的文件；
  • upperdir 是可读写层，用户能够修改这个层的文件；
  • merged 是合并层，把 lowerdir 层和 upperdir 层的文件合并展示。

  使用 OverlayFS 前需要进行挂载操作，挂载 OverlayFS 文件系统的基本命令如下：

$ mount -t overlay overlay -o lowerdir=lower1:lower2,upperdir=upper,workdir=work merged

• 参数 -t 表示挂载的文件系统类型，这里设置为 overlay 表示文件系统类型为 OverlayFS，而参数 -o 指定的是 lowerdir、upperdir 和 workdir，最后的 merged 目录就是最终的挂载点目录。

2、OverlayFS 实现原理

• OverlayFS 文件系统的作用是合并 upper 目录和 lower 目录的中的内容，如果 upper 目录与 lower 目录同时存在同一文件或目录，那么 OverlayFS 文件系统怎么处理呢？

  • 如果 upper 和 lower 目录下同时存在同一文件，那么按 upper 目录的文件为准。比如 upper 与 lower 目录下同时存在文件 a.txt，那么按 upper 目录的 a.txt 文件为准。
  • 如果 upper 和 lower 目录下同时存在同一目录，那么把 upper 目录与 lower 目录的内容合并起来。比如 upper 与 lower 目录下同时存在目录 test，那么把 upper 目录下的 test 目录中的内容与 lower 目录下的 test 目录中的内容合并起来。

• 具体实现如下：

  在调用 ovl_dir_read() 函数读取 lower 和 upper 目录中的文件列表时会调用 ovl_fill_merge() 函数过滤相同的文件。过滤操作通过红黑树来实现，过滤过程如下：

  读取 upper 目录中的文件列表，保存到 list 列表中，并且保存到红黑树中。

  读取 lower 目录中的文件列表，查询红黑树中是否已经存在此文件，如果存在，那么跳过此文件，否则添加到 list 列表中。

总结

• Linux奉行了Unix的理念：一切皆文件，比如一个目录是一个文件，一个设备也是一个文件等，因而文件系统在Linux中占有非常重要的地位。