文件管理：文件的物理结构

1.文件的物理结构

逻辑结构：在用户看来，文件内部的数据是如何组织起来的
物理结构：在OS看来，文件的数据是如何放在外存（磁盘）中的

OS需要对空闲和非空闲（已存数据）的磁盘块进行管理
对非空闲块的管理：文件分配方式
对空闲块的管理：文件存储空间管理

1.1 文件分配方式

文件数据怎样存放在外存（磁盘）中
下图来自王道考研操作系统

1.1.1 连续分配

下图来自程序员cxuan

下图来自小林coding

下图来自王道考研操作系统

1.1.2 链接分配

1.1.2.1 隐式链接

下图来自王道考研操作系统

查找下一个磁盘块时需要根据磁盘块内指针来找到下一个磁盘块，这就需要移动磁头。这种工作形式就使得访问速度不会很快。隐式链接支持顺序访问，但不支持随机访问

下图来自程序员cxuan

1.1.2.2 显式链接

下图来自王道考研操作系统

文件分配表在内存中，从目录项中找到起始块号，若用户给出的逻辑块号合法（逻辑块号大于0），则查找FAT则可得到逻辑块号对应的物理块号，查询过程无需读取磁盘。支持随机访问（直接得到要访问的物理块号，无需从文件的第一个物理块号开始往后找），其实也支持顺序访问（从前往后找）

下图来自程序员cxuan
FAT文件分配表

1.1.3 索引分配

FAT需要占用较大的内存空间，在打开某个文件时，只需将该文件对应的磁盘块号调入内存即可，完全没有必要将整个FAT调入内存。为此，我们将每个文件的所有磁盘块号都集中放在一起构成索引块/表（放在磁盘中）

下图来自王道考研操作系统

若一个磁盘块可以存放256个索引项，但一个文件的索引项超过了256个我们应该采用什么方案？

方案一：链接方案
将多个索引块/表链接起来

若想访问文件的最后一个逻辑块，那就得先顺序访问完前面所有的逻辑块，显然效率很低。由此引出多层索引

方案二：多层索引

二层中二级索引表有256个，每一个二级索引表又对应256个，所以为256*256

除法结果为第几个逻辑块，取余结果为该逻辑块内的第几个表项

如果为两层索引，则访问目标数据块需要3次磁盘I/O
如果为三层索引，则访问目标数据块需要4次磁盘I/O

如果一个文件很小，用了两层索引后依然需要3次读磁盘

方案三：混合索引（可针对不同大小的文件建立不同索引方案）
既包含直接地址索引（直接指向数据块）、又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表）

下图来自本人笔记Linux文件系统

下图来自王道考研操作系统