> For the complete documentation index, see [llms.txt](https://lfool.gitbook.io/operating-system/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lfool.gitbook.io/operating-system/di-si-zhang-wen-jian-guan-li/3.-wen-jian-de-wu-li-jie-gou.md).

# 3. 文件的物理结构

**物理结构：**文件的数据是如何存放在外存中的

**文件块：**文件的逻辑地址空间也被分为一个一个的**文件块**【**逻辑块号，块内地址**】

**磁盘块：**磁盘的存储单元也会被分为一个个 **块/磁盘块/物理块**

## 1. 连续分配

**连续分配**要求**每个文件在磁盘上占有一组连续的块**

![](https://824295091-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEmUhsvIFBb8ar2-Um3%2F-MFVn_vU__1Q70TV3T48%2F-MFVntYYYcpOl_51BBs4%2Fimage.png?alt=media\&token=d09ab00e-0c04-4644-b691-3e189a578823)

![](https://824295091-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEmUhsvIFBb8ar2-Um3%2F-MFVn_vU__1Q70TV3T48%2F-MFVpGpwbKSF4yW6W8mh%2Fimage.png?alt=media\&token=a374fe97-9e0b-40e4-9eca-e4ee63abddbb)

文件目录中记录存放该文件在外存中的**起始块**和**长度**

用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB）

* **物理块号 = 起始块号 + 逻辑块号**

**优点：**

* 连续分配的文件在顺序读写时速度最快
* 连续分配可以支持**顺序访问** & **随机访问**

**缺点：**

* 不方便扩展。如果需要新增一个磁盘块，但连续的地方没有位置了，就需要把所有磁盘块一起移动到空间满足的位置
* 存储空间利用率低，会产生难以利用的磁盘碎片（可用紧凑技术处理碎片，但是时间代价大）

## 2. 链接分配

链接分配采用离散分配的方式，可以为文件分配离散的磁盘块，分为隐式链接 & 显示链接

### 2.1 隐式链接

除文件的最后一个盘块之外，每个盘块都存有指向下一个盘块的指针

![](https://824295091-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEmUhsvIFBb8ar2-Um3%2F-MFVqzp4gYCaGTb63ovP%2F-MFVrVAkd6wYgx-FkndX%2Fimage.png?alt=media\&token=87f319e9-2b74-4b85-8834-9ead85982ea9)

文件目录中记录存放该文件在外存中的**起始块号**和**结束块号**

用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB）

* 从目录项中找到起始块号（即 0 号块），将 0 号逻辑地址读入内存，由此知道 1 号逻辑块存放的物理地址，于是读入 1 号逻辑块，再找到 2 号逻辑块，以此类推...
* 因此，读入 i 号逻辑块，总共需要 i + 1 次磁盘 I/O

**扩展文件：**随便找到一个空闲磁盘块，挂到文件的磁盘块链尾，并修改文件的 FCB

**优点：**方便文件扩展，不会有碎片问题，外存利用率高

**缺点：**只支持顺序访问，不支持随机访问，查找效率低，指向下一个磁盘块的指针也需要消耗一定的存储空间

### 2.2 显示链接

把用于链接文件各物理块的指针显式地存放在一张表中，即**文件分配表（FAT）**

假设某个新创建的文件 “aaa” 依次存放在磁盘块 2 -> 5 -> 0 -> 1；假设某个新创建的文件 “bbb” 依次存放在磁盘块4 -> 23 -> 3。其文件分配表如下图所示：

![](https://824295091-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEmUhsvIFBb8ar2-Um3%2F-MFVu-6UNsEcQ3Cggo-w%2F-MFVu1phIN2Zv0ps2tq4%2Fimage.png?alt=media\&token=04036753-2846-46ff-9c84-9f9528a69ad0)

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

用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB）

* 从目录项中找到起始块号，若 i > 0，则查询内存中的文件分配表 FAT，往后找到 i 号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作

**优点：**很方便文件拓展，不会有碎片问题，外存利用率高，并且**支持随机访问**。相比于隐式链接来说，**地址转换时不需要访问磁盘，因此文件的访问效率更高**

**缺点：**文件分配表的需要占用一定的存储空间

## 3. 索引分配

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

![](https://824295091-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEmUhsvIFBb8ar2-Um3%2F-MFVvP35JOaqI_DXkqxD%2F-MFVvhhQdUyT39ugdXFh%2Fimage.png?alt=media\&token=e3801f6a-6d56-4f19-832f-ca5d9a399bc9)

**注：**在显式链接的链式分配方式中，**文件分配表FAT 是一个磁盘对应一张**。而索引分配方式中，**索引表是一个文件对应一张**

用户给出要访问的逻辑块号 i，操作系统找到该文件对应的目录项（FCB）

* 从目录项中可知索引表存放位置，将索引表 从外存读入内存，并查找索引表即可只 i 号逻辑块在外存中的存放位置

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

**问题：**如果一个文件的大小超过了256块，那么一个磁盘块是装不下文件的整张索引表的，如何解决这个问题？

### 3.1 链接索引

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

![](https://824295091-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEmUhsvIFBb8ar2-Um3%2F-MFVxF-f-wbJEbEsOF6g%2F-MFW-Ynm7vxESILhE48f%2Fimage.png?alt=media\&token=30d5c267-1851-4ae5-a9dd-fc71ed6083c8)

**存在问题：**如果需要访问第 256 块，需要先调出 7 号物理块对应的索引块，然后遍历到 255 号，知道第二个索引块，然后才能访问到 256 号，效率极低

### 3.2 多层索引

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

![](https://824295091-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEmUhsvIFBb8ar2-Um3%2F-MFW0XY33m_stcYyBEew%2F-MFW0YqlCCaIyTtRFMgu%2Fimage.png?alt=media\&token=d7778383-ced7-4ee0-8195-8d5a13fd6aa3)

假设磁盘块大小为 1KB，一个索引表项占 4B，则一个磁盘块只能存放 256 个索引

若某文件采用**两层索引**，则该**文件最大长度**可以到 256 \* 256 \* 1KB = 65536KB = 64MB

可以根据逻辑块号计算出应该查询索引表中的表项：

* 如：要访问 1026 号逻辑块，则 1026 / 256 = 4，1026 % 256 = 2
* 一级索引的 4 号块，二级索引的 2 号块

采用 K 层索引结构，且**顶级索引表未调入内存**，则访问一个数据块只需要 K + 1 次读写操作

### 3.3 混合索引

多种索引方式的结合。例如，一个文件的顶级索引表中，既包含**直接地址索引**（直接指向**数据块**），又包含**一级间接索引**（指向单层索引块），还包含**两级间接索引**（指向两层索引表）

![](https://824295091-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEmUhsvIFBb8ar2-Um3%2F-MFW2be1yvAK4NdEoTGF%2F-MFW2cg9bQ1GYesI843H%2Fimage.png?alt=media\&token=d992d32d-2948-4f68-b2d7-67d78d14c9c1)

### 3.4 总结

若文件太大，索引表项太多，可以采取以下三种方法解决：

* **链接方案：**
  * 如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放
  * **缺点：**若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到 i 号索引块，必须先依次读入0 \~ i - 1 号索引块，这就导致磁盘 I/O 次数过多，查找效率低下
* **多层索引：**
  * 建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。采用K 层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K + 1 次读磁盘操作
  * **缺点：**即使是小文件，访问一个数据块依然需要K+1次读磁盘
* **混合索引：**
  * 多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表）
  * **优点：**对于小文件来说，访问一个数据块所需的读磁盘次数更少

## 4. 总结

![](https://824295091-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEmUhsvIFBb8ar2-Um3%2F-MFW3sL0i3Wb-OfTClQ2%2F-MFW3xbmKCfd0RYI3VAB%2Fimage.png?alt=media\&token=0568db29-db2d-4555-8aea-d0a51f2ed5ee)