文件的物理结构是指文件在外存上的存储组织形式,与存储介质的存储性能有关。常用的物理结构有连续文件结构、串联文件结构、索引文件结构三种。

1. 文件块

类似于内存分页，磁盘中的存储的单元也会被分为一个个的”块/磁盘块/物理块”很多操作系统中磁盘块的大小与内存块、页面的大小相同。

内存与磁盘间的数据交互(即读/写操作、磁盘IO) 都是以 “块” 为单位进行的。

在内存管理中，进程的逻辑地址空间被分为一个一个的页面，同样的，在外存管理中，为了方便对文件数据的管理文件的逻辑地址空间也被分为一个一个的文件块

于是文件的逻辑地址也可以表示为(逻辑块号，块内地址)的形式

2. 文件分配方式

2.1. 连续分配

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

用户通过逻辑地址来操作自己的文件,操作系统如何实现从逻辑地址到物理地址的映射?

(逻辑块号,块内地址)→(物理块号,块内地址)。只需转换块号,块内地址保持不变

文件目录中记录存放的起始块号和长度（总共占用几个块）

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

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

当然，还需要检查用户提供的逻辑块号是否合法（逻辑块号≥长度就不合法）

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

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

结论: 连续分配的文件在顺序读/写时速度最快

如图: 若此时文件 A 要拓展，需要再增加一个磁盘块（总共需要连续的4个磁盘块）。由于采用连续结构，因此
文件 A 占用的磁盘块必须是连续的。

因此只能将文件 A 全部“迁移”到绿色区域。

结论: 物理上采用连续分配的文件不方便拓展

物理上采用连续分配，存储空间利用率低，会产生难以利用的磁盘碎片可以用紧凑来处理碎片，但是需要耗费很大的时间代价。

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

优点

  • 支持顺序访问和直接访问（即随机访问〉：连续分配的文件在顺序访问时速度最快

缺点

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

2.2. 链接分配

链接分配采取离散分配的方式,可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。

2.2.1. 隐式链接

隐式链接除文件的最后一个盘块之外，每个盘块中都存有指向下一个盤块的指升。文件目录包括文件第一块的指针和最后一块的指针。

用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项 FCB
从目录项中找到起始块号（即0号块），将 0 号逻辑块读入内存，由此知道 1 号逻辑块存放的物理块号，乎是读入1号逻辑块，再找到 2 号逻辑块的存放位置，以此类推。因此，读入 i 号逻辑块，总共需要 i+1 次磁盘 IO。

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

若此时要拓展文件，则可以随便找一个空闲磁盘块，挂到文件的磁盘块链尾，并修改文件的 FCB

**结论: **采用隐式链接的链接分配方式，很方便文件拓展。另外，所有的空闲磁盘块都可以被利用，不会有碎片问题，外存利用率高。

2.2.2. 显示链接

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

假设某个新创建的文件 aaa 依次存放在磁盘块: 2->5->0->1
假设某个新创建的文件 bbb 依次存放在磁盘块: 4->23->3

目录中只需记录文件的起始块号

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

用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项(FCB) 从目录项中找到起始块号，若i>0，则查询内存中的文件分配表 FAT，往后找到 1 逻辑块对应的物理块号。

逻辑块号转换成物理块号的过程不需要读磁盘操作

**结论: ** 采用链式分配（显式链接）方式的文件，支持顺序访问，也支持随机访问（想访问i号逻辑块时，并不需要依次访问之前的0~i-1 号逻辑块），由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多。

显式链接也不会产生外部碎片，也可以很方便地对文件进行拓展。

2.3. 索引分配

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

假设某个新创建的文件 aa 的数据依次存放在磁盘块 2→5→13→9。7 号磁盘块作为 aa 的索引块，索引块中保存了索引表的内容。

**注意: **

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

索引表中的“逻辑块号〞可以是隐含的

2.3.1. 如何实现文件的逻辑块号到物理块号的转换?

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

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

2.3.2. 如何解决一个磁盘块是装不下文件的整张索引表的?

  1. 链接方案

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

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

  1. 多层索引

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

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

若采用多层索引，则各层索引表大小不能超过一个磁盘块

若某文件采用两层索引，则该文件的最大长度可以到 $2562561KB = 65,536 KB = 64MB$
可根据逻辑块号算出应该查找索引表中的哪个表项。

要访问 1026 号逻辑块，则 $1026/256= 4, 1026%256=2$
因此可以先将一级索引表调入内存，查询 4 号表项，将其对应的二级索引表调入内存，再查询二级索引表的 2 号表项即可知道 1026 号逻辑块存放的磁盘块号了。访问目标数据块，需要3次磁盘 I/O。
若采用三层索引，则文件的最大长度头 $256256256*1KB = 16GB$ 类似的，访问目标数据块，需要4次磁盘 I/O

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

  1. 混合索引

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

    这种结构的索引支持的最大文件长度为 65800 KB

    若顶级索引表还没读入内存

    • 访问0~7号逻辑块: 两次读磁盘
    • 访问 8~263: 三次读磁盘
    • 访问 264~65799: 四次读磁盘

    对于小文件，只需较少的读磁盘次数就可以访问目标数据块。（一般计算机中小文件更多）

3. 总结